数据结构学习——链表（C语言版）

太过爱你忘了你带给我的痛 2022-12-24 15:58 185阅读 0赞

### 数据结构学习——链表的简单解析 ###

*  一、何为链表
 *   *  （1）概念：
     *  （2）特点：
 *  二、链表的简单实现
 *   *  （1）头插法：
     *  （2）尾插法
     *  （3）模拟学生管理系统：

# 一、何为链表 #

## （1）概念： ##

> 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)

> 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大

## （2）特点： ##

链表有很多种：**单向链表**，**双向链表**以及**循环链表**

先从最简单的单向链表开始，其主要特点如下：

*  是一种线性结构（和数组一样）
 *  每个节点存储下一个节点的指针（而数组是根据下标访问）
 *  是一种动态数据结构，不需要预先设置大小
 *  不支持随机访问（Random Access）

![在这里插入图片描述][2020112916384539.jpg_pic_center]

> 上图是单链表基本结构，每个节点除了存储自身的数据外，还需要存储指向下一个节点的指针，分别称为数据域和指针域，最后一个节点的指针指向NULL

*  A节点称为头结点
 *  E节点称为尾结点
 *  A节点称为B节点的前驱节点
 *  B节点称为A节点的后继节点

> 因为每个节点至多只能有一个前驱节点和一个后继节点，所以链表是线性结构。由于链表依靠指针相互连接，可以无限扩展，不需要预先设置链表的大小。又由于链表没有下标，所以不支持随机访问，只能通过指针进行遍历访问

# 二、链表的简单实现 #

> 这里以头插法和尾插法为例子，两种方法运行结果都有，可以体现不同的数据排列结构

## （1）头插法： ##

#include<stdio.h>
    #include<stdlib.h>
    
    struct Data{
        
    	
    	int Data;
    	struct Data *next;	//	节点移动指针
    	
    };
    struct Data* InsertData(struct Data *head,struct Data *new1)
    {
        
    	struct Data *p =head;
    
    	if( p == NULL)	//	判断是否是第一个节点
    	{
        
    			head = new1;
    		
    	}
    	else{
        		//	第二个节点开始，把节点之间连接起来
    			
    		new1->next = head;		//	让新节点指向旧节点
    		head = new1;			//	让新节点变成头节点
    		
    	}
    		
    	return head;
    	
    }
    struct Data* CreateData(struct Data *head)
    {
        
    	
    	struct Data *p;
    	while(1)
    	{
        	
    		p = (struct Data *)malloc(sizeof(struct Data));	//	开辟一个节点空间
    		
    		//	非Linux环境下，一定要注意创建的第一个节点是否指向NULL
    		p->next = NULL;		//	使得第一个头节点指向NULL，为了后续打印退出
    							//	在Linux系统中会自动补上最后一个节点指向NULL
    							
    		printf("请输入数据:\n");
    		scanf("%d",&(p->Data));
    		 
    		if( p ->Data == 0)		//	碰到0结束输入
    		{
        
    			
    			return head;
    		}
    		
    		head = InsertData(head,p);	//	每输入一个数据存入对应的节点
    		
    	}
    	
    }
    
    void show(struct Data *head)
    {
        
    	
    	while( head != NULL)	//	从尾巴开始打印直到碰到头节点指向NULL
    	{
        
    		printf("%d\n",head->Data);
    		
    	
    		
    		head = head->next;	//	每输出一个数据，节点指针移动
    		
    	}
    
    	
    }
    
    int main()
    {
        
    	struct Data *head = NULL;		//	创建头节点指针
    	head = CreateData(head);		//	返回创建后的头节点指针
    
    	show(head);						//	打印链表数据
    	
    	return 0;
    }

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]

## （2）尾插法 ##

