程序设计与算法综合训练教学大纲.doc

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