实验五：实现循环双链表各种基本运算的算法
一、实验目的与要求
目的:领会循环双链表存储结构和掌握循环双链表中各种基本运算算法设计。
内容:编写一个程序cdinklist.cpp,实现循环双链表的各种基本运算和整体建表算法(假设循环双链表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能:
(1)初始化循环双链表h。
(2)依次采用尾插法插入a、b、c、d、e元素
(3)输出循环双链表h。
(4)输出循环双链表h长度
(5)判断循环双链表h是否为空。
(6)输出循环双链表h的第3个元素
(7)输出元素a的位置。
(8)在第4个元素位置上插人f元素
(9)输出循环双链表h。
(10)删除循环双链表h的第3个元素
(11)输出循环双链表h。
(12)释放循环双链表h。
二、实验类型
C++算法编程
三、实验原理及说明
循环链表(circular linked list)是另一种形式的链式存储结构。循环链表有循环单链表和循环双链表两种类型,循环单链表的结点类型和非循环单链表的结点类型LinkNode 相同,循环双链表的结点类型和非循环双链表的结点类型 DinkNode 相同。
把双链表改为循环双链表的过程是将它的尾结点的next指针域由原来为空改为指问头结点,将它的头结点的 prior 指针域改为指向尾结点,整个双链表形成两个环。
循环链表的基本运算的实现算法与对应非循环链表的算法基本相同,主要差别是对于循环单链表或循环双链表L,判断表尾结点p的条件是p->next=-L;另外在循环双链表L 中可以通过L->prior 快速找到尾结点
四、实验主要仪器设备和材料
序 号 |
名 称 |
主要用途 |
1 |
电脑 |
打开软件 |
2 |
Dev c++ |
编写代码，运行代码 |
五、实验内容和步骤
根据《教程》中2.3.4节的算法得到cdlinklist.cpp程序,其中包含如下函数。
InitList(DLinkNode *&L):初始化循环双链表L。
DestroyList(DLinkNode xL):释放循环双链表L。
ListEmpty(DLinkNode *L):判断循环双链表L是否为空表。
ListLength(DLinkNodexL):返回循环双链表L的元素个数
DispList(DLinkNode *L):输出循环双链表L。
GetElem(DLinkNode *L,inti,ElemType &e):获取循环双链表L中第i个元素。LocateElem(DLinkNode *L,ElemType e):在循环双链表L中查找元素e。ListInsert(DLinkNode *&L,inti,ElemTypee):在循环双链表L中第i个位置上插入元素e。
ListDelete(DLinkNode *&L,inti,ElemType&e):从循环双链表L中删除第i个元素。对应的程序代码如下(设计思路详见代码中的注释):
步骤：
创建一个cdlinklist.cpp文件，将函数写入文件中
创建一个main.cpp文件，编写主函数，对函数进行验证
实验内容：
-
- 编写cdlinklist
#include <iostream>
#include <malloc.h>
using namespace std;
typedef char ElemType;
typedef struct DNode {
ElemType data;
struct DNode *prior;
struct DNode *next;
} DLinkNode;
//头插法建立循环双链表
void CreateListF(DLinkNode *&L, ElemType a[], int n) {
DLinkNode *s;
L = new DLinkNode;
L->next = NULL;
for (int i = 0; i < n; i++) {
s = new 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;
s->next = L;
}
//尾插法创建循环双链表
void CreateListR(DLinkNode * &L, ElemType a[], int n) {
DLinkNode *s, *r;
L = new DLinkNode;
L->next = NULL;
r = L;
for (int i = 0; i < n; i++) {
s = new DLinkNode;
s->data = a[i];
r->next = s;
s->prior = r;
r = s;
}
r->next = L;
L->prior = r;
}
void InitList(DLinkNode *&L) { //初始化循环双链表
L = new DLinkNode;
L->prior = L->next = L;
}
void DestroyList(DLinkNode *&L) { //摧毁循环双链表
DLinkNode *pre = L, *p = pre->next;
while(p != L) {
delete pre;
pre = p;
p = pre->next;
}
delete pre;
}
bool ListEmpty(DLinkNode *L) { //判断是否为空
return (L->next == L);
}
int ListLength(DLinkNode *L) { //判断长度
DLinkNode *p = L;
int i = 0;
while(p->next != L) {
i++;
p = p->next;
}
return i;
}
void DispList(DLinkNode *L) { //输出线性表
DLinkNode *p = L->next;
while(p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//获取循环双链表L中的第i个元素
bool GetElem(DLinkNode *L, int i, ElemType &e) {
int j = 1;
DLinkNode *p = L->next;
if (i <= 0|| L->next == L) return 0;
if (i == 1) {
e = L->next->data;
return 1;
}
else {
while(j < i && p!= L) {
j++;
p = p->next;
}
if (p == L)
return 0;
else {
e = p->data;
return 1;
}
}
}
//在循环双链表L中查找元素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;
else
return i;
}
bool ListInsert(DLinkNode *&L, int i, ElemType e) {
int j = 1;
DLinkNode *p = L, *s;
if(i <= 0) return 0;
if (p->next == L) {
s = new DLinkNode;
s->data = e;
p->next = s; s->next = p;
p->prior = s; s->prior = p;
return 1;
}
else if (i == 1) {
s = new DLinkNode;
s->data = e;
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;
return 1;
}
else {
p = L->next;
while(j < i - 1 && p != L) {
j++;
p = p->next;
}
if (p == L)
return 0;
else {
s = new DLinkNode;
s->data = e;
s->next = p->next;
if (p->next != NULL) p->next->prior = s;
s->prior = p;
p->next = s;
return 1;
}
}
}
bool ListDelete(DLinkNode *&L, int i, ElemType &e) {
int j = 1;
DLinkNode *p = L, *q;
if (i <= 0 || L->next == L) return 0;
if (i == 1) {
q = p->next;
e = q->data;
L->next = q->next;
q->next->prior = L;
delete q;
return 1;
}
else {
p = L->next;
while(j < i - 1 && p != L) {
j++;
p = p->next;
}
if(p == L)
return 0;
else {
q = p->next;
e = q->data;
p->next = q->next;
if (p->next != L) p->next->prior = p;
delete q;
return 1;
}
}
}编写main函数
#include "cdlinklist.cpp"
int main() {
DLinkNode *h;
ElemType e;
cout <<"双链表的基本运算如下:" << endl;
cout << "(1)初始化循环双链表h" << endl; InitList(h);
cout <<"(2)依次采用尾插法插人a,b,c,d,e元素" << endl;
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'b');
ListInsert(h,5,'a');
cout <<"(3)输出循环双链表h:"; DispList(h);
cout << "(4)循环双链表h长度:"<< ListLength(h) << endl;
cout << "(5)循环双链表h为"<< (ListEmpty(h)?"空":"非空") << endl;
GetElem(h, 3, e); cout << "(6)循环双链表h的第3个元素:" << e << endl;
cout <<"(7)元素a的位置:" << LocateElem(h,'a') << endl;
cout <<"(8)在第4个元素位置上插人f元素" << endl; ListInsert(h,4,'f');
cout <<"(9)输出循环双链表h:"; DispList(h);
cout <<"(10)删除h的第3个元素" << endl; ListDelete(h,3,e);
cout <<"(11)输出循环双链表h:"; DispList(h);
cout <<"(12)释放循环双链表h"<< endl;
DestroyList(h);
return 1;
}运行结果：
六、实验小结与分析
在此次实验中我领会了循环双链表链表存储结构，掌握了循环双链表链表中的各种基本运算算法设计，循环链表是另一种形式的链式存储结构，但是它可以在链表的基础上修改而来，把双链表改为循环双链表的过程是将它的尾结点的next指针域由原来为空改为指问头结点,将它的头结点的 prior 指针域改为指向尾结点,整个双链表形成两个环。这种可以不用双链表的形式就可以实现快速找到尾结点等功能。在判断是否为对称的链表问题中很好的表现出了循环双链表相对于双链表的优势，可以向后遍历，也可以向前遍历，比双链表更加容易比较是否对称。此次实验使我了解到了循环链表的好处，与循环链表的区别所在，使我对算法有了更加的了解。