/*

文件名 doublelnk.h

作用 定义必要的结构体，并对双向链表的操作函数做声明

*/

/************************************************************************/

#ifndef DList_H

#define DList_H

typedef  int Item

typedef struct Node * PNode

typedef PNode Position

/*定义节点类型*/

typedef struct Node

{

Item id /*编号*/

Item data /*数据域*/

PNode previous /*指向前驱*/

PNode next /*指向后继*/

}Node

/*定义链表类型*/

typedef struct

{

PNode head /*指向头节点*/

PNode tail /*指向尾节点*/

int size

}DList

enum enumSortType

{

ID,

DATA

}

/*分配值为i的节点，并返回节点地址*/

Position MakeNode(Item id, Item data)

/*释放p所指的节点*/

void FreeNode(PNode p)

/*构造一个空的双向链表*/

DList* InitList()

/*摧毁一个双向链表*/

void DestroyList(DList *plist)

/*将一个链表置为空表，释放原链表节点空间*/

void ClearList(DList *plist)

/*返回头节点地址*/

Position GetHead(DList *plist)

/*返回尾节点地址*/

Position GetTail(DList *plist)

/*返回链表大小*/

int GetSize(DList *plist)

/*返回p的直接后继位置*/

Position GetNext(Position p)

/*返回p的直接前驱位置*/

Position GetPrevious(Position p)

/*将pnode所指节点插入第一个节点之前*/

PNode InsFirst(DList *plist,PNode pnode)

/*将链表第一个节点删除并返回其地址*/

PNode DelFirst(DList *plist)

/*获得节点的数据项*/

Item GetItem(Position p)

/*设置节点的数据项*/

void SetItem(Position p,Item i)

/*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/

PNode Remove(DList *plist)

/*在链表中p位置之前插入新节点S*/

PNode InsBefore(DList *plist,Position p,PNode s)

/*在链表中p位置之后插入新节点s*/

PNode InsAfter(DList *plist,Position p,PNode s)

/*返回在链表中第i个节点的位置*/

PNode LocatePos(DList *plist,int i)

void ListTraverse(DList *plist,void (*visit)(Node))

/*对双向链表按照执行的排序方式进行排序*/

void SortDLnk(DList * plist, enumSortType sortType)

void SortDLnkbyID(DList * plist)

void SortDLnkbyData(DList * plist)

void swapnode(PNode anode, PNode bnode)

#endif

/************************************************************************/

/*

文件名 doublelnk.cpp

作用 对双向链表的操作函数进行具体实现

*/

/************************************************************************/

#include"doublelnk.h"

#include<malloc.h>

#include<stdlib.h>

/*分配值为i的节点，并返回节点地址*/

Position MakeNode(Item id, Item data)

{

PNode p = NULL 

p = (PNode)malloc(sizeof(Node))

if(p!=NULL)

{

p->id =id

p->data = data

p->previous = NULL

p->next = NULL

}

return p

}

/*释放p所指的节点*/

void FreeNode(PNode p)

{

free(p)

}

/*构造一个空的双向链表*/

DList * InitList()

{

DList *plist = (DList *)malloc(sizeof(DList))

PNode head = MakeNode(0, 0) 

if(plist!=NULL)

{

if(head!=NULL)

{

plist->head = head

plist->tail = head

plist->size = 0

}

else

return NULL

}

return plist

}

/*摧毁一个双向链表*/

void DestroyList(DList *plist)

{

ClearList(plist)

free(GetHead(plist))

free(plist)

}

/*判断链表是否为空表*/

int IsEmpty(DList *plist)

{

if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))

return 1

else

return 0

}

/*将一个链表置为空表，释放原链表节点空间*/

void ClearList(DList *plist)

{

PNode temp,p

p = GetTail(plist)

while(!IsEmpty(plist))

{

temp = GetPrevious(p)

FreeNode(p)

p = temp

plist->tail = temp

plist->size--

}

}

/*返回头节点地址*/

Position GetHead(DList *plist)

{

return plist->head

}

/*返回尾节点地址*/

