數(shù)據(jù)結(jié)構(gòu)與算法-C語言8-單循環(huán)列表

數(shù)據(jù)結(jié)構(gòu)與算法-目錄
循環(huán)鏈表是另一種形式的鏈式存貯結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。

對于單個鏈表，由于每個結(jié)點只存儲了向后的指針，到了尾標志就停止了向后鏈的操作，這樣當中某一結(jié)點就無法找到它的前驅(qū)結(jié)點了。

將單鏈表中終端結(jié)點的指針由空指針改為指向頭結(jié)點，就使整個單鏈表形成一個環(huán)， 這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表。

循環(huán)鏈表解決了一個很麻煩的問題，如何從當中一個結(jié)點出發(fā)，訪問到鏈表的全部結(jié)點。

循環(huán)鏈表和單鏈表的主要差異就是在于循環(huán)的判斷條件上，原來是判斷p->next是否為空，現(xiàn)在則是p->next不等于頭結(jié)點，則循環(huán)未結(jié)束。

示例程序

CList.h
//CList.h 
//結(jié)構(gòu)體定義以及函數(shù)聲明


#ifndef CLIST_H
#define CLIST_H

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <iostream>

typedef  int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node, *PNode;

typedef struct List
{
    PNode head;
    PNode tail;
    int size;
}List,*PList;

bool InitList(PList list);
void Create_t(PList list,ElemType x);             //尾插
void Create_h(PList list,ElemType x);             //頭插
void del_back(PList list);                        //尾刪
void del_front(PList list);                       //頭刪
void sortList(PList list);                        //排序
void insert_val(PList list,ElemType x);           //按值插
PNode find(PList list,ElemType x);
void del_val(PList list,ElemType x);
void modify(PList list,ElemType x1,ElemType x2);
void clear(PList list);
void destroy(PList list);
void reserve(PList list);
int length(PList list);
void menu();
void showList(PList list);
void show_tail(PList list);
ElemType next(PList list,ElemType x);
ElemType prio(PList list,ElemType x);
PNode prev(PList list,PNode p);

#endif
CList.cpp
//CList.cpp 
//函數(shù)實現(xiàn)

#include"CList.h"

void menu()           //提供選項的菜單函數(shù)
{
    printf("***************************************************************\n");
    printf("* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *\n");
    printf("* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*\n");
    printf("* [8] find        [9] del_val    [10] sortList   [11] modify  *\n");
    printf("* [12]clear       [13]destroy    [14] resver     [15]length   *\n");
    printf("* [16] next       [17]prio                                    *\n");
    printf("***************************************************************\n");
}
bool InitList(PList list)
{
    list->head = (PNode)malloc(sizeof(Node)); //初始化一個頭結(jié)點
    assert(list->head != NULL);               //斷言，表達式為真，接著往下執(zhí)行

    list->head->next = list->head;            //初始化head和tail指針，使其都指向頭節(jié)點
    list->tail = list->head;

    list->size = 0;                           //長度初始化為0
    return true;
}

