手把手教你写链表
程序员文章站
2023-12-22 23:35:58
...
本文只讲逻辑，源码参考本文之下的五篇博客（关注后可以往下找）
数据结构： 数据结构是计算机存储、组织数据的方式。
数据：(data) 是对客观事物的符号表示。在计算机科学是指所有能够输入到计算机中并能够被计算机处理的符号的总数。
数据元素： (data element) ： 是数据的基本单位，在计算机通常作为一个整体进行描述或处理。
数据项(data item)：数据项数据的不可分割的最小单位。一个数据元素可以由多个数据项组成。
数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。
数据结构： 不仅要保存数据，而且还保存数据与数据之间的关系。
结构： 数据元素之间关系的不同的特性，称之结构(structure)，根据数据元素之间的关系，通常会讲结构分为四种：
(1) 集合 ：结构中的数据元素之间关系，除了"同属于一个集合"之外就没有其他的任何关系。
(2) 线性结构：数据元素之间的关系是线性的。线性？ 一条直线
(3) 树形结构：数据元素之间关系是树状(层次)
(4) 网状结构(图)：图论(应用数学)
数据结构的形式定义：数据结构是一个二元组 DATA_Structure = (D, S)
D: 数据元素的有限集
S: 是D上关系(数据元素之间的关系)的有限集
结构定义中的“关系”描述数据元素之间的逻辑关系，又称之为数据的逻辑结构。
逻辑结构：数据在某种逻辑下面的关系
数据结构在计算机里面的表示称之为物理结构，也称为存储结构
存储结构：就是数据元素地址编号的关系。
1.线性表
例子：
26个英文字母(ABCDEF....) 单个字母字符A必须是在B的前面，B在C的前面
班级人数(20200 58, 20201 46, 20202 78 58 46 78....)
"线性表"中的数据元素可以是各式各样的类型。但是同一线性表中的数据元素之间必须是同一类型的，并且相邻的数据元素之间
存在着序偶关系(顺序)。将线性表标记为：
(a1,a2,a3,a4........an)
(1) 存在唯一一个被称为"第一个"的数据元素
(2) 存在唯一一个被称为"最后一个"的数据元素
(3) 除“第一个”元素外，集合中的每一个数据元素有且仅有
一个前驱数据元素
(4) 除“最后一个”元素外，集合中的每一个数据元素有且仅有
一个后继数据元素
(1,3,5,7,2,4)
上面的这串数据呈线性关系，那么我们需要解决问题？
(1) 数据保存
1 3 5 7 2 4
(2) 关系要保存
"逻辑关系"
int a[] = {1,3,5,7,2,4};
a[0] = 1
a[1] = 3
a[2] = 5
......
线性表的物理结构的实现：
(1) 顺序结构 -》 数组
线性表的顺序表示是指用一组连续的存储单元依次保存线性表中的数据元素。
在这种情况，数据保存啦， 并且数据与数据之间的逻辑关系也保存。(用物理地址的关系来表示逻辑关系)
(2) 链式结构 -》链表
保存每个数据元素时，不必用一组连续的地址空间，数据元素之间的存储单元不是连续的
但是保存每一个数据元素的同时，额外开辟了一个空间
这个空间用来保存它逻辑上面的上一个或下一个或上下两个
数据元素的地址 -》 链式结构
链式线性表 -》 链表
2. 单链表
(1 2 5 4 7 6 8) ( a b c d e f g)
typedef int Elemtype ; //数据元素的类型
typedef struct node
{
Elemtype data; //"数据域" 保存数据元素
//“指针域”：用来保存数据元素之间的关系
struct node * next; //保存下一个数据元素的地址
struct node * prev; //保存上一个数据元素的地址
}Node;
任意一个数据集合，都会去分析如下操作：
数组：
链表： 增、删、改、查
例子：
(1 2 5 4 7 )
Node * a = (Node *)malloc(sizeof(Node));
Node * b = (Node *)malloc(sizeof(Node));
Node * c = (Node *)malloc(sizeof(Node));
Node * d = (Node *)malloc(sizeof(Node));
Node * e = (Node *)malloc(sizeof(Node));
a->data = 1;
a->next = b;
b->data = 2;
b->next = c;
c->data = 5;
c->next = d;
d->data = 4;
d->next = e;
e->data = 7;
e->next = NULL;
练习：
写一个函数，用来访问链表的各个结点(将数据元素的值打印出来)
1.要求要根据用户的输入创建一个链表，返回链表的第一个结点的指针。
/*
Create_linkedlist: 创建一个链表
void：无参数
返回值：
第一个节点的指针 Node *
*/
Node * Create_linkedlist(void)
2.要求要根据用户的输入创建一个有序链表，返回链表的第一个结点的指针。
/*
Create_order_linkedlist: 创建一个有序链表
void：无参数
返回值：
第一个节点的指针 Node *
*/
Node * Create_order_linkedlist(void)
{
“插入排序的算法”
(1) 找到你要插入的位置
“遍历整个链表”：找到链表中第一个比你大的
if 找到啦
break
pk = h;
while(pk)
{
if(pk->data > p->data)
{
//哦豁，找到了
break;
}
pr = pk; //保证pr永远指向pk前面那一个结点的
pk = pk->next;
}
遍历完了，并没有找到第一个比待插入的数据还要大的
尾插法
如果找到：
第一个结点就比待插入的数据要大
头插法
else
中间插入
}
3. 删除链表中的一个结点 data == x
删除操作可以分为两步：
(1) 找到要删除的那一个结点
"遍历链表"
找到了 goto (2)
没找到 return
(2) 删除(干掉)
2.1 先摘下来(先把你要干掉的结点孤立)
2.2 free
/*
delete_x:删除链表中的一个结点
@h : 原链表第一个结点的指针
@x ：要删除的那个结点的数据域
返回值：
返回删除后的链表的第一个结点的指针
*/
Node * delete_x(Node * h, Elemtype x)
{
Node * px = h; //指向要删除的那个结点
Node * pr = NULL;// 指向要删除的那个结点的前面那一个结点
while(px)
{
if(px->data == x)
{
//找到啦
break;
}
pr = px;
px = px->next;
}
if 没有找到
{
return h;
}
//找到啦
if()//你要删除的使第一个结点
{
}
else //要么是中间的结点，要么是最后一个结点
{
}
return h;
}
4. 删除链表中的所有的 data == x 结点
删除操作可以分为两步：
while(1)
(1) 找到要删除的那一个结点
"遍历链表"
找到了 goto (2)
没找到 return
(2) 删除(干掉)
2.1 先摘下来(先把你要干掉的结点孤立)
2.2 free
/*
delete_all_x:删除链表中的一个结点
@h : 原链表第一个结点的指针
@x ：要删除的那个结点的数据域
返回值：
返回删除后的链表的第一个结点的指针
*/
Node * delete_all_x(Node * h, Elemtype x)
5. 已知px指向一个单链表的某一个系欸但(不是第一个结点，也不是最后一个结点)
要删除px, 该如何操作?
pn = px->next;
px->data = pn->data;
px->next = pn->next;
pn->next = NULL;
free(pn);
6. 找单链表中的最后一个结点，并返回其指针。
“遍历链表”
7. 计算一下一个单链表有多少个结点。
作业：
1.逆置一个单链表(不允许申请新的结点空间)
1 3 5
=》 5 3 1
算法一：(1) 先按顺序从原链表摘除一个结点p
p = h;
h = h->next;
p->next = NULL;
(2) 在把p按“头插法”加入到新的链表first中
if(first == NULL)
{
first = p;
}
else
{
p->next = first;
first = p;
}
goto (1) ，直到h == NULL , return first.
算法二：
就地逆置
Node * nizhi(Node * h)
{
if(h == NULL)
{
return NULL;
}
Node * pk = NULL;
Node * pr = NULL;
pk = h->next;
pr = h;
pr->next = NULL;
while(pk)
{
pr = pk;
pk = pk->next;
pr->next = h;
h = pr;
}
return h;
}
2.归并两个有序的链表，要求归并之后任然有序
算法一：
以hb为母链表，把ha的每一个结点摘下来
然后按照"插入排序"的算法，添加到hb指向的那一个链表。
while(ha)
{
if(ha == NULL)
{
return hb;
}
if(hb == NULL)
{
return ha;
}
p = ha;
ha = ha->next;
p->next = NULL;
//先找插入的位置
//插入操作
}
算法二： 谁小谁就往后面挪
Node * pc = NULL;// 指向合并之后的第一个结点
if(ha == NULL)
{
return hb;
}
if(hb == NULL)
{
return ha;
}
pc = ha->data < hb->data ? ha : hb;
while(ha && hb)
{
if(ha->data < hb->data)
{
//如果ha存在，ha < hb 将ha往后面挪，pr在ha的前面
while(ha && ha->data < hb->data)
{
pr = ha;
ha = ha->next;
}
pr->next = hb;
}
else
{
//如果hb存在，hb < ha 将hb往后面挪，pr在hb的前面
while(hb && hb->data < ha->data)
{
pr = hb;
hb = hb->next;
}
pr->next = ha;
}
}
return pc;
3. 返回一个链表的倒数第k个结点的指针。
算法一：
开辟一个指针数组，保存每一个结点的地址
返回num-k+1
Node * a[1024];
int i = 0;
p = h;
while(p)
{
a[i++] = p;
p = p->next;
}
num = i;
算法二：
遍历算出有num个结点
return num-k+1
算法三：
派两个哨兵pr,pk
先让pk 走k步
然后再两个同时走，每一个同时往后挪一个结点
直到pk == NULL ,return pr;
4.返回一个链表中间结点的指针(只允许遍历一次)
算法一：
派两个哨兵pr,pk
pk 走每次两步， pr走每一一步
直到pk == NULL ,return pr;
算法二：
开辟一个指针数组，保存每一个结点的地址
a[i/2]
Node * a[1024];
int i = 0;
p = h;
while(p)
{
a[i++] = p;
p = p->next;
}
return a[i/2];
算法三：
int a = 1, b = 1;
Node * t = h;
Node * p =h;
if(h == NULL)
{
return h;
}
else
{
while(p)
{
if((double)a/b > 2.0)
{
t = t->next;
b++;
}
a++;
p = p->next;
}
return t;
}
5.反序输出单链表中每个结点的值。
算法一：
开辟一个指针数组，保存每一个结点的指针
遍历链表
反序数组数组里面每一个指针对应的data
Node * a[1024];
int i = 0;
while(h)
{
a[i++] = h;
h = h->next;
}
i = i--;
while(i >= 0)
{
printf("%d ", a[i]->data);
i--;
}
printf("\n");
算法二: 递归
f(h) : 表示逆序输出h指向的那一个链表
f(h) : (1)
逆序输出h后面的那一个链表
f(h->next)
(2)
输出h这个结点的值
printf("%d ", h->data);
void f(Node * h)
{
if(h == NULL)
{
return ;
}
f(h->next);
printf("%d ", h->data);
}
6.请您设计一个算法，判断一个单链表中是否有环？
pa = h; //每次走一步
pb = h; //每次走两步
while(pb)
{
//结束循环有两种可能
//pb == NULL 没有环
//pb == pa 有环
pa = pa->next;
pb = pb->next ? pb->next->next : NULL;
if(pb == NULL)
{
return 1; //表示没有环
}
if(pa == pb)
{
return 0;//表示有环
}
}
思路：
两个哨兵，一个走一步
一个走两步
有环两个定会相遇
如果走得快那一个已经为NULL,说明没有环
如何证明？
已知条件：
用两个哨兵 A ,B
A每次移动一个结点， B每次移动两个结点
要证明，在环内，A和B 终会相遇
假设有环，并且A，B进入环内了。环内n个结点，
A，B顺时针方向的第k个结点(k > 0, k = 0表示
A，B相遇，从B的下一个结点开始数)
结论： 做了k个操作之后，A,B相遇
数学归纳法 证明：
按顺时针方向，从B所在的位置给每一个结点编号
B所在的结点的编号为1， A所在的结点的编号为 (k + 1)
设 f(x , i) 表示x做了i个操作后所在的结点的编号。
得到:
f(B, 0) = 1 , f(A ,0) = k+1
原结论为：
f(B, k) = f(A, k)
用数组归纳法来证明 ： f(B, k) = f(A, k)
(1) 当k = 1 时
f(B,1) = 1 + 2
f(A,1) = K+1 + 1 = 3
f(B, 1) = f(A, 1)
(2) 当k = i 结论也成立
f(B, i) = 1 + 2i
f(A, i) = k + 1 + i = 2i + 1
当 k = i+1时，
f(B, i+1) = 1 + 2(i+1) = 2i + 3
f(A, i+1) = k+1 + i+1 = 2i + 3
f(A, i+1) = f(B, i+1)
即 f(B, k) = f(A , k)得证。。。。。
7.删除单链表(无序)中最小值结点(假设最小值的结点是唯一的)
pmin //永远指向最小的那一个结点的指针
遍历链表
p = h;
while(p)
{
if p->data < pmin->data
{
pk = pr;
pmin = p;
}
pr = p;
p = p->next;
}
//分情况删除 pmin
....
2. 带头结点的单链表
如果有了带头节点链表，那么我们就可以轻松解决很多问题。
头结点： 用来管理和唯一标识一个链表的。 linkedlistwithhead
Node * first ; //指向链表的第一个结点
Node * last ; // 指向链表的最后一个结点
int num; //记录链表中数据结点的个数
.....
typedef int Elemtype; //数据元素的类型
//数据结点
typedef struct node
{
//指针域
struct node * next; //指向下一个数据结点
//数据域
Elemtype data;
}Node;
//头结点
struct head_node
{
Node * first ; //指向链表的第一个结点
Node * last ; // 指向链表的最后一个结点
int num; //记录链表中数据结点的个数
};
(1) 给链表创建一个头结点 (头结点存在，那么链表也就存在)
/*
create_head: 给链表创建一个头结点
无参数
返回值：
返回创建好的头结点的指针 struct head_node *
*/
struct head_node * create_head(void)
{
}
(2) 往链表中添加结点，使链表任然有序
/*
add_Node:往一个有序的带头结点的单链表中添加一个数据结点
使添加后的单链表任然有序
@head： 原链表的头结点的指针
@p : 带加入数据结点的指针
*/
void add_Node(struct head_node * head, Node * p)
{
}
(3) 删除一个data为x的数据结点
/*
delete_x : 删除一个data为X的数据结点
@head : 原链表的头结点
x : 要删除的那个结点的数据域
返回值： 无返回值
*/
void delete_x(struct head_node * head, Elemtype x)
{
if(链表不存在 || head->first == NULL)
{
return;
}
Node * px = head->first; //指向您要删除的那一个数据结点
Node * pr = NULL; //指向 px的前面那一个数据结点的
//找到要删除的那一个结点 "遍历链表"
while(px)
{
if(px->data == x)
{
//找到啦
}
px就要往后挪
}
//分情况
if(没有找到)
{
return;
}
if(找到了)
{
//找到的要删除的那个结点是第一个
//找到的要删除的那个结点是中间结点
//找到的要删除的那个结点是最后一个结点
}
}
3. 不带头结点的双向链表 doulue linked list
typedef int Elemtype; //数据元素的类型
//数据结点
typedef struct node
{
//指针域
struct node * next; //指向下一个数据结点
struct node * prev; //指向上一个数据结点
//数据域
Elemtype data;
}Node;
create_order_linkedlist()//根据用户输入创建一个有序的双链表
add_Node()
delete_x()
delete_all_x()
4. 带头结点的双链表
5. 上面讲到了单链表，双链表，都有一个特点，如果你已经遍历到了最后一个结点，此时你想用第一个结点的指针，只能再次遍历。因为最后一
个结点的指针指向NULL， 可以不可以把最后一个结点的指针指向第一个结点，那么这样的话我们就可以不用二次遍历就可以轻松找到第一个
结点了。
循环链表：
单向循环链表
最后一个结点的指针域(next),指向第一个结点
双向循环链表 Double circular linkedlist
最后一个结点的指针域(next),指向第一个结点
第一个结点的指针域(prev),指向最后一个结点
//数据元素的类型
typedef int Elemtype;
//数据结点的类型
typedef struct DbiNode
{
//指针域
struct DbiNode * next ;
struct DbiNode * prev ;
//数据域
Elemtype data;
}DbiNode;
//头结点的类型
typedef struct D_head
{
DbiNode * first;
DbiNode * last;
int num;
}D_head;
完成常规操作：增，删，改，查
作业：
8. 逆序存储整数的各个位，并实现两个整数相加。
“也实现大数据相加的方法之一”
int 123
list1 :
3 2 1
int 456
list 2 :
6 5 4
list1 + list 2 == > list 3:
9 7 5
先将每一个位的数据提取，
尾插法加入到链表
Node * nixu(int num)
{
Node * first = NULL;
Node * last = NULL;
Node * p = NULL; //指向加入的那个结点
while(num)
{
p = malloc(sizeof(*p));
p->data = num % 10;
p->next = NULL;
num = num / 10;
if(first == NULL)
{
first = last = p;
}
else
{
last->next = p;
last = p;
}
}
return first;
}
int num1, num2;
scanf("%d%d", &num1, &num2);
Node * ha = nixu(num1);
Node * hb = nixu(num2);
Node * add_two_num(Node * ha, Node * hb)
{
Node * first = NULL;
Node * last = NULL;
Node * p = NULL;
int a, b;
int c = 0; //进位值
while(ha || hb)
{
a = ha ? ha->data : 0;
b = hb ? hb->data : 0;
p = malloc(sizeof(*p));
p->data = (a+b+c) % 10;
p->next = NULL;
c = (a+b+c)/10;
if(first == NULL)
{
first = last = p;
}
else
{
p->next = first;
first = p;
}
}
if(c)
{
p = malloc(sizeof(*p));
p->data = 1;
p->next = NULL;
p->next = first;
first = p;
}
return first;
}
9. 链表A,B，判断A是否为B的子序列(子序列： 连续的一部分)
A： 1 2 5
B: 9 8 1 1 1 5 6 1 2 5
遍历B，找到第一个与A相等的结点
然后再手牵手一起走
直到A走不动，
A就是B的一个子序列
XXX(Node * ha, Node * hb)
{
pa = ha;
pb = hb;
while(pb)
{
pa = ha;
if(pa->data == pb->data)
{
pn = pb->next;
while(pa && pb)
{
if(pa->data != pb->data)
{
break;
}
pa = pa->next;
pb = pb->next;
}
if(pa == NULL)
{
return 1; //是一个子序列
}
if(pb == NULL)
{
return 0; //不是一个子序列
}
pb = pn;
}
else
{
pb = pb->next;
}
}
}
10. 链表A中保存的是整数，有正有负，写一个程序，把链表A中
的负数放置到链表的前面。
算法：
遍历链表， 找到第一个为非负数 ps
(1)然后从ps遍历链表 找到一个结点为负数 pn
(2)摘下(pn)来，
(3)然后按照“头插法”加入到原链表中去
goto (1)
Node * XXX(Node * h)
{
Node * pn = NULL;
Node * pr = NULL; //指向pn的前面那个结点
Node * ps = h; //指向每一次搜索的起点位置
//遍历链表， 找到第一个为非负数 ps
while(ps)
{
if(ps->data >= 0)
{
break;
}
ps = ps->next;
}
if(ps == NULL)
{
return h;
}
//(1)然后从ps遍历链表 找到一个结点为负数 pn
pn = ps->next;
pr = ps;
while(1)
{
while(pn)
{
if(pn->data < 0)
{
break;
}
pr = pn ;
pn = pn->next;
}
if(pn == NULL) //表示链表后面没有负数了
{
return h;
}
//(2)摘下(pn)来，
pr->next = pn->next;
//pn->next = NULL;
pn->next = h;
h = pn;
pn = pr->next;
}
}
如果是一个双向链表，可以用如下算法
ha = first, hb = last
顺序遍历链表，找到第一个非负数 ha,
逆序遍历链表，找到第一个负数 hb
交换 ha->data , hb->data
如此重复上述操作，直到ha与hb相遇
11.设A，B为单链表，且A，B都是升序的。求：
(1) A,B的交集
a、A, B是否有重复的元素
算法：
遍历A链表，以A链表中的结点为基准
所搜B链表中的每一个结点
head * jiaoji(head * ha, head * hb)
{
head * hc = malloc(sizeof(*hc));
hc->first = NULL;
hc->last = NULL;
Node * pa = ha->first;
Node * pb = hb->first;
Node * pk = hb->first; // 链表B开始匹配的结点
while(pa)
{
pb = pk;
while(pb)
{
if(pa->data == pb->data)
{
break;
}
pb = pb->next;
}
pa = pa->next;
if(pb == NULL) //B链表中没有与当前pa相等的结点
{
continue;
}
pk = pb->next;
//排除重复的结点
if((hc->last == NULL) || (hc->last && hc->last-data != pb->data) )
{
Node * pc = malloc(ziseof(*pc));
pc->data = pb->data;
pc->next = NULL;
if(hc->first == NULL)
{
hc->first = pc;
hc->last = pc;
}
else
{
hc->last->next = pc;
hc->last = pc;
}
}
}
}
算法二：
同时遍历A，B，谁小谁往后走，
相同则取值，然后手牵手一起走。
(2) A,B的并集
先取A的每一个结点，不重复地添加到C
再取B每一个结点，不重复插入到C
12. 对一个链表进行排序。(选做题)
(1) 冒泡
(2) 选择
交换：
交换结点的位置
交换元素的数据