数据结构线性表之双向循环链表的全部基本操作(C语言实现)(完美版)

//参考书是人民邮电出版社的数据结构(C语言版|第2版);

//此书编著者是严蔚敏,李冬梅,吴伟民三位老师;

//由于书上伪代码不能直接编译运行;

//故博主使用自己学过C Primer Plus中的知识来实现代码;

//本程序是可移植性程序;

//能在Linux/Mac os/Windows下编译运行;

//若有不足之处请提出，博主会尽所能修改;

//若是对您有用的话请点赞或分享提供给它人;

//未经允许严禁抄袭以及转载;

//源代码奉上,希望能够对您有所启发;

//Du_LinkedList.c

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define LEN 10

typedef int ElemType;

typedef struct node
{
    ElemType data;
    struct node *prior; //双向链表前指针域;
    struct node *next;  //双向链表后指针域;
} DuLNODE, *Du_LinkedList;

//1) 创建一个空的双向循环链表;
Du_LinkedList Init_List(void);
/*----------------------------------------------------------------------*/

//2) 若双向循环链表已存在则销毁整个链表;
bool Destroy_List(Du_LinkedList phead);
/*----------------------------------------------------------------------*/

//3) 若双向循环链表已存在且非空表则将其重置为空表;
bool Clear_List(Du_LinkedList phead);
/*----------------------------------------------------------------------*/

//4) 若双向循环链表已存在则判断其是否为空表;
bool List_Empty(Du_LinkedList phead);
/*----------------------------------------------------------------------*/

//5) 若双向循环链表已存在则获取其中数据元素个数;
int List_Length(Du_LinkedList phead);
/*----------------------------------------------------------------------*/

//6) 若双向循环链表已存在且非空表,位置pos满足1<=pos<=当前链表长度,则用*val存取并返回第i个数据元素的值;
bool Get_Elem(Du_LinkedList phead, int pos, ElemType *val);
/*----------------------------------------------------------------------*/

//7) 若双向循环链表已存在且非空表则返回第一个与val值相同的元素在表中的位置,若无相同元素则返回0;
int Locate_Elem(Du_LinkedList phead, ElemType val);
/*----------------------------------------------------------------------*/

//8) 若双向循环链表已存在且非空表, val是表中数据元素且不是第一个则用*pre返回其前驱,若val在表中不存在则操作失败;
bool Prior_Elem(Du_LinkedList phead, ElemType val, ElemType *pre);
/*----------------------------------------------------------------------*/

//9) 若双向循环链表已存在且非空表, val是表中数据元素且不是最后一个则用*next返回其后继,若val在表中不存在则操作失败;
bool Next_Elem(Du_LinkedList phead, ElemType val, ElemType *next);
/*----------------------------------------------------------------------*/

//10) 若双向循环链表已存在且位置pos满足1<=pos<=当前链表长度,则在第i个位置前添加新元素val;
bool List_Insert(Du_LinkedList phead, int pos, ElemType val);
/*----------------------------------------------------------------------*/

//11) 若双向循环链表已存在且非空表,位置pos满足1<=pos<=当前链表长度,则删除第i个数据元素;
bool List_Delete(Du_LinkedList phead, int pos);
/*----------------------------------------------------------------------*/

//12) 若双向循环链表已存在且非空表则遍历其中所有数据元素;
void Traverse_List(Du_LinkedList phead);
/*----------------------------------------------------------------------*/

//13) 在双向循环链表尾部添加新元素val;
bool add_item(Du_LinkedList ptail, ElemType val);
/*----------------------------------------------------------------------*/

//14) 显示主菜单;
int show_menu(void);
/*----------------------------------------------------------------------*/

//15) 获取用户输入的第1个字符;
int get_first(void);
/*----------------------------------------------------------------------*/

//16) 清空输入缓冲区;
void eatline(void);
/*----------------------------------------------------------------------*/

