数据结构——单向循环链表、双链表、双向循环链表

目录

一、单向循环链表

  1.1 单向循环链表的概念

  1.2 单向循环链表的操作

    1.2.1 单向循环链表的创建

    1.2.2 单向循环链表的头插

    1.2.3 单向循环链表的遍历

    1.2.4 单向循环链表的头删

    1.2.5 单向循环链表的尾插

    1.2.6 单向循环链表的尾删

    1.2.7 约瑟夫环

  1.3 单向循环列表所有程序

    1.3.1 head.h

    1.3.2 main.c

    1.3.3 fun.c

  1.4 输出效果

二、双链表

  2.1 双链表的概念

  2.2 双链表的操作

    2.2.1 双链表的创建

    2.2.2 双链表的头插

    2.2.3 双链表的遍历

    2.2.4 双链表的头删

    2.2.5 双链表的尾插

    2.2.6 双链表的尾删

  2.3 双链表所有程序

    2.3.1 head.h

    2.3.2 main.c

    2.3.3 fun.c

  2.4 输出效果

三、双向循环列表

  3.1 双向循环链表的概念

  3.2 双向循环链表的操作

    3.2.1 双向循环链表的创建

    3.2.2 双向循环链表的头插

    3.2.3 双向循环链表的遍历

    3.2.4 双向循环链表的头删

    3.2.5 双向循环链表的尾插

    3.2.6 双向循环链表的尾删

  3.3 双向循环链表所有程序

    3.3.1 head.h

    3.3.2 main.c

    3.3.3 fun.c

  3.4 输出效果

---

一、单向循环链表

  1.1 单向循环链表的概念

        1.单向循环链表：尾节点的指针域指向头结点的地址

        2.单向循环链表的节点：数据域和指针域

        数据域：存储的数据元素

        指针域：存储节点之间的关系，下一个节点的地址，单向循环链表的指针域指向该节点的地址

  1.2 单向循环链表的操作

    1.2.1 单向循环链表的创建

// 创建单向循环链表---------------
Linklist creat_node()
{// 1.创建一个新的节点Linklist s=(Linklist)malloc(sizeof(struct Node));// 2. if(NULL==s)return NULL;// 初始化新节点的数据域s->data=0;// 初始化新节点的指针域s->next=s;return s;
}

    1.2.2 单向循环链表的头插

// 头插---------------
Linklist insert_head(Linklist head,datatype element)
{Linklist s=creat_node();s->data=element;// 1.判断链表是否为空if(NULL==head)head=s;else  // 链表中存在多个节点 >=1{// 找到尾节点Linklist del=head;while(del->next!=head){del=del->next;}s->next=head;head=s;del->next=head;}return head;
}

    1.2.3 单向循环链表的遍历

// 循环遍历---------------
void output(Linklist head)
{//  1.判断链表是否为空if(NULL==head)return;// 2.循环遍历Linklist p=head;printf("Linklist=");do{printf("%d ",p->data);p=p->next;}while(p!=head);putchar(10);return;
}

    1.2.4 单向循环链表的头删

// 单向循环链表的头删---------------
Linklist delete_head(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表是否为1if(head->next==head){free(head);head=NULL;return head;}// 3.头删//  找到尾节点Linklist real=head;while(real->next!=head){real=real->next;}Linklist del;del=head;head=head->next;free(del);del=NULL;real->next=head;return head;
}

    1.2.5 单向循环链表的尾插

// 单向循环链表的尾插---------------
Linklist insert_tail(Linklist head,datatype element)
{// 1.创建新节点，并输入值Linklist s=creat_node();s->data=element;s->next=head;// 2.判断链表是否为空if(NULL==head){head=s;}else{// 3.尾插Linklist p=head;while(p->next!=head)  // 找到最后一个节点{p=p->next;}p->next=s;  // 链接:p指针域指向新节点的地址}return head;
}

    1.2.6 单向循环链表的尾删

// 单向循环链表的尾删---------------
Linklist delete_tail(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.只有一个节点时else if(head->next==head){free(head);head=NULL;}// 3.有多个节点时else{Linklist del=head;// 找到倒数第二个节点while(del->next->next!=head){del=del->next;}// 删除p的后继free(del->next);del->next=head;}return head;
}

    1.2.7 约瑟夫环

        约瑟夫环：用循环链表编程实现约瑟夫问题

        n个人围成一圈，从某人开始报数1, 2, …, m，数到m的人出圈，然后从出圈的下一个人(m+1)开始重复此过程，直到 全部人出圈，于是得到一个出圈人员的新序列

        如当n=8，m=4时，若从第一个位置数起，则所得到的新的序列 为4, 8, 5, 2, 1, 3, 7, 6。

