C语言数据结构 单链表的建立、遍历、查找、插入和删除操作_单链表的创建及遍历

参考文献

本博文为半摘记性质
——
声明：全文主干部分摘自
[1] 杨智明. 数据结构（C语言版）[M]. 第一版. 北京:北京理工大学出版社, 2016.
[2] 严蔚敏, 李冬梅, 吴伟民. 数据结构(C语言版)[M]. 第2版. 北京:人民邮电出版社, 2015.

部分资料转自互联网各类技术博客，内容有一定改动，并非全文转载。本人尊重各位的知识成果，大幅引用的文章原文网址已在各小节末尾给出。
——
C语言在线运行工具：https://tool.lu/coderunner/

1链表简介

由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。链表即线性表的链式表示和实现。

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

链表由一系列结点（node，链表中每一个元素称为结点）组成，每一次为一个结构体 动态分配的内存空间，可称之为一个结点，每个结点之间可以是不连续的，但结点内是连续的。结点个数是不受限定的，可以随时删改，这是与数组相比的优点。

结点由指针域和数据域构成。存储数据元素信息的成员项称为数据域；存放下一结点的首地址的成员项被称为指针域，存储信息称为指针。第n个结点的指针域内存入第n+1个结点的首地址，如此串联下去直到最后一个结点，即尾结点，没有直接后继，其指针域为NULL，被称为空指针，表示该链表结束。

如果链表的每一个结点只有一个指针，则称为单链表（单向链表）。单链表分为两种：不带头结点的链表和带头结点的链表。
所有的链表都有一个头指针 head，头指针具有标识一个单链表的作用，整个单链表的存取必须从头指针开始进行，头指针指示链表的第一个结点，即首元结点。
在首元结点之前附加一个结点，称作头结点，可以不存储数据，也可存储附加信息。无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。不带头结点时，这时链表直接在首元结点存入数据，那么当从头插入数据时，head需要时刻变化。因此带头结点的链表性能更优良。

图中每个节点，a_n表示数据，^表示NULL。

深刻理解：带头结点和不带头结点的区别 使用头结点的优势

2链表的使用

对链表的使用涉及到内存的动态分配。
下面介绍如何新建一个动态单链表以及对该链表的主要操作。

2.1线性表的链式储存结构的类型定义

单链表在C语言中可用结构指针来描述。

#define int ElemType;	//数据域data用通用类型标识符ElemType表示
typedef struct LNode{
   ElemType data;  //数据域，存放元素值
   struct LNode *next;//指针域，指向后继结点
}LNode,LinkList;
Linklist L;//头指针L
LNode *p;//工作指针P
1
2
3
4
5
6
7

工作指针是指向单链表中任意结点的指针变量。

2.2单链表的建立

在单向链表中插入结点，先要确定插入的位置。当待插结点插在工作指针p所指的结点之前称为前插（头插法）；当待插结点插在工作指针p所指的结点之后称为后插（尾插法）。

这里展示用尾插入法建立带头结点的单链表（正序建立），为了使新结点能够插入到表尾，除了头指针L、指向新建结点的指针P，还需增加一个始终指向尾结点的尾指针s。

1. 建立头结点，并将头指针（L）指向头结点，头结点的指针域写NULL；
2. 利用一个工作指针（p)，从头到尾依次指向链表中的每个结点。生成一个新结点，用p指向该结点，并向数据域写数据，指针域写NULL；
3. 将上一步生成的新结点插入表尾，新结点的地址赋给前一个地址的指针域；
4. 将第二个生成的新结点插入在第一个结点后，重复第二到第四步，使新结点总是插在当前链表的表尾，便可建立一个含有n个结点的单链表。

尾插法算法实现

