双向链表
在线性链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋，则需从表头指针出发。换句话说，在单链表中，NextElem的执行时间是o(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双向链表。
//双链循环线性表的表示与实现 #include <stdio.h> #include <stdlib.h> /****************************************************************************** /* 数据类型和常量定义 /******************************************************************************/ #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int ElemType; /****************************************************************************** /* 数据结构声明 /******************************************************************************/ /* 线性表的双向链表存储结构 */ typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DuLinkList; //初始化双链循环线性表 Status InitList_DuL(DuLinkList &L) { L = (DuLinkList)malloc(sizeof(DuLNode)); L->next = L->prior = L; return OK; } //获取双链循环线性表中的元素 DuLNode * GetElemP_Dul(DuLinkList L, int i) { int j; struct DuLNode *p = L; if (i < 1) //非法i值 return NULL; if (p->next == L) //空双向循环链表 return L; p = L->next; j = 1; //初始化, p指向第一个结点, j为计数器 while(p != L && j < i) { //顺指针向后查找, 直到p指向第i个元素或p指向头结点 p = p->next; ++j; } return p; } //插入元素 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e //i的合法值为1 <= i <= 表长 + 1 struct DuLNode *p = NULL; struct DuLNode *s = NULL; if (!(p = GetElemP_Dul(L, i))) return ERROR; if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; } //删除元素 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) { //在带头结点的双链线性表L中, 删除第i个元素, 并由e返回其值 //i的合法值为1 <= i <= 表长 struct DuLNode *p = NULL; if (!(p = GetElemP_Dul(L, i)) || L == GetElemP_Dul(L, i)) return ERROR; e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; } //遍历线性表 Status ListTraverse_DuL(DuLinkList &L, Status (*Visit)(ElemType)) { printf("traverse list: "); struct DuLNode *p = L->next; //略过头结点 while (p != L) { Visit(p->data); p = p->next; } return OK; } //访问线性表中的元素 Status Visit(ElemType e) { printf("%d ", e); return OK; } //测试函数 void main() { DuLinkList L; ElemType e; InitList_DuL(L); //插入元素 if (OK == ListInsert_DuL(L, 0, 55)) printf("insert 55 succeed!\n"); if (OK == ListInsert_DuL(L, 1, 56)) printf("insert 56 succeed!\n"); ListTraverse_DuL(L, Visit); printf("\n"); if (OK == ListInsert_DuL(L, 2, 57)) printf("insert 57 succeed!\n"); if (OK == ListInsert_DuL(L, 1, 58)) printf("insert 58 succeed!\n"); ListTraverse_DuL(L, Visit); printf("\n"); //删除元素 if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1); if (OK == ListDelete_DuL(L, 3, e)) printf("the %drd elem deleted!\n", 3); if (OK == ListDelete_DuL(L, 4, e)) printf("the %dth elem deleted!\n", 4); else printf("delete the %dth elem failed!\n", 4); if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1); ListTraverse_DuL(L, Visit); printf("\n"); if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1); ListTraverse_DuL(L, Visit); printf("\n"); }