C语言_链表总结

举报
DS小龙哥 发表于 2022/03/30 09:20:54 2022/03/30
【摘要】 本篇文章介绍C语言链表相关知识点，涉及链表的创建、单向链表、循环链表、双向链表、单向循环链表，链表常见问题总结等，还列出了结构体数组与链表的练习题，将在下篇文章贴出完整代码。

本篇文章介绍C语言链表相关知识点，涉及链表的创建、单向链表、循环链表、双向链表、单向循环链表，链表常见问题总结等，还列出了结构体数组与链表的练习题，将在下篇文章贴出完整代码。

1. 链表

1.1 结构体对比

数组特性: 内存空间连续、只能存放相同类型的数据
结构体特性: 内存空间连续、可以存放不同类型的数据

#include <stdio.h>
struct MyStruct
{
	int a;
	char b;
};

int main()
{
	struct MyStruct *p;
	struct MyStruct data={12,'A'};
	data.a=123;
	data.b='B';

	p=&data;
	printf("%d\n",p->a);
	printf("%c\n",p->b);
	return 0;
}

数组学生管理系统作业：

作业:   学生管理系统
需求:   (每一个功能都是使用函数进行封装)
1.实现从键盘上录入学生信息。 (姓名、性别、学号、成绩、电话号码)
2.将结构体里的学生信息全部打印出来。
3.实现根据学生的姓名或者学号查找学生，查找到之后打印出学生的具体信息。
4.根据学生的成绩对学生信息进行排序。
5.根据学号删除学生信息。

1.2 单向链表的创建与运用

链表: 单链表、双链表 区分: 循环和不循环链表
链表的特性: 一种数据结构的运行—>结构体。

学习结构体数组(编写学生管理系统): 学生的人数问题不好确定。
链表本身就是一个结构体。

单向链表的创建与运用:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义结构体
struct MyListStruct
{
	int a;
	struct MyListStruct *next; //结构体指针。存放下一个节点的地址
};

//定义链表头
struct MyListStruct *ListHead=NULL; 

//函数声明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void  PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);


int main()
{
	int i;
	struct MyListStruct temp;
	int a;
	//1. 创建链表头
	ListHead=CreateListHead(ListHead);

	//2. 添加节点
	for(i=0; i<5; i++)
	{
		printf("输入新节点数据:");
		scanf("%d",&temp.a);
		AddListNode(ListHead,temp);
	}

	//3. 打印所有节点数据
	PintListInfo(ListHead);

	//4. 删除节点数据
	printf("输入删除的节点数据值:");
	scanf("%d",&a);
	DeleteListNode(ListHead,a);

	//5. 打印所有节点数据
	PintListInfo(ListHead);
	return 0;
}


/*
函数功能: 创建链表头
返回值  : 链表头指针
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
	if(head==NULL)
	{
		head=malloc(sizeof(struct MyListStruct));
		head->next=NULL; 
	}
	return head; //返回链表头
}

/*
函数功能: 添加链表节点
说明: 链表头一般不存放数据
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
	struct MyListStruct *p=head; //保存头地址
	struct MyListStruct *new_p=NULL;  //新的节点

	/*1. 寻找链表尾*/
	while(p->next!=NULL)
	{
		p=p->next; //移动到下一个地址
	}
    /*2. 创建新节点*/
	new_p=malloc(sizeof(struct MyListStruct));
	if(new_p==NULL)
	{
		printf("新节点内存申请失败!\n");
		return;
	}
	/*3. 新节点赋值*/
	memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝
	new_p->next=NULL; //尾节点指向空

	/*4. 新节点添加*/
	p->next=new_p;
}

/*
函数功能: 删除链表节点
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
	struct MyListStruct *p=head; //保存头地址
	struct MyListStruct *tmp=NULL;
	/*查找数据存在的节点位置*/
	while(p->next!=NULL)
	{
		tmp=p; //保存上一个节点的地址
		p=p->next;
		if(p->a==a)  //查找成功
		{
			tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域
			//tmp->next=tmp->next->next;
			free(p); //直接释放p节点空间
			//break;
			p=head; //重新指向链表头
		}
	}
}