// 约瑟夫环
Linklist joseph(Linklist head,int n, int m)
{Linklist p=head;Linklist del=NULL;Linklist s=NULL;for(int i=1;i<=n;i++){for(int j=1;j<m-1;j++){p=p->next;}del=p->next;p->next=p->next->next;p=p->next;if(i==1){head=del;head->next=head;}else{s=head;while(s->next!=head){s=s->next;}del->next=head;s->next=del;}}return head;
}

  1.3 单向循环列表所有程序

    1.3.1 head.h

#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int datatype;
enum passble{SUCCSSES,FALSE=-1};
// 节点结构定义
// 节点：数据、指针域
// Node不可省略
typedef struct Node
{datatype data;  // 数据域：数据元素struct Node *next;  // 指针域：节点之间的关系，下一个节点的地址
}*Linklist;Linklist creat_node();
Linklist insert_head(Linklist head,datatype element);
void output(Linklist head);
Linklist delete_head(Linklist);
Linklist insert_tail(Linklist head,datatype element);
Linklist delete_tail(Linklist head);
int get_len(Linklist head);
Linklist joseph(Linklist head,int n, int m);#endif

    1.3.2 main.c

#include "head.h"
int main(int argc, const char *argv[])
{
// 单向循环链表的创建
// 单向循环链表的头插Linklist head=NULL;int n;printf("请输入插入个数:");scanf("%d",&n);datatype element;for(int i=0;i<n;i++){printf("请输入插入的第 %d 个元素:",i+1);scanf("%d",&element);head=insert_head(head,element);}output(head);// 单向循环链表的头删head=delete_head(head);printf("头删后");output(head);
// 单向循环链表的尾插printf("请输入尾插个数:");scanf("%d",&n);for(int i=0;i<n;i++){printf("请输入尾插元素:");scanf("%d",&element);head=insert_tail(head,element);}output(head);// 单向循环链表的尾删head=delete_tail(head);printf("尾删后");output(head);// 约瑟夫环int m=4;head=joseph(head,n,m);output(head);return 0;
}

    1.3.3 fun.c

#include "head.h"
// 创建单向循环链表---------------
Linklist creat_node()
{// 1.创建一个新的节点Linklist s=(Linklist)malloc(sizeof(struct Node));// 2. if(NULL==s)return NULL;// 初始化新节点的数据域s->data=0;// 初始化新节点的指针域s->next=s;return s;
}
// 头插---------------
Linklist insert_head(Linklist head,datatype element)
{Linklist s=creat_node();s->data=element;// 1.判断链表是否为空if(NULL==head)head=s;else  // 链表中存在多个节点 >=1{// 找到尾节点Linklist del=head;while(del->next!=head){del=del->next;}s->next=head;head=s;del->next=head;}return head;
}// 循环遍历---------------
void output(Linklist head)
{//  1.判断链表是否为空if(NULL==head)return;// 2.循环遍历Linklist p=head;printf("Linklist=");do{printf("%d ",p->data);p=p->next;}while(p!=head);putchar(10);return;
}
// 单向循环链表的头删---------------
Linklist delete_head(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表是否为1if(head->next==head){free(head);head=NULL;return head;}// 3.头删//  找到尾节点Linklist real=head;while(real->next!=head){real=real->next;}Linklist del;del=head;head=head->next;free(del);del=NULL;real->next=head;return head;
}
// 单向循环链表的尾插---------------
Linklist insert_tail(Linklist head,datatype element)
{// 1.创建新节点，并输入值Linklist s=creat_node();s->data=element;s->next=head;// 2.判断链表是否为空if(NULL==head){head=s;}else{// 3.尾插Linklist p=head;while(p->next!=head)  // 找到最后一个节点{p=p->next;}p->next=s;  // 链接:p指针域指向新节点的地址}return head;
}
// 单向循环链表的尾删---------------
Linklist delete_tail(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.只有一个节点时else if(head->next==head){free(head);head=NULL;}// 3.有多个节点时else{Linklist del=head;// 找到倒数第二个节点while(del->next->next!=head){del=del->next;}// 删除p的后继free(del->next);del->next=head;}return head;
}// 约瑟夫环
Linklist joseph(Linklist head,int n, int m)
{Linklist p=head;Linklist del=NULL;Linklist s=NULL;for(int i=1;i<=n;i++){for(int j=1;j<m-1;j++){p=p->next;}del=p->next;p->next=p->next->next;p=p->next;if(i==1){head=del;head->next=head;}else{s=head;while(s->next!=head){s=s->next;}del->next=head;s->next=del;}}return head;
}

  1.4 输出效果

