linux 环境下双向循环链表简单定义及使用

Dancersky

刚刚开始学习 希望多多交流

初来乍到 :ton:

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct Node
{
        DataType data;
        struct Node *next;             //指向后继结点的指针域
        struct Node *prior;            //指向前驱结点的指针域
}DLNode;

void ListIntiate(DLNode **head)    //双向循环链表初始化   
{
        *head = (DLNode *)malloc(sizeof(DLNode));  
        (*head)->prior = *head;        //构成前驱指针循环链表
        (*head)->next = *head;         //构成后继指针循环链表
}

int ListInsert(DLNode *head,int i,DataType x) //插入数据元素
{
        DLNode *p,*q;
        int j;
        p = head->next;
        j = 0;
       
        while(p != head && j < i)     //遍历到i结点
        {
                p = p->next;
                j ++;
        }
        if(j != i)
        {
                printf("ListInsert error..\n");
                return 0;
        }

        q = (DLNode *)malloc(sizeof(DLNode));
        q->data = x;                //插入数据元素x

        q->prior = p->prior;        //插入结点的前驱结点变成原结点p的前驱结点
        p->prior->next = q;         //原结点p的前驱结点的后继结点变为插入结点q
        q->next = p;
        p->prior = q;
        return 1;
}

int ListDelete(DLNode *head,int i,DataType *x)  //删除数据元素
{
        DLNode *p;
        int j = 0;
        p = head->next;

        while(p != head && j < i)
        {
                p = p->next;
                j ++;
        }
        if(j != i)
        {
                printf("ListDelete input i is error..\n");
                return 0;
        }
        *x = p->data;
        p->prior->next = p->next;
        p->next->prior = p->prior;


        free(p);           //记得释放动态内存空间
        return 1;
}

int ListLength(DLNode *head)   //求链表长度
{
        DLNode *p;
        int length = 0;
        p = head;

        while(p->next != head)
        {
                p = p->next;
                length ++;
        }
        return length;
}

int ListGet(DLNode *head,int i,DataType *x)   //取链表数据元素
{
        DLNode *p;
    p = head->next;
        int j = 0;
        while(p != head && j<i)
        {
                p = p->next;
                j ++;
        }
        if(j != i)
        {
                printf("ListGet input i is error...\n");
                return 0;
        }
        *x = p->data;
        return 1;
}

void ListDestroy(DLNode **head)    //销毁链表
{
        DLNode *p,*q;
        p = *head;

        while(p->next != *head)
        {
                q = p;
                p = p->next;
                free(q);
        }
        *head = NULL;   //记得头结点置NULL
}

int main()          //一个小程序 调用上述函数 实现双向循环链表简单功能
{
        DLNode *head;
        int i,x;

        ListIntiate(&head);         //初始化
        for(i = 0; i < 10 ;i ++)
        {
                ListInsert(head,i,i+1);  //插入数据1到10
        }
        ListDelete(head,4,&x);       //删除第5个元素
        for(i = 0; i < ListLength(head); i++)
        {
                ListGet(head,i,&x);      //取数据元素
                printf("%d\t",x);        //打印
        }
        printf("\n");
        ListDestroy(&head);          //销毁链表

        return 0;
}

ELI_

谢谢分享