精华内容
下载资源
问答
  • 3 删除链表中指定元素 #include <stdio.h> #include <stdlib.h> #include<malloc.h> #include "test1.h" /* 创建一个结构体 */ typedef struct Node { int data;//数据 struct Node *nex...

    本段代码实现了

    1 新建链表

    2 输出链表

    3 删除链表中的指定元素

    #include <stdio.h>
    #include <stdlib.h>
    #include<malloc.h>
    #include "test1.h"
    
    /*
    创建一个结构体
    */
    typedef struct Node {
    	int data;//数据
    	struct Node *next;//下一个结点的指针
    }Node;
    int count = 0;//记录链表的长度
    
    Node *InitList() {
    	Node *head;//定义头指针
    	Node *q, *p;//定义两个结构体指针用于后面迭代
    	head = (Node *)malloc(sizeof(Node));
    	q = head;
    	while (1)
    	{
    		count++;
    		p = (Node *)malloc(sizeof(Node));
    		printf("请输入第%d个数: (如需结束输入0):   ", count);
    		scanf_s("%d", &p->data);
    		if (p->data == 0) {
    			return head;
    		}
    		//在迭代插入新的节点的过程中一直使P指向新的节点,q指向当前节点
    		p->next = NULL;
    		q->next = p;
    		q = p;
    	}
    }
    
    void showList(Node *m) {
    	Node *p;
    	p = m->next;//让p指针指向第一个节点
    	while (p!=NULL)
    	{	
    		//注意头指针的数据是不需要输出的
    		printf("%d\n", p->data);
    		p = p->next;
    	}
    }
    void DeleteListItem(Node *n,int x) {
    	Node *p,*q,*pre; //p为循环指针,q指向需要删除的指针, pre始终为当前指针的前一位,类似双链表
    	p = n->next;//让p指向第一个节点,跳过头节点
    	pre = n;
    	while (p!=NULL)
    	{
    		if (p->data==x)
    		{	
    			printf("找到要删除的数据%d---%d\n",p->data,x);
    			q = p;//q指针指向需要删除的指针
    			p = p->next;//循环指针跳到下一个位置
    			pre->next = p;//此时,可以理解为前驱节点跳过要删除的点,next指向P
    			free(q);//释放内存
    			count--;
    		}else
    		{
    			pre = p;
    			p = p->next;
    		}
    	}
    }
    
    int main() {
    	//创建好了一个链表
    	Node *m = InitList();
    	//输出链表中的数据信息
    	showList(m);
    	printf("请输入需要删除的元素: ");
    	int d;
    	scanf_s("%d", &d);
    	//删除链表中指定元素
    	DeleteListItem(m, d);
    	//删除完再输出数据
    	printf("删除了指定元素后的列表:\n", d);
    	printf("链表总长度为:%d\n", count);
    	showList(m);
    	system("pause");
    	return 0;
    }
    
    展开全文
  •  大家都知道,一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没,一个有序链表中又怎么样呢?让我们假设有这样一个链表,每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱...
    
    			

        大家都知道,在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没,在一个有序链表中又怎么样呢?让我们假设有这样一个链表,每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素(如果有的话)。另外,我们知道每个元素在内存中的地址,因此可以进行随机存取。或者可以说,这个有序链表中的所有元素都是储存在一个数组中的,但数组本身并不有序。
        现在,我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来?


     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
        下面是一个平均复杂度为O(√n)的算法。在数组中随机选取Θ(√n)个数,然后通过不断地比较更新,找出这些数当中比x小的最大的数(不妨记作p),以及比x大的最小的数(记作q)。从p所在的位置出发,沿着链表往下走,直到找到x或者走到q(表明x不在链表中)为止。
        可以证明,O(√n)已经是最优的了。

    展开全文
  • int *sum(int a,int b){//这个函数返回的是int类型指针 }
  • public interface Link { //定义行为标准 void add(Object obj);//增 boolean remove(int index);//删除指定位置数据 boolean set(int index,Object obj);//改变指定位置数据 Object get...//查找指定位置数据 int ...

    package www.bite.Link;


    public interface Link {  //定义行为标准
    void add(Object obj);//增
    boolean remove(int index);//删除指定位置数据
    boolean set(int index,Object obj);//改变指定位置数据
    Object get(int index);//查找指定位置数据
    int contains(Object obj);//确认数据是否存在
    void clear();//清除
    void printLink();//输出链表
    int length();//计算链表长度
    Object []toArray();//将链表转换成数组
    boolean addAt(int index,Object obj);

    }



    package www.bite.Link;


    class LinkImpl implements Link {  //实现接口行为
    private Node first;
    private Node last;
    private int size = 0;


    // ------------------定义链表内部内容


    private class Node {
    private Object data;
    private Node prav;
    private Node next;


    public Node(Node prav, Object data, Node next) {
    this.data = data;
    this.prav = prav;
    this.next = next;
    }
    }
    // ----------------------------


    @Override
    public void add(Object obj) { // 增
    Node temp = this.last;
    Node newNode = new Node(temp, obj, null);
    this.last = newNode;
    if (this.first == null) {
    this.first = newNode;
    } else {
    temp.next = newNode;
    }
    this.size++;


    }


    @Override
    public boolean remove(int index) { // 删除指定位置数据
    if(!isRight(index)) {
    return false;
    }
    Node node=node(index);
    if(node==this.first) {
    if(node==this.last) {
    node=null;
    this.size--;
    return true;
    }
    else {
    Node temp=this.first;
    this.first=node.next;
    temp.next=null;
    this.first.prav=null;
    this.size--;
    return true;
    }
    }
    else if(node==this.last){
    Node temp=this.last;
    this.last=node.prav;
    temp.prav=null;
    this.last.next=null;
    this.size--;
    return true;
    }
    node.next.prav=node.prav;
    node.prav.next=node.next;
    node.prav=node.next=null;
    this.size--;
    return true;
    }


    @Override
    public boolean set(int index, Object obj) { // 改变指定位置数据
    if (!isRight(index)) {
    return false;
    }
    Node node = node(index);
    node.data = obj;
    return true;
    }


    // 得到指定元素的位置
    private Node node(int index) {
    if (index < (size >> 1)) {
    Node result = this.first;
    for (int i = 0; i < index; i++) {
    result = result.next;
    }
    return result;
    }
    Node result = this.last;
    for (int i = size - 1; i > index; i--) {
    result = result.prav;
    }
    return result;
    }


    @Override
    public Object get(int index) { // 查找指定位置数据
    if (!isRight(index)) {
    return false;
    }


    return node(index).data;
    }


    @Override
    public int contains(Object obj) { // 确认数据是否存在


    if (obj == null) {
    int index = 0;
    for (Node node = first; node != null; node = node.next) {


    if (node.data.equals(obj)) {
    return index;
    }
    index++;
    }
    } else {
    int index = 0;
    for (Node node = first; node != null; node = node.next) {


    if (node.data.equals(obj)) {
    return index;
    }
    index++;
    }

    }
    return -1;
    }


    @Override
    public void clear() { // 清除
    for (Node a = this.first; a != null;) {
    Node b = a.next;
    a.prav = a.next = null;
    a = b;
    }
    this.size = 0;
    this.first = null;
    this.last = null;
    }


    @Override
    public void printLink() { // 输出链表
    Object[] result = this.toArray();
    for (Object obj : result) {
    System.out.println(obj);
    }


    }


    @Override
    public int length() { // 计算链表长度
    return this.size;
    }


    @Override
    public Object[] toArray() { // 将链表转换成数组
    Object[] result = new Object[size];
    int i = 0;
    for (Node temp = first; temp != null; temp = temp.next) {
    result[i++] = temp.data;
    }
    return result;
    }


    public boolean isRight(int index) {// 确认输入的数字是否合法
    return index >= 0 && index < size;
    }

    public boolean addAt(int index,Object obj) {
    if(index<0||index>size-1) {
    return false;
    }else if(index==0) {
    Node node=node(index);
    Node newnode=new Node(first, obj, node);
    node.prav=newnode;
    first=newnode;
    }else if(index==4) {
    Node node=node(index);
    Node newnode=new Node(node, obj, null);
    node.next=newnode;
    last=newnode;
    }

    else {
    Node node=node(index);
    Node newnode=new Node(node.prav, obj, node);
    node.prav.next=newnode;
    node.prav=newnode;
    }
    this.size++;
    return true;
    }

    }


    package www.bite.Link;


    public class Factory { //工厂模式,保证只new同一个对象
    private Factory() {

    }
    public static Link getInstance() {
    return new LinkImpl();

    }


    }

    package www.bite.Link;


    public class Main {
    public static void main(String[] args) {
    Link link=Factory.getInstance();
    link.add("火车头");
    link.add("车厢一");
    link.add("车厢二");
    link.add("车厢三");
    link.add("火车尾");
    //link.printLink();
    link.addAt(4, "火车1");
        link.printLink();
    // System.out.println("输出链表----------------");
    // System.out.println(link.length());
    // link.printLink();
    // System.out.println("输出链表长度的测试----------------");
    //
    // System.out.println(link.contains("车厢一"));
    // link.printLink();
    // System.out.println("确认元素是否存在的测试----------------");
    //
    // System.out.println(link.contains("车厢9"));
    // link.printLink();
    // System.out.println("确认元素是否存在的测试----------------");
    //
    // System.out.println(link.get(2));
    // link.printLink();
    // System.out.println("得到指定位置元素的测试----------------");
    //
    // link.set(2, "车厢1");
    // link.printLink();
    // System.out.println("更改指定位置元素的测试----------------");
    // link.clear();
    // link.printLink();
    // System.out.println("清除链表--------------");
    }


    }

    展开全文
  • [C语言]查找链表的中间元素

    千次阅读 2016-02-15 12:36:48
    查找链表的中间元素,最简便的方法之一,就是先遍历一遍链表,得到链表长度,再根据长度遍历得到中间的元素。我这里用的是快慢指针去查找,只需要遍历一次即可,快指针每次走两步,慢指针每次走一步,当快指针走完了...

    查找链表的中间元素,最简便的方法之一,就是先遍历一遍链表,得到链表长度,再根据长度遍历得到中间的元素。我这里用的是快慢指针去查找,只需要遍历一次即可,快指针每次走两步,慢指针每次走一步,当快指针走完了,慢指针所指位置即中间元素的位置,具体实现如下

    C代码实现

    struct ListNode {
        int val;
        struct ListNode *next;
    };
    
    /*
    ** 若链表元素为奇数个,则返回中间的元素,若链表元素为偶数个,则返回中间 元素偏左的一个 
    */
    struct ListNode* link_list_find_mid_ele(struct ListNode* head)
    {
        struct ListNode* fast, *slow;
    
        fast = head;
        slow = head;
    
        if(!head)
            return NULL;
    
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    
        return slow;
    }
    展开全文
  • 链表节点查找

    2017-08-08 14:12:38
    一个非空单向链表中(数据域的值没有重复)找到值为key的节点, 找到则返回节点的地址,否则返回nullElemSN* FindNode(ElemSN *h,int key) { ElemSN *p; for (p = h; p; p = p->next) { if (p->data == key) ...
  • // 链表基本操作.cpp : 定义控制台应用程序的入口点。 // // 链表基本操作.cpp : 定义控制台应用程序的入口点。 // #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef ...
  • C语言—链表查找

    千次阅读 2017-01-20 15:57:31
    我们以后想要得到的插入和删除,都是建立链表的查找之上,如果你想删除或者插入但是你却连位置都没有,这就很尴尬了,所以链表查找我觉得挺重要的,也是挺难理解的,因为只要理解这个后面的插入和删除功能,你自己...
  • Java链表查找、插入、删除等

    千次阅读 2018-09-16 00:10:28
    双向链表结构和单向链表的区别:最后一个结点的链接地址上,单向链表是null,而双向链表是表头的链接地址。 即双向链表的head和last互相指向 示意图   表头为空  head之前的节点是last=50这个节点 ,head...
  • /* head 为要查询的链表的头指针 */ SN *Get_S_Node = NULL; INT32 OSM = 1,i32i = 0, data_num = 0; /* OSM是标志符,i32i是一个循环体内的变量,data为要获取的元素的序号 */ Get_S_Node = ( SN * )
  • 链表指定位置输出

    2017-07-19 17:00:15
    当输入1时,输出链表中第一元素的数, 同理,输入3, 输出第三个元素
  • C++单向链表-查找某个节点

    千次阅读 2016-04-14 08:33:36
    本算法从下标1开始遍历 利用双指针的形式遍历, 大大提高了代码的查找速度: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (pListHead == NULL || k ==0) { return NULL; } ListNode*...
  • //查找指定数据的节点位置 if (ptemp == head->next) { //判断是不是头结点的下一个节点,如果是就从头部删了它 DeleteElemAtHead(); } else { ElemType * p = head; //p指向头结点 while (p->...
  • ``` typedef struct LNode { int data; struct LNode* next; }LNode,*LinkList; LinkList LocalElem(LinkList a,int e) { LNode* p=a->next; int i=1;...(代码里面省略了创建链表的部分)
  • p指针用来找链表中数字为x的位置,pre指针始终指向p指针所指向位置的前一个位置 最好自己纸上模拟一下 代码: #include&lt;bits/stdc++.h&gt; using namespace std; typedef struct Node { int value...
  • L是一个带头结点的单链表,函数ListLocate_L(LinkList L, ElemType x)要求在链表中查找第一个数据域取值为x的节点,返回其位序(从1开始),查找不到则返回0。例如,原单链表各个元素节点的元素依次为1,2,3,4,则...
  • 链表由一系列结点(链表中每一个元素称为结点)组成,结点可以运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便...
  • 链表

    千次阅读 2017-04-29 23:22:15
    链表由一系列结点(链表中每一个元素称为结点)组成,结点可以运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作。循环链表...
  • list一个简单介绍: List是一个接口,主要实现类有两个LinkedList,... List的特征:存放元素有序,且可重复查找: 根据list下标查找元素: list.get(index) 根据元素查找第一次出现的位置 :list.indexOf(o...
  • 单向链表和双向链表分析与操作

    万次阅读 2021-03-15 16:03:40
    单链表和双链表 链表结构: 优点: 1、程序使用数组之前,必须事先知道数组的大小,增加数组的大小...由于在链表中,仅仅只有头节点和尾节点是可见的,因此要想查找某个节点,必须从头节点或尾节点一路找下去,时间
  • 之前说记录自己大学学习代码的历程的,结果疫情以来就没更过,从现在起要勤快了!加油! #include<stdlib.h>...void CreateTree(BitNode** T)//创建二叉链表 { elemtype ch; scanf("%c",&am
  • C++ vector 删除符合条件的元素 C++ vector实际删除元素使用的是容器vectorstd::vector::erase()方法。 C++ std::remove()并不删除元素,因为容器的size()没有变化,只是元素的替换。...//删除指定元素 it...
  • 双向链表

    2016-12-11 16:47:06
    查找双向链表中指定位置的结点 向双向链表中指定位置插入结点 删除双向列表指定位置的的结点 1.定义循环链表和双向链表是对单链表的改进,仍属于链存储结构 双向链表的结点包括一个数据域和两个指针域,后继指针和前...
  • 一、单向链表C语言代码 #include<stdio.h> #include<stdlib.h> //定义数据类型,假设为int typedef int ElemType; //定义自引用结构体(结点) struct node { ElemType data; struct node *next; }; ...
  • 2、 提供操作:自表首插入元素、删除指定元素、搜索表是否有指定元素、输出链表。 3、 接收键盘录入的一系列整数(例10,25,8,33,60)作为节点的元素值,创建链表。输出链表内容。 4、 输入一个整数(例33),在链表...
  • 1、情景:有一个值value,需要知道他在链表中的位置
  • 链表分为单向链表和双向链表,前两篇都是关于单向链表的函数,这篇是有关双向循环链表的函数, 首先,我们我要知道双向循环链表长什么样子 双向循环链表结构体: typedef int DataType; typedef struct ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,088
精华内容 34,435
关键字:

在链表中查找指定元素