二、双链表

  2.1 双链表的概念

        引入目的：无论是单向循环或单向链表，只能向后遍历吗，不可以向前访问，引出双链表

        1.双向链表：链表既可以向前访问也可以向后访问

        2.双向链表的节点

        3.双向链表节点的结构体定义

        结构体：数据域，两个指针域

        4.双向链表插入和删除的思想

  2.2 双链表的操作

    2.2.1 双链表的创建

// 创建节点
Doublelink creat_link()
{Doublelink s=(Doublelink)malloc(sizeof(struct Node));if(NULL==s)return NULL;s->data=0;  // 新节点的数据域初始化s->next=NULL;  // 新节点的指针域初始化s->last=NULL;return s;
}

    2.2.2 双链表的头插

// 双向列表的头插
Doublelink insert_head(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s;return head;}// 2.链表不为空，存在多个节点s->next=head;  // 新节点的next指向头节点head->last=s;  // 头结点的last指向新节点head=s; // 使新节点成为头结点return head;
}

    2.2.3 双链表的遍历

// 双向列表的遍历
void outlink(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return;// 2.链表不为空else{Doublelink p=head;printf("正向遍历 Doublelink= ");while(p->next!=NULL){printf("%c ",p->data);p=p->next;}printf("%c ",p->data);putchar(10);printf("逆向遍历 Doublelink= ");while(p){printf("%c ",p->data);p=p->last;}putchar(10);}return;
}

    2.2.4 双链表的头删

// 双向链表的头删
Doublelink delete_head(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==NULL){free(head);head=NULL;return head;}// 2.链表有多个节点head=head->next;  // 让第二个节点成为头结点free(head->last);  // 释放原头结点head->last=NULL;  // 让新头结点的last指向空
}

    2.2.5 双链表的尾插

