数据结构实验二之线性表（下）

实验题5:实现循环双链表的各种基本运算的算法

题目描述

编写一个程序cdlinklist.cpp,实现循环双链表的各种基本运算和整体建表算法

(假设循环双链表的元素类型ElemType为int),并在此基础上设计一个程序exp2-5.cpp

完成以下功能。

(1)初始化循环双链表h。

(2)依次采用尾插法插入元素a、b、c、d、e。

(3)输出循环双链表h。

(4)输出循环双链表h的长度。

(5)判断循环双链表h是否为空。

(6)输出循环双链表的第3个元素。

(7)输出元素a的位置。

(8)在第4个元素的位置上插入元素i

(9)输出循环双链表。

(10)副除循环双链表的第3个元素。

(11)输出循环双链表。

(12)释放循环双链表L。

算法:cdlinklist.cpp程序,其中包含如下函数。

· InitList(DLinkNode*&L),初始化循环双链表L。

· DestroyList(DLinkNode *I.):释放循环双链表L。

· ListEmpty(DLinkNode *L):判断循环双链表L是否为空表。

· ListLength(DLinkNode*L):返回循环双链表I中的元素个数。

· DispList(DLinkNode *L);输出循环双链表L。

• GetElem(DLinkNode*L.int i,ElemType &e);获取循环双链表L中的第i个元素。

· LocateElem(DLinkNode*L,ElemType e);在循环双链表L中查找元素e。

· ListInsert(DLinkNode&L,int i,ElemType e),在循环双链表L中的第i个位置上插入元素e。

· ListDelete(DLinkNode * &L,int i,ElemType &e):从循环双链表L中删除第i个元素。

运行代码

