image.png

CircleList.h:

#ifndef CIRCLELIST_H_INCLUDED
#define CIRCLELIST_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#include <assert.h>

typedef int ElemType ;//數(shù)據(jù)類型
typedef struct Node{
    ElemType data;//數(shù)據(jù)域
    struct Node *next;//下一節(jié)點(diǎn)
}Node,*PNode;
typedef struct CircleList{
    PNode head;
    PNode tail;
    int size;
}CircleList;

void Init_List(CircleList *pList);             //初始化單鏈表
void Show_List(CircleList *pList);         //顯示鏈表內(nèi)容
PNode Buy_Node(ElemType e); //創(chuàng)建一個(gè)新節(jié)點(diǎn)
void Push_Front(CircleList *pList,ElemType e);//頭插法
void Push_Back(CircleList *pList,ElemType e); //尾插法
ElemType Pop_Front(CircleList *pList);            //頭刪法
ElemType Pop_Back(CircleList *pList);             //尾刪法
Node* Find_Val(CircleList *pList,ElemType e,int* index);     //查找函數(shù)滤蝠，找到返回指向該元素的指針
bool Modify_Val(CircleList *pList,ElemType oldVal,ElemType newVal);    //修改某一元素的值
void Delete_Val(CircleList *pList,ElemType e);//按值刪除
void Clear_List(CircleList *pList);                //清空鏈表
void Destroy_List(CircleList *pList);              //銷毀鏈表
int  Length_List(CircleList *pList);               //求鏈表長度
bool IsEmpty_List(CircleList *pList);               //判斷鏈表是否為空
PNode Prio_List(CircleList *pList,ElemType e);      //求某個(gè)值的前驅(qū)
PNode Next_List(CircleList *pList,ElemType e);      //求某個(gè)值的后繼

#endif // CIRCLELIST_H_INCLUDED

CircleList.c:

#include "CircleList.h"


//初始化單鏈表
void Init_List(CircleList *pList){

    PNode p = (PNode)malloc(sizeof(Node)); //初始化一個(gè)結(jié)點(diǎn)
    assert(pList->head != NULL);
    //初始化head和tail指針，使其都指向頭節(jié)點(diǎn)
    pList->tail = pList->head = p;
    pList->head->next=pList->head;
    pList->tail->next=pList->head;
    pList->size=0;
}
 //顯示鏈表內(nèi)容
