程序设计和算法综合训练教学大纲2016年.docx

?程序设计与算法综合训练?教学大纲课程编号：课程名称：程序设计与算法综合训练英文名称：ComprehensiveTrainingofProgrammingDesignandAlgorithm学分/学时：/80课程性质：必修适用专业：软件工程/网络工程/计算机科学与技术专业先修课程：高级语言程序设计(C语言版)，数据构造(C语言版)开课单位：计算机科学与技术学院一、课程的教学目标与任务?程序设计与算法综合训练?是一门面向软件工程专业、网络工程专业、计算机科学与技术专业的综合实践课程。它是配合专业学科平台课程?高级语言程序设计?和？数据构造?而开设的实践性教育环节。本课程的目的是：通过本课程的综合实践训练，使学生加深对?高级语言程序设计?和？数据构造?课程中基本知识与基本原理的理解；掌握各种数据类型的使用技巧和模块化程序设计的方法；掌握程序设计的过程和技巧，确立分析问题、建设模型和运用程序进展问题求解的思维方式；掌握复杂数据构造在计算机中的存储表示及其运算，建设正确的数据组织与数据处理的设计思想,培养学生综合运用数据构造课程的相关设计理论与实际问题相结合解决数据组织与分析、数据处理与算法设计等设计问题的能力。二、课程具体内容及基本要求工程一迷宫问题的求解(8学时)问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1 .基本要求(1)首先实现一个以链表作存储构造的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。其中：(Lj)指示迷宫中的一个坐标，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)o用已建好的哈夫曼树，对文件ToBeTran.data中的文本进展编码形成报文，将报文写在文件Code.txt中；(3)译码(Decoding)o利用已建好的哈夫曼树，对文件COdeFile.data中的代码进展解码形成原文，结果存入文件Textfile.txt中；输出(Output)o输出DataFile.data中出现的字符以及各字符出现的频度(或概率)；输出ToBeTran.data及其报文Code.txt；输出CodeFileJata及其原文Textfile.txt；2 .重点、难点重点：(1)通过实验理解哈夫曼树的特征及其应用；(2)哈夫曼树的构造算法设计；(3)利用构造的哈夫曼树进展编码和译码。难点：(I)字符的哈夫曼树编码及存储；(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个)，然后根据人数通过ma11oc函数来分配存放选手信息的顺序表；(2)将选手的编号和姓名依此存入顺序表中；(3)观众通过按键进展投票，按'1'为1号选手投票，按'2,为2号选手投票，以此类推，以按'0,作为投票完毕标志；(4)投票完毕后进展排序，在此采用各种排序算法，然后为每个选手计算名次，得票一样的名次也一样；2 .重点、难点重点：(1)参赛选手数据构造的设计；(2)排序算法的设计；难点：各种排序算法的性能分析与比较3 .作业及课外学习要求：按照题意要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点43能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力，稳固良好的编程习惯，掌握工程软件设计的基本方法,为后续课程的学习打下坚实根基。工程七药店的药品销售统计系统的设计与实现(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熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点43能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力，稳固良好的编程习惯，掌握工程软件设计的基本方法,为后续课程的学习打下坚实根基。三、教学安排及方式总学时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能够对原型验证方法进展研究与分析，合理验证软件系统"的指标达成度进展评估。了解程序设计与算法的前沿开展现状和趋势，对新知识、新技术有较敏锐的洞察能力，为后续课程的学习打下坚实根基。五、考核及成绩评定方式考核方法：针对每个设计工程，设计报告占30%,设计作品占70%。总成绩取8个设计工程成绩的平均值。六、教材及参考书目1 .教材?数据构造(C语言版)?,严蔚敏，吴伟民编著，清华大学出版社，1997年.2 .参考书目(1) ?数据构造一C语言描述？，耿国华等，西安电子科技大学出版社，2002年.(2) ?(：程序设计(第三版)？谭浩强著，清华大学出版社，2005年.(3) ?数据构造题集(C语言版)？，严蔚敏，吴伟民编著，清华大学出版社，1997年.(4) ?数据构造教程(第4版)?,李春葆等，清华大学出版社，2012年附：综合设计报告标准1需求分析在该局部中根据设计题目的要求，充分地分析和理解问题，表达系统的功能要求，明确问题要求做什么限制条件是什么1.1 问题描述1.2 基本要求(1)输入的形式和输入值的范围;(2)输出的形式；程序所能到达的功能。2概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。(1)数据构造(2)程序模块(3)各模块之间的调用关系以及算法设计3 .详细设计实现概要设计中定义的所有数据类型,对每个操作写出C语言算法;对主程序和其他模块也都需要写出C语言算法：写出函数和过程的调用关系。4 .测试与分析测试数据，输出测试的结果，这里的测试数据应该完整和严格。并对结果进展分析。5 .总结总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据构造这门课程的思考、在课程设计过程中对所学课程的认识等内容。6.附录源程序清单。(执笔人：邹海审核人：高湘萍)2016年6月15日