数据结构实验线性表及其应用.docx

数据结构实验线性表及其应用.docx

《数据结构实验线性表及其应用.docx》由会员分享，可在线阅读，更多相关《数据结构实验线性表及其应用.docx（18页珍藏版）》请在冰点文库上搜索。

数据结构实验线性表及其应用

实验1线性表及其应用

实验性质：

验证性

实验学时：

2学时

1、实验目的

1.掌握线性表的顺序存储结构在计算机的表示方法及其基本操作的实现；

2.掌握线性表的链式存储结构在计算机的表示方法及其基本操作的实现；

3.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。

2、实验预备知识

1.复习C/C++语言相关知识（如：

结构体的定义、typedef的使用、函数的定义、调用及参数传递方式）；

2.阅读并掌握顺序表与链表的类型定义及其查找、插入、删除等基本操作。

3、实验内容

1.理解并分别用顺序表、链表的操作运行下列程序：

#include

usingnamespacestd;

#include"Status.h"

typedefintElemType;

#include"SqList.h"//用#include"LinkList.h"替换

voidmain（）

{

SqListL;//用LinkListL;替换，与#include"LinkList.h"配合

intn,i;

ElemTypee;

InitList（L）;

cout<<"\nL=";

ListTraverse（L）;

cout<<"\n请设置将向线性表L中输入的元素个数：

";

cin>>n;

CreateList（L,n）;

cout<<"\nL=";

ListTraverse（L）;

cout<<"\nL的表长为：

"<

cout<<"\n请输入想要获取的元素位序：

";

cin>>i;

if（GetElem（L,i,e））cout<<"\n第"<

"<

elsecout<<"\n第"<

"<

cout<<"\n请输入要查找的元素：

";

cin>>e;

if（i=LocateElem（L,e））cout<<"\n元素"<

"<

elsecout<<"\n元素"<

"<

cout<<"\n请输入插入位置和所插入元素：

";

cin>>i>>e;

if（ListInsert（L,i,e））

{

cout<<"\nL=";

ListTraverse（L）;

}

elsecout<<"\n插入操作失败！

"<

cout<<"\n请输入被删元素的位置：

";

cin>>i;

if（ListDelete（L,i,e））cout<<"\n被删元素为：

"<

elsecout<<"\n删除操作失败！

"<

cout<<"\nL=";

ListTraverse（L）;

}

本题目说明：

（1）头文件Status.h的内容如下：

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;

（2）头文件SqList.h（内容包括顺序表的结构定义及基本操作实现）。

（3）头文件LinkList.h（内容包括链表的结构定义及基本操作实现）。

（4）顺序表中基本操作的补充：

●CreateList（&L,n）：

向顺序表L中输入n个元素（0≤n≤MAXSIZE）。

StatusCreateList（SqList&L,intn）

{

inti;

if（!

L.elem||n<0||n>MAXSIZE）returnERROR;

cout<<"\n请输入"<

";

for（i=1;i<=n;i++）

cin>>L.elem[i-1];//可以用随机函数rand（）自动生成

L.length=n;

returnOK;

}

●ListTraverse（L）：

以线性表的记录形式遍历输出顺序表L，例如：

（a1,a2,…，ai,…an）。

voidListTraverse（SqListL）

{

inti;

cout<<'（';

for（i=1;i<=L.length;i++）

cout<

if（L.length）cout<<"\b）"<

elsecout<<'）'<

}

2.设计实现一个算法，用以对两个非递减有序表A、B进行合并，其中A=（2，5，8，9），B=（3，4，8，10，12，20）。

3.（任选题）已知有两个多项式P（x）和Q（x），基于链表设计算法实现P（x）+Q（x）运算，而且不重新开辟存储空间。

实验2栈和队列的实现

实验性质：

验证性

实验学时：

2学时

4、实验目的

4.掌握栈的特点、在计算机中的存储表示方法及其基本操作的实现；

5.掌握队列的特点、在计算机中的存储表示方法及其基本操作的实现；

6.能够利用栈和队列求解一些常见问题。

5、实验预备知识

3.阅读并掌握顺序栈、链栈两种存储方法的类型定义及其压栈、弹栈等基本操作。

4.阅读并掌握循环队列、链队列两种存储方法的类型定义及其入队、出队等基本操作。

6、实验内容

1.理解并用顺序栈操作运行下列程序：

#include

usingnamespacestd;

#include"Status.h"

typedefintElemType;

#include"SqStack.h"

voidmain（）