void Create_t(PList list,ElemType x)     //尾插法
{
    PNode s = (PNode)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;                         //填充數(shù)據(jù)域
    list->tail->next = s;                //tail指向最后一個節(jié)點，把新建立的節(jié)點鏈接到鏈表的最后
    s->next = list->head;                //單循環(huán)鏈表，新節(jié)點的next指向頭結(jié)點           
    list->tail = s;                      //改變尾指針的指向
    list->size++;
} 
void showList(PList list)            //鏈表顯示函數(shù)
{
    if(1>list->size)
    {
        printf("--鏈表為空\n");
        return ;
    }
    PNode p = list->head->next;
    while(list->head != p)           //逐個遍歷鏈表
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
void Create_h(PList list,ElemType x)  //頭插法
{
    PNode s = (PNode)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;                             //填充數(shù)據(jù)域
    s->next = list->head->next;              //新節(jié)點指向第一個節(jié)點           
    list->head->next = s;                    //頭節(jié)點的next指向新節(jié)點s
    if(list->size == 0)                      //如果是第一次頭插，需改變尾指針和尾節(jié)點的next指向，之后都不改變
    {
        list->tail = s;
        list->tail->next = list->head;        
    }
    list->size++;        //插入一個，長度加1
}

void del_back(PList list)    //尾刪
{
    if(0==list->size)
        return;
    PNode p = list->head;
    while(list->head != p->next->next)      //找到倒數(shù)第二個節(jié)點
    {
        p = p->next;
    }                      
    p->next = list->head;                   //把最后一個節(jié)點分離
    free(list->tail);                       //釋放最后一個節(jié)點
    list->tail = p;                         //尾指針指向原來的倒數(shù)第二個節(jié)點（現(xiàn)在倒數(shù)第一）
    printf("--尾節(jié)點已刪除\n");
    list->size--;
}

void del_front(PList list)   //頭刪
{
    if(0==list->size)
        return;
    else
    {
        PNode p = list->head->next;
        if(1==list->size) 
        {                                    //只有一個節(jié)點，若刪去，需改變尾指針
            list->tail = list->head;
            list->head->next = list->head;
        }
        else
        {                
            list->head->next = p->next;      //頭指針指向第二個節(jié)點    
        }
        free(p);                             //釋放第一個節(jié)點
    }                            
    printf("--頭節(jié)點已刪除\n");
    list->size--;
}


void show_tail(PList list)     //為測試尾指針是否正確改變，需顯示最后一個節(jié)點
{
    printf("--鏈表的尾節(jié)點是：》%d \n",list->tail->data);
}

void sortList(PList list)      // 對無序鏈表進行從小到大排序
{
    if(2>list->size)
        return ;
    PNode p = list->head->next;
    PNode q = p->next;
    for(int i = 0;i<list->size-1;i++,p = list->head->next,q = p->next)      //n個數(shù)比較n-1趟
    {
        for(int j = 0;j<list->size-1-i;j++,p=q,q=q->next)   //第i趟比較n-i次
        {
            if(p->data > q->data)        //如果前面的數(shù)大于后面，則交換
            {
                p->data = p->data + q->data;
                q->data = p->data - q->data;
                p->data = p->data - q->data;
            }
        }
    }
}

void insert_val(PList list,ElemType x)   //鏈表有序的前提下，給一個值插入
{
    PNode p = list->head->next,q = list->head;
    while(list->head != p)               //找到能插入的位置，會在p、q之間
    {   
        if(x<p->data)
            break;
        q = p;
        p = p->next;
    }
    PNode s = (PNode)malloc(sizeof(Node)); //初始化新節(jié)點
    s->data = x;
    q->next = s;              //把新節(jié)點插入到鏈表中（在p,q之間插入）
    s->next = p;
    if(list->head == p)       //如果新節(jié)點的值最大，即尾插，需改變尾指針和尾節(jié)點的next指向
    {
        list->tail = s;
        list->tail->next=list->head;
    }
    list->size++;
}

PNode find(PList list,ElemType x)       //返回要查找元素的前面一個的地址
{
    PNode p = list->head;
    while(list->tail != p && list->head != p->next && x != p->next->data)
    {
        p = p->next;                   //循環(huán)結(jié)束，p指向x的前面一個元素
    }                      
    if(list->head == p->next)          //如果p指向最后一個元素，說明沒有找到
    {
        printf("--沒找到！\n");
        return NULL;
    }
    return p;
}

void del_val(PList list,ElemType x)     //刪除指定的值x
{
    if(0 == list->size)
        return ;
    PNode p = find(list,x);
    PNode q = NULL;
    if(NULL != p)
    {
        q = p->next;               //q指向要刪除的節(jié)點  
        if(q == list->tail)        //若刪除最后一個節(jié)點，需改變尾指針
        {
            p->next = list->head;
            list->tail = p;
        }
        else
        {
            p->next = q->next;
        }
        free(q);                  //釋放要刪除的節(jié)點
        list->size--;
        printf("--%d已刪除!\n",x);
    }
    return ;
}

void modify(PList list,ElemType x1,ElemType x2)    //把原有的x1修改成x2
{
    PNode p = find(list,x1);
    if(NULL != p)
        p->next->data = x2;
    else
        return ;
}

void clear(PList list)       //刪除鏈表的所有節(jié)點，但不刪除頭結(jié)點
{
    PNode p = list->head->next;
    PNode q = p;
    while(list->head != p)      
    {
        p = p->next;         //p依次后移，跟屁蟲q依次釋放節(jié)點
        free(q);
        q = p;
    }
    list->tail = list->head;   //修改尾指針和鏈表長度
    list->head->next = list->head;
    list->size = 0;
    printf("--鏈表已被清空！\n");
}

void destroy(PList list)   //摧毀鏈表，包括所有節(jié)點和頭結(jié)點
{
    clear(list);
    free(list->head);
    list->head = NULL;
    list->tail = NULL;
    printf("--鏈表已被摧毀！\n");
}

PNode prev(PList list,PNode p)     //返回p指向的前面一個節(jié)點
{
    if(p != list->head)
    {
        PNode q = list->head->next;
        while(q != list->head && q->next != p)  //依次往后移，知道尾指針的前面一個節(jié)點
            q=q->next;
        if(q->next == p)
            return q;
    }
    return NULL;
}
void reserve(PList list)   //逆置鏈表 
{
    PNode s = (PNode)malloc(sizeof(Node));       //建立一個節(jié)點
    s->next = list->tail;
    PNode p = list->tail;
    while(list->tail != list->head->next)        //把原鏈表的尾節(jié)點到第一個節(jié)點依次連接到新節(jié)點上
    {
        list->tail = prev(list,list->tail);
        list->tail->next = list->head;
        p->next = list->tail;
        p=p->next;
    }
    p->next = s;              //p指向第一個節(jié)點，即新鏈表的最后一個節(jié)點，尾指針的next指向頭結(jié)點s，鏈表結(jié)束
    free(list->head);         //釋放原來的頭結(jié)點
    list->head = s;           //把s變成新的頭指針
}

int length(PList list)     //求鏈表的長度
{
    return list->size;
}

ElemType next(PList list,ElemType x)      //返回x的后繼
{
    PNode p = find(list,x);  
    if(NULL == p) 
        return -1;
    if(p->next == list->tail)           //因為是單循環(huán)鏈表，尾節(jié)點的下一個元素是第一個節(jié)點
    {
        return list->head->next->data;    
    }
    p=p->next;
    return p->next->data;
}
ElemType prio(PList list,ElemType x)         //返回x的前驅(qū)
{
    PNode p = find(list,x);
    if(NULL != p)
    {
        if(p == list->head || p == list->tail)
        {
            return list->tail->data;
        }
        return p->data;
    }
    return -1;
}
main.cpp
//main.cpp 
//測試函數(shù)
#include "CList.h"

int main()
{
    List mylist;
    InitList(&mylist);
    ElemType item = 0;
    int pos = 0;
    int chose = 1;
    PNode p = NULL;
    while(chose)
    {
        menu();
        printf("給出想要操作的序號：\n");
        scanf("%d",&chose);
        switch(chose)
        {
        case 0:
            destroy(&mylist);
            chose = 0;
            break;
        case 1:
            printf("輸入要尾插的數(shù)據(jù)[-1結(jié)束]：\n");
            while(scanf("%d",&item),item!=-1)
            {
                Create_t(&mylist,item);
            }
            break;
        case 2:
            printf("輸入要頭插的數(shù)據(jù)：\n");
            while(scanf("%d",&item),item!=-1)
            {
                Create_h(&mylist,item);
            }
            break;
        case 3:
            showList(&mylist);
            break;
        case 4:
            del_back(&mylist);
            break;
        case 5:
            del_front(&mylist);
            break;
        case 6:
            printf("給出要插入的數(shù)：\n");
            scanf("%d",&item);
            insert_val(&mylist,item);
            break;
        case 7:
            show_tail(&mylist);
            break;
        case 8:
            printf("輸入要查找的數(shù)：\n");
            scanf("%d",&item);
            p = find(&mylist,item);
            if(NULL!=p)
                printf("%d\n",p->next->data);
            break;
        case 9:
            printf("輸入要刪除的數(shù)：\n");
            scanf("%d",&item);
            del_val(&mylist,item);
            break;
        case 10:
            sortList(&mylist);
            break;
        case 11:
            printf("輸入要修改的數(shù)和修改后的數(shù)\n");
            scanf("%d %d",&item,&pos);
            modify(&mylist,item,pos);
            break;
        case 12:
            clear(&mylist);
            break;            
        case 13:
            destroy(&mylist);
            break;
        case 14:
            reserve(&mylist);
            break;
        case 15:
            printf("鏈表長度為：%d\n",length(&mylist));
            break;
        case 16:
            printf("輸入想要找哪個一數(shù)的后繼：\n");
            scanf("%d",&item);
            printf("%d 的后繼是：%d\n",item,next(&mylist,item));
            break;
        case 17:
            printf("輸入想要找哪個一數(shù)的前驅(qū)：\n");
            scanf("%d",&item);
            printf("%d 的前驅(qū)是：%d\n",item,prio(&mylist,item));
            break;
        default:
            printf("重新輸入\n");
            break;
        }   
    }
    return 0;
}

運行測試：

***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
1
輸入要尾插的數(shù)據(jù)[-1結(jié)束]：
5 6  9 2 8 2 6 -1
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
3
5 6 9 2 8 2 6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
8
輸入要查找的數(shù)：
2
2
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
7
--鏈表的尾節(jié)點是：》6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
10
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
3
2 2 5 6 6 8 9
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
14
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
3
9 8 6 6 5 2 2
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
16
輸入想要找哪個一數(shù)的后繼：
8
8 的后繼是：6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
12
--鏈表已被清空！
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
給出想要操作的序號：
3
--鏈表為空
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容