链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

线性表的顺序存储结构缺点是每一次插入和删除元素，大量元素的移动会导致时间效率低下。为了改进顺序存储结构的缺点，引入链式存储结构，即为链表。

链式存储结构的特点是用一组任意的存储单元来存储线性表中的数据元素。这样在插入和删除元素时，可以通过直接修改指针完成操作，时间效率大大提高。但因为链式存储结构的存储单元不连续，所以需要通过指针来访问它的后续元素。

为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，我们需要存出一个其直接后继的存储位置。我们把存储数据元素信息的域成为数据域，把存储后继位置的域称为指针域，这两部分构成一个节点。

n个节点链接成一个链表，即为线性表的链式存储结构。因为每个节点只有一个指针域，所以又将这样的链表称为单链表。

下面介绍单链表的几种基本操作：

单链表的基本操作

链表的创建

链表的一个节点由指针域和数据域构成。

链表的整体思想其实并不难懂，但一旦让他和指针结合在一起时，就容易让人摸不得头脑。

可以这样理解：在链表的创建中，添加一个指向下一个节点的指针，这个指针保存的是下一个节点的地址，我们说这个指针指向下一个节点。

那么指针的类型是什么呢？当然是Node了，因为指针不仅仅指向数据域，同时也指向指针域。

下面引入一段话来帮助理解：

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

代码实现：

struct Node{ 
   
    ElemType data;
    struct Node *next;
};

链表的初始化

参数的传入：涉及改变链表的操作统统用指针传链表，不然函数调用完成之后，为传入的链表分配的的内存会自动释放，链表不会有任何改变。
创建头结点，为头结点分配内存。
令头节点的指针为空指针(指针不初始化容易出现很多问题)

PS：这里为什么要动态分配内存呢？

因为这就是数组和链表的区别呀：线性表的顺序存储结构用数组实现，而数组占用的是一整块内存，数组元素分布很集中，需要提前预定数组的长度。

而链表是一种动态结构，它所占用的大小和位置是不需要提前分配的，可以根据自身的需求即时生成。

代码实现：

void InitList(LinkList *L){ 
   
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
}

判断链表是否为空

如果链表头结点指针域不为空，证明链表不为空。反之链表为空。（因为头结点指针域存储的就是链表的第一个元素的地址）

bool EmptyList(LinkList L){ 
   
	if(L->next)
		return false;
	else
		return true;
}

返回链表元素个数

因为链表中没有定义表长，所以要用到“工作指针后移”的思想，就是从第一个节点指针开始依次后移，直到节点为空为止，这时循环执行的的次数就是表长。

声明一个节点指针 p 指向链表的第一个节点。
当 p 不为空时，使指针 p 不断后移。
用 i 计数，循环结束后返回。

代码实现：

int LengthList(LinkList L){ 
   
	int i = 0;
	LinkList p = L->next;
	//L是头结点，L->next 代表链表的第一个节点。
	//LinkList其实是 Node * ，所以p指向链表的链表的第一个节点。
	while(p){ 
   
		i++;
		p = p->next;
	}
	//指针一直后移，直到节点不存在为止。
	return i;
}

清空链表

这里仍然用到了“工作指针后移”的思想，从第一个节点开始，每一个节点依次释放内存，直到最后一个节点停止。

声明节点q，p。
将第一个节点赋值给p。
将下一个节点赋值给q，释放q，将q赋值给q。
往复循环，直到全部节点的内存释放完成。

代码实现：

