《数据结构实验-线性表及其应用.docx》由会员分享，可在线阅读，更多相关《数据结构实验-线性表及其应用.docx（11页珍藏版）》请在三一文库上搜索。
1、实验 1 线性表及其应用实验性质：验证性实验学时： 2 学时一、实验目的1. 掌握线性表的顺序存储结构在计算机的表示方法及其基本操作的实现；2. 掌握线性表的链式存储结构在计算机的表示方法及其基本操作的实现；3. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。二、实验预备知识1. 复习C/C+语言相关知识(如：结构体的定义、typedef的使用、函数的定义、调用及参数传递方式) ；2. 阅读并掌握顺序表与链表的类型定义及其查找、插入、删除等基本操作。三、实验内容1. 理解并分别用顺序表、链表的操作运行下列程序：#include <iostream>using names
2、pace std;#include "Status.h"typedef int ElemType;#i nclude "SqList.h"/ 用 #i nclude "Li nkList.h" 替换void main()SqList L;/用 LinkList L; 替换，与 #include "LinkList.h" 配合int n,i;ElemType e;InitList(L);cout<<"nL="ListTraverse(L);cout<<"n 请设置
3、将向线性表 L 中输入的元素个数： "cin>>n;CreateList(L,n);cout<<"nL="ListTraverse(L);cout<<"nL 的表长为： "<<ListLength(L)<<endl;cout<<"n 请输入想要获取的元素位序： "cin>>i;if(GetElem(L,i,e) cout<<"n 第 "<<i<<" 个元素为： "&l
4、t;<e<<endl;else cout<<"n 第 "<<i<<" 个元素不存在！ "<<endl;cout<<"n 请输入要查找的元素："cin>>e;if(i=LocateElem(L,e) cout<<"n元素 "<<e<<" 的位置为： "<<i<<endl;else cout<<"n 元素 "<&l
5、t;e<<" 不存在！ "<<endl;cout<<"n 请输入插入位置和所插入元素： " cin>>i>>e;if(ListInsert(L,i,e)cout<<"nL=" ListTraverse(L);else cout<<"n 插入操作失败！ "<<endl; cout<<"n 请输入被删元素的位置： " cin>>i;if(ListDelete(L,i,e) cout
6、<<"n 被删元素为： "<<e<<endl; else cout<<"n 删除操作失败！ "<<endl;cout<<"nL=" ListTraverse(L);本题目说明：( 1)头文件 Status.h 的内容如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;( 2)头文件
7、SqList.h (内容包括顺序表的结构定义及基本操作实现) 。 ( 3)头文件 LinkList.h (内容包括链表的结构定义及基本操作实现) 。 (4)顺序表中基本操作的补充：CreateList(&L,n):向顺序表 L 中输入 n 个元素(Ow n< MAXSIZE )。 Status CreateList(SqList &L,int n)int i; if(!L.elem|n<O|n>MAXSIZE) return ERROR;cout<<"n 请输入 "<<n<<" 个元素: &qu
8、ot; for(i=1;i<=n;i+)cin>>L.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+)cout<<L.elemi-1<<','if(L.length) cout<<"b)"&
9、lt;<endl;else cout<<')'<<endl;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 学时一、实验目的1. 掌握栈的特点、在计算机中的存储表示方法及其基本操作的实现；2. 掌握队列的特点、在计算机中的存储表示方法及其基本操作的实现；3. 能够利用栈和队列求解一些
10、常见问题。二、实验预备知识1. 阅读并掌握顺序栈、链栈两种存储方法的类型定义及其压栈、弹栈等基本操作。2. 阅读并掌握循环队列、链队列两种存储方法的类型定义及其入队、出队等基本操作。三、实验内容1. 理解并用顺序栈操作运行下列程序：#include <iostream>using namespace std;#include "Status.h" typedef int ElemType;#include "SqStack.h"void main()SqStack S;ElemType e;InitStack(S);Push(S,2);Pus
11、h(S,4);Push(S,6);Push(S,8);cout<<"n 由栈底至栈顶的元素为： "StackTraverse(S);cout<<"n 栈的长度为： "<<StackLength(S)<<endl; GetTop(S,e);cout<<"n 栈顶元素为： "<<e<<endl;Pop(S,e);cout<<"n 由栈底至栈顶的元素为： "StackTraverse(S);cout<<"
12、n 栈的长度为： "<<StackLength(S)<<endl; GetTop(S,e);cout<<"n 栈顶元素为： "<<e<<endl;2. 理解并用循环队列、链队列操作运行下列程序：#include <iostream> using namespace std;#include "Status.h"typedef int ElemType;#include "SqQueue.h"void main()SqQueue Q;ElemType e;
13、InitQueue(Q);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);GetHead(Q,e);cout<<"n 队头元素为： "<<e<<endl;cout<<"n 队列中从队头至队尾的元素为： " QueueTraverse(Q);cout<<"n 队列的长度为： "<<QueueLength(Q)<<endl; DeQueue(Q,e);cout<<"n 出队的元素
14、为： "<<e<<endl;cout<<"n 出队操作完成之后队列中从队头至队尾的元素为： "QueueTraverse(Q); cout<<"n 队列的长度为： "<<QueueLength(Q)<<endl; 本题目说明：( 1)头文件 Status.h 的内容同实验 1。( 2)头文件 SqStack.h (内容包括顺序栈的结构定义及基本操作实现)。( 3)头文件 SqQueue.h (内容包括循环队列的结构定义及基本操作实现)。 (4)顺序栈中基本操作的补充：Sta
15、ckTraverse(S) ：从栈底到栈顶依次对 S 的每个数据元素进行访问。 void StackTraverse(SqStack S)ElemType *p;p=S.base;while(p!=S.top) cout<<*p+<<" " cout<<endl; (5)循环队列中基本操作的补充：QueueTraverse(L):从队头到队尾，依次对Q的每个数据元素访问。void QueueTraverse(SqQueue Q)int i;i=Q.front; while(i!=Q.rear)cout<<Q.basei<
16、<" " i=(i+1)%MAXSIZE;cout<<endl;3. 从键盘输入一个表达式，试编写算法计算表达式的值。4. 有n个人围成一圈，从第 1个人开始，1, 2，m报数，报至m出局，余下的 人继续从1, 2,，m报数，重复之前的流程，要求：求出被淘汰编号的序列， 及最后剩下的一人是原来的第几号？（要求：用循环队列解决该问题。 ）实验 3 树和二叉树实验性质：验证性实验学时： 4 学时一、实验目的4. 掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现；5. 能够利用二叉树求解一些常见问题。二、实验预备知识3. 阅读并掌握二叉树二叉链表存储
17、方法的类型定义及其创建、遍历等基本操作。4. 阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。三、实验内容1. 理解并用二叉链表的操作运行下列程序： #include <iostream> using namespace std;#include "Status.h" typedef char ElemType;#include "BiTree.h" void main()BiTree T;CreateBiTree(T);cout<<" 二叉树的深度为： "<<Depth(T)<<
18、endl;cout<<" 二叉树中结点个数为： "<<NodeCount(T)<<endl;cout<<" 二叉树中叶子结点个数为： "<<LeavesNodeCount(T)<<endl; cout<<" 先序遍历： "PreOrderTraverse(T); cout<<"n 中序遍历： "InOrderTraverse(T);cout<<"n 后序遍历： "PostOrderTrav
19、erse(T); cout<<endl;本题目说明：（ 1）头文件 Status.h 的内容同实验 1。（ 2）头文件 BiTree.h （内容包括二叉树的二叉链表中结点的结构定义及二叉链表 基本操作的实现）。（3）基本操作的补充：LeavesNodeCount（T） ：二叉树中叶子结点的个数。int LeavesNodeCount(BiTree T) if(!T) return 0;else if(!T->lchild&&!T->rchild) return 1;else return LeavesNodeCount(T->lchild)+Lea
20、vesNodeCount(T->rchild);2. 已知某系统在通信联络中只可能出现 8种字符， 其概率分别为 0.05 ，0.29 ，0.07 ， 0.08 ， 0.14 ，0.23 ， 0.03 ，0.11 ，试编写算法求其赫夫曼编码。实验 4 图实验性质：综合性实验学时： 2 学时一、实验目的6. 掌握有向图、无向图在计算机的表示方法及其基本操作的实现；7. 能够利用图形结构对实际问题进行分析建模，利用计算机求解。二、实验预备知识5. 阅读并掌握有向图（网） 、无向图（网）用邻接矩阵和邻接表两种存储方法的类型定义及 其创建、遍历等基本操作。6. 阅读并掌握最短路径中迪杰斯特拉算法
21、的实现。三、实验内容1. 理解并分别用邻接矩阵、邻接表的操作运行下列程序：#include<iostream>#include"Status.h"using namespace std;#include"MGraph.h"void main（）MGraph G;int i;CreateUDG（G）;cout<<"n 深度优先遍历序列为： " TraverseDFS（G）;cout<<"n 广度优先遍历序列为： "for（i=0;i<G.vexnum;i+） visitedi
22、=false;TraverseBFS（G）; cout<<endl;本题目说明：（ 1）头文件 Status.h 的内容同实验 1。（ 2）头文件 MGraph.h （内容包括图采用邻接矩阵存储的结构定义及基本操作实 现）。2. 以南阳理工学院校园平面图为例，试编写程序输出从学校大门到其他各建筑物的最短路 径。（说明：校园平面图可自行绘制，或以图 5-1 为参考）1大门m操场46号宿含5 一小礼當召-下沉广场7.孝苑琴亍&专宝公題 虫教丄2村 m解池11.9#独学糧12込较学檢 薛1辟教学橫 14学生广场 讣.网斥场图5-1南阳理工学院校园平面图（粗略图）16冻均耀厅实验
23、5 查找 实验性质：验证性 实验学时： 2 学时一、实验目的8. 掌握静态查找表中折半查找算法的实现；9. 掌握动态查找表中二叉排序树的特点及其创造、插入、查找算法的实现。二、实验预备知识7. 阅读并掌握折半查找算法的实现。8. 阅读并掌握二叉排序树的插入、生成、查找的基本操作实现。三、实验内容1. 理解并运行下列程序： #include<iostream> using namespace std; #define ENDFLAG 10000 typedef int KeyType; typedef char * InfoType; typedef struct KeyType k
24、ey;InfoType otherinfo;ElemType; typedef structElemType *R;int length;SSTable;void CreateSTable(SSTable &ST,int n)int i;ST.R=new ElemTypen+1; cout<<" 请输入 "<<n<<" 个测试数据： " for(i=1;i<=n;i+) cin>>ST.Ri.key;ST.length=n;int Search_Bin1(SSTable ST,KeyType
25、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(key<ST.Rmid.key) high=mid-1;else low=mid+1;return 0;int Search_Bin2(SSTable ST,int low,int high,KeyType key)int mid;if(low>high) return 0;mid=(low+high)/2;if(key=ST.Rmid.key) re
26、turn mid;else if(key<ST.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;cout<<" 请输入静态查找表长： "cin>>n;CreateSTable(ST,n);cout<<" 请输入待查记录的关键字： "cin>>key;cout<<"Sear
27、ch_Bin1 算法计算的位置为： "<<Search_Bin1(ST,key)<<endl;cout<<"Search_Bin2 算 法 计 算 的 位 置 为 ： "<<Search_Bin2(ST,1,ST.length,key)<<endl;2. 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2， 13，9，21，4，试编写程序创建这棵二叉排序树(要求：创建完成之后对其进行中序遍历 检验其是否是递增序列以证明其正确) 。实验 6 排序实验性质：验证性 实验学时： 2 学时一
28、、实验目的快速排序的算法1. 熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、 实现及其性能分析；2. 掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析。二、实验预备知识阅读并掌握各种排序算法的排序过程及算法实现。三、实验内容1. 理解并运行下列程序： #include<iostream> using namespace std; #include<time.h> typedef int KeyType; typedef char * InfoType; typedef struct KeyType key;InfoType otherinfo;E
29、lemType;typedef structElemType *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;void ListTraverse(SqList L)int i;for(i=1;i<=L.length;i+)cout<<L.Ri.key<<'t'cout<<
30、;endl;void BubbleSort(SqList &L)int m,flag,i;m=L.length-1;flag=1;while(m>0&&flag)flag=0;for(i=1;i<=m;i+)CmpNum+;if(L.Ri.key>L.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);"<<CmpNum<<endl;cout<<"BubbleSort 排序方法中数据的比较次数为： 2. 设待排序的关键字序列为 12，2，16，30，28，10，16，20，6，18 ，试编写程序分别用直接插入、折半插入、希尔排序、快速排序对其进行排序。 （要求：每种排序方法都有排序前后的关键字序列对比，以便验证排序结果的正确性。)