数据结构（C语言版）设计性上机实训.docx

《数据结构（C语言版）设计性上机实训.docx》由会员分享，可在线阅读，更多相关《数据结构（C语言版）设计性上机实训.docx（11页珍藏版）》请在课桌文档上搜索。

1、附录设计性上机实训内容概要：课程设计是高职高专、应用型本科院校非常重要的教学环节，是学完一门课程后应用该深程知识及以前的加识积累进行然合性、开放性的调练。通过课程设计，使学生得到系统的技能训练，巩固和加强所学的专业理论知识，培养学生工程恚识、创新能力、团队精神等蛉合素质，提高学生的谩计和解决实际问麴的能力。课程设计指导课程设计的目的1 .训练学生灵活运用数据结构知识解决实际问题的能力.2 .加强学生的动手能力，提高学生的算法设计的能力.3 .巩固和深化学生的理论知识,提高编程水平,并在此过程中培养学生严谨的科学态度和良好的工作作风.课程设计的要求学会从问超入手,分析研咒数楙结构中数据表示和数据

2、处理的特性.以使为所涉及的数据选择和设计适当的逻辑结构、存储结构及其相应的操作IZ法，并初步掌握时间和空间复杂度分析技术,要求学生书写符合软件工程珑莅的文档，编写的程序代码应结构清嘶、正确易读，能上机脚试并排除错误。=.课程设计的步骤1 .上机前要求认真分析题目要求，完成H面的总体设计和详细设计.2 .完成程序设计并调试正确后,应请指导教师检查并得到认可.全部完成后应写出完整的课程设计报告，并装订成册，连同源代码交给指导教师.四.考核形式1 .在机上运行程序,演示程序的正确执行情况和每个任务的完成情况.2 .课程设计答时.五.考核成绩考核成绩为优、良、中、及格和不及格.考核方法以平时我现、实验

3、报告和实验质*为考核依据，1 .独立完成设计任务占20%。2 .设计方案明确、数据结构设计合理算法及其实践性能合理、程序调试成功占40%.3 .创新与发挥占10%.4 .答解占30%,课程设计参考题目学生成誉M设计目的：1 .掌握线性琏表的建立.2 .掌握线性进发的基本操作.3,掌握”找的恭本算法。设计内容：利用线性鞋表实现学生成绩管理系统,具体功能：给入、输出、捅入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，井熊在屏幕上输出授作前后的结果。设计要求：1 .写出系统篙求分析.并建模，2 .编程实现.界面友好。3 .谕出操作前后的结果.售程设计一：停邨IEK跳设计目的

4、：1 .掌握极和队列的建立.2 .掌握栈和队列的基本操作。3 .深入了解栈和队列的特性.以便在解决实际向即中灵活运用它们。4 .加深对栈和认列的理解和认识.设计内容：设有一个可以停放n辆汽车的狭长停车场.它只有一个大门可以供车辆进舟.车辆按到也停车场时间的晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的奴胆面）。如果停车场己放满n辆车,则后来的车辆只能在停车场大门外的便道上等待.一旦停车场内有车开走.则桂在便道上的第一辆车就进入停车场。停车场内如有某辆乍要开走,在他之后进入停车场的车都必须先退出杵车场为它让路.待其开出停车场后,这些车辆在依原来的次序进场.每辆车在离开停车场时

5、,都应依据它在停车场内停留的时间长短交拢,如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费.并旦仍然保持在便道上等待的车辆的次序.编制一程序模拟该停午场的管理。设计要求：1 .以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理.2 .每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻.3,对出一组输入数据进行操作后的输出信息为：若是车辆到达,则输出汽车在停车场或便道上的停车位置：若是乍辆离去.则输出汽车在停车场内停倒的时间和应交纳的费用（在便道上停留的时间不收费,功能可自己添加）.*8ttHB:依夫(Josep

6、h)I?设计目的：1 .掌握的向循环链去的建立。2 .常板单向循环链表的操作。设计内容：编号是12.n的n个人按照顺时针方向阳坐假.每个人只有一个密码(正整数)。-开始任选一个正整数作为报数上未值m.从第一个仍开始项时针方向自I开始Mj序报数.报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在惭时针方向的下一个人开始新从1报数,如此下去.直到所有人全部出列为止。请设计一个程序求出出列顺序。设计要求：1 .利用单向循环链去存储结构模拟此过程,按照出列的顺序输出各个人的编号.2 .测武数据：m的初值为20ji=7,7个人的密码依次为3J724.74首先m=6.则正确的输出是什么？3 .