void ClearList(LinkList *L){ 
   
	LinkList p,q;
	p = (*L)->next;
	while(p){ 
   
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
}

思考：while循环里的值能不能为：

free(p);
p = p->next;

答：肯定会出错。

因为这里的free释放的是 p 整个节点，指针域也会消失。指针域消失后运行第二行代码时会报错。

返回给定位置的元素值

节点指针从第一个节点开始后移，直到指针移动到到指定位置时，若节点不为空，直接返回其值。

创建一个节点指针p指向链表的第一个节点，初始化cnt从1开始
（为什么从1开始，因为位置最小是1）
当 cnt < i 时，遍历链表，使p的指针不断后移
当 cnt = i 时，返回该节点数据域的值。
如果链表末尾p为空，则说明第i个元素不存在

代码实现：

Status(LinkList L,int i,Elemtype *e){ 
   
	int cnt = 1;
	LinkList p = L->next;
	while(p && cnt < i){ 
   
		p = p->next;
		cnt++; 
	}
	if(!p)
		return ERROR;
	*e = p->data;
	return OK;
}

查找数据

结合“工作指针后移”的思想，以下的代码应该不难理解。

声明一个节点 p 指向链表的第一个节点，初始化 i 从0开始。
依次对每一个 p 节点的指针域与 e 进行对比，相等则返回对应值，不相等则返回0。
当 p 不为空时，使 p 指针不断后移。

代码实现：

int LocateList(LinkList L,Elemtype *e){ 
   
	int i = 0;
	LinkList p = L->next;
	
	while(p){ 
   
		i++;
		if(p->data == e)
			return i;
			
		p = p->next;	
	}
	return 0;
}

删除元素

节点指针依次后移，到指定位置后，如果节点不为空，返回其数据域。释放该节点前，要将前一个节点的指针指向该删除节点的后继元素。

声明一节点 p 指向链表的头结点，初始化 cnt 为 1。
当 cnt 小于 i 时，遍历链表，然p的指针不断后移，不断指向下一个节点，cnt 逐次加1。
如果链表末尾 p 不存在，说明要查找的元素不存在。
将要删除的节点赋值给 q。
将 q 的后继赋值给 p 的后继。
返回 q 的数据域给 e。
系统回收 q 节点，释放q的内存。

代码实现：

Status ListDelete(LinkList *L,int i,ElemType *e){ 
   
	int cnt = 1;
	LinkList q,p;
	p = (*L);
	//此时 p 为头节点，p->next为第一个节点，对应cnt的值为1。
	while( p->next && cnt < i){ 
   
		p = p->next;
		cnt++;
	}
	//第一个节点不为空，并且 cnt 小于要删除的节点位置，开始循环 
	if(!(p->next))
		return ERROR;
	//与上方呼应，p->next是要删除的元素，也就是下文的q。
	q = p->next;
	p->next = q->next;  //将p节点的指针指向q的下一个节点
	*e = q->data;  //保留要删除节点的数据域
	free(q);
	return OK;
}

插入元素

插入操作的思路和删除有点类似，大体步骤为找到要插入的位置，创建新节点，使前一个节点的指针指向新节点，使新节点的指针指向原节点后面的节点。

声明一节点 p 指向链表的头结点，初始化 cnt 为 1。
当 cnt 小于 i 时，遍历链表，然p的指针不断后移，不断指向下一个节点，cnt 逐次加1。
如果链表末尾 p 不存在，说明插入位置有误。
查找成功就创建新节点 s ，并为 s 节点分配内存。
将要插入的元素的值 e 赋值给s->data。
将 p 节点的指针域赋值给 s 节点的指针域（使两者的后继元素相同）。
使 p 节点的指针指向 s 。

代码实现：

Status ListInsert(LinkList *L,int i,ElemType e){ 
   
	LinkList p,s;
	p = (*L);
	int cnt = 1;
	while(p && cnt < i){ 
   
		cnt++;
		p = p->next;
	}
	if(!p)
		return ERROR;
	s = (LinkList)malloc(sizeof(Node));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

随机数：

在讲下面的两个操作之前，先说明一下如何产生随机数：

随机数的产生与两个函数相关：srand函数和rand函数，两者配合使用可以产生伪随机数序列。头文件为：<stdlib. h>。

rand函数：

rand函数在产生随机数前，需要系统提供的生成伪随机数序列的种子，rand根据这个种子的值产生一系列随机数。如果系统提供的种子没有变化，每次调用rand函数生成的伪随机数序列都是一样的。

srand函数：

srand()通过参数seed改变系统提供的种子值，从而可以使得每次调用rand函数生成的伪随机数序列不同，从而实现真正意义上的“随机”。

生成随机数序列的方法：

通常可以利用系统时间来改变系统的种子值，即srand(time(NULL))，可以为rand函数提供不同的种子值，进而产生不同的随机数序列。

示例：

#include<stdlib.h>//头文件包含rand和srand函数
#include<stdio.h>
#include<time.h>
 
int main(){ 
   
	srand(time(0));//选取种子文件
	int k;
	
	for(int i = 0; i < 20; i++){ 
   
 	 	k = rand() % 101;  //输出0-100之间的随机数
 	 	printf("k = %d\n",k);
}
	return 0;
}

建立有头结点的单链表（头插法）

声明一指针节点 p
初始化随机数种子
建立一个带头结点的链表
在循环里执行如下操作：生成新节点 p，为新节点 p 的数据域随机赋值，将 p 插入到表头，执行 n 次

代码实现：

void CreateListHead(LinkList *L,int n){ 
   
	LinkList p;
	srand(time(0));
	//初始化随机数种子
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
	//初始化链表
	for(int i = 0 ; i < n ; i++){ 
   
		p = (LinkList)malloc(sizeof(Node));  //建立新节点 p
		p->data = rand()%100 + 1;  //数据域赋值
		p->next = (*L)->next;
		//将p节点的指针指向头结点后面的节点
		(*L)->next = p;
		//将节点 p 插入到表头
	}
}

建立有头结点的单链表（尾插法）

尾插法和头插法大体类似，不过尾插法需要另外一个指向尾部的结点 r ，在链表中插入元素时，只需要将 r 的指针指向 p 即可，然后将 p 赋值给 r ，这样可以使 r 始终在链表尾部，并且将要插入的元素置于 r 的后方，也就是链表的尾部。插入结束后，将链表尾部的元素的指针指向NULL。

声明两节点指针 p，r
初始化随机数种子
初始化 r 的值和空链表
在循环里执行如下操作：生成新节点 p，为新节点 p 的数据域随机赋值，将 r 的指针指向 p，将 p 赋值给 r ，执行 n 次。

代码实现：

void CreateListTail(LinkList *L,int n){ 
   
	LinkList p,r;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r = *L;
	for(int i = 0 ; i < n ; i++){ 
   
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100 + 1;
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

个人的一点感受：

首先就是链表的确很难，在学链表之前，最好先把指针搞懂，明白指针到底是一个什么东西，再来看链表中的指针。这一节的指针太多，很容易把自己搞懵，其实还是需要一点时间来理解。

还有就是最好用笔在纸上写写画画，大致理解有关链表的一些基本操作。然后上机手撕代码，要想真正的把链表吃透，还是需要多敲，多悟，多练（刷题）。

个人虽然可以基本上实现这些基本操作，但有些地方还是似懂非懂，有什么操作和表述上不妥的地方，还望大家指出。

下面给出完整代码的实现（加入测试）：

#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#define MAXSIZE 20

#define ERROR 0
#define OK 1

typedef int Status;
typedef int ElemType;

struct Node{ 
   
	ElemType data;
	struct Node * next;
};

typedef struct Node *LinkList;

void InitList(LinkList *L){ 
   
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
} 

bool ListEmpty(LinkList L){ 
   
	if(L->next)
		return false;
	else
		return true;
}

void ClearList(LinkList *L){ 
   
	LinkList p,q;
	p = (*L)->next;
	while(p){ 
   
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
}

int ListLength(LinkList L){ 
   
	int i = 0;
	LinkList p = L->next;
	while(p){ 
   
		i++;
		p = p->next;
	}
	return i;
}

Status GetElem(LinkList L,int i,ElemType *e){ 
   
	int cnt = 1;
	LinkList p = L->next;
	while(p && cnt < i){ 
   
		p = p->next;
		cnt++;
	}
	if(!p)
		return ERROR;
	*e = p->data;
	return OK;
}

int LocateElem(LinkList L,ElemType e){ 
   
	int cnt = 0;
	LinkList p = L->next;
	
	while(p){ 
   
		cnt++;
		if(p->data == e)
			return cnt;
		p = p->next;
	}  
	
	return 0;
}

Status ListInsert(LinkList *L,int i,ElemType e){ 
   
	LinkList p,s;
	p = (*L);
	int cnt = 1;
	while(p && cnt < i){ 
   
		cnt++;
		p = p->next;
	}
	if(!p)
		return ERROR;
	s = (LinkList)malloc(sizeof(Node));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

Status ListDelete(LinkList *L,int i,ElemType *e){ 
   
	int cnt = 1;
	LinkList q,p;
	p = (*L);
	//此时 p 为头节点，p->next为第一个节点
	while( p->next && cnt < i){ 
   
		p = p->next;
		cnt++;
	}
	//第一个节点不为空，并且 cnt 小于要删除的节点位置，开始循环 
	if(!(p->next))
		return ERROR;
	q = p->next;
	p->next = q->next;
	*e = q->data; 
	free(q);
	return OK;
}

Status ListTraverse(LinkList L){ 
   
	LinkList p = L->next;
	while(p){ 
   
	 	printf("%d ",p->data);
	 	p = p->next;
	} 
	printf("\n");
	return OK;
}

void CreateListHead(LinkList *L,int n){ 
   
	LinkList p;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
	
	for(int i = 0 ; i < n ; i++){ 
   
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100 + 1;
		p->next = (*L)->next;
		(*L)->next = p;
	}
}

void CreateListTail(LinkList *L,int n){ 
   
	LinkList p,r;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r = *L;
	for(int i = 0 ; i < n ; i++){ 
   
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100 + 1;
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

int main(){ 
   
    ElemType e;
    Status r;
    LinkList L;
    InitList(&L);
    printf("初始化L后：ListLength(L) = %d \n",ListLength(L));
    for(int i = 1;i <= 5;i++){ 
   
    	r = ListInsert(&L,1,i);
	}
	printf("在表头依次插入1-5后：L.data = ");
	ListTraverse(L);
	
	printf("ListLength(L) = %d \n",ListLength(L));
	r = ListEmpty(L);
	printf("L是否为空：r = %d (1:是 0:否)\n",r);
	
	ClearList(&L);
	printf("清空L后，ListLength(L) = %d \n",ListLength(L));
	r = ListEmpty(L);
	printf("L是否为空：r = %d (1:是 0:否) \n",r);
	
	for(int i = 1; i <= 10 ; i++){ 
   
		ListInsert(&L,i,i);
	}
	printf("在L的表尾依次插入1-10后，L.data = ");
	ListTraverse(L);
	
	printf("ListLength(L) = %d\n",ListLength(L));
	
	ListInsert(&L,1,0);
	printf("在表头插入0后：L.data = ");
	ListTraverse(L);
	printf("ListLength(L) = %d\n",ListLength(L));
	
	GetElem(L,5,&e);
	printf("第5个元素的值为%d\n",e);
	
	for(int i = 3 ; i <= 4 ;i++){ 
   
		r = LocateElem(L,i);
		if(r)
			printf("第%d位元素的值为%d\n",r,i);
		else
			printf("不存在值为%d的元素\n",i);
	}
	
	int l = ListLength(L);
	for(int i = l + 1; i >= l ; i--){ 
   
		r = ListDelete(&L,i,&e);
		if(r == ERROR)
			printf("删除第%d个元素失败\n",i);
		else
			printf("删除第%d个元素值为: %d\n",i,e);
	}
	printf("依次输出L的元素: ");
	ListTraverse(L);
	
	r = 5;
	ListDelete(&L,r,&e);
	printf("删除的第%d个元素的值为：%d\n",r,e);
	
	printf("依次输出L的元素: ");
	ListTraverse(L);
	
	ClearList(&L);
	printf("\n清空L后,ListLength = %d\n",ListLength(L));
	CreateListHead(&L,20);
	printf("整体创建L的元素(头插法)： ");
	ListTraverse(L);
	
	ClearList(&L);
	printf("\n清空L后,ListLength = %d\n",ListLength(L));
	CreateListTail(&L,20);
	printf("整体创建的元素(尾插法)：");
	ListTraverse(L); 
	
    return 0;
}

第二次发博客，希望大家多多关注呀，哈哈！！

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

关于链表，看这一篇就够了！（新手入门）

单链表的基本操作

链表的创建

链表的初始化

判断链表是否为空

返回链表元素个数

清空链表

返回给定位置的元素值

查找数据

删除元素

插入元素

建立有头结点的单链表（头插法）

建立有头结点的单链表（尾插法）

发表回复

关于链表，看这一篇就够了！（新手入门）

单链表的基本操作

链表的创建

链表的初始化

判断链表是否为空

返回链表元素个数

清空链表

返回给定位置的元素值

查找数据

删除元素

插入元素

建立有头结点的单链表（头插法）

建立有头结点的单链表（尾插法）

相关推荐

发表回复