【数据结构】——循环链表 – 此乃刘同学-记录生活

速通回忆

如果你之前学过链表，可以直接看我下面的这个项目，实现了下面专题中所有内容；

如果你是个新手，建议先不要看下面这个项目，先好好看一下下面每一个部分的代码思路，并尝试自己去写一下

/* 
 * 功能：单向循环链表操作 
 * 作者：此乃刘同学（www.liustu.com.cn）
 */
 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

/* 学生信息结构体 */
typedef struct{
    char name[20];
    int age;
} stu_demo;

/* 单循环链表结构体 */
typedef struct stu_l{
    stu_demo studemo;
    struct stu_l *next;
}stu_link;

/* 初始化单循环链表 */
stu_link *LinkListInit(){
    /* 动态分配存储空间 */
    stu_link *temp = (stu_link*)malloc(sizeof(stu_link)) ;
    if(temp == NULL){
        /* 如果分配空间失败 */
        printf("创建失败\n");
        return NULL;
    }else{
        /* 初始化时指向自己，形成循环 */ 
        temp->next = temp; 
        return temp;
    }
}

/* 循环单链表创建一个数据 */
void LinkLListCreate(stu_link *p){
    stu_link *temp = (stu_link *)malloc(sizeof(stu_link));
    stu_link *point = p;

    printf("（创建）输入创建的学生姓名\n");
    scanf("%s",temp->studemo.name);
    printf("（创建）输入创建的学生年龄\n");
    scanf("%d",&temp->studemo.age);

    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point->next != p)
        point = point->next;
    temp->next = point->next;
    point->next = temp;
}

/* 遍历显示所有节点的数据 */
void LinkListShow(stu_link *p){
    stu_link *point = p->next;
    printf("|\t姓名\t|\t年龄\t|\n");
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        printf("|\t%s\t|\t%d\t|\n",point->studemo.name,point->studemo.age);
        point = point->next;
    }
}

/* 修改对应节点的信息 */
void LinkListInsert(stu_link *p, char *name){
    stu_link *point = p->next;
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        if(strcmp(point->studemo.name, name) == 0){
            printf("（修改）输入要修改的%s同学的年龄:", point->studemo.name);
            scanf("%d", &point->studemo.age);
            return;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

/* 删除某个姓名的节点 */
void LinkListDelete(stu_link *p, char *name){
    stu_link *point = p->next;
    stu_link *prev = p;
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        if(strcmp(point->studemo.name, name) == 0){
            prev->next = point->next;
            free(point);
            printf("删除成功\n");
            return;
        }
        prev = point;
        point = point->next;
    }
    printf("查询无结果\n");
}

int main(){
    /* 将stu初始化，并将stu的next指向自己（头节点） */
    stu_link *stu = LinkListInit();
    /* 添加数据到循环单链表 */
    LinkLListCreate(stu);
    LinkLListCreate(stu);
    /* 遍历输出节点 */
    LinkListShow(stu);
    /* 修改节点信息 */
    LinkListInsert(stu, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu);
    /* 删除节点 */
    LinkListDelete(stu, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu);
    free(stu);
    return 0;
}

循环链表的概念

对于单链表以及双向链表，其就像一个小巷，无论怎么样最终都能从一端走到另一端，然而循环链表则像一个有传送门的小巷，因为循环链表当你以为你走到结尾的时候，其实你又回到了开头

循环链表和非循环链表其实创建的过程以及思路几乎完全一样，唯一不同的是，非循环链表的尾结点指向空（NULL），而循环链表的尾指针指向的是链表的开头

通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）

单向循环链表结点设计

typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据，next指针为指向下一个结点

循环单链表初始化

循环单链表和

//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败，退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}

在主函数重调用可以是这样

    //////////初始化头结点//////////////
    list *head=initlist();
    head->next=head;

循环链表的创建操作

//创建——插入数据
int insert_list(list *head){
    int data;   //插入的数据类型
    printf("请输入要插入的元素：");
    scanf("%d",&data);
  
    list *node=initlist();
    node->data=data;
    //初始化一个新的结点，准备进行链接
  
    if(head!=NULL){
        list *p=head;
        //找到最后一个数据
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("头结点已无元素\n");
        return 0;
    }
  
}

循环单链表的插入操作

//插入元素
list *insert_list(list *head,int pos,int data){
    //三个参数分别是链表，位置，参数
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<pos;i++){
            t=t->next;  //走到需要插入的位置处
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}

循环单链表的删除操作

//删除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("链表为空！\n");
        return 0;
    }
    //建立临时结点存储头结点信息（目的为了找到退出点）
    //如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    list *temp = head;          
    list *ptr = head->next;
  
    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);
  
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { 
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;    //核心删除操作代码
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}

