数据结构线性表链表

作者：IC00

2022 年 10 月 08 日
湖南
本文字数：4362 字
阅读完需：约 14 分钟

前言：

今天课上我们老师复习了单链表的头插法和尾插法，插入和删除，这几个不太懂的童鞋关注我上一篇文章，然后老师讲解了约瑟夫环，约瑟夫环采用的是循环链表，今天我们复习一下约瑟夫环的算法，顺便提前预习一下双向链表和循环双向链表。

每日一遍，防止颓废

你的室友可能在划水，但绝对没有停止学习，明修栈道，暗度陈仓

1.1 约瑟夫环

我们先了解一下约瑟夫环，约瑟夫环是一个悲惨的故事在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止，我们用简单一点的数据，N 个人围成一圈，从第一个开始报数，第 M 个将被出列。例如 N=6，M=5，出列的顺序是：5，4，6，2，3**，**1

来个图分析一下：

讲人话就是：一个首尾连接的单链表，每次计数，达到要求了把它输出再删除，差不多和单链表的删除一样（只是多循环了几次）：写一下给大家看看，代码如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct Node {    int  data;    struct Node *next;}link;link * creattail(int * arc, int length) {//这里我们采用尾插法 ,来创建链表     int i;    link * q ; //q用来标记上个结点的位置，然后q和下一个新建结点连接    link * H =(link*)malloc(sizeof(link));//创建第一个结点     H->data = arc[0];    H->next = NULL;    q = H;  //q要记住第一个结点     for (i = 1; i<length; i++) {        link * a = (link*)malloc(sizeof(link));//创建新结点         q->next = a;    //上个结点连接新建立的结点，从而产生每次新建结点在最后一个         a->data = arc[i]; //给新建立的结点赋值         a->next = NULL; //因为新建立的结点是最后一个，所以它的指针域是NULL         q = a;  //q 现在标记新建立的结点，作为最后一个结点，方便后面新建立的结点连接q      }    return H;//返回第一个结点 }link * creatcycle (int * arc, int length) {//这里我们采用尾插法 ,来创建链表     int i;    link * q ; //q用来标记上个结点的位置，然后q和下一个新建结点连接    link * H =(link*)malloc(sizeof(link));//创建第一个结点     H->data = arc[0];    H->next = NULL;    q = H;  //q要记住第一个结点     for (i = 1; i<length; i++) {        link * a = (link*)malloc(sizeof(link));//创建新结点         q->next = a;    //上个结点连接新建立的结点，从而产生每次新建结点在最后一个         a->data = arc[i]; //给新建立的结点赋值         a->next = H; //因为新建立的结点是最后一个，所以我们指向头结点形成循环链表         q = a;  //q 现在标记新建立的结点，作为最后一个结点，方便后面新建立的结点连接q      }    return H;//返回第一个结点 }void yuesefu(link *p,int n,int m){   int i=1;   link * q;   q = p;   int j=1;   while(j<n&&p!=NULL)   {       if(i==m)//判断计数i是不是等于m,如果等于m说明到了q这个指针要出列      {       i=1;       j++;  //统计结点数        printf("%d,",p->data);       q->next = p->next; //上一个结点连接当前的下一个结点        free(p);  //释放结点        p=q->next; //因为我i赋值为1，所以我之间把p指向q的下一个      }     else     {       i++;//没到位置计数+1        q =p; //标记当前位置，因为p马上要去下一个位置        p=p->next;//到下一个结点      }   }    printf("%d",p->data);//输出最后一个结点     free(p);}
void display(link *p) { //链表的输出函数,遍历链表     while (p) {        printf("%d ", p->data);        p = p->next;    }    printf("\n");}void displaycycle(link *p,int a) { // 因为是循环链表不管那个结点都可以遍历整个表，所要传遍历次数 a   int i=0;    while (i<a) {       i++;        printf("%d ", p->data);         p = p->next;    }    printf("\n");}int main() {    int a[6] = { 1,2,3,4,5,6};    link * cycle = creatcycle(a, 6);    //采用尾插法,创建循环链表     displaycycle(cycle,6);      //输出一下     yuesefu(cycle,6,5);        //约瑟夫环实现，cycle代表循环链表，6代表总结点数，5为第几个位置输出     free(cycle);    return 0;}

复制代码

效果展示：

2.双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点（讲人话就是：一个结点可以往前访问也可以往后面访问）结合生活中的楼梯或者电梯联想一下吧：

用个小故事加深大家的映像

微风拂过那窗口那个女孩的脸庞，她似乎在注视着什么，楼下的人群过马路的人群，有着一个男孩的，她注视着，直到那个男孩注视着她，他们的眼神在交流，女孩脸庞展露着丝丝红润，似刚刚开放的桃花，微微泛红，又似蜜桃，甜润饱满，男孩的眼神，如电一般，犀利，迷人，他们眼神相对，彼此逃避着，又互相牵引着，女孩快速出门，来到了，楼梯间，她犹豫着，他会走那边，这边也可以上下，那边也可以，男孩也犹豫着，天公不作美，他们之间，一个下楼，一个上楼，彼此错过，男孩摇摇头说：“下次遇到她一定要叫她交房租”，女孩叹着气说：“幸亏跑的快，不然就要交房租了”，哈哈哈，女孩下楼就是链表往下遍历 next，男孩上楼就是往上遍历 port，他们之间其实就是相当于两条链表，但是有同学就问了，我要是那个男孩就上去一半，发现她不在，然后再到另一边下去，就可以遇到她了，说明我们同学还是很聪明的，这就相当于我往下遍历一半，再往上遍历回到起点，这种做法在双向链表里可以做到的，双向链表就好比坐电梯能上能下，楼层就是我们的数据。

#include <stdio.h>#include <stdlib.h>#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct Node {    int  data;    struct Node *port,*next;}link;link * creat(int * arc, int length) {//使用尾插法创建     int i=0;    link * q,* p,*head;    head = q = p=(link*)malloc(sizeof(link));//创建第一个结点     q->data = arc[0];    q->next = NULL;//第一个结点后继NULL     q->port = NULL;// 第一个结点前驱NULL     for (i = 1; i<length; i++) {          p = (link*)malloc(sizeof(link));//创建新结点         p ->data =arc[i];        p ->port = q; //新结点前驱连接上一个结点     q ->next = p;//上一个结点的后继连接当前的结点     q =p;    //然后把上一个结点的标记q，指向新结点     p->next =NULL; //新结点的指针域指向NULL     }   return head;}void displayport(link *p) { //链表的输出函数,使用前驱遍历链表     while (p) {        printf("%d ", p->data);        p = p->port;    }    printf("\n");}void displaynext(link *p) { //链表的输出函数,使用后继遍历链表      printf("%d ", p->data);  while (p->next) {    p = p->next;         printf("%d ", p->data);       }     printf("\n");    displayport(p);//传最后一个结点用后继输出一下     }int main(int argc, char *argv[]) {   int a[6] = { 1,2,3,4,5,6};     link * list = creat(a, 6);          displaynext(list);//使用后继输出      }

复制代码

博主用的是尾插法新建的效果展示一下:

3.双向链表插入和删除：

3.1 双向链表的插入，插入是需要两个结点的，注意：要保持 p 的后继是最后断开就可以了，也就是第四步其他几步的位置没要求。

void insert(link *p,int n,int m)//在第n后的位置插入数据m {  int i= 1;  while(i<n)  {    p =p->next;      i++;  }  link * q=(link*)malloc(sizeof(link));//创建结点   q->data = m;//把m的数据给q   p->next->port = q;//2.p->next的前驱连接新结点   q->next = p->next;//1.新插入的结点后继连接p->next   q->port = p;//3 新插入的结点的前驱指向p   p->next = q;//4 p的后继指向q;注前三条位置可以随便动       }

复制代码

效果展示：

3.2 双向链表的删除，只需要一个结点，就可以完成啦

代码如下：

void deletelist(link *p,int n){  int i=1;  while(i<n)  {    p =p->next;      i++;  }  p->port->next = p->next;//第一步   p->next->port = p->port;//第二步   free(p);//第三步  }

复制代码

效果展示：我删除了链表 3 位置的数据

3.循环双向链表

3.1 循环双向链表和循环单链表差不多，就是多了个前驱结点，可以往前执行。

3.2 创建循环双向链表，让我们卷起来，铁子们

用代码实现一下：


link * creatcycle(int * arc, int length) {//使用尾插法创建     int i=0;    link * q,* p,*head;    head = q = p=(link*)malloc(sizeof(link));//第一步：创建第一个结点     p->data = arc[0];    p->next = p;//第一个结点后继NULL     p->port = p;// 第一个结点前驱NULL     for (i = 1; i<length; i++) {          p = (link*)malloc(sizeof(link));//第二步：创建新结点         p ->data =arc[i];        p ->port = q; //第三步：新结点前驱连接上一个结点     q ->next = p;//第四步上一个结点的后继连接当前的结点     p->next =head;//第五步：最后一个结点指向head     head->port = p;//head的前驱指向p     q =p;    //然后把上一个结点的标记q，指向新结点     }   return head;}void displaycycle(link *p) { //链表的输出函数,使用后继遍历链表     link * head=p;    printf("%d ", p->data);  p = p->next;   while (p!=head) {        printf("%d ", p->data);     p = p->next;       }     printf("\n");}

复制代码

效果展示：

使用我们之前双向链表后继的输出应该是死循环

使用我们之前双向链表前驱的输出应该是死循环

总结：

数据结构，线性表链表的操作我们基本上都操作，循环双向链表的插入和删除和双向表的插入删除是一样的，我们没有做更多的操作了，如果有什么问题，可以评论问我，我们可以一起探讨一下，学习还是得动手敲，博主提供的代码是可以直接建项目跑，也可以跟着博主总结的步骤图，一步一步的敲。好了，创作不易，希望大家喜欢，点赞，关注，评论，收藏，博主会跟着数据结构往下面更新，有喜欢的可以收藏哦。放个图让大家卷起来。

上一篇：# 数据结构专升本学习笔记，线性表链表小节</br>下一篇：# 数据结构专升本学习，栈篇（顺序栈）