單向循環(huán)鏈表和單向鏈表差不多，只不過是最后的尾節(jié)點(diǎn)指向的不是空，而是指向頭節(jié)點(diǎn)。理解這一點(diǎn)很重要，因?yàn)檫@是我們寫程序的關(guān)鍵

image.png

下面用代碼實(shí)現(xiàn)以下，不帶頭節(jié)點(diǎn)的

1.創(chuàng)建

準(zhǔn)備條件：定義節(jié)點(diǎn)，狀態(tài)

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

#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

//定義結(jié)點(diǎn)
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

分為2種情況:① 第一次開始創(chuàng)建; ②已經(jīng)創(chuàng)建,往里面新增數(shù)據(jù)

注意：這里使用尾插法實(shí)現(xiàn)的，更符合邏輯，也可以用頭插發(fā)實(shí)現(xiàn)

/*
判斷是否第一次創(chuàng)建鏈表
    YES->創(chuàng)建一個(gè)新結(jié)點(diǎn),并使得新結(jié)點(diǎn)的next 指向自身; (*L)->next = (*L);
    NO-> 找鏈表尾結(jié)點(diǎn),將尾結(jié)點(diǎn)的next = 新結(jié)點(diǎn). 新結(jié)點(diǎn)的next = (*L);
 */
Status CreateList(LinkList *L){

    int item;
    LinkList temp = NULL;//創(chuàng)建的新節(jié)點(diǎn)
    LinkList target = NULL;//尾結(jié)點(diǎn)
    printf("輸入節(jié)點(diǎn)的值，輸入0結(jié)束\n");
    while(1)
    {
        scanf("%d",&item);
        if(item==0) break;

          //如果輸入的鏈表是空。則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，使其next指針指向自己  (*head)->next=*head;
        if(*L==NULL)
        {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        }
        else
        {
           //輸入的鏈表不是空的，尋找鏈表的尾節(jié)點(diǎn)，使尾節(jié)點(diǎn)的next=新節(jié)點(diǎn)。新節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)

            for (target = *L; target->next != *L; target = target->next);

            temp=(LinkList)malloc(sizeof(Node));

            if(!temp) return ERROR;

            temp->data=item;
            temp->next=*L;  //新節(jié)點(diǎn)指向頭節(jié)點(diǎn)
            target->next=temp;//尾節(jié)點(diǎn)指向新節(jié)點(diǎn)
            /// ??加上這一行就成了頭插法
            //*L = temp; 
        }
    }

    return OK;
}

這里尋找尾結(jié)點(diǎn)用了一個(gè)for循環(huán)，我們可以在每次新增節(jié)點(diǎn)是，用一個(gè)變量記錄尾結(jié)點(diǎn)的位置

Status CreateList2(LinkList *L){

    int item;
    LinkList temp = NULL;//新加的node
    LinkList r = NULL;//記錄尾結(jié)點(diǎn)
    printf("請輸入新的結(jié)點(diǎn), 當(dāng)輸入0時(shí)結(jié)束: ");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }

        //第一次創(chuàng)建
        if(NULL == *L){

            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            r = *L;//記錄尾結(jié)點(diǎn)
        }else{

            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            //尾結(jié)點(diǎn)的指針域指向新創(chuàng)建的節(jié)點(diǎn)
            r->next = temp;
            //更新尾結(jié)點(diǎn)
            r = temp;
            ///??注釋上一行r = temp;，打開這一行成頭插法
            //*L = temp;//頭插法
        }

    }

    return OK;
}

image.png

2.遍歷

遍歷循環(huán)鏈表，循環(huán)鏈表的遍歷最好用do while語句，因?yàn)轭^節(jié)點(diǎn)就有值

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");
    }

}

3.插入

插入分為2種情況，在首元結(jié)點(diǎn)插入和非首元結(jié)點(diǎn)插入，因?yàn)槭自Y(jié)點(diǎn)插入要處理頭指針

