链表 订阅
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。 展开全文
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。
信息
构    成
一系列结点组成
分    类
计算机数据结构
中文名
链表
外文名
linked list
链表特点
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系,对数据元素 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。由这两部分信息组成一个"结点"(如概述旁的图所示),表示线性表中一个数据元素。线性表的链式存储表示,有一个缺点就是要找一个数,必须要从头开始找起,十分麻烦。根据情况,也可以自己设计链表的其它扩展。但是一般不会在边上附加数据,因为链表的点和边基本上是一一对应的(除了第一个或者最后一个节点,但是也不会产生特殊情况)。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向,反向标记加在边上可能会更方便。对于非线性的链表,可以参见相关的其他数据结构,例如树、图。另外有一种基于多个线性链表的数据结构:跳表,插入、删除和查找等基本操作的速度可以达到O(nlogn),和平衡二叉树一样。其中存储数据元素信息的域称作数据域(设域名为data),存储直接后继存储位置的域称为指针域(设域名为next)。指针域中存储的信息又称做指针或链。由分别表示,,…,的N 个结点依次相链构成的链表,称为线性表的链式存储表示,由于此类链表的每个结点中只包含一个指针域,故又称单链表或线性链表。
收起全文
精华内容
参与话题
问答
  • 一步一步教你从零开始写C语言链表

    万次阅读 多人点赞 2017-04-02 14:34:39
    发送"链表"即可获取。 为什么要学习链表链表主要有以下几大特性: 1、解决数组无法存储多种数据类型的问题。 2、解决数组中,元素个数无法改变的限制(C99的变长数组,C++也有变长数组可以实现)。 3、数组...

    完整源码获取:
    微信关注:嵌入式云IOT技术圈
    发送"链表"即可获取。watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95YW5neXVhbnhpbi5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70

    为什么要学习链表?

    链表主要有以下几大特性:

    1、解决数组无法存储多种数据类型的问题。

    2、解决数组中,元素个数无法改变的限制(C99的变长数组,C++也有变长数组可以实现)。

    3、数组移动元素的过程中,要对元素进行大范围的移动,很耗时间,效率也不高。

    先来感性的认识一下链表,我们先来认识下简单的链表:

    从这幅图我们得出以下信息:

    这个简单链表的构成:

    头指针(Header),若干个节点(节点包括了数据域和指针域),最后一个节点要指向空。

    实现原理:头指针指向链表的第一个节点,然后第一个节点中的指针指向下一个节点,然后依次指到最后一个节点,这样就构成了一条链表。

    接下来看看链表的数据结构:

    struct  list_node
    {
    	int data ; //数据域,用于存储数据
    	struct list_node *next ; //指针,可以用来访问节点数据,也可以遍历,指向下一个节点
    };
    

    那么如何来创建一个链表的一个节点呢?

    我们写个程序演示一下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct  list_node
    {
    	int data ; 
    	struct list_node *next ;
    };
    
    typedef struct list_node list_single ; 	
    
    int main(void)
    {
    	list_single *node = NULL ;          //1、首先,当然是定义一个头指针
    	node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single)); //3、清一下
    	node->data = 100 ;		    		//4、给链表节点的数据赋值
    	node->next = NULL ;                 //5、将链表的指针域指向空
    	printf("%d\n",node->data);
    	free(node);
    	return 0 ;
    }

    那么,这仅仅只是创建一个链表中的一个节点,为了好看,我们把创建节点封装成函数,以后想创建多少个节点,我们就可以反复调用一个函数来创建,会很方便:

    list_single *create_list_node(int data)
    {
    	list_single *node = NULL ;
    	node = (list_single *)malloc(sizeof(list_single));
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single));
    	node->data = 100 ;
    	node->next = NULL ;
    	return node ;
    }

    接下来在程序上完成的程序:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct  list_node
    {
    	int data ; 
    	struct list_node *next ;
    };
    
    typedef struct list_node list_single ; 	
    list_single *create_list_node(int data)
    {
    	list_single *node = NULL ;
    	node = (list_single *)malloc(sizeof(list_single));
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single));
    	node->data = data;
    	node->next = NULL ;
    	return node ;
    }
    int main(void)
    {
    	int data = 100 ;
    	list_single *node_ptr = create_list_node(data); //创建一个节点
    	printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
    	printf("node_ptr->next=%d\n",node_ptr->next);  
    	free(node_ptr);
    	return 0 ;
    }

    执行结果 :



    这样我们就完成一个链表节点的创建了,那么它现在的样子如下图:

    链表的结构里,数据存储了100,因为这个链表只有一个节点,所以它的指针域指向了NULL。

       上面只是建立一个单链表的基本雏形,接下来咱们再来增加一点难度。如果创建多个单链表节点,实现单链表的增删改查?把单链表应用起来。

    1、首先定义一个单链表的数据结构

    创建节点函数原型可定义如下:
    struct list *create_node(int data) ;
    如何创建单链表的节点,主要分以下步骤:
    (1)给当前的每个节点的数据结构配置定量的空间大小
       ep : struct list *node = malloc(sizeof(struct list));
    (2)清节点数据(由于结构体变量在未初始化的时候,数据是脏的)
       ep : memset(node,0,sizeof(struct list));
    (3)给节点初始化数据
       ep : node->id = data ; 
    (4)将该节点的指针域设置为NULL
       ep : node->next = NULL ;

    2、单链表的尾插:

    尾插节点函数原型可定义如下:

    如何将当前链表和新的节点相连接?只要实现:
    header->next = new 
    尾插流程如下:

    (1)获取当前节点的位置,也就是访问头节点
       ep : struct list *p = header ;
    (2)判断是否为最后一个节点,如果不是,移动到下一个节点,如果是,将数据插入尾部。
       ep : while(NULL != p->next) p = p->next ;
            p->next = new ;

    3、单链表的头插

    很好理解,头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图,新的节点插在头节点和节点1。
    所以可以推出头插流程如下:
    (1)获取当前节点的位置,也就是访问头节点
        ep : struct list *p = header ;
    (2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)
        ep : new->next = p->next ;
    (3)原来的头节点的下一个节点设置为现在新插入的头节点
        ep : p->next = new ;

    4、单链表的遍历

    如图为一条单向链表的模型,看图知道该链表由头节点和若干个节点组成,最后一个节点(尾节点)为NULL 。
    从图中可以得出信息,如果我们要打印出各个节点的数据,要考虑以下问题:
    (1)需要打印头节点吗?(头节点肯定是不用打印的,因为这是我们为了操作方便而设置的一个节点)。
    (2)这条链表有多少个节点我们怎么知道?(通过判断该链表是否已经到达了尾节点,标志就是NULL)
    那么可以得到流程如下:
    (1)获取当前节点的位置,也就是访问头节点
        ep : struct list *p = header ;
    (2)由于头节点我们不需要去打印它,这时候,初始化打印的节点需要从第一个节点开始。
        ep : p = p->next ;  
    (3)判断是否为最后一个节点,如果不是,先打印第一个节点的数据(1),然后移动到下一个节点(2),重复这两个步骤。
       如果是最后一个节点,直接打印数据即可。
        while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
        printf("node:%d\n",p->data);
        当然还可以一句代码解决,这样就达到了先偏移,后取数据。
        while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }
     

    5、单链表的删除

    删除节点的函数原型可定义如下:
    int detele_list_node(struct list *pH , int data);
    单向链表的删除要考虑两种情况,一种的普通节点的删除(当然,头节点不能算)
    还有一种是尾节点的前一个节点的删除情况,注意,删除完节点还需要释放对应节点的内存空间。

    删除节点的设计流程:
    (1)先定义两个指针,一个表示当前的节点,另一个表示当前节点的上一个节点。
        ep : struct list *p = header ;  //当前节点
             struct list *prev = NULL ; //当前节点的上一个节点
    (2)遍历整个链表,同时保存当前节点的前一个节点
        ep : while(NULL != p->next)
            { 
              //保存了当前的节点的前一个节点
              prev = p ;  
              //保存当前偏移的节点
              p = p->next ; 
              return 0 ;
            }
    (3)在遍历的过程中查找要删除的数据
        ep : while(NULL != p->next)
            { 
              //保存了当前的节点的前一个节点
              prev = p ;  
              //保存当前偏移的节点
              p = p->next ; 
              //查找到了数据
              if(p->id == data)
              {
              
              }
              return 0 ;
            }
    (4)查找到了数据后,分两种情况删除
        ep : 普通节点的删除
            if(p->id == data)
            {
                prev->next = p->next ;
                free(p);
            }
        ep : 考虑尾节点的下一个节点为NULL的节点删除
            if(p->id == data)
            {
                if(p->next == NULL)
                {
                    prev->next = NULL ;
                    free(p);
                }
            }

    6、单链表的逆序

    逆序步骤:

    单链表的基本操作流程咱们基本搞懂了,下面写一个程序,这将会变得非常非常的简单。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct slist
    {
    	int id ;
    	struct slist *next ;			
    }L;
     
    //创建一个节点 
    L *create_node(int data)
    {
    	//给每个节点分配结构体一样的空间大小 
    	L *p = malloc(sizeof(L));
    	if(NULL == p)
    	{
    		printf("malloc error!\n");
    		return NULL ;
    	}
    	//由于结构体在未初始化的时候一样是脏数据,所以要清 
    	memset(p,0,sizeof(L));
    	//初始化第一个节点 
    	p->id = data ; 
    	//将节点的后继指针设置为NULL 
    	p->next = NULL ;
    }
     
    //链表的尾插 
    void tail_insert(L *pH , L *new)
    {
    	//获取当前的位置 
    	L *p = pH ; 
    	//如果当前位置的下一个节点不为空 
    	while(NULL != p->next)
    	{
    		//移动到下一个节点 
    		p = p->next ;
    	}
    	//如果跳出以上循环,所以已经到了NULL的这个位置
    	//此时直接把新插入的节点赋值给NULL这个位置 
    	p->next = new ;
    }
     
    //链表的头插 
    void top_insert(L *pH , L *new)
    {
    	L *p = pH ;
    	new->next = p->next ;
    	p->next = new ;
    }
     
    //链表的遍历 
    void Print_node(L *pH)
    {
    	//获取当前的位置 
    	L *p = pH ;
    	//获取第一个节点的位置 
    	p = p->next ;
    	//如果当前位置的下一个节点不为空 
    	while(NULL != p->next)
    	{
    		//(1)打印节点的数据 
    		printf("id:%d\n",p->id);
    		//(2)移动到下一个节点,如果条件仍为真,则重复(1),再(2) 
    		p = p->next ;
    	}
    	//如果当前位置的下一个节点为空,则打印数据
    	//说明只有一个节点 
    	printf("id:%d\n",p->id);
    }
     
    //删除链表中的节点 
    int detele_list_node(L * pH , int data)
    {
    	//获取当前头节点的位置 
    	L *p = pH ;
    	L *prev = NULL;
    	while(NULL != p->next)
    	{
    		//保存当前节点的前一个节点的指针 
    		prev = p ;
    		//然后让当前的指针继续往后移动 
    		p = p->next ; 	
    		//判断,找到了要删除的数据  
    		if(p->id == data)
    		{
    			//两种情况,一种是普通节点,还有一种是尾节点
    			if(p->next != NULL)  //普通节点的情况 
    			{
    				prev->next = p->next ;
    				free(p);
    			}
    			else //尾节点的情况 
    			{
    				prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
    				free(p); 
    			}
    			return 0  ;
    		}
    	}
    	printf("没有要删除的节点\n");
    	return -1 ;
    }
     
    void trave_list(L * pH)
    {
    	//保存第一个节点的位置 
    	L *p = pH->next;
    	L *pBack;
    	int i = 0 ;
    	if(p->next == NULL || p == NULL)
    		return ;
    		
    	while(NULL != p->next) //遍历链表 
    	{
    		//保存第一个节点的下一个节点 
    		pBack = p->next ; 
    		//找到第一个有效节点,其实就是头指针的下一个节点 
    		if(p == pH->next) 
    		{
    			//第一个有效节点就是最后一个节点,所以要指向NULL 
    			p->next = NULL ; 
    		} 
    		else
    		{
    			/*
    			new->next = p->next ;
    			p->next = new ;
    			*/
    			p->next = pH->next ; //尾部连接 
    		}
    		pH->next = p ; //头部连接 
    		p = pBack ; //走下一个节点 
    	}
    	top_insert(pH,p); //插入最后一个节点 
    }
     
    int main(int argc , char **argv) 
    {
    	//创建第一个节点 
    	int i ;
    	L *header = create_node(0); 
    	for(i = 1 ; i < 10 ; i++)
    	{
    		tail_insert(header,create_node(i));
    	}
    	Print_node(header);
    	detele_list_node(header,5);
    	putchar('\n');
    	Print_node(header);
    	putchar('\n');
    	trave_list(header);
    	Print_node(header);
    	return 0 ;
    }
    

    运行结果:

    当然,单链表存在一定的弊端,就是查找数据和删除数据的时候比较麻烦,而双链表的出现就是为了解决它的弊端:

    双链表的引入是为了解决单链表的不足:
    (1)双链表可以往前遍历,也可以往后遍历,具有两个方向
    双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)
    双向链表的图形结构描述:

    struct double_list                                   struct double_list
    {                                                            {
        数据域;                  ep :------->                   int data ;
        指针域(前向指针) ;                                   struct double_list *prev ;
        指针域(后向指针) ;                                   struct double_list *next ;
    };                                                             };
     

    1、双向链表的创建

    struct list *create_node(int data) ;
    创建步骤(与单链表类似,就是多了一个指针):
    (1)给节点申请空间:
       ep : struct double_list *p = malloc(sizeof(struct double_list));
    (2)初始化数据域
       ep : p->data = data ;
    (3)初始化指针域
       ep : p->prev = NULL ; 
            p->next = NULL ;

    2、双向链表的尾插

    双向链表尾插节点的函数可以定义如下:
    void double_list_tail_insert(struct double_list *header , struct double_list *new) ;
    尾插图示操作:

    尾插的步骤:


    (1)找到链表的尾节点
       ep : 和单链表差不多
            DL *p = header ;
            while(NULL != p->next)
                p = p->next ;
    (2)将新的节点连接到尾节点的后面成为新的节点
       1.原来的next指针指向新节点的首地址。            p->next = new ;
       2.新节点的prev指针指向原来的尾节点的首地址。 new->prev = p;
     

    3、双向链表的头插

    双向链表头插节点的函数可以定义如下:
    void double_list_top_insert(struct double_list *header , struct double_list *new) ;

    4、双向链表的遍历

    4.1 正向遍历
        void double_list_for_each(DL *header)
        步骤:和单链表完全一致,没什么好写的。
        
        
    4.2 反向遍历
        void double_list_for_each_nx(DL *header)
        步骤:(1)和单链表一样,先循环找到最后一个节点的地址
              (2)再依靠prev指针循环往前移动
                 2.1 先打印最后一个数据  ep : printf("%d ",p->data);
                 2.2 向前循环遍历         ep : p = p->prev ;
                 
                 判断条件:header->prev != p->prev,
                 header保存的是头节点的地址,
                 header->prev保存的是头节点的prev的地址,
                 header->next保存的是头节点的next的地址,
                 头节点在创建的时候:
                 header->prev = NULL ;
                 header->next = NULL ;
                 所以这个条件这样写header->prev = NULL也是对的。

    5、双向链表节点的删除


    假设需要删除节点1:    
        首先:
        (1)获取当前节点的地址: 
            ep : p = header;
        (2)遍历所有的节点,找到要删除的节点:
            ep : 
            while(NULL != p->next)
            {
                p = p->next ;
                if(p->data == data)
                {
                
                }
            }
        (3)找到要删除的数据以后,需要做判断,判断两种情况,这和单链表差不多
        3.1 如果找到当前节点的下一个节点不为空
        3.1.1    
            那就把当前节点的prev节点指向要删除的这个节点的prev
            因为当前的prev节点保存的是要删除的上一个节点的指针 
            p->next->prev = p->prev ;
        3.1.2    
            然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点:
            p->prev->next = p->next ;
        3.1.3    
            最后释放删除指针的空间:
            free(p);
            
        3.2 如果找到当前节点的下一个节点为空
        3.2.1   
        直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。
        p->prev->next = NULL ;
        3.2.2
        将删除的指针的空间释放:
        free(p);
        看来,双链表学起来比单链表容易多了!确实啊,多了一个方向,操作起来就更加容易了,但是多了一个方向,一维多了一个指针,相比增加了一定的复杂度,但是,只要牢记prev指针和next指针的指向,那么,手画一图,代码即可写出!
    下面给一个案例实现一下双向链表:
     

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    //创建一个双链表的数据结构
    typedef struct __double_list
    {
    	int data ;
    	struct __double_list *prev ;
    	struct __double_list *next ;
    }DL ; 
     
    //创建双向链表并插入一个节点 
    DL *create_dl_node(int data)
    {
    	DL *p = malloc(sizeof(DL));
    	if(NULL == p)
    	{
    		printf("create dl node fair!\n");
    		return NULL ;
    	}
    	//初始化数据 
    	p->data = data ;
    	//初始化指针 
    	p->next = NULL ;
    	p->prev = NULL ;
    }
     
    //双向链表的尾插 
    void double_list_tail_insert(DL *header , DL *new)
    {
    	//取得当前节点的地址 
    	DL *p = header ;
    	//找到链表的尾节点 
    	while(NULL != p->next)
    	{
    		//找不到接着找 
    		p = p->next ;
    	}
    	//找到了尾节点,指向新节点的首地址 
    	p->next = new ;
    	//新节点的prev指针指向原来的尾节点的首地址。
    	new->prev = p;
    }
     
    //双向链表的头插(也就是插在两个节点之间的插入方式)
    void double_list_top_insert(DL *header , DL *new)
    {
    	//新节点的next指针指向原来的节点一的地址
    	new->next = header->next ; 
    	//判断当前节点的下一个节点的地址是否为空
    	if(NULL != header->next) 
    		header->next->prev = new ; //节点1的prev指针指向新节点的地址 
    	header->next = new ;
    	new->prev = header ;
    }
     
    //双向链表的正向遍历 
    void double_list_for_each(DL *header)
    {
    	DL *p = header ;
    	while(NULL != p->next)
    	{
    		p = p->next ;
    		printf("%d ",p->data);
    	}
    }
     
    //双向链表的反向遍历 
    void double_list_for_each_nx(DL *header)
    {
    	DL *p = header ;
    	//先找到尾节点
    	while(NULL != p->next)
    	{
    		p = p->next ;	
    	} 
    	//已经找到了尾节点,向前遍历,注意,遍历到头节点之前
    	//限制条件: != 头结点 
    	while(NULL != p->prev)
    	{
    		printf("%d ",p->data);
    		p = p->prev ;
    	}
    }
     
    //双向链表节点的删除
    int double_list_delete_node(DL *header , int data)
    {
    	//取得当前节点 
    	DL *p = header;
    	//遍历所有的节点 
    	while(NULL != p->next)
    	{
    		p = p->next ;
    		//找到了对应要删除的数据了 
    		if(p->data == data)
    		{
    			//一样存在两种情况
    			//(1)当前节点的下一个节点不为空
    			if(p->next != NULL)
    			{
    				//那就把当前节点的prev节点指向要删除的这个节点的prev
    				//因为当前的prev节点保存的是要删除的上一个节点的指针 
    				p->next->prev = p->prev ;
    				//还要指定它的next节点 
    				p->prev->next = p->next ;
    				free(p);
    			}
    			//(2)当前节点的下一个节点为空 
    			else
    			{
    				//把 
    				p->prev->next = NULL ;
    				free(p); 
    			}
    			return 0 ;
    		}
    	}
    	printf("\n没有找到对应要删除的节点,或者节点已经被删除!\n");
    	return -1 ;	
    } 
     
    int main(void)
    {
    	int i ;
    	DL *header = create_dl_node(0);
    	for(i = 0 ; i < 10 ; i++)
    	{
    		//双向链表的尾插 
    		//double_list_tail_insert(header,create_dl_node(i));
    		//双向链表的头插 
    		double_list_top_insert(header,create_dl_node(i));
    	}
    	//双向链表的正向遍历 
    	printf("双向链表的正向遍历:");
    	double_list_delete_node(header,5);
    	double_list_for_each(header);
    //	double_list_delete_node(header,9);
    	double_list_delete_node(header,5);
    	putchar('\n');
    	printf("双向链表的反向遍历:");
    	double_list_for_each_nx(header);
    	return 0 ;
    }
    

    运行结果:

    展开全文
  • 链表详解(易懂)

    万次阅读 多人点赞 2019-04-24 21:13:32
    链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点...
    • 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点(node)。
    • 链表的第一个节点和最后一个节点,分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空(null)。链表中每个节点的 next 引用都相当于一个指针,指向另一个节点,借助这些 next 引用,我们可以从链表的头节点移动到尾节点。
    • 链表数据结构中主要包含单向链表、双向链表及循环链表:
    1. 单向链表
        单向链表只有一个指针域,在整个节点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的节点。
      在这里插入图片描述
      在这里插入图片描述
        单向链表中,每个节点的数据域都是通过一个 Object 类的对象引用来指向数据元素的,与数组类似,单向链表中的节点也具有一个线性次序,即如果节点 a1 的 next 引用指向节点 a2,则 a1 就是 a2 的直接前驱,a2 是 a1 的直接后续。只能通过前驱节点找到后续节点,而无法从后续节点找到前驱节点。
      特点:
        数据元素的存储对应的是不连续的存储空间,每个存储结点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
        逻辑上相邻的节点物理上不必相邻。
      缺点:
      1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
      2、查找结点时链式存储要比顺序存储慢(每个节点地址不连续、无规律,导致按照索引查询效率低下)。
      优点:
      1、插入、删除灵活 (不必移动节点,只要改变节点中的指针,但是需要先定位到元素上)。
      2、有元素才会分配结点空间,不会有闲置的结点。

    2. 双向链表
        要在单向链表中找到某个节点的前驱节点,必须从链表的头节点出发依次向后寻找,但是需要Ο(n)时间。为此我们可以扩展单向链表的节点结构,使得通过一个节点的引用,不但能够访问其后续节点,也可以方便的访问其前驱节点。扩展单向链表节点结构的方法是,在单链表节点结构中新增加一个域,该域用于指向节点的直接前驱节点。该链表称为双向链表。单向链表只能从一个方向遍历,双向链表可以从两个方向遍历。
      在这里插入图片描述
      在这里插入图片描述
        在使用双向链表实现链接表时,为使编程更加简洁,我们使用带两个哑元节点的双向链表来实现链接表。其中一个是头节点,另一个是尾节点,它们都不存放数据元素,头节点的pre 为空,而尾节点的 Next 为空。
      在这里插入图片描述
        在具有头尾节点的双向链表中插入和删除节点,无论插入和删除的节点位置在何处,因为首尾节点的存在,插入、删除操作都可以被归结为某个中间节点的插入和删除;并且因为首尾节点的存在,整个链表永远不会为空,因此在插入和删除节点之后,也不用考虑链表由空变为非空或由非空变为空的情况下 head 和 tail 的指向问题;从而简化了程序。

    3. 循环链表
        头节点和尾节点被连接在一起的链表称为循环链表,这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点,反之亦然。
      在这里插入图片描述
      在这里插入图片描述

    简单用双向列表模拟一下LinkedList,Java代码如下:

    public class Node {//节点类
            private Object previous;//每个节点的前一个指向
            private Object obj;//每个节点中间位置用来存放你存储的东西
            private Object next;//每个节点的后一个指向
            public Object getPrevious() {
                    return previous;
            }
            public void setPrevious(Object previous) {
                    this.previous = previous;
            }
            public Object getObj() {
                    return obj;
            }
            public void setObj(Object obj) {
                    this.obj = obj;
            }
            public Object getNext() {
                    return next;
            }
            public void setNext(Object next) {
                    this.next = next;
            }
    }
    
    public class MyLinkedList {//模拟LinkedList
            //对于每一个LinkedList集合,都有一个首节点和一个尾节点:
            private Node first;//首节点
            private Node last;//尾节点 
            
            
            public void add(Object obj){
                    if(first==null){	//证明我放入的是第一个节点
                            //创建一个独立的节点:
                            Node n=new Node();
                            n.setPrevious(null);
                            n.setObj(obj);
                            n.setNext(null);
                            
                            //将我想象的这个链中的首节点,位节点都设置为n
                            first=n;
                            last=n;
                    }else{	//放入的是第二个节点,第三个节点。。。。。
                            //创建一个独立的节点:
                            Node n=new Node();
                            n.setPrevious(last);
                            n.setObj(obj);
                            n.setNext(null);
                            
                            //将链表的最后一个的下一个指向为n
                            last.setNext(n);
                            
                            //将链表的最后一个指向n
                            last=n;
                    }
            }
            
            public static void main(String[] args) {
                    MyLinkedList list=new MyLinkedList();
                    list.add("java");
                    list.add("css");
                    list.add("solr");
                    list.add("jsp");
                    
                    System.out.println("结束");
      
            }
         
    }
    
    
    展开全文
  • c语言链表详解(超详细)

    万次阅读 多人点赞 2018-06-03 16:16:01
    链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入...

    链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入节点。链表都有一个头指针,一般以head来表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数据域的。链表中每个节点都分为两部分,一个数据域,一个是指针域。说到这里你应该就明白了,链表就如同车链子一样,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。

    作为有强大功能的链表,对他的操作当然有许多,比如:链表的创建,修改,删除,插入,输出,排序,反序,清空链表的元素,求链表的长度等等。

    初学链表,一般从单向链表开始

    --->NULL
    head

    这是一个空链表。

     ---->[p1]---->[p2]...---->[pn]---->[NULL]
    head   p1->next  p2->next   pn->next

    有n个节点的链表。

    创建链表

    typedef struct student{
    	int score;
    	struct student *next;
    } LinkList;

    一般创建链表我们都用typedef  struct,因为这样定义结构体变量时,我们就可以直接可以用LinkList  *a;定义结构体类型变量了。

    初始化一个链表,n为链表节点个数。

    LinkList *creat(int n){
    	LinkList *head, *node, *end;//定义头节点,普通节点,尾部节点;
    	head = (LinkList*)malloc(sizeof(LinkList));//分配地址
    	end = head;         //若是空链表则头尾节点一样
    	for (int i = 0; i < n; i++) {
    		node = (LinkList*)malloc(sizeof(LinkList));
    		scanf("%d", &node->score);
    		end->next = node;
    		end = node;
    	}
    	end->next = NULL;//结束创建
    	return head;
    }

    修改链表节点值

    修改链表节点值很简单。下面是一个传入链表和要修改的节点,来修改值的函数。

    void change(LinkList *list,int n) {//n为第n个节点
    	LinkList *t = list;
    	int i = 0;
    	while (i < n && t != NULL) {
    		t = t->next;
    		i++;
    	}
    	if (t != NULL) {
    		puts("输入要修改的值");
    		scanf("%d", &t->score);
    	}
    	else {
    		puts("节点不存在");
    	}
    }

    删除链表节点

    删除链表的元素也就是把前节点的指针域越过要删除的节点指向下下个节点。即:p->next = q->next;然后放出q节点的空间,即free(q);

    void delet(LinkList *list, int n) {
    	LinkList *t = list, *in;
    	int i = 0;
    	while (i < n && t != NULL) {
    		in = t;
    		t = t->next;
    		i++;
    	}
    	if (t != NULL) {
    		in->next = t->next;
    		free(t);
    	}
    	else {
    		puts("节点不存在");
    	}
    }

     

    插入链表节点

    我们可以看出来,插入节点就是用插入前节点的指针域链接上插入节点的数据域,再把插入节点的指针域链接上插入后节点的数据域。根据图,插入节点也就是:e->next = head->next;  head->next = e;

    增加链表节点用到了两个结构体指针和一个int数据。

    void insert(LinkList *list, int n) {
    	LinkList *t = list, *in;
    	int i = 0;
    	while (i < n && t != NULL) {
    		t = t->next;
    		i++;
    	}
    	if (t != NULL) {
    		in = (LinkList*)malloc(sizeof(LinkList));
    		puts("输入要插入的值");
    		scanf("%d", &in->score);
    		in->next = t->next;//填充in节点的指针域,也就是说把in的指针域指向t的下一个节点
    		t->next = in;//填充t节点的指针域,把t的指针域重新指向in
    	}
    	else {
    		puts("节点不存在");
    	}
    }

    输出链表

    输出链表很简单,边遍历边输出就行了。

            while (h->next != NULL) {
    		h = h->next;
    		printf("%d  ", h->score);
    	}

     

     

     

    展开全文
  • 【C语言】链表及单链表基本操作

    万次阅读 多人点赞 2019-04-29 15:20:45
    1、什么是链表链表的分类? 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 数据结构中: 2、链表的分类 共有8种链表结构 ...

    1、什么是链表?链表的分类?

    链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

    数据结构中:

    在这里插入图片描述

    2、链表的分类

    共有8种链表结构
    在这里插入图片描述

    3、单链表的基本操作

    类似于顺序表,我们来实现单链表的基本操作,具体见SList.h 代码中语句及注释。

    #pragma once
    typedef int SDataType;
    //链表的节点
    typedef struct SListNode
    {
     SDataType _data;
     struct SListNode* _PNext;
    }Node,*PNode;
    
    typedef struct SList       //封装了链表的结构
    {
     PNode _pHead;//指向链表第一个节点
    }SList;
    
    void SListInit(SList*s);//链表的初始化
    
    //在链表s最后一个节点后插入一个值为data的节点
    void SListPushBack(SList* s, SDataType data);
    
    //删除链表s最后一个节点
    void SListPopBack(SList* s);
    
    //在链表s第一个节点前插入值为data的节点
    void SListPushFront(SList* s, SDataType data);
    
    //删除链表s的第一个节点
    void SListPopFront(SList* s);
    
    //在链表的pos位置后插入值为data的节点
    void SListInsert(PNode pos, SDataType data);
    
    //删除链表s中pos位置的节点
    void SListErase(SList* s, PNode pos);
    
    // 在链表中查找值为data的节点,找到返回该节点的地址,否则返回NULL 
    PNode SListFind(SList* s, SDataType data);
    
    //移除链表中第一个值为data的元素
    void SListRemove(SList*s, SDataType data);
    
    // 获取链表中有效节点的个数 
    int SListSize(SList* s);
    
    // 检测链表是否为空 
    int SListEmpty(SList* s);
    
    // 将链表中有效节点清空 
    void SListClear(SList* s);
    
    // 销毁链表 
    void SListDestroy(SList* s);
    //打印链表
    void SListPrint(SList* s);
    

    以下为SList.c具体代码:

    #include <stdio.h>
    #include "Slist.h"
    #include <assert.h>
    #include <stdlib.h>
    #include <stddef.h>
    

    1.初始化部分,我们只需要将链表的头结点置为NULL即可。

    void SListInit(SList*s) {
     assert(s);
     s->_pHead = NULL;
    }
    

    2.尾插,首先我们要创建一个新节点,然后判断链表当前是否有节点,若没有,则直接让第一个节点指向新节点,若有,找到最后一个节点,让他指向新节点。

    void SListPushBack(SList* s, SDataType data) {
     //找链表最后一个节点
     assert(s);
     PNode pNewNode = BuySListNode(data);
     if (s->_pHead == NULL) {//链表没有节点的情况
      s->_pHead = pNewNode;
     }
     else {
      PNode pCur = s->_pHead;
      while (pCur->_PNext) {
       pCur = pCur->_PNext;
      }
      //让最后一个节点指向新节点
      pCur->_PNext = pNewNode;
     }
    }
    

    3.尾删,首先判断链表中有没有节点,若没有,直接返回,若有一个节点,直接让第一个节点指向NULL,若有多个节点,则需要记录下倒数第二个节点,让它指向NULL。

    void SListPopBack(SList* s) {
     assert(s);
     if (s->_pHead == NULL) {//链表中没有节点
      return;
     }
     else if (s->_pHead->_PNext == NULL) {//只有一个节点
      free(s->_pHead);
      s->_pHead = NULL;
     }
     else {                           //多个节点
      PNode pCur = s->_pHead;
      PNode pPre = NULL;
      while (pCur->_PNext) {
       pPre = pCur;
       pCur = pCur->_PNext;
      }
      free(pCur);
      pPre->_PNext = NULL;
     }
    }
    

    4.头插

    void SListPushFront(SList* s, SDataType data) {
     assert(s);
     PNode pNewNode = BuySListNode(data);
     if (s->_pHead == NULL) {//链表为空
      s->_pHead = pNewNode;
     }
     else {
      pNewNode->_PNext = s->_pHead;
      s->_pHead = pNewNode;
     }
    }
    

    5.头删

    void SListPopFront(SList* s) {
     assert(s);
     if (s->_pHead == NULL) {//链表为空
      return;
     }
     else if (s->_pHead->_PNext == NULL) {//只有一个节点
      free(s->_pHead);
      s->_pHead = NULL;
     }
     else {
      PNode pCur = s->_pHead;
      s->_pHead = pCur->_PNext;
      free(pCur);
     }
    }
    

    6.在给定pos位置插入值为data的节点,分两步完成:首先找到pos位置的节点,然后再插入,所以要实现这一个功能需要两个函数来共同完成。

    在这里插入图片描述
    注意:应该先连接好新节点,再断开原来的指针指向。
    插入:

    void SListInsert(PNode pos, SDataType data) {
     PNode pNewNode = NULL;
     if (pos == NULL) {
      return;
     }
     pNewNode = BuySListNode(data);
     
     pNewNode->_PNext = pos->_PNext;
     pos->_PNext = pNewNode;
    }
    

    查找:

    PNode SListFind(SList* s, SDataType data) {
     assert(s);
     PNode pCur = s->_pHead;
     while (pCur) {
      if (pCur->_data == data) {
       return pCur;
      }
      pCur = pCur->_PNext;
     }
     return NULL;
    }
    

    7.删除给定pos位置的节点。
    在这里插入图片描述

    void SListErase(SList* s, PNode pos) {
     assert(s);
     if (pos == NULL || s->_pHead == NULL) {
      return;
     }
     if (pos== s->_pHead) {
      s->_pHead = pos->_PNext;
     }
     else {
      PNode pPrePos = s->_pHead;
      while (pPrePos&&pPrePos->_PNext != pos) {
       pPrePos = pPrePos->_PNext;
      }
      pPrePos->_PNext = pos->_PNext;
     }
     free(pos);
    }
    

    8.删除第一个值为data的节点。要分三种情况:链表为空直接返回、要删除的节点为第一个节点、其它位置的节点。

    void SListRemove(SList*s, SDataType data) {
     assert(s);
     if (s->_pHead == NULL) {
      return;
     }
     PNode pPre = NULL;
     PNode pCur = s->_pHead;
     while (pCur) {
      if (pCur->_data == data) {
       if (pCur == s->_pHead) {         //要删除的是第一个位置的节点
        s->_pHead = pCur->_PNext;
       }
       else {
        pPre->_PNext = pCur->_PNext;      //其它位置的情况,让前一个节点指向其后一个节点
       }
       free(pCur);
       return;
      }
      else {
       pPre = pCur;
       pCur = pCur->_PNext;
      }
     }
    }
    

    其它:

    int SListSize(SList* s) {            //获取链表有效节点的个数
     assert(s);
     int count = 0;
     PNode pCur = s->_pHead;
     while (pCur) {
      count++;
      pCur = pCur->_PNext;
     }
     return count;
    }
    
    int SListEmpty(SList* s) {              //检测链表是否为空
     assert(s);
     if (s->_pHead == NULL) {
      return -1;
     }
     return 0;
    }
    
    void SListClear(SList* s) {             //清空链表
     assert(s);
     if (s->_pHead == NULL) {
      return;
     }
     PNode pCur = s->_pHead;
     while (pCur->_PNext) {    //循环清空链表中的节点
      PNode Tmp = pCur->_PNext;
      free(pCur);
      pCur = Tmp;
     }
     if (pCur) {      //清空最后一个节点
      free(pCur);
      pCur = NULL;
     }
    }
    
    void SListDestroy(SList* s) {            //销毁链表
     assert(s);
     if (s->_pHead == NULL) {
      free(s->_pHead);
      return;
     }
     while (s->_pHead) {    
      PNode Tmp = s->_pHead->_PNext;
      free(s->_pHead);
      s->_pHead = Tmp;
     }
    }
    
    void SListPrint(SList* s) {             //打印链表
     assert(s);
     PNode pCur = s->_pHead;
     while (pCur) {
      printf("%d--->", pCur->_data);
      pCur = pCur->_PNext;
     }
     printf("\n");
    }
    void main() {
     SList s;
     SListInit(&s);
     SListPushBack(&s, 1);
     SListPushBack(&s, 2);
     SListPushBack(&s, 3);
     printf("size=%d\n", SListSize(&s));
     SListPrint(&s);
     SListInsert(SListFind(&s, 2), 0);
     SListPrint(&s);
     SListRemove(&s, 2);
     SListPrint(&s);
      system("pause");
     return;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • C语言 —— 链表简学

    千次阅读 多人点赞 2020-03-11 22:32:43
    C语言 —— 链表简学链表创建简单链表 链表 链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。 链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据...
  • 链表

    2019-09-12 10:39:03
    链表 什么是链表 链表与数据结构有些不同。栈和队列都是申请一段连续的空间,然后按顺序存储数据;链表是一种物理上非连续、非顺序的存储结构,数据元素之间的顺序是通过每个元素的指针关联的。 链表由一系列节点...
  • 链表-基础算法题

    2020-11-15 09:52:35
    1.添加/删除链表节点 添加值为x的结点 向递增有序的带头结点的单链表 L 添加一个值为 x 的结点,使其仍保持递增有序 void insert(ListNode* L, int x) { ListNode* pre = L; ListNode* cur = L->next; // 先...
  • 链表基础知识总结

    万次阅读 多人点赞 2018-05-02 19:47:49
    链表和数组作为算法中的两个基本数据结构,在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据,但又各有各的特点。数组的优势,在于可以方便的遍历查找需要的数据。在查询数组指定位置(如查询数组...
  • 链表(图文详解)

    万次阅读 多人点赞 2019-07-10 12:49:49
    链表与数组的对比,单链表和双链表的对比,双链表性能比单链表好,为什么不经常使用?有环链表面试题?
  • 循环链表C语言实现

    2018-02-03 17:48:33
    1.创建链表 2.销毁链表 3.获取链表长度 4.清空链表 5.获取第pos个元素操作 6.插入元素到位置pos 7.删除位置pos处的元素 8.获取当前游标指向的数据元素; 9.将游标重置指向链表中的第一个数据元素; 10.将游标移动...
  • C语言链表操作详解

    万次阅读 多人点赞 2018-12-29 19:01:55
    为什么要使用链表 在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显: 使用前需声明数组的长度,一旦声明长度就不能更改 插入和删除操作需要...
  • 数据结构问题,编程实现约瑟夫环,原题是严淑敏的《数据结构C语言版题集》实习一的第二题
  • 单向循环链表C语言实现

    千次阅读 2016-06-27 22:03:14
    我们都知道,单向链表最后指向为NULL,也就是为空,那单向循环链表就是不指向为NULL了,指向头节点,所以下面这个程序运行结果就是,你将会看到遍历链表的时候就是一个死循环,因为它不指向为NULL,也是周而复始的...
  • 链表C语言实现

    万次阅读 多人点赞 2018-12-09 23:41:42
    一、单向链表C语言实现 链表作为一种基本的数据结构在程序开发过程当中经常会使用到。对C语言来说链表的实现主要依靠结构体和指针,所以本文相关内容和程序需要有C语言当中指针和结构体的基础。 链表是一种线性...
  • C语言链表超简单教程

    万次阅读 多人点赞 2018-04-05 16:19:22
    笔者作为一名C语言的初学者,在刚接触链表时,几乎找不到教程能用很通俗易懂的语言去讲解链表。大多数时候找到的关于链表的教程,或许是生硬的塞给读者一大段代码,或许是使用了一些过于专业的词汇,对于萌新非常地...
  • c语言结构体 链表

    万次阅读 多人点赞 2018-11-16 00:01:30
    单链表 尾插法 头插法 看这篇https://blog.csdn.net/viafcccy/article/details/84502334 https://blog.csdn.net/viafcccy/article/details/85041942 单链表实现贪吃蛇看这篇https://blog.c...
  • RE:从零开始我的c语言链表之旅
  • 顾名思义,链表每个结点有两个指针域,一个指向前驱节点,一个指向后继结点。 结点定义如下 typedef struct Node { int data; struct Node *prior; //指向前驱 struct Node *next; //指向后继 }Node,*pNode; //...
  • 实现通用的双向链表c语言实现)

    千次阅读 2017-10-16 15:46:08
    从实现一个通用的双向链表开始。 1. 构建链表节点   链表节点存值还是存值的地址(指针)?对于通用链表首先要做到能够存放任何数据类型的数据,首先可能会想到的是union,但是数据类型无穷无尽,不可能在union...
  • 双向链表-C语言

    千次阅读 2014-11-13 13:17:57
    不是自己亲自完成代码,你永远都想不到要注意的细节在哪里!!!

空空如也

1 2 3 4 5 ... 20
收藏数 736,823
精华内容 294,729
关键字:

链表