// 双向列表的尾插
Doublelink insert_tail(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s; // 直接让head指向新节点，即让新节点成为头结点return head;}// 2.链接有一个或多个节点Doublelink p=head;while(p->next!=NULL)  // 找到最后一个节点{p=p->next;}p->next=s;  // 让位后一个节点指向新节点，即新节点成为尾节点s->last=p;  // 让新节点的last指向原尾节点return head;}

    2.2.6 双链表的尾删

// 双向列表的尾删
Doublelink delete_tail(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==NULL){free(head);  // 释放头结点head=NULL;  // head指向空return head;}// 3.链表有多个节点else{Doublelink p=head;while(p->next->next!=NULL)  // 找到倒数第二个节点{p=p->next;}free(p->next);  // 释放最后一个节点p->next=NULL;  // 让原倒数第二个节点指向空，即成为最后一个节点return head;}}

  2.3 双链表所有程序

    2.3.1 head.h

#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum passble{SUCCESS,FALSE=-1};
typedef char datatype;
// 双向链表节点结构体
typedef struct Node
{//数据域：数据元素datatype data;//指针域：下一个节点的地址struct Node *next;//指针域：上一个节点的地址struct Node *last;
}*Doublelink;
Doublelink creat_link();
Doublelink insert_head(Doublelink head,datatype element);
void outlink(Doublelink head);
Doublelink delete_head(Doublelink head);
Doublelink insert_tail(Doublelink head,datatype element);
Doublelink delete_tail(Doublelink head);#endif

    2.3.2 main.c

#include "head.h"
int main(int argc, const char *argv[])
{Doublelink head=NULL;  // 定义一个链表节点指针int n;printf("请输入存入数据数量n:");scanf("%d",&n);datatype element;for(int i=1;i<=n;i++){printf("请输入第%d个元素:",i);// scanf("%c",&element);getchar();element=getchar();head=insert_head(head,element);}
// 双向列表的遍历outlink(head);// 双向链表的头删head=delete_head(head);printf("头删后\n");outlink(head);// 双向列表的尾插printf("请输入尾插元素个数:");scanf("%d",&n);for(int i=1;i<=n;i++){printf("请输入尾插的第%d个元素:",i);getchar();element=getchar();head=insert_tail(head,element);}outlink(head);// 双向列表的尾删head=delete_tail(head);printf("尾删后\n");outlink(head);return 0;
}

    2.3.3 fun.c

#include "head.h"
// 创建节点
Doublelink creat_link()
{Doublelink s=(Doublelink)malloc(sizeof(struct Node));if(NULL==s)return NULL;s->data=0;  // 新节点的数据域初始化s->next=NULL;  // 新节点的指针域初始化s->last=NULL;return s;
}// 双向列表的头插
Doublelink insert_head(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s;return head;}// 2.链表不为空，存在多个节点s->next=head;  // 新节点的next指向头节点head->last=s;  // 头结点的last指向新节点head=s; // 使新节点成为头结点return head;
}// 双向列表的遍历
void outlink(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return;// 2.链表不为空else{Doublelink p=head;printf("正向遍历 Doublelink= ");while(p->next!=NULL){printf("%c ",p->data);p=p->next;}printf("%c ",p->data);putchar(10);printf("逆向遍历 Doublelink= ");while(p){printf("%c ",p->data);p=p->last;}putchar(10);}return;
}// 双向链表的头删
Doublelink delete_head(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==NULL){free(head);head=NULL;return head;}// 2.链表有多个节点head=head->next;  // 让第二个节点成为头结点free(head->last);  // 释放原头结点head->last=NULL;  // 让新头结点的last指向空
}// 双向列表的尾插
Doublelink insert_tail(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s; // 直接让head指向新节点，即让新节点成为头结点return head;}// 2.链接有一个或多个节点Doublelink p=head;while(p->next!=NULL)  // 找到最后一个节点{p=p->next;}p->next=s;  // 让位后一个节点指向新节点，即新节点成为尾节点s->last=p;  // 让新节点的last指向原尾节点return head;}// 双向列表的尾删
Doublelink delete_tail(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==NULL){free(head);  // 释放头结点head=NULL;  // head指向空return head;}// 3.链表有多个节点else{Doublelink p=head;while(p->next->next!=NULL)  // 找到倒数第二个节点{p=p->next;}free(p->next);  // 释放最后一个节点p->next=NULL;  // 让原倒数第二个节点指向空，即成为最后一个节点return head;}}

  2.4 输出效果

三、双向循环列表

  3.1 双向循环链表的概念

        双向循环链表：尾节点的下一个节点是头节点，头节点的上一个节点是尾节点

  3.2 双向循环链表的操作

    3.2.1 双向循环链表的创建

#include "head.h"
// 创建节点
Doublelink creat_link()
{Doublelink s=(Doublelink)malloc(sizeof(struct Node));if(NULL==s)return NULL;s->data=0;  // 新节点的数据域初始化s->next=s;  // 新节点的指针域初始化s->last=s;return s;
}

    3.2.2 双向循环链表的头插

// 双向循环列表的头插
Doublelink insert_head(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s;return head;}// 2.链表不为空，存在多个节点s->next=head;  // 新节点的next指向头节点s->last=head->last;  // 新节点的last指向尾节点head->last->next=s;  // 尾节点的next指向新节点head->last=s;  // 头结点的last指向新节点head=s; // 使新节点成为头结点return head;
}

    3.2.3 双向循环链表的遍历

// 双向循环列表的遍历
void outlink(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return;// 2.链表不为空else{Doublelink p=head;printf("正向遍历 Doublelink= ");while(p->next!=head){printf("%c ",p->data);p=p->next;}printf("%c ",p->data);putchar(10);printf("逆向遍历 Doublelink= ");while(p!=head){printf("%c ",p->data);p=p->last;}printf("%c",p->data);putchar(10);}return;
}

    3.2.4 双向循环链表的头删

// 双向循环链表的头删
Doublelink delete_head(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==head){free(head);head=NULL;return head;}// 2.链表有多个节点Doublelink p=head;head->last->next=head->next;head=head->next;  // 让第二个节点成为头结点head->last=head->last->last;  // 让新头结点指向尾节点free(p);  // 释放原头结点p=NULL;  // 让指针p指向空return head;
}

    3.2.5 双向循环链表的尾插

