链表是linux c中非常重要的数据结构，双向链表与单向链表的区别，是它每个节点有两个指针域，分别指向该节点的前一个节点与后一个节点；
而链表的操作主要是查询、插入、删除、遍历等，下面来看一个双向链表，主要是进行写小练习，加深印象！
代码如下：
Dlist.h
[cpp]view plaincopy#ifndefDList_H #defineDList_H typedefintItem; typedefstructNode*PNode; typedefPNodePosition; /*定义节点类型*/ typedefstructNode { Itemdata;/*数据域*/ PNodeprevious;/*指向前驱*/ PNodenext;/*指向后继*/ }Node; /*定义链表类型*/ typedefstruct { PNodehead;/*指向头节点*/ PNodetail;/*指向尾节点*/ intsize; }DList; /*分配值为i的节点，并返回节点地址*/ PositionMakeNode(Itemi); /*释放p所指的节点*/ voidFreeNode(PNodep); /*构造一个空的双向链表*/ DList*InitList(); /*摧毁一个双向链表*/ voidDestroyList(DList*plist); /*将一个链表置为空表，释放原链表节点空间*/ voidClearList(DList*plist); /*返回头节点地址*/ PositionGetHead(DList*plist); /*返回尾节点地址*/ PositionGetTail(DList*plist); /*返回链表大小*/ intGetSize(DList*plist); /*返回p的直接后继位置*/ PositionGetNext(Positionp); /*返回p的直接前驱位置*/ PositionGetPrevious(Positionp); /*将pnode所指节点插入第一个节点之前*/ PNodeInsFirst(DList*plist,PNodepnode); /*将链表第一个节点删除并返回其地址*/ PNodeDelFirst(DList*plist); /*获得节点的数据项*/ ItemGetItem(Positionp); /*设置节点的数据项*/ voidSetItem(Positionp,Itemi); /*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/ PNodeRemove(DList*plist); /*在链表中p位置之前插入新节点S*/ PNodeInsBefore(DList*plist,Positionp,PNodes); /*在链表中p位置之后插入新节点s*/ PNodeInsAfter(DList*plist,Positionp,PNodes); /*返回在链表中第i个节点的位置*/ PNodeLocatePos(DList*plist,inti); /*依次对链表中每个元素调用函数visit()*/ voidListTraverse(DList*plist,void(*visit)()); #endif
DList.c
[cpp]view plaincopy#include"DList.h" #include<malloc.h> #include<stdlib.h> /*分配值为i的节点，并返回节点地址*/ PositionMakeNode(Itemi) { PNodep=NULL; p=(PNode)malloc(sizeof(Node)); if(p!=NULL) { p->data=i; p->previous=NULL; p->next=NULL; } returnp; } /*释放p所指的节点*/ voidFreeNode(PNodep) { free(p); } /*构造一个空的双向链表*/ DList*InitList() { DList*plist=(DList*)malloc(sizeof(DList)); PNodehead=MakeNode(0); if(plist!=NULL) { if(head!=NULL) { plist->head=head; plist->tail=head; plist->size=0; } else returnNULL; } returnplist; } /*摧毁一个双向链表*/ voidDestroyList(DList*plist) { ClearList(plist); free(GetHead(plist)); free(plist); } /*判断链表是否为空表*/ intIsEmpty(DList*plist) { if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist)) return1; else return0; } /*将一个链表置为空表，释放原链表节点空间*/ voidClearList(DList*plist) { PNodetemp,p; p=GetTail(plist); while(!IsEmpty(plist)) { temp=GetPrevious(p); FreeNode(p); p=temp; plist->tail=temp; plist->size--; } } /*返回头节点地址*/ PositionGetHead(DList*plist) { returnplist->head; } /*返回尾节点地址*/ PositionGetTail(DList*plist) { returnplist->tail; } /*返回链表大小*/ intGetSize(DList*plist) { returnplist->size; } /*返回p的直接后继位置*/ PositionGetNext(Positionp) { returnp->next; } /*返回p的直接前驱位置*/ PositionGetPrevious(Positionp) { returnp->previous; } /*将pnode所指节点插入第一个节点之前*/ PNodeInsFirst(DList*plist,PNodepnode) { Positionhead=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; returnpnode; } /*将链表第一个节点删除,返回该节点的地址*/ PNodeDelFirst(DList*plist) { Positionhead=GetHead(plist); Positionp=head->next; if(p!=NULL) { if(p==GetTail(plist)) plist->tail=p->previous; head->next=p->next; head->next->previous=head; plist->size--; } returnp; } /*获得节点的数据项*/ ItemGetItem(Positionp) { returnp->data; } /*设置节点的数据项*/ voidSetItem(Positionp,Itemi) { p->data=i; } /*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/ PNodeRemove(DList*plist) { Positionp=NULL; if(IsEmpty(plist)) returnNULL; else { p=GetTail(plist); p->previous->next=p->next; plist->tail=p->previous; plist->size--; returnp; } } /*在链表中p位置之前插入新节点s*/ PNodeInsBefore(DList*plist,Positionp,PNodes) { s->previous=p->previous; s->next=p; p->previous->next=s; p->previous=s; plist->size++; returns; } /*在链表中p位置之后插入新节点s*/ PNodeInsAfter(DList*plist,Positionp,PNodes) { 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++; returns; } /*返回在链表中第i个节点的位置*/ PNodeLocatePos(DList*plist,inti) { intcnt=0; Positionp=GetHead(plist); if(i>GetSize(plist)||i<1) returnNULL; while(++cnt<=i) { p=p->next; } returnp; } /*依次对链表中每个元素调用函数visit()*/ voidListTraverse(DList*plist,void(*visit)()) { Positionp=GetHead(plist); if(IsEmpty(plist)) exit(0); else { while(p->next!=NULL) { p=p->next; visit(p->data); } } } test.c[cpp]view plaincopy#include"DList.h" #include<stdio.h> voidprint(Itemi) { printf("数据项为%d\n",i); } main() { DList*plist=NULL; PNodep=NULL; plist=InitList(); p=InsFirst(plist,MakeNode(1)); InsBefore(plist,p,MakeNode(2)); InsAfter(plist,p,MakeNode(3)); 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("除了头节点该链表共有%d个节点\n",GetSize(plist)); FreeNode(DelFirst(plist)); printf("删除第一个节点后重新遍历输出为:\n"); ListTraverse(plist,print); printf("除了头节点该链表共有%d个节点\n",GetSize(plist)); DestroyList(plist); printf("链表已被销毁\n"); }
执行结果如下：
