双向非循环链表

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

#define NAMELEN 32
#define    ADDRLEN 128

/*双向链表的虚拟实现*/
typedef struct dunode
{
    char name[NAMELEN];
    char addr[ADDRLEN];
    char sex;
    float score;
    int id;
    struct dunode * next;
    struct dunode * prior;
}DUNODE;

typedef DUNODE * DuNodePtr;

int InitDuList(DuNodePtr * headptr);
int CreatDuNode(DuNodePtr * nodeptr, char * name, char * addr, char sex, float score, int id);
int LenDuList(DuNodePtr headptr);
int GetDuNode(DuNodePtr headptr, int num, DuNodePtr * nodeptr);
int AddDuNode(DuNodePtr headptr, DuNodePtr nodeptr);
int PrintAllDuNode(DuNodePtr headptr);
int InserDuNode(DuNodePtr headptr, int num, DuNodePtr nodeptr);
int DeleteDuNode(DuNodePtr headptr, int num);
int UnionDuList(DuNodePtr headptr1, DuNodePtr headptr2);
int SortDuNode(DuNodePtr headptr);
int SortDuNode2(DuNodePtr headptr);

int main(int argc, char ** argv)
{
    printf("*********双向非循环链表的操作********\n");

    DuNodePtr headptr = NULL;
    InitDuList(&headptr); /*需传指针的地址，才能改变指针变量的值*/

    DuNodePtr nodeptr = NULL;
    CreatDuNode(&nodeptr, "王贤才", "湖北", 'm', 100.00, 1);
    AddDuNode(headptr, nodeptr);
    CreatDuNode(&nodeptr, "张秋苹", "湖北", 'w', 100.00, 2);
    AddDuNode(headptr, nodeptr);
    CreatDuNode(&nodeptr, "程序员", "上海", 'm', 100.00, 3);
    AddDuNode(headptr, nodeptr);
    CreatDuNode(&nodeptr, "我老婆", "上海", 'w', 100.00, 4);
    AddDuNode(headptr, nodeptr);
    CreatDuNode(&nodeptr, "王贤才", "上海", 'm', 99.00, 6);
    AddDuNode(headptr, nodeptr);
    PrintAllDuNode(headptr);

    DuNodePtr getnodeptr = NULL;
    int num = 3;
    GetDuNode(headptr, num, &getnodeptr);
    printf("*************取得第[%d]个元素如下：************\n", num);
    printf(" id   =[%d]\n name =[%s]\n addr =[%s]\n sex  =[%c]\n score=[%.2f]\n", getnodeptr->id, getnodeptr->name, getnodeptr->addr, getnodeptr->sex, getnodeptr->score);

    CreatDuNode(&nodeptr, "我老子", "上海", 'm', 98.00, 5);
    num = 3;
    InserDuNode(headptr, num, nodeptr);

    /*
    num = 4;
    DeleteDuNode(headptr, num);
    */

    PrintAllDuNode(headptr);

    DuNodePtr headptr2 = NULL;
    InitDuList(&headptr2); /*需传指针的地址，才能改变指针变量的值*/

    DuNodePtr nodeptr2 = NULL;
    CreatDuNode(&nodeptr2, "王贤才", "湖北", 'm', 98.00, 13);
    AddDuNode(headptr2, nodeptr2);
    CreatDuNode(&nodeptr2, "张秋苹", "湖北", 'w', 99.00, 12);
    AddDuNode(headptr2, nodeptr2);
    CreatDuNode(&nodeptr2, "程序员", "上海", 'm', 100.00, 11);
    AddDuNode(headptr2, nodeptr2);

    UnionDuList(headptr, headptr2);
    PrintAllDuNode(headptr);

    SortDuNode(headptr);
    PrintAllDuNode(headptr);

    SortDuNode2(headptr);
    PrintAllDuNode(headptr);

    return 0;
}

/*功能：初始化双向非循环链表:（带头结点的）初始时链表为空*/
int InitDuList(DuNodePtr * headptr)
{
    printf("初始化双向链表......\n");
    *headptr = (DuNodePtr)malloc(sizeof(DUNODE)); /*头结点:数据域为空"*/
    (*headptr)->next = NULL;
    (*headptr)->prior = NULL;
    return 0;
}

/*创建一个节点*/
int CreatDuNode(DuNodePtr * nodeptr, char * name, char * addr, char sex, float score, int id)
{
    *nodeptr = (DuNodePtr)malloc(sizeof(DUNODE));
    memset((*nodeptr)->name, 0, sizeof(char)*NAMELEN);
    strcpy((*nodeptr)->name, name);
    memset((*nodeptr)->addr, 0, sizeof(char)*ADDRLEN);
    strcpy((*nodeptr)->addr, addr);
    (*nodeptr)->sex = sex;
    (*nodeptr)->score = score;
    (*nodeptr)->id = id;
    (*nodeptr)->next = NULL;
    (*nodeptr)->prior = NULL;
    return 0;
}

