C语言链表操作详解

朱雀 2022-04-01 06:41 230阅读 0赞

## 为什么要使用链表 ##

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

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

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

### 链表的特点： ###

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

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

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

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

## 创建链表前须知 ##

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

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

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

### 建立一个单向链表 ###

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 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 <stdio.h>
    #include <stdlib.h>
    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指向节点的内存 
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 3][]

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

#include <stdio.h> 
    #include <stdlib.h>
    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<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->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++;
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 4][]

### 前插法创建链表 --逆序输出 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 5][]

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

### 删除节点 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 6][]

void deleteNode(struct Stu *head,int n){         //删除n处的节点 
    	struct  Stu *p = head,*pr = head;
    	int i =0;
    	while(i<n&&p!=NULL){       //到达指定节点，此时p指向指定节点，pr指向上一节点 
    		pr = p;            //将p的地址赋值给pr
    		p = p->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指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。**

### **插入节点** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 7][]

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<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->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<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在！\n");
    	}

### 链表的逆序 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 8][]

**思路：假如此时链表有两个有效节点，头节点为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号），返回头指针即可**

**                                                                          逆序后**

![20181231144703290.png][]

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 <stdio.h> 
    #include <stdlib.h>
    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<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->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<n&&p!=NULL){       //到达指定节点，此时p指向指定节点，pr指向上一节点 
    		pr = p;
    		p = p->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<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->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<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在！\n");
    	} 	 
    }

[Link 1]: https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8
[Link 2]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8
[Link 3]: https://baike.baidu.com/item/%E5%A4%B4%E6%8C%87%E9%92%88/9794674
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20220401/4a85d8ef7bf24ab3a6116d2bf14951bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20220401/d703654ad2984a878c8f2701b2a5170d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2]: /images/20220401/0889f8d535d34bd7924f54fc8156fa1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 3]: /images/20220401/97d7fad8c7854a3bb26fb9a37ae14237.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 4]: /images/20220401/d1c437130e384df5ba6115f43744c46c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 5]: /images/20220401/f75fed97b3c842a2ad0952aa12aacc62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 6]: /images/20220401/d0a86b765f3d4c3ba70cc3599e1e53c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 7]: /images/20220401/ec92039699c444668d9b11778a79dfa5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 8]: /images/20220401/648bd5ba9f854aa5a42474b81fbca75f.png
[20181231144703290.png]: /images/20220401/1deb948105674ba6b24171b88d826e28.png