双向链表 C语言 （创建，插入，删除，判空，返回链表长度）

嘿，(≧▽≦)/ 前几天在书上看见了双向链表，就学了一下，哈哈哈（〜^㉨^)〜

顾名思义，双向链表每个结点有两个指针域，一个指向前驱节点，一个指向后继结点。

但是双向链表在创建，插入，和删除操作上略有不同。例如在插入和删除时，不必像单链表一样只能在目标的前驱结点上操作

（觉得它能实现查询数据时上一个，下一个的功能哦！！）

下面只是我的一些想法，可能很菜啊    ╮(￣▽￣")╭；

结点定义如下：

typedef struct Node
{
    int data;
    struct Node *prior;  //指向前驱
    struct Node *next;   //指向后继
}Node,*pNode;    //这里 pNode 等价于 Node* 是指向结点的指针

函数声明如下：

pNode creat(int n);        //创建双向链表
void output(pNode h);    //打印双向链表
int if_empty(pNode);     //判空
int length(pNode h);      //返回链表长度
void Insert(pNode h,int i,int data);     //插入
void Delete(pNode h,int i);    //删除

各项功能的函数定义如下：

（1）创建双链表

pNode creat(int n)  //创建链表
{
    int i;
    pNode h,p,r;
    h=r=(pNode)malloc(sizeof(Node));//其中h是头指针，r是尾指针
    if(h==NULL)    //内存分配失败
        exit(-1);
    h->prior=h->next=NULL;  //将头节点的两个指针域都指向NULL
    printf("输入数据：");
    for(i=0; i<n; i++)
    {
        p=(pNode)malloc(sizeof(Node));
        if(h==NULL)      //内存分配失败
            exit(-1);
        scanf("%d",&p->data);
        p->next=NULL;
        r->next=p;
        p->prior=r;
        r=r->next;
    }
    return h;
}

  双向链表的创建我采用的是尾插法，因为如果是头插法则会有两种情况，1是在头结点和NULL之间插，2是在头结点与其后结点之间插，稍微麻烦一点点。而尾插法只需插在尾结点和NULL之间。在文章最后我附上了双向链表的头插法。

（2）打印链表，判空，返回链表长度

void output(pNode h)   //打印链表
{
    pNode p=h->next;
    printf("打印链表：");
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}

int empty(pNode h)    //判断链表是否为空
{
    pNode p=h->next;
    if(p==NULL)
        return 1;
    else
        return 0;
}

int length(pNode h)    //返回链表长度
{
    int length=0;
    pNode p=h->next;
    while(p)
    {
        length++;
        p=p->next;
    }
    return length;
}

（3）插入操作

void Insert(pNode h,int i,int data) //插入 1<=i<=length+1
{
    pNode p,r;
    p=r=h;
    int j=0;
    if(i==length(h)+1) //当插入的位置为length+1时
    {
        pNode q=(pNode)malloc(sizeof(Node));
        q->data=data;
        q->next=NULL;
        while(r->next) //找到链表尾结点
            r=r->next;
        r->next=q;
        q->prior=r;
    }
    else
    {
        while(p&&(j<i))  //找到第i个结点的
        {
            p=p->next;
            j++;
        }
        if(!p||(j>i)) 
            exit(-1);
        pNode q=(pNode)malloc(sizeof(Node));
        q->data=data;
        //插入的核心步骤
        q->prior=p->prior;
        p->prior->next=q;
        q->next=p;
        p->prior=q;
        //
    }
}

  1.插入有两种情况，一是在两结点之间，另外一个是最后一个节点与NULL之间。

  2.对于两节点之间插入的情况，指针p指向了其中一个节点，则新结点先与另一个结点连接，之后再与该结点连接。因为指针p已经记录了该结点的位置，不用担心指向它的指针域被覆盖。

（3）删除操作

void Delete(pNode h,int i)  //删除
{
    pNode p=h;
    int j=0;
    while(p&&(j<i))  //找到删除结点
    {
        p=p->next;
        j++;

    }
    if(p->next==NULL)
        p->prior->next=NULL;
    else
    {
        p->prior->next=p->next;
        p->next->prior=p->prior;
    }
    free(p);
}

  删除操作有p->next==NULL和p->next！=NULL两种情况

用于测试的主函数

int main()
{
    int n,i,data;
    pNode head;
    printf("输入输入数据个数");
    scanf("%d",&n);
    head=creat(n);
    output(head);
    printf("
输入插入 位置i 和 数据data :
");
    scanf("%d",&i);
    scanf("%d",&data);
    Insert(head,i,data);
    output(head);


    printf("
要删除第几个数据");
    scanf("%d",&i);
    Delete(head,i);
    output(head);
    return 0;
}

(≧▽≦)/(≧▽≦)/(≧▽≦)/(≧▽≦)/(≧▽≦)/(≧▽≦)/~~~~~~先结束了。

附录

双向链表的头插法

pNode creat(int n)
{
    int i;
    pNode h,p;
    h=(pNode)malloc(sizeof(Node));
    if(h==NULL)
        exit(-1);
    h->prior=h->next=NULL;
    printf("输入数据：");
    p=(pNode)malloc(sizeof(Node));
    if(h==NULL)
        exit(-1);
    scanf("%d",&p->data);
    h->next=p;
    p->prior=h;
    p->next=NULL;
    for(i=1; i<n; i++)
    {
        p=(pNode)malloc(sizeof(Node));
        if(h==NULL)
            exit(-1);
        scanf("%d",&p->data);
        p->next=h->next;
        h->next->prior=p;
        h->next=p;
        p->prior=h;
    }
    return h;
}