int CreateListTail(Linklist &L,int n){
    LNode *s,*p;
    L=(Linklist *)malloc(sizeof(LNode));//创建头结点
    L->next = NULL; //将头结点next域置空
    s=L;//s,l同时指向头结点，开始时头结点和尾结点是同一个

    for(int i=0;i<n;i++){
      p=(LNode *)malloc(sizeof(LNode));//创建数据结点,函数malloc分配了一个LNode类型的结点空间，并将其首地址存入指针变量p中
	  scanf("%d",&p->data);
      s->next=p;//新结点插入到当前链表的表尾
      s=p;//使s指向尾结点
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头插法和尾插法建立单链表

2.3单链表的遍历

利用一个工作指针p，从头到尾依次指向链表中的每个结点，当指针指向某个结点时，就输出该结点数据域中的内容，直到指针为空。如果是空链表，就只输出有关信息并返回调用函数。

遍历算法实现

int DisplayList( LinkList L )
//遍历带头结点的单链表
{
LNode *p =L->next ;//工作指针p初始化
while ( p!=NULL )
 { printf("%d",&p->data);
 p=p->next;
 }
}
1
2
3
4
5
6
7
8
9

2.4单链表的查找

不同于顺序表，链表不是随机存储结构，只能从链表首元结点出发，顺着指针域逐个结点向下查找。
有以下几种查找项：

1. 按序号查找
2. 按值查找
3. 相等的结点个数
4. 最大值/最小值

下面介绍按值查找的算法思路：
从首元结点出发，逐个将结点的值与给定值做比较，若有结点值相等，则返回首次找到的值相等的结点的储存位置；若到尾结点都没有找到，返回0。

按值查找算法实现

int getelem2(Linklist L, ElemType e)
{
	int i=0;
	Lnode *p = L->next;
	while (p!=NULL&&p->data!=e)
	{
		p = p->next;
		i++;
	}
	if(p!=NULL)return(i);
	else return p,i;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.5单链表的插入

在链表中第i个位置之前插入数据元素e，即插入到结点a_i-i和a_i之间。

1. 查找第i-1个结点的地址，并使工作指针p指向第i-1个结点的地址;
2. 生成一个数据域为e的新结点*s；
3. 使新结点s的指针域指向结点a_i；
4. 使结点*p的指针域指向新结点s；
   
   插入算法实现

int ListInsert(LinkList &L,int i ,ElemType e)
{
LNode *p,*s; 
p = L;
int j = 0;
while (p && j<i-1) //寻找第i-1个结点
    {
    p = p->next;
    ++j;
    }
if (!p || j >i)
    return ERROR;  //第i个元素不存在

s = (LNode)malloc(sizeof(Node)); //生成新的结点
s->data = e;
s->next = p->next;  //将p的后继结点赋值给s的后继
p->next = s;  //将s赋值给p的后继
return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果表中有n个结点，则插入操作中合法的插入位置有n+1个，即1≤i≤n+1。当i=n+1时，新结点则插在链表尾部。

2.6单链表的删除

删除单链表上第i个结点a_i。

为了删除单向链表中的某个结点，首先要找到待删除结点的前趋结点，然后将此前趋结点的指针域去指向待删除结点的后继结点（p->next=q->next)，最后释放被删除结点所占的存储空间。

1. 查找第i-1个结点的地址，并使工作指针p指向第i-1个结点的地址;
2. 将q指向被删除的第i个结点；
3. 使p的指针域指向被删除结点的直接后继；
4. 释放被删除的结点的空间；
   
   删除算法实现

int ListDelete(LinkList &L,int i ,ElemType &e)
{
int j=0;
LNode *p,*q;
p = L;

while(p->next && j <i-1)//寻找第i-1个结点，当1<=i<=n时是合法的。
    {               //当i=n+1时，虽然被删结点不存在，但其前驱结点存在，是尾结点
    p = p->next;   
    ++j;
    }
if(!(p->next) || j>i-1)//前者表明p指针已指向最后结点；后者表明要删除头结点
    return ERROR;
q = p->next;//用q指向将要删除的结点
p->next = q->next;//删除q指针指向的结点
e = q->data;
free(q);//释放删除结点的存储空间
return OK;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除算法中的循环条件(p->next&&j<i-1)和插入算法中的循环条件(p&&(j<i−1))是有所区别的。
因为插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n个，如果使用与插入操作相同的循环条件，则会出现引用空指针的情况，使删除操作失败。

更新日志

2020-4-26 首次发布
2022-8-1 正常维护