cdlinklist.cpp

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>typedef int ElemType;
typedef struct DNode
{ElemType data;struct DNode* prior;struct DNode* next;
} DLinkNode;// 头插法创建循环双链表
void CreateListF(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s;// 分配头结点空间L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = NULL;// 遍历数组，用头插法插入节点for (int i = 0; i < n; i++){s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];// 将新节点插入头结点之后s->next = L->next;if (L->next != NULL) L->next->prior = s;L->next = s;s->prior = L;}// 找到尾结点s = L->next;while (s->next != NULL){s = s->next;}// 尾结点的 next 指向头结点s->next = L;// 头结点的 prior 指向尾结点L->prior = s;
}// 尾插法创建循环双链表
void CreateListR(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s, * r;// 分配头结点空间，初始化头结点的 next 和 prior 指向自身L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L;L->prior = L;r = L;// 遍历数组，用尾插法插入节点for (int i = 0; i < n; i++){s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];// 将新节点插入尾结点之后r->next = s;s->prior = r;r = s;}// 尾结点的 next 指向头结点r->next = L;// 头结点的 prior 指向尾结点L->prior = r;
}// 初始化循环双链表
void InitList(DLinkNode*& L)
{// 分配头结点空间，初始化头结点的 next 和 prior 指向自身L = (DLinkNode*)malloc(sizeof(DLinkNode));L->prior = L;L->next = L;
}// 销毁循环双链表
void DestroyList(DLinkNode*& L)
{DLinkNode* pre = L, * p = pre->next;// 遍历链表释放节点内存while (p != L){free(pre);pre = p;p = p->next;}// 释放最后一个节点（此时 pre 指向最后一个节点）free(pre);
}// 判断循环双链表是否为空
bool ListEmpty(DLinkNode* L)
{return L->next == L;
}// 求循环双链表的长度
int ListLength(DLinkNode* L)
{DLinkNode* p = L;int i = 0;// 遍历链表计算长度while (p->next != L){p = p->next;i++;}return i;
}// 输出循环双链表
void DispList(DLinkNode* L)
{DLinkNode* p = L->next;// 遍历链表输出节点数据while (p != L){printf("%c ", p->data);p = p->next;}printf("\n");
}// 求循环双链表中第 i 个元素的值
bool GetElem(DLinkNode* L, int i, ElemType& e)
{int j = 1;DLinkNode* p = L;if (i <= 0) return false;if (i == 1){// 提取第一个节点的值e = L->next->data;return true;}p = L->next;while (j < i && p != L){j++;p = p->next;}if (p == L)return false;else{// 提取第 i 个节点的值e = p->data;return true;}
}// 查找第一个值域为 e 的元素的序号
int LocateElem(DLinkNode* L, ElemType e)
{int i = 1;DLinkNode* p = L->next;// 遍历链表查找特定值的节点while (p != L && p->data != e){p = p->next;i++;}if (p == L)return 0;elsereturn i;
}// 在循环双链表中插入第 i 个元素
bool ListInsert(DLinkNode*& L, int i, ElemType e)
{int j = 1;DLinkNode* p = L, * s;if (i <= 0) return false;if (L->next == L){// 链表为空时插入节点s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = L;s->prior = L;L->next = s;L->prior = s;return true;}if (i == 1){// 在第一个位置插入节点s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = L->next;L->next->prior = s;s->prior = L;L->next = s;return true;}p = L->next;while (j < i - 1 && p != L){j++;p = p->next;}if (p == L)return false;else{s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = p->next;if (p->next != L) p->next->prior = s;s->prior = p;p->next = s;return true;}
}// 删除循环双链表中第 i 个元素
bool ListDelete(DLinkNode*& L, int i, ElemType& e)
{int j = 1;DLinkNode* p = L, * q;if (i <= 0 || L->next == L)return false;if (i == 1){// 删除第一个元素q = L->next;e = q->data;L->next = q->next;if (q->next != L) q->next->prior = L;free(q);return true;}p = L->next;while (j < i - 1 && p != L){j++;p = p->next;}if (p == L)return false;else{q = p->next;if (q == L) return false;e = q->data;p->next = q->next;if (q->next != L) q->next->prior = p;free(q);return true;}
}

excp2-5.cpp

#include <stdio.h>
#include <stdlib.h>
#include "cdlinklist.cpp"int main() {DLinkNode* h;ElemType e;printf("循环双链表的基本运算如下:\n");printf("(1)初始化循环双链表 h\n");InitList(h);printf("(2)依次采用尾插法插入元素 a,b,c,d,e\n");ListInsert(h, 1, 'a');ListInsert(h, 2, 'b');ListInsert(h, 3, 'c');ListInsert(h, 4, 'd');ListInsert(h, 5, 'e');printf("(3)输出循环双链表 h:");DispList(h);printf("(4)循环双链表 h 长度:%d\n", ListLength(h));printf("(5)循环双链表 h 为%s\n", (ListEmpty(h) ? "空" : "非空"));GetElem(h, 3, e);printf("(6)循环双链表 h 的第 3 个元素:%c\n", e);printf("(7)元素 a 的位置:%d\n", LocateElem(h, 'a'));printf("(8)在第 4 个元素位置上插入元素 f\n");ListInsert(h, 4, 'f');printf("(9)输出循环双链表 h:");DispList(h);printf("(10)删除 h 的第 3 个元素\n");ListDelete(h, 3, e);printf("(11)输出循环双链表 h:");DispList(h);printf("(12)释放循环双链表 h\n");DestroyList(h);return 1;
}

代码结果与思路

定义了一个循环双链表的节点结构体DNode（重命名为DLinkNode），包含以下成员：

data：存储节点的数据，这里数据类型为ElemType，实际上是int类型。
prior：指向前驱节点的指针。
next：指向后继节点的指针。

创建链表函数
- 头插法创建循环双链表（CreateListF）：
  - 首先为头结点分配内存空间，并将头结点的next指针置为NULL。
  - 然后遍历输入的数组，对于数组中的每个元素：分配新节点s的内存空间。将新节点s的数据域设置为当前数组元素的值。将新节点s插入到头结点之后，具体操作是让新节点的next指针指向原来头结点的下一个节点，如果原来头结点有下一个节点，则让原来头结点的下一个节点的前驱指针指向新节点；再让头结点的next指针指向新节点，新节点的前驱指针指向头结点。
  - 接着找到尾结点，即从新的头结点开始遍历，直到找到next指针为NULL的节点。
  - 让尾结点的next指针指向头结点，同时让头结点的prior指针指向尾结点，形成循环双链表。
- 尾插法创建循环双链表（CreateListR）：
  - 同样先为头结点分配内存空间，并将头结点的next和prior指针都指向自身，形成只有一个头结点的循环双链表。
  - 设置一个指针r指向头结点，作为尾指针。
  - 遍历输入数组，对于每个元素：分配新节点s的内存空间。将新节点s的数据域设置为当前数组元素的值。将新节点s插入到尾指针r之后，具体操作是让尾指针r的next指针指向新节点，新节点的前驱指针指向尾指针r；然后更新尾指针r为新节点。
  - 最后让尾指针的next指针指向头结点，同时让头结点的prior指针指向尾指针，形成循环双链表。
初始化链表函数（InitList）：为循环双链表分配头结点空间，并将头结点的next和prior指针都指向自身，形成只有一个头结点的循环双链表。
销毁链表函数（DestroyList）：
- 从链表的第一个有效节点开始，依次释放每个节点的内存空间。设置两个指针pre和p，pre初始指向头结点，p初始指向头结点的下一个节点。
- 当p不等于头结点时，释放pre所指节点的内存空间，然后将pre指向p，p指向p的下一个节点。
- 当p等于头结点时，说明链表中的所有节点都已释放，再释放pre所指的头结点的内存空间。
判断链表是否为空函数（ListEmpty）：只需要检查头结点的next指针是否指向自身，如果是，则链表为空，返回true；否则返回false。
求链表长度函数（ListLength）：
- 从链表的第一个有效节点开始遍历，设置一个指针p指向头结点的下一个节点，设置一个计数器i初始值为 0。
- 当p的next指针不等于头结点时，说明还有节点未遍历，计数器i加一，移动指针p指向下一个节点。
- 遍历结束后，返回计数器i的值，即为链表的长度。
输出链表函数（DispList）：
- 从链表的第一个有效节点开始输出，设置一个指针p指向头结点的下一个节点。
- 当p不等于头结点时，输出p所指节点的数据域，然后移动指针p指向下一个节点，继续输出直到回到头结点。
求链表中第 i 个元素的值函数（GetElem）：
- 首先检查输入的序号i是否合法（大于 0），如果不合法则返回false。
- 如果i等于 1，直接提取头结点的下一个节点的值并返回true。
- 如果i大于 1，设置一个指针p指向头结点的下一个节点，一个计数器j初始值为 1。
- 当j小于i且p不等于头结点时，计数器j加一，移动指针p指向下一个节点，目的是找到第i个节点。
- 如果遍历结束后p等于头结点，说明没有找到第i个节点，返回false；否则将p所指节点的数据域赋值给参数e，并返回true。
查找第一个值域为 e 的元素的序号函数（LocateElem）：
- 从链表的第一个有效节点开始查找，设置一个计数器i初始值为 1，设置一个指针p指向头结点的下一个节点。
- 当p不等于头结点且p所指节点的数据域不等于要查找的值e时，计数器i加一，移动指针p指向下一个节点。
- 如果遍历结束后p等于头结点，说明没有找到值为e的节点，返回 0；否则返回计数器i的值，即找到的节点的序号。
在链表中插入第 i 个元素函数（ListInsert）：
- 首先检查输入的序号i是否合法（大于 0），如果不合法则返回false。
- 如果链表为空，即头结点的next指针指向自身，直接在头结点之后插入新节点，具体操作是分配新节点s的内存空间，设置新节点的数据域为要插入的值e，让新节点的next和prior指针分别指向头结点和头结点的前驱指针，再让头结点的next和前驱指针分别指向新节点。
- 如果i等于 1，直接在头结点之后插入新节点，具体操作是分配新节点s的内存空间，设置新节点的数据域为要插入的值e，让新节点的next指针指向头结点的下一个节点，新节点的前驱指针指向头结点，然后让头结点的下一个节点的前驱指针指向新节点，头结点的next指针指向新节点。
- 如果i大于 1，设置一个指针p指向头结点的下一个节点，一个计数器j初始值为 1。
- 当j小于i - 1且p不等于头结点时，计数器j加一，移动指针p指向下一个节点，目的是找到要插入位置的前一个节点。
- 如果遍历结束后p等于头结点，说明没有找到要插入位置的前一个节点，返回false。
- 分配新节点s的内存空间，设置新节点的数据域为要插入的值e。
- 将新节点s插入到节点p之后，具体操作是让新节点的next指针指向p的下一个节点，如果p有下一个节点，则让p的下一个节点的前驱指针指向新节点；再让新节点的前驱指针指向p，p的next指针指向新节点。
删除链表中第 i 个元素函数（ListDelete）：

首先检查输入的序号i是否合法（大于 0）以及链表是否为空，如果不合法或链表为空则返回false。
如果i等于 1，直接删除头结点的下一个节点，具体操作是设置一个指针q指向头结点的下一个节点，将q所指节点的数据域赋值给参数e，让头结点的next指针指向q的下一个节点，如果q的下一个节点存在，则让q的下一个节点的前驱指针指向头结点，最后释放q所指节点的内存空间，并返回true。
如果i大于 1，设置一个指针p指向头结点的下一个节点，一个计数器j初始值为 1。
当j小于i - 1且p不等于头结点时，计数器j加一，移动指针p指向下一个节点，目的是找到要删除节点的前一个节点。
如果遍历结束后p等于头结点，说明没有找到要删除节点的前一个节点，返回false。
设置一个指针q指向p的下一个节点，如果q等于头结点，说明不存在第i个节点，返回false。
将q所指节点的数据域赋值给参数e，然后将节点q从链表中删除，具体操作是让p的next指针指向q的下一个节点，如果q的下一个节点存在，则让q的下一个节点的前驱指针指向p，最后释放q所指节点的内存空间，并返回true。