计算机科学与技术专业数据结构上机实验手册.doc

《计算机科学与技术专业数据结构上机实验手册.doc》由会员分享，可在线阅读，更多相关《计算机科学与技术专业数据结构上机实验手册.doc（34页珍藏版）》请在三一办公上搜索。

1、计算机科学与技术专业数 据 结 构上 机 实 验 手 册台州学院数学与信息工程学院计 算 机 科 学 系前 言上机实践是学生对所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。通常，实验中的问题比理论课的习题复杂得多，也更接近实际。实验课的内容一般着眼于原理与应用的结合，使学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能。另一方面，能使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。理论课习题较偏重于如何编写功能单一的“小”算法，而实验是软件设计的综合训练

2、，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能、多人合作，以至一整套软件工程规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严格的把关者。为了达到上述目的，本实验课程安排了9个独立的实验单元，各单元的训练重点在于基本数据结构的实现及其应用。各实验单元与理论教学的各章具有紧密的联系，每个实验单元安排有难度不等的多个实验题，包括必做实验内容和选作实验内容，以便学生根据自己的实际情况选做部分实验内容。每次上机实验前，要求同学们做好充分的准备，包括实验的目的要求、程序清单、测试数据和预计运算结果等，实验后写出完整的实验报告。每份实验报告包括三部分内容：实验目的和要

3、求、实验内容及实验小结。 实验报告书写规范实验报告包括三部分： 实验目的与要求 实验内容 实验小结其中，实验内容包括： 实验题目 问题分析 程序清单 测试数据 调试分析 运行结果实验一 线性表及其应用一、实验目的与要求巩固对线性表逻辑结构的理解，熟练掌握线性表的两种存储结构及线性表的基本操作在两种存储结构上的实现，掌握以线性表作为数据结构解决实际问题的方法。二、实验内容（一）顺序表操作验证1问题描述 对以顺序存储结构存储的线性表，验证其插入、删除、查找、就地逆置等操作。2基本要求用菜单实现操作选择。3测试数据自拟。（二）顺序表归并（选作）1问题描述 已知两顺序表SA、SB，其元素均为递增有序，

4、将此两表归并成一个新的顺序表SC，并保持递增顺序。2基本要求略。3测试数据（1）顺序表A：1 3 6 7 9 顺序表B：2 4 5 8。（2）自拟。4实现提示 归并处理算法思想是：依次扫描SA和SB中的元素，比较当前元素的值，将较小的元素赋给SC，直到一个顺序表扫描完毕，然后将另一个顺序表的余下的元素复制到SC中。（三）单链表操作验证1问题描述 对以链式存储结构存储的线性表，验证其插入、删除、查找、求长度和就地逆置等操作。2基本要求用菜单实现操作选择。3测试数据自拟。（四）单链表的应用（选作）1问题描述某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表存于计算机中，链表的每个

5、结点指出同样价格的电视机的台数。现在又有m台价格为h元的电视机入库。将新入库的电视机的相关数据加入链表中。2基本要求注意价格在链表中是否已出现。3测试数据自拟。4 实现提示链表结点至少包含三个域：价格、数量和指针域，其结构可如下表示： cost num next（五）一元多项式相加（选做）1问题描述求两个一元多项式A(x)=a0+a1x+a2x2+anxn 和B(x)=b0+b1x+b2x2+bmxm 的和C（x）。2基本要求算法输入为两个多项式中各项的系数和指数。算法输出为多项式的和，参考输出格式：7x0+6x1+1x2+2x4+4x9+6x11。3测试数据（1）多项式A：7+2x+5x3+