Position GetTail(DList *plist)

{

return plist->tail

}

/*返回链表大小*/

int GetSize(DList *plist)

{

return plist->size

}

/*返回p的直接后继位置*/

Position GetNext(Position p)

{

return p->next

}

/*返回p的直接前驱位置*/

Position GetPrevious(Position p)

{

return p->previous

}

/*将pnode所指节点插入第一个节点之前*/

PNode InsFirst(DList *plist,PNode pnode)

{

Position head = GetHead(plist)

if(IsEmpty(plist))

plist->tail = pnode

plist->size++

pnode->next = head->next

pnode->previous = head

if(head->next!=NULL)

head->next->previous = pnode

head->next = pnode

return pnode 

}

/*将链表第一个节点删除,返回该节点的地址*/

PNode DelFirst(DList *plist)

{

Position head = GetHead(plist)

Position p=head->next

if(p!=NULL)

{

if(p==GetTail(plist))

plist->tail = p->previous

head->next = p->next

head->next->previous = head

plist->size--

}

return p

}

/*获得节点的数据项*/

Item GetItem(Position p)

{

return p->data

}

/*设置节点的数据项*/

void SetItem(Position p,Item i)

{

p->data = i

}

/*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/

PNode Remove(DList *plist)

{

Position p=NULL

if(IsEmpty(plist))

return NULL

else

{

p = GetTail(plist)

p->previous->next = p->next

plist->tail = p->previous

plist->size--

return p

}

}

/*在链表中p位置之前插入新节点s*/

PNode InsBefore(DList *plist,Position p,PNode s)

{

s->previous = p->previous

s->next = p

p->previous->next = s

p->previous = s

plist->size++

return s

}

/*在链表中p位置之后插入新节点s*/

PNode InsAfter(DList *plist,Position p,PNode s)

{

s->next = p->next

s->previous = p

if(p->next != NULL)

p->next->previous = s

p->next = s

if(p = GetTail(plist))

plist->tail = s

plist->size++

return s

}

/*返回在链表中第i个节点的位置*/

PNode LocatePos(DList *plist,int i)

{

int cnt = 0

Position p = GetHead(plist)

if(i>GetSize(plist)||i<1)

return NULL

while(++cnt<=i)

{

p=p->next

}

return p

}

/*依次对链表中每个元素调用函数visit()*/  

void ListTraverse(DList *plist,void (*visit)(Node))  

{  

Position p = GetHead(plist)  

if(IsEmpty(plist))  

exit(0)  

else  

{  

while(p->next!=NULL)  

{  

p = p->next  

visit(*p)            

}         

}  

}  

void SortDLnk(DList * plist, enumSortType sortType)

{

switch(sortType)

{

case ID:

SortDLnkbyID(plist)

break

case DATA:

SortDLnkbyData(plist)

break

}

}

void SortDLnkbyID(DList * plist)

{

PNode head = plist->head

Node tmpnode

Position currnode = head

Position bianlinode

while ((currnode=currnode->next) != NULL)

{

bianlinode =currnode

while((bianlinode=bianlinode->next) != NULL)

{

if (currnode->id > bianlinode->id)

{

swapnode(currnode, bianlinode)

}

}

}

}

void SortDLnkbyData(DList * plist)

{

PNode head = plist->head

Node tmpnode

Position currnode = head

Position bianlinode

while ((currnode=currnode->next) != NULL)

{

bianlinode =currnode

while((bianlinode=bianlinode->next) != NULL)

{

if (currnode->data > bianlinode->data)

{

swapnode(currnode, bianlinode)

}

}

}

}

void swapnode(PNode anode, PNode bnode)

{// 这里面要特别注意防止前驱节点是头结点和后驱节点是Null的情况

Node tmpnode

tmpnode.id = anode->id

tmpnode.data = anode->data

anode->id = bnode->id

anode->data = bnode->data

bnode->id = tmpnode.id

bnode->data = tmpnode.data

}

/************************************************************************/

/*

文件名 program.cpp

作用 对双向链表的操作函数进行测试

*/

/************************************************************************/

