【数据结构】链表的算法和代码实现(C语言)

华南飞虎 · 发表于 2022-12-8 08:14:01

本篇文章将会对算法与数据结构中的链表进行详细介绍. 将详细介绍单链表, 双链表, 循环链表的算法和代码实现(C语言).
0.为什么要开发链表?
试想一下, 你想往一个数组里面存数据, 但是不知道上层程序到底会送多少数据过来, 怎么办? 申请小了可能内存访问越界. 那我们多申请点?

直接申请int的最大值21亿

这样内存迟早会爆的.
再试想一下, 如果我们需要一种长度可变, 并且能存放多种数据类型的结构, 需要怎么做呢? 比如说我希望有既能存一些数, 又能存一些字符串, 并且长度还可变的数据类型.
而以上这些需求, 都可以通过线性表中的链表实现.
1.单链表
我们设计一个数据结构, 包含以下数据, 1.真实的数据(Data域), 2.下一个类似的结构的内存地址(Point域).
这样一来, Data域存放我们想存放的数据, 而Point域指向下一个这种结构的地址.
这种数据结构就被叫做链表结点, 简称结点.
如果我们不断地将一个的指针域指向后一个结点, 后一个结点的指针域再指向他的后一个结点, 以此类推, 我们不就将很多结点像项链一样串起来了吗?
所以这种, 或者类似这种, 前后可以串起来并且储存一定数据的数据结构, 叫做链表.

明白了大致原理, 我们来思考一下应该怎么样创建这个数据结构, 并且将他串起来.

定义一个叫结点的数据结构.
申请一片内存, 并且将其划分为Data域和Point域, 命名为&#34;结点&#34;.
Data存放我们的数据, Point域指向下一个结点.
让新申请的结点的Point域指向刚刚申请的结点, 再返回新申请的结点的内存地址
不断重复过程4, 就将链表串了起来.

OK, 这个就是大致算法, 我们在充分理解算法的基础上(如果有问题评论区呼叫Pandora), 用代码实现这个算法.
定义一个叫 listNode 的数据结构.

该数据结构有Data域(非必须)和Point域(必须), 其中Data域包含了一个int数组, 一个用unsigned int储存的结点编号. 一个bool型变量表面是否有效.

该结点还必须包含一个point域, 用于指向后一个结点. 该数据类型为指针变量.

这个数据结构被命名为 node

OK, 至此, 结点就定义完成了. 我们下一步要创建一个结点, 就像推倒多米诺骨牌的第一块.
定义一个函数叫 creatNewNode , 该函数返回一个指针, 指向新创建的结点.

为这个结点申请一片内存, 长度就是这个结点的长度.

将结点内的int数组的值赋值为输入的int数组的值

因为只是创建了结点, 并没有串起来, 所以可以将Ponit域赋值为NULL

返回这个结点的内存地址(指针).

OK, 到目前为止, 我们定义了结点这个数据结构, 也创建了第一个结点, 我们下一步是不是要把结点之间串起来呀.
我们用一下头插法, 意思是插在链表的头, 类似于排队, 只不过后来的人排队伍前面(有这样排队的???), 注意辨析这个知识点.
如果现在有 \begin{align} 2(\text{head})\to1\to0\to\text{NULL} \end{align} 这个链表, 现在有一个新结点要插入, 头插法相当于
\begin{align} 3(\text{head})\to2\to1\to0\to\text{NULL} \end{align} , 直接在链表的头连上一个形成新链表(注意链表的头是变化的, 不是 0 , 注意这里的链表为了简便, 不含头结点)
我们用图式说明一下这个算法. 我们把要被插的叫做 head, 去插别人的叫做 needToInsert, (感觉有点奇怪?) 实的粉红色的线代表已经建立的连接, 虚线代表即将建立的连接.

那这个算法要怎么用代码实现呢?
哈哈哈, 就是这么简单, 定义一个函数 headInsert 用于头插法插入节点.

指针域指向被插入的链表,

更新一下去插别人的结点的 nodeNumber

返回去插别人的结点的指针, 现在它就是这个链表的头了.

不错不错, 我们跑个程序试一下, 就让这个挨个链表输出自己的结点编号吧. 不过我们要怎么访问呢? 我们得定义一个函数, 用来遍历这个单链表. 就叫他goThrough吧.

这个结点处理结束就跑到下一个节点那里去.

然后我们来看看main函数, 用一个数组存放 114514 , 然后再把这个数组放在这个结点里面.

不断建立新结点并且头插法插入.

遍历这个链表.

跑下试试? 哇真的输出了结点的编号, 而且和我们插入的顺序是一样的.