void Show_List(CircleList *pList){
    if(pList->size<1){
        printf("[]\n");
        return ;
    }
     PNode p = pList->head->next;//第一個(gè)節(jié)點(diǎn)
     bool flag=false;
     printf("[");
     while(p!=pList->head){
        if(flag){
            printf(",");
        }
        flag=true;
        printf("%d",p->data);
        p=p->next;
     }
     printf("]\n");
}
//創(chuàng)建一個(gè)新節(jié)點(diǎn)
PNode Buy_Node(ElemType e){
    PNode p = (PNode)malloc(sizeof(Node)); //初始化一個(gè)結(jié)點(diǎn)
    assert(p != NULL);//斷言，表達(dá)式為真，接著往下執(zhí)行
    p->next=NULL;
    p->data=e;//填充數(shù)據(jù)域
    return p;

}
//頭插法
void Push_Front(CircleList *pList,ElemType e){
    PNode nexNode=Buy_Node(e);//獲取一個(gè)節(jié)點(diǎn)
    nexNode->next=pList->head->next;
    pList->head->next=nexNode;
    //如果是第一次頭插，需改變尾指針和尾節(jié)點(diǎn)的next指向，之后都不改變
    if(pList->size==0){
        pList->tail=nexNode;
    }
    pList->size++;//有效個(gè)數(shù)加1
}
//尾插法
void Push_Back(CircleList *pList,ElemType e){
    PNode nexNode=Buy_Node(e);//獲取一個(gè)節(jié)點(diǎn)
    nexNode->next=pList->tail->next;//單循環(huán)鏈表，新節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)
    pList->tail->next=nexNode; //tail指向最后一個(gè)節(jié)點(diǎn)，把新建立的節(jié)點(diǎn)鏈接到鏈表的最后
    pList->tail=nexNode;//改變尾指針的指向
    pList->size++;//有效個(gè)數(shù)加1
    return true;
}
//頭刪法
ElemType Pop_Front(CircleList *pList){

    if(0==pList->size)return 0;
    PNode first=pList->head->next;
    ElemType val=first->data;
     //只有一個(gè)節(jié)點(diǎn)摊腋，若刪去，需改變尾指針
    if(1==pList->size) {
        pList->tail=pList->head;
    }
    pList->head->next=first->next;
    free(first);
    printf("--頭節(jié)點(diǎn)已刪除\n");
    pList->size--;

    return val;
}
//尾刪法
ElemType Pop_Back(CircleList *pList){
    if(0==pList->size)return 0;
    PNode last=pList->tail;
//    PNode p = pList->head->next;
//    while(p->next!=last){////找到倒數(shù)第二個(gè)節(jié)點(diǎn)
//        p=p->next;
//    }
    PNode p = pList->head;
    while(pList->head != p->next->next)      //找到倒數(shù)第二個(gè)節(jié)點(diǎn)
    {
        p = p->next;
    }
    p->next=last->next;
    pList->tail=p;
    ElemType val=last->data;
    free(last);
    printf("--尾節(jié)點(diǎn)已刪除\n");
    pList->size--;
    return val;
}
//查找函數(shù)嘁傀，找到返回指向該元素的指針 即要查找元素的前面一個(gè)的地址 以及下標(biāo)
Node* Find_Val(CircleList *pList,ElemType e,int *index){
    if(0==pList->size){
         printf("--鏈表為空兴蒸！\n");
        return NULL;
    }
    PNode p=pList->head;//第一個(gè)節(jié)點(diǎn)
    int j=0;
    PNode pre;
    bool flag=true;
    while(p->next!=pList->head && flag){//尋找指向這個(gè)元素的指針
        pre=p;
        p=p->next;
        j++;
        if(p->data == e){
            flag=false;
        }
    }

    if(pList->head == pre->next||flag){          //如果p指向最后一個(gè)元素，說明沒有找到
        printf("--沒找到细办！\n");
        if(index){
            *index=-1;
        }
        return NULL;
    }
    if(index){
        *index=j;
    }
    return pre;
}
//修改某一元素的值
bool Modify_Val(CircleList *pList,ElemType oldVal,ElemType newVal){
     PNode p = Find_Val(pList,oldVal,NULL);
     if(!p){
        return false;
     }
     p->next->data=newVal;
     return true;
}
//按值刪除
void Delete_Val(CircleList *pList,ElemType e){
    if(0==pList->size){
         printf("--鏈表為空橙凳！\n");
        return ;
    }
    //尋找到前一個(gè)元素
    PNode pre = Find_Val(pList,e,NULL);
    PNode temp = NULL;//要?jiǎng)h除的節(jié)點(diǎn)
    if(pre){
        temp=pre->next;
        if(temp == pList->tail)        //若刪除最后一個(gè)節(jié)點(diǎn)，需改變尾指針
        pList->tail = pre;
        pre->next=temp->next;
        free(temp);
        printf("元素%d已刪除!\n",e);
    }

}
//清空鏈表
void Clear_List(CircleList *pList){
    PNode p=pList->head->next;//p指向第一個(gè)節(jié)點(diǎn)
    PNode temp;
    while(p!=pList->head){
        temp=p->next;
        free(p);//將節(jié)點(diǎn)依次釋放
        p=temp;
    }
    //尾指針以及頭指針都指向頭結(jié)點(diǎn)
    pList->tail = pList->head;
    pList->tail->next= pList->head;
    pList->head->next = pList->head;
    pList->size = 0;
    printf("--鏈表已被清空笑撞！\n");
}
//銷毀鏈表
void Destroy_List(CircleList *pList){
    Clear_List(pList);
    free(pList->head);//頭結(jié)點(diǎn)釋放
    pList->head = NULL;
    pList->tail = NULL;
    printf("--鏈表已被摧毀痕惋！\n");
}
//求鏈表長度
int  Length_List(CircleList *pList){
    if(!pList->head){
         printf("--鏈表未初始化！\n");
        return 0;
    }
    int length=0;
    PNode p=pList->head->next;
    while(p!=pList->head){
        p=p->next;
        length++;
    }
    return length;
}
//判斷鏈表是否為空
bool IsEmpty_List(CircleList *pList){
//    if(pList->size==0){
//        return true;
//    }
      if(pList->head==pList->head->next){
        printf("鏈表為空\n");
        return true;
      }
      return false;

}

