《数据结构课程设计》教学大纲2014.doc

《数据结构课程设计一、课程的性质、目的《数据结构》是计算机专业的专业基础课，学生通过理论学习，并在完成每章后面的一些小程序后，理解了数据结构的基本概念，掌握了一些基本的编程技术，但仅有这一方面的训练还是很不够的。《数据结构课程设计》是在学完数据结构课程之后的实践教学环节课程中学到的理论知识，使学生们在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构理论知识的理解，强化学生的逻辑思维能力和动手能力，培养良好的编程习惯，掌握实用软件设计的基本方法，可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、教学的基本要求1、基础知识2、基本技能问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧3、基本要求理解和熟练掌握常用数据结构和算法设计所需的技术，设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。设计结束后要写出课程设计报告、【重点】 【难点】 提高综合运用栈和队列知识，解决复杂问题的能力，以便熟练掌握栈和队列两种数据结构的实际应用。 2、主要内容 　【问题】 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。　【任务】 试为停车场编制按上述要求进行管理的模拟程序。设n=,输入数据为：(A,1,5)，(A,2,6)，D,1,10)，A,3,7)，A,4,8)，A,5,10)，D,2,12)，D,4,20)，E,0,0)。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。 【重点】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。 【难点】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 提高综合运用二叉树的知识，解决复杂问题的能力，以达到熟练掌握二叉树的运算和性质。 2、主要内容 　【问题】 (复原)。对于双工信道 (即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。　【任务】 试为这样的信息收发站写一个哈夫曼码的编译码系统。 输入THIS PROGRAM IS MY FAVORITE，字符集和其频度如下： 空格 A B C D E F G H I J K L M 频度 186 64 23 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 20 56 19 2 50 51 55 30 10 11 2 21 2 3、重点与难点 【重点】 哈夫曼码的编译码系统 (l)I:初始化 (Initialization)。从终端读入字符集大小n，及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。 (2)从终端读入字符(3)C:编码 (Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。 ()D:译码 (Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。 ()P:输出编码文件 (Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 ()T:输出哈夫曼树 (Tree printing)。将已在内存中的哈夫曼树以直观的方式 (树或凹入表