菜鸟笔记
提升您的技术认知
当前位置：菜鸟笔记 > C 笔记 > 正文

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 <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指向节点的内存 
	}
}

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

#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++;
	}
}

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

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;  
}

 

删除节点

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指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。

插入节点

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");
	}

链表的逆序

 

思路：假如此时链表有两个有效节点，头节点为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 <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");
	} 	 
}

相关推荐

菜鸟笔记

热门教程