//17) 获取用户输入的数据元素;
void input(ElemType *ch);
/*----------------------------------------------------------------------*/

//18) 获取用户输入的操作位置;
int input_pos(int *tp);
/*----------------------------------------------------------------------*/

//19) 操作双向循环链表中的数据元素;
void choice(int ch, Du_LinkedList phead);
/*----------------------------------------------------------------------*/
//前12个操作是书上的线性表的链式(双向循环)实现,后面的操作是博主CLOVER~X的补充;

int main(void)
{
    int ch;
    Du_LinkedList phead = NULL;

    phead = Init_List();
    while ((ch = show_menu()) != 'q')
    {
        choice(ch, phead);
    }
    Destroy_List(phead); //用户输入q时退出菜单并释放动态分配的内存;
    printf("本程序完成!\n");

    return 0;
}

Du_LinkedList Init_List(void)
{
    Du_LinkedList phead = (Du_LinkedList)malloc(sizeof(DuLNODE));
    if (NULL == phead)
    {
        fprintf(stderr, "动态内存分配失败!本程序退出!\n");
        exit(EXIT_FAILURE);
    }
    phead->prior = phead;
    phead->next = phead;
    return phead;
}

bool Destroy_List(Du_LinkedList phead)
{
    if (List_Empty(phead)) //若为空表则此表仅有头结点,因此只销毁头结点;
    {
        free(phead);
    }
    else
    {
        DuLNODE *p = phead->next;
        DuLNODE *q = p;
        phead->next = NULL;
        while (q) //由于此链表是循环链表,故先销毁头结点之后的点最后再销毁头结点;
        {
            q = q->next;
            free(p);
            p = q;
        }
    }
    return true;
}

bool Clear_List(Du_LinkedList phead)
{
    DuLNODE *p, *q;

    p = phead->next;   //指向首元结点;
    while (p != phead) //指针p指向头结点时退出循环;
    {
        q = p->next; //保存当前结点p的后继结点的地址;
        free(p);     //释放当前结点p的内存;
        p = q;       //指向下一个结点q;
    }
    phead->prior = phead;
    phead->next = phead;
    return true;
}

bool List_Empty(Du_LinkedList phead)
{
    return phead == phead->next ? true : false;
}

int List_Length(Du_LinkedList phead)
{
    int i = 0;
    Du_LinkedList p = phead->next;

    while (p != phead)
    {
        p = p->next;
        ++i;
    }
    return i;
}

bool Get_Elem(Du_LinkedList phead, int pos, ElemType *val)
{
    int j = 1;
    Du_LinkedList p = phead->next;

    while ((p != phead) && (j < pos)) //顺序查找到第pos个结点;
    {
        p = p->next;
        ++j;
    }
    if ((phead == p) || (j > pos)) //若循环查找到头结点(位置pos大于当前链表长度)或位置pos小于1时,获取数据无效;
    {
        printf("您输入的位置不合理!无法获取数据!\n");
        return false;
    }
    *val = p->data;
    return true;
}

int Locate_Elem(Du_LinkedList phead, ElemType val)
{
    int i = 1;
    Du_LinkedList p = phead->next;

    while ((p != phead) && (p->data != val))
    {
        p = p->next;
        ++i;
    }
    return phead == p ? 0 : i;
    //表中若是无数据元素val则返回位置0;
    //否则返回数据元素val在链表中的位置i;
}

bool Prior_Elem(Du_LinkedList phead, ElemType val, ElemType *pre)
{
    Du_LinkedList p = phead->next;

    while ((p != phead) && (p->data != val))
    {
        p = p->next;
    }
    if (phead == p) //若是循环结束后返回到头结点则说明表中无相同元素;
    {
        printf("数据元素%d不在此链表中!\n", val);
        return false;
    }
    if (phead == p->prior) //此链表是循环链表,若数据元素存储在首元结点(首元结点前只有头结点)则无前驱元素;
    {
        printf("%d是链表中第一个数据元素!无前驱元素!\n", val);
        return false;
    }
    *pre = p->prior->data;
    return true;
}