{

SqStackS;

ElemTypee;

InitStack（S）;

Push（S,2）;

Push（S,4）;

Push（S,6）;

Push（S,8）;

cout<<"\n由栈底至栈顶的元素为：

";

StackTraverse（S）;

cout<<"\n栈的长度为：

"<

GetTop（S,e）;

cout<<"\n栈顶元素为：

"<

Pop（S,e）;

cout<<"\n由栈底至栈顶的元素为：

";

StackTraverse（S）;

cout<<"\n栈的长度为：

"<

GetTop（S,e）;

cout<<"\n栈顶元素为：

"<

}

2.理解并用循环队列、链队列操作运行下列程序：

#include

usingnamespacestd;

#include"Status.h"

typedefintElemType;

#include"SqQueue.h"

voidmain（）

{

SqQueueQ;

ElemTypee;

InitQueue（Q）;

EnQueue（Q,1）;

EnQueue（Q,3）;

EnQueue（Q,5）;

EnQueue（Q,7）;

GetHead（Q,e）;

cout<<"\n队头元素为：

"<

cout<<"\n队列中从队头至队尾的元素为：

";

QueueTraverse（Q）;

cout<<"\n队列的长度为：

"<

DeQueue（Q,e）;

cout<<"\n出队的元素为：

"<

cout<<"\n出队操作完成之后队列中从队头至队尾的元素为：

";

QueueTraverse（Q）;

cout<<"\n队列的长度为：

"<

}

本题目说明：

（1）头文件Status.h的内容同实验1。

（2）头文件SqStack.h（内容包括顺序栈的结构定义及基本操作实现）。

（3）头文件SqQueue.h（内容包括循环队列的结构定义及基本操作实现）。

（4）顺序栈中基本操作的补充：

●StackTraverse（S）：

从栈底到栈顶依次对S的每个数据元素进行访问。

voidStackTraverse（SqStackS）

{

ElemType*p;

p=S.base;

while（p!

=S.top）

{

cout<<*p++<<"";

}

cout<

}

（5）循环队列中基本操作的补充：

●QueueTraverse（L）：

从队头到队尾，依次对Q的每个数据元素访问。

voidQueueTraverse（SqQueueQ）

{

inti;

i=Q.front;

while（i!

=Q.rear）

{

cout<

i=（i+1）%MAXSIZE;

}

cout<

}

3.从键盘输入一个表达式，试编写算法计算表达式的值。

4.有n个人围成一圈，从第1个人开始，1，2，…，m报数，报至m出局，余下的人继续从1，2，…，m报数，重复之前的流程，要求：

求出被淘汰编号的序列，及最后剩下的一人是原来的第几号？

（要求：

用循环队列解决该问题。

）

实验3树和二叉树

实验性质：

验证性

实验学时：

4学时

1、实验目的

7.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现；

8.能够利用二叉树求解一些常见问题。

2、实验预备知识

5.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作。

6.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。

3、实验内容

1.理解并用二叉链表的操作运行下列程序：

#include

usingnamespacestd;

#include"Status.h"

typedefcharElemType;

#include"BiTree.h"

voidmain（）

{

BiTreeT;

CreateBiTree（T）;

cout<<"二叉树的深度为：

"<

cout<<"二叉树中结点个数为：

"<

cout<<"二叉树中叶子结点个数为：

"<

cout<<"先序遍历：

";

PreOrderTraverse（T）;

cout<<"\n中序遍历：

";

InOrderTraverse（T）;

cout<<"\n后序遍历：

";

PostOrderTraverse（T）;

cout<

}

本题目说明：

（1）头文件Status.h的内容同实验1。

（2）头文件BiTree.h（内容包括二叉树的二叉链表中结点的结构定义及二叉链表基本操作的实现）。

（3）基本操作的补充：

●LeavesNodeCount（T）：

二叉树中叶子结点的个数。

intLeavesNodeCount（BiTreeT）

{

if（!

T）return0;

elseif（!

T->lchild&&!

T->rchild）return1;

elsereturnLeavesNodeCount（T->lchild）+LeavesNodeCount（T->rchild）;

}

2.已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试编写算法求其赫夫曼编码。

实验4图

实验性质：

综合性

实验学时：

2学时

1、实验目的

9.掌握有向图、无向图在计算机的表示方法及其基本操作的实现；

10.能够利用图形结构对实际问题进行分析建模，利用计算机求解。

2、实验预备知识

7.阅读并掌握有向图（网）、无向图（网）用邻接矩阵和邻接表两种存储方法的类型定义及其创建、遍历等基本操作。

8.阅读并掌握最短路径中迪杰斯特拉算法的实现。

3、实验内容

2.理解并分别用邻接矩阵、邻接表的操作运行下列程序：

#include

#include"Status.h"

usingnamespacestd;

#include"MGraph.h"

voidmain（）

