C语言之链表

链表就像一个铁链，每个节点node除了自身数据外，还包括一个指向下一个数据的指针(*nest)，也就是该该指针即是节点数据结构体的成员又是一个指向下个元素的指针。链表都有一个头（*head指针指向首个元素地址）和尾指针（*tail=NULL）,加上每个节点就构成了简单的链表。

链表的创建可以静态地用结构体实现，也可以动态的用malloc实现。

链表据说打破了C的2个特例：先定义后使用（链表里自己定义自己，递归函数）

简单链表的基本操作：创建链表、定位、插入、删除、输出内容。

一创建链表：创建结构体，初始化节点数据，head,tail,nest指针的初始化

 1 void CreatList_Demo(void)
 2 {
 3     struct student a,b,c;
 4     struct student *head,*p;
 5     
 6     /*初始化静态链表成员*/
 7     a.ID =1001;a.score =90;
 8     b.ID =1002;b.score =80;
 9     c.ID =1003;c.score =100;
10     
11     /*初始化链表指针*/
12     head =&a;a.nest=&b;b.nest=&c;c.nest =NULL;
13     p=head;
14     
15      /*打印输出，注意p指针的变化*/
16     do{
17         printf("学号:%ld,分数：%5.1f
",p->ID,p->score);
18         p=p->nest;
19     }while(p!=NULL);
20 }

创建链表

二节点的删除：

 1 struct student * DelList_Demo(struct student **head,long num)
 2 {
 3     
 4     struct student *p1,*p2;
 5     if(*head ==NULL)/*空链表情况*/
 6     {
 7         printf("list is empty!!!
");
 8         goto end;
 9     }
10     p1 =*head;/*从头开始查找*/
11     while((p1->ID !=num) &&(p1->nest !=NULL))
12     {
13         p2=p1;/*p2始终是p1的前继*/
14         p1=p1->nest;
15     }
16     if(p1->ID ==num)/*找到了*/
17     {
18         if(p1 ==*head)/*第一个*/
19         {
20             *head =p1->nest;
21         }
22         else
23         {
24             p2->nest =p1->nest;
25         }
26     }
27     else/*没找到*/
28     {
29         printf("no find this node!!!
");
30     }
31     end:
32         return *head;
33 }

List_Del.c

三节点的添加：注意空链表，插入头部等特殊处理

/*
   （**head）：链表，二维指针，实参调用List_Insert(struct node 
                      &head,p0)这样更改才会对链表有修改
    p0：待插入的节点指针
*/
void List_Insert(struct node **head,struct node *p0)
{
   struct node *front,*behind;
   
   if((*head)==NULL)/*空链表*/
   {
      *head=p0; 
      return;
   }
   else
   {
       if((*head)->num > p0->num)/*插入第一个位置*/
       {
           p0->nest =*head;
           *head =p0;
           return;
       }
       front =*head;
       behind =(*head)->nest;
       while(behind!=NULL)
       {
          if(behind->num < p0->num) 
          {
              front =behind;
              behind =behind->nest;
          }
          else
            break;
       }
       front->nest =p0;/*找到位置后正确插入*/
       p0->nest =behind;
   }
}

View Code

工程代码：https://www.onlinegdb.com/edit/HJAdIuM2H

参考学习https://wenku.baidu.com/view/d85a996c561252d380eb6ebc.html?sxts=1574257668264

循环链表与双向链表：参考https://www.cnblogs.com/dengfaheng/p/9245770.html

循环链表：

　　引入原因：单链表要想访问某个元素，必须从head指针开始顺序访问，即使是尾元素也需要遍历一遍，效率很低，当将尾指针指向头指针折成一个环时就成了单循环链表。也可以只定义尾指针，顺序移动一个位置就到了头位置，对单循环链表的操作与单链表差不多，唯一区别就是判断结束条件不再是p=null,而是p=head

双向链表：

　　引入原因：单链表只能顺序逐一朝后，不能朝前；所以在单链表结构体中增加一个pre前继指针就成了双向链表，可以向前遍历了。

双向链表的创建：给首尾节点分配空间，且首节点的前继与尾结点的后继都为null,且前继的next指向尾节点的前继pre.

双向链表的插入和删除：画个模拟图就能搞明白。