实验三：实现双链表各种基本运算的算法
一、实验目的与要求
目的:
领会双链表存储结构和掌握双链表中各种基本运算算法设计。
内容:
编写一个程序dlinklist.cpp,实现双链表的各种基本运算和整体建表算法(假设链表的元素类型ElemType为char),并在此基础上设计一个程序exp2-3.cPp,完成如下能:
(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++算法编程
三、实验原理及说明
顺序表必须占用一整块事先分配大小的存储空间,这样会降低存储空间的利用率,为此有了可以实现存储空间动态管理的链式存储结构--链表。
线性表的链式存储结构称为链表(linked list)。线性表的每个元素用一个内存结点存储,嗜每个内存结点不仅包含元素本身的信息(称为数据域),而且包含表示元素之间逻辑关系的信息.
在 C/C++语言中采用指针来实现,这称为指针域由于线性表中的每个元素最多只有一个前驱元素和一个后继元素。在每个结点中除包含数据域以外设置两个指针域,分别用于指向其前驱结点和后继结点,这样构成的链表称为线性双向链接表,简称双链表(doubly linked list)。若一个结点中的某个指针域不需要指向其他任何结点,则将它的值置为空,用常量 NULL表示。
四、实验主要仪器设备和材料
| 序 号 | 名 称 | 主要用途 |
| 1 | 电脑 | 打开软件 |
| 2 | Dev c++ | 编写代码，运行代码 |
五、实验内容和步骤
根据《教程》中2.3.3节的算法得到dlinklist.cpp程序,其中包含如下函数
[nitList(DLinkNode x&L):初始化双链表L。
DestroyList(DLinkNode xL):释放双链表L。
ListEmpty(DLinkNodexL):判断双链表是否为空表
ListLength(DLinkNode *L):返回双链表L的元素个数
DispList(DLinkNode *L):输出双链表L。
GetElem(DLinkNode *L,inti,ElemType&e):获取双链表L中第i个元素LocateElem(DLinkNode *L,ElemTypee):在双链表L中查找元素e。ListInsert(DLinkNode *&L,inti,ElemTypee):在双链表L第i个位置上插入元素e。
ListDelete(DLinkNode *&L,inti,ElemType &e):从双链表L中删除第i个元素。
步骤：
创建一个linklist.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 = L->prior = 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;
s->prior = L;
L->next = s;
}
}
void CreateListR(DLinkNode *&L, ElemType a[], int n) //采用尾插法建立双链表
{
DLinkNode *s, *r;
L = new DLinkNode;
L->prior = 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 = NULL;
}
void InitList(DLinkNode *&L) { //初始化双链表
L = new DLinkNode;
L->prior = NULL;
L->next = NULL;
}
void DestroyList(DLinkNode *L) { //摧毁双链表
DLinkNode *pre = L, *p = L->next;
while(p != NULL) {
delete pre;
pre = p;
p = pre->next;
}
delete pre;
}
bool ListEmpty(DLinkNode *L) { //判断是否为空
return (L->next == NULL);
}
int ListLength(DLinkNode *L) { //判断长度
DLinkNode *p = L;
int i = 0;
while(p->next != NULL) {
i++;
p = p->next;
}
return i;
}
void DispList(DLinkNode *L) { //输出线性表
DLinkNode *p = L->next;
while(p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//获取单链表L中第i个元素
bool GetElem(DLinkNode *L, int i, ElemType &e) {
int j = 0;
DLinkNode *p = L;
if (i <= 0) return 0;
while(j < i && p != NULL) {
j++;
p = p->next;
}
if (p == NULL)
return 0;
else {
e= p->data;
return 1;
}
}
//在单链表中查找元素e
int LocateElem(DLinkNode *L, ElemType e) {
int i = 1;
DLinkNode *p = L->next;
while(p->data != e && p != NULL) {
p = p->next;
i++;
}
if (p == NULL) return 0;
else return (i);
}
bool ListInsert(DLinkNode *&L, int i, ElemType e)
{
int j = 0;
DLinkNode *p = L, *s;
if(i <= 0) return false;
while(j < i-1 && p != NULL) {
j++;
p = p->next;
}
if(p == NULL)
return false;
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 true;
}
}
bool ListDelete(DLinkNode *&L, int i, ElemType &e) {
int j = 0;
DLinkNode *p = L, *q;
if (i <= 0) return false;
while (j < i - 1 && p != NULL) {
j++;
p = p->next;
}
if ( p == NULL)
return 0;
else
{
q = p->next;
if (q == NULL)
return false;
e = q->data;
p->next = q->next;
if (p->next != NULL) {
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,'d');
ListInsert(h,5,'e');
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;
}运行结果：
六、实验小结与分析
在此次实验中我领会了双链表链表存储结构，掌握了双链表链表中的各种基本运算算法设计，双链表就是在单链表的基础上，对每一个结点增加了一个指针，用以指向其前驱结点，这样的双链表就可以实现双向查找等功能。并且知道了如何使用C++语言中的指针来实现存储空间的动态管理，实现了单链表的各种基本运算和整体见表算法。并且使用了双链表对对一些应用实例进行了解答，使我对链表的功能有了更深入的了解，以及知道了如何实现链表来解决对应的实际问题，是我受益匪浅。
标签：DLinkNode,运算,int,ElemType,next,算法,双链,NULL From： https://blog.csdn.net/About_Yu/article/details/139070978