《数据结构及应用》教学大纲.docx

致寤绪扬及用课程教学大纲一、课程的基本信息适应对象：电子信息工程本科专业课程代码：22E00314学时分配：总学时64学时，讲授48学时, 上机实验16学时赋予学分：4分先修课程：C语言程序设计 后续课程：面向对象程序设计等二'课程性质与任务数据结构及应用是电子信息工程 本科专业的一门核心课程，它与电子信息 工程本科专业的各门主课都有密切联系， 是一门实践性极强的技术基本课，其内容 随信息科学与技术的飞速开展而不断更 新。课程通过讲授、练习和课外上机实践, 培养学生根据求解的要求，选择合适的数 据结构，应用抽象数据类型的思想方法， 组织数据和算法的能力，培养良好的程序 设计方法，为学习各后继课程及实际工程 开发打下良好基础。三、教学目的与要求1、理解数据结构的基本概念，包括算法、 数据类型、抽象数据类型、复杂度的分析等。 理解数据结构和程序设计方法的联系和作用。2、掌握用C描述抽象数据类型的方法，在 原有的基础上进一步理解C语言中的一些重要 概念，如动态存储结构，指针和链表等。3、掌握字符串、表、堆栈、队列、树、二 叉树、队列、散列表、图等典型的数据结构的 概念、性质、实现方法。4、了解各数据结构之间的关系，包括结构 上的关系和实现关系。5、掌握一些基本的查找和排序方法，如顺 序查找、二分查找、树查找、散列、Hash、简 单排序、快速排序、堆排序、归并排序、基数 排序等。6、掌握一些重要的应用和算法，如多项式、 稀疏矩阵、表达式求值、拓扑排序、哈夫曼树、 最短路径、最小生成树、堆排和快排等。7、掌握经典的算法思想，如分治法、贪心 法、动态规划和回溯法；8、会用时间复杂性和空间复杂度，以评价 实现各数据结构的算法和各应用算法的优劣。四'教学内容与安排1、课时安排本课程共48个课时（课堂讲授48课时）， 按照课程内容，分成8个教学单元，各单元的 课时安排如下表。序号单元名称讲 授讨 论实 验小 计1绪论222线性表的顺序存储及其 运算622103链表42284串225数组和广义表226树和二叉树824147图824148查找和排序62412课时合计381016642、教学内容第一单元绪论【教学内容】本课程讲解内容；数据结构的课程地位、 整体安排；数据结构的基本概念和术语；算法 的描述和算法分析。【教学重点与难点】教学重点：数据结构的基本概念和术语； 算法的描述和算法分析。教学难点：算法的描述和算法分析。【基本要求】掌握数据结构的基本概念和术语；理解算法的描述和算法分析；理解数据结构的地位。【培养的能力】对算法的描述方法和评价方式。第二单元线性表的顺序存储及其运算【教学内容】线性表的逻辑结构；线性表上的运算；栈 和队列的概念；栈和队列的运算；栈和队列的 应用。【教学重点与难点】教学重点：线性表的定义、描述、操作； 栈和队列的概念、运算和应用；。教学难点：线性表的描述；栈和队列的运 算和应用。【基本要求】掌握顺序表的定义及逻辑特征；掌握顺序表上的运算在两种存储结构上的 实现；会编写顺序表上制定要求的算法；掌握栈和队列的特性，并能实现栈和队列 的的基本运算；能灵活运用栈和队列解决程序设计中的问 题。完成通讯录管理的应用。（实验）【培养的能力】线性表的顺序存储结构的操作、实现和解 决相关问题的能力。第三单元链表【教学内容】线性表的链式存储；链表的逻辑结构与定 义；链式栈和链式队列的概念和运算；循环链 表；链式栈和链式队列的的应用。【教学重点与难点】教学重点：线性表的链式存储、定义、描 述、操作；链式栈和链式队列的概念、运算和 应用；循环链表。教学难点：链表的逻辑结构与定义；链式 栈和链式队列的运算。【基本要求】掌握线性链表的结构特点和运算；掌握栈和队列的链式存储；掌握循环链表的结构特点和运算；能灵活运用链式栈和链式队列解决程序设 计中的问题。完成停车场管理的应用。（实验）【培养的能力】线性表的链式存储结构的操作、实现和解 决相关问题的能力。第四单元串【教学内容】串类型的定义；串的存储；串的运算实现。【教学重点与难点】教学重点：串的存储；串的运算实现。教学难点：串的运算。【基本要求】掌握串类型的定义，串的存储；理解串的运算实现。【培养的能力】串的操作、实现和解决相关问题的能力。第五单元数组和广义表【教学内容】数组的定义；数据的顺序存储和实现；特 殊矩阵的压缩存储；广义表的定义和存储结构。【教学重点与难点】教学重点：数据的顺序存储和实现；特殊 矩阵的压缩存储；广义表的定义和存储结构。教学难点：特殊矩阵的压缩存储。【基本要求】掌握数组的定义；掌握特殊矩阵的压缩存储方式；了解广义表的定义和存储结构。【培养的能力】数据分析、存储和解决相关问题的能力。第六单元树和二叉树【教学内容】树的定义和基本术语；树的存储结构；二 叉树的概念、存储及遍历二叉树；哈夫曼树及 其应用；树和森林的概念；森林与树的转换； 树和森林的遍历；二叉排序树。【教学重点与难点】教学重点：树的存储结构；二叉树的概念、 存储及遍历二叉树；哈夫曼树及其应用。教学难点：遍历二叉树；哈夫曼树及其应 用。【基本要求】掌握二叉树的定义；掌握二叉树存储结构的特点与适用范围；掌握二叉树的各种遍历方法；能编写二叉树的各种运算算法；掌握树与森林的定义与转换；了解哈夫曼树的特性，掌握建立哈夫曼树 和哈夫曼编码的方法；了解二叉排序树；完成家谱管理的应用；（实验）完成哈夫曼编码的应用。（实验）【培养的能力】数据分析、存储、查找、编码和解决相关 问题的能力。第七单元图【教学内容】图的定义和术语；图的存储结构与操作实 现；图的遍历；最小生成树；图的连通性问题; 最短路径；拓扑排序；图的应用。【教学重点与难点】教学重点：图的存储结构与操作实现；图 的遍历；最小生成树；最短路径。教学难点：图的存储结构；图的遍历算法; 最小生成树；图的应用。【基本要求】掌握图的定义；掌握图的存储结构及实现；掌握图的遍历方法；掌握最小生成树算法；理解图的连通性问题；了解图的应用的各种算法思想，并会用这 种思想求解图的问题；完成图的遍历实验；（实验）完成图的应用实验。（实验）【培养的能力】问题分析、算法设计和解决相关问题的能 力。第八单元查找和排序【教学内容】顺序表上查找；树表上的查找；散列表构 造和查找；各种排序算法；排序算法的分析。【教学重点与难点】教学重点：顺序表上的三种查找方法；二 叉排序树的构造和查找；散列表的构造方法； 各种排序算法。教学难点：二叉排序树；散列表；各种排 序算法的特点与应用。【基本要求】掌握顺序表上的三种查找方法并灵活运 用；掌握二叉排序树的构造和查找方法；掌握散列表的构造方法和散列表上的查找 方法；掌握各种排序方法的实现算法，排序过程;深刻理解各种排序算法的特点，适用范围 并灵活运用；完成教学计划安排的应用。（实验）【培养的能力】顺序、二分、索引查找与散列表构造查找 算法的实现；选择、插入、交换排序算法实现 和解决相关问题的能力。五、教学设备和设施授课使用多媒体教室。六'课程考核与评估1、考试形式：闭卷笔试（120分钟）;2、考试要求：本课程根据本大纲要求 命题；3、课程成绩构成=平时（30%）+期 末考试（70%）七、附录教学参考文献目录1梅霍内等.算法与数据结构.清华大学出版社20132王曙燕.数据结构与算法.人民邮电出版社,20133徐凤生著.数据结构与算法.机械工业出版社20144李春葆主编.数据结构教程.清华大学出版社20165恰汗.合孜尔主编.C语言程序设计中国铁道出版社2014年。第四版、C语言程序设计习题集与上机指导.大纲制定人：李文彬大纲审定人：潘理