/*功能：求双向非循环链表的长度,参数node：头结点指针*/
int LenDuList(DuNodePtr headptr)
{
    int len = 0;
    DuNodePtr p = NULL;
    p = headptr->next;
    while(p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

/*功能：求双向非循环链表中的第num个元素的节点指针*/
int GetDuNode(DuNodePtr headptr, int num, DuNodePtr * nodeptr)
{
    DuNodePtr p = NULL;
    int count = 1;

    p = headptr->next;
    while((p != NULL)&&(count < num))
    {
        p = p->next;
        count++;
    }
    if((p == NULL)||(count > num))  /*第num个元素不存在*/
    {
        printf("第[%d]个元素不存在！\n", num);
        return -1;
    }
    else if((p != NULL)&&(count == num))  /*第num个元素存在*/
        {
            *nodeptr = p;
            return 0;
        }
}

/*功能：在双向非循环链表尾插入一个元素*/
int AddDuNode(DuNodePtr headptr, DuNodePtr nodeptr)
{
    printf("在链尾增加一个元素！\n");
    DuNodePtr p = NULL;

    p = headptr;
    while(p->next != NULL)  /*p指向最后一个节点元素了*/
    {
        p = p->next;
    }
    p->next = nodeptr;  /*连接后继指针*/
    nodeptr->prior = p; /*连接前驱指针*/
    return 0;
}

/*功能：打印出双向非循环链表中所有节点元素的信息*/
int PrintAllDuNode(DuNodePtr headptr)
{
    DuNodePtr p = NULL;
    p = headptr->next;
    printf("链表长度=[%d]\n", LenDuList(headptr));
    printf("显示链表的所有内容如下：\n");
    printf("*************************************************************************\n");
    printf("id        name        addr        sex        score\n");
    while(p != NULL)
    {
        printf("[%d]        [%s]    [%s]        [%c]        [%.2f]\n", p->id, p->name, p->addr, p->sex, p->score);
        p = p->next;
    }
    return 0;
}

/*功能：在双向非循环链表的第num个元素之前插入一个元素（先找到第num个元素）*/
int InserDuNode(DuNodePtr headptr, int num, DuNodePtr nodeptr)
{
    int count = 1;
    DuNodePtr p = NULL;
    p = headptr->next;
    while(p != NULL) /*p会指向第num个元素*/
    {
        if(count == num) break;
        p = p->next;
        count++;
    }

    if((p == NULL)||(count > num))  /*第num个元素不存在*/
    {
        printf("第[%d]个元素不存在！\n", num);
        return -1;
    }
    else if((p != NULL)&&(count == num))  /*p指向第num个元素*/
    {/*断链是有一定顺序的*/
        nodeptr->prior = p->prior;            /*第1步：让新节点的前驱指向第num-1个节点*/
        p->prior->next = nodeptr;            /*第2步：让第num-1个节点的后驱指向新节点*/
        p->prior = nodeptr;                    /*第3步：让第num个节点的前驱指向新节点*/
        nodeptr->next = p;                    /*第4步：让新节点的后驱指向第num个节点*/
        return 0;
    }

    return 0;
}

/*功能：删除双向非循环链表中的第num个元素*/
int DeleteDuNode(DuNodePtr headptr, int num)
{
    int count = 1;
    DuNodePtr p = NULL;

    p=headptr->next;
    while(p != NULL) /*p会指向第num个元素*/
    {
        if(count == num) break;
        p = p->next;
        count++;
    }

    if((p == NULL)||(count > num))  /*第num个元素不存在*/
    {
        printf("第[%d]个元素不存在！\n", num);
        return -1;
    }
    else if((p != NULL)&&(count == num))  /*p指向第num个元素*/
    {
        p->prior->next = p->next;            /*第1步：第num-1个元素的后继指向第num-2个元素*/
        p->next->prior = p->prior;            /*第2步：第num+1个元素的前驱指向第num-1个元素*/
        free(p);  /*删除的节点要释放*/
        return 0;
    }

    return 0;
}

/*功能：按照数据域中某个数据成员的值(id)对双向非循环链表的元素进行递减排序
使用条件：链表中至少要有2个节点元素*/
int SortDuNode(DuNodePtr headptr)
{
    int i, j, len;
    DuNodePtr p0 = NULL;
    DuNodePtr p1 = NULL;
    DuNodePtr p2 = NULL;
    DuNodePtr p3 = NULL;

    printf("对双链表排序如下：\n");
    len = LenDuList(headptr);
    printf("len=[%d]\n", len);
    /*只能用冒泡法排序：相邻两数比较，对链表来说，交换相邻两数要相对容易的多*/
    for(i=0; i
    {
        p0 = headptr;  /*p0指向头节点*/
        for(j=0; j
        {
            /*使每个元素都有自己的*/
            p1 = p0->next;
            p2 = p0->next->next;
            p3 = p0->next->next->next;
            /*p1，p2是要交换的2个节点的指针，p0是这2个节点之前的节点指针,p3值这2个节点之后的节点*/
            /*4个节点的指针都已经保存，就绝对不会断链了，也可以只定义3个*/
            if(p1->id < p2->id)
            {
                p1->next = p3;
                /*p2的next域非空：即若p2后面还有元素，则其后面的元素的前驱也要赋值
                如果其后面的元素不存在，当然其前驱也不存在了，也就不需要赋值*/
                if(p3 != NULL)
                {
                    p3->prior = p1;
                }
                p0->next = p2;
                p2->prior = p0;
                p2->next = p1;
                p1->prior = p2;
            }
            p0 = p0->next;  /*第一个最小的已经排好，所以p0可以指向下一个节点了*/
        }
    }

    return 0;
}

/*功能：按照数据域中某个数据成员的值(id)对双向非循环链表的元素进行递增排序
使用条件：链表中至少要有2个节点元素*/
int SortDuNode2(DuNodePtr headptr)
{
    int i, j, len;
    DuNodePtr p0 = NULL, p1 = NULL, p2 = NULL, p3 = NULL;

    printf("对双链表排序如下：\n