2015数据结构实践题目计科13级

一、课题内容：任意选作一j1、【山西农业大学校园导游程序】问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径：查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。选作内容：①求多个景点的最佳(最短)游览路径。②区分机动车道和人行道。③实现导游图的仿真界面。数据结构：typedefstnictmessage(intnum;//景点代码charname[l00]为景点名称charpro[500];//简介}Ciceroni;例如：Ciceromschool[10]={{l,”行政楼\n”},{2,”食堂\ii"},(3,"赛博楼，信息分院办公室所在地心”},{4,”求是楼，实验楼计算机中心\n”},{5,”格致楼，法学管理学院”},{6,”工程实习中心，金工实习\n”},{7,”仰仪楼,机电计测分院"},{&”体育馆滂边有篮球场'足球场'还有网球场"},{9,”一号教学楼，主要以阶梯教室为主{10,”二号教学楼，小教室为多\n”}}；/*景点名称和简介*/要求以本校的景点为例进行编号与介绍。操作：/*给景点之间的路径赋最大值*//*最短路径的C语言函数*//*输出最短路径和最短距离函数*//*输入景点代码查景点名称和简介*//*输入景点代码查到其它景点的最短距离*/2、【员工管理系统】问题描述：每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。基本要求：排序：按不同关键字，对所有员工的信息进行排序；查询：按特定条件查找员工；更新，按编号对某个员工的某项信息进行修改；插入，加入新员工的信息；删除，按编号删除己离职的员工的信息。选作内容：实现图形用户界面。通过链表实现数据结构：stnictworkers{chai-name[15姓名chardepartment]18];//单位chargender;//性别unsignedmtage;〃年龄unsignedlongtelephone;〃电话unsignedlongwage;//工资unsignedlongnum;//职工号stiuctworkers*next;};操作实现：/*插入职工信息，通过链表实现*//*具体实现职工信息的插入*//*对职工信息的删除操作*〃*修改操作*//*实现对员工信息的查找*//*排序勺/*输出员工信息*//*显示职工工资情况计算平均工资*/3、【本班学生成绩管理】实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。能实现对学生信息的简单管理。具体要求：建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩(FOX,C,ENGLISH)°程序运行时显示一个简单的菜单，例如：：信息输入(INPUT)：总分统计(COUNT)：总分排序(SORT)：查询(QUERY)其中：：对4个学生的信息进行输入；：对每个学生的3门课程统计总分；：对4个学生的总分按降序排序并显示出来：：查询输入一个学号后，显示出该学生的有关信息：数据结构：structstudent(mtnum;//学号charname[20];〃姓名mtfbxscorey/fbx成绩mtcscore;//C语言mtenglishscore;//英语成绩stnictstudent*next;};操作：成绩信息输入；统计总分;排序；查询4、【订票系统】任务：通过此系统可以实现如下功能：录入：可以录入航班情况(数据可以存储在一个数据文件中，数据结构、具体数据自定)查询：可以查询某个航线的情况(如，输入航班号，查询起降时间，起飞抵达城市,航班票价，票价折扣，确定航班是否满仓)可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班己经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息:当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；航班信息数据结构typedefchaikeytype;//航班信息结构typedefstnict（clwstart[6]y/;起点站chai-end[6];//终点站chai-sche[10];〃航班期chaitune1[5];//起飞时间chaitune2[5];//到达时间clwmodel[4];//机型mtprice;//^价}nifbtype;〃定义航班节点typedefstnict（keytypekeys[keylen];//航班号uifotypeothers;〃航班信息mtnext;〃下一航班}slnode;〃航班表typedefstnict（slnodesl[maxspace];intkeynum;mtlength;}sllist;操作实现：（1）录入航班信息：（2）查询航班信息：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵这城市，航班票价，票价折扣，确定航班是否满仓）；可■以输入起飞抵达城市，查询飞机航班情况：航班信息查询系统：可以按：1.航班号；2.起点站；3.终点站；4.起飞时间：5.到达时间；以下选作：（3）航班订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班巳经无票，可以提供相关可选择航班；（4）航班退票：可■退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。（5）修改航班信息：当航班信息改变可以修改航班数据文件。注：因为航班号为两位字母后跟数字，所以在排序时应该使用多关键字的基数排序对航班号进行排序。5、【商店存货管理系统】功能：建立一商店存货管理系统，要求每次出货时取进货时间最早旦最接近保质期中止时间的货物。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数：完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加）,修改和删除以及简单的排序；进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。6、【中国道路交通网络信息查询系统（****）】【问题描述】出于不同的目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可■能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到这或最省钱到达。全程只考虑一种交通工具：（4）旅途中耗费的总时间应该包括中转站的等候时间；（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】参考《数据结构》清华版7.6节图7.33的全国交通图，自行设计列车时刻表和飞机航班。【实现提示】（1）对时刻表和飞机航班进行编辑，应提供文件输入和键盘输入两种形式。飞机航班信息包括:起始站的出发时间，终点站的到达时间和票价;列车时刻表则需根据交通图给出各个路段的详细信息，如:对从北京到上海的火车,给出北京至天津，天津至徐州及徐州至上海各段的出发时间，到达时间及票价等信息。（2）以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还包括交通工具,路途中耗费的时间和花费以及出发和到达时间等多种属性。【选做内容】增加旅途中中转次数最少的最优决策二、作业提交上交相关内容要求:以班为单位刻盘,并在盘面标明班级名称，如：计科1301♦每个同学上交成果的内容必须由以下两大部分组成，缺一不可（一）电子版：每个同学建立一个文件夹。◊文件夹名禾尔为：学号（两位）-姓名-课题名称：◊文件夹I法a容：包含下面3个内容。1、上交源程序：学生按照课程实践的具体要求所开发的所有源程序（应该放到一个文件夹中，文件夹名称：姓名-课题名称，如：张三-学生成绩管理）；2、上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录,上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3、课程实践报告：（保存在word文档中，文件名要求按照”姓名-**课程实践报告”）报告按所给样例完成，样例见文件后边。（二）纸质版：课程设计报告A4打印一份，封面由学委统一监督打印，全班保持封面格式一致。提交日期：2015年9月16日下午4点，学委交到教师备课室教师办公桌。每推迟提交报告一天，扣5分。三、考核评分上机情况30%+实践报告70%1、上机情况（30%）包括出勤情况、调试表现、是否上网、玩游戏。一次扣10分。2、实践报告（70%）见详细评分标准。附件一:《数据结构》

综合实践报告评分标准TOC\o"1-5"\h\z1、内容完整10分2、概要设计合理、明了20分3、详细设计思路清晰、内容完善40分4、调试分析过程认真、合理10分5、测试结果正确合理10分6、实践总结深刻10分共计100分以上内容可以在评分标准内按所做系统实际情况酌情给分。附件二:《数据结构》

综合实践报告学院：班级：学号：姓名：课题名称：指导教师：完成日期：1.实践题目编制一个演示单链表插入、删除、查找等操作的程序需求分析本演示程序用vc编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。程序所能达到的功能：完成单链表的生成(通过插入操作)、插入、删除、查找操作测试数据：插入操作中依次输入11,12,13,14,15,16,生成一个单链表查找操作中依次输入12,15,22返回这3个元素在单链表中的位置删除操作中依次输入2,5,删除位于2和5的元素概要设计为了实现上述程序功能，需要定义单链表的抽象数据类型：ADTLinkList{数据对象：D={ai|aieintegerSetzi=0,l/2,...znzn>0}数据关系：R={<ai,ai+l>|ai,ai+leD}基本操作：InitLinkList(&L)操作结果：构造一个空的单链表L.InsLinkList(&Lzpos,e)初始条件：单链表L己存在操作结果：将元素e插入到单链表L的pos位置DelLinkList(&L,pos,&e)初始条件：单链表L己存在操作结果：将单链表L中pos位置的元素删除，元素值置入e中返回LocLinkList(Lze)初始条件：单链表L依存在操作结果：单链表L中查找是否元素e,若存在，返回元素在表中的位置；若不存在，返回-1.Menu()操作结果：在屏幕上显示操作菜单

本程序包含7个函数：主函数main()初始化单链表函数InitLinkListO显示操作菜单函数menu()显示单链表内容函数dispLinkList()插入元素函数InsLinkList()删除元素函数DelLinkList()查找元素函数LocLinkList()各函数间关系如下：mainInitLinkListMenumainInitLinkListMenuDispLinkListInsLinkListDelLinkListLocLinkList4.详细设计对主程序和其他模实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。块也都需要写出伪码算法。对主程序和其他模结点类型和指针类型typedefstructnode〈intdata;structnode*next;}Node,*LinkListl;单链表的基本操作为了方便，在单链表中设头结点，其data域没有意义。boolInitLinkList(LinkList&L)(伪码算法)voidDispLinkList(LinkListL)(伪码算法)voidmenu()(伪码算法)boolInsLinkList(LinkList&L,intposjnte)(伪码算法)boolDelLinkList(LinkList&L,intposjnt&e)(伪码算法)intLocLinkList(LinkListLzinte)(伪码算法)其他模块伪码算法调试分析调试过程中所做的工作，时间复杂度等分析。使用说明程序名为LinkList.exe,运行环境为DOS。程序执行后显示0—-EXIT-INSERT—DELETE-LOCATESELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可•以进行其他的操作。每执行一次功能，就会显示执行的结果(正确或错误