7、静入数据：建立谕入函数处理怆入的数据.情入m的初值n.谕入每个人的定码.建立单向循环鞋衣.4,输出形式；建立一个输出函数,将正确的出列顺序输出。.程设前四，文学研究Jtt手的实现设计目的：1 .熟悉率类型的实现方法和文本匹配方法.2 .4悉一般文字处理软件的设计方法.设计内容：文学研究人员需要统计某篇英文小说中某些形容词的址现次数和位置.试写一个实现这一目标的文字统计系统,称为“文学研究助手”.设计要求：1 .英文小说存于一个文本文件中.2 .待统计的词汇集合要一次输入完毕.3 .程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。程阳t*五IVM多项式计算设计目的：1 .掌

8、握林疏矩阵的相关运尊.2 .掌握广义表的操作.设计内容：设计一个一元稀疏多项式简单计算器.设计要求：一元稀玻多项式简单计算器的基本功能是：1 .输入并建立多项式：2 .输出多项式,输出形式为整数序列:n.cUIc2.e2CnlenI其中n是一项式的项数.ci和ei分别是第i项的系数和指数,序列按指数降序排列。3 .多项式a和b相加.建立多项式a+b4 .多项式a和b相减,建立多多式N售发设计六：哈夫受及其应用设计目的：1 .熟悉树的各种存储结构及其特点。2 .掌握建立哈夫曼树和哈夫曼端码的方法及帝权路径长度的计算.设计内容：欲发一封内容为AABBCAB（共长100字符.其中:A、B、C、D、E

9、、F分别有7、9、12、丝、23、27个）的电报报文.实现哈夫里编码.设计要求：1 .分析系统需求，2 .建立哈夫亚树.3 .进行哈夫她编码,并求出平均编码长度.4 .编程实现2、3步骤。森&设计.七,哈夫设计目的：1 .掌握建立哈夫树和哈夫变娘码的方法.2 .掌握哈夫曼编码的实际应用方法.设计内容：利用哈夫亚编码进行通信可以大大提高信道利用率.缗短信息传输时间.降低传输成本.但是.这要求在发送端通过个编码系统对待传数据预先编码,在接收她将传来的数据进行详码.时于双工信道（即可以双向传输信息的信道）.好端都需要个完成的编译码系统.试为这样的信息收发站另一个哈夫曼的端谛码系统。设计要求：1 .初

10、始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树“2 .编码。利用己建好的哈夫曼树,对正文进行涮码。3 .详眄.对编码好的内容进行译码.4 .打印编码.5 .打印哈夫曼树.计A，图的历演示设计目的：1 .理解图的荔本概念.熟悉图的各种存储结构及其何造律法.2 .掌握图的遍历方法.设计内容：实现图的深度优先、广度优先遍步舞法*并输出原图结构及说方结果.设计要求：1 .两种遍历方法必须都要实现.写出画图的思路.2 .界面友好.函数功能要划分合理.3 .总体设计应图一流程图.4 .程序要加必要的注择。5 .提供程序测演方案。程设出九：交咨询系统设计设计目的：1 .熟练掌旌迪杰斯特拉

11、算法和费洛伊德究法,能够利用它们解决锻短路径同题.2 .能帔解决工程项目实俺过程中的关神路径向阳，设计内容：设计一个交通咨沏系统能让旅客咨询从任一个城市定点到另一个城市定点之间的鼓短路径或最低花费或以少时间等问题，对于不同的咨询娈求、可输入城市间的跖程或所需时间或所需花费。设计要求：1 .建立交通网络网的存储结构。2 .总体设计要倒流程图.3 .提供程序测试方案.4 .界面友好。覆设计十，Imfll息的好与检It设计目的：1 .深刻理解排序的定义和各种排序方法的特点.并能灵活的应用：2 .掌握描述我找过程的判定树的构造方法.设计内容：设计民航竹票处的计算机系统可以为客户提供下列各项服务：1 .