6、4x9+6x11 多项式B： 4x+x2-5x3+2x4（2）自拟。4 实现提示（1）多项式的存储结构多项式的每一项由其相应的系数和指数确定，各项间具有线性关系，因而可以采用线性表实现。鉴于多项式非零项项数的不确定性，采用单链表存储更为恰当，多项式的每一个非零项对应链表中的一个结点，且链表中的结点从头到尾按指数递增有序排列。多项式链表中的结点结构如下：coef exp next其中coef域存放项的系数，exp域存放项的指数，next域存放指向下一结点的指针。（2）求两个多项式和的算法基本思想：定义三个指针分别指向三个多项式两多项式A(x)、B(x)和C(x)的链表中的当前结点。依次扫描多项式

7、A链表和多项式B链表中各结点，作相应结点的指数比较。若指数相等，则系数相加，相加后系数若不为0，则生成一个新结点，链入多项式和C的链表，相应指针后移。若指数不相等，则对指数小的项生成一新结点，链入多项式和C的链表，相应指针后移。这一过程直到A、B链表中有一个链表扫描完毕为止。将另一个未扫描完毕的多项式中剩余项结点链入和C的链表。三、实验要求本实验最低要求为在4个学时内完成实验内容（一）和（四）。实验二 栈和队列及其应用一、实验目的与要求深入了解栈和队列的特性，以便在实际问题中灵活运用，巩固对这两种结构的构造方法的掌握。二、实验内容（一）栈操作的验证1问题描述 对于顺序栈、链栈的基本操作进行验证

8、。2基本要求考虑各种可能情况（包括溢出等）。3测试数据自拟。（二）队列操作的验证1问题描述 对于顺序队列、链队列的基本操作进行验证。2基本要求考虑各种可能情况（包括溢出等）。3测试数据自拟。（三）队列元素倒置（选做）1问题描述Q是一个非空队列，S是一个空栈。实现将Q中元素倒置。2基本要求仅使用栈和队列的基本操作及单个变量x 。3测试数据自拟。4实现提示将队列中元素出队，入栈，再将栈中元素出栈并入队。三、实验要求本实验最低要求为在4个学时内完成实验内容（一）和（二）中一种存储结构下的操作验证。四、应用举例（一）利用队列解决分油问题问题描述 设有大小不等的三个无刻度的油桶，分别能盛满x，y，z公升

9、油。初始时，第一个油桶盛满油，第二、三个油桶为空，寻找一种最少步骤的分油方式，在某一个油桶上分出targ公升油。算法输入 三个油桶的盛油量，要分出的油量targ。算法输出 分油的结果。算法要点 分油过程中，由于油桶上没有刻度，只能将油桶倒满或者倒空。三个油桶盛油的总量始终等于初始时第一个油桶盛满的油量。算法的主要思想：每次判断当前油桶是不是可以倒出油，以及其他某个油桶是不是可以倒进油。如果满足以上条件，那么当前油桶的油或全部倒出，或将另一油桶倒满，针对两种不同的情况作不同的处理。使用一个队列p，记录每次分油时各个油桶的盛油量和倒油过程等信息，队列中只记录互不相同的盛油状态（各个油桶的盛油量）。

10、如果列举出倒油过程的所有不同的盛油状态，经考察全部状态后，未能分出targ公升油的情况，就确定这个分油问题无解。队列p通过指针he和ta实现倒油过程的控制。1、算法（1）数据类型定义typedef struct int st4; int sb,eb; int last; object;object p100;int fu4;int q100;（2）分油算法void fenyou( ) int w4,w14; int he,ta,i,j,k,m,re,targ,fo,un,bo; printf(输入各油桶盛油量n); printf(1:); /输入油桶盛油量 scanf(%d,&fu1); pr

11、intf(n); printf(2:); scanf(%d,&fu2); printf(n); printf(3:); scanf(%d,&fu3); printf(n); printf(要分出的油量:); /输入要分出的油量 scanf(%d,&targ); printf(n); fo=FALSE; /标志，TRUE表示分油成功，FALSE表示分油失败 un=FALSE; he=1; /he 队列的头指针，ta 队列的尾指针 ta=1; p1.st1=fu1; /油桶初始状态：1 满，2、3空 p1.st2=0; p1.st3=0; p1.sb=1; p1.eb=1; p1.last=1;

