致远数据结构课程大纲

1、数据结构课程大纲、课程简介课程名称：数据结构 学时/学分： 52/3先修课程：程序设计面向对象：ACM 班教学目标：在学生已掌握了结构化程序设计和面向对象程序设计的基础上， 进一步介绍 数据结构和算法设计 /分析的基本知识。本课程围绕着数据结构的思想、方 法、 实现和应用等方面， 培养学生掌握设计一个有效的算法和数据结构的能 力，以及用计算机解决问题的能力。主要内容：以数据的逻辑关系为线索，介绍了线性关系、 树状关系、 集合关系和图形关 系的数据元素的存储及处理方法，以及在C+ 中的具体实现。、教学内容第一章 绪论 主要内容：数据结构的研究内容、算法分析。 重点与难点：什么是数据结构，如何计算

2、算法的时间复杂度。第二章 线性表 主要内容：线性表的顺序实现和链接实现。 重点与难点：如何用面向对象的方法封装一个类。第三章 栈 主要内容：栈的顺序实现和链接实现，栈的主要应用。 重点与难点：如何用栈消除递归、计算算术表达式和检查程序中的括号配对。第四章 队列 主要内容：队列的顺序实现和链接实现、队列的应用。 重点与难点：循环队列的实现，排队系统的模拟。第五章 树 主要内容：树和二叉树的实现，以及树的应用。 重点与难点：二叉树的实现。第六章 优先级队列 主要内容：基于树的优先级队列的实现和应用。 重点与难点：二叉堆、多服务台的排队系统的模拟。第七章 集合与静态查找表主要内容：无序表和有序表的查

3、找。重点与难点：二分查找第八章查找树主要内容：二叉查找树、 AVL树、红黑树、AA树、伸展树、B+树。 重点与难点：二叉查找树的思想、平衡的概念第九章散列表主要内容：散列表的组成、散列函数、碰撞的解决。 重点与难点：散列的基本思想。第十章排序主要内容：插入排序、选择排序、交换排序、归并排序、外排序。 重点与难点：堆排序、冒泡排序、快速排序。第十一章不相交集主要内容：不相交集的实现与应用。重点与难点：不相交集的实现即算法的改进。第十二章图的基本概念主要内容：图的存储方法及基本运算的实现。重点与难点：邻接表与邻接矩阵、深度优先搜索与广度优先搜索。第十三章最小生成树主要内容：最小生成树的生成。重点与

4、难点：Prim算法和Kruskal算法第十四章最短路径问题主要内容：单源最短路径和所有顶点对的最短路径。重点与难点：Dijkstra算法和Floyd算法。第十五章算法设计基础主要内容：常用的算法设计技术。重点与难点：分治法、动态规划、回溯法三、教学进度安排教学内容教学形式作业第一周概论课堂教学第二周线性表的实现及线性表的应用课堂教学、上机第三周栈的概念与实现、栈的应用课堂教学、上机第四周队列的概念、实现与应用课堂教学、上机第五周二叉树的概念与实现课堂教学、上机第六周二叉树的应用与哈夫曼树、树的实现课堂教学、上机第七周优先级队列、优先级队列的应用课堂教学、上机第八周集合与静态查找、二叉查找树课堂

5、教学、上机第九周AVL树、红黑树、AA树课堂教学、上机第十周伸展树、B+树课堂教学、上机第十一周散列表课堂教学、上机第十二周排序课堂教学、上机第十三周不相交集与图的基本概念课堂教学、上机第十四周图的存储、基本运算的实现课堂教学、上机第十五周最小生成树和最短路径问题课堂教学、上机第十六周算法设计基础课堂教学、上机四、课程考核及说明50%为平时成绩（大作业等）：机考（15）+平时作业（10）+大作业（15）+课堂练习（10）50%为期末考试成绩五、教材与参考书1。 数据结构：思想与实现翁惠玉 俞勇 高等教育出版社 2009。2。数据结构：题解与拓展翁惠玉 俞勇高等教育出版社 2011。3。Mark

6、 Allen Weiss.Data Structures and Algorithm Analysis in C+（Third Edition ）人民邮电出版社2007年1月4。 Mark Allen Weiss. Data Structures and Problem Solving Using JAVA （Third Edition ） 人民邮电出版社2006年7月5。 陈慧南数据结构-C+语言描述人民邮电出版社2005年3月6。Sartaj Sahni. Data Structures, Algorithms, and Applications in C+机械工业出版社 2000年1月7。 晋良颖数据结构人民邮电出版