《双向链表也叫双链表.docx》由会员分享，可在线阅读，更多相关《双向链表也叫双链表.docx（30页珍藏版）》请在三一办公上搜索。
1、双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。 所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造 双向循环链表。一、循环链表循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指 向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。2、在判断是否到表尾时，
2、是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。二、双向链表双向链表其实是单链表的改进。当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这 是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能 定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构 呢？这就是双向链表。在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域;一个存储直接前驱结点地址，一般称之为左链域。在c
3、语言中双向链表结点类型可以定义为：typedef struct node(int data; /* 数据域 */struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/ JD;当然，也可以把一个双向链表构建成一个双向循环链表。双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。双向链表的基本运算：1、查找假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时我们同样从表头结点 往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾。下例就是应用双向循环链表查找算法的一个程
4、序。searchpoint=search(head,studname);printf(你所要查找的人的姓名是:s”,*&searchpoint- name);/*线性表的双向链表存储结构*/typedef struct DuLNode(ElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*带头结点的双向循环链表的基本操作(14个)*/void InitList(DuLinkList *L)( /*产生空的双向循环链表L */*L=(DuLinkList)malloc(sizeof(DuLNode);(bud(d)M-(：
5、txCDuAdnb) /* 亦邮前d*/(l*_L!.dCDzM /* 嵯蜩|=0 /*!邮堪氐艘也所制那-咪蜩义嗤I) (!* -SPIMUnnausnAOHS a po (Mo_lu_a:LJJouxCDS-CDm* Hod 4 (|*|艾 u 4 (I*)(l*w5*L=NULL;void ClearList(DuLinkList L) /* 不改变 L */( /*初始条件：L已存在。操作结果：将L重置为空表*/DuLinkList q,p=L-next; /* p 指向第一个结点 */ while(p!=L) /* p 没到表头 */t;free(p);p=q;L-next=L-pr
6、ior=L; /*头结点的两个指针域均指向自身*/ Status ListEmpty(DuLinkList L)( /*初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */if(L-next=L&L-prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkList L)( /*初始条件：L已存在。操作结果：返回L中数据元素个数*/int i=0;DuLinkList p=L-next; /* p 指向第一个结点 */while(p!=L) /* p 没到表头 */ (i+；p=p-next;retu
7、rn i;Status GetElem(DuLinkList L,int i,ElemType *e)( /*当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */ int j=1; /* j为计数器*/DuLinkList p=L-next; /* p 指向第一个结点 */while(p!=L&jnext;j+;if(p=L|ji) /*第i个元素不存在*/return ERROR;*e=p-data; /* 取第 i 个元素 */return OK;int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,
8、ElemType)( /*初始条件：L已存在，compare()是数据元素判定函数*/*操作结果：返回l中第1个与e满足关系compare()的数据元素的位序。*/*若这样的数据元素不存在，则返回值为0 */int i=0;DuLinkList p=L-next; /* p 指向第 1 个元素 */while(p!=L)(i+；if(compare(p-data,e) /*找到这样的数据元素*/return i;p=p-next;return 0;Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)( /*操作结果：若cur
9、_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*/*否则操作失败，pre_e无定义*/DuLinkList p=L-next-next; /* p 指向第 2 个元素 * while(p!=L) /* p 没到表头 */if(p-data=cur_e)*pre_e=p-prior-data;return TRUE;p=p-next;return FALSE;Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)( /*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*/*否则
10、操作失败，next_e无定义*/DuLinkList p=L-next-next; /* p 指向第 2 个元素 */while(p!=L) /* p 没到表头 */(if(p-prior-data=cur_e)(*next_e=p-data;return TRUE;p=p-next;return FALSE;DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */( /*在双向链表L中返回第i个元素的地址。i为0 ,返回头结点的地址。若第i个元素不存在，*/* 返回 NULL */int j;DuLinkList p=L; /* p 指向头结点 */i
11、f(iListLength(L) /* i 值不合法 */return NULL;for(j=1;jnext;return p;Status ListInsert(DuLinkList L,int i,ElemType e)( /*在带头结点的双链循环线性表L中第i个位置之前插入元素e , i的合法值为1i表长+1 */*改进算法2.18，否则无法在第表长+1个结点之前插入元素*/DuLinkList p,s;if(iListLength(L)+1) /* i 值不合法 */return ERROR;p=GetElemP(L,i-1); /*在L中确定第i个元素前驱的位置指针p */if(!p
12、) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)*/return ERROR;s=(DuLinkList)malloc(sizeof(DuLNode);if(!s)return OVERFLOW;s-data=e;s-prior=p; /*在第i-1个元素之后插入*/s-next=p-next;p-next-prior=s;p-next=s;return OK;Status ListDelete(DuLinkList L,int i,ElemType *e)( /*删除带头结点的双链循环线性表L的第i个元素，i的合法值为1i表长*/DuLinkList p;if(
13、idata;p-prior-next=p-next;p-next-prior=p-prior;free(p);return OK; void ListTraverse(DuLinkList L,void(*visit)(ElemType)( /*由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit() */DuLinkList p=L-next; /* p 指向头结点 */while(p!=L)(visit(p-data);p=p-next;printf(n);void ListTraverseBack(DuLinkList L,void(*visit)(ElemType)( /*由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()。另加*/DuLinkList p=L-prior; /* p 指向尾结点 */ while(p!=L)visit(p-data);p=p-prior;printfCV);
