在双链表中插入结点

lixiangrong
2024-01-29 / 0 评论 / 41 阅读 / 正在检测是否收录...

在双链表中值为y的结点前插入一个值为x的结点

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

typedef int dataType;

// 3.5 双链表
typedef struct dLinkNode
{
    dataType data;
    struct dLinkNode *lLink,*rLink;
}dNode,*dLinkList;

// 1.初始化不带头结点的双链表
void init(dLinkList *head)
{
    *head = NULL;
}

// 2.输出双链表各结点的值
void display(dLinkList head)
{
    dNode *p = head;
    if(!p)
    {
        printf("双链表为空!\n");
        return;
    }
    do{
        printf("%d ",p->data);
        p = p->rLink;
    } while (p);
    printf("\n");
}

// 4.在双链表尾部插入值为x的结点
void rearInsert(dLinkList *head, dataType x)
{
    dNode *p = *head,*q;
    q = (dNode*) malloc(sizeof(dNode));
    q->data = x;
    q->rLink = NULL;
    if(!p) // 链表为空时
    {
        *head = q;
        q->lLink = NULL;
    } else
    {
        while (p->rLink) // 找到双链表的尾结点
            p = p->rLink;
        p->rLink = q;
        q->lLink = p;
    }
}

// 3.8.9 在双链表中值为y的结点前插入一个值为x的结点
void frontInsert(dLinkList *head, dataType y, dataType x)
{
    dNode *p = *head,*q; // p为工作指针,q为新结点指针
    if(!p)
    {
        printf("双链表为空,无法插入!\n");
        return;
    }
    while (p && p->data != y) // 找到y结点
        p = p->rLink;
    if(!p)
    {
        printf("没有这样的结点,无法插入!\n");
        return;
    }
    q = (dNode*) malloc(sizeof(dNode));
    q->data = x;
    if(p == *head) // 如果是头结点前插入
    {
        p->lLink = q;
        q->rLink = *head;
        q->lLink = NULL;
        *head = q; // 更新头结点
    } else
    {
        q->lLink = p->lLink;
        p->lLink->rLink = q;
        q->rLink = p;
        p->lLink = q;
    }
}

int main()
{
    dLinkList list; // 声明指向双链表的头指针
    init(&list); // 初始化双链表
    for (int i = 1; i <= 5; i++)
        rearInsert(&list,i); // 插入结点
    display(list); // 输出双链表
    dataType y = 1,x = 8;
    printf("在双链表中值为%d的结点前插入一个值为%d的结点\n",y,x);
    frontInsert(&list,y,x);
    display(list);
    return 0;
}
0

评论 (0)

取消