C语言双向链表

#include "stdio.h"

#include "stdlib.h"

typedef int ElemType//元素类型

typedef struct DuLNode

{//双向链表

ElemType data

struct DuLNode *prior, *next

}DuLNode,*DuLinkList

int Create(DuLinkList &L)

{//建立双向链表

DuLinkList p,q

ElemType n,i

L = (DuLinkList) malloc (sizeof(DuLNode))

L->next = NULL

q = L

printf("输入数据个数:")

scanf("%d",&n)

printf("输入数据元素:")

for ( i = 0i <ni++)

{

p = (DuLinkList) malloc (sizeof(DuLNode))

scanf("%d",&p->data)//插入数仿信核据

p->prior = q

q->next = p

p->next = 0

q = q->next

}

return 1

}

int Visit(DuLinkList &L)

{//遍历双向链表

DuLinkList p

p = L->next

printf("双向链表为:")

while (p)

{

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

p = p->坦郑next

}

printf("\n")

return 1

}

int Clear(DuLinkList &L)

{

DuLinkList p

p = L->next

while(p)

{

L->next = p->next

free(p)

p = L->next

}

return 1

}

main()

{

int i,e,s,num

char c='y'

DuLinkList L

Create(L)

Visit(L)

while (c=='y')

{

printf("\n\n\n1.双向链表插入元素\n2.双向链表中删除元素\n")

printf("3.判断双向链表元素是否对称\n")

printf("4.双向链表中奇数排在偶数前面\n")

printf("5.建立递增链表并有序插入元素\n\n")

printf("选备掘择需要的 *** 作\n\n")

scanf("%d",&num)

switch(num)

{

case 1:

printf("输入插入元素位置以及元素:\n")

scanf("%d%d",&i,&e)

ListInsert(L, i, e)

Visit(L)

break

case 2:

printf("输入删除元素位置:")

scanf("%d",&i)

Delete(L,i,s)

printf("删除的元素为:%d\n",s)

Visit(L)

break

case 3:

if(Same(L)) printf("链表对称\n")

else printf("链表不对称\n")

break

case 5:

printf("清空原链表，建立递增链表:\n")

XCreate(L)

Visit(L)

break

case 4:

printf("奇数放在偶数前面:\n")

Jiou(L)

Visit(L)

break

}

printf("继续 *** 作(y/n):\n")

scanf("%s",&c)

}

}

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

/*

文件名 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）

---