C语言链表操作详解

为什么要使用链表

在未学习链表时，我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快，但是它的弊端也很明显：

1.  使用前需声明数组的长度，一旦声明长度就不能更改
2. 插入和删除操作需要移动大量的数组元素，效率慢
3. 只能存储一种类型的数据.

而链表则可以实现以上这些数组所不具备的功能，此时引入了结构体来实现创建链表的操作。

链表的特点：

1.  n个节点离散分配
2. 每一个节点之间通过指针相连
3. 每一个节点有一个前驱节点和一个后继节点
4. 首节点没有前驱节点，尾节点没有后继节点

首先先定义一个简单的结构体

struct link{ int data; //定义数据域 struct link *next; //定义指针域，存储直接后继的节点信息 };

数据域的内容可以自己指定，指针域用来存放下一个节点的地址。

创建链表前须知

首节点：存放第一个有效数据的节点

头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空

头指针：指向头节点的指针

尾节点：存放最后一个有效数据的节点

尾指针：指向尾节点的指针

建立一个单向链表

方法：定义方法向链表中添加节点来建立一个单向链表

思路：首先定义一个结构体指针变量p，使用malloc函数为新建节点申请内存空间，让p指向这个节点(指向它刚申请的内存空间），再将其添加到链表中。此时需考虑两种情况：

1.若单链表为空表，则将新建节点置为头节点

//若此时只在链表中插入头节点 struct link *p = head; p = (struct link *)malloc(sizeof(struct link)); //让p指向新建节点创建的内存空间 if(p == NULL){ //新建节点申请内存失败 exit(0); } //此时head也指向头节点的地址 p->next = NULL; //因为没有后续节点，所以新建节点指针域置空

2.链表非空，则将新建节点添加到表尾

//此时已存在头节点,再插入一个节点（首节点） struct link *p = NULL,*pr = head; p = (struct link *)malloc(sizeof(struct link)); if(p == NULL){ exit(0); } if(head == NULL){ head = p; }else{ while(pr->next != NULL){ //当头节点的指针域不为NULL pr = pr->next; //pr指向下一个节点的地址 } pr->next = p; //使头节点的指针域存储下一个节点的地址 }

完整操作

#include 
  
    #include 
   
     struct link *AppendNode(struct link *head); void DisplayNode(struct link *head); void DeleteMemory(struct link *head); //定义结构体 struct link{ int data; //定义数据域 struct link *next; //定义指针域 }; int main(){ int i =0; //定义i，记录创建的节点数 char c; struct link *head = NULL; //创建头指针，初始化为NULL printf("DO you wang to append a new node(Y or N)?"); scanf(" %c",&c); while(c == 'Y' || c == 'y'){ //如果确定继续添加结点 head = AppendNode(head); //通过函数获得链表的地址，AppendNode函数返回的是链表的头指针 //可以根据头指针指向的地址来获取链表中保存的数据 DisplayNode(head); //根据头指针打印链表 printf("DO you want to append a new node(Y or N)?"); scanf(" %c",&c); i++; } printf("%d new nodes hava been appended!\n",i); DeleteMemory(head); //释放占用的内存 } struct link *AppendNode(struct link *head){ //声明创建节点函数 struct link *p = NULL,*pr = head; //创建p指针，初始化为NULL；创建pr指针，通过pr指针来给指针域赋值 int data ; p = (struct link *)malloc(sizeof(struct link)) ; //为指针p申请内存空间，必须操作，因为p是新创建的节点 if(p == NULL){ //如果申请内存失败，则退出程序 printf("NO enough momery to allocate!\n"); exit(0); } if(head == NULL){ //如果头指针为NULL,说明现在链表是空表 head = p; //使head指针指向p的地址(p已经通过malloc申请了内存，所以有地址） }else{ //此时链表已经有头节点 ，再一次执行了AppendNode函数 //注：假如这是第二次添加节点 //因为第一次添加头节点时，pr = head，和头指针一样指向头节点的地址 while(pr->next!= NULL){ //当pr指向的地址，即此时的p的指针域不为NULL(即p不是尾节点) pr = pr->next; //使pr指向头节点的指针域 } pr->next = p; //使pr的指针域指向新键节点的地址，此时的next指针域是头节点的指针域 } printf("Input node data:"); scanf("%d",&data); p->data = data; //给p的数据域赋值 p->next = NULL; //新添加的节点位于表尾，所以它的指针域为NULL return head; //返回head的地址 } void DisplayNode(struct link *head){ //输出函数，打印链表 struct link *p = head; // 定义p指针使其指向头节点 int j = 1; //定义j记录这是第几个数值 while(p != NULL){ //因为p = p->next,所以直到尾节点打印结束 printf("%5d%10d\n",j,p->data); p = p->next; //因为节点已经创建成功，所以p的指向由头节点指向下一个节点(每一个节点的指针域都指向了下一个节点) j++; } } void DeleteMemory(struct link *head){ //释放资源函数 struct link *p = head,*pr = NULL; //定义p指针指向头节点 while(p != NULL){ //当p的指针域不为NULL pr = p; //将每一个节点的地址赋值给pr指针 p = p->next; //使p指向下一个节点 free(pr); //释放此时pr指向节点的内存 } } 
    
  

第二种创建链表方式-优化

#include 
  
    #include 
   
     struct Stu *create(int n); void print(struct Stu *head); struct Stu{ int id; char name[50]; struct Stu *next; }; int main(){ int n; struct Stu *head = NULL; //创建头指针 printf("请输入你想要创建的节点个数：\n"); scanf("%d",&n); head = create(n); print(head); } struct Stu *create(int n){ struct Stu *head,*node,*end; //定义头节点，普通节点，尾节点 head = (struct Stu *)malloc(sizeof(struct Stu)); //给头节点申请内存 end = head; //若是空表，则头尾地址一致 for(int i=0;i 
    
      id,node->name); //给数据域赋值 end->next = node; //让上一个节点的数据域指向当前节点 end = node; //end指向当前节点，最终end指向尾节点 } end->next = NULL; //给end的指针域置空 return head; //返回头节点的地址 } void print(struct Stu *head){ struct Stu *p = head; int j =1; p = p->next; //不打印头节点的数据域中的值 while(p != NULL){ printf("%d\t%d\t%s\n",j,p->id,p->name); p = p->next; j++; } } 
     
    
  

前插法创建链表 –逆序输出

struct link *create(int n){ struct link *headnode ,*node; headnode = (struct link *)malloc(sizeof(struct link)); //为头节点申请内存 headnode ->next = NULL; //让头节点的指针域置空 for(int i=0;i 
  
    data); //新建节点数据域传值 node->next = headnode->next; //新建节点的数据域指向头节点 == 创建尾节点 headnode->next = node; //将新建节点数据域传给头节点 } return headnode; } 
  

删除节点

void deleteNode(struct Stu *head,int n){ //删除n处的节点 struct Stu *p = head,*pr = head; int i =0; while(i 
  
    next; //p指向下一节点 i++; } if(p!=NULL){ //当p不为空时，即p不能指向尾节点之后的节点 pr->next = p->next; free(p); } else{ printf("节点不存在！\n"); } } 
  

我在这着重解释一下p->next = NULL和p!=NULL的区别，因为我刚开始也经常弄错！！

• while(p->next ！= NULL) 循环结束时，此时p的位置是尾节点的位置，但如果用于输出函数的判断条件，则尾节点的数据不会输出。
• while(p!=NULL) 循环结束时， 此时p指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。

插入节点

void insertNode(struct Stu *head,int n){ //插入节点 struct Stu *p = head,*pr; pr = (struct Stu*)malloc(sizeof(struct Stu)); //让pr指向新建节点申请的内存 printf("input data:\n"); scanf("%d %s",&pr->id,pr->name); int i = 0; //当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空 while(i 
  
    next; i++; } if(p!=NULL){ //如果p没越界 pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 p->next = pr; //使插入节点指向新建节点 }else{ printf("节点不存在！\n"); } } 
  

修改节点

void change(struct Stu *head,int n){ struct Stu *p = head; int i = 0; while(i 
  
    next; i++; } if(p != NULL){ printf("请输入修改之后的值:\n"); scanf("%d %s",&p->id,p->name); }else{ printf("节点不存在！\n"); } 
  

链表的逆序

思路：假如此时链表有两个有效节点，头节点为0号，中间的节点为1号，尾节点为2号

1.定义三个指针pf指向链表的头节点（0号），tmp，pb初始化为NULL

2.让pb指向pf的下一个节点（1号），并将此时头节点的指针域置空（变为尾节点）

3.第一次while循环，让tmp指向pb（1号），然后让pb指向下一个节点，再让tmp让1号节点的指针域（tmp->next = pf)指向pf(上一个节点）（0号），再将pf指向tmp（1号）(pf = tmp)

4.第二次while循环，让tmp指向pb（2号），然后让pb指向下一个节点，此时pb==NULL，所以这是最后一次循环，再让tmp让2号节点的指针域（tmp->next = pf)指向pf（1号），再将pf指向tmp（2号）

 5.此时链表逆序完成，让头指针指向首节点（2号），返回头指针即可

                                                                          逆序后

STU *link_reversed_order(STU *head) { STU *pf = NULL, *pb = NULL, *tmp = NULL; pf = head; //将头节点的地址赋值给pf if(head == NULL) { //如果链表为空 printf("链表为空，不需要逆序！\n"); return head; } else if(head->next == NULL) { //如果只有一个节点 printf("链表只有一个节点，不需要逆序！\n"); return head; } else { pb = pf->next; //pb指向pf的下一个节点 head->next = NULL; //头节点的指针域置空(变为尾节点) while(pb != NULL) //当pb不为空时 { tmp = pb; //将pb的地址赋值给temp pb = pb->next; //pb指向下一个节点 tmp->next = pf; //pb的上一个节点的指针域指向pf pf = tmp; //让pf指向tmp } head = pf; return head; } }*/

所有操作

#include 
  
    #include 
   
     struct Stu *create(int n); void print(struct Stu *head); void deleteNode(struct Stu *head,int n); void insertNode(struct Stu *head,int n); void change(struct Stu *head,int n); struct Stu{ int id; char name[50]; struct Stu *next; }; int main(){ int n,j,in,cn; char c; struct Stu *head = NULL; //创建头指针 printf("请输入你想要创建的节点个数：\n"); scanf("%d",&n); head = create(n); print(head); while(true){ printf("请选择你想要执行的操作：\n"); printf("1.插入节点\n2.删除节点\n3.修改节点\n4.退出程序\n"); scanf(" %c",&c); if(c =='1'){ printf("你想要在哪插入节点：\n"); scanf("%d",&in); insertNode(head,in); print(head); }else if(c == '2'){ printf("你想要删除哪个节点的数据：\n"); scanf("%d",&j); deleteNode(head,j); print(head); }else if(c =='3'){ printf("你想要修改哪个节点的数据：\n"); scanf("%d",&cn); change(head,cn); print(head); }else if(c =='4'){ exit(0); } } } struct Stu *create(int n){ struct Stu *head,*node,*end; //定义头节点，普通节点，尾节点 head = (struct Stu *)malloc(sizeof(struct Stu)); //给头节点申请内存 //head->id = n; //头节点的数据域保存链表的长度 end = head; //若是空表，则头尾地址一致 for(int i=0;i 
    
      id,node->name); //给数据域赋值 end->next = node; //让上一个节点的数据域指向当前节点 end = node; //end指向当前节点，最终end指向尾节点 } end->next = NULL; //给end的指针域置空 return head; //返回头节点的地址 } void print(struct Stu *head){ struct Stu *p = head; int j =1; p = p->next; //不打印头节点的数据域中的值 while(p != NULL){ printf("%d\t%d\t%s\n",j,p->id,p->name); p = p->next; j++; } } void deleteNode(struct Stu *head,int n){ //删除n处的节点 struct Stu *p = head,*pr = head; int i =0; while(i 
     
       next; i++; } if(p!=NULL){ pr->next = p->next; free(p); } else{ printf("节点不存在！\n"); } } void insertNode(struct Stu *head,int n){ //插入节点 struct Stu *p = head,*pr; pr = (struct Stu*)malloc(sizeof(struct Stu)); //让pr指向新建节点申请的内存 printf("input data:\n"); scanf("%d %s",&pr->id,pr->name); int i = 0; //当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空 while(i 
      
        next; i++; } if(p!=NULL){ //如果p没越界 pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 p->next = pr; //使插入节点指向新建节点 }else{ printf("节点不存在！\n"); } } void change(struct Stu *head,int n){ struct Stu *p = head; int i = 0; while(i 
       
         next; i++; } if(p != NULL){ printf("请输入修改之后的值:\n"); scanf("%d %s",&p->id,p->name); }else{ printf("节点不存在！\n"); } }