线性表,双向链表,静态链表,循环链表(约瑟夫环)(下)

简介: 线性表,双向链表,静态链表,循环链表(约瑟夫环)

线性表,双向链表,静态链表,循环链表(约瑟夫环)(上):https://developer.aliyun.com/article/1471358


静态链表及其创建(C语言实现)


顺序表和链表优缺点》一节,我们了解了两种存储结构各自的特点,那么,是否存在一种存储结构,可以融顺序表链表各自的优点,从而既能快速访问元素,又能快速增加或删除数据元素


静态链表,也是线性存储结构的一种,它兼顾了顺序表和链表的优点于一身,可以看做是顺序表和链表的升级版。


使用静态链表存储数据,数据全部存储在数组中(和顺序表一样),但存储位置是随机的,数据之间"一对一"的逻辑关系通过一个整形变量(称为"游标",和指针功能类似)维持(和链表类似)。


例如,使用静态链表存储 {1,2,3} 的过程如下:


创建一个足够大的数组,假设大小为 6,如图 1 所示:

image.png

图 1 空数组


接着,在将数据存放到数组中时,给各个数据元素配备一个整形变量,此变量用于指明各个元素的直接后继元素所在数组中的位置下标,如图 2 所示:

image.png

图 2 静态链表存储数据


通常,静态链表会将第一个数据元素放到数组下标为 1 的位置(a[1])中。

图 2 中,从 a[1] 存储的数据元素 1 开始,通过存储的游标变量 3,就可以在 a[3] 中找到元素 1 的直接后继元素 2;

通过元素 a[3] 存储的游标变量 5,可以在 a[5] 中找到元素 2 的直接后继元素 3,这样的循环过程直到某元素的游标变量为 0 截止(因为 a[0] 默认不存储数据元素)


类似图 2 这样,通过 "数组+游标" 的方式存储具有线性关系数据的存储结构就是静态链表。


静态链表中的节点


通过上面的学习我们知道,静态链表存储数据元素也需要自定义数据类型,至少需要包含以下 2 部分信息:

  • 数据域:用于存储数据元素的值;
  • 游标:其实就是数组下标,表示直接后继元素所在数组中的位置;


因此,静态链表中节点的构成用 C 语言实现为:

typedef struct {
int data;//数据域
int cur;//游标
}component;

备用链表


图 2 显示的静态链表还不够完整,静态链表中,除了数据本身通过游标组成的链表外,还需要有一条连接各个空闲位置的链表,称为备用链表。


备用链表的作用是回收数组中未使用或之前使用过(目前未使用)的存储空间,留待后期使用。也就是说,静态链表使用数组申请的物理空间中,存有两个链表,一条连接数据,另一条连接数组中未使用的空间。

通常,备用链表的表头位于数组下标为 0(a[0]) 的位置,而数据链表的表头位于数组下标为 1(a[1])的位置。


静态链表中设置备用链表的好处是,可以清楚地知道数组中是否有空闲位置,以便数据链表添加新数据时使用。比如,若静态链表中数组下标为 0 的位置上存有数据,则证明数组已满。


例如,使用静态链表存储 {1,2,3},假设使用长度为 6 的数组 a,则存储状态可能如图 3 所示:

image.png

图 3 备用链表和数据链表


图 3 中,备用链表上连接的依次是 a[0]、a[2] 和 a[4],而数据链表上连接的依次是 a[1]、a[3] 和 a[5]。


静态链表的创建


假设使用静态链表(数组长度为 6)存储 {1,2,3},则需经历以下几个阶段:


  1. 在数据链表未初始化之前,数组中所有位置都处于空闲状态,因此都应被链接在备用链表上,如图 4 所示:
    image.png
    图 4 未存储数据之前静态链表的状态


当向静态链表中添加数据时,需提前从备用链表中摘除节点,以供新数据使用。


备用链表摘除节点最简单的方法是摘除 a[0] 的直接后继节点;同样,向备用链表中添加空闲节点也是添加作为 a[0] 新的直接后继节点。因为 a[0] 是备用链表的第一个节点,我们知道它的位置,操作它的直接后继节点相对容易,无需遍历备用链表,耗费的时间复杂度O(1)


  1. 在图 4 的基础上,向静态链表中添加元素 1 的过程如图 5 所示:
    image.png
    图 5 静态链表中添加元素 1


  1. 在图 5 的基础上,添加元素 2 的过程如图 6 所示:
    image.png
    图 6 静态链表中继续添加元素 2


  1. 在图 6 的基础上,继续添加元素 3 ,过程如图 7 所示:
    image.png
    图 7 静态链表中继续添加元素 3


由此,静态链表就创建完成了。


下面给出了创建静态链表的 C 语言实现代码:

