双链表的定义及其基本操作

双链表的定义

双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

双链表中结点类型的描述：

struct DouNode
{
struct DATATYPE data;
struct DouNode* next;
struct DouNode* prev;
};

双链表上的操作

初始化

 双链表与单链表一样，为了操作方便也可以加入头结点，那么初始化双链表其实就是定义一个头结点，然后将指针域置空。

struct DouLinkList* CreateDouLinkList() 
{
    struct DouLinkList* dl = (struct DouLinkList*) malloc(sizeof(struct DouLinkList));
    if(NULL == dl)
    {
        fprintf(stderr,"CreateDouLinkList malloc\n");
        return NULL;
    }
    dl->head = NULL;
    dl->clen = 0;
    return dl;
}

插入操作

//头插法建立双链表
int InsertHeadDouLinkList(struct DouLinkList* dl, struct DATATYPE* data) 
{
    struct DouNode * newnode =   (struct DouNode*)malloc(sizeof(struct DouNode));
    if(NULL == newnode)
    {
        fprintf(stderr,"inserthead malloc\n");
        return 1;
    }
    memcpy(&newnode->data,data,sizeof(struct DATATYPE));
    newnode->next = NULL;
    newnode->prev = NULL;

    newnode->next = dl->head;
    if(dl->head)
    {
        dl->head->prev = newnode;
    }
    dl->head  = newnode;
    dl->clen++;
    return 0;

}
//

//尾插法建立双链表
int InsertTailDouLinkList(struct DouLinkList*dl,struct DATATYPE*data)
{
    if(IsEmptyDouLinkList(dl))
    {
        return InsertHeadDouLinkList(dl,data);
    }
    else  
    {
        struct DouNode* tmp = dl->head ;
        while(tmp->next)
        {
            tmp= tmp->next;
        }

        struct DouNode* newnode = (struct DouNode*)malloc(sizeof(struct DouNode));
        if(NULL == newnode)
        {
            fprintf(stderr,"InsertTailDouLinkList malloc\n");
            return 1;
        }
        //初始化节点
        memcpy(&newnode->data,data,sizeof(struct DATATYPE));
        newnode->next  = NULL;
        newnode->prev = NULL;
       // 连接链表
        newnode->prev  = tmp;
        tmp->next  = newnode;
        dl->clen++;
    }
    return 0;
}
//

//按位插入
int InsertPosDouLinkList(struct DouLinkList*dl,struct DATATYPE*data,int pos)
{
    int len = GetSizeDouLinkList(dl);
    
    if(pos<0 || pos>len)
    {
        return 1;
    }
    if(0 == pos)
    {
        return InsertHeadDouLinkList(dl,data);
    }
    else if(pos == len)
    {
        return InsertTailDouLinkList(dl,data);
    }
    else 
    {
        struct DouNode* tmp = dl->head;
        int i = 0 ;
        for(i = 0 ;i<pos;++i)
        {
            tmp=tmp->next;
        }

        struct DouNode* newnode = (struct DouNode*)malloc(sizeof(struct DouNode));
        if(NULL == newnode)
        {
            fprintf(stderr,"InsertposDouLinkList malloc\n");
            return 1;
        }
        memcpy(&newnode->data , data,sizeof(struct DATATYPE));
        newnode->next  = NULL;
        newnode->prev  = NULL; 

        newnode->next  = tmp;
        newnode->prev  = tmp->prev;
        tmp->prev = newnode;
        newnode->prev->next  = newnode;
        dl->clen++;
    }
    return 0;
}
int IsEmptyDouLinkList(struct DouLinkList*dl)
{
    return 0 == dl->clen;

}
//

遍历操作

从单链表的第一个结点开始，依次遍历输出结点的数据直到最后一个结点。

int ShowDouLinkList(struct DouLinkList* dl,DIR dir) 
{
    struct DouNode* tmp = dl->head;
    if( FORWADR==dir)
    {
        while(tmp)
        {
            printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
            tmp=tmp->next;
        }
    }
    else if(BACKWADR == dir)
    {
        while(tmp->next)
        {
            tmp=tmp->next;
        } // end node 

        while(tmp)
        {
            printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
            tmp=tmp->prev;
        }
    }

查找操作

按值查找

 与单链表的按值查找是一样的，不会用到前驱结点指针prev。

struct DouNode* FindDouLinkList(struct DouLinkList* dl,char *name)
{
    if(IsEmptyDouLinkList(dl))
    {
        return NULL;
    }

    struct DouNode* tmp = dl->head;
    int len = GetSizeDouLinkList(dl);
    int i = 0 ;
    for(i = 0 ;i< len; ++i)
    {
        if(0 == strcmp(tmp->data.name,name))
        {
            return tmp;
        }
        tmp= tmp->next;
    }
    return NULL;
}

修改操作

int ModifyDouLinkList(struct DouLinkList* dl,char *name,struct DATATYPE* data)
{
    struct DouNode* ret = FindDouLinkList(dl,name);
    if(NULL == ret)
    {
        return 1;
    }
    memcpy(&ret->data,data,sizeof(struct DATATYPE));
    return 0;
}