线性表 - 循环链表

1.引子

单链表解决了从A 查找到E的过程，假设现在要求从E 查找到A,用时最短，
因为单链表是单向的，只能从前往后，无法解决这个问题。因此引出了循环链表。

思路图

将单链表的终端结点的指针由空指针改为头结点，就使整个单链表形成一个环。
这种头尾相接的单链表成为单循环链表，简称循环链表

循环链表和单链表的主要差异就在于循环判断条件上，原来是判断p->next 是否为空，
现在则是p->next 不等于头结点。则循环未结束

2.循环链表的使用

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


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

typedef int Status;
typedef int ElemType;
typedef struct node {
    ElemType data;
    struct node *next;
} Node,*LinkList;


/** 初始化链表 next指向自身*/
void Init_circleList(LinkList *list) {
    (*list) = (LinkList)malloc(sizeof(Node));
    (*list)->next = *list;
}


/** 从1开始 创建n个数据 */
void create_circlrList(LinkList list, int n) {
    LinkList rear, s;
    rear = list;

    for (int i = 1; i <= n; i++) {
        s = (LinkList) malloc(sizeof(Node));
        s->data = I;
        rear->next = s;
        rear = s;
    }
    rear->next = list;
}


/** 获得链表的长度 */
int get_circle_list_Length(LinkList list) {
    LinkList headr = list->next;
    int count =0;
    while (headr != list) {
        headr = headr->next;
        count++;
    }
    return count;
}


/** 在某个位置插入某个元素*/
Status insert_circleList(LinkList list, int i, ElemType e) {
    
    if (i < 0 ) {
        return ERROR;
    }
    
    LinkList headr = list;
    LinkList node = (LinkList)malloc(sizeof(Node));
    node->data = e;
    
    //区分中间插入 or  尾部插入 or 头插
    if (i == 0) {
        node->next = headr->next;
        headr->next = node;
    } else if(i == get_circle_list_Length(list)+1) {
        
        while (headr->next != list) {
            headr = headr->next;
        }
        headr->next = node;
        node->next = list;
        
    } else {
        for (int k = 1; k < i; k++) {
            headr = headr->next;
        }
        node->next = headr->next;
        headr->next = node;
    }
    return OK;
}

/** 删除某一个元素 需要考虑头、尾、中间*/
Status delete_Node_circleList(LinkList list, int kill) {
    LinkList header = list;
    LinkList deleteNodel;
    
    int currentAllCount = get_circle_list_Length(list);
    
    if (kill > currentAllCount) {
        return ERROR;
    }
    if (kill == 0) {
        deleteNodel = header->next;
        header->next = deleteNodel->next;
        free(deleteNodel);
    } else if (kill == currentAllCount) {
        
        for (int i = 1; i < currentAllCount; i++) {
            header = header->next;
        }
        deleteNodel = header->next;
        header->next = deleteNodel->next;
        
        free(deleteNodel);
        
    } else {
        
        for (int i = 1; i < kill; i++) {
            header = header->next;
        }
        deleteNodel = header->next;
        header->next = deleteNodel->next;
        free(deleteNodel);
    }
    return OK;
}


/** 遍历链表*/
void Iteretor_circleList(LinkList list) {
    
    LinkList headr = list->next;
    while (headr != list) {
        printf("+++ current data is %d\n",headr->data);
        headr = headr->next;
    }
}


#pragma mark - 使用
void k_circleNodel(void) {
    LinkList list;
    Init_circleList(&list);
    create_circlrList(list, 10);
    Iteretor_circleList(list);
    
    printf("\n\n");
    insert_circleList(list, 4, 13);
    Iteretor_circleList(list);
    
    printf("\n\n");
    delete_Node_circleList(list, 10);
    Iteretor_circleList(list);
}

3.将两个单链表合并成一个循环链表

两个单链表 合并流程

整个过程需要借助一个指针作为临时变量，并祛除一个的头结点

1.p = rearA -> next;    //保存A的头结点
2.rearA->next = rearB->next-next;
//将本是指向B的第一个结点(不是头结点) 赋值给rearA->next
3.rearB->next = p; //将原A表的头结点赋值给rearB->next
4.free(p);