了解了单链表, 双链表就很容易了.
2.双链表
双链表和单链表类似, 但有以下不同

Point变成两个, 分别指向前一个(Prior)和后一个结点(Next)
单链表只能从头往尾遍历, 双链表可以从尾往头遍历.

OK, 我们改改代码实现双链表. 双链表有两个Point域, 一个指向前一个结点, 一个指向后一个.

像刚刚单链表一样, 双链表也需要创建第一个结点. 不同的是需要有一个 Prior 指针.

结点创建完毕, 我们要怎么样插入呢? 也和单链表类似, 不过得改一下被插入的结点的 Prior 域, 指向插别人的结点.

除此之外, 我们还可以在链表中间插入. 粉红色的线是之前的连接, 蓝色的平滑的线是之后要更改的连接, 绿色的线是要新建立的连接.

这个函数就比较复杂了, 可以选择在哪个结点之后插入, 首先判断插入位置合不合法, 然后再判断是不是相当于头插, 如果是相当于头插, 直接用头插法然后return.

找到应该插入的位置

判断是不是尾插(如果不是则判断为true)

判断需不需要改变结点的编号(只需要改变之前的结点)

注意这两句代码有严格的顺序, 不能交换.

我们在 main 函数里面跑一下试试? 先用头插法, 然后再在结点3之前插入一个编号为 114514 的结点(不改变结点编号), 再遍历.

遍历函数和单链表的写法完全一样

不错不错, 真的在 3 结点后插入了.

OK, 那么现在我们学习了单链表, 双链表, 剩下的循环链表就更简单了.
3.循环链表
循环链表和双链表类似, 只不过有以下区别

头结点的Prior域不再为NULL, 而是指向尾结点
尾结点的Next域不再为NULL, 而是指向头结点

是的, 非常简单, 就这两点区别.
我们稍微改改代码就能创建并且串起循环链表. 结构和双链表一样. 不再赘述.

注意循环链表在创建结点的时候, 不能把prior和next都置位NULL, 而是必须指向自身.

循环链在表中间插入和双链表完全一样, 我们不在赘述.
重点介绍一下头插(尾插类似).
如图所示, 这是插入之前的状态, 我们要让最左边的插入右边的链表.

而红色的线是要进行的更改, 建议按照图式的顺序进行更改.

因为这样做的好处是都是以去插别人的结点为主体, 不容易混, 代码也容易写.

注意return的是去插别人的结点.

尾插法类似, 留作课后习题.
我们也在main函数中写段代码试一下.

强制手动退出, 不然这遍历永远不停, 永远循环遍历.

OK, 至此, 我们就一起学会了单链表, 双链表, 循环链表的数据结构算法和代码实现.
嘻嘻嘻, 可以要你一个赞吗?

<hr/>C语言计算 100 亿之前的所有质数:
<hr/>文章封面
蛍ちゃん

<hr/>//  linkedList
//  Created by Pandora on 2022/11/21.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct listNode{
int data[1024];
unsigned nodeNumber;
bool valid;
struct listNode *next;
}node;

typedef struct doubleListNode{
int data[1024];
unsigned nodeNumber;
bool valid;
struct doubleListNode *prior;
struct doubleListNode *next;
}dNode;

typedef struct circularListNode{
int data[1024];
unsigned nodeNumber;
bool valid;
struct circularListNode *prior;
struct circularListNode *next;
}cNode;

node *creatNewNode(int *intArray,bool ifValid){
node *newNode=malloc(sizeof(node));
for(int arrayIndex=0;arrayIndex<1024;arrayIndex++){
      newNode->data[arrayIndex]=intArray[arrayIndex];
}
newNode->next=NULL;
newNode->valid=ifValid;
newNode->nodeNumber=0;
return newNode;
}

dNode *creatNewDoubleNode(int *intArray,bool ifValid){
dNode *newNode=malloc(sizeof(dNode));
for(int arrayIndex=0;arrayIndex<1024;arrayIndex++){
      newNode->data[arrayIndex]=intArray[arrayIndex];
}
newNode->prior=NULL;
newNode->next=NULL;
newNode->valid=ifValid;
newNode->nodeNumber=0;
return newNode;
}

cNode *creatNewCircularNode(int *intArray,bool ifValid){
cNode *newNode=malloc(sizeof(cNode));
for(int arrayIndex=0;arrayIndex<1024;arrayIndex++){
      newNode->data[arrayIndex]=intArray[arrayIndex];
}
newNode->prior=newNode;
newNode->next=newNode;
newNode->valid=ifValid;
newNode->nodeNumber=0;
return newNode;
}