/*
函数功能: 遍历所有链表信息
*/
void  PintListInfo(struct MyListStruct *head)
{
	int cnt=0;
	struct MyListStruct *p=head;
	printf("\n链表遍历的数据如下:\n");
	while(p->next!=NULL)
	{
		p=p->next;
		cnt++;
		printf("第%d个节点的数据=%d\n",cnt,p->a);
	}
}

作业:

1.看代码、理解链表的创建流程
2.编写出单向链表的基础运用
3.将之前的学生管理系统使用链表方式做出来

链表的功能:
(1)创建链表头
(2)在链表结尾添加一个节点
(3)删除指定的一个链表节点
(4)遍历链表，打印出所有的数据。
(5)在链表的指定节点的后面添加一个节点。
(6)根据链表节点里的数据对链表进行排序。
    
    
双向链表:
(1)使用逆向+顺向两种遍历方式删除链表节点，目的: 提高效率。
     类似于二分法查找。

2. 链表问题总结

动态空间分配:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	char *p=malloc(100); //申请动态空间。
	if(p==NULL)
	{
		return -1;
	}
	strcpy(p,"1234567890");
	printf("%s\n",p);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	char *p1=malloc(100); //申请动态空间。
	printf("%p\n",p1);
	char *p2=malloc(100); //申请动态空间。
	printf("%p\n",p2);
	char *p3=malloc(100); //申请动态空间。
	printf("%p\n",p3);
	char *p4=malloc(100); //申请动态空间。
	printf("%p\n",p4);
	return 0;
}
错误解决:
1.第一个错误开始解决
2.常规错误:  函数没有声明、分号每加、括号没有加、=
3.括号没有对齐。

3. 双向链表和循环链表

3.1 单向循环链表:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义结构体
struct MyListStruct
{
	int a;
	struct MyListStruct *next; //结构体指针。存放下一个节点的地址
};

//定义链表头
struct MyListStruct *ListHead=NULL;

//函数声明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void  PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);


int main()
{
	int i;
	struct MyListStruct temp;
	int a;
	//1. 创建链表头
	ListHead=CreateListHead(ListHead);

	//2. 添加节点
	for(i=0; i<5; i++)
	{
		printf("输入新节点数据:");
		scanf("%d",&temp.a);
		AddListNode(ListHead,temp);
	}

	//3. 打印所有节点数据
	PintListInfo(ListHead);

	//4. 删除节点数据
	printf("输入删除的节点数据值:");
	scanf("%d",&a);
	DeleteListNode(ListHead,a);

	//5. 打印所有节点数据
	PintListInfo(ListHead);
	return 0;
}


/*
函数功能: 创建链表头
返回值  : 链表头指针
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
	if(head==NULL)
	{
		head=malloc(sizeof(struct MyListStruct));
		head->next=head;
	}
	return head; //返回链表头
}

/*
函数功能: 添加链表节点
说明: 链表头一般不存放数据
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
	struct MyListStruct *p=head; //保存头地址
	struct MyListStruct *new_p=NULL;  //新的节点
    
	/*1. 寻找链表尾*/
	while(p->next!=head)
	{
		p=p->next; //移动到下一个地址
	}
	/*2. 创建新节点*/
	new_p=malloc(sizeof(struct MyListStruct));
	if(new_p==NULL)
	{
		printf("新节点内存申请失败!\n");
		return;
	}
	/*3. 新节点赋值*/
	memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝
	new_p->next=head; //尾节点指向头

	/*4. 新节点添加*/
	p->next=new_p;
}

/*
函数功能: 删除链表节点
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
	struct MyListStruct *p=head; //保存头地址
	struct MyListStruct *tmp=NULL;

	/*查找数据存在的节点位置*/
	while(p->next!=head)
	{
		tmp=p; //保存上一个节点的地址
		p=p->next;
		if(p->a==a)  //查找成功
		{
			tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域
							   //tmp->next=tmp->next->next;
			free(p); //直接释放p节点空间
					 //break;
			p=head; //重新指向链表头
		}
	}
}