Status ListInsert(LinkList *L, int place, int num){

    if (place < 1 || place > getLength(*L)) {
        printf("位置不合法");
        return ERROR;
    }

    //temp是要插入的新節(jié)點(diǎn)，
    LinkList temp ,target;
    int i;
    if (place == 1) {
        //target是尾結(jié)點(diǎn)

        //如果插入的位置為1,則屬于插入首元結(jié)點(diǎn),所以需要特殊處理
        //1\. 創(chuàng)建新結(jié)點(diǎn)temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
        //2\. 找到鏈表最后的結(jié)點(diǎn)_尾結(jié)點(diǎn),
        //3\. 讓新結(jié)點(diǎn)的next 指向首元結(jié)點(diǎn).
        //4\. 尾結(jié)點(diǎn)的next 指向新的首元結(jié)點(diǎn);
        //5\. 讓頭指針指向temp(臨時(shí)的新結(jié)點(diǎn))

        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        //尋找尾結(jié)點(diǎn) target
        for (target = *L; target->next != *L; target = target->next);

        temp->next = *L;
        target->next = temp;
        *L = temp;

    }else
    {

        //target是插入位置的前一個(gè)結(jié)點(diǎn)

        //如果插入的位置在其他位置;
        //1\. 創(chuàng)建新結(jié)點(diǎn)temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
        //2\. 先找到插入的位置,如果超過鏈表長度,則自動(dòng)插入隊(duì)尾;
        //3\. 通過target找到要插入位置的前一個(gè)結(jié)點(diǎn), 讓target->next = temp;
        //4\. 插入結(jié)點(diǎn)的前驅(qū)指向新結(jié)點(diǎn),新結(jié)點(diǎn)的next 指向target原來的next位置 ;

        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        //尋找插入位置的前一個(gè)結(jié)點(diǎn) target
        for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
        //先鏈后斷
        temp->next = target->next;
        target->next = temp;
    }

    return OK;
}

首元節(jié)點(diǎn)位置插入

image.png

非首元節(jié)點(diǎn)位置插入

image.png

4.刪除

刪除和插入一樣，也分為2種情況，在首元結(jié)點(diǎn)刪除和非首元結(jié)點(diǎn)刪除，因?yàn)槭自Y(jié)點(diǎn)要處理頭指針

Status  LinkListDelete(LinkList *L,int place){

    if (place < 1 || place > getLength(*L)) {
        printf("位置不合法");
        return ERROR;
    }

    LinkList temp,target;
    int i;
    //temp 指向鏈表首元結(jié)點(diǎn)
    temp = *L;
    if(temp == NULL) return ERROR;

    if (place == 1) {

        //①.如果刪除到只剩下首元結(jié)點(diǎn)了,則直接將*L置空;
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }

        //②.鏈表還有很多數(shù)據(jù),但是刪除的是首結(jié)點(diǎn);
        //1\. 找到尾結(jié)點(diǎn), 使得尾結(jié)點(diǎn)next 指向首元結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) target->next = (*L)->next;
        //2\. 新結(jié)點(diǎn)做為首元結(jié)點(diǎn),則釋放原來的首元結(jié)點(diǎn)

        for (target = *L; target->next != *L; target = target->next);
        //記錄首元結(jié)點(diǎn)，即要?jiǎng)h除的節(jié)點(diǎn)
        temp = *L;
        //有指針后移一位
        *L = (*L)->next;
        //尾結(jié)點(diǎn)指向頭指針
        target->next = *L;
        free(temp);
    }else
    {

        //如果刪除其他結(jié)點(diǎn)--其他結(jié)點(diǎn)
        //1\. 找到刪除結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)target
        //2\. 使得target->next 指向下一個(gè)結(jié)點(diǎn)
        //3\. 釋放需要?jiǎng)h除的結(jié)點(diǎn)temp
        for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++);

        temp = target->next;
        target->next = temp->next;
        free(temp);
    }

    return OK;

}

5.查詢

int findValue(LinkList L,int value){

    int i = 1;
    LinkList p;
    p = L;

    //尋找鏈表中的結(jié)點(diǎn) data == value
    while (p->data != value && p->next != L) {
        i++;
        p = p->next;
    }

    //當(dāng)尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)就會(huì)直接跳出循環(huán),所以要額外增加一次判斷尾結(jié)點(diǎn)的data == value;
    if (p->next == L && p->data != value) {
        return  -1;
    }

    return i;

}

6.判斷鏈表是否為空

Status isEmpty(LinkList L)
{
    if (NULL == L)
        return 1;
    if (L->next == L)
        return 1;
    else
        return 0;
}

7.計(jì)算鏈表長度

int getLength(LinkList L)
{
    int length = 1;
    LinkList pt = L->next;

    while (pt != L)
    {
        length++;
        pt = pt->next;
    }
    return length;
}

8.刪除整個(gè)鏈表，釋放內(nèi)存

void FreeList(LinkList *L)
{
    LinkList pt = NULL;

    while (*L != NULL)
    {
        //如果只有頭節(jié)點(diǎn)一個(gè)
        if (*L == (*L)->next) {
            free(*L);
            *L = NULL;
        }
        else                    //如果不止頭節(jié)點(diǎn)一個(gè)
        {
            pt = (*L)->next->next;
            free((*L)->next);
            (*L)->next = pt;
        }
    }
}