完整数据结构c++版实验书.docx

完整数据结构c++版实验书.docx

《完整数据结构c++版实验书.docx》由会员分享，可在线阅读，更多相关《完整数据结构c++版实验书.docx（64页珍藏版）》请在冰点文库上搜索。

完整数据结构c++版实验书

前言

《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之一。

它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现,在此基础上介绍一些典型算法及时、空效率分析。

这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。

通过学习,要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。

学习这门课程，习题和实验是两个关键环节.学生理解算法，上机实验是最佳的途径之一.因此,实验环节的好坏是学生能否学好《数据结构》的关键。

为了更好地配合学生实验，特编写实验指导书。

一、实验目的

更好的理解算法的思想、培养编程能力.

二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。

2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。

3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机.

5、实验学时内必须做数据结构的有关内容,不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分.

6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。

三、实验环境VC++6.0

四、说明

1、本实验的所有算法中元素类型可以根据实际需要选择。

2、实验题目中带＊者为较高要求,学生可自选；其余部分为基本内容，应尽量完成（至少完成70％，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解,以便为考研做一定的准备。

五、实验报告的书写要求

1．明确实验的目的及要求；

2．记录实验的输入数据和输出结果；

3．说明实验中出现的问题和解决过程；

4．写出实验的体会和实验过程中没能解决的问题；

六、参考书目

《数据结构》（C++语言描述）王红梅等清华大学出版社

《DATASTRUCTUREWITHC++》WilliamFord，WilliamTopp

清华大学出版社（影印版）

实验一线性表的操作

实验类型：

验证性

实验要求：

必修

实验学时：

2学时

一、实验目的：

参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。

二、实验要求：

1、掌握线性表顺序表类和链表类的特点。

掌握线性表的常见算法。

2、提交实验报告,报告内容包括:

目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会.

三、实验内容：

1．设计一个静态数组存储结构的顺序表类,要求编程实现如下任务：

建立一个线性表，首先依次输人数据元素1,2，3，…，10,然后删除数据元素6，最后依次显示当前线性表中的数据元素.要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。

2．设计一个带头结点的单链表类，要求：

（1）生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）.

（2）设计一个测试主函数，实际运行验证所设计单链表类的正确性.

3．设计一个不带头结点的单链表类，要求：

（1）不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素.

（提示：

要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。

）

（2）设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。

4．设计一个带头结点的循环单链表类，实现约瑟夫环问题；

问题描述：

设编号为1,2,…,n（n〉0）个人按顺时针方向围坐-圈，每人持有一个正整数密码.开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。

报到m时停止报数,报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数。

如此下去，直到所有人全部出列为止。

要求设计一个程序模拟此过程，并给出出列人的编号序列.

测试数据：

n=7，7个人的密码依次为3,1,7，2，4，8，4

初始报数上限值m=20

＊5．设计一个带头结点的循环双向链表类，要求：

（1）带头结点循环双向链表类的成员函数包括:

取数据元素个数、插入、删除、取数据元素。

（2）设计一个测试主函数,实际运行验证所设计循环双向链表类的正确性.＊6．设计一个单链表实现一元多项式求和问题。

要求：

（1）设计存储结构表示一元多项式;

（2）设计算法实现一元多项式相加。

四、程序样例

顺序表类定义：

将该类保存在文件SeqList.h中.

constintMaxSize=100;//100只是示例性的数据,可根据实际问题具体定义

template〈classT〉//定义模板类SeqList

classSeqList

｛

public:

SeqList（）{length=0;｝//无参构造函数

SeqList（Ta［],intn）;//有参构造函数

