第二部分—C语言提高篇_9. 链表

9.1 链表基本概念

9.1.1 什么是链表

 

1. 链表是一种常用的数据结构，它通过指针将一些列数据结点，连接成一个数据链。相对于数组，链表具有更好的动态性（非顺序存储）。
2. 数据域用来存储数据，指针域用于建立与下一个结点的联系。
3. 建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。
4. 链表的开销，主要是访问顺序性和组织链的空间损失。

数组和链表的区别：

数组：一次性分配一块连续的存储区域。 优点：随机访问元素效率高 缺点：1) 需要分配一块连续的存储区域（很大区域，有可能分配失败）            2) 删除和插入某个元素效率低 链表：无需一次性分配一块连续的存储区域，只需分配n块节点存储区域，通过指针建立关系。 优点：1) 不需要一块连续的存储区域            2) 删除和插入某个元素效率高 缺点：随机访问元素效率低

 

9.1.2 有关结构体的自身引用

问题1：请问结构体可以嵌套本类型的结构体变量吗？

问题2：请问结构体可以嵌套本类型的结构体指针变量吗？

typedef struct _STUDENT
{
	char name[64];
	int age;
}Student;

typedef struct _TEACHER
{
	char name[64];
	Student stu;                //结构体可以嵌套其他结构体
	//Teacher stu;
	//struct _TEACHER teacher;  //此时Teacher类型的成员还没有确定，编译器无法分配内存
	struct _TEACHER* teacher;   //不论什么类型的指针，都只占4个字节，编译器可确定内存分配
}Teacher;

结构体可以嵌套另外一个结构体的任何类型变量; 结构体嵌套本结构体普通变量（不可以）。本结构体的类型大小无法确定，类型本质：固定大小内存块别名; 结构体嵌套本结构体指针变量（可以）, 指针变量的空间能确定，32位， 4字节， 64位， 8字节;

9.1.3 链表节点

大家思考一下，我们说链表是由一系列的节点组成，那么如何表示一个包含了数据域和指针域的节点呢？

链表的节点类型实际上是结构体变量，此结构体包含数据域和指针域：

1. 数据域用来存储数据；
2. 指针域用于建立与下一个结点的联系，当此节点为尾节点时，指针域的值为NULL；

typedef struct Node 
{
	//数据域
	int id;
	char name[50];

	//指针域
	struct Node *next;       
}Node;

 

9.1.4 链表的分类

链表分为：静态链表和动态链表

静态链表和动态链表是线性表链式存储结构的两种不同的表示方式：

1. 所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为静态链表。
2. 所谓动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。

9.1.4.1 静态链表

typedef struct Stu
{
	int id;	                 //数据域
	char name[100];
	struct Stu *next;        //指针域
}Stu;

void test()
{
	//初始化三个结构体变量
	Stu s1 = { 1, "yuri", NULL };
	Stu s2 = { 2, "lily", NULL };
	Stu s3 = { 3, "lilei", NULL };

	s1.next = &s2;         
	s2.next = &s3;
	s3.next = NULL;          //尾结点

	Stu *p = &s1;
	while (p != NULL)
	{
		printf("id = %d, name = %s\n", p->id, p->name);
		//结点往后移动一位
		p = p->next; 
	}
}

输出结果

id = 1, name = yuri
id = 2, name = lily
id = 3, name = lilei

9.1.4.2 动态链表

typedef struct Stu
{
	int id;	           //数据域
	char name[100];
	struct Stu *next;  //指针域
}Stu;

void test()
{
	//动态分配3个节点
	Stu *s1 = (Stu *)malloc(sizeof(Stu));
	s1->id = 1;
	strcpy(s1->name, "yuri");

	Stu *s2 = (Stu *)malloc(sizeof(Stu));
	s2->id = 2;
	strcpy(s2->name, "lily");

	Stu *s3 = (Stu *)malloc(sizeof(Stu));
	s3->id = 3;
	strcpy(s3->name, "lilei");
	//建立节点的关系
	s1->next = s2; 
	s2->next = s3;
	s3->next = NULL;    //尾结点
	//遍历节点
	Stu *p = s1;
	while (p != NULL)
	{
		printf("id = %d, name = %s\n", p->id, p->name);
		//结点往后移动一位
		p = p->next; 
	}
	//释放节点空间
	p = s1;
	Stu *tmp = NULL;
	while (p != NULL)
	{
		tmp = p;
		p = p->next;
		free(tmp);
		tmp = NULL;
	}
}