#include <stdio.h>
#define maxSize 6
typedef struct {
int data;
int cur;
}component;
//将结构体数组中所有分量链接到备用链表中
void reserveArr(component *array);
//初始化静态链表
int initArr(component *array);
//输出函数
void displayArr(component * array,int body);
//从备用链表上摘下空闲节点的函数
int mallocArr(component * array);
int main() {
component array[maxSize];
int body=initArr(array);
printf("静态链表为:\n");
displayArr(array, body);
return 0;
}
//创建备用链表
void reserveArr(component *array){
for (int i=0; i<maxSize; i++) {
array[i].cur=i+1;//将每个数组分量链接到一起
array[i].data=-1;
}
array[maxSize-1].cur=0;//链表最后一个结点的游标值为0
}
//提取分配空间
int mallocArr(component * array){
//若备用链表非空,则返回分配的结点下标,否则返回 0(当分配最后一个结点时,该结点的游标值为 0)
int i=array[0].cur;
if (array[0].cur) {
array[0].cur=array[i].cur;
}
return i;
}
//初始化静态链表
int initArr(component *array){
reserveArr(array);
int body=mallocArr(array);
//声明一个变量,把它当指针使,指向链表的最后的一个结点,因为链表为空,所以和头结点重合
int tempBody=body;
for (int i=1; i<4; i++) {
int j=mallocArr(array);//从备用链表中拿出空闲的分量
array[tempBody].cur=j;//将申请的空闲分量链接在链表的最后一个结点后面
array[j].data=i;//给新申请的分量的数据域初始化
tempBody=j;//将指向链表最后一个结点的指针后移
}
array[tempBody].cur=0;//新的链表最后一个结点的指针设置为0
return body;
}
void displayArr(component * array,int body){
int tempBody=body;//tempBody准备做遍历使用
while (array[tempBody].cur) {
printf("%d,%d ",array[tempBody].data,array[tempBody].cur);
tempBody=array[tempBody].cur;
}
printf("%d,%d\n",array[tempBody].data,array[tempBody].cur);
}

代码输出结果为:


静态链表为:


-1,2 1,3 2,4 3,0


提示,此代码创建了一个带有头节点的静态链表,因此最先输出的 "-1,2" 表示的是头节点(-1表示此处未存储数据),其首元节点(存储元素 1 的节点)在数组 array[2] 中。


循环链表(约瑟夫环)的建立及C语言实现


无论是静态链表还是动态链表,有时在解决具体问题时,需要我们对其结构进行稍微地调整。比如,可以把链表的两头连接,使其成为了一个环状链表,通常称为循环链表。


和它名字的表意一样,只需要将表中最后一个结点的指针指向头结点,链表就能成环儿,如图 1 所示。

image.png

图1 循环链表


需要注意的是,虽然循环链表成环状,但本质上还是链表,因此在循环链表中,依然能够找到头指针和首元节点等。循环链表和普通链表相比,唯一的不同就是循环链表首尾相连,其他都完全一样。


循环链表实现约瑟夫环


约瑟夫环问题,是一个经典的循环链表问题


题意是:已知 n 个人(分别用编号 1,2,3,…,n 表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 开始,还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,直到圆桌上剩余一个人


如图 2 所示,假设此时圆周周围有 5 个人,要求从编号为 3 的人开始顺时针数数,数到 2 的那个人出列:

image.png

图 2 循环链表实现约瑟夫环


出列顺序依次为:


  • 编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列;
  • 4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;
  • 1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;
  • 3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;
  • 最后只剩下 5 自己,所以 5 胜出。


约瑟夫环问题有多种变形,比如顺时针转改为逆时针等,虽然问题的细节有多种变数,但解决问题的中心思想是一样的,即使用循环链表。


通过以上的分析,我们可以尝试编写 C 语言代码,完整代码如下所示:

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int number;
struct node * next;
}person;
person * initLink(int n){
person * head=(person*)malloc(sizeof(person));
head->number=1;
head->next=NULL;
person * cyclic=head;
for (int i=2; i<=n; i++) {
person * body=(person*)malloc(sizeof(person));
body->number=i;
body->next=NULL;
cyclic->next=body;
cyclic=cyclic->next;
}
cyclic->next=head;//首尾相连
return head;
}
void findAndKillK(person * head,int k,int m){
person * tail=head;
//找到链表第一个结点的上一个结点,为删除操作做准备
while (tail->next!=head) {
tail=tail->next;
}
person * p=head;
//找到编号为k的人
while (p->number!=k) {
tail=p;
p=p->next;
}
//从编号为k的人开始,只有符合p->next==p时,说明链表中除了p结点,所有编号都出列了,
while (p->next!=p) {
//找到从p报数1开始,报m的人,并且还要知道数m-1de人的位置tail,方便做删除操作。
for (int i=1; i<m; i++) {
tail=p;
p=p->next;
}
tail->next=p->next;//从链表上将p结点摘下来
printf("出列人的编号为:%d\n",p->number);
free(p);
p=tail->next;//继续使用p指针指向出列编号的下一个编号,游戏继续
}
printf("出列人的编号为:%d\n",p->number);
free(p);
}
int main() {
printf("输入圆桌上的人数n:");
int n;
scanf("%d",&n);
person * head=initLink(n);
printf("从第k人开始报数(k>1且k<%d):",n);
int k;
scanf("%d",&k);
printf("数到m的人出列:");
int m;
scanf("%d",&m);
findAndKillK(head, k, m);
return 0;
}

输出结果:


输入圆桌上的人数n:5

从第k人开始报数(k>1且k<5):3

数到m的人出列:2

出列人的编号为:4

出列人的编号为:1

出列人的编号为:3

出列人的编号为:2

出列人的编号为:5


最后出列的人,即为胜利者。当然,你也可以改进程序,令查找出最后一个人时,输出此人胜利的信息。


总结


循环链表和动态链表唯一不同在于它的首尾连接,这也注定了在使用循环链表时,附带最多的操作就是遍历链表。


在遍历的过程中,尤其要注意循环链表虽然首尾相连,但并不表示该链表没有第一个节点和最后一个结点。所以,不要随意改变头指针的指向。


目录
相关文章
|
1月前
|
存储 算法 C语言
线性表,双向链表,静态链表,循环链表(约瑟夫环)(上)
线性表,双向链表,静态链表,循环链表(约瑟夫环)
47 5
|
18天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
16 0
|
18天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
19 0
|
1月前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
18天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
11 0
|
18天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
10 0
|
18天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
15 0
|
27天前
|
缓存 算法
【数据结构】----链表--双向链表
【数据结构】----链表--双向链表
19 0
|
27天前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
65 0