bool Next_Elem(Du_LinkedList phead, ElemType val, ElemType *next)
{
    Du_LinkedList p = phead->next;

    while ((p != phead) && (p->data != val))
    {
        p = p->next;
    }
    if (phead == p)
    {
        printf("数据元素%d不在此链表中!\n", val);
        return false;
    }
    if (phead == p->next) //此链表是循环链表,若数据元素存储在尾结点则无后继元素;
    {
        printf("%d是链表中最后一个数据元素!无后继元素!\n", val);
        return false;
    }
    *next = p->next->data;
    return true;
}

bool List_Insert(Du_LinkedList phead, int pos, ElemType val)
{
    int i = 0;
    Du_LinkedList p = phead->next;

    while ((p != phead) && (i < pos - 1)) //查找到第pos个结点;
    {
        p = p->next;
        ++i;
    }
    if ((phead == p) || (i > pos - 1)) //若循环查找到尾结点后或位置小于1时,添加无效;
    {
        printf("您输入的位置不合理!添加失败!\n");
        return false;
    }
    Du_LinkedList pnew = (Du_LinkedList)malloc(sizeof(DuLNODE));
    if (NULL == pnew)
    {
        fprintf(stderr, "动态内存分配失败!本程序退出!\n");
        exit(EXIT_FAILURE);
    }
    pnew->data = val;       //赋值给新结点的数据域;
    pnew->prior = p->prior; //新结点指向当前结点(p)的前驱结点;
    p->prior->next = pnew;  //当前结点(p)的前驱结点后指针域指向新结点;
    pnew->next = p;         //新结点的后指针域指向当前结点(p);
    p->prior = pnew;        //当前结点(p)的前指针域指向新结点;
    return true;
}

