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

1、数据结构实验线性表及其应用实验1 线性表及其应用实验性质：验证性实验学时：2学时1、实验目的1.掌握线性表的顺序存储结构在计算机的表示方法及其基本操作的实现；2.掌握线性表的链式存储结构在计算机的表示方法及其基本操作的实现；3.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。2、实验预备知识1.复习C/C+语言相关知识（如：结构体的定义、typedef的使用、函数的定义、调用及参数传递方式）；2.阅读并掌握顺序表与链表的类型定义及其查找、插入、删除等基本操作。3、实验内容1.理解并分别用顺序表、链表的操作运行下列程序：#include using namespace std;#inc

2、lude Status.htypedef int ElemType;#include SqList.h /用#include LinkList.h替换void main() SqList L; /用LinkList L;替换，与#include LinkList.h配合 int n,i; ElemType e; InitList(L); coutnL=; ListTraverse(L); coutn; CreateList(L,n); coutnL=; ListTraverse(L); coutnL的表长为：ListLength(L)endl; couti; if(GetElem(L,i,e)

3、 coutn第i个元素为：eendl; else coutn第i个元素不存在！endl; coute; if(i=LocateElem(L,e) coutn元素e的位置为：iendl; else coutn元素e不存在！endl; coutie; if(ListInsert(L,i,e) coutnL=; ListTraverse(L); else coutn插入操作失败！endl; couti; if(ListDelete(L,i,e) coutn被删元素为：eendl; else coutn删除操作失败！endl; coutnL=; ListTraverse(L);本题目说明：（1）头文件

4、Status.h的内容如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;（2）头文件SqList.h（内容包括顺序表的结构定义及基本操作实现）。（3）头文件LinkList.h（内容包括链表的结构定义及基本操作实现）。（4）顺序表中基本操作的补充： CreateList(&L,n)：向顺序表L中输入n个元素（0nMAXSIZE）。Status CreateList(SqList &L,int n) int i;

5、 if(!L.elem|nMAXSIZE) return ERROR; coutn请输入n个元素：; for(i=1;iL.elemi-1; /可以用随机函数rand()自动生成 L.length=n; return OK; ListTraverse(L)：以线性表的记录形式遍历输出顺序表L，例如：(a1,a2,，ai,an)。void ListTraverse(SqList L) int i; cout(; for(i=1;i=L.length;i+) coutL.elemi-1,; if(L.length) coutb)endl; else cout)endl;2.设计实现一个算法，用以对

6、两个非递减有序表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.阅读并掌握循环队列、链队列两种存储方法的类型定义及其入队、

7、出队等基本操作。6、实验内容1. 理解并用顺序栈操作运行下列程序：#include using namespace std;#include Status.htypedef int ElemType;#include SqStack.hvoid main() SqStack S; ElemType e; InitStack(S); Push(S,2); Push(S,4); Push(S,6); Push(S,8); coutn由栈底至栈顶的元素为：; StackTraverse(S); coutn栈的长度为：StackLength(S)endl; GetTop(S,e); coutn栈顶元素

8、为：eendl; Pop(S,e); coutn由栈底至栈顶的元素为：; StackTraverse(S); coutn栈的长度为：StackLength(S)endl; GetTop(S,e); coutn栈顶元素为：eendl;2. 理解并用循环队列、链队列操作运行下列程序：#include using namespace std;#include Status.htypedef int ElemType;#include SqQueue.hvoid main() SqQueue Q; ElemType e; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,3)

9、; EnQueue(Q,5); EnQueue(Q,7); GetHead(Q,e); coutn队头元素为：eendl; coutn队列中从队头至队尾的元素为：; QueueTraverse(Q); coutn队列的长度为：QueueLength(Q)endl; DeQueue(Q,e); coutn出队的元素为：eendl; coutn出队操作完成之后队列中从队头至队尾的元素为：; QueueTraverse(Q); coutn队列的长度为：QueueLength(Q)endl;本题目说明：（1）头文件Status.h的内容同实验1。（2）头文件SqStack.h（内容包括顺序栈的结构定义

10、及基本操作实现）。（3）头文件SqQueue.h（内容包括循环队列的结构定义及基本操作实现）。（4）顺序栈中基本操作的补充： StackTraverse(S)：从栈底到栈顶依次对S的每个数据元素进行访问。void StackTraverse(SqStack S) ElemType *p; p=S.base; while(p!=S.top) cout*p+ ; coutendl;（5）循环队列中基本操作的补充： QueueTraverse(L)：从队头到队尾，依次对Q的每个数据元素访问。void QueueTraverse(SqQueue Q) int i; i=Q.front; while(i

11、!=Q.rear) coutQ.basei ; i=(i+1)%MAXSIZE; coutendl;3. 从键盘输入一个表达式，试编写算法计算表达式的值。4. 有n个人围成一圈，从第1个人开始，1，2，m报数，报至m出局，余下的人继续从1，2，m报数，重复之前的流程，要求：求出被淘汰编号的序列，及最后剩下的一人是原来的第几号？（要求：用循环队列解决该问题。）实验3 树和二叉树实验性质：验证性实验学时：4学时1、实验目的7.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现；8.能够利用二叉树求解一些常见问题。2、实验预备知识5.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历

12、等基本操作。6.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。3、实验内容1. 理解并用二叉链表的操作运行下列程序：#include using namespace std;#include Status.htypedef char ElemType;#include BiTree.hvoid main() BiTree T; CreateBiTree(T); cout二叉树的深度为：Depth(T)endl; cout二叉树中结点个数为：NodeCount(T)endl; cout二叉树中叶子结点个数为：LeavesNodeCount(T)endl; cout先序遍历：; PreOr

13、derTraverse(T); coutn中序遍历：; InOrderTraverse(T); coutn后序遍历：; PostOrderTraverse(T); coutlchild&!T-rchild) return 1; else return LeavesNodeCount(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.掌握有向图、无向图在计

14、算机的表示方法及其基本操作的实现；10.能够利用图形结构对实际问题进行分析建模，利用计算机求解。2、实验预备知识7.阅读并掌握有向图（网）、无向图（网）用邻接矩阵和邻接表两种存储方法的类型定义及其创建、遍历等基本操作。8.阅读并掌握最短路径中迪杰斯特拉算法的实现。3、实验内容2.理解并分别用邻接矩阵、邻接表的操作运行下列程序：#include#includeStatus.husing namespace std;#includeMGraph.h void main() MGraph G; int i; CreateUDG(G); coutn深度优先遍历序列为：; TraverseDFS(G);

15、 coutn广度优先遍历序列为：; for(i=0;iG.vexnum;i+) visitedi=false; TraverseBFS(G); coutendl;本题目说明：（1）头文件Status.h的内容同实验1。（2）头文件MGraph.h（内容包括图采用邻接矩阵存储的结构定义及基本操作实现）。3.以南阳理工学院校园平面图为例，试编写程序输出从学校大门到其他各建筑物的最短路径。（说明：校园平面图可自行绘制，或以图5-1为参考）图5-1 南阳理工学院校园平面图（粗略图）实验5 查找实验性质：验证性实验学时：2学时1、实验目的11.掌握静态查找表中折半查找算法的实现；12.掌握动态查找表中二

16、叉排序树的特点及其创造、插入、查找算法的实现。2、实验预备知识9.阅读并掌握折半查找算法的实现。10.阅读并掌握二叉排序树的插入、生成、查找的基本操作实现。3、实验内容1. 理解并运行下列程序：#includeusing namespace std;#define ENDFLAG 10000typedef int KeyType;typedef char * InfoType;typedef struct KeyType key; InfoType otherinfo;ElemType;typedef struct ElemType *R; int length;SSTable;void Cr

17、eateSTable(SSTable &ST,int n) int i; ST.R=new ElemTypen+1; cout请输入n个测试数据：; for(i=1;iST.Ri.key; ST.length=n;int Search_Bin1(SSTable ST,KeyType key) int low,high,mid; low=1; high=ST.length; while(low=high) mid=(low+high)/2; if(key=ST.Rmid.key) return mid; else if(keyhigh) return 0; mid=(low+high)/2; i

18、f(key=ST.Rmid.key) return mid; else if(keyST.Rmid.key) return Search_Bin2(ST,low,mid-1,key); else return Search_Bin2(ST,mid+1,high,key);void main() int n; KeyType key; SSTable ST; coutn; CreateSTable(ST,n); coutkey; coutSearch_Bin1算法计算的位置为：Search_Bin1(ST,key)endl; coutSearch_Bin2算法计算的位置为：Search_Bin2

19、(ST,1,ST.length,key)endl;2. 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，试编写程序创建这棵二叉排序树（要求：创建完成之后对其进行中序遍历检验其是否是递增序列以证明其正确）。实验6 排序实验性质：验证性实验学时：2学时1、实验目的1.熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、快速排序的算法实现及其性能分析；2.掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析。2、实验预备知识阅读并掌握各种排序算法的排序过程及算法实现。3、实验内容1. 理解并运行下列程序：#includeusing name

20、space std;#includetypedef int KeyType;typedef char * InfoType;typedef struct KeyType key; InfoType otherinfo;ElemType;typedef struct ElemType *R; int length;SqList;int CmpNum;void CreateList(SqList &L,int n) int i; L.R=new ElemTypen+1; srand(time(0); for(i=1;i=n;i+) L.Ri.key=rand()%100; L.length=n;v

21、oid ListTraverse(SqList L) int i; for(i=1;i=L.length;i+) coutL.Ri.keyt; cout0&flag) flag=0; for(i=1;iL.Ri+1.key) flag=1; L.R0=L.Ri+1; L.Ri+1=L.Ri; L.Ri=L.R0; m-; void main() SqList L; CreateList(L,8); cout测试数据：endl; ListTraverse(L); BubbleSort(L); cout排序后：endl; ListTraverse(L); coutBubbleSort排序方法中数据的比较次数为：CmpNumendl;2. 设待排序的关键字序列为12，2，16，30，28，10，16，20，6，18，试编写程序分别用直接插入、折半插入、希尔排序、快速排序对其进行排序。（要求：每种排序方法都有排序前后的关键字序列对比，以便验证排序结果的正确性。）