/*
文件名 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<stdio.h>#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)//第二题输出结果
}
#include <stdio.h>typedef struct Link/*双向链表结构体*/
{
int data
struct Link *lift
struct Link *right
}linkx,*linky
linky Init()/*建立双向链表*/
void PrLink(linky p)/*输出双向链表*/
linky Sort(linky head)/*对双向链表排序*/
linky Swap(linky head,linky one,linky two)/*任意交换双向链表两个结点的地址*/
void main(void)
{
linky head
head=Init()
head=Sort(head)
PrLink(head)
}
linky Init()/*建立链表*/
{
linky p,q,head
int n=0
head=p=q=(linky)malloc(sizeof(linkx))
clrscr()
printf("please input 10 num: ")
scanf("%d",&p->data)/*输入数据*/
head->lift=NULL
n++
while(n!=10)/*一直输入到规定的数字个数停止*/
{
q=p
p=(linky)malloc(sizeof(linkx))
scanf("%d",&p->data)/*输入数据*/
q->right=p
p->lift=q
n++
}
p->right=NULL
return(head)
}
linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/
{linky temp
if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交换*/
{
if(one->right==two)/*只有两个结点的情况下*/
{
two->right=one
two->lift=NULL
one->lift=two
one->right=NULL
head=two
}
else/*有间隔的首尾交换*/
{
one->right->lift=two
two->lift->right=one
two->right=one->right
one->lift=two->lift
two->lift=one->right=NULL
head=two/*尾结点成为头结点*/
}
}
else if(two->right==NULL)/*尾和任意一个交换*/
{
if(one->right==two)/*交换最后两个结点*/
{
one->lift->right=two
two->lift=one->lift
two->right=one
one->lift=two
one->right=NULL
}
else/*和前面其他结点交换*/
{
temp=two->lift
temp->right=one
one->lift->right=two
one->right->lift=two
two->lift=one->lift
two->right=one->right
one->lift=temp
one->right=NULL
}
}
else if(one->lift==NULL)/*头和任意一个交换*/
{
if(one->right==two)/*交换头两个结点*/
{
two->right->lift=one
one->right=two->right
one->lift=two
two->right=one
two->lift=NULL
head=two
}
else/*头结点和后面其他结点交换*/
{
temp=one->right
temp->lift=two
one->lift=two->lift
one->right=two->right
two->lift->right=one
two->right->lift=one
two->right=temp
two->lift=NULL
head=two/*交换的结点成为头结点*/
}
}
else/*当中的任意两个交换*/
{
if(one->right==two)/*交换连在一起的两个结点*/
{
temp=one->lift
one->lift->right=two
one->right->lift=two
one->lift=two
one->right=two->right
two->right->lift=one
two->right=one
two->lift=temp
}
else/*交换隔开的两个结点*/
{
one->lift->right=two
one->right->lift=two
one->lift=two->lift
temp=one->right
one->right=two->right
two->lift->right=one
two->right->lift=one
two->right=temp
two->lift=one->lift
}
}
return(head)
}
linky Sort(linky head)/*对链表排序*/
{
linky i,j,t,p
int max
p=head
for(i=pi->right!=NULLi=i->right)/*用选择法的思想对这些结点排序*/
{
max=i->data
for(j=i->rightj!=NULLj=j->right)
if(j->data<max)
{
max=j->data
t=j
}
if(max!=i->data)/*如果没有找到比i小的结点*/
{
head=Swap(head,i,t)/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/
i=t
}
}
return(head)
}
void PrLink(linky p)/*输出链表*/
{
linky q
printf("Now the link: ")
do
{
q=p
printf("%d ",p->data)
p=p->right
free(q)/*释放输出结点*/
}
while(p!=NULL)
getch()
}
