双链表的一些基本考点（经过gcc调试并附带详细注释）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

双链表在笔试面试中也是常用考点，下面为双链表的一些基本操作，附带测试程序main,可在linux下通过gcc编译直接运行。

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

/*定义数据结构类型*/
typedef struct dnode
{
    int data;
    struct dnode *pre;/*前驱*/
    struct dnode *next;/*后继*/
} dlink;

/*****************************************************************
 *功能描述：创建一个带头结点的双链表，头结点数据域不存放有效数据
 *传入参数：无
 *传出参数：无
 *返回值： 创建后的双链表的头指针
 ****************************************************************/
dlink *creat()
{
    dlink *head = NULL;
    dlink *p = NULL;
    dlink *s = NULL;
    int d;

    /*为头结点分配空间*/
    head = (dlink *)malloc(sizeof(dlink));
    if(!head)
    {
        printf("error\n");
        exit(1);
    }

    p = head;
    while(1)
    {
        printf("please input data:");
        scanf("%d", &d);
        if(d <= 0)
        {
            break;/*当输入数据小于0时退出循环*/
        }
        s = (dlink *)malloc(sizeof(dlink));
        if(!s)
        {
            printf("error\n");
            exit(1);
        }
        s->data = d;

        /*将新增结点插入到链表尾部，并更新当前指针的指向*/
        p->next = s;
        s->pre = p;
        p = s;
    }

    p->next = NULL;/*将最后一个结点的后继赋空*/
    head->pre = NULL;/*将第一个结点的前驱赋空*/

    printf("create double list success\n");
    return head;
}

/*****************************************************************
 *功能描述：删除双链表中的一个结点
 *传入参数：head：双链表的头指针 num:需删除结点的数据域
 *传出参数：无
 *返回值： 删除结点后的双链表的头指针
 ****************************************************************/
dlink *del(dlink *head, int num)
{
    dlink *p = NULL;

    /*判断链表是否为空 */
    if(!head || !head->next)
    {
        printf("no data del\n");
        return NULL;
    }

    /*文中链表为带头结点的，从头结点的下一个结点开始*/
    p = head->next;

    /*如果num==p->data或者p->next为空即到了链表尾部则退出循环，通过此while循环找到需要删除的数据*/
    while((num!=p->data) && p->next)
    {
        p = p->next;
    }
    if(num == p->data)
    {
        if(!p->next)/*删除结点为尾结点*/
        {
            p->pre->next = NULL;
            free(p);
            printf("del tail\n");
        }
        else/*从前面代码可知删除的结点不可能为头结点，所以可以将其他情况归为一类*/
        {
            p->pre->next = p->next;
            p->next->pre = p->pre;

            free(p);
        }
    }
    else/*未找到要删除的结点*/
    {
        printf("couldn't been deleted the data:%d\n", num);
        return NULL;
    }

    printf("delete node success\n");

    return head;
}

/*****************************************************************
 *功能描述：插入一个新结点到双链表中
 *传入参数：head：双链表的头指针 num:需删除结点的数据域
 *传出参数：无
 *返回值： 插入结点后的双链表的头指针
 ****************************************************************/
dlink *insert(dlink *head, int num)
{
    dlink *p = NULL;
    dlink *p0 = NULL;

    /*判空*/
    if(!head || !head->next)
    {
        return NULL;
    }

    /*分配空间*/
    p0 = (dlink *)malloc(sizeof(dlink));
    if(!p0)
    {
        printf("malloc error\n");
        exit(1);
    }
    p0->data = num;
    p = head->next;

    /*确定插入位置*/
    while(p->next && (p0->data>p->data))
    {
        p = p->next;
    }
    if(p0->data <= p->data)
    {
        p->pre->next = p0;
        p0->pre = p->pre;
        p0->next = p;
        p->pre = p0;
    }
    else/*比任何数都大，直接插到链表尾部*/
    {
        p->next = p0;
        p0->pre = p;
        p0->next = NULL;
    }

    printf("insert success\n");

    return head;
}

/*****************************************************************
 *功能描述：打印一个带头结点的双链表中存放的数据（不包含头结点）
 *传入参数：无
 *传出参数：无
 *返回值： 无
 ****************************************************************/
void printl(dlink *head)
{
    dlink *p = NULL;

    if(!head || !head->next)
    {
        return;
    }
    p = head->next;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    return;
}

int main(void)
{
    dlink *p = NULL;
    dlink *head = NULL;
    int d;

    head = creat();
    printl(head);

    printf("please input insert data:");
    scanf("%d", &d);
    p = insert(head, d);
    printl(p);


    printf("please input del data:");
    scanf("%d", &d);
    p = del(head, d);
    printl(p);


    return 0;
}