bool List_Delete(Du_LinkedList phead, int pos)
{
    int i = 0;
    Du_LinkedList p = phead->next;

    while ((p != phead) && (i < pos - 1)) //查找到第pos-1个结点;
    {
        p = p->next;
        ++i;
    }
    if ((phead == p) || (i > pos - 1)) //若循环查找到头结点或位置小于1时,删除无效;
    {
        printf("您输入的位置不合理!删除失败!\n");
        return false;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return true;
}

void Traverse_List(Du_LinkedList phead)
{
    DuLNODE *p = phead->next;

    while (p != phead)
    {
        printf("%-8d", p->data);
        p = p->next;
    }
    return;
}

bool add_item(Du_LinkedList ptail, ElemType val)
{
    Du_LinkedList pnew = (Du_LinkedList)malloc(sizeof(DuLNODE));
    if (pnew == NULL)
    {
        fprintf(stderr, "动态内存分配失败!本程序退出!\n");
        exit(EXIT_FAILURE);
    }
    pnew->data = val;
    pnew->next = ptail->next;  //使新结点后指针域指向头结点;
    ptail->next->prior = pnew; //头结点前指针域指向新结点(尾结点);
    ptail->next = pnew;        //使原尾结点后指针域指向新结点;
    pnew->prior = ptail;       //使新结点前指针域指向原尾结点(添加新结点成功);
    return true;
}

int show_menu(void)
{
    int ch;

    puts("===================================================");
    puts("a) 销毁双向循环链表");
    puts("b) 清空双向循环链表");
    puts("c) 判断双向循环链表是否为空");
    puts("d) 查看双向循环链表长度");
    puts("e) 获取双向循环链表中的指定位置的数据");
    puts("f) 查找用户输入的数据在此双向循环链表中是否存在");
    puts("g) 查看链表中已存在元素的前驱元素");
    puts("h) 查看链表中已存在元素的后继元素");
    puts("i) 在指定位置前(非尾部)添加新的数据元素");
    puts("j) 在链表尾端添加新的数据元素");
    puts("k) 删除指定位置的数据元素");
    puts("m) 对当前双向循环链表进行遍历");
    puts("q) 退出本程序");
    puts("===================================================");
    printf("请您输入选择:");
    ch = get_first();
    while (strchr("abcdefghijkmq", ch) == NULL)
    {
        printf("您的输入无效!请重新输入:");
        ch = get_first();
    }
    return ch;
}

int get_first(void)
{
    int ch;

    do
    {
        ch = tolower(getchar());
    } while (isspace(ch));
    eatline();

    return ch;
}

void eatline(void)
{
    while (getchar() != '\n')
        continue;
    return;
}

void input(ElemType *ch)
{
    printf("请您输入一个数据元素:");
    while (scanf("%d", ch) != 1)
    {
        eatline();
        printf("数据无效!请重新输入:");
    }
    eatline();
    return;
}

int input_pos(int *tp)
{
    printf("请您输入一个需要操作的位置:");
    while (scanf("%d", tp) != 1)
    {
        eatline();
        printf("数据无效!请重新输入:");
    }
    eatline();
    return *tp;
}

void choice(int ch, Du_LinkedList phead)
{
    int pos;
    ElemType val, pre, next;

    switch (ch)
    {
    case 'a':
    {
        if (Destroy_List(phead))
        {
            printf("销毁链表成功!退出本程序!\n");
            exit(EXIT_SUCCESS);
        }
        break;
    }
    case 'b':
    {
        if (List_Empty(phead))
        {
            printf("链表是空表!无法清空!\n");
            break;
        }
        if (Clear_List(phead))
        {
            printf("清空链表成功!\n");
        }
        break;
    }
    case 'c':
    {
        if (List_Empty(phead))
        {
            printf("链表是空表!\n");
        }
        else
        {
            printf("链表非空表!\n");
        }
        break;
    }
    case 'd':
    {
        printf("链表中元素个数:%d个\n", List_Length(phead));
        break;
    }
    case 'e':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法获取数据!\n");
            break;
        }
        if (Get_Elem(phead, input_pos(&pos), &val))
        {
            printf("链表中第%d个数据元素是%d\n", pos, val);
        }
        break;
    }
    case 'f':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法查找数据!\n");
            break;
        }
        input(&val);
        pos = Locate_Elem(phead, val);
        if (pos != 0)
        {
            printf("%d是链表中是第%d个数据元素", val, pos);
        }
        else
        {
            printf("数据元素%d不在此链表中!\n", val);
        }
        break;
    }
    case 'g':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法获取前驱元素!\n");
            break;
        }
        input(&val);
        if (Prior_Elem(phead, val, &pre))
        {
            printf("第%d个数据元素的前驱元素是%d\n", val, pre);
        }
        break;
    }
    case 'h':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法获取后继元素!\n");
            break;
        }
        input(&val);
        if (Next_Elem(phead, val, &next))
        {
            printf("第%d个数据元素的后继元素是%d\n", val, next);
        }
        break;
    }
    case 'i':
    {
        input(&val);
        if (List_Insert(phead, input_pos(&pos), val))
        {
            printf("在第%d个位置添加数据元素%d成功!\n", pos, val);
        }
        break;
    }
    case 'j':
    {
        input(&val);
        if (add_item(phead->prior, val))
        {
            printf("在此链表中添加数据元素%d成功!\n", val);
        }
        break;
    }
    case 'k':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法删除数据!\n");
            break;
        }
        if (List_Delete(phead, input_pos(&pos)))
        {
            printf("删除第%d个数据元素成功!\n", pos);
        }
        break;
    }
    case 'm':
    {
        if (List_Empty(phead))
        {
            printf("此链表为空表!无法进行遍历!\n");
            break;
        }
        Traverse_List(phead);
        break;
    }
    }
    printf("\n\n\n\n\n\n\n\n\n\n\n\n");
    return;
}

//---------------------------------------------------------;

//-------------------------------------------------2020年5月19日-------------------------------------------------------;