/*
函数功能: 遍历所有链表信息
*/
void  PintListInfo(struct MyListStruct *head)
{
	int cnt=0;
	struct MyListStruct *p=head;
	printf("\n链表遍历的数据如下:\n");
	while(p->next!=head)
	{
		p=p->next;
		cnt++;
		printf("第%d个节点的数据=%d\n",cnt,p->a);
	}
}

3.2 双向链表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义结构体
struct MyListStruct
{
	int a;
	struct MyListStruct *next; //结构体指针。存放下一个节点的地址
	struct MyListStruct *old;  //结构体指针。存放上一个节点的地址
};


//定义链表头
struct MyListStruct *ListHead=NULL;

//函数声明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void  PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);
void  PintListInfo_old(struct MyListStruct *head);


int main()
{
	int i;
	struct MyListStruct temp;
	int a;
	//1. 创建链表头
	ListHead=CreateListHead(ListHead);

	//2. 添加节点
	for(i=0; i<5; i++)
	{
		printf("输入新节点数据:");
		scanf("%d",&temp.a);
		AddListNode(ListHead,temp);
	}

	//3. 打印所有节点数据
	PintListInfo(ListHead);
	PintListInfo_old(ListHead);

	//4. 删除节点数据
	printf("输入删除的节点数据值:");
	scanf("%d",&a);
	DeleteListNode(ListHead,a);

	//5. 打印所有节点数据
	PintListInfo(ListHead);
	PintListInfo_old(ListHead);
	return 0;
}


/*
函数功能: 创建链表头
返回值  : 链表头指针
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
	if(head==NULL)
	{
		head=malloc(sizeof(struct MyListStruct));
		head->next=NULL; //尾节点指向空
		head->old=head;  //上一个节点指向头
	}
	return head; //返回链表头
}

/*
函数功能: 添加链表节点
说明: 链表头一般不存放数据
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
	struct MyListStruct *p=head;     //保存头地址
	struct MyListStruct *new_p=NULL; //新的节点
    
	/*1. 寻找链表尾*/
	while(p->next!=NULL)
	{
		p=p->next; //移动到下一个地址
	}
	/*2. 创建新节点*/
	new_p=malloc(sizeof(struct MyListStruct));
	if(new_p==NULL)
	{
		printf("新节点内存申请失败!\n");
		return;
	}
	/*3. 新节点赋值*/
	memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝
	new_p->next=NULL; //尾节点指向NULL
	new_p->old=p;     //保存上一个节点的地址
	/*4. 新节点添加*/
	p->next=new_p;
}

/*
函数功能: 删除链表节点
顺向删除。
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
	struct MyListStruct *p=head; //保存头地址
	struct MyListStruct *tmp=NULL;

	/*查找数据存在的节点位置*/
	while(p->next!=NULL)
	{
		tmp=p; //保存上一个节点的地址
		p=p->next;
		if(p->a==a)  //查找成功
		{
			tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域
							   //tmp->next=tmp->next->next;
			p->next->old=tmp;  //保存上一个节点的地址

			free(p); //直接释放p节点空间
					 //break;
			p=head; //重新指向链表头
		}
	}
}


/*
函数功能: 遍历所有链表信息
从头到尾遍历
*/
void  PintListInfo(struct MyListStruct *head)
{
	int cnt=0;
	struct MyListStruct *p=head;
	printf("\n(顺向)链表遍历的数据如下:\n");
	while(p->next!=NULL)
	{
		p=p->next;
		cnt++;
		printf("第%d个节点的数据=%d\n",cnt,p->a);
	}
}

/*
函数功能: 遍历所有链表信息
从尾到头遍历
*/
void  PintListInfo_old(struct MyListStruct *head)
{
	int cnt=0;
	struct MyListStruct *p=head;
	printf("\n(逆向)链表遍历的数据如下:\n");
	/*1. 找到链表尾*/
	while(p->next!=NULL)
	{
		p=p->next;
	}
	/*2. 通过链表尾遍历链表的数据*/
	while(p!=head)
	{
		cnt++;
		printf("第%d个节点的数据=%d\n",cnt,p->a);
		p=p->old; //访问上一个节点
	}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C语言 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入