数据结构与算法（二）：单向循环链表的实现

单向循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表.

单向循环链表.png

1.单向循环链表的创建

#define ERROR 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;

Status CreatLinkList(LinkList *L){
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    
    printf("输入结点的值,输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) return ERROR;
        if (*L==NULL) { // 如果链表为空 则创建一个新的结点
            *L = (LinkList)malloc(sizeof(Node));
            if (!L) exit(0); // 没有创建成功
            (*L)->data = item;
            (*L)->next = *L;
        }else{
            // 输入的链表不为空 寻找链表的尾结点 尾结点的next->新结点 新结点的next->head(首元结点)
            for (target = *L; target->next != *L; target = target->next);// 遍历查找到尾结点
            temp = (LinkList)malloc(sizeof(Node));// 创建新结点
            if (!temp) return ERROR;
            
            temp->data = item;
            temp->next = *L;//指向首元结点
            target->next = temp; // 遍历出的尾结点指向新增的结点
        }
    }
    return OK;
}

//4.2 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
void show(LinkList p)
{
    //如果链表是空
    if(p == NULL){
        printf("打印的链表为空!\n");
        return;
        
    }else{
        LinkList temp;
        temp = p;
        do{
            printf("%5d",temp->data);
            temp = temp->next;
        }while (temp != p);
        printf("\n");
    }
    
}

// 循环链表插入数据
Status LinkListInsert(LinkList *L,int place,int value){
    return OK;
}
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        printf("hello,world");
        printf("\n");
        LinkList head;
        int place,num;
        int iStatus;
        
        iStatus = CreatLinkList(&head);
        show(head);
    }
    return 0;
}

输出结果

链表创建成功.png

1.单向循环链表的插入

// 循环链表插入数据
Status LinkListInsert(LinkList *L,int place,int value){
    LinkList temp,target;
    int i;
    
    if (place < 1) {
        printf("输入的位置不合法");
        return ERROR;
    }
    if (place == 1) { // 插入第一个位置（首元结点）所以尾结点的指向有变动 所以比较特殊
         //1.创建新结点
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->data = value;
        //2.找到尾结点
        for(target = *L;target->next != *L;target = target->next);
        //3.新结点指向头结点
        temp->next = *L;
        //3.尾结点指向新的头结点
        target->next = temp;
        //4.头结点指向新的结点
        *L = temp;
        
    }else{ // 插入的位置不在首元结点的时候 ,这里需要注意插入在尾结点时候和其他的位置处理的逻辑是一样的。 尾结点也是有指向(首元结点)的
        // 1.创建新结点
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->data = value;
        
        // 2.查找到需要插入的位置:前驱结点(place-1)
        for(i = 1,target = *L;target->next != *L&& i != place-1;target->next = target,i++);//遍历不断给target赋值 直到找到目标i结点
        
        //3.没有找到这个结点的位置 直接插入到尾结点
     
        
        //4.新插入结点next指向目标结点(前驱结点)指向的结点的next
        temp->next = target->next;
        
        //5.前驱结点的next再指向再新创建的结点
        target->next = temp;
        #warning ⚠️ 3和4的顺序不能颠倒
    }
    
    return OK;
}

输出结果

单向循环链表的插入.png

单向循环链表的插入一定要处理好插入位置的情况,插入到首元结点和其他结点处理的方式不一样

2.单向循环链表的元素删除

Status LinklistDelete(LinkList *L,int place){
    
    LinkList temp,target;
    int i;
    
    temp = *L;
    if (temp == NULL) return ERROR;
    if (place == 1) {
        // 如果链表中只有一个结点了 则直接清空链表
        if ((*L)->next == (*L)) {
            *L = NULL;
            return OK;
        }
        
        // 如果链表中的元素>1 删除的是首元结点
        // 1.查找尾结点 使尾结点next指向首元结点的next指向的结点 target->next = (*L)->next
        for (target = *L; target->next != *L; target = target->next);
        temp = *L; // 用一个临时变量保存头结点
        
        //2.新节点作为头结点
        *L = (*L)->next;
        target->next = *L;
        
        //3.释放原来的头结点 才算彻底删除该元素
        free(temp);
    }else{
        
        // 删除的不是首元结点
        
        //1.找到要删除结点的前驱结点 target
        for (i = 1,target = *L; target->next != *L && i!=place-1; target = target->next);
        
        //2.用临时变量temp保存要删除的结点即 target->next,因为最后要释放该结点
        temp = target->next;
        
        //3.使target->next 指向 要删除结点的后驱结点
        target->next = temp->next;
        
        //4.释放temp结点
        free(temp);
    }
    
    return OK;
}

单向循环链表删除元素和插入元素一样，需要处理首元结点和非首元结点位置元素的删除操作。

输出结果

单向循环链表元素的删除.png

单向循环链表元素的删除要注意释放删除的元素

3.单向循环链表的查找

单向循环链表查询时需要注意当尾结点指向头结点时,要跳出循环

// 查询链表中元素的data所在的位置
int findValue(LinkList L,int value){
    
    int i = 1;
    LinkList p;
    p = L;
    
    // 查询链表中的结点 data == value
    while (p->data != value && p->next != L) {
        i ++;
        p = p->next;
    }
    
    //当尾结点指向头结点就会跳出循环 所以要判断尾结点的data == value;
    if(p->next == L && p->data != value){
        return -1;
    }
    
    return i;
}

输出结果

单向循环链表的查询.png