投稿
  1. 极客之音首页
  2. 数据结构

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

小半 • • 数据结构 • 阅读 308

导读：本篇文章讲解 数据结构学习——链表（C语言版），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

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

一、何为链表

（1）概念：

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

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

（2）特点：

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

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

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

在这里插入图片描述

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

运行结果：
在这里插入图片描述

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

运行结果：
在这里插入图片描述

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

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/68451.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！