线性表-单循环链表（含头指针和尾指针）

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 ;//数据类型
typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//下一节点
}Node,*PNode;
typedef struct CircleList{
    PNode head;
    PNode tail;
    int size;
}CircleList;

void Init_List(CircleList *pList);             //初始化单链表
void Show_List(CircleList *pList);         //显示链表内容
PNode Buy_Node(ElemType e); //创建一个新节点
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);     //查找函数，找到返回指向该元素的指针
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);      //求某个值的前驱
PNode Next_List(CircleList *pList,ElemType e);      //求某个值的后继

#endif // CIRCLELIST_H_INCLUDED

CircleList.c:

#include "CircleList.h"


//初始化单链表
void Init_List(CircleList *pList){

    PNode p = (PNode)malloc(sizeof(Node)); //初始化一个结点
    assert(pList->head != NULL);
    //初始化head和tail指针，使其都指向头节点
    pList->tail = pList->head = p;
    pList->head->next=pList->head;
    pList->tail->next=pList->head;
    pList->size=0;
}
 //显示链表内容
void Show_List(CircleList *pList){
    if(pList->size<1){
        printf("[]\n");
        return ;
    }
     PNode p = pList->head->next;//第一个节点
     bool flag=false;
     printf("[");
     while(p!=pList->head){
        if(flag){
            printf(",");
        }
        flag=true;
        printf("%d",p->data);
        p=p->next;
     }
     printf("]\n");
}
//创建一个新节点
PNode Buy_Node(ElemType e){
    PNode p = (PNode)malloc(sizeof(Node)); //初始化一个结点
    assert(p != NULL);//断言，表达式为真，接着往下执行
    p->next=NULL;
    p->data=e;//填充数据域
    return p;

}
//头插法
void Push_Front(CircleList *pList,ElemType e){
    PNode nexNode=Buy_Node(e);//获取一个节点
    nexNode->next=pList->head->next;
    pList->head->next=nexNode;
    //如果是第一次头插，需改变尾指针和尾节点的next指向，之后都不改变
    if(pList->size==0){
        pList->tail=nexNode;
    }
    pList->size++;//有效个数加1
}
//尾插法
void Push_Back(CircleList *pList,ElemType e){
    PNode nexNode=Buy_Node(e);//获取一个节点
    nexNode->next=pList->tail->next;//单循环链表，新节点的next指向头结点
    pList->tail->next=nexNode; //tail指向最后一个节点，把新建立的节点链接到链表的最后
    pList->tail=nexNode;//改变尾指针的指向
    pList->size++;//有效个数加1
    return true;
}
//头删法
ElemType Pop_Front(CircleList *pList){

    if(0==pList->size)return 0;
    PNode first=pList->head->next;
    ElemType val=first->data;
     //只有一个节点，若删去，需改变尾指针
    if(1==pList->size) {
        pList->tail=pList->head;
    }
    pList->head->next=first->next;
    free(first);
    printf("--头节点已删除\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){////找到倒数第二个节点
//        p=p->next;
//    }
    PNode p = pList->head;
    while(pList->head != p->next->next)      //找到倒数第二个节点
    {
        p = p->next;
    }
    p->next=last->next;
    pList->tail=p;
    ElemType val=last->data;
    free(last);
    printf("--尾节点已删除\n");
    pList->size--;
    return val;
}
//查找函数，找到返回指向该元素的指针 即要查找元素的前面一个的地址 以及下标
Node* Find_Val(CircleList *pList,ElemType e,int *index){
    if(0==pList->size){
         printf("--链表为空！\n");
        return NULL;
    }
    PNode p=pList->head;//第一个节点
    int j=0;
    PNode pre;
    bool flag=true;
    while(p->next!=pList->head && flag){//寻找指向这个元素的指针
        pre=p;
        p=p->next;
        j++;
        if(p->data == e){
            flag=false;
        }
    }

    if(pList->head == pre->next||flag){          //如果p指向最后一个元素，说明没有找到
        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 ;
    }
    //寻找到前一个元素
    PNode pre = Find_Val(pList,e,NULL);
    PNode temp = NULL;//要删除的节点
    if(pre){
        temp=pre->next;
        if(temp == pList->tail)        //若删除最后一个节点，需改变尾指针
        pList->tail = pre;
        pre->next=temp->next;
        free(temp);
        printf("元素%d已删除!\n",e);
    }

}
//清空链表
void Clear_List(CircleList *pList){
    PNode p=pList->head->next;//p指向第一个节点
    PNode temp;
    while(p!=pList->head){
        temp=p->next;
        free(p);//将节点依次释放
        p=temp;
    }
    //尾指针以及头指针都指向头结点
    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);//头结点释放
    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;

}