//求某個(gè)值的前驅(qū)
PNode Prio_List(CircleList *pList,ElemType e){
    PNode pre = Find_Val(pList,e,NULL);
    if(NULL != pre){
        if(pre == pList->head ) {//首元素?zé)o前驅(qū)
            printf("首元素?zé)o前驅(qū)\n");
            return NULL;
        }
        return pre;
    }
    return NULL;
}
//求某個(gè)值的后繼
PNode Next_List(CircleList *pList,ElemType e){
    PNode pre = Find_Val(pList,e,NULL);
    if(NULL != pre){
        if(pre->next == pList->tail ) {//尾元素?zé)o后繼
            printf("尾元素?zé)o后繼\n");
            return NULL;
        }
        return pre->next->next;
    }
    return NULL;
}

測試：

#include "CircleList.h"
void menu()           //提供選項(xiàng)的菜單函數(shù)
{
    printf("***************************************************************\n");
    printf("* [0] 退出系統(tǒng)    [1] 展示鏈表   [2] 頭插數(shù)據(jù)    [3] 尾插數(shù)據(jù) *\n");
    printf("* [4] 頭刪數(shù)據(jù)    [5] 尾刪數(shù)據(jù)   [6] 查找元素    [7] 修改元素*\n");
    printf("* [8] 按值刪除    [9] 鏈表長度   [10]判斷空鏈表  [11]獲取前驅(qū)  *\n");
    printf("* [12]獲取后繼    [13]獲取前驅(qū)   [14] 銷毀鏈表       *\n");
    printf("***************************************************************\n");
}
int main()
{
    CircleList pList;
    Init_List(&pList);
    ElemType val= 0;
    bool flag=true;
    PNode p = NULL;
    int chose;
    int pos ;
     int index=0;
    while(flag){
         menu();
         printf("輸入序號(hào)選擇您的操作：\n");
         scanf("%d",&chose);
         switch(chose){
            case 0:
                flag=false;
                exit(0);
                break;
            case 1:
                Show_List(&pList);
                break;
            case 2:
                printf("輸入要頭插的數(shù)據(jù)[-1結(jié)束]：\n");
                while(scanf("%d",&val),val!=-1){
                    Push_Front(&pList,val);
                }
                break;
            case 3:
                printf("輸入要尾插的數(shù)據(jù)[-1結(jié)束]：\n");
                while(scanf("%d",&val),val!=-1){
                    Push_Back(&pList,val);
                }
                break;
            case 4:
                Pop_Front(&pList);
                break;
            case 5:
                Pop_Back(&pList);
                break;
            case 6:

                printf("輸入要查找的數(shù)據(jù)：\n");
                scanf("%d",&val);
                p = Find_Val(&pList,val,&index);
                if(p){
                    printf("查找的元素為%d,下標(biāo)為：%d",p->next->data,index);
                }
                break;
            case 7:
               printf("輸入要修改的數(shù)和修改后的數(shù)\n");
                scanf("%d %d",&val,&pos);
                Modify_Val(&pList,val,pos);
                break;
            case 8:
                printf("輸入要?jiǎng)h除的數(shù)\n");
                scanf("%d",&val);
                Delete_Val(&pList,val);
                break;
            case 9:
                printf("鏈表的長度為：%d\n",Length_List(&pList));
                break;
            case 10:
                if(!IsEmpty_List(&pList)){
                    printf("鏈表不為空\n");
                }
                break;
            case 11:
                printf("輸入想要找哪個(gè)一數(shù)的前驅(qū)：\n");
                scanf("%d",&val);
                p=Prio_List(&pList,val);
                if(p){
                    printf("%d 的前驅(qū)是：%d\n",val,p->data);
                }
                break;
            case 12:
                printf("輸入想要找哪個(gè)一數(shù)的后繼：\n");
                scanf("%d",&val);
                p=Next_List(&pList,val);
                if(p){
                    printf("%d 的前驅(qū)是：%d\n",val,p->data);
                }
                break;
            case 13:
                Clear_List(&pList);
                break;
            case 14:
                Destroy_List(&pList);
                break;
            default:
                printf("重新輸入\n");
            break;
         }
    }
    return 0;
}