数据结构实验指导书
吉林大学珠海学院计算机系
2012.12
实验目的与要求
《数据结构》是计算机学科重要的专业基础课,北京市高校已将该课作为理工科非计算机专业的提高课程,北京大学将此课列为理工科非计算机专业必修课已经超过15 年。该课程主要研究信息在计算机中的组织和表示方法。上机实验是本课程教学至关重要的环节,通过上机实验,使学生在数据结构的逻辑结构定义、存储表示、操作的实现、数据结构的选择和应用、算法实践等方面加深对课程内容的理解,训练学生进行复杂程序设计的技能和培养良好程序设计的习惯。
考虑到大一上学期学习过C程序设计,本学期有C课程设计和C++程序设计,故数据结构课程的实验不安排验证性实验,按课程设计要求。具体说是期初布置题目,按学号顺序确定如下题目,学生自己准备,期中检查,15周开始验收。验收时间安排在周末。
实验内容
从以下题目中选一题
题目一、航空客运订票系统
题目二、文章编辑
题目三、宿舍管理查询软件
题目四、校园导航系统
题目五、散列法的实验研究
题目六、小型图书馆管理系统(链表的插入,排序,查询,删除)
题目七、学生搭配问题
题目八、敢死队问题
题目九、教学计划编制问题
题目十、活期储蓄帐目管理
题目十一、通讯录的制作
题目十二、二叉排序树的实现
题目十三、利用栈求表达式的值
题目十四、走迷宫游戏
题目十五、顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现
题目十六、线索二叉树的应用
题目十七、稀疏矩阵实现与应用
题目十八、树的应用
题目十九、图的遍历和生成树求解实现
题目二十、排序综合
题目二十一、纸牌游戏
题目二十二、利用栈求表达式的值,可供小学生作业,并能给出分数
题目二十三、数制转换问题
题目二十四、停车场问题
题目二十五、学生成绩管理系统
题目二十六、哈夫曼编码/译码器
题目二十七、特殊矩阵的压缩存储算法的实现
题目二十八、产品进销存管理系统
题目二十九、客户消费积分管理系统
题目三十、约瑟夫环
题目三十一、任意长的整数加法
题目三十二、广义表的应用
题目三十三、关键路径问题
题目三十四、构造可以使n个城市连接的最小生成树
题目三十五、神秘国度的爱情故事
题目三十六、利用Hash技术统计C源程序中关键字的频度
题目一、航空客运订票系统
通过此系统可以实现如下功能:
录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定);
查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓);可以输入起飞抵达城市,查询飞机航班情况;
订票:(订票情况可以存在一个数据文件中,结构自己设定)可以订票,如果该航班已经无票,可以提供相关可选择航班;
退票:可退票,退票后修改相关数据文件;客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。
修改航班信息:当航班信息改变可以修改航班数据文件
要求:根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能;
题目二、文章编辑
功能:输入一页文字,程序可以统计出文字、数字、空格的个数。
静态存储一页文章,每行最多不超过80个字符,共N行;要求(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移。
要求:
存储结构使用线性表,分别用几个子函数实现相应的功能;
输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"(3)输出删除某一字符串后的文章;
题目三、宿舍管理查询软件
1.任务:为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求:
A.采用交互工作方式
B.建立数据文件,数据文件按关键字(姓名、学号、房号)进行排序(分别用冒
泡、选择、插入排序实现)
2.查询菜单: (用二分查找实现以下操作)
C.按姓名查询
D.按学号查询
E.按房号查询
打印任一查询结果并可以连续操作
题目四、校园导航系统
设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
题目五、散列法的实验研究
基本要求:
1、设每个记录有下列数据项:电话号码、用户名、地址;
2、从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;
3、采用一定的方法解决冲突;
4、查找并显示给定电话号码的记录;
5、查找并显示给定用户名的记录。
进一步完成内容:
1、设计不同的散列函数,比较冲突率;
2、在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变
化。
题目六、小型图书馆管理系统(链表的插入,排序,查询,删除)
对C语言软件开发有一定的认识,了解并掌握开发的各个流程,以及各功能代码的实现。创建一个图书馆管理系统,可进行还书(插入),排序,查找,借书(删除)操作。
【设计原理】
1.所有信息存储在一个带头结点的单向链表中,每个结点存储一条图书记录,即结构体(book),其中各域为:书号(number)、书名(title)、作者(writer)、定价(pricing)、出版社(publishinghouse),指针域(next)。
2.系统初始时图书记录为空,由用户录入信息,进行插入(包括创建),排序,查找,删除操作。
3.有两种排序算法可选:选择排序和直接插入排序,均由链表实现。
4.如输入有错,给出出错提示。
题目七、学生搭配问题
一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的
两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.
请设计一系统模拟动态地显示出上述过程,要求如下:
1、输出每曲配对情况
2、计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.
至少求出K的两个值.
3、尽量设计出多种算法及程序
4、提示:用队列来解决比较方便.
题目八、敢死队问题
有M个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。
排长是不愿意去的,假设排长为1号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
题目九、教学计划编制问题
题目十、活期储蓄帐目管理
活期储蓄处理中,储户开户、销户、存入、支出活动频繁,系统设计要求:
能比较迅速地找到储户的帐户,以实现存款、取款记账;
能比较简单,迅速地实现插入和删除,以实现开户和销户的需要。
题目十一、通讯录的制作
模块要求:
第一个模块——主函数main()的功能是:根据选单的选项调用各函数,并完成相应的功能。第二个模块——Menu()的功能是:显示英文提示选单。
第三个模块——Quit()的功能是:退出选单。
第四个模块——Create()的功能是:创建新的通讯录。
第五个模块——Add()的功能是:在通讯录的末尾,写入新的信息,并返回选单。
第六个模块——Find()的功能是:查询某人的信息,如果找到了,则显示该人的信息,如果未找到,则提示通讯录中没有此人的信息,并返回选单。
第七个模块——Alter()的功能是:修改某人的信息,如果未找到要修改的人,则提示通讯录中没有此人的信息,并返回选单。
第八个模块——Delete()的功能是:删除某人的信息,如果未找到要删除的人,则提示通讯录中没有此人的信息,并返回选单。
第九个模块——List()的功能是:显示通讯录中的所有记录。;
设计要求:
每条信息至包含:姓名(NAME )、性别(GENDER)、电话(TEL)、城市(CITY)邮编(EIP)几项。
作为一个完整的系统,应具有友好的界面和较强的容错能力
题目十二、二叉排序树的实现
用顺序和二叉链表作存储结构
1) 以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;
2) 对二叉排序树T作中序遍历,输出结果;
3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历
(执行操作2);否则输出信息“无x”;
题目十三、利用栈求表达式的值
编写程序实现表达式求值,即验证某算术表达式的正确性,若正确,则计算该算术表达式的值。
主要功能描述如下:
1、从键盘上输入表达式。
2、分析该表达式是否合法:
(1)是数字,则判断该数字的合法性。若合法,则压入数据到堆栈中。
(2)是规定的运算符,则根据规则进行处理。在处理过程中,将计算该表达式的值。(3)若是其它字符,则返回错误信息。
3、若上述处理过程中没有发现错误,则认为该表达式合法,并打印处理结果。
程序中应主要包含下面几个功能函数:
void initstack():初始化堆栈
int Make_str():语法检查并计算
int push_operate(int operate):将操作码压入堆栈
int push_num(double num):将操作数压入堆栈
int procede(int operate):处理操作码
int change_opnd(int operate):将字符型操作码转换成优先级
int push_opnd(int operate):将操作码压入堆栈
int pop_opnd():将操作码弹出堆栈
int caculate(int cur_opnd):简单计算+,-,*,/
double pop_num():弹出操作数
题目十四、走迷宫游戏
程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。
要求:
老鼠形象可辨认,可用键盘操纵老鼠上下左右移动;
迷宫的墙足够结实,老鼠不能穿墙而过;
正确检测结果,若老鼠在规定时间内走到粮仓处,提示成功,否则提示失败;
添加编辑迷宫功能,可修改当前迷宫,修改内容:墙变路、路变墙;
找出走出迷宫的所有路径,以及最短路径。
利用序列化功能实现迷宫地图文件的存盘和读出等功能
题目十五、顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。
设有一元多项式A m(x)和B n(x).
A m(x)=A0+A1x1+A2x2+A3x3+… +A m x m
B n(x)=B0+B1x1+B2x2+B3x3+… +B n x n
请实现求M(x)= A m(x)+B n(x)、M(x)= A m(x)-B n(x)和M(x)= A m(x)×B n(x)。
题目十六、线索二叉树的应用
要求:实现线索树建立、插入、删除、恢复线索的实现。
题目十七、稀疏矩阵实现与应用
要求:实现三元组,十字链表下的稀疏矩阵的下列应用。
(1)稀疏矩阵的存储
(2)稀疏矩阵加法
(3)矩阵乘法
(4)矩阵转置
题目十八、树的应用
要求:实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现。
题目十九、图的遍历和生成树求解实现
要求:
先任意创建一个图;
图的DFS,BFS的递归和非递归算法的实现
最小生成树(两个算法)的实现,求连通分量的实现
要求用邻接矩阵、邻接表、十字链表多种结构存储实现
题目二十、排序综合
利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。
要求:
至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
如果采用4种或4种以上的方法者,可适当加分。
题目二十一、纸牌游戏
任务:编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后…从第4张开始,以4为基数,是4的倍数的牌翻一次,直到最后一张牌;...再依次5的倍数的牌翻一次,6的,7的直到以52为基数的翻过,输出:这时正面向上的牌有哪些?
题目二十二、利用栈求表达式的值,可供小学生作业,并能给出分数。
要求:建立试题库文件,随机产生n个题目;题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价
题目二十三、数制转换问题
任意给定一个M进制的数x ,请实现如下要求
1)求出此数x的10进制值(用MD表示)
2)实现对x向任意的一个非M进制的数的转换。
3)至少用两种或两种以上的方法实现上述要求(用栈解决,用数组解决,其它方法解决)。
题目二十四、停车场问题
停车场是一条可以停放n辆车的狭窄通道,且只有一个大门汽车停放安到达时间的先后依次由北向南排列(大门在最南端,最先到达的第一辆车停在最北端)若停车场已经停满n辆车,后来的汽车在便道上等候,一旦有车开走,排在便道上的第一辆车可以开入;当停车场的某辆车要离开时,停在他后面的车要先后退为他让路,等它开出后其他车在按照原次序开入车场,每两停在车场的车要安时间长短缴费。要求:以栈模拟停车场,以队列车场外的便道,按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为:若是车辆到达,则输出汽车在停车场的内或便道上的位置:若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用(在便道上的停留时间不收费)。栈以顺序结构实现,队列以链表结构实现。
题目二十五、学生成绩管理系统
现有学生成绩信息文件1(1.txt),内容如下
姓名学号语文数学英语
张明明01677882
李成友02789188
张辉灿03688256
王露04564577
陈东明05673847
….......…
学生成绩信息文件2(2.txt),内容如下:
姓名学号语文数学英语
陈果31576882
李华明32889068
张明东33484256
李明国34504587
陈道亮35475877
…. ......…
试编写一管理系统,要求如下:
1)实现对两个文件数据进行合并,生成新文件3.txt
2)抽取出三科成绩中有补考的学生并保存在一个新文件4.txt
3)合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)
4)输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)
5)要求使用结构体,链或数组等实现上述要求.
6)采用多种方法且算法正确者,可适当加分.
题目二十六、哈夫曼编码/译码器
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
【基本要求】
1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中)
2)分别采用动态和静态存储结构
3)初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;
4)编码:利用建好的哈夫曼树生成哈夫曼编码;
5)输出编码;
6)设字符集及频度如下表:
字符空格A B C D E F G H I J K L M
频度186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符N O P Q R S T U V W X Y Z
频度57 63 15 1 48 51 80 23 8 18 1 16 1
【进一步完成内容】
1)译码功能;
2)显示哈夫曼树;
3)界面设计的优化。
题目二十七、特殊矩阵的压缩存储算法的实现
问题描述:对于特殊矩阵可以通过压缩存储减少存储空间。
基本要求:
1.针对多种特殊矩阵进行压缩存储,并能显示压缩后的相关地址和值;
2.输入在原来特殊矩阵中的地址,要求能从压缩后的矩阵中读出相应的值;
题目二十八、产品进销存管理系统
问题描述:针对某一种行业的库房的产品进销存情况进行管理。
基本要求:
采用一定的存储结构对库房的货品及其数量进行分类管理;
可以进行产品类的添加、产品的添加、产品数量的添加;
能够查询库房每种产品的总量、进货日期、销出数量、销售时间等;
题目二十九、客户消费积分管理系统
问题描述:针对客户的消费情况,进行客户管理,根据客户的消费积分对客户实行不同程度的打折优惠。
基本要求:
采用一定的存储结构进行客户信息的存储;
对客户的信息可以进行修改、删除、添加;
能够根据消费情况进行客户积分的计算;
根据积分情况实行不同程度的打折优惠;
题目三十、约瑟夫环
问题描述:编号为1,2… n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个开始重新从1报数,如此下去,直至所有人全部出列为止,设计一个程序求出出列顺序。
基本要求:
1、利用单循环链表作为存储结构模拟此过程;
2、键盘输入总人数、初始报数上限值m及各人密码;
3、按照出列顺序输出各人的编号。
题目三十一、任意长的整数加法
问题描述:设计一个程序实现两个任意长的整数的求和运算。
基本要求:利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。如:1,0000,0000,0000,0000。
题目三十二、广义表的应用
由于广义表在结构上较线性表复杂得多,因此,广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。
本设计用一个主控菜单程序控制,共分为6个子系统。
(1).建立广义表
(2)输出广义表
(3)结点的查找
(4)求广义表表头
(5)求广义表表尾
(6)求广义表的深度
题目三十三、关键路径问题
问题描述:设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求:
(1)对一个描述工程的AOE网,应判断其是否能够顺利进行。
(2)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。
题目三十四、构造可以使n个城市连接的最小生成树
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。
基本要求:
1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。
2、表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)
3、最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。
题目三十五、神秘国度的爱情故事
输入要求:输入由若干组测试数据组成。
每组数据的第1行包含一正整数N(1≤N≤50000),代表神秘国度中小村的个数,每个小村即从0到N-1编号。接下来有N-1行输入,每行包含一条双向道路的两端小村的编号,中间用空格分开。之后一行包含一正整数M(1≤M≤500000),代表着该组测试问题的个数。接下来M行,每行给出A,B,C三个小村的编号,中间用空格分开。
当N为0时,表示全部测试结束,不要对该数据做任何处理。
输出要求:对每一组测试给定的A,B,C,在一行里输出答案,即:如果C在A和B之间的路径上,输出Yes,否则输出No。
题目三十六、利用Hash技术统计C源程序中关键字的频度
一、任务描述
扫描一个C源程序,用Hash表存储该程序中出现的关键字,并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为:Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41。关键字39个,参考C语言教材。
二、数据结构设计
①关键字表的存储结构;②Hash表中的结点结构。频度、冲突次数
三、功能设计
①从一个大字符串中分解单词
②识别是否是关键词;用哪种方法:有序表查找、二叉查找树?
③Hash函数,解决冲突,统计冲突次数。key => 地址
④插入Hash表,或调整Hash表项中的频度
⑤输出Hash表,关键词总数,冲突次数
实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法; 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找; 2.建立二叉排序树并对该树进行查找; 3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 实验七查找 一、实验目的 1. 掌握查找的不同方法,并能用高级语言实现查找算法; 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数,然后构造二叉排序树,进行查找。 三、实验步骤 1. 从空的二叉树开始,每输入一个结点数据,就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序(课后自己做)。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t; while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出 现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的 重庆文理学院软件工程学院实验报告册 专业:_____软件工程__ _ 班级:_____软件工程2班__ _ 学号:_____201258014054 ___ 姓名:_____周贵宇___________ 课程名称:___ 数据结构 _ 指导教师:_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素(数据类型为整型)。 2.编程实现把顺序表中从i个元素开始的k个元素删除(数据类型为整型)。 3.编程序实现将单链表的数据逆置,即将原表的数据(a1,a2….an)变成 (an,…..a2,a1)。(单链表的数据域数据类型为一结构体,包括学生的部分信息:学号,姓名,年龄) 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置(下标值),空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.51 指导教师孙世良 实验项目编号实验7 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午~月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性; 熟悉二叉树的各种存储结构的特点及适用范围; 掌握遍历二叉树的各种操作及其实现方式。 (二)实验内容和要求 编写一个算法,输出以二叉树表示的算术表达式,若该表达式中含有括号,则应该在输出时添上。 (三)主要仪器设备 实验环境:Microsoft Visual Studio 2012 (四)源程序 #include if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } void middle_order(bitree &Node){ if(Node != NULL){ if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf("( "); middle_order(Node->lchild); if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf(") "); printf("%c ", Node->data); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf("( "); middle_order(Node->rchild); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf(") "); } } int main() { bitree y; printf("以先序遍历的方式输入二叉树:"); create(y); printf("输出表达式:"); middle_order(y); return 0; } (五)数据调试 实验指导-数据结构B 附录综合实验 1、实验目的 本课程的目标之一是使得学生学会如何从问题出发,分析数据,构造求解问题的数据结构和算法,培养学生进行较复杂程序设计的能力。本课程实践性较强,为实现课程目标,要求学生完成一定数量的上机实验。从而一方面使得学生加深对课内所学的各种数据的逻辑结构、存储表示和运算的方法等基本内容的理解,学习如何运用所学的数据结构和算法知识解决应用问题的方法;另一方面,在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。 2、实验基本要求: 1)学习使用自顶向下的分析方法,分析问题空间中存在哪些模块,明确这些模块之间的关系。 2)使用结构化的系统设计方法,将系统中存在的各个模块合理组织成层次结构,并明确定义各个结构体。确定模块的主要数据结构和接口。 3)熟练使用C语言环境来实现或重用模块,从而实现系统的层次结构。模块的实现包括结构体的定义和函数的实现。 4)学会利用数据结构所学知识设计结构清晰的算法和程序,并会分析所设计的算法的时间和空间复杂度。 5)所有的算法和实现均使用C语言进行描述,实验结束写出实验报告。 3、实验项目与内容: 1、线性表的基本运算及多项式的算术运算 内容:实现顺序表和单链表的基本运算,多项式的加法和乘法算术运算。 要求:能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。 2、二叉树的基本操作及哈夫曼编码译码系统的实现 内容:创建一棵二叉树,实现先序、中序和后序遍历一棵二叉树,计算二叉树结点个数等操作。哈夫曼编码/译码系统。 要求:能成功演示二叉树的有关运算,实现哈夫曼编码/译码的功能,运算完毕后能成功释放二叉树所有结点占用的系统内存。 3、图的基本运算及智能交通中的最佳路径选择问题 内容:在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法,实现图的深度和宽度优先遍历算法,解决智能交通中的路径选择问题。设有n 个地点,编号为0~n-1,m条路径的起点、终点和代价由用户输入提供,寻找最佳路径方案(例如花费时间最少、路径长度最短、交通费用最小等,任选其一即可)。 要求:设计主函数,测试上述运算。 4、各种内排序算法的实现及性能比较 内容:验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求:使用随机数产生器产生较大规模数据集合,运行上述各种排序算法,使用系统时钟测量各算法所需的实际时间,并进行比较。 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验报告 实验六图的应用及其实现 一、实验目的 1.进一步功固图常用的存储结构。 2.熟练掌握在图的邻接表实现图的基本操作。 3.理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目:(本类题目属于验证性的,要求学生独立完成) [题目一]:从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据:教材图7.29 【题目五】连通OR 不连通 描述:给定一个无向图,一共n个点,请编写一个程序实现两种操作: D x y 从原图中删除连接x,y节点的边。 Q x y 询问x,y节点是否连通 输入 第一行两个数n,m(5<=n<=40000,1<=m<=100000) 接下来m行,每行一对整数 x y (x,y<=n),表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q(q<=100000) 以下q行每行一种操作,保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答,连通的回答C,不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 实验八内部排序 一、实验目的 1、掌握内部排序的基本算法; 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序: #include 《数据结构》实验指导 (计算机信息大类适用) 实验报告至少包含以下内容: 实验名称 实验目的与要求: 实验内容与步骤(需要你进行细化): 实验结果(若顺利完成,可简单说明;若实验过程中遇到问题,也请在此说明) 收获与体会(根据个人的实际情况进行说明,不得空缺) 实验1 大整数加法(8课时) 目的与要求: 1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。 2、单链表的简单应用训练。 3、熟悉标准模版库STL中的链表相关的知识。 内容与步骤: 1、编程实现单链表的基本操作。 2、利用单链表存储大整数(大整数的位数不限)。 3、利用单链表实现两个大整数的相加运算。 4、进行测试,完成HLOJ(https://www.wendangku.net/doc/3f16221096.html,) 9515 02-线性表大整数A+B。 5、用STL之list完成上面的任务。 6、尝试完成HLOJ 9516 02-线性表大菲波数。 实验2 栈序列匹配(8课时) 目的与要求 1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。 2、栈的简单应用训练。 3、熟悉标准模版库STL中的栈相关的知识。 内容与步骤: 1、编程实现顺序栈及其基本操作。 2、对于给出的入栈序列和出栈序列,判断2个序列是否相容。即:能否利用栈 将入栈序列转换为出栈序列。 3、进行测试,完成HLOJ 9525 03-栈与队列栈序列匹配。 4、用STL之stack完成上面的任务。 5、尝试完成HLOJ 9522 03-栈与队列胡同。 实验3 二叉排序树(8课时) 目的与要求 1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。 2、二叉树的遍历方法的训练。 3、二叉树的简单应用。 内容与步骤: 1、编程实现采用链式存储结构的二叉排序树。 2、实现插入节点的操作。 3、实现查找节点的操作(若查找失败,则将新节点插入二叉排序树)。 4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出,完成 HLOJ 9576 07-查找二叉排序树。 5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。 实验4 最小生成树(8课时) 目的与要求 1、图的邻接矩阵存储结构及其相关运算的训练。 2、掌握最小生成树的概念。 3、利用Prim算法求解最小生成树。 实验背景: 给定一个地区的n个城市间的距离网,用Prim算法建立最小生成树,并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。 内容与步骤: 1、建立采用邻接矩阵的图。 2、编程实现Prim算法,求解最小生成树的代价。 3、尝试利用Prim算法完成:HLOJ 9561 06-图最小生成树。 姓名: 学号: 班级: 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include 云南大学软件学院数据结构实验报告 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □ 学期:2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间: 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号:姓名:本人承担角色: 综合得分:(满分100分) 指导教师:年月日(注:此表在难度为C时使用,每个成员一份。) (下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%) 1 哈希表查找。根据全年级学生的姓名,构造一个哈希表,选择适当的哈希函数和解决冲突的方法,设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中: typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理,先将用户名进行折叠处理折叠处理后的数,用除留余数法构造哈希函数,并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) (本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系) 1抽象数据类型的功能规格说明和结构体: #include 《数据结构》实验指导书 贵州大学 电子信息学院 通信工程 目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109) 实验一顺序表的操作 实验学时:2学时 实验类型:验证 实验要求:必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作(建立、插入、删除等)的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型,输入一组整型数据,建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数,调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程,上机调试、得出正确的运行程序。 2、编译运行程序,观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试,并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等,并将其写入实验报告中。 【附录----源程序】 #include 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.wendangku.net/doc/3f16221096.html,。提交时限:本次实验后24小时之内。 阅读程序,完成填空,并上机运行调试。 1、顺序栈,对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后,base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作(存储结构由SqStackDef.h 定义) Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数,即栈的长度, 编写此函数 洛阳理工学院实验报告 附:源程序: #include { InsertBST(&((*bst)->lchild),key); return OK; } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); return OK; } } void CreateBST(BSTree *bst) { int key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) { InsertBST(bst, key); scanf("%d", &key); } } BSTree SearchBST(BSTree bst, int key) { if(!bst) return NULL; else if(bst->key==key) return bst; //查找成功 else if(bst->key>key) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); 实验七图的创建与遍历 实验目的: 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求: 要求: ⑴能根据输入的顶点、边/弧的信息建立图; ⑵实现图中顶点、边/弧的插入、删除; ⑶实现对该图的深度优先遍历; ⑷实现对该图的广度优先遍历。 备注:单号基于邻接矩阵,双号基于邻接表存储结构实现上述操作。算法设计: #include . } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i 《数据结构实验》实验指导书及答案 信电工程学院计算机科学和技术教研室编 2011.12 数据结构实验所有代码整理 作者郑涛 声明:在这里我整理了数据结构实验的所有代码,希望能对大家的数据结构实验的考试有所帮助,大家可以有选择地浏览,特别针对一些重点知识需要加强记忆(ps:重点知识最好让孙天凯给出),希望大家能够在数据结构实验的考试中取得令人满意的成绩,如果有做的 不好的地方请大家谅解并欢迎予以指正。 实验一熟悉编程环境 实验预备知识: 1.熟悉本课程的语言编译环境(TC或VC),能够用C语言编写完整的程序,并能够发现和改正错误。 2.能够灵活的编写C程序,并能够熟练输入C程序。 一、实验目的 1.熟悉C语言编译环境,掌握C程序的编写、编译、运行和调试过程。 2.能够熟练的将C程序存储到指定位置。 二、实验环境 ⒈硬件:每个学生需配备计算机一台。 ⒉软件:Windows操作系统+Turbo C; 三、实验要求 1.将实验中每个功能用一个函数实现。 2.每个输入前要有输入提示(如:请输入2个整数当中用空格分割:),每个输出数据都要求有内容说明(如:280和100的和是:380。)。 3.函数名称和变量名称等用英文或英文简写(每个单词第一个字母大写)形式说明。 四、实验内容 1.在自己的U盘中建立“姓名+学号”文件夹,并在该文件夹中创建“实验1”文件夹(以后每次实验分别创建对应的文件夹),本次实验的所有程序和数据都要求存储到本文件夹中(以后实验都按照本次要求)。 2.编写一个输入某个学生10门课程成绩的函数(10门课程成绩放到结构体数组中,结构体包括:课程编号,课程名称,课程成绩)。 3.编写一个求10门成绩中最高成绩的函数,输出最高成绩和对应的课程名称,如果有多个最高成绩,则每个最高成绩均输出。 4.编写一个求10门成绩平均成绩的函数。 5.编写函数求出比平均成绩高的所有课程及成绩。 #include数据结构实验七 查找
数据结构课程实验指导书
数据结构实验答案1
数据结构实验7实验报告
实验指导-数据结构B教案资料
数据结构实验报告
数据结构_实验六_报告
数据结构实验八内部排序
《数据结构》实验指导
数据结构实验报告
数据结构实验报告七查找、
2017数据结构实验指导书
数据结构实验
数据结构实验六
数据结构实验七图的创建与遍历
数据结构实验指导书及答案(徐州工程学院)