C语言：循环双链表的创建，插入，删除-蒲公英云

C语言：循环双链表的创建，插入，删除

电玩女神 2022-08-03 11:51 312阅读 0赞

/*
    双向循环链表的创建，插入，删除
*/
# include <stdio.h>
# include <malloc.h>
//节点类型
typedef struct node
{
    int data;
    struct node * pNext;
    struct node * pPrior;
}NODE, *PNODE;
PNODE creat_list();  //建立链表
void traverse(PNODE pHead);  //遍历链表
void insert(PNODE pHead, int pos, int val);  //在链表的第pos位置插入元素val
int Length(PNODE pHead);  //求链表的长度
void getEle(PNODE pHead, int pos);  //获取第pos位置的前驱、后继元素
void dele(PNODE pHead, int pos);  //删除第pos位置的元素
int main(void)
{
    PNODE pHead = creat_list();  //创建循环双链表
    traverse(pHead);
    //在第pos节点前插入新节点
    printf("在第1个节点前插入4：");
    insert(pHead, 1, 4);
    traverse(pHead);
    //获取pos位置的前驱、后继
    getEle(pHead, 2);
    getEle(pHead, 3);
    //删除第pos位置的元素
    printf("删除第4个节点：");
    dele(pHead, 4);
    traverse(pHead);
    return 0;
}
//创建循环双链表
PNODE creat_list()
{
    int len;
    int val;
    int i;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));  //创建头结点
    pHead->pNext = pHead;
    pHead->pPrior = pHead;
    PNODE pTail = pHead;
    PNODE pNew;
    printf("链表节点个数为 len = ");
    scanf("%d", &len);
    for(i = 0; i < len; i++)
    {
        printf("输入第%d个节点的值：", i+1);
        scanf("%d", &val);
        pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data = val;
        pNew->pPrior = pTail;
        pNew->pNext = pHead;
        pTail->pNext = pNew;
        pTail = pNew;
    }
    return pHead;
}
//遍历链表
void traverse(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while(p != pHead)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}
//在第pos位置前插入元素val
void insert(PNODE pHead, int pos, int val)
{
    PNODE p = pHead->pNext;   //p指向首节点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    int len = Length(pHead);
    int count = 0;  //计数器
    if(1 == pos)  //新节点插在首节点前
    {
        pNew->pNext = p;
        p->pPrior = pNew;
        pNew->pPrior = pHead;
        pHead->pNext = pNew;
    }
    //获取第pos-1个节点的指针p,新节点插在p后面
    else if(pos > 1 && pos <= len + 1) 
    {
        while(p != pHead)
        {
            count ++;
            if(count == pos - 1)
            {
                pNew->pNext = p->pNext;
                p->pNext->pPrior = pNew;
                p->pNext = pNew;
                pNew->pPrior = p;
                break;
            }
            p = p->pNext;
        }
    }
    else
    {
        printf("插入位置错误");
        return;
    }
}
//求链表的长度
int Length(PNODE pHead)
{
    int len = 0;
    PNODE p = pHead->pNext; //p指向首节点
    while(p != pHead)
    {
        len ++;
        p = p->pNext;
    }
    return len;
}
//获取第pos个节点的前驱，后继
void getEle(PNODE pHead, int pos)
{
    PNODE p = pHead->pNext;
    int count = 0;
    while(p != pHead)
    {
        count ++;
        if(count == pos)  //获取第pos节点的指针
        {
            if(p->pPrior == pHead)
            {
                printf("第%d个节点的前驱数头结点\n", pos);
            }
            else
            {
                printf("第%d个节点的前驱是：%d\n", pos, p->pPrior->data);
            }
            if(p->pNext == pHead)
            {
                printf("第%d个节点的后继数头结点\n", pos);
            }
            else
            {
                printf("第%d个节点的后继是：%d\n", pos, p->pNext->data);
            }        
        }
        p = p->pNext;
    }
}
//删除第pos节点
void dele(PNODE pHead, int pos)
{
    PNODE p = pHead->pNext;
    int count = 0;
    int len = Length(pHead);
    if(1 == pos)  //删除首节点
    {
        pHead->pNext = p->pNext;
        p->pNext->pPrior = pHead;
    }
    else if(pos > 1 && pos < len + 1)
    {
        while(p != pHead)
        {
            count ++;
            if(count == pos - 1)  //获取第pos-1节点的指针p
            {
                p->pNext = p->pNext->pNext;
                p->pNext->pNext->pPrior = p;
                break;
            }
            p = p->pNext;
        }
    }
    else
    {
        printf("删除位置错误");
        return ;
    }
}