输出结果

id = 1, name = yuri
id = 2, name = lily
id = 3, name = lilei

9.1.4.3 带头和不带头链表

1.带头链表：固定一个节点作为头结点(数据域不保存有效数据)，起一个标志位的作用，以后不管链表节点如果改变，此头结点固定不变。

 

2.不带头链表：头结点不固定，根据实际需要变换头结点(如在原来头结点前插入新节点，然后，新节点重新作为链表的头结点)。

 

9.1.4.4 单向链表、双向链表、循环链表

单向链表：

 双向链表：

 

循环链表：

 

9.2 链表基本操作

9.2.1 创建链表

typedef struct _LINKNODE
{
	int data;
	struct _LINKNODE* next;
}link_node;

link_node* init_linklist()
{
	link_node* head = NULL;                            //创建头结点指针
	head = (link_node*)malloc(sizeof(link_node));      //给头结点分配内存
	if (head == NULL)
    {
		return NULL;
	}
	head->data = -1;
	head->next = NULL;
	link_node* p_current = head;                       //保存当前节点
	int data = -1;
	while (1)                                          //循环向链表中插入节点
    {
		printf("please input data:\n");
		scanf("%d",&data);
		if (data == -1)                                //如果输入-1，则退出循环
        {
			break;
		}
		//给新节点分配内存
		link_node* newnode = (link_node*)malloc(sizeof(link_node));
		if (newnode == NULL)
        {
			break;
		}
		newnode->data = data;                          //给节点赋值
		newnode->next = NULL;

		p_current->next = newnode;                     //更新辅助指针p_current
		p_current = newnode;
	}
	return head;
}

9.2.2 遍历链表

//遍历链表
void foreach_linklist(link_node* head)
{
	if (head == NULL)
    {
		return;
	}

	//赋值指针变量
	link_node* p_current = head->next;
	while (p_current != NULL)
    {
		printf("%d ",p_current->data);
		p_current = p_current->next;
	}
	printf("\n");
}

9.2.3 插入节点

//在值val前插入节点
void insert_linklist(link_node* head, int val, int data)
{
	if (head == NULL)
    {
		return;
	}
	//两个辅助指针
	link_node* p_prev = head;
	link_node* p_current = p_prev->next;
	while (p_current != NULL)
    {
		if (p_current->data == val)
        {
			break;
		}
		p_prev = p_current;
		p_current = p_prev->next;
	}

	//如果p_current为NULL，说明不存在值为val的节点
	if (p_current == NULL)
    {
		printf("不存在值为%d的节点!\n",val);
		return;
	}

	//创建新的节点
	link_node* newnode = (link_node*)malloc(sizeof(link_node));
	newnode->data = data;
	newnode->next = NULL;

	//新节点入链表
	newnode->next = p_current;
	p_prev->next = newnode;
}

9.2.4 删除节点

//删除值为val的节点
void remove_linklist(link_node* head,int val)
{
	if (head == NULL)
    {
		return;
	}

	//辅助指针
	link_node* p_prev = head;
	link_node* p_current = p_prev->next;

	//查找值为val的节点
	while (p_current != NULL)
    {
		if (p_current->data == val)
        {
			break;
		}
		p_prev = p_current;
		p_current = p_prev->next;
	}
	//如果p_current为NULL，表示没有找到
	if (p_current == NULL)
    {
		return;
	}	
	//删除当前节点
	p_prev->next = p_current->next;
	//释放待删除节点的内存
	free(p_current);
}

9.2.5 销毁链表

//销毁链表
void destroy_linklist(link_node* head)
{
	if (head == NULL)
    {
		return;
	}
	//赋值指针
	link_node* p_current = head;
	while (p_current != NULL)
    {
		//缓存当前节点下一个节点
		link_node* tmp= p_current->next;
		free(p_current);
		p_current = tmp;
	}
}