循环单链表的遍历

循环链表需要进行结点的特判，找到尾节点的位置，由于尾节点的next指针是指向头结点的，所以不能使用链表本身是否为空（NULL）的方法进行简单的循环判断，我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断

//遍历元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍历头节点到，最后一个数据
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行 ( o=^•ェ•)o　┏━┓
        //把最后一个节点赋新的节点过去
        return 1;
    } else {
        printf("头结点为空!\n");
        return 0;
    }
}

双向循环链表（升级~变身）

/* 
 * 功能：双向循环链表操作 
 * 作者：此乃刘同学（www.liustu.com.cn）
 */

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

/* 学生信息结构体 */
typedef struct{
    char name[20];
    int age;
} stu_demo;

/* 双向循环链表结构体 */
typedef struct stu_l{
    stu_demo studemo;
    struct stu_l *next;
    struct stu_l *prev;
}stu_link;

/* 初始化双向循环链表 */
stu_link *LinkListInit(){
    /* 动态分配存储空间 */
    stu_link *temp = (stu_link*)malloc(sizeof(stu_link)) ;
    if(temp == NULL){
        /* 如果分配空间失败 */
        printf("创建失败\n");
        return NULL;
    }else{
        /* 初始化时指向自己，形成循环 */ 
        temp->next = temp;
        temp->prev = temp;
        return temp;
    }
}

/* 双向循环链表创建一个数据 */
void LinkLListCreate(stu_link *p){
    stu_link *temp = (stu_link *)malloc(sizeof(stu_link));
    stu_link *point = p;

    printf("（创建）输入创建的学生姓名\n");
    scanf("%s",temp->studemo.name);
    printf("（创建）输入创建的学生年龄\n");
    scanf("%d",&temp->studemo.age);

    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point->next != p)
        point = point->next;
    temp->next = point->next;
    temp->prev = point;
    point->next->prev = temp;
    point->next = temp;
}

/* 遍历显示所有节点的数据 */
void LinkListShow(stu_link *p){
    stu_link *point = p->next;
    printf("|\t姓名\t|\t年龄\t|\n");
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        printf("|\t%s\t|\t%d\t|\n",point->studemo.name,point->studemo.age);
        point = point->next;
    }
}

/* 修改对应节点的信息 */
void LinkListInsert(stu_link *p, char *name){
    stu_link *point = p->next;
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        if(strcmp(point->studemo.name, name) == 0){
            printf("（修改）输入要修改的%s同学的年龄:", point->studemo.name);
            scanf("%d", &point->studemo.age);
            return;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

/* 删除某个姓名的节点 */
void LinkListDelete(stu_link *p, char *name){
    stu_link *point = p->next;
    /* 控制指针指向最后一个节点，最后一个节点的next指向头节点 */
    while(point != p){
        if(strcmp(point->studemo.name, name) == 0){
            point->prev->next = point->next;
            point->next->prev = point->prev;
            free(point);
            printf("删除成功\n");
            return;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

int main(){
    /* 将stu初始化，并将stu的next指向自己（头节点） */
    stu_link *stu = LinkListInit();
    /* 添加数据到循环双向链表 */
    LinkLListCreate(stu);
    LinkLListCreate(stu);
    /* 遍历输出节点 */
    LinkListShow(stu);
    /* 修改节点信息 */
    LinkListInsert(stu, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu);
    /* 删除节点 */
    LinkListDelete(stu, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu);
    free(stu);
    return 0;
}