双向链表
和单向链表相比有以下优势：
插入删除不需要移动元素外，可以原地插入删除
可以双向遍历
结构体定义如下：
typedef struct Node
{
DateType data;
struct Node *next,*prior;
}Node,*LinkList;
双向循环链表的操作实现：
在双向循环链表中，有如下指针关系：设指针p指向双向循环链表中的第i个结点，则p->next指向第i+1个结点，p->next->prior仍指向第i个结点，即p->next->prior==p；同样地，p->prior指向第i-1个结点，p->prior->next仍指向第i个结点，即p->prior->next==p。双向循环链表的上述指针关系可以方便算法设计。
双向循环链表指针关系
初始化
int InitList(DLNode **head)
{
*head = (DLNode *)malloc(sizeof(DlNode));
(*head)->prior = *head;
(*head)->next = *head;
return 1;
}
插入数据元素
和单链表相比，双向循环链表的插入算法指针p可以直接指在第i个结点上，而不需要让指针p指在第i-1个结点上。
双向循环链表的插入过程
删除数据元素
和单链表相比，双向循环链表的删除算法指针p可以直接指在第i个结点上，而不需要让指针p指在第i-1个结点上。
循环双向链表的删除过程
双向链表的C语言实现:
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ // 用到的库文件 #include <stdio.h> // printf();scanf() #include <stdlib.h> // exit() #include <malloc.h> // malloc() #include <time.h> // srand((unsigned)time(NULL)); // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 // Status是函数的类型，其值是函数结果状态代码 typedef int Status; // #define ElemType int // 也可以用宏定义确定ElemType类型 typedef int ElemType; // -----双向链表----- typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱 struct DuLNode *next; // 指向后继 } DuLNode, *DuLinkList; // 操作结果：构造一个空的线性表L。 Status InitList_DuL(DuLinkList &L) { if(L != NULL) { printf("线性表已存在！！！"); return INFEASIBLE; // 返回-1 } L = (DuLinkList)malloc(sizeof(DuLNode)); if(!L) { // 存储分配失败 printf("初始化失败！！！"); exit(OVERFLOW); // exit(-2)程序异常退出 } L->next = L; // 先建立一个带头结点的双向链表， L->prior = L; // 并使头结点2个指针域指向本身（即头指针L） return OK; }// InitList_DuL // 操作结果：销毁线性表L。 Status DestroyList_DuL(DuLinkList &L) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; } DuLinkList p = L->next, ptmp; // p指向线性表第一个结点(线性表为空表时，指向头结点) while(p != L) { // p指向头结点时，循环停止 ptmp = p->next; free(p); // 释放每个数据结点的指针域 p = ptmp; } free(L); // 释放头结点 L = NULL; return OK; }// DestroyList_DuL // 操作结果：将L重置为空表。 Status ClearList_DuL(DuLinkList &L) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; } if(L->next == L) { printf("线性表本已空！！！"); return INFEASIBLE; } DuLinkList p = L->next, ptmp; // p指向线性表第一个结点 while(p != L) { // p指向头结点时，循环停止 ptmp = p->next; free(p); // 释放每个结点的指针域 p = ptmp; } L->next = L; // 头结点指针域指向本身 return OK; }// ClearList_DuL // 操作结果：若L为空表，返回TRUE，否则返回FALSE Status ListEmpty_DuL(DuLinkList L) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; // 返回-1 } else if(L->next == L) { printf("线性表为空。"); return TRUE; // 返回1 } else { printf("线性表非空。"); return FALSE; // 返回0 } }// ListEmpty_DuL // 操作结果：返回L中数据元素个数。 int ListLength_DuL(DuLinkList L) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; // 返回-1 } int nElem = 0; DuLinkList p = L->next; // p指向第一个结点(空表时，指向头结点) while(p != L) { nElem ++; p = p->next; } return nElem; }// ListLength // 操作结果：用e返回L中第i个数据元素的值。1≤i≤ListLength(L) 。 Status GetElem_DuL(DuLinkList L, int i, ElemType &e) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; // 返回-1 } DuLinkList p = L->next; // p指向第一个结点(空表时，指向头结点) int j = 1; // j为计数器，统计当p指向第i个数据时，表中已有元素个数 while ( (p->next != L) && j<i ) // 顺指针向后查找，直到p指向第i个元素或p指向头结点 { p = p->next; ++j; } if ( p==L || j<i || i<1 ) // p == L 指向头结点，说明表为空表。j<i i的值大于表中现有元素个数。 i<1 传入参数有问题。 { return ERROR; // 第i个元素不存在 } e = p->data; // 取第i个元素 return OK; }// GetElem_DuL 算法2.8更改 // 操作结果：用p返回L中第i个数据元素的指针。1≤i≤ListLength(L)。 DuLinkList GetElemP_DuL(DuLinkList L, int i) { DuLinkList p = L; // p指向头结点 int j = 0; // j为计数器，统计当p指向第i个结点时，表中已有元素个数 // p->next == L，表为空。i>j，超出查找范围 while ( (p->next != L) && j<i ) // 顺指针向后查找，直到p指向第i个元素或p指向头结点 { p = p->next; ++j; } if ( i<1 || i>j+1 ) // i>j+1 i的值大于表长+1。 i<1 传入参数有问题。 { return NULL; // i大于表长加1时，p=NULL } // 插入时：i=表长加1，返回头结点; if ( i==j+1 ) { return L; } return p; // i<表长加1时，p指向第i个结点; }// GetElem_DuL 更改 // 操作结果：返回L中第1个与e满足compare()(数据元素判定函数)的数据元素的位序，若这样的数据元素不存在，则返回值为0。 Status compare(ElemType listElem, ElemType e) { return listElem == e ? TRUE : FALSE; }// Compare int LocateElem_DuL(DuLinkList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; // 返回-1 } int pos = 1; DuLinkList p = L->next; // p指向第一个结点(空表时，指向头结点) while( (p != L) && !(*pfn_compare)(p->data, e) ) { ++ pos; p = p->next; // 指针后移p->next = L时，循环回到头结点 } // p == L 指向头结点，说明表为空表。pos>ListLength_DuL(L) pos的值大于表中现有元素个数。 if( (p == L) || pos>ListLength_DuL(L) ) { return ERROR; // 返回0 } return pos; }// LocateElem_DuL // 操作结果：若cur_e是L的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。 Status PriorElem_DuL(DuLinkList L, ElemType cur_e, ElemType &pre_e) { int i = LocateElem_DuL(L, cur_e, compare); // cur_e为第一个元素，其前驱为最后一个元素 if(i==0 || i==1) { GetElem_DuL(L, ListLength_DuL(L), pre_e); return OK; } GetElem_DuL(L, i-1, pre_e); return OK; }// PriorElem_DuL // 操作结果：若cur_e是L的数据元素，则用next_e返回它的后继，否则操作失败，pre_e无定义。 Status NextElem_Sq(DuLinkList L, ElemType cur_e, ElemType &next_e) { int i = LocateElem_DuL(L, cur_e, compare); // cur_e为最后一个元素，其后继为第一个元素 if(i==0 || i==ListLength_DuL(L)) { GetElem_DuL(L, 1, next_e); return OK; } GetElem_DuL(L, i+1, next_e); return OK; }// NextElem_Sq // 操作结果：在L中第pos个位置插入新的元素e，L的长度加1。1≤pos≤ListLength(L)+1。 Status ListInsert_DuL(DuLinkList &L, int pos, ElemType e) { if(!L) { // 线性表是否存在 printf("线性表未初始化。"); return INFEASIBLE; } DuLinkList p, s; if( !(p = GetElemP_DuL(L, pos) ) ) { // 在L中确定插入位置指针p printf("插入位置不合法。"); return ERROR; // i等于表长加1时，p指向头结点;i大于表长加1时，p=NULL } if( !(s = (DuLinkList)malloc(sizeof(DuLNode)) ) ) {// 生成新结点 printf("存储分配失败。"); return ERROR; } s->data = e; // 将插入的元素值 赋给 新生成结点的数据域 s->prior = p->prior; // 插入结点 反向指向 前驱 p->prior->next = s; // 前驱 指向 插入结点 s->next = p; // 插入结点 指向 后继 p->prior = s; // 后继 反向指向 插入结点 printf("插入的位置：%d, 插入的元素：%d", pos, e); return OK; }// ListInsert_DuL 算法2.18更改 // 操作结果：删除L的第pos个数据元素，并用e返回其值,L的长度减1。1≤pos≤ListLength(L)。 Status ListDelete_DuL(DuLinkList &L, int pos, ElemType &e) { if(!L) { // 线性表是否存在 printf("线性表未初始化。"); return INFEASIBLE; } DuLinkList p; if( !(p = GetElemP_DuL(L, pos)) || p==L) { // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL或p=L时，即第pos个元素不存在 } e = p->data; // 要删除结点的数据域，赋给e p->prior->next = p->next; // 删除结点前驱 指向 删除结点后继 p->next->prior = p->prior; // 删除结点后继 指向 删除结点前驱 free(p); // 释放指针变量p return OK; }// ListDelete_DuL 算法2.19更改 // 操作结果：依次对L的每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。 Status visit(ElemType e) { printf("%d <-> ", e); return OK; } Status ListTraverse_DuL(DuLinkList L, Status (*pfn_visit)(ElemType)) { if(!L) { printf("线性表未初始化。"); return INFEASIBLE; } if(L->next == L) { printf("线性表为空表。"); return ERROR; } DuLinkList p = L->next; // p指向第一个结点 while(p != L) { visit(p->data); p = p->next; } return OK; }// ListTraverse // 创建随机表,包含10个随机数（头插法）。 void CreateList_DuL_10(DuLinkList &L) { // 提供随机数种子 srand((unsigned)time(NULL)); // 生成头结点 L = (DuLinkList)malloc(sizeof(DuLNode)); if(!L) { printf("存储分配失败！！！"); exit(OVERFLOW); // exit(-1)程序异常退出 } L->next = L; // 头结点指针域指向本身 L->prior = L; for (int i=0; i<10; i++) { // 生成新结点 DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode)); // scanf("%d", &p->data); // 输入元素值 赋给新生成结点的数据域 p->data = rand()%100; // 插入到表头 p->next = L->next; // 插入结点 指向 后继 p->prior = L; // 插入结点 反向指向 头结点 L->prior->next = p; // 后继 反向指向 插入结点 L->next = p; // 头结点 指向 插入结点 //printf("%d ", p->data); // 查看是否插入了新的元素 } }// CreateList_DuL_10 // 逆位序输入(随机产生)n个元素的值，建立带表头结点的线性表L（头插法）。 void CreateList_DuL_Head(DuLinkList &L, int n) { srand((unsigned)time(NULL)); // 初始化随机数种子 // 先建立一个带头结点的单链表 L = (DuLinkList)malloc(sizeof(DuLNode)); if(!L) { printf("存储分配失败！！！"); exit(OVERFLOW); // exit(-1)程序异常退出 } L->next = L; // 头结点指针域指向本身 L->prior = L; L->data = 5201314; for (int i=n; i>0; --i) { DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));// 生成新结点 // scanf("%d", &p->data); // 输入元素值 // 随机生成100以内的数字 p->data = rand()%100; // 将生成的元素值赋给新生成结点的数据域 // p->data = i; // 将生成的元素值赋给新生成结点的数据域 // 插入到表头 p->next = L->next; // 插入结点 指向 第一个结点 L->next->prior = p; // 第一个结点 反向指向 插入结点 p->prior = L; // 插入结点 反向指向 头结点 L->next = p; // 头结点 指向 插入结点 } }// CreateList_DuL 算法2.11更改 // 顺位序输入(随机产生)n个元素的值，建立带表头结点的线性表L（尾插法）。 void CreateList_DuL_Tail(DuLinkList &L, int n) { srand((unsigned)time(NULL)); // 初始化随机数种子 // 先建立一个带头结点的单链表 L = (DuLinkList)malloc(sizeof(DuLNode)); if(!L) { printf("存储分配失败！！！"); exit(OVERFLOW); // exit(-1)程序异常退出 } L->next = L; // 头结点指针域指向本身 L->prior = L; for (int i=0; i<n; ++i) { DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode)); // scanf("%d", &p->data); // 输入元素值 // 随机生成100以内的数字 p->data = rand()%100; // 将生成的元素值赋给新生成结点的数据域 // 插入到表尾 p->prior = L->prior; // 插入结点 反向指向 表尾结点 L->prior->next = p; // 表尾结点 指向 插入结点 p->next = L; // 插入结点 指向 头结点 L->prior = p; // 头结点 反向指向 插入结点 } } // 初始化菜单 void initMenu() { printf("\n\t\t*****************************************\n"); printf("\n\t\t\t\t 循环双向链表\n"); printf("\n\t\t 1.创建随机表\t\t 2.构造空线性表\n\t\t 3.销毁线性表\t\t 4.清空线性表\n\t\t 5.线性表是否为空\t 6.线性表的长度"); printf("\n\t\t 7.查找表中元素\t 8.插入新元素\n\t\t 9.删除某个元素\t 10.遍历线性表\n\t\t 11.回到主菜单\t\t 0.退出"); } // 回到主菜单 void mainMenu() { printf("\n\t\t*****************************************\n"); printf("\n\t\t\t\t 循环双向链表\n"); printf("\n\t\t 1.创建随机表\t\t 2.构造空线性表\n\t\t 3.销毁线性表\t\t 4.清空线性表\n\t\t 5.线性表是否为空\t 6.线性表的长度"); printf("\n\t\t 7.查找表中元素\t 8.插入新元素\n\t\t 9.删除某个元素\t 10.遍历线性表\n\t\t 11.回到主菜单\t\t 0.退出"); } int main() { DuLinkList L = NULL; initMenu(); int select = -1; while(select != 0) { printf("\n\n请选择你的操作："); scanf("%d", &select); switch(select) { case 1:// 创建随机表 { int nCreateOption = -1; while(nCreateOption!=0 && nCreateOption!=11) { printf("\n1.头插法 2.尾插法 3.10个元素的随机表 11.回到主菜单 0.退出查找\n请选择你的操作："); scanf("%d", &nCreateOption); switch(nCreateOption) { case 1:// 1.头插法 { printf("请输入要创建的随机表元素个数："); int nElem; scanf("%d", &nElem); CreateList_DuL_Head(L, nElem); printf("头插法创建随机链表："); ListTraverse_DuL(L, visit); } break; case 2:// 2.尾插法 { printf("请输入要创建的随机表元素个数："); int nElem; scanf("%d", &nElem); CreateList_DuL_Tail(L, nElem); printf("尾插法创建随机链表："); ListTraverse_DuL(L, visit); } break; case 3:// 3.10个元素的随机表 CreateList_DuL_10(L); printf("10个元素的随机表："); ListTraverse_DuL(L, visit); break; case 11:// 11.回到主菜单 mainMenu(); break; case 0:// 0.退出查找 break; default: printf("请输入正确的数字!!!\n"); break; } } } break; case 2:// 构造空线性表 printf("构造一个空的线性表L。"); InitList_DuL(L); break; case 3:// 销毁线性表 printf("销毁线性表L。"); DestroyList_DuL(L); break; case 4:// 清空线性表 printf("将L重置为空表。"); ClearList_DuL(L); break; case 5:// 线性表是否为空 ListEmpty_DuL(L); break; case 6:// 线性表的长度 { int lLength = ListLength_DuL(L); if(lLength != -1) printf("线性表的长度为: %d ", lLength); } break; case 7:// 查找表中元素 { int nSearchOption = -1; while(nSearchOption!=0 && nSearchOption!=11) { printf("1.按位置查找\t 2.按元素查找\t 11.回到主菜单\t 0.退出查找\n请选择你的操作："); scanf("%d", &nSearchOption); switch(nSearchOption) { case 1:// 1.按位置查找 { int pos; ElemType e; printf("请输入要查找的位置："); scanf("%d", &pos); int ret = GetElem_DuL(L, pos, e); if (ret == -1) { printf("\n"); break; } else if (ret == 0) { printf("查找位置不正确！\n"); break; } printf("第%d个元素的值为：%d ", pos, e); ElemType pre_e, next_e; if(PriorElem_DuL(L, e, pre_e)) printf("前一个元素为：%d ", pre_e); if(NextElem_Sq(L, e, next_e)) printf("后一个元素为：%d", next_e); printf("\n"); } break;// 2.按元素查找 case 2: { printf("请输入要查找的元素："); ElemType e; scanf("%d", &e); int pos = LocateElem_DuL(L, e, compare); if (pos == -1) { printf("\n"); break; } else if (pos == 0) { printf("没有值为%d的元素。\n", e); break; } printf("值为%d是表中的第%d个元素。\n", e, pos); } break; case 11:// 11.回到主菜单 mainMenu(); break; case 0:// 0.退出查找 break; default: printf("请输入正确的数字!!!\n"); break; } } } break; case 8:// 插入新元素 { ElemType e; int pos; int nInsertOption = -1; while(nInsertOption) { printf("请输入要插入的元素位置和元素的值："); scanf("%d %d", &pos, &e); int ret = ListInsert_DuL(L, pos, e); // 线性表未初始化，中断循环，回到主界面 if(ret == -1) break; // 插入位置不合法，结束本次循环，继续下次循环 else if(!ret) { printf("\n"); continue; } // 插入元素 printf("\n现在线性表为："); ListTraverse_DuL(L, visit); printf("\n1.是 0.否 是否继续: "); scanf("%d", &nInsertOption); } } break; case 9:// 删除某个元素 { int nDeleteOption = -1; while(nDeleteOption!=0 && nDeleteOption!=11) { printf("1.按位置删除\t 2.按元素删除\t 11.回到主菜单\t 0.退出删除\n请选择你的操作："); scanf("%d", &nDeleteOption); switch(nDeleteOption) { case 1: // 1.按位置删除 { ElemType e; int pos; printf("请输入要删除的位置："); scanf("%d", &pos); int ret = ListDelete_DuL(L, pos, e); if (ret == -1) { printf("\n"); break; } else if (ret == 0) { printf("删除位置不正确！\n"); break; } printf("现在线性表为："); ListTraverse_DuL(L, visit); printf("\n"); } break; case 2: // 2.按元素删除 { printf("请输入要删除的元素："); ElemType e; scanf("%d", &e); // 删除的将是第一个出现的元素 int pos = LocateElem_DuL(L, e, compare); if (pos == -1) { printf("\n"); break; } else if (pos == 0) { printf("没有值为%d的元素。", e); break; } printf("值为%d是表中的第%d个元素。", e, pos); ListDelete_DuL(L, pos, e); printf("\n现在线性表为："); ListTraverse_DuL(L, visit); printf("\n"); } break; case 11:// 11.回到主菜单 mainMenu(); break; case 0:// 0.退出查找 break; default: printf("请输入正确的数字!!!\n"); break; } } } break; case 10:// 遍历线性表 printf("遍历线性表："); ListTraverse_DuL(L, visit); break; case 11:// 回到主菜单 mainMenu(); break; case 0:// 退出 break; default: printf("请输入正确的数字!!!"); break; } } return 0; }