《程序设计》课程大纲-Shouleme.doc

《数据结构》课程大纲 课程简介 课程名称： 数据结构 学时/学分：68/4 先修课程：程序设计 面向对象：ACM班 教学目标：在学生已掌握了结构化程序设计和面向对象程序设计的基础上，进一步介绍数据结构和算法设计/分析的基本知识。本课程围绕着数据结构的思想、方法、实现和应用等方面，培养学生掌握设计一个有效的算法和数据结构的能力，以及用计算机解决问题的能力。 主要内容：以数据的逻辑关系为线索，介绍了线性关系、树状关系、集合关系和图形关系的数据元素的存储及处理方法，以及在C++中的具体实现。 教学内容 绪论 主要内容：数据结构的研究内容、算法分析。 重点与难点：什么是数据结构，如何计算算法的时间复杂度。 线性表 主要内容：线性表的顺序实现和链接实现。 重点与难点：如何用面向对象的方法封装一个类。 栈 主要内容：栈的顺序实现和链接实现，栈的主要应用。 重点与难点：如何用栈消除递归、计算算术表达式和检查程序中的括号配对。 队列 主要内容：队列的顺序实现和链接实现、队列的应用。 重点与难点：循环队列的实现，排队系统的模拟。 树 主要内容：树和二叉树的实现，以及树的应用。 重点与难点：二叉树的实现。 优先级队列 主要内容：基于树的优先级队列的实现和应用。 重点与难点：二叉堆、多服务台的排队系统的模拟。 集合与静态查找表 主要内容：无序表和有序表的查找。 重点与难点：二分查找 查找树 主要内容：二叉查找树、AVL树、红黑树、AA树、伸展树、B+树。 重点与难点：二叉查找树的思想、平衡的概念 散列表 主要内容：散列表的组成、散列函数、碰撞的解决。 重点与难点：散列的基本思想。 排序 主要内容：插入排序、选择排序、交换排序、归并排序、外排序。 重点与难点： 堆排序、冒泡排序、快速排序。 不相交集 主要内容：不相交集的实现与应用。 重点与难点：不相交集的实现即算法的改进。 图的基本概念 主要内容：图的存储方法及基本运算的实现。 重点与难点：邻接表与邻接矩阵、深度优先有哪些信誉好的足球投注网站与广度优先有哪些信誉好的足球投注网站。 最小生成树 主要内容：最小生成树的生成。 重点与难点：Prim算法和Kruskal算法 最短路径问题 主要内容：单源最短路径和所有顶点对的最短路径。 重点与难点：Dijkstra算法和Floyd算法。 算法设计基础 主要内容：常用的算法设计技术。 重点与难点：分治法、动态规划、回溯法 教学进度安排 教学内容 教学形式 作业 第一周 概论 课堂教学 第二周 线性表的实现及线性表的应用 课堂教学、上机 第三周 栈的概念与实现、栈的应用 课堂教学、上机 第四周 队列的概念、实现与应用 课堂教学、上机 第五周 二叉树的概念与实现 课堂教学、上机 第六周 二叉树的应用与哈夫曼树、树的实现 课堂教学、上机 第七周 优先级队列、优先级队列的应用 课堂教学、上机 第八周 集合与静态查找、二叉查找树 课堂教学、上机 第九周 AVL树、红黑树、AA树 课堂教学、上机 第十周 伸展树、B+树 课堂教学、上机 第十一周 散列表 课堂教学、上机 第十二周 排序 课堂教学、上机 第十三周 不相交集与图的基本概念 课堂教学、上机 第十四周 图的存储、基本运算的实现 课堂教学、上机 第十五周 最小生成树和最短路径问题 课堂教学、上机 第十六周 算法设计基础 课堂教学、上机 课程考核及说明 50%为平时成绩（大作业等）：机考（15）+平时作业（10）+大作业（15）+课堂练习（10） 50%为期末考试成绩 教材与参考书 1。数据结构：思想与实现 翁惠玉 俞勇 高等教育出版社 2009。 2。 Mark Allen Weiss. Data Structures and Algorithm Analysis in C++（Third Edition） 人民邮电出版社2007年1月 3。Mark Allen Weiss. Data Structures and Problem Solving Using JAVA（Third Edition）人民邮电出版社 2006年7月 4。陈慧南 数据结构 – C++语言描述 人民邮电出版社 2005年3月 5。Sartaj Sahni. Data Structures, Algorithms, and Applications in C++ 机械工业出版社 2000年1月 6。晋良颖 数据结构 人民邮电出版社 2006年1月 7。Cormen T H. Introduction to Algorithms 高等教育出版社 2001年 8。严慰敏、吴伟民 数据结构（C语言版） 清华大学出版社 2007年 9。陈小平