#include"doublelnk.h"

#include<stdio.h>

void print(Node node)

{

printf("数据项: id=%d, data=%d \n",node.id, node.data)

}

int main()

{

DList *plist = NULL

PNode p = NULL

plist = InitList()

p = InsFirst(plist,MakeNode(12, 23))

InsBefore(plist,p,MakeNode(2, 54))

InsAfter(plist,p,MakeNode(3, 34))

printf("p前驱位置的值为%d\n",GetItem(GetPrevious(p)))

printf("p位置的值为%d\n",GetItem(p))

printf("p后继位置的值为%d\n",GetItem(GetNext(p)))

printf("遍历输出各节点数据项:\n")

ListTraverse(plist,print)

printf("按照ID排序后遍历输出:\n")

SortDLnk(plist, ID)

ListTraverse(plist,print)

printf("按照Data排序后遍历输出:\n")

SortDLnk(plist, DATA)

ListTraverse(plist,print)

printf("除了头节点该链表共有%d个节点\n",GetSize(plist))

FreeNode(DelFirst(plist))

printf("删除第一个节点后重新遍历输出为:\n")

ListTraverse(plist,print)

printf("除了头节点该链表共有%d个节点\n",GetSize(plist))

DestroyList(plist)

printf("链表已被销毁\n")

return 0

}

程序总共分三部分， 分别是双向链表的头文件、源文件和测试程序

建立工程后，分别建立相应的文件并添加相应代码应该就可以

下面的图片是我的运行效果（声明：程序中很多代码参考了以为前辈的代码http://blog.csdn.net/hopeyouknow/article/details/6716177）

直接在链表中排序太麻烦，不如把关键字和指针单独抽取出来放到一个结构体数组中

然后对这个数组进行排序，排好后按相应指针顺序输出链表元素即可

在输入规模不大的情况下增加了一些空间代价，但是却可使代码简化不少，应该是可行的。

当然直接交换双向链表中的两个元素也非难事。

#include<malloc.h>

#define ElemType int

int count=0

typedef struct DulNode

{

ElemType data

DulNode *prior

DulNode *next

}DulNode,*DulLinkList

//初始化链表，结束后产生一个头结点指针

void InitDLList(DulLinkList *L)

{

(*L)=(DulLinkList)malloc(sizeof(DulNode))

(*L)->next=*L

(*L)->prior=(*L)->next

}

//对链表进行插入操作

void ListInsert(DulLinkList *L)

{

int i=0,n

ElemType temp

DulNode *s,*p

p=(*L)->next

printf("请输入插入元素数量：\n")

scanf("%d",&n)

count=n

printf("请输入%d个自然数\n",n)

while(i<n)

{

scanf("%d",&temp)

s=(DulNode*)malloc(sizeof(DulNode))

s->data=temp

while((p!=(*L))&&(p->data<temp))//查找所要插入的位置

{

p=p->next

}

s->prior=p->prior//新节点的插入

s->next=p

p->prior->next=s

p->prior=s

p=(*L)->next//将指针回指到链表第一个非空节点，主要是为了下次查找插入位置

i++

}

}

void Display(DulLinkList L)

{

DulNode *p

p=L->next

printf("双向链表中的数据为:\n")

while(p!=L)

{

printf("%d ",p->data)

p=p->next

}

printf("\n")

}

void Sort(DulLinkList *L)

{

ElemType temp

DulNode *p,*q

p=(*L)->next

q=(*L)->prior

if(count%2!=0)

q=q->prior

p=p->next

while(p!=q)

{

temp=p->data

p->data=q->data

q->data=temp

p=p->next

if(p!=q) //第二题只需交换节点数据

q=q->prior//这几个if else语句需要仔细

else

break

if(p!=q)

p=p->next

else

break

if(p!=q)

q=q->prior

else

break

}

}

void main()

{

DulLinkList L

InitDLList(&L)//初始化链表

ListInsert(&L)//顺序插入数据

Display(L)//显示结果

Sort(&L)//第二题操作

Display(L)//第二题输出结果

}