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

作者: 掖莯圷 | 来源:发表于2018-09-02 16:24 被阅读0次

线性表-单循环链表（含头指针和尾指针）
数据结构与算法-线性表-循环链表
线性表
队列（链队列）
循环链表
单链表线性表
数据结构课程第四周线性表--链式表循环链表
队列
LinkedList源码剖析
Redis有这一篇就够了

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