#include<stdio.h>
    #include<stdlib.h>
    
    struct Data{
        
    	
    	int Data;
    	struct Data *next;	//	节点移动指针
    	
    };
    
    struct Data* InsertBehind(struct Data *head,struct Data *new1)
    {
        
    	struct Data *p =head;
    
    	if( p == NULL)		//	判断是否创建第一个节点
    	{
        
    			head = new1;	//	让新节点变成头
    			return head; 
    	}
    	while(p->next != NULL)	//	尾巴开始遍历
    	{
        
    		p=p->next;		//	遍历到链表最后一个节点
    						//	也就是让尾巴节点当成头节点
    	}
    	p->next = new1;		//	在尾巴节点（头节点）开始连接新的节点
    	return head;
    	
    }
    
    struct Data* CreateData(struct Data *head)
    {
        
    	
    	struct Data *p;
    	while(1)
    	{
        	
    		p = (struct Data *)malloc(sizeof(struct Data));	//	开辟一个节点空间
    		
    		//	非Linux环境下，一定要注意创建的第一个节点是否指向NULL
    		p->next = NULL;		//	使得第一个头节点指向NULL，为了后续打印退出
    							//	在Linux系统中会自动补上最后一个节点指向NULL
    							
    		printf("请输入数据:\n");
    		scanf("%d",&(p->Data));
    		 
    		if( p ->Data == 0)		//	碰到0结束输入
    		{
        
    			
    			return head;
    		}
    		
    		head = InsertBehind(head,p);	//	每输入一个数据存入对应的节点
    		
    	}
    	
    }
    
    void show(struct Data *head)
    {
        
    	
    	while( head != NULL)	//	从尾巴开始打印直到碰到头节点指向NULL
    	{
        
    		printf("%d\n",head->Data);
    		
    	
    		
    		head = head->next;	//	每输出一个数据，节点指针移动
    		
    	}
    
    	
    }
    
    int main()
    {
        
    	struct Data *head = NULL;		//	创建头节点指针
    	head = CreateData(head);		//	返回创建后的头节点指针
    
    	show(head);						//	打印链表数据
    	
    	return 0;
    }

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70 1]