12、do /分油过程 w1=phe.st1; w2=phe.st2; w3=phe.st3; i=0; while (i0) j=0; while (j3)&(!fo)&(!un) j=j+1; if (wjre) w1j=fuj; w1i=wi-re; else w1i=0; w1j=wj+wi; bo=FALSE; k=1; while (k=ta)&(!bo) bo=TRUE; for (m=1;m=3;m+) if (w1m!=pk.stm) bo=FALSE; k=k+1; if (!bo) ta=ta+1; /分油的一个步骤入队 pta.st1=w11; pta.st2=w12; pt

13、a.st3=w13; pta.sb=i; pta.eb=j; pta.last=he; for (m=1;mta) un=TRUE; while (!fo&!un); printf(分油过程:n); if (!fo) /分油失败 printf(失败); else /分油成功，将分油过程的步骤依次输出 k=0; i=ta; while (i!=1) k=k+1; qk=i; i=pi.last; for (;k=1;k-) printf(%2d-%2d,pqk.sb,pqk.eb); printf(%3d%3d%3d,pqk.st1, pqk.st2, pqk.st3); printf(n);

14、2、程序#include typedef struct int st4; int sb,eb; int last; object;object p100;int fu4;int q100;/各算法清单同前 void main( )fenyou( );3、测试数据三个油桶盛油量分别为：80 50 30要分出的油量为：404、程序运行结果分油过程：1-2 30 50 0 2-3 30 20 30 3-1 60 20 0 2-3 60 0 20 1-2 10 50 20 2-3 10 40 30（二） 迷宫问题问题描述 编写一个程序求解迷宫问题。迷宫是一个如图2.6所示的m行n列的0、1矩阵，其中0

15、表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。算法输入 代表迷宫人口的坐标（默认取1，1）。算法输出 穿过迷宫的结果，两种情况之一： 穿越成功，输出路径； 穿越失败，给出提示。算法要点要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可走时，退回一步，重新选择未走过的可走的路，如此继续，直至到达出口或返回入口（无法通过迷宫）。可使用如下的数据结构：mg1.m,1.n表示迷宫，为避免在走迷宫时出界，将迷宫数组的边界以1包围起来

16、，所以一个mn大小的迷宫，则需要一个（m+2）(n+2)大小的数组表示，即mg0.m+1,0.n+1表示迷宫，用数组zx，zy分别表示X，Y方向的移动增量，其值如表2.1所示。在探索前进路径时，需要将搜索的踪迹记录下来，记录的踪迹应包含当前位置以及前趋位置。在搜索函数中，将所有需要搜索的位置形成一个队列，将队列中的每一个元素可能到达的位置加入到队列中，当队列中某元素有可能到达的位置全部加入到队列之后，即从队列中将该元素去掉。用变量front和rear分别表示队列的首与尾，当rear指示的元素已到达出口（m，n）时，根据rear所指示的前驱号可回溯得到走迷宫的最短路径。表2.1 zx，zy数组的

17、方向取值方向北东北东东南南西南西西北下标12345678zx-1-101110-1zy01110-1-1-1入口出口图2.1 迷宫示意图1、算法（1）类型定义 迷宫定义int mgm+2n+2; 定义struct stypeint x,y,pre; sq400;（3）方向数组定义int zx8,zy8;（2）操作算法输出路径算法void printpath( int rear) int i,j; structstype p100; i=rear; do printf(%d,%d),sqi.r,sqi.c); i=sqi.pre; while(i!=0); 走迷宫算法void mgpath( )

18、 int i,j,x,y,v,find,rear,front; sq1.r=1; sq1.c=1; sq1.pre=0; find=0; j=0; front=1; /从（1，1）开始搜索 rear=1; mg11=-1; while(front=rear&!find) x=sqfront.r; y=sqfront.c; for(v=0;v8;v+) /循环扫描每个方向 i=zxv+x; /选择一个前进方向（i,j） j=zyv+y; if (mgij=0) /如果该方向可走 rear+; /进入队列 sqrear.r=i; sqrear.c=j; sqrear.pre=front; mgij