{

MGraphG;

inti;

CreateUDG（G）;

cout<<"\n深度优先遍历序列为：

";

TraverseDFS（G）;

cout<<"\n广度优先遍历序列为：

";

for（i=0;i

visited[i]=false;

TraverseBFS（G）;

cout<

}

本题目说明：

（1）头文件Status.h的内容同实验1。

（2）头文件MGraph.h（内容包括图采用邻接矩阵存储的结构定义及基本操作实现）。

3.以南阳理工学院校园平面图为例，试编写程序输出从学校大门到其他各建筑物的最短路径。

（说明：

校园平面图可自行绘制，或以图5-1为参考）

图5-1南阳理工学院校园平面图（粗略图）

实验5查找

实验性质：

验证性

实验学时：

2学时

1、实验目的

11.掌握静态查找表中折半查找算法的实现；

12.掌握动态查找表中二叉排序树的特点及其创造、插入、查找算法的实现。

2、实验预备知识

9.阅读并掌握折半查找算法的实现。

10.阅读并掌握二叉排序树的插入、生成、查找的基本操作实现。

3、实验内容

1.理解并运行下列程序：

#include

usingnamespacestd;

#defineENDFLAG10000

typedefintKeyType;

typedefchar*InfoType;

typedefstruct

{

KeyTypekey;

InfoTypeotherinfo;

}ElemType;

typedefstruct

{

ElemType*R;

intlength;

}SSTable;

voidCreateSTable（SSTable&ST,intn）

{

inti;

ST.R=newElemType[n+1];

cout<<"请输入"<

";

for（i=1;i<=n;i++）

cin>>ST.R[i].key;

ST.length=n;

}

intSearch_Bin1（SSTableST,KeyTypekey）

{

intlow,high,mid;

low=1;

high=ST.length;

while（low<=high）

{

mid=（low+high）/2;

if（key==ST.R[mid].key）returnmid;

elseif（key

elselow=mid+1;

}

return0;

}

intSearch_Bin2（SSTableST,intlow,inthigh,KeyTypekey）

{

intmid;

if（low>high）return0;

mid=（low+high）/2;

if（key==ST.R[mid].key）returnmid;

elseif（key

elsereturnSearch_Bin2（ST,mid+1,high,key）;

}

voidmain（）

{

intn;

KeyTypekey;

SSTableST;

cout<<"请输入静态查找表长：

";

cin>>n;

CreateSTable（ST,n）;

cout<<"请输入待查记录的关键字：

";

cin>>key;

cout<<"Search_Bin1算法计算的位置为：

"<

cout<<"Search_Bin2算法计算的位置为：

"<

}

2.在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，试编写程序创建这棵二叉排序树（要求：

创建完成之后对其进行中序遍历检验其是否是递增序列以证明其正确）。

实验6排序

实验性质：

验证性

实验学时：

2学时

1、实验目的

1.熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、快速排序的算法实现及其性能分析；

2.掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析。

2、实验预备知识

阅读并掌握各种排序算法的排序过程及算法实现。

3、实验内容

1.理解并运行下列程序：

#include

usingnamespacestd;

#include

typedefintKeyType;

typedefchar*InfoType;

typedefstruct

{

KeyTypekey;

InfoTypeotherinfo;

}ElemType;

typedefstruct

{

ElemType*R;

intlength;

}SqList;

intCmpNum;

voidCreateList（SqList&L,intn）

{

inti;

L.R=newElemType[n+1];

srand（time（0））;

for（i=1;i<=n;i++）

{

L.R[i].key=rand（）%100;

}

L.length=n;

}

voidListTraverse（SqListL）

{

inti;

for（i=1;i<=L.length;i++）

cout<

cout<

}

voidBubbleSort（SqList&L）

{

intm,flag,i;

m=L.length-1;flag=1;

while（m>0&&flag）

{

flag=0;

for（i=1;i<=m;i++）

{

CmpNum++;

if（L.R[i].key>L.R[i+1].key）

{

flag=1;

L.R[0]=L.R[i+1];

L.R[i+1]=L.R[i];

L.R[i]=L.R[0];

}

}

m--;

}

}

voidmain（）

{

SqListL;

CreateList（L,8）;

cout<<"测试数据：

"<

ListTraverse（L）;

BubbleSort（L）;

cout<<"排序后：

"<

ListTraverse（L）;

cout<<"BubbleSort排序方法中数据的比较次数为：

"<

}

2.设待排序的关键字序列为{12，2，16，30，28，10，16，20，6，18}，试编写程序分别用直接插入、折半插入、希尔排序、快速排序对其进行排序。

（要求：

每种排序方法都有排序前后的关键字序列对比，以便验证排序结果的正确性。

）