C语言进阶（八）—— 链表

1. 链表基本概念

1.1 什么是链表

• 链表是一种常用的数据结构，它通过指针将一些列数据结点，连接成一个数据链。相对于数组，链表具有更好的动态性（非顺序存储）。

• 数据域用来存储数据，指针域用于建立与下一个结点的联系。

• 建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。

• 链表的开销，主要是访问顺序性和组织链的空间损失。

数组和链表的区别：

数组：一次性分配一块连续的存储区域。

优点：随机访问元素效率高

缺点：1) 需要分配一块连续的存储区域（很大区域，有可能分配失败）

2) 删除和插入某个元素效率低

链表：无需一次性分配一块连续的存储区域，只需分配n块节点存储区域，通过指针建立关系。

优点：1) 不需要一块连续的存储区域

2) 删除和插入某个元素效率高

缺点：随机访问元素效率低

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字节;

1.3 链表节点

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

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

• 数据域用来存储数据；

• 指针域用于建立与下一个结点的联系，当此节点为尾节点时，指针域的值为NULL；

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

1.4 链表的分类

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

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

• 所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。

• 所谓动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。

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; //s1的next指针指向s2s2.next = &s3;s3.next = NULL; //尾结点Stu *p = &s1;while (p != NULL){printf("id = %d, name = %s\n", p->id, p->name);//结点往后移动一位p = p->next; }
}

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; //s1的next指针指向s2s2->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;}
}

1.4.3 带头和不带头链表

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

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

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

单向链表：

双向链表：

循环链表：

2. 链表基本操作

2.1 创建链表

使用结构体定义节点类型：

typedef struct _LINKNODE
{int id; //数据域struct _LINKNODE* next; //指针域
}link_node;

编写函数：link_node* init_linklist()

建立带有头结点的单向链表，循环创建结点，结点数据域中的数值从键盘输入，以 -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);//如果输入-1，则退出循环if (data == -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_currentp_current = newnode;}return head;
}

2.2 遍历链表

编写函数：void foreach_linklist(link_node* head)

顺序输出单向链表各项结点数据域中的内容：

//遍历链表
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");
}

2.3 插入节点

编写函数: void insert_linklist(link_node* head,int val,int data)

在指定值后面插入数据data,如果值val不存在，则在尾部插入：li

//在值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;
}

2.4 删除节点

编写函数: void remove_linklist(link_node* head,int val)

删除第一个值为val的结点：

//删除值为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_current)的前驱后继节点关系p_prev->next = p_current->next;//释放待删除节点的内存free(p_current);
}

2.5 销毁链表

编写函数: void destroy_linklist(link_node* head)

销毁链表，释放所有节点的空间：

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

2.6 反转链表

编写函数: void reverse_linklist(link_node* head)

反转链表通过3个辅助指针变量实现链表的翻转:

void reverse_linklist(link_node* head){if (head == NULL){return;}//辅助指针link_node* p_prev = NULL;link_node* p_current = head->next;link_node* p_next = NULL;while (p_current != NULL){p_next = p_current->next;//更改指针指向p_current->next = p_prev;//移动辅助指针p_prev = p_current;p_current = p_next;}//更新头结点head->next = p_prev;
}

2.7 统计链表长度

编写函数: int size_linklist(link_node* head)

int size_linklist(link_node* head){if (head == NULL){return -1;}//临时指针变量执行第一个真实数据的结点link_node* p_current = head->next;//记录结点个数int num = 0;while (p_current != null) {num++;p_current = p_current->next;}return num;
}