计算机学院13级数据结构课程设3周..docVIP

《数据结构》课程设计任务书 学期：-1 班级： 一、设计目的 《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 设计要求 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。学生必须仔细读《数据结构》课程设计，认真完成课设的有问题及时主动与教师沟通。课程设计按照教学要求需要周时间完成学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。设计选题typedef struct { /*员工通讯信息的结构类型定义*/ char num[5]; /*员工编号*/ char name[10]; /*员工姓名*/ char phone[15]; /*办公室电话号码*/ char call[15]; /*手机号码*/ char mail[25]; /*邮箱*/ }DataType; /*通讯录单链表的结点类型*/ typedef struct node { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode,*LinkList; 2、停车场管理（栈和队列的应用） [问题描述] 设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 [实现提示] 以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。 3、哈夫曼编码/译码系统（树应用） [问题描述] 利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的必威体育官网网址性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。 [实现提示] 在本例中设置发送者和接受者两个功能， 发送者的功能包括： ①输入待传送的字符信息； ②统计字符信息中出现的字符种类数和各字符出现的次数（频率）； ②根据字符的种类数和各自出现的次数建立哈夫曼树； ③利用以上哈夫曼树求出各字符的哈夫曼编码； ④将字符信息转换成对应的编码信息进行传送。 接受者的功能包括： ①接收发送者传送来的编码信息； ②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。 从以上分析可发现，在本例中的主要算法有三个： （1）哈夫曼树的建立； （2）哈夫曼编码的生成； （3）对编码信息的翻译。 4、校园导游咨询（图的应用） [问题描述] 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 （1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息； （2）提供基本信息的修改功能； （3）为来访客人提供图中任意景点相关信息的查询； （4）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。 5、药店的药品销售统计系统（排序应用） [问题描述] 设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。 [实现提示] 在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前