数据结构与算法(4)-单向循环链表

1. 单向循环链表

单向循环链表就是一个单链表，然后最后一个节点的后继指向第一个节点。
图例：

单向循环链表.png

2. 单向循环链表的实现

2.1 链表节点设计和辅助信息

上代码：

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

2.2 单向循环链表的创建

由于我们没有使用带头结点的链表，所以链表的初始化操作需要判断是新建还是已经存在。此处采用的是带值的初始化，即链表初始化事会存在一些值，当然不存在也可以。此处是初始化一个链表，初始的数据使用尾插法进行添加。尾插法的具体实现可参考我的其他博客。
代码实现：(使用需循环遍历的方法查找尾节点)

/// 创建一个单向循环链表
/// @param L 链表
Status CreateLinkList(LinkList *L){

    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) { break; }
        if (*L == NULL) {//刚初始化没有节点
            // 初始化
            *L = (LinkList)malloc(sizeof(Node));
            if(!(*L)) return ERROR;
            // 赋值
            (*L)->data = item;
            // 指向自己
            (*L)->next = (*L);
        } else {
            // 使用尾插法，遍历寻找到最后一个节点
            for (target = *L; target->next!=*L; target=target->next);
            // 初始化新节点
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return ERROR;
            // 赋值
            temp->data = item;
            // 新节点的指针指向原来尾节点的next即*L(首元节点)
            temp->next = target->next;
            // 原来的尾节点指向新节点
            target->next = temp;
        }
    }

    return OK;
}

由于使用循环遍历的方法查找尾节点会增加时间复杂度，下面我们通过增加一个辅助节点来记录尾节点的方法来减少时间复杂度。
代码实现：（使用辅助节点记录尾节点来实现）

/// 创建一个单向循环链表
/// @param L 链表
Status CreateLinkList2(LinkList *L){

    int item;
    LinkList temp = NULL;
    LinkList end = NULL;//记录尾节点
    printf("输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) { break; }
        if (*L == NULL) {//刚初始化没有节点
            // 初始化
            *L = (LinkList)malloc(sizeof(Node));
            if(!(*L)) return ERROR;
            // 赋值
            (*L)->data = item;
            // 指向自己
            (*L)->next = (*L);
            // 记录尾节点
            end = *L;
        } else {
            // 初始化新节点
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp)  return ERROR;
            // 赋值
            temp->data = item;
            // 新节点的指针指向原来尾节点的next即*L(首元节点)
            temp->next = end->next;
            // 原来的尾节点指向新节点
            end->next = temp;
            // 记录新的尾节点
            end = temp;
        }
    }

    return OK;
}

2.3 打印单向循环链表

实现代码：

void printLinkList(LinkList L) {
    if (L == NULL) {
        printf("链表为空\n");
        return;
    }
    LinkList p = L;
    int i = 1;
    
    do {
        printf("第%d个节点的值是%d\n",i,p->data);
        i++;
        p = p->next;
    } while (p != L);
}

2.4 在链表的指定位置插入数据

插入不同于初始化，是链表已经存在了才会进行插入（但是这里对未初始化进行了判断）。由于插入的位置不同需要作出相应的判断，（在位置合法的前提下）当插入的位置为第一个节点时需要：

  • 1.修改头结点为新节点

  • 2.修改尾节点的后继


    插入位置为第一个.png

当插入位置为其他位置时只需：

  • 1.找到待插入位置的前一个节点
  • 2.前一个节点的next赋值给新节点的next

  • 3.前一个节点的next指向新节点


    插入到其他位置.png

实现代码：

/// 指定位置插入新节点
/// @param L 链表
/// @param location 位置
/// @param e 数据
Status InsertLinkList(LinkList *L, int location, ElemType e){
    
    LinkList p, temp, end;
    
    if (*L == NULL) {// 如果没节点则初始化第一个节点
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->data = e;
        (*L)->next = *L;
    } else {
        // 位置不合法
        if (location<1) { return ERROR; }
        if (location == 1) {// 插入到第一个位置
            // 初始化新节点
            temp = (LinkList)malloc(sizeof(Node));
            if (temp == NULL) { return ERROR; }
            // 找到尾节点
            for (end=*L; end->next!=*L; end = end->next);
            // 赋值
            temp->data = e;
            // 新节点的next指向*L
            temp->next = *L;
            // 尾节点的next指向新节点
            end->next = temp;
            // 第一个节点修改为temp
            *L = temp;
        } else {
            
            p = *L;
            // 查找待插入位置的前一个节点
            for (int i = 2; i<location; i++) {
                // 下一个节点
                p=p->next;
                // 位置不合法,已经找到头结点了还没找到要插入的位置
                if (p==*L) { return ERROR;}
            }
            
            // 初始化新节点
            temp = (LinkList)malloc(sizeof(Node));
            if (temp == NULL) { return ERROR; }
            // 赋值
            temp->data = e;
            // 新节点的next指向前一个节点的next即：要插入位置的节点
            temp->next = p->next;
            // 前一个节点的next指向新节点
            p->next = temp;
        }
    }
    
    return OK;;
}

