信息工程实习数据结构部分.doc

信息工程实习数据结构部分一、熟悉project组织应用程序一. 实验目的和要求1、 熟悉vc6.0开发环境；使用workspace和project组织应用程序；2、 回顾c语言程序设计，编写完整的实验应用程序， 并调试通过。3、 掌握文件包含，以及库函数iostream.h中的标准输入、输出流对象cin和cout，理解“引用（&）”方式的参数传递。二. 实验内容1、 按下述介绍的方法，练习并掌握使用project组织应用程序的方法。步骤： 启动vc+，选择“文件（file）”菜单中的“新建（new）”项，选择“工程（projects）页，然后选择“win32 console application”，在右上角输入project的名称（如：test1），再选择合适的存储路径，然后按下“确定”按钮。这样就建立了一个新的工程。如下图所示： 在窗口左侧出现workspace视图，选择“fileview”页可浏览该工程所包含的文件。然后可在项目中新建源文件（菜单：文件新建），包括“c/c+header file”和“c/c+source file”两类文件，或将已有的源文件加入到这个工程中（菜单：工程增加到工程）。如下图：完成后程序组织结构如下图：其中source fileste中包含主程序等源程序文件（如：test1_main.cpp），header fileste中包含头文件等（如：test1_function.h）。2、在vc中建立工程（取名为test1），并编写如下程序加入到工程中，编译执行该程序。要求使用cin和cout进行数据的输入输出。程序题目如下：设a为长度为n的整数型一维数组。（1）试编写求a中的最大值、最小值和平均值的函数。 请分别用两种方法完成：l 分别编写三个函数int amax(int *a,int n) 、 int amin(int *a,int n) 、 int aave(int *a,int n) 实现求最大值、最小值和平均值。l 用一个函数void amax_min_ave(int *a, int n, int &max, int &min, int &aver) 实现求上述三个值，用“引用参数”带回结果。（2）试编写函数 int prime_sum(int *a, int n) 计算a中所有素数之和。（3）编写函数 void asort(int *a,int n) 对a进行从小到大的排序，并输出排序结果。要求：把以上函数存放在头文件test1.h中，并自行设计主函数来测试各类操作实现的正确性，主函数存放在文件test1.cpp中。3、填写实验报告，实验报告文件取名为report1.doc。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】二、约瑟夫环的实现一、实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用线性表的各种操作来进行具体的实际应用。3、加强程序设计的能力。二实验内容1、编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，n (n0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0i=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求:（1） 人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。（2） 参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。（3） 根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_seq.h（基本操作函数）、test6_seq.cpp（主函数）中，链式存储结构的程序存放在文件test6_link.h（基本操作函数）、test6_link.cpp（主函数）中。（4） 设计测试数据，并调试程序，直到正确运行。2、填写实验报告，实验报告文件取名为report6.doc。三. 抽象数据类型定义（需说明你设计的每个基本操作的功能）四. 两种类型（顺序和链式）的存储结构定义及算法思路（包括两种存储结构定义及一些重要函数的算法实现思路）五. 实验结果与分析（包括运行结果截图、结果分析等）六. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】三、栈与队列的应用一、实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用栈和队列的各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。二、实验内容1、请编制程序模拟停车场管理。停车场管理问题描述如下：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向大门口处停放 (即最先到达的第一辆车停放在停车场的最里面) 。如果停车场已放满n辆车，则以后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。要求： 以顺序栈模拟停车场，以链队列模拟停车场外的便道，另设一个顺序栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车。 按从终端读入的数据序列进行管理。每一组输入数据包括三个数据项：汽车到达或离开的信息、汽车牌照号码、汽车到达或离开的时刻。如: （a, 1, 5）, (a, 2, 10), (d, 1, 15), , (e, 0, 0)。 其中 a 表示到达，d 表示离去，e表示结束。输出数据为：若有车辆到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。 建立头文件test9_stack.h和test9_queue.h，分别包含顺序栈和链队列的基本操作实现函数，建立主程序文件test9.cpp，在主函数中通过调用栈和队列的基本操作函数来实现上述功能。提示：栈与队列中的每个元素表示一辆汽车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test9.cpp中可定义：typedef struct int num; /汽车牌照号码 int time; /进入停车场的时刻 elemtype; /栈与队列中元素的数据类型主函数的框架可参考如下：void main() elemtype x, y; char flag; cout请输入车辆情况(a: 到达 d: 离开 e: 结束) ，车牌号码，时间；coutflagx.numx.time; while (flag!=e) if (flag=a) . /进栈或进队列，并输出汽车的停车位置else if (flag=d) /出栈，并输出在车场内停留的时间和应交纳的费用 /若队列非空，则队头元素出队列（便道）并入栈（停车场）else /打印出错信息，提示重新输入coutflagx.numx.time; 2、填写实验报告，实验报告文件取名为report9.doc。三. 抽象数据类型定义（分别说明你设计的栈和队列所包含的基本操作及功能）四. 存储结构定义及算法思路（包括栈和队列的存储结构定义、数据元素的类型定义及主函数的算法实现思路）五. 实验结果与分析（包括运行结果截图、结果分析等）六. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】四、二叉树的基本操作一、 实验目的和要求1、掌握二叉树的链式存储结构。2、掌握在二叉链表上的二叉树操作的实现原理与方法。3、进一步掌握递归算法的设计方法。二、 实验内容1、建立头文件test10.h，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件test10.cpp，编译并调试程序，直到正确运行。注意，需要用到栈和队列的有关操作，可使用已编制过的栈和队列的基本操作文件test9_stack.h、test9_queue.h来实现。说明：二叉树的基本操作可包括：(1) void initbtree( btreenode *&bt ) /初始化二叉树bt (2) void createbtree( btreenode *&bt, char *a ) /根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 (3) int emptybtree( btreenode *bt) /检查二叉树bt是否为空，空返回1，否则返回0 (4) int depthbtree( btreenode *bt) /求二叉树bt的深度并返回该值 (5) int findbtree( btreenode *bt, elemtype x) /查找二叉树bt中值为x的结点，若查找成功返回1，否则返回0 (6) void preorder( btreenode *bt) /先序遍历二叉树bt(7) void inorder( btreenode *bt) /中序遍历二叉树bt(8) void postorder( btreenode *bt) /后序遍历二叉树bt(9) void levelorder( btreenode *bt ) /按层次遍历二叉树bt (10) void printbtree( btreenode *bt ) /输出二叉树bt (11) void clearbtree( btreenode *&bt ) /清除二叉树bt2、以下内容为第二次实验完成：(1) 请编写函数实现中序遍历的非递归算法。将此函数输入到前述头文件test10.h中，并在主函数文件test10.cpp中增加测试语句测试这个函数的正确性。注意需要用到栈的有关操作。提示： 二叉树中序遍历的非递归算法就是运用栈这种数据结构将递归的中序遍历转换成非递归的中序遍历，采用的是间接转换方式。中序遍历非递归算法的n-s流程图如下： 注意：栈中存放的应该是指向结点的指针，即结点的地址，而不是结点的值。因为，只有根据结点的地址才能在二叉树中查找到该结点。(2) 完成以下算法的设计，并将这些函数输入到前述头文件test10.h中，在主函数文件test10.cpp中增加测试语句测试其正确性。(a) 将二叉树中的所有结点的左右子树进行交换，函数原型如下：void changebtree(btreenode *bt);(b) 统计二叉树中的所有结点数，函数原型如下：int countbtree(btreenode *bt);(c) 复制一棵二叉树，并返回复制得到的二叉树根结点指针，函数原型如下：btreenode * copybtree(btreenode *bt);3、填写实验报告，实验报告文件取名为report10.doc。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】五、图的基本操作一、实验目的和要求1、掌握图的主要存储结构。2、学会对几种常见的图的存储结构进行基本操作。二、实验内容1、 图的邻接矩阵定义及实现：建立头文件test11_adjm.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test11.cpp（以下图为例），编译并调试程序，直到正确运行。01246532、图的邻接表的定义及实现：建立头文件test11_adjl.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test11.cpp中调用这些函数进行验证（以下图为例）。0011223343、填写实验报告，实验报告文件取名为report11.doc。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】我的大学爱情观目录：1、 大学概念2、 分析爱情健康观3、 爱情观要三思4、 大学需要对爱情要认识和理解5、 总结1、什么是大学爱情：大学是一个相对宽松，时间自由，自己支配的环境，也正因为这样，培植爱情之花最肥沃的土地。大学生恋爱一直是大学校园的热门话题，恋爱和学业也就自然成为了大学生在校期间面对的两个主要问题。恋爱关系处理得好、正确，健康，可以成为学习和事业的催化剂，使人学习努力、成绩上升；恋爱关系处理的不当，不健康，可能分散精力、浪费时间、情绪波动、成绩下降。因此，大学生的恋爱观必须树立在健康之上，并且树立正确的恋爱观是十分有必要的。因此我从下面几方面谈谈自己的对大学爱情观。2、什么是健康的爱情：1) 尊重对方，不显示对爱情的占有欲，不把爱情放第一位，不痴情过分；2) 理解对方，互相关心，互相支持，互相鼓励，并以对方的幸福为自己的满足; 3) 是彼此独立的前提下结合；3、什么是不健康的爱情：1)盲目的约会，忽视了学业;2)过于痴情，一味地要求对方表露爱的情怀，这种爱情常有病态的夸张;3)缺乏体贴怜爱之心，只表现自己强烈的占有欲;4)偏重于外表的追求;4、大学生处理两人的在爱情观需要三思：1. 不影响学习：大学恋爱可以说是一种必要的经历，学习是大学的基本和主要任务，这两者之间有错综复杂的关系，有的学生因为爱情，过分的忽视了学习，把感情放在第一位；学习的时候就认真的去学，不要去想爱情中的事，谈恋爱的时候用心去谈，也可以交流下学习，互相鼓励，共同进步。2. 有足够的精力：大学生活，说忙也会很忙，但说轻松也是相对会轻松的！大学生恋爱必须合理安排自身的精力，忙于学习的同时不能因为感情的事情分心，不能在学习期间，放弃学习而去谈感情，把握合理的精力，分配好学习和感情。3、 有合理的时间；大学时间可以分为学习和生活时间，合理把握好学习时间和生活时间的“度”很重要；学习的时候，不能分配学习时间去安排两人的在一起的事情，应该以学习为第一；生活时间，两人可以相互谈谈恋爱，用心去谈，也可以交流下学习，互相鼓励，共同进步。5、大学生对爱情需要认识与理解，主要涉及到以下几个方面：（1） 明确学生的主要任务“放弃时间的人，时间也会放弃他。”大学时代是吸纳知识、增长才干的时期。作为当代大学生，要认识到现在的任务是学习学习做人、学习知识、学习为人民服务的本领。在校大学生要集中精力，投入到学习和社会实践中，而不是因把过多的精力、时间用于谈情说爱浪费宝贵的青春年华。因此，明确自己的目标，规划自己的学习道路，合理分配好学习和恋爱的地位。（2） 树林正确的恋爱观提倡志同道合、有默契、相互喜欢的爱情：在恋人的选择上最重要的条件应该是志同道合，思想品德、事业理想和生活情趣等大体一致。摆正爱情与学习、事业的关系：大学生应该把学习、事业放在首位，摆正爱情与学习、事业的关系，不能把宝贵的大学时间，锻炼自身的时间都用于谈情说有爱而放松了学习。 相互理解、相互信任，是一份责任和奉献。爱情是奉献而不时索取，是拥有而不是占有。身边的人与事时刻为我们敲响警钟，不再让悲剧重演。生命只有一次，不会重来，大学生一定要树立正确的爱情