C语言实现循环双链表

本文实例为大家分享了C语言实现循环双链表的具体代码，供大家参考，具体内容如下

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct Node
{
    DataType data;            //    数据域
    struct Node * prior;      //    前趋指针
    struct Node * next;       //    后继指针

}LinkList;

LinkList* Init_List();                                //    初始化循环双链表
bool Creat_List(LinkList * L);                        //    创建链表
int Length_List(LinkList * L);                        //    链表长度
bool Empty_List(LinkList * L);                        //    判空
bool Insert_List(LinkList * L, int pos, DataType x);  //    插入
bool Delete_List(LinkList * L, int pos, DataType * x);//    删除
bool Destroy_List(LinkList * L);                      //    销毁链表
bool Traverse_List(LinkList * L);                     //    遍历链表
int Prior_Value(LinkList * L, int pos);               //    前趋结点的值

int main()
{
    DataType x;
    int pos;

    LinkList * L = Init_List();
    if(Creat_List(L))
        printf("链表构造成功！\n");
    else
        printf("链表构造失败！\n");
    printf("遍历链表：");
    Traverse_List(L);

    printf("链表结点个数：%d\n\n", Length_List(L));

    printf("输入要求前趋结点的结点：");
    scanf("%d",&pos);
    printf("第%d个结点的前趋结点：%d\n\n",pos,Prior_Value(L, pos));

    Insert_List(L, 2, 5);
    printf("插入结点：第2个结点\n");
    printf("插入元素：5\n");
    printf("遍历链表：");
    Traverse_List(L);

    Delete_List(L, 3, &x);
    printf("删除结点：第3个结点\n");
    printf("被删除元素：%d\n",x);
    printf("遍历链表：");
    Traverse_List(L);

    if(Destroy_List(L))
        printf("销毁成功！\n");
    else
        printf("销毁失败！\n");

    return 0;
}

LinkList* Init_List()
{
    LinkList * L = (LinkList *)malloc(sizeof(LinkList));    //    创建头结点
    if(!L)
    {
        printf("申请空间失败！\n");
        exit(-1);
    }

    L->next = L->prior = L;    //    空表，前趋指针和后继指针均指向其自身
    return L;                 //    返回头结点的地址
}

bool Creat_List(LinkList * L)
{
    int i,n,val;
    LinkList * p = L;    //    保证L始终指向头结点

    printf("请输入循环双链表的结点个数：");
    scanf("%d",&n);

    for(i=0; i<n; ++i)
    {
        printf("第%d个结点：",i+1);
        scanf("%d",&val);

        LinkList * q = (LinkList*)malloc(sizeof(LinkList));
        q->data = val;
        p->next = q;
        q->prior = p;
        p = q;
    }

    p->next = L;    //    保证最后一个结点的后继指针指向头结点
    L->prior = p;    //    保证头结点的前趋指针指向最后一个结点
    return true;
}

int Length_List(LinkList * L)
{
    int len = 0;
    LinkList * p = L->next;

    while(p!=L)    //    最后一个结点也要加上
    {
        len++;
        p = p->next;
    }

    return len;
}

bool Empty_List(LinkList * L)
{
    if(L->next==L&&L->prior==L)
        return true;
    else
        return false;
}

bool Insert_List(LinkList * L, int pos, DataType x)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos-1&&L!=p)    //    指针移动到被插入结点的前一个结点
    {
        i++;
        p = p->next;
    }

    LinkList * q = (LinkList*)malloc(sizeof(LinkList));
    q->data = x;
    q->next = p->next;
    q->prior = p;
    p->next->prior = q;
    p->next = q;
    return true;
}

bool Delete_List(LinkList * L, int pos, DataType * x)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos-1&&L!=p)
    {
        i++;
        p = p->next;
    }

    LinkList * q = p->next;
    *x = q->data;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

bool Destroy_List(LinkList * L)
{
//    将循环双链表变成单链表
    LinkList * p = L->next;
    L->next = NULL;        //    空表时， 头结点的前趋指针、后继指针都是指向其自身
    L->prior = NULL;    //    销毁时，头结点前趋指针、后继指针指向空

    while(p)
    {
        LinkList * q = p->next;
        free(p);
        p = q;
    }

    L = p = NULL;
    return true;
}

bool Traverse_List(LinkList * L)
{
    if(Empty_List(L))
        return false;

    LinkList * p = L->next;

    while(p!=L)
    {
        printf("%3d",p->data);
        p = p->next;
    }

    printf("\n\n");

}

int Prior_Value(LinkList * L, int pos)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos&&L!=p)    //    指向pos要求的结点
    {
        i++;
        p = p->next;
    }

    return p->prior->data;

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：https://blog.csdn.net/Mr_Morgans/article/details/120987758