2.4 删除指定位置的数据

删除指定位置的数据跟插入有些类似，都是要区分删除的位置是不是第一个，（在链表不为空并且位置合法的前提下）当删除的位置为第一个的时候则需要：

  • 1.判断是否只剩一个元素，是的话直接置空链表
  • 2.剩余元素大于一个，首先找到尾节点
  • 3.尾节点的next指向原首元节点的next
  • 4.更新第一个节点为原首元节点的next

  • 5.释放被删除节点的内存


    删除首元节点.png

当被删除的节点不是第一个的时候则需要：

  • 1.找到待删除节点的前一个节点，如果遍历一遍还是找不到就返回错误
  • 2.找到后存储待删除节点
  • 3.将前一个节点的next指向待删除节点的next

  • 4.释放待删除节点的内存


    删除其他节点.png
/// 删除指定位置的节点
/// @param L 链表
/// @param location 位置
/// @param e 返回被删除元素的值
Status DeleteLinkList(LinkList *L, int location, ElemType *e) {
    // 为NULL则报错
    if (*L == NULL) { return ERROR; }
    // 位置不合法
    if (location<1) { return ERROR; }
    // 辅助变量
    LinkList p, end, temp;
    
    if (location == 1) {
        // 第一个节点
        temp = *L;
        if (temp->next == (*L)) { //如果只剩一个节点
            *e = temp->data;
            free(temp);
            *L = NULL;
        } else {
            // 找到尾节点
            for (end = *L; end->next!=*L; end = end->next);
            // 尾节点的next指向第一个节点的next
            end->next = temp->next;
            // 更新第一个节点
            *L = temp->next;
            // 返回删除节点的值
            *e = temp->data;
            // 释放删除节点的内存
            free(temp);
        }
    } else {
        // 首元节点
        p = *L;
        // 找到待删除节点的前一个节点
        for (int i = 2; i<location; i++) {
            // 一直寻找
            p = p->next;
            // 循环一遍了还没找到要删除的位置
            if (p == *L) { return ERROR; }
        }
        // 记录待删除节点
        temp = p->next;
        // 前一个节点的next指向待删除节点的next
        p->next = temp->next;
        // 返回删除节点的值
        *e = temp->data;
        // 释放删除节点的内存
        free(temp);
    }
    
    return OK;
}

2.5 查找指定位置的值

因为链表的位置是不固定的存储单元，这里的位置指的是从头结点开始的位置，从1开始计算。在位置和链表合法的前提下，通过循环遍历查找指定位置的值。条件是：

  • 1.找到最后一个节点，即节点的next指向首元节点
  • 2.查找的位置大于等于输入的位置

查找完毕后需要做判断，如果查找到的节点是最后一个结点，并且位置不匹配则返回-1。

代码实现：

/// 根据指定位置查找值
/// @param L 链表
/// @param location 位置
int GetValueForLinkList(LinkList L, int location){
    // 空值判断
    if (L==NULL) { return -1; }
    // 位置判断
    if (location<1) { return -1; }
    // 辅助变量
    LinkList p = L;
    int i;
    // 循环查找
    for (i = 1; i<location && p->next != L; i++) {
        p=p->next;
    }
    // 如果找到了最后一个节点，并且位置不匹配，说明查找了一圈了，没找到
    if (p->next == L && i != location) {
        return -1;
    }
    
    // 返回查找到的值
    return p->data;
}

2.6 查找某个值得位置

因为链表的位置是不固定的存储单元，这里的位置指的是从头结点开始的位置，从1开始计算。在位置和链表合法的前提下，通过循环遍历查找指定值的位置。条件是：

  • 1.数据域的值匹配
  • 2.找到最后一个节点：即其next指向头结点

查找完毕后需要做判断，如果查找到的节点的next指向头结点，并且值不匹配则返回-1。

代码实现：

/// 查找值的位置
/// @param L 链表
/// @param e 值
int GetLocationForLinkList(LinkList L, ElemType e){
    // 空值判断
    if (L==NULL) { return -1; }
    // 辅助变量
    LinkList p = L;
    int i = 1;
    // 循环查找
    while (p->data != e && p->next != L) {
        p=p->next;
        i++;
    }
    // 如果该节点的next指向头节点，但是内容不匹配，说明没找到，返回-1
    if (p->next == L && p->data != e) {
        return -1;
    }
    
    return i;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,012评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,628评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,653评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,485评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,574评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,590评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,596评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,340评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,794评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,102评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,276评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,940评论 5赞 339
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,583评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,201评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,441评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,173评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,136评论 2赞 352

推荐阅读更多精彩内容