node *headInsert(node *head,node *nodeToInsert){
nodeToInsert->next=head;
nodeToInsert->nodeNumber=head->nodeNumber+1;
return nodeToInsert;
}

dNode *headInsertDnode(dNode *head,dNode *nodeToInsert){
nodeToInsert->next=head;
head->prior=nodeToInsert;
nodeToInsert->nodeNumber=head->nodeNumber+1;
return nodeToInsert;
}

cNode *headInsertCnode(cNode *head,cNode *nodeToInsert){
nodeToInsert->nodeNumber=head->nodeNumber+1;
nodeToInsert->prior=head->prior;          // 1
nodeToInsert->next=head;                   // 2
nodeToInsert->prior->next=nodeToInsert;    // 3
nodeToInsert->next->prior=nodeToInsert;    // 4
return nodeToInsert;
}

dNode *insertByNumber(dNode *doubleList,dNode *needToInsert,unsigned whereToInsert,bool changeNodeNumber){
if(whereToInsert>((doubleList->nodeNumber)+1)){
      printf(&#34;INSERT FAILED!&#34;);
      return doubleList;
}
dNode *head=doubleList;
if(whereToInsert==((doubleList->nodeNumber)+1)){
      int nodeNumber=needToInsert->nodeNumber;
      head=headInsertDnode(doubleList,needToInsert);
      head->nodeNumber=nodeNumber;
      return head;
}
while(!(doubleList->nodeNumber==whereToInsert)){
      doubleList=doubleList->next;
}
int priorNodeNumber=0;
if(doubleList->next){
      priorNodeNumber=needToInsert->nodeNumber;
      needToInsert->next=doubleList->next;
      doubleList->next->prior=needToInsert;
}
doubleList->next=needToInsert;
needToInsert->prior=doubleList;
if(changeNodeNumber){
      while(needToInsert){
         priorNodeNumber++;
         needToInsert->nodeNumber=priorNodeNumber;
         needToInsert=needToInsert->prior;
      }
}
return head;
}

void goThrough(node *toGoThrough){
while(toGoThrough){
      if(toGoThrough->valid){
         printf(&#34;NODE NUMBER: %d\n&#34;,toGoThrough->nodeNumber);
      }
      toGoThrough=toGoThrough->next;
}
}

void goThroughDnode(dNode *toGoThrough){
while(toGoThrough){
      if(toGoThrough->valid){
         printf(&#34;NODE NUMBER: %d\n&#34;,toGoThrough->nodeNumber);
      }
      toGoThrough=toGoThrough->next;
}
}

void goThroughCnode(cNode *toGoThrough){
while(toGoThrough){
      if(toGoThrough->valid){
         printf(&#34;NODE NUMBER: %d\n&#34;,toGoThrough->nodeNumber);
      }
      toGoThrough=toGoThrough->next;
}
}

int main(int argc, const char * argv[]) {
int intArray[1024]={114514};
node *list=creatNewNode(intArray,true);
for(int i=0;i<7;i++){
      node *toInsert=creatNewNode(intArray,true);
      list=headInsert(list,toInsert);
}
dNode *dList=creatNewDoubleNode(intArray,true);
for(int i=0;i<7;i++){
      dNode *dNodeToInsert=creatNewDoubleNode(intArray,true);
      dList=headInsertDnode(dList,dNodeToInsert);
}
dNode *dNodeToInsert=creatNewDoubleNode(intArray,true);
dNodeToInsert->nodeNumber=114514;
dList=insertByNumber(dList,dNodeToInsert,3,false);
cNode *cList=creatNewCircularNode(intArray,true);
for(int i=0;i<7;i++){
      cNode *cNodeToInsert=creatNewCircularNode(intArray,true);
      cList=headInsertCnode(cList,cNodeToInsert);
}
goThroughCnode(cList);
return 0;
}

评论区太酸 · 发表于 2022-12-8 08:14:32

写的很详细很容易就看懂了[赞同]

谢松荣 · 发表于 2022-12-8 08:15:08

臭死了这个链表不能用了[捂脸][捂脸]

徐登峰 · 发表于 2022-12-8 08:15:43

深入浅出地从链式存储的优势入手，讲解并实现了链表这种基础且实用的数据结构，每一步都有详细的代码和说明，是一篇很好的基础教程帖。但是能不能好好说话，你放这种图的时候有没有考虑过营养不好的农村人的感受[生气]一个月才能喝一瓶的营养快线你这一张图就霍霍完了[大哭]

徐丰 · 发表于 2022-12-8 08:16:06

很详细nice[爱]