//求某个值的前驱
PNode Prio_List(CircleList *pList,ElemType e){
    PNode pre = Find_Val(pList,e,NULL);
    if(NULL != pre){
        if(pre == pList->head ) {//首元素无前驱
            printf("首元素无前驱\n");
            return NULL;
        }
        return pre;
    }
    return NULL;
}
//求某个值的后继
PNode Next_List(CircleList *pList,ElemType e){
    PNode pre = Find_Val(pList,e,NULL);
    if(NULL != pre){
        if(pre->next == pList->tail ) {//尾元素无后继
            printf("尾元素无后继\n");
            return NULL;
        }
        return pre->next->next;
    }
    return NULL;
}

测试：

#include "CircleList.h"
void menu()           //提供选项的菜单函数
{
    printf("***************************************************************\n");
    printf("* [0] 退出系统    [1] 展示链表   [2] 头插数据    [3] 尾插数据 *\n");
    printf("* [4] 头删数据    [5] 尾删数据   [6] 查找元素    [7] 修改元素*\n");
    printf("* [8] 按值删除    [9] 链表长度   [10]判断空链表  [11]获取前驱  *\n");
    printf("* [12]获取后继    [13]获取前驱   [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("输入序号选择您的操作：\n");
         scanf("%d",&chose);
         switch(chose){
            case 0:
                flag=false;
                exit(0);
                break;
            case 1:
                Show_List(&pList);
                break;
            case 2:
                printf("输入要头插的数据[-1结束]：\n");
                while(scanf("%d",&val),val!=-1){
                    Push_Front(&pList,val);
                }
                break;
            case 3:
                printf("输入要尾插的数据[-1结束]：\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("输入要查找的数据：\n");
                scanf("%d",&val);
                p = Find_Val(&pList,val,&index);
                if(p){
                    printf("查找的元素为%d,下标为：%d",p->next->data,index);
                }
                break;
            case 7:
               printf("输入要修改的数和修改后的数\n");
                scanf("%d %d",&val,&pos);
                Modify_Val(&pList,val,pos);
                break;
            case 8:
                printf("输入要删除的数\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("输入想要找哪个一数的前驱：\n");
                scanf("%d",&val);
                p=Prio_List(&pList,val);
                if(p){
                    printf("%d 的前驱是：%d\n",val,p->data);
                }
                break;
            case 12:
                printf("输入想要找哪个一数的后继：\n");
                scanf("%d",&val);
                p=Next_List(&pList,val);
                if(p){
                    printf("%d 的前驱是：%d\n",val,p->data);
                }
                break;
            case 13:
                Clear_List(&pList);
                break;
            case 14:
                Destroy_List(&pList);
                break;
            default:
                printf("重新输入\n");
            break;
         }
    }
    return 0;
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,406评论 6赞 503
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,732评论 3赞 393
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 163,711评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,380评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,432评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,301评论 1赞 301
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,145评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,008评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,443评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,649评论 3赞 334
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,795评论 1赞 347
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,501评论 5赞 345
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,119评论 3赞 328
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,731评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,865评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,899评论 2赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,724评论 2赞 354

线性表-单循环链表（含头指针和尾指针）

推荐阅读更多精彩内容