《高级程序设计实践》教学大纲
一、课程说明
课程编号：090274X11
总学时数：2.0 (其中实践学时：2天)
学 分：2.0
先修课程：
本大纲适用专业（已默认取出培养方案中开设的专业）
计算机科学与技术,交通运输,交通运输卓越人才培养
教材、教学参考书
教材名称*
ISBN编号*
数据结构（用面向对象方法与C++语言描述）
9787302148111
C++程序设计(第2版)
9787302254881
二、课程达成目标
本课程设计是学生必做的实践教学环节之一。其任务是使学生能够获得较系统的技能训练，进一步加深对所学知识的了解，特别是对C++程序设计、数据结构、算法设计与分析的相关知识有深刻了解，并能熟练运用相关算法解决实际问题，从而巩固和加强所学的面向对象程序设计和数据结构知识。目的是培养学生的综合运用能力，使学生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人才。
三、课程的基本要求
知识：
掌握C++基本语法和面向对象的基本概念，线性表、树、图等数据结构的操作算法及常见的排序查找算法，了解相关算法的作用，算法在系统中的基本实现等知识。学会从数据逻辑结构的理念出发来优化系统，建立系统优化的基本思维方式，从各种数据结构的特性，从结构表达算法和结构处理算法出发，形成数据结构表达－数据结构操作－系统实现的基本知识结构。
能力：
从系统性能优化的角度进行数据结构基本知识方法的掌握，将相关算法用于解决数据结构操作的关键问题；用优化思想进行数据结构的算法的设计，培养解决复杂工程问题的能力；掌握最基本的算法设计理念，针对具体问题提出有效的解决方案，提高开发新算法的能力；在交叉知识的讨论中培养创新意识，提高分析、发现、研究和解决问题的能力；
素质：
建立数据表达－数据操作－系统优化一体的观念，通过课程中的分析讨论辩论，培养分析沟通交流素质，建立基本数据结构到算法的思维模式，提升理解工程管理与经济决策的基本素质。通过课外导学的模式，提升自主学习和终身学习的意识，形成不断学习和适应发展素质。
四、教学内容、重点难点及教学设计
五、实践教学内容和基本要求
对教学内容的知识点进行整理归纳，分别与四个实际应用问题（航空机票订票系、四则运算表达式求值、哈夫曼编/译码器、校园景点规划和导游）相结合，因此将实践的内容分为必做（基本操作）和选做（系统设计）两部分。其中基本操作部分与课堂教学的知识点相对应，为必做部分；系统设计是从四个实际问题中选做一个，设计并实现相应的界面、功能模块等，构建一个具有良好人机交互的原型系统。
（一） 单链表、队列、二叉树查找和排序算法的实践
实践目的或任务：通过指导学生上机实践，结合航空机票订票系统，对单链表、队列、二叉树查找和排序算法的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。
实践基本要求：
1、了解实验目的及实验原理；
2、编写程序，并附上程序代码和结果图；
3、总结在编程过程中遇到的问题、解决办法和收获。
实践的内容或要求：
1、基本操作（必做部分）
（1）编写函数，实现输入一组元素，建立一个带头结点的单链表；对该链表进行非递减排序；实现在非递减有序链表中删除值为x的结点；
（2）编写函数，采用链式存储和顺序存储实现队列的初始化、入队、出队操作；
（3）编写函数，建立有序表，利用二叉排序树的插入算法建立二叉排序树；在以上二叉排序树中删除某一指定关键字元素；采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)
（4）选用1-3的数据结构，编写程序实现下述五种算法：简单插入排序，冒泡排序，快速排序，归并排序，堆排序。
2、航空机票订票系统设计（四选一选做部分）
（1）设计每条航线所涉及的信息，如终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）等；
（2）结合基本操作的单链表、队列、二叉树等数据结构以及排序算法，设计机票系统的查询、订票、退票等功能；
（3）设计并实现人机交互友好的界面或菜单。
（二） 栈与二叉树遍历的实践
实践目的或任务：通过指导学生上机实践，对栈与二叉树遍历的基本概念及其不同的实现方法的理论得到进一步掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。
实践基本要求：
1、了解实验目的及实验原理；
2、编写程序，并附上程序代码和结果图；
3、总结在编程过程中遇到的问题、解决办法和收获。
实践的内容或要求：
1、基本操作（必做部分）
（1）编写函数，分别采用链式存储和顺序存储实现栈的初始化、入栈、出栈操作； 3.编写函数，采用链式存储实现队列的初始化、入队、出队操作
（2）编写函数，建立二叉树的二叉链表；实现二叉树的前中后序的递归和非递归遍历算法。
2、四则运算表达式的求值系统设计（四选一选做部分）
（1）结合基本操作，建立表达式二叉树，输出树的前中后序遍历的结果，计算表达式的值。
（2）当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。
（3）设计并实现人机交互友好的界面或菜单。
（三） 哈夫曼树编译码的实践
实践目的或任务：通过指导学生上机实践，对哈夫曼树的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。
实践基本要求：
1、了解实验目的及实验原理；
2、编写程序，并附上程序代码和结果图；
3、总结在编程过程中遇到的问题、解决办法和收获。
实践的内容或要求：
1、基本操作（必做部分）
（1）编写函数，实现创建哈夫曼树的算法；
（2）编写函数，实现求哈夫曼编码的算法；
（3）根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码
2、哈夫曼编/译码器的系统设计（四选一选做部分）
（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中。将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
（2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
（3）利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。
（4）设计并实现人机交互友好的界面或菜单。
（四） 图的最小生成树和最短路径的实践
实践目的或任务：
通过指导学生上机实践，对图的基本概念，以及图的最小生成树和最短路径的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。
实践基本要求：
1、了解实验目的及实验原理；
2、编写程序，并附上程序代码和结果图；
3、总结在编程过程中遇到的问题、解决办法和收获。
实践的内容或要求：
1、基本操作（必做部分）
（1）编写用邻接矩阵表示无向带权图时图的基本操作的实现函数，主要包括：①初始化邻接矩阵表示的无向带权；②建立邻接矩阵表示的无向带权图； ③输出邻接矩阵表示的无向带权图；编写生成最小生成树的Prim算法函数以及输出边集数组的函数
（3）利用邻接矩阵构造有向带权图，并求出某一顶点到其余顶点的最短路径并打印输出；编写求最短路径的DijKstra算法函数，该算法求从顶点i到其余顶点的最短路径与最短路径长度；3.编写打印输出从源点到每个顶点的最短路径及长度的函数；
2、校园景点规划和导游的系统设计（四选一选做部分）
（1）设计你所在学校的校园平面图，所含景点不少于10个。
（2）在n个校园景点之间要先建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题，利用最小生成树的Prim算法求解。通信线路一旦建立，必然是双向的，因此，构造最小生成树的网一定是无向网；设图的顶点数不超过30个，且网中的权值设成小于100的整数，可用随机函数产生。
（2）以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度的相关信息。①为来访客人提供图中任意景点的相关信息查询；②为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径；③提供图中任意景点问路查询，即求任意两个景点之间的所有路径。
（4）设计并实现人机交互友好的界面或菜单。
六、考核方式及成绩评定