【数据结构】 循环单链表的基本操作 (C语言版)

这篇具有很好参考价值的文章主要介绍了【数据结构】 循环单链表的基本操作 (C语言版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、循环单链表

1、循环单链表的定义:

2、循环单链表的优缺点:

二、循环单链表的基本操作算法(C语言)  

 1、宏定义

 2、创建结构体

3、循环单链表的初始化 

4、循环单链表的插入

5、求单链表长度

6、循环单链表的清空

7、循环单链表的销毁

8、循环单链表的取值

9、循环单链表的查找

10、循环单链表的删除

11、头插法创建循环链表

12、尾插法创建循环链表

13、输出链表元素

三、循环单链表的基本操作完整代码(C语言)

四、运行结果


一、循环单链表

1、循环单链表的定义:

循环单链表是一种特殊类型的单链表,其特点是链表的最后一个结点的指针域指向整个链表的第一个结点,从而形成一个环状结构。

这种数据结构可以用来存储有序的数据集合,其插入和删除操作可以在平均时间复杂度O(1)内完成,这是其相比单链表的一大优势。循环单链表的操作一般更复杂,因为需要维护环状的结构,并保证对链表的操作满足时间复杂度的要求。

【数据结构】 循环单链表的基本操作 (C语言版),数据结构,c语言,算法,链表

2、循环单链表的优缺点:

优点:

  1. 循环单链表可以高效地执行插入和删除操作,因为不需要像单链表那样从头或尾部开始遍历整个链表。
  2. 循环单链表的空间利用率较高,因为最后一个结点的指针域指向整个链表的第一个结点,从而避免了浪费空间存储空指针。
  3. 循环单链表适合用于处理有序的数据集合,可以快速地执行查找、插入和删除操作。

缺点:

  1. 循环单链表的操作相对复杂,因为需要维护环状的结构,并保证对链表的操作满足时间复杂度的要求。
  2. 在某些情况下,循环单链表可能比单链表更难以理解和实现。

二、循环单链表的基本操作算法(C语言)  

 1、宏定义
#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;
 2、创建结构体
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
3、循环单链表的初始化 
//循环链表初始化
Status InitList(LinkList &head) {
    head = new LNode;
    //head->next=NULL;
    head->next = head;
    return OK;
}
4、循环单链表的插入
//插入
Status ListInsert(LinkList &head, int i, ElemType e) {
    LinkList p = head;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        return ERROR;
    }

    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}
