双链表及其实现

#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");
}

// 3.查找双链表中第i个结点
dNode *find(dLinkList head, int i)
{
    dNode *p = head;
    if(i < 1)
    {
        printf("非法的索引！\n");
        return NULL;
    }
    if(!p)
    {
        printf("双链表为空！\n");
        return NULL;
    }
    int j = 1;
    while (p->rLink && i != j)
    {
        p = p->rLink;
        j++;
    }
    if(i > j)
        return NULL;
    return p;
}

// 4.找到双链表的尾结点
dNode *rear(dLinkList head)
{
    dNode *p = head;
    if(!p)
        return NULL;
    while (p->rLink)
        p = p->rLink;
    return p;
}

// 5.在双链表尾部插入值为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
    {
        p = rear(p);
        p->rLink = q;
        q->lLink = p;
    }
}

// 6.在双链表的第i个结点后插入值为x的新结点
void insert(dLinkList *head, int i, dataType x)
{
    if(i < 0)
    {
        printf("非法的插入位置！\n");
        return;
    }
    dNode *p = *head,*q;
    q = (dNode*) malloc(sizeof(dNode));
    q->data = x;
    q->rLink = NULL;
    if(i == 0) // 在表头插入
    {
        if(p) // 链表非空时
        {
            q->rLink = *head;
            (*head)->lLink = q;
            *head = q;
        }
        q->lLink = NULL;
        *head = q;
        return;
    }
    p = find(*head,i);
    if(p)
    {
        if(p->rLink) // 如果p不是尾结点
            p->rLink->lLink = q;
        q->rLink = p->rLink; // 以下两行不可换位置
        q->lLink = p;
        p->rLink = q;
    } else
        printf("插入索引越界！\n");
}

// 7.双链表中删除一个值为x的结点
void del(dLinkList *head, dataType x)
{
    dNode *p = *head;
    if(!p)
    {
        printf("链表为空，无法删除！\n");
        return;
    }
    while (p) // 寻找要删除的p结点
    {
        if(p->data == x)
            break;
        p = p->rLink;
    }
    if(p)
    {
        if(!p->lLink && !p->rLink) // 只有一个结点时
        {
            free(p);
            *head = NULL;
            return;
        }
        if(!p->lLink) // 如果删除首结点
        {
            *head = p->rLink;
            p->rLink->lLink = NULL;
            free(p);
            return;
        }
        if(!p->rLink) // 如果删除尾结点
        {
            p->lLink->rLink = NULL;
            free(p);
            return;
        } // 中间结点的删除
        p->lLink->rLink = p->rLink;
        p->rLink->lLink = p->lLink;
        free(p);
        return;
    } else
        printf("没有找到这样的结点，无法删除！\n");
}

int main()
{
    dLinkList list; // 声明指向双链表的头指针
    init(&list); // 初始化双链表
    display(list); // 输出双链表
    for (int i = 1; i <= 5; i++)
        rearInsert(&list,i); // 插入结点
    display(list);
    int i = 5;
    dataType x = 6;
    dNode *n = find(list,i);
    if(n)
        printf("链表的第%d个元素是%d\n",i,n->data);
    else
        printf("链表访问越界！\n");
    printf("在第%d个位置后面插入元素%d\n",i,x);
    insert(&list,i,x);
    display(list);
    printf("删除一个值为%d的元素\n",x);
    del(&list,x);
    display(list);
    return 0;
}