## （3）模拟学生管理系统： ##

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    struct Data{
        
    	
    	int Age;			//	年龄 
    	int ID;				//	学号 
    	
    	char Name[20];		//	姓名 
    	char Sex[10];		//	性别	 
    	char Time[20];		//	出生年月 
    	char Major[20];		//	专业 
    	
    	struct Data *next;	//	指向链表下一个节点 
    };
    
    struct Data *CreateLink()
    {
        
    	struct Data *new = (struct Data*)malloc(sizeof(struct Data));	//	开辟链表内存空间 
    	
    	new ->next = NULL;	//	让链表尾结点先指向NULL 
    
    	return new;		//	返回头节点 
    } 
    
    //	链表初始化 
    struct Data *Init_Link(int id,char *name,char *sex,int age,char *major,char *born)
    {
        
    	struct Data *q = (struct Data *)malloc(sizeof(struct Data));
    	q->ID = id;
    	q->Age= age;
    	strcpy(q->Name,name);
    	strcpy(q->Sex,sex);
    	strcpy(q->Major,major);
    	strcpy(q->Time,born);
    	return q; 
    	
    }
    
    //	尾插法 
    void InsertStudentLink_Behind(struct Data *head,int id,char *name,char *sex,int age,char *major,char *born)
    {
        
    	struct Data *add = Init_Link(id,name,sex,age,major,born);	//	初始化学生信息 
    	struct Data *p = head;									//	链表头 
    	
    	while(p->next != NULL){
        									 
    		p = p->next;			//	遍历到链表的尾巴，此时尾巴当做头节点
    	}
    	add->next = NULL;			//	头指向空先 
    	p->next = add;									
    }
    
    //	删除学生信息链表节点
    void  DeleteLink(struct Data *head,int id )
    {
        
    	struct Data *p = head;		//	用来确认要删除的那个节点的前一个节点
    	struct Data *q = head->next;//	当前下一个节点开始寻找要删除的节点
    	
    	while(q->ID != id)
    	{
        
    		p = p->next;	//	节点遍历移动下一个继续寻找 
    		q = q->next;	
    	} 
    	p ->next = q->next; 
    }
    
    //	查找在链表中学生信息 
    struct Data *SearchLink(struct Data *head,char *StudentName)
    {
        
    	struct Data *p = head->next;		
    	while(strcmp(p->Name,StudentName) != 0)	//	查询学生姓名是否和形参StudentName一致的学生 
    	{
        
    		if(p->next == NULL)		//	遍历到链表的尾部还找不到 
    		{
        
    			printf("找不到这个学生\n");
    		}
    		p = p->next;
    	}
    
    	printf("\n查询信息如下:\n");
    	printf("学号为: %d\n",p->ID);
    	printf("姓名为: %s\n",p->Name);
    	printf("性别: %s\n",p->Sex);
    	printf("年龄: %d\n",p->Age);
    	printf("专业: %s\n",p->Major);
    	printf("出生年月: %s\n",p->Time);
    	return p;
    	
    }
    //	打印学生的信息
    void ShowData(struct Data *head)
    {
        
    	struct Data *p = head->next;
    	if( p == NULL)
    	{
        
    		printf("没有学生信息\n");
    	}
    	
    	while( p)
    	{
        
    		printf("学号为: %d\n",p->ID);
    		printf("姓名为: %s\n",p->Name);
    		printf("性别: %s\n",p->Sex);
    		printf("年龄: %d\n",p->Age);
    		printf("专业: %s\n",p->Major);
    		printf("出生年月: %s\n",p->Time);
    		putchar('\n');
    		
    		p = p->next;		
    		
    	}
    	
    } 
    //	修改学生信息数据 
    void XiuGaiData(struct Data *head)
    {
        
    	char a[20] = {
        '\0'};
        char num[20] = {
        '\0'};
        printf("请输入你想修改学生的姓名: ");
        scanf("%s",&num);
    	struct Data *q=SearchLink(head,num);
    	printf("请选择你想修改的值（姓名、性别、专业、出生年月）:");
    	scanf("%s",a);
    	printf("请输入你改的内容：");
    	if(strcmp(a,"姓名")==0)
    	    scanf("%s",q->Name);
    	else if(strcmp(a,"性别")==0)
    	    scanf("%s",q->Sex);
        else if(strcmp(a,"专业")==0)
    	    scanf("%s",q->Major);
    	else if (strcmp(a,"出生年月")==0)
    		scanf("%s",q->Time);
    	else 
    	    printf("查无此名");  
    } 
    
    //	界面初始化 
    void Init_JieMian()
    {
        
    	printf("********************************\n");
    	printf("*                              *\n");
    	printf("*                              *\n");
    	printf("*       1.插入学生信息         *\n");
    	printf("*       2.查找学生信息         *\n");
    	printf("*       3.删除学生信息         *\n");
    	printf("*       4.修改学生信息         *\n");
    	printf("*       5.打印所有学生信息     *\n");
    	printf("*       6.退出系统             *\n");
    	printf("*                              *\n");
    	printf("*                              *\n");
    	printf("********************************\n");	
    	
    } 
    //	输入指令 
    int ChoiceStudent()
    {
        
    	int n;
    	printf("请输入你的指令:\n");
    	scanf("%d",&n);
    	
    	while(n<1 || n>6){
        
    		printf("无法实现这个功能，请重新输入指令:\n");
    		scanf("%d",&n);
    	}
    	return n;
    }
    
    void HandleData(struct Data *head)
    {
        
    	int p;
    	
    	Init_JieMian();			//	初始化界面 
    		
    	p = ChoiceStudent();	//	输入指令，进行分类 
    	switch(p){
        
    		case 1:
    			{
        	
    				char name[20] = {
        '\0'};		//	姓名 
    				char sex[20]  = {
        '\0'};		//	性别 
    				char born[20] = {
        '\0'};		//	出生年月日 
    				char major[20]= {
        '\0'};		//	专业 
    				int id = 0;					//	学号 
    				int age= 0;					//	年龄 
    				
    				printf("请输入学号、姓名、性别、年龄、专业、出生年月\n");
    				scanf("%d",&id);
    				scanf("%s",name);
    				scanf("%s",sex); 
    				scanf("%d",&age);
    				scanf("%s",major);
    				scanf("%s",born);
    				InsertStudentLink_Behind(head,id,name,sex,age,major,born);	//	尾插法 
    			} 
    			break;
    		
    		case 2:
    		{
        
    			char StudentName[20] = {
        '\0'};
    			printf("请输入你要查找的学生的姓名:\n");
    			scanf("%s",StudentName);
    			SearchLink(head,StudentName);	
    		}
    			break;
    		
    		case 3:
    			{
        
    				int StudentId;
    				printf("请输入你要删除的学生学号:\n");
    				scanf("%d",&StudentId);
    				DeleteLink(head,StudentId);
    			}
    			break;
    			
    		case 4:
    			{
        
    				XiuGaiData(head);
    			}
    			break;
    			
    		case 5:
    			{
        
    				ShowData(head);
    			}
    			break;
    		case 6:
    			{
        
    				printf("\n感谢你的使用 \n"); 
    				exit(-1);					//	结束进程 
    			}
    		default:
    			printf("命令错误,请重新输入\n");
    			break;
    	} 
    	
     } 
    
    int main()
    {
        
    	struct Data *head = CreateLink();	//	创建头节点 
    	
    	while(1){
        
    		HandleData(head);	//	将指令进行选择功能处理 
    	}
    		
    	return 0;
    }

[2020112916384539.jpg_pic_center]: /images/20221120/a46d13f7ff7042139d130d80e4f0ea76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201129165058164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201129170131623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl,size_16,color_FFFFFF,t_70