本文共 5231 字，大约阅读时间需要 17 分钟。

链表基本概念

什么是链表

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

数组和链表的区别：

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

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

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

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

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

优点：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字节;

链表节点

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

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

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

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

链表的分类

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

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

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

静态链表

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指针指向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; 	}}

动态链表

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指针指向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;	}}

带头和不带头链表

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

  

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

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

单向链表：

双向链表：

循环链表：

链表基本操作

创建链表

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

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_current		p_current = newnode;	}	return head;}

遍历链表

编写函数：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");}

插入节点

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

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

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

删除节点

编写函数: 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);}

销毁链表

编写函数: 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;	}}

转载地址：http://izxmi.baihongyu.com/