5、求单链表长度
//求单链表长度
Status GetLinkListLength(LinkList head) {
    LinkList p = head->next;
    int length = 0;
    while (p != head) {   //p!=NULL          //单链表不为空表时
        length++;
        p = p->next;
    }
    return length;
}
6、循环单链表的清空
//清空
Status ClearLinkList(LinkList &head) {
    LinkList p = head->next;
    LinkList q;
    while (p != head) { //p != L  p!=NULL
        q = p;
        p = p->next;
        delete q;
    }
    head->next = head; //链表为空
    return OK;
}
7、循环单链表的销毁
//销毁
Status DestoryLinkList(LinkList &head) {
    LinkList p = head->next;
    LinkList q;
    while (p != head) { //p != L  p!=NULL
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    // printf("\n销毁成功\n");
    return OK;
}
8、循环单链表的取值
//取值
Status GetLinkList(LinkList head, int i, ElemType &e) {
    LinkList p = head->next;
    int j = 1;
    while (p != head && j < i) {  //p != L
        p = p->next;
        j++;
    }
    if (p == head) {//p==L
        return ERROR;
    }
    e = p->data;

    return OK;
}
9、循环单链表的查找
//查找
int LocateLinkListElem(LinkList head, ElemType e) {
    LinkList p = head->next;
    int j = 1;
    while (p != head && (p->data != e)) {//p != L p!=NULL
        p = p->next;
        j++;
    }
    if (p == head) { //p==L  !p<=>p==NULL
        return 0;
    }
    return j;
}
10、循环单链表的删除
//删除
Status ListDelete(LinkList &head, int i, ElemType &e) {
    LinkList p = head;
    int j = 0;
    while (p->next != head && j < i - 1) {  //p != L
        p = p->next;
        j++;
    }
    if (p->next == head) { //p==L
        return ERROR;
    }
    LinkList q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return OK;
}
11、头插法创建循环链表
//头插法创建循环链表
void CreateLinkList_H(LinkList &head, int n) {
    InitList(head);
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        //scanf("%c",&p->data);
        p->data = getche();
        //cin >> p->data;
        p->next = head->next;
        head->next = p;
    }
}
12、尾插法创建循环链表
//尾插法创建循环链表
void CreateLinkList_R(LinkList &head, int n) {
    InitList(head);
    LinkList r = head;
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        //scanf("%c",&p->data);
        p->data = getche();
        //cin >> p->data;
        //p->next=NULL   p->next=head
        //p->next = r->next;
        r->next = p;
        r = p;
    }
    r->next = head;                //尾结点next域指向头结点
}
13、输出链表元素
//输出链表元素
void printLinkList(LinkList head) {
    LinkList p = head->next;
    while (p != head) { //p != L
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

三、循环单链表的基本操作完整代码(C语言)

#include <stdio.h>
#include <conio.h>//getche()
#include <cstdlib>//free()

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

//循环链表初始化
Status InitList(LinkList &head) {
    head = new LNode;
    //head->next=NULL;
    head->next = head;
    return OK;
}

//功能菜单
Status choice() {
    printf("==================================\n");
    printf("         循环链表操作功能菜单        \n");
    printf("1、插入元素  2、查询表长  3、按位查找\n");
    printf("4、按值查找  5、删除元素  6、销毁链表\n");
    printf("7、清空链表  8、批量插入  9、链表元素\n");
    printf("10、头插法创建单链表11、尾插法创建单链表\n");
    printf("==================================\n");
    return 1;
}

//插入
Status ListInsert(LinkList &head, int i, ElemType e) {
    LinkList p = head;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        return ERROR;
    }

    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

//求单链表长度
Status GetLinkListLength(LinkList head) {
    LinkList p = head->next;
    int length = 0;
    while (p != head) {   //p!=NULL          //单链表不为空表时
        length++;
        p = p->next;
    }
    return length;
}


//销毁
Status DestoryLinkList(LinkList &head) {
    LinkList p = head->next;
    LinkList q;
    while (p != head) { //p != L  p!=NULL
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    // printf("\n销毁成功\n");
    return OK;
}


//清空
Status ClearLinkList(LinkList &head) {
    LinkList p = head->next;
    LinkList q;
    while (p != head) { //p != L  p!=NULL
        q = p;
        p = p->next;
        delete q;
    }
    head->next = head; //链表为空
    return OK;
}

//取值
Status GetLinkList(LinkList head, int i, ElemType &e) {
    LinkList p = head->next;
    int j = 1;
    while (p != head && j < i) {  //p != L
        p = p->next;
        j++;
    }
    if (p == head) {//p==L
        return ERROR;
    }
    e = p->data;

    return OK;
}

//查找
int LocateLinkListElem(LinkList head, ElemType e) {
    LinkList p = head->next;
    int j = 1;
    while (p != head && (p->data != e)) {//p != L p!=NULL
        p = p->next;
        j++;
    }
    if (p == head) { //p==L  !p<=>p==NULL
        return 0;
    }
    return j;
}

//删除
Status ListDelete(LinkList &head, int i, ElemType &e) {
    LinkList p = head;
    int j = 0;
    while (p->next != head && j < i - 1) {  //p != L
        p = p->next;
        j++;
    }
    if (p->next == head) { //p==L
        return ERROR;
    }
    LinkList q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return OK;
}

//头插法创建循环链表
void CreateLinkList_H(LinkList &head, int n) {
    InitList(head);
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        //scanf("%c",&p->data);
        p->data = getche();
        //cin >> p->data;
        p->next = head->next;
        head->next = p;
    }
}

//尾插法创建循环链表
void CreateLinkList_R(LinkList &head, int n) {
    InitList(head);
    LinkList r = head;
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        //scanf("%c",&p->data);
        p->data = getche();
        //cin >> p->data;
        //p->next=NULL   p->next=head
        //p->next = r->next;
        r->next = p;
        r = p;
    }
    r->next = head;                //尾结点next域指向头结点
}

//输出链表元素
void printLinkList(LinkList head) {
    LinkList p = head->next;
    while (p != head) { //p != L
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {

    LinkList list;

    //初始化
    printf("单链表正在初始化....\n");
    int InitStatus = InitList(list);
    if (InitStatus == OK) {
        printf("单链表初始化成功!\n");
    } else {
        printf("单链表初始化失败!\n");
    }

    choice();    //调用功能菜单函数
    int temp = 1;  //通过改变temp的值来跳出while循环

    while (temp) {
        int flag;
        printf("请输入所需的功能编号:\n");
        scanf("%d", &flag);

        switch (flag) {//通过开关进行功能选择
            case 1: {//插入元素
                int insertIndex;
                ElemType inserElem;
                printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
                scanf("%d,%c", &insertIndex, &inserElem);
                Status InsertS = ListInsert(list, insertIndex, inserElem);
                if (InsertS == OK) {
                    printf("向循环链表%d个位置,插入元素为%c成功!\n\n", insertIndex, inserElem);
                } else {
                    printf("向循环链表插入元素失败!\n\n");
                }
            }
                break;
            case 2: {//求单链表的长度
                int length = GetLinkListLength(list);
                printf("循环链表的长度为:%d。 \n\n", length);
            }
                break;
            case 3: {//取值
                Status GetIndex;
                printf("请输入需要查询的元素的位置:\n");
                scanf("%d", &GetIndex);
                ElemType GetElem;
                int GetStatus = GetLinkList(list, GetIndex, GetElem);
                if (GetStatus == OK) {
                    printf("从循环链表中获取第%d位置元素成功,所获取到的元素为:%c。\n\n", GetIndex, GetElem);
                } else {
                    printf("从循环链表中获取第%d位置元素失败!\n\n", GetIndex);
                }
            }
                break;
            case 4: {//查找
                ElemType LocateElem;
                printf("请输入想要查找元素:\n");
                getchar();    //用于接收回车
                scanf("%c", &LocateElem);
                Status LocateIndex = LocateLinkListElem(list, LocateElem);
                if (LocateIndex > 0) {
                    printf("从循环链表中查找元素%c成功,它在循环链表中的位置为第%d个!\n\n", LocateElem, LocateIndex);
                } else {
                    printf("从循环链表中查找元素%c失败!\n\n", LocateElem);
                }
            }
                break;
            case 5: {//删除
                Status DeleteIndex;
                printf("请输入想要删除元素的位置:\n");
                scanf("%d", &DeleteIndex);
                ElemType DeleteElem;
                ElemType DeleteStatus = ListDelete(list, DeleteIndex, DeleteElem);
                if (DeleteStatus == OK) {
                    printf("删除循环链表第%d个位置的元素成功,删除的元素为:%c。\n\n", DeleteIndex, DeleteElem);
                } else {
                    printf("删除循环链表第%d个位置的元素失败!\n\n", DeleteIndex);
                }
            }
                break;
            case 6: {//销毁
                Status DestoryStatus = DestoryLinkList(list);
                if (DestoryStatus == OK) {
                    printf("循环链表销毁成功!\n\n");
                } else {
                    printf("循环链表销毁失败!\n\n");
                }
            }
                break;
            case 7: {//清空
                Status ClearStatus = ClearLinkList(list);
                if (ClearStatus == OK) {
                    printf("循环链表清空成功!\n\n");
                } else {
                    printf("循环链表清空失败!\n\n");
                }
            }
                break;
            case 8: {//批量插入
                int on;
                printf("请输入想要插入的元素个数:\n");
                scanf("%d", &on);
                ElemType array[on];
                for (int i = 1; i <= on; i++) {
                    getchar();
                    printf("向循环链表第%d个位置插入元素为:", (i));
                    scanf("%c", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status InsertStatus = ListInsert(list, i, array[i]);
                    if (InsertStatus == OK) {
                        printf("向循环链表第%d个位置插入元素%c成功!\n", i, array[i]);
                    } else {
                        printf("向循环链表第%d个位置插入元素%c失败!\n", i, array[i]);
                    }
                }
            }
                break;
            case 9: {//输出链表元素
                //temp=0;
                //return 0;
                printf("现在链表的元素为:");
                printLinkList(list);
            }
                break;
            case 10: {//头插法创建单链表
                //getchar();
                LinkList L;
                printf("请输入五个字符:\n");
                CreateLinkList_H(L, 5);
                int length = GetLinkListLength(L);
                printf("\n循环链表的长度为:%d。 \n", length);
                printf("循环链表的元素为:");
                printLinkList(L);
                printf("\n");
            }
                break;
            case 11: {//尾插法创建单链表
                LinkList L;
                printf("请输入五个字符:\n");
                CreateLinkList_R(L, 5);
                int length = GetLinkListLength(L);
                printf("\n循环链表的长度为:%d。 \n", length);
                printf("循环链表的元素为:");
                printLinkList(L);
                printf("\n");
            }
                break;
            default:
                printf("输入错误,无此功能,请检查输入:\n\n");
        }
    }

}

四、运行结果

【数据结构】 循环单链表的基本操作 (C语言版),数据结构,c语言,算法,链表 

【数据结构】 循环单链表的基本操作 (C语言版),数据结构,c语言,算法,链表 

【数据结构】 循环单链表的基本操作 (C语言版),数据结构,c语言,算法,链表 

【数据结构】 循环单链表的基本操作 (C语言版),数据结构,c语言,算法,链表 文章来源地址https://www.toymoban.com/news/detail-815351.html

到了这里,关于【数据结构】 循环单链表的基本操作 (C语言版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】 循环双链表的基本操作 (C语言版)

    目录 一、循环双链表 1、循环双链表的定义: 2、循环双链表的优缺点: 二、循环双链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(58)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(57)
  • 数据结构——单链表基本操作实现 (c++)

    单链表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这里存储单元可以是连续的,也可以是不连续的),为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系,除了存储信息本身外还要存储一个指示其直接后继的信息(地址). 这两部分信

    2024年02月03日
    浏览(67)
  • 【数据结构】单链表基本操作:查找、插入、删除、创建

     链表由结点组成,结点由数据域和指针域组成。其中,数据域存放的就是数据元素,指针域存放下一个结点的地址。数据元素可以只有一个,也可以有多个不同类型的数据元素,甚至是数组。下图和代码来自《C Primer Plus》,该链表每个节结点同时含char类型和int类型。 ​​

    2024年02月02日
    浏览(63)
  • 数据结构——单链表上基本操作的实现

    1.按位序插入(带头结点) : ==ListInsert(L, i, e): ==在表L 中的第 i 个位置上插入指定元素 e = 找到第 i-1 个结点 ( 前驱结点 ) ,将新结点 插入其后;其中头结点可以看作第 0 个结点,故 i=1 时也适用。 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; // 在第 i 个位置插入

    2024年01月21日
    浏览(57)
  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 数据结构 2.1 线性表的定义和基本操作

    数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构) 线性表是具有 相同数据类型 的n(n=0)个数据元素的 有限序列 ,其中n为表长,当n=0时,线性表是一个空表。 每个数据元素所占空间一样大,有次序。 几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

    2024年02月07日
    浏览(53)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(62)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包