数据结构与算法——线性表3

线性表——单向循环链表

3、单向循环链表

在单向链表的基础上，单向链表的尾结点的Next指向链表的头部，就是为循环列表。如下图所示

单向循环链表的一系列操作
3.1单向循环链表的初始化

Status CreateList(LinkList *L){
    if (*L==NULL) {
        //创建,创建首元结点
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->data = -1;
        //结点的next指向自身
        (*L)->next = *L;
    }
    return OK;
}

3.2单向循环链表插入

Status InsertLinkList(LinkList *L,int i ,int e){
    if (*L==NULL) {
        return ERROR;
    }
    LinkList p,temp,p2;
    p = NULL;
    temp =*L;
    //初始化的时候有一个首元结点，开始计数为1
    int sum = 1;
    //统计个数
    for (temp =*L ; temp->next!=*L; temp=temp->next) {
        sum++;
    }
    if (sum<i || i == 0) {
        printf("位置不存在\n");
    }else{
            //指向L
            p2 = *L;
            //循环遍历到下表为i-1
            for (int j = 1; j< i; j++) {
                p2=p2->next;
            }
            LinkList target;
            target = (LinkList)malloc(sizeof(Node));
            target ->data = e;
            target->next = p2->next;
            p2->next = target;
    }
    return OK;
}

3.3单向循环链表遍历

Status TraveLinkList(LinkList L){
    if (L==NULL) {
        printf("链表为空\n");
    }else{
        LinkList temp;
        temp = L->next;
        do {
            printf("%d ",temp->data);
            temp = temp->next;
        } while (temp!=L);
    }
    return OK;
}

3.4删除其中一个数据

Status DeleteLinkList(LinkList *L,int place){
    LinkList temp;
    if ((*L) == NULL) {
        printf("链表为空");
    }else{
            LinkList target;
            int i = 1;
            int sum = 0;
          //统计个数，首元结点只是个辅助作用
          for (temp =*L ; temp->next!=*L; temp=temp->next) {
              sum++;
          }
        if (place>sum) {
            printf("越界\n");
            return ERROR;
        }
        for (target = *L, i = 1; target->next!=*L && i<place; i++,target = target->next);
        temp  = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}

完整代码如下

//
//  main.c
//  循环链表
//
//  Created by mac on 2020/4/8.
//  Copyright © 2020 mac. All rights reserved.
//

#include <stdio.h>
#include "stdlib.h"

#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;
//4.1循环列表的初始化
Status CreateList(LinkList *L){
    if (*L==NULL) {
        //创建,创建首元结点
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->data = -1;
        //结点的next指向自身
        (*L)->next = *L;
    }
    return OK;
}
//4.2遍历循环列表
Status TraveLinkList(LinkList L){
    if (L==NULL) {
        printf("链表为空\n");
    }else{
        LinkList temp;
        temp = L->next;
        do {
            printf("%d ",temp->data);
            temp = temp->next;
        } while (temp!=L);
    }
    return OK;
}
//4.3插入数据
Status InsertLinkList(LinkList *L,int i ,int e){
    if (*L==NULL) {
        return ERROR;
    }
    LinkList p,temp,p2;
    p = NULL;
    temp =*L;
    //初始化的时候有一个首元结点，开始计数为1
    int sum = 1;
    //统计个数
    for (temp =*L ; temp->next!=*L; temp=temp->next) {
        sum++;
    }
    if (sum<i || i == 0) {
        printf("位置不存在\n");
    }else{
            //指向L
            p2 = *L;
            //循环遍历到下表为i-1
            for (int j = 1; j< i; j++) {
                p2=p2->next;
            }
            LinkList target;
            target = (LinkList)malloc(sizeof(Node));
            target ->data = e;
            target->next = p2->next;
            p2->next = target;
    }
    return OK;
}
//4.4删除其中一个数据
Status DeleteLinkList(LinkList *L,int place){
    LinkList temp;
    if ((*L) == NULL) {
        printf("链表为空");
    }else{
            LinkList target;
            int i = 1;
            int sum = 0;
          //统计个数，首元结点只是个辅助作用
          for (temp =*L ; temp->next!=*L; temp=temp->next) {
              sum++;
          }
        if (place>sum) {
            printf("越界\n");
            return ERROR;
        }
        for (target = *L, i = 1; target->next!=*L && i<place; i++,target = target->next);
        temp  = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}
int main(int argc, const char * argv[]) {
    // insert code here...
//    printf("Hello, World!\n");
    printf("循环列表\n");
    LinkList L;
    printf("列表是否创建成功---%d!\n",CreateList(&L));
    printf("循环链表添加数据\n");
    for (int i = 1; i < 10; i++) {
        InsertLinkList(&L, i, i);
    }
    TraveLinkList(L);
    printf("\n");
    //4.4删除元素
    printf("循环链表删除元素\n");
    DeleteLinkList(&L, 10);
    TraveLinkList(L);
    printf("\n");
    return 0;
}

代码自己写的，有不对的地方欢迎指出。