// 双向循环列表的尾插
Doublelink insert_tail(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s; // 直接让head指向新节点，即让新节点成为头结点return head;}// 2.链接有一个或多个节点head->last->next=s;  // 让最后一个节点指向新节点，即新节点成为尾节点s->next=head;s->last=head->last;  // 让新节点的last指向原尾节点head->last=s;return head;}

    3.2.6 双向循环链表的尾删

// 双向循环列表的尾删
Doublelink delete_tail(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==head){free(head);  // 释放头结点head=NULL;  // head指向空return head;}// 3.链表有多个节点else{head->last=head->last->last;  // 让头结点的last指向倒数第二个节点free(head->last->next);  // 释放最后一个节点head->last->next=head;  // 让原倒数第二个节点指向头结点，即成为最后一个节点return head;}}

  3.3 双向循环链表所有程序

    3.3.1 head.h

#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum passble{SUCCESS,FALSE=-1};
typedef char datatype;
// 双向链表节点结构体
typedef struct Node
{//数据域：数据元素datatype data;//指针域：下一个节点的地址struct Node *next;//指针域：上一个节点的地址struct Node *last;
}*Doublelink;
Doublelink creat_link();
Doublelink insert_head(Doublelink head,datatype element);
void outlink(Doublelink head);
Doublelink delete_head(Doublelink head);
Doublelink insert_tail(Doublelink head,datatype element);
Doublelink delete_tail(Doublelink head);#endif

    3.3.2 main.c

#include "head.h"
int main(int argc, const char *argv[])
{Doublelink head=NULL;  // 定义一个链表节点指针int n;printf("请输入存入数据数量n:");scanf("%d",&n);datatype element;for(int i=1;i<=n;i++){printf("请输入第%d个元素:",i);// scanf("%c",&element);getchar();element=getchar();head=insert_head(head,element);}
// 双向循环列表的遍历outlink(head);// 双向循环链表的头删head=delete_head(head);printf("头删后\n");outlink(head);// 双向循环列表的尾插printf("请输入尾插元素个数:");scanf("%d",&n);for(int i=1;i<=n;i++){printf("请输入尾插的第%d个元素:",i);getchar();element=getchar();head=insert_tail(head,element);}outlink(head);// 双向循环列表的尾删head=delete_tail(head);printf("尾删后\n");outlink(head);return 0;
}

    3.3.3 fun.c

#include "head.h"
// 创建节点
Doublelink creat_link()
{Doublelink s=(Doublelink)malloc(sizeof(struct Node));if(NULL==s)return NULL;s->data=0;  // 新节点的数据域初始化s->next=s;  // 新节点的指针域初始化s->last=s;return s;
}// 双向循环列表的头插
Doublelink insert_head(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s;return head;}// 2.链表不为空，存在多个节点s->next=head;  // 新节点的next指向头节点s->last=head->last;  // 新节点的last指向尾节点head->last->next=s;  // 尾节点的next指向新节点head->last=s;  // 头结点的last指向新节点head=s; // 使新节点成为头结点return head;
}// 双向循环列表的遍历
void outlink(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return;// 2.链表不为空else{Doublelink p=head;printf("正向遍历 Doublelink= ");while(p->next!=head){printf("%c ",p->data);p=p->next;}printf("%c ",p->data);putchar(10);printf("逆向遍历 Doublelink= ");while(p!=head){printf("%c ",p->data);p=p->last;}printf("%c",p->data);putchar(10);}return;
}// 双向循环链表的头删
Doublelink delete_head(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==head){free(head);head=NULL;return head;}// 2.链表有多个节点Doublelink p=head;head->last->next=head->next;head=head->next;  // 让第二个节点成为头结点head->last=head->last->last;  // 让新头结点指向尾节点free(p);  // 释放原头结点p=NULL;  // 让指针p指向空return head;
}// 双向循环列表的尾插
Doublelink insert_tail(Doublelink head,datatype element)
{Doublelink s=creat_link();s->data=element;// 1.判断链表是否为空if(NULL==head){head=s; // 直接让head指向新节点，即让新节点成为头结点return head;}// 2.链接有一个或多个节点head->last->next=s;  // 让最后一个节点指向新节点，即新节点成为尾节点s->next=head;s->last=head->last;  // 让新节点的last指向原尾节点head->last=s;return head;}// 双向循环列表的尾删
Doublelink delete_tail(Doublelink head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.判断链表节点是否为1else if(head->next==head){free(head);  // 释放头结点head=NULL;  // head指向空return head;}// 3.链表有多个节点else{head->last=head->last->last;  // 让头结点的last指向倒数第二个节点free(head->last->next);  // 释放最后一个节点head->last->next=head;  // 让原倒数第二个节点指向头结点，即成为最后一个节点return head;}}

  3.4 输出效果