《程序设计与算法综合训练教学大纲2016》由会员分享，可在线阅读，更多相关《程序设计与算法综合训练教学大纲2016（10页珍藏版）》请在金锄头文库上搜索。
1、程序设计与算法综合训练教学大纲课程编号：课程名称：程序设计与算法综合训练 英文名称：Comprehensive Training of Programming Design and Algorithm学分/学时： /80 课程性质：必修 适用专业： 软件工程/网络工程/计算机科学与技术专业先修课程： 高级语言程序设计（C 语言版） ，数据结构（C 语言版）开课单位： 计算机科学与技术学院一、课程的教学目标与任务程序设计与算法综合训练是一门面向软件工程专业、网络工程专业、计算机科学与技术专业的综合实践课程。它是配合专业学科平台课程高级语言程序设计和数据结构而开设的实践性教育环节。本课程的目的是：
2、通过本课程的综合实践训练，使学生加深对高级语言程序设计和数据结构课程中基本知识与基本原理的理解；掌握各种数据类型的使用技巧和模块化程序设计的方法；掌握程序设计的过程和技巧，确立分析问题、建立模型和运用程序进行问题求解的思维方式；掌握复杂数据结构在计算机中的存储表示及其运算，建立正确的数据组织与数据处理的设计思想，培养学生综合运用数据结构课程的相关设计理论与实际问题相结合解决数据组织与分析、数据处理与算法设计等设计问题的能力。 二、课程具体内容及基本要求 项目一 迷宫问题的求解( 8 学时)问题描述：以一个 m*n 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意
3、设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.基本要求（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i ，j ，d）的形式输出。其中：（i，j ）指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如，对于教材第 50 页图 3.4 所示的迷宫，输出一条通路为：（1，1，1） ， （1，2，2） ， （2，2，2） ， （3，2，3） ， （3，1，2） ，。（2）编写递归形式的算法，求得迷宫中所有可能的通路。（3）以方阵形式输出迷宫及其通路。2.重点、难点重点：针对迷宫问题的特点，利用栈的后进先出特点，选择适当的数据结构。
4、难点：递归算法的设计与求解。3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点 4.2 熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.3 能够对原型验证方法进行研究与分析，合理验证软件系统”的指标达成度进行评估。使学生在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计
5、的基本方法，为后续课程的学习打下坚实基础。项目二 停车场管理系统的设计与实现( 8 学时)问题描述：停车场内只有一个可停放 n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端） ，若车场内已停满 n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要
6、求进行管理的模拟程序。1.基本要求（1）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。（2）每一组输入数据包括三个数据项：汽车“到达”或“ 离去 ”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费） 。（3）栈以顺序结构实现，队列以链表实现。2.重点、难点重点：针对停车场问题的特点，利用栈的后进先出特点，选择栈这种数据结构来模拟停车场，利用队列先进先出的特点，选择队列这种数据结构来模拟车场外的便
7、道。难点：离散事件问题的模拟算法设计与求解。3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点 4.2 熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.3 能够对原型验证方法进行研究与分析，合理验证软件系统”的指标达成度进行评估。使学生在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，
8、掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。项目三 银行业务模拟系统的设计与实现( 8 学时)问题描述：假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。1.基本要求（1）初始化（OpenForDay） ，模拟银行开门时各数据结构的状态。（2）事件驱动（EventDrived
9、）, 对客户到达和离开事件做相应处理。（3）下班处理（CloseForDay ） ，模拟银行关门时的动作，统计客户平均逗留时间。2.重点、难点重点：（1）通过实验掌握对离散事件模拟的认识；（2）进一步理解队列的实现与应用；（3）对链表的操作有更深层次的理解。难点：离散事件的模拟。3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点 4.2 熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.3 能
10、够对原型验证方法进行研究与分析，合理验证软件系统”的指标达成度进行评估。使学生在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。项目四 哈夫曼编/译码系统的设计与实现 ( 16学时)问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/
11、译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。1.基本要求（1）初始化（Initialzation） 。从数据文件 DataFile.data 中读入字符及每个字符的权值，建立哈夫曼树 HuffTree；（2）编码（EnCoding） 。用已建好的哈夫曼树，对文件 ToBeTran.data 中的文本进行编码形成报文，将报文写在文件 Code.txt 中；（3）译码（Decoding） 。利用已建好的哈夫曼树，对文件 CodeFile.data 中的代码进行解码形成原文，结果存入文件 Textfile.txt 中；（4）输出（Output） 。输出 DataFile.data 中出现
12、的字符以及各字符出现的频度（或概率） ；输出 ToBeTran.data 及其报文 Code.txt；输出 CodeFile.data 及其原文 Textfile.txt；2.重点、难点重点：（1）通过实验理解哈夫曼树的特征及其应用；（2）哈夫曼树的构造算法设计；（3）利用构造的哈夫曼树进行编码和译码。难点：（1）字符的哈夫曼树编码及存储；（2）字符的译码与串的匹配算法。3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点
13、4.2 熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.3 能够对原型验证方法进行研究与分析，合理验证软件系统”的指标达成度进行评估。使学生在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。项目五 通讯录查询系统的设计与实现( 8 学时)问题描述：为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的电话与地址。设计散列表存储，设计并实现通讯录查找系统。1.基本要求（1）每个记录有下列数据项
14、：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码为关键字建立散列表；（3）采用二次探测再散列法解决冲突；（4）查找并显示给定电话号码的记录；（5）通讯录信息文件保存。2.重点、难点重点：（1）通过实验深入理解哈希表既是一种存储形式，又是一种查找方法；（2）哈希表的构造；（3）哈希冲突方案的设计。难点：哈希表的构造与哈希冲突方案的设计3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点 4.2 熟悉复杂软件系统
15、的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.3 能够对原型验证方法进行研究与分析，合理验证软件系统”的指标达成度进行评估。使学生在解决具体问题的过程中，能够灵活熟练地选择合适的数据结构及设计有效的算法，从而加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。项目六 电视大赛观众投票及排名系统的设计与实现( 8 学时)问题描述：在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。
16、要求编写算法模拟实现上述系统的功能。1.基本要求（1）首先输入参赛选手的人数（范围为 1-9 个） ，然后根据人数通过 malloc 函数来分配存放选手信息的顺序表；（2）将选手的编号和姓名依此存入顺序表中；（3）观众通过按键进行投票，按1为 1 号选手投票，按2 为 2 号选手投票，以此类推，以按0 作为投票结束标志；（4）投票结束后进行排序，在此采用各种排序算法，然后为每个选手计算名次，得票相同的名次也相同；2.重点、难点重点：（1）参赛选手数据结构的设计； （2）排序算法的设计；难点：各种排序算法的性能分析与比较3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求 4 研究”中的“指标点 4.1 能够运用科学的研究方法对复杂软件工程问题进行需求分析研究；指标点 4.2 熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点 4.