19、=- /避免搜索过的位置重复搜索 if (i=m&j=n) /找到了出口 printpath(rear); find=1; front+; if (!find) printf(不存在路径！);2、程序#include #define m 8 /m、n为迷宫的行、列数，可以自选 #define n 8struct stype int r,c,pre; sq400;int mgm+2n+2;int zx8=-1,-1,0,1,1,1,0,-1,zy8=0,1,1,1,0,-1,-1,-1;/各算法清单同前 void main() int i,j; printf(输入迷宫:); for(i=0;i=

20、m+1;i+) printf(第%d行:n,i); for(j=0;j=n+1;j+) scanf(%d,&mgij); printf(输出迷宫:); for(i=0;i=m+1;i+) for(j=0;jdata=ch; s-lchild=NULL; s-rchild=NULL; rear+; Qrear=s; /虚结点指针NULL或新结点地址入队 if(rear=1) /输入的第一个结点为根结点 root=s; else if(s&Qfront) /孩子和双亲结点均不是虚结点 if(rear%2=0) Qfront-lchild=s; /新结点是左孩子 else Qfront-rchild

21、=s; /新结点是右孩子 if(rear%2=1) front+; /结点*Qfront的两个孩子已处理完毕，出队列 ch=getchar(); /输入下一个字符 return root; /返回根指针 （二）二叉树的线索化1问题描述对二叉树进行中序线索化。2基本要求 以二叉链表作为存储结构，并对该线索二叉树进行中序遍历。3测试数据自拟。三、实验要求本实验要求为在4个学时内完成实验内容（一）和（二）。实验六 树的应用一、实验目的与要求通过应用树结构解决实际问题，掌握树的实际应用，从而将理论与实际结合起来。二、实验内容（一）借助二叉排序树实现排序1问题描述对于给定的n个关键字值，采用二叉排序树方

22、法对其进行排序。2基本要求 以二叉链表作为存储结构。3测试数据自拟。4实现提示整个问题的求解可抓住以下重点: 采用建立二叉排序树的方法，将n个键值作为结点值，生成一棵二叉排序树。 对生成的二叉排序树进行中序遍历，得到递增序列。（二）哈夫曼树的构造1问题描述对于给定的n 个结点的权值，建立一棵哈夫曼树。2基本要求 详细说明所采用的哈夫曼树的存储格式及输出方式。3测试数据（1）7个叶子结点，权值分别为：7 5 2 3 8 10 20（2）自拟。（三）标识符的处理（选做）1问题描述识别源程序文件“b.txt”中出现的标识符，并按字母顺序输出这些标识符及所在的行号序列，对于同一个标识符出现的不同行号，

23、要求按递增的顺序排序输出。2基本要求 无。3测试数据自拟。4实现提示算法分两步实现: 识别标识符，形成一棵二叉排序树。树结点的键值为标识符的前10个字符，并将同一标识符所在的不同行号按从小到大的顺序存放在一个链式队列中。二叉排序树中的结点数据域及左、右指针域之外，增设两个分别指向链表的首结点和尾结点的指针域。如下图所示： 输出标识符和相应的行号序列。按中序遍历由标识符组成的二叉排序树，输出结点中的标识符及行号队列中的行号。三、实验要求本实验最低要求为在4个学时内完成实验内容（一）和（二）。实验七 图及其应用一、实验目的与要求掌握图的存储结构在计算机中的实现，将图的相关理论应用到解决实际问题的过

24、程中，深入理解数据结构理论在解决实际问题中的作用，锻炼综合设计能力。二、实验内容（一）以邻接矩阵为存储结构的图的遍历1问题描述对以邻接矩阵为存储结构的图实现深度优先搜索和广度优先搜索遍历。2基本要求采用连通无向图作为遍历对象。3测试数据自拟。（二）以邻接表为存储结构的图的遍历1问题描述对以邻接表为存储结构的图实现深度优先搜索和广度优先搜索遍历。2基本要求采用连通无向图作为遍历对象，建立邻接表时顶点对序号从大到小输入。3测试数据自拟。（三）求图中两顶点间给定长度的简单路径1问题描述利用遍历图的方法输出一个无向图中从顶点vi到顶点vj的长度为l的简单路径。2基本要求无向图采用邻接表作为存储结构，顶

25、点用整数编号表示。3测试数据自拟。4实现提示算法思想：利用深度优先搜索遍历图，并设一个栈（stack）保存遍历路径上的顶点，同时以变量d记下当前的路径长度。从v=vi出发，找v的邻接顶点w，若w已访问过，则找下一个邻接顶点；若w=vj，且d=l-1，则路径即为所求；若wvj，且dl-1，则从w出发继续遍历，否则找下一个邻接顶点，若找不到下一个邻接顶点（设w=0），则退栈，找前一顶点的下一个邻接顶点，若栈空，则说明没有这样的路径。（四）医院选址问题1问题描述n个村庄之间的交通图用有向加权图表示，图中的有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择

26、一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2基本要求无。3测试数据题中所给加权有向图。4实现提示这是一个求有向图中心点的问题。设图G=（V，E），对任一顶点k，称E（k）=为顶点k的偏心度，偏心度最小的顶点即为图G的中心点。图中所示的加权有向图中，其各顶点的偏心度如表所示。表1 顶点的偏心度顶 点偏心度ab6c8d5e7d是具有最小偏心度的顶点，所以图G的中心点是顶点d。算法分三步实现： 对加权有向图G，调用Floyd算法，求每对顶点间最短路径长度的矩阵length。 对矩阵length的每一列求最大值 E（j）=，即得各顶点j的偏心度。 求出具有最小偏心

27、度的顶点k ， 使得E（k）=，顶点k即为图的中心点。三、实验要求本实验最低要求为在6个学时内完成：1实验内容（一）或（二）中一题。 2实验内容（三）或（四）中一题。实验八 查找一、实验目的与要求本实验验证数据处理的重要技术之一：查找。通过对不同查找技术的实践，注意查找操作的效率，理解提高查找的效率是提高其他操作效率的基础。二、实验内容（一）有序线性表的查找1问题描述 在有序表sortlist中插入一个元素x，并保持表的有序性。2基本要求 利用二分查找方法完成。3测试数据 根据以下数据类型定义自拟。typedef char datatype;typedef int keytype;typede

28、f struct keytype key; datatype temp80; TABLE; / 定义有序线性表类型 TABLE sortlist20; / 定义有序线性表 在程序中构造线性表sortlist时应使表中结点按关健字有序排列。4实现提示（1）先在有序表中利用二分查找算法查找关健字等于或小于x.key的结点，查找思想如下： 定义有序表的两个端点值：low=0; high=表长； 定义折半点：mid = (low+high)/2； 将待查值x.key与折半点(mid)处结点的关健字进行比较：若x.key与listmid.key相等：查找结束，mid即插入位置；若x.key大于listm

29、id.key：low=mid+1（定义右子表）；若x.key小于listmid.key：high=mid-1（定义左子表）。 反复执行、，直到插入位置（mid或low）确定。（2）将插入位置后的结点全部右移一个结点位置，并将新结点放入插入位置。（二）树表的查找1问题描述 设计一个在二叉排序树中查找指定结点并对该结点进行修改的非递归算法。2测试数据 为提高树表查找的可操作性，算法中的输入数据可由数据文件TREE.TXT提供。文件内每一行可视作一个结点，行首数字为结点关键字，文件末尾的数字-1可做为文件读取结束的标志。树表建立的结果输出到文件TREELIST.TXT中，而查找结果输出到文件。SEARCH.T