《数据结构》课程教学大纲

数据结构教学大纲一、本大纲适用专业本大纲适用于计算机科学与技术本科专业。二、编写本教学大纲的说明（一）课程类别与教学任务《数据结构》是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是操作系统、数据库原理、编译原理、软件工程、人工智能等课程的基础。数据结构技术广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。通过本课程的学习，使学生了解软件分析阶段、设计阶段、编码阶段的若干基本问题，明确数据结构的内容包括抽象、实现和评价三个层次，即五个基本组成“要素”逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析，初步具备分析问题、解决问题的能力，养成良好的程序设计风格。为学生在此领域中继续学习和研究打下坚实的基础。（二）本课程的基本要求1.

了解数据结构的基本概念和术语、掌握算法描述、算法分析方法。2.

掌握线性表的抽象数据类型定义，线性表的逻辑结构和存储结构，及线性表的各种运算的实现技巧。3.

掌握栈和队列这两种最常用数据结构的逻辑结构、存储结构，初步掌握栈和队列的运用技巧，应用方法。4.掌握串的基本概念、串的基本操作和存储结构，理解串的模式匹配算法和改进的KMP算法。5.

掌握数组的定义、顺序存储表示与实现，掌握几种特殊矩阵的存储方法，掌握广义表的概念及存储的实现。6.

掌握树和二叉树的概念、存储结构，基本运算及其遍历，掌握哈夫曼树的概念和构造方法以及哈夫曼编码的概念。7.

掌握图的有关概念、存储结构、遍历算法、生成树的求法以及拓扑排序的概念及求法。8.

掌握静态查找表、动态查找表及哈希表的概念、存储结构、及实现方法。9.

掌握各类排序的方法，算法的性能分析，应用特点。（三）本课程的重点和难点1.

数据结构的基本概念和术语，算法的时间复杂度分析；2.

线性表的逻辑结构、存储结构及线性表的各种运算的实现技巧；3.

栈和队列的数据结构的逻辑结构、存储结构，运用技巧，应用方法；4.

串的基本概念、串的基本操作和存储结构，理解串的模式匹配算法和改进的KMP算法。5.

数组的定义、顺序存储表示与实现，特殊矩阵的存储方法，广义表的概念及存储的实现；6.

树和二叉树的概念、存储结构，基本运算及树的遍历，哈夫曼树的概念和构造方法；7.

图的有关概念、存储结构、遍历算法、生成树的求法以及拓扑排序的概念及求法，最短路径的概念及其实现算法；8.

各类排序的方法，算法的性能分析。（四）本课程与其他相关课程的联系和后续课程先修课程：《高级程序设计语言》、《离散数学》（五）学时、学时分配安排本课程理论课时为54课时，18个课时的实践课时，具体学时安排见教学内容。（六）本课程的教学方式及其它教学环节的安排本课程采用通常的课堂教学方式，并注重理论与实践相结合的方法，即以教师的课堂教授为主，同时辅以学生课外实践，培养与提高学生对本学科的兴趣和研究能力。三、教学基本内容和学时分配第1章

绪论（3课时）1．什么是数据结构2．基本概念和术语3．抽象数据类型的表示与实现4．算法和算法分析第2章

线性表（3课时）1．线性表的类型和定义2．线性表的顺序表示和实现3．线性表的链式存储和实现4．一元多项式的表示及相加第3章

栈和队列（6课时）1．栈的定义及实现2．栈的应用3．队列的定义及实现4．队列的应用第四章串（3课时）1.

串的基本概念、串的基本操作和存储结构2.

串的模式匹配算法和改进的KMP算法第5章

数组和广义表（3课时）1．数组的类型定义2．数组的顺序表示和实现3．矩阵的压缩存储第6章

树和二叉树（9课时）1．树的定义和基本术语2．二叉树3．遍历二叉树和线索二叉树4．树和森林5．哈夫曼树及其应用第7章

图（12课时）1．图的定义和术语2.

图的存储结构3．图的遍历4．图的连通性问题5．有向无回图及其应用6．最短路径第9章

查找（6课时）1.

静态查找表2.

动态查找表3.

哈希表第10章

内部排序（9课时）1．概述2．插入排序3．快速排序4.

选择排序5.

归并排序6.

各类内部排序方法的比较讨论上机实践及内容1.

线性表操作（链表）——插入、删除、合并、查找（4课时）2.

树和二叉树的应用

——建立二叉树、遍历二叉树（4课时）3.

图的应用

——寻找两顶点间边数最少的一条路径（4课时）4.

查找

——静态、动态查找算法（2课时）5.

排序

——数组、链表排序算法（4课时）四、教材与教学参考书教材：《数据结构》（C语言版）

严蔚敏吴伟民编著清华大学出版社教学参考书：1.

《数据结