12、查闻航线：根据旅客提出的终点站名输出下列信息:航班号、飞机号、星期几飞行、最近一天航班的H期和余票额：2 .承办订票业务：根据客户提出的要求（航班号、/票数额1）查询该航班票制情况.设计要求：1 .对飞机航班伯息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息诳行宜询。2 .采用班数排序法时一组具有结构特点的飞机航班号进行排序.3 .利用二分查找法对排好序的航班记录按航班号实现快速排序.4 .每个航班记录包括八项,分别为：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等。课程设计（实训）报告参考格式实一线性我的应用系别：班fS：时间：学H：姓名：

13、分数：一、实蕤目的1 .掌握线性表的慨会.2 .掌握.戏性表的各种基本操作。3 .理耨线性表的顺序、徒我存储.二、实脸内容I,从键盘输入10个整数，设计算法，实现雄性结构上的顺序表的产生以及元素的宜找、插入与删除。4 .从城盘釉入5个整数.设计算法,实现线性结构上的单性表的产生以及元索的查找、插入与捌除.三实骐要求I.在程序的运行过程中给出以下提示信息以供选择数字,从而进行相应的操作“O-EXIT友示退出程序1JNSERT表示插入节点，需从键世上输入插入的位汉和元素的值（都是整数。2-DE1.ETE衣东要删除元素的位置，执行后返回元素的假.3-1.oCATE要求输入要查找元案的值,执行后返网该

14、元案在表中的位置.2 .C完成以法设计和程序设计并上机调试通过。3 .撰写实验报告,提供实验结果和数据.4 .分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度.并简要给出算法设计小站和心得。四、算法设计1 .单性表的存储结构cypcdcf5iru1.Nodc(inidatxstruct1.Ncdc*ncxt;J1.NiKteZUnl1.islk2 .范本操作：IniI1.ink1.iSH&1.)操作结果：构造一个空的单性表1.Ins1.ink1.isU&1.pos.c)初始条件：的链表1.己存在操作结果：将元泰e插入到单链表1.的pos位置Del1.ink1.isU&1.,po

15、s.&e)初始条件：总魅表1.已存在操作结果：将总链表1.中POS位司的元素删除，元素值置入e中返回1.oc1.ink1.isi(Ue)初始条件：单桂表1.依存在一作结果:1.中查找是否元Ite,若存在.返回元一在表中的位置;若不存在，返回MenuO操作结果：在解能上显示操作菜单3 .需要设计的函数主函数main。初始化单跳表函数IniI1.ink1.isl()显示操作菜单的数menu。显示单排我内容函数disp1.inkl.M)插入元素函数InS1.ink1.iW。删除元成函数Del1.ink1.istO看找元素,函数1.oC1.lnk1.iSt()各个函数之间的关系：nanInit1.in

16、k1.istIenuDisp1.ink1.lstIns1.ink1.istDel1.ink1.lst1.oc1.ink1.ist五、程序实现写出年个操作的算法(操作过程)boolInit1.ink1.M1.ink1.iQ1.(伪码算法lUnk1.iM)malloc(sizco(1.Nncxt=NU1.1.;voidDi5p1.ink1.isKUnid1.Bt1.)(的代科算法JVoidmenuO(伪代码。法)boollnjnkl.ist(IJnkl.iit&l.inlps,inte)(”一代码算法JbootDcIUnk1.isKUnk1.ist&1.intpm.int&c)(伪代码律法)i11

17、tIjK1.inkIisH1.inkIiMl.,intc)(一代码算法六、运行结果1,建立单就表：选择I.分别怆入0.II),(0.12).013),显示输入错误选择I输入(7,选择1输入(6.2),显示输入错误2),得到单锥表(15.1,14.13,12,11.2)3 .删除:选择2,选择2,选择2,输入1.输入0。输入4。选择2,输入5.返回BlO0,泡到单鞋表(15.14.1312.II.2)返回e=IS,得到单链去(14,13.12.I1.2返回e=2,得到单链表(14.13.12.11)返回输入惜管4 .查找选择3.输入14,返回pos=0选择3,输入100。返回输入错误七存在的问逊画八、源程序清单(略