～SeqList（）{｝//析构函数为空

intLength（）｛returnlength;｝//求线性表的长度

TGet（inti）;//按位查找，取线性表的第i个元素

intLocate（Tx）;//按值查找，求线性表中值为x的元素序号

voidInsert（inti，Tx）；//在线性表中第i个位置插入值为x的元素

TDelete（inti）;//删除线性表的第i个元素

voidPrintList（）；//遍历线性表，按序号依次输出各元素

private：

Tdata[MaxSize];//存放数据元素的数组

intlength；//线性表的长度

｝；

template

SeqList：

:

SeqList（Ta[］,intn）

｛

if（n>MaxSize）throw”参数非法”;

for（i=0；i〈n；i++）

data[i］=a［i］;

length=n;

}

template

TSeqList：

:

Get（inti）

{

if（i〈1&&i>length）throw"查找位置非法"；

elsereturndata［i—1］；

}

template〈classT>

intSeqList：

:

Locate（Tx）

｛

for（i=0；i〈length；i++）

if（data[i］==x）returni+1；//下标为i的元素等于x，返回其序号i+1

return0；//退出循环，说明查找失败

}

template

voidSeqList:

：

Insert（inti，Tx）

{

if（length>=MaxSize）throw"上溢”；

if（i<1|｜i>length+1）throw”位置”;

for（j=length;j>=i；j--）

data［j］=data［j—1］;//注意第j个元素存在数组下标为j-1处

data[i—1］=x；

length++;

｝

template

TSeqList：

:

Delete（inti）

｛

if（length==0）throw”下溢";

if（i〈1|｜i>length）throw”位置";

x=data[i-1］;

for（j=i;j

data［j-1］=data［j];//注意此处j已经是元素所在的数组下标

length—-；

returnx;

}

链表类定义:

将该类保存在文件LinkList.h中。

template〈classT>

structNode

{

Tdata;

Node＊next;//此处〈T>也可以省略

}

template

classLinkList

｛

public：

LinkList（）{first=newNodenext=NULL;｝//建立只有头结点的空链表

LinkList（Ta［］,intn）；//建立有n个元素的单链表

~LinkList（）;//析构函数

intLength（）；//求单链表的长度

TGet（inti）；//取单链表中第i个结点的元素值

intLocate（Tx）;//求单链表中值为x的元素序号

voidInsert（inti,Tx）;//在单链表中第i个位置插入元素值为x的结点

TDelete（inti）;//在单链表中删除第i个结点

voidPrintList（）;//遍历单链表，按序号依次输出各元素

private：

Node〈T〉＊first；//单链表的头指针

};

template

LinkList：

：

～LinkList（）

{

p=first;//工作指针p初始化

while（p）//释放单链表的每一个结点的存储空间

{

q=p;//暂存被释放结点

p=p-〉next；//工作指针p指向被释放结点的下一个结点，使单链表不断开

deleteq;

｝

｝

template

TLinkList:

:

Get（inti）

{

p=first—〉next;j=1；//或p=first；j=0;

while（p＆＆j

{

p=p->next;//工作指针p后移

j++；

}

if（！

p）throw”位置”;

elsereturnp-〉data;

}

template〈classT〉

voidLinkList：

:

Insert（inti,Tx）

{

p=first;j=0;//工作指针p初始化

while（p&&j〈i—1）

{

p=p—〉next;//工作指针p后移

j++；

｝

if（！

p）throw"位置";

else｛

s=newNode〈T>;s->data=x；//向内存申请一个结点s，其数据域为x

s—>next=p—〉next;//将结点s插入到结点p之后

p—〉next=s;

}

｝

template〈classT〉

TLinkList:

:

Delete（inti）

｛

p=first；j=0；//工作指针p初始化

while（p&&j〈i—1）//查找第i—1个结点

｛

p=p-〉next；

j++；

}

if（!

p|｜！

p->next）throw"位置”；//结点p不存在或结点p的后继结点不存在

else{

q=p—>next；x=q—>data；//暂存被删结点

p—〉next=q—>next;//摘链

deleteq;

returnx；

｝

}

template

LinkList：

:

LinkList（Ta[]，intn）

{

first=newNode〈T>；

first->next=NULL；//初始化一个空链表

for（i=0;i

｛

s=newNode〈T〉;s-〉data=a[i］;//为每个数组元素建立一个结点

s—〉next=first->next；//插入到头结点之后

first->next=s;

｝

｝

template

LinkList：

:

LinkList（Ta［］,intn）

｛

first=newNode〈T〉;//生成头结点

r=first；//尾指针初始化

for（i=0;i〈n;i++）

{

s=newNode〈T>;s—〉data=a［i]；//为每个数组元素建立一个结点

r—>next=s；r=s;//插入到终端结点之后

}

r—〉next=NULL；//单链表建立完毕，将终端结点的指针域置空

｝

1．#include

h>

＃include

voidmain（）

｛intr[］={1,2，3,4，5,6,7,8,9，10}；

SeqLista（r，50）;

cout<〈”执行删除操作前数据为：

”〈

a.PrintList（）；

a。

Delete（6）；

cout<〈”执行删除操作后数据为：

”〈

a。

PrintList（）；

｝

2．

＃include〈iostream。

h>

＃include

h>

voiddivid（LinkList&L）

｛Node〈T>*p，＊q,*h;

h=newNode（）；

p=L。

first-〉next；q=L.first；

while（p）

｛if（p—>data%2!

=0）{q=p;p=p—〉next;｝

else{q=p；p=p—>next；q-next=h.first->next；h.first—>next=q;｝

｝

p=L.first—〉next;

while（p—〉next!

=Null）

｛p=p-〉next;｝

p-〉next=h.first—〉next；

deleteh；

}

voidmain（）

｛intr[］=｛1，—2，3，—4，—5,6,-7，8,9,10};

LinkListList（r,10）；

cout〈〈”执行操作前数据为：

"〈〈endl;

List.PrintList（）；

divid（List）;

cout<〈”执行操作后数据为:

”<

List。

PrintList（）;

}

6．voidAdd（LinkList〈elem〉＆A,LinkList〈elem〉B）

｛

pre=A.first;p=pre->next；//工作指针p初始化，指针pre始终指向p的前驱结点

qre=B.first;q=qre-〉next;//工作指针q初始化，指针qre始终指向q的前驱结点

while（p&&q）

{

if（p-〉exp〈q->exp）｛//第1种情况

pre=p；

p=p->next；

}

elseif（p—〉exp>q—>exp）｛//第2种情况，将结点q插入到结点p之前

v=q—>next；

pre—>next=q;

q-〉next=p;

q=v;

｝

else｛//第3种情况

p—>coef=p-〉coef+q->coef;//系数相加

if（p->coef==0）｛//系数为0，删除结点p和结点q

pre-〉next=p—>next;//删除结点p

deletep;

p=pre->next;

｝

else｛//系数不为0，只删除结点q

pre=p；

p=p—>next；

}

qre—>next=q—>next//删除结点q

deleteq;

q=qre—〉next;

｝

if（q）pre—〉next=q；//将结点q链接在第一个单链表的后面

deleteB.first;//释放第二个单链表的头结点所占的内存

}

实验二栈、队列、串的操作

实验类型：

验证性

实验要求：

必修

实验学时:

2学时

一、实验目的：

参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作.

二、实验要求：

1、掌握栈、队列、串的特点。

掌握特殊线性表的常见算法。

2、提交实验报告,报告内容包括:

目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会.

三、实验内容：

1。

堆栈类测试和应用问题.要求：

（1）设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。

测试方法为：

依次把数据元素1，2，3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。

（2）定义数据元素的数据类型为如下形式的结构体：

typedefstruct

{chartaskname［10]；//任务名

inttaskno；　　　　//任务号

｝DataType;

设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈,然后出栈堆栈中的数据元素并在屏幕上显示。

2.队列类测试和应用问题。

要求:

设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：

依次把数据元素1,2，3，4，5入队，然后出队中的数据元素并在屏幕上显示.

3．设计串采用顺序存储结构,编写函数实现两个串的比较Compare（S，T）.要求比较结果有大于、等于和小于三种情况。

*4.设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出.

*5.设计串采用静态数组存储结构,编写函数实现串的替换Replace（S，start,T，V），即要求在主串S中,从位置start开始查找是否存在子串T，若主串S中存在子串T,则用子串V替换子串T,且函数返回1；若主串S中不存在子串T，则函数返回０。

并要求设计主函数进行测试。

一个测试例子为：

S＝”Iamastudent”，T=”student"，V=”teacher“。

四、程序样例

1．顺序栈类的定义

constintStackSize=10;//10只是示例性的数据，可以根据实际问题具体定义

template〈classT〉//定义模板类SeqStack

classSeqStack

｛

public:

SeqStack（）{top=-1;｝//构造函数，栈的初始化

～SeqStack（）｛}//析构函数

voidPush（Tx）；//将元素x入栈

TPop（）;//将栈顶元素弹出

TGetTop（）{if（top！

=—1）returndata[top］；}//取栈顶元素（并不删除）

boolEmpty（）｛top==-1？

return1:

return0；}//判断栈是否为空

private:

Tdata［StackSize］;//存放栈元素的数组

inttop；//栈顶指针,指示栈顶元素在数组中的下标

}；

template

voidSeqStack：

：

Push（Tx）

｛

if（top==StackSize—1）throw”上溢”；

top++;

data［top]=x;

｝

template〈classT〉

TSeqStack:

：

Pop（）

｛

if（top==-1）throw”下溢”;

x=data[top--]；

returnx;

｝

2．链式栈类的定义

template〈classT〉

classLinkStack

{

public:

LinkStack（）{top=NULL；｝//构造函数，置空链栈

~LinkStack（）；//析构函数，释放链栈中各结点的存储空间

voidPush（Tx）；//将元素x入栈

TPop（）；//将栈顶元素出栈

TGetTop（）{if（top！

=NULL）returntop—〉data；｝//取栈顶元素（并不删除）

boolEmpty（）｛top==NULL？

return1：

return0；｝//判断链栈是否为空栈

private：

Node*top;//栈顶指针即链栈的头指针

};

template

voidLinkStack：

:

Push（Tx）

｛

s=newNode

s—>next=top;top=s；//将结点s插在栈顶

}

template〈classT〉

TLinkStack:

:

Pop（）

｛

if（top==NULL）throw"下溢";

x=top-〉data;//暂存栈顶元素

p=top;top=top—>next；//将栈顶结点摘链

deletep；

returnx；

}

template〈classT>

LinkStack:

:

～LinkStack（）

｛

while（top）

{

p=top—〉next；

deletetop；

top=p;

｝

｝

3．双栈类的定义

constintStackSize=100;//100只是示例数据,需根据具体问题定义

template〈classT>

classBothStack

{

public:

BothStack（）{top1=-1;top2=StackSize；｝//构造函数，将两个栈分别初始化

～BothStack（）｛}//析构函数

voidPush（inti，Tx）;//将元素x压入栈i

TPop（inti）;//对栈i执行出栈操作

TGetTop（inti）;//取栈i的栈顶元素

boolEmpty（inti）；//判断栈i是否为空栈

private：

Tdata［StackSize］;//存放两个栈的数组

inttop1，top2；//两个栈的栈顶指针，分别指向各自的栈顶元素在数组中的下标

｝；

template〈classT〉

voidBothStack:

:

Push（inti，Tx）

｛

if（top1==top2-1）throw”上溢”；

if（i==1）data［++top1］=x;

if（i==2）data[——top2］=x；

｝

template

TBothStack：

:

Pop（inti）

{

if（i==1）｛//将栈1的栈顶元素出栈

if（top1==—1）throw”下溢”;

returndata[top1——]；

｝

if（i==2）｛//将栈2的栈顶元素出栈

if（top2==StackSize）throw''下溢"；

returndata