2022年《数据结构教程》 .pdf

《2022年《数据结构教程》 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构教程》 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构教程自学指导教材：数据结构教程，迟乐军等编，北京航空航天大学出版社教师：曾晓红单位：昭通师范高等专科学校计算机科学系2009年 5 月名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -一、绪论1、课程知识体系：数据结构是计算机专业一门重要的专业技术基础课程。数据结构的研究范围主要涉及数据的逻辑结构、存储结构和操作的实现，以及常用的查找和排序技术。其内容是程序设计(特别是非数值计算的程序设计)的基础，也是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。通过这门课程的学习，使学生在软件开发的过程中能够正确、合理地选择数据的存储结构，有效地

2、设计算法，从而提高软件整体质量。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。知识体系如下：(1)数据的定义：数据的逻辑结构、数据的存储结构、数据的运算、线性结构、树形结构、图结构、文件结构、图树二叉树线性表、顺序方法、链接方法、索引方法(线性、树形)、散列方法。(2)算法的效率问题：对于给定的一类问题：算法需要多少存储空间和时间？最好算法的最坏情况是什么？平均来说，算法的运行好到何种程度？算法一般化到何种程度？什么情况下，最好的算法是什么？(3)抽象数据类型：抽象数据类型是定义了一组运算的数学模型。把数据结构的存储与实现细节剥离。在适当的抽象层次上考虑程序的结构和算法。

3、封装和信息隐蔽。2、课程学习要求：本课程学习范围及要求：本课程将分别讲述数据结构的基本概名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等内容。应掌握的知识点及层次要求：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价；掌握线性表的概念和类型定义、线性表的顺序存储结构和链式存储结构；掌握栈和队列的应用方法，理解栈的重要作用、利用栈实现行编辑，利用栈实现表达式求值；了解数据结构的基本概念，理解常用术语、掌握串的基本概念及其基本运算、掌握串的存储结构；掌握数组和广义表的定义、运算及存储

4、结构、矩阵的压缩存储；掌握树和二叉树的类型定义、运算及存储结构、树的各种表示、各种存储方式和运算，二叉树的概念及其运算和应用、二叉树的非递归运算及应用；掌握图的基本概念、图的存储结构和图的常用算法；掌握排序的概念、熟悉各种排序方法、掌握插入法排序的各种具体实现方法及算法分析、掌握选择法排序的各种具体方法的实现及时间性能分析、掌握交换法排序的具体实现及性能分析、掌握归并排序和基数排序的各自实现算法；掌握各种不同的查找表的查找算法和性能分析(线性表的查找、树表的查找和哈希表的查找以及各种查找的性能分析)；掌握文件的概念、顺序文件、索引文件、ISAM 文件、VSAM 文件、散列文件的组织形式与检索方

5、法。学员自主学习要求：自学时仔细阅读教材中的例题，从中体会并最终掌握数据结构中的基本概念；认真上机实习，加强对相关知识点的理解；独立完成每个章节后面的练习题；能够用计算机解决一个名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -实际问题，将实际问题的数据信息存入计算机，并设计能解决问题的算法。面授辅导设计：串讲本课程；深入讲解学员在自学过程中普遍遇到的问题；针对每个学员的个别问题逐一解答。课程考核要求及考核方式：课程考核方式采用笔试，平时作业成绩占学期成绩的50%。严禁抄袭别人作业，否则，一经发现学期成绩不予及格。3、学 习 支 持 服 务 方 式 及 承 诺：学 生 可

6、 以 通 过 电 子 邮 件(ZTZXH126.COM)与我进行交流。对于学生在学习中提出的问题，我一定尽快帮助解决，最迟不超过1周帮助学生解决提出的问题。二、分论第一章绪论1、本章的知识结构：数据结构的基本概念。2、本章的重点、难点、测评点：数据结构包含数据元素集合和数据元素之间关系的集合。理解算法与数据结构之间的关系。理解算法设计的要求。掌握算法效率度量方法。3、本章自测题：P17(15)。第二章线性表1、本章的知识结构：线性表的特点，线性表的顺序实现和链式实现，线性表的应用；字符串的基本运算，及其应用。2、本章的重点、难点、测评点：1)理解线性表的结构和特点，掌握线性表上基本操作的实现算

7、法。2)掌握顺序存储线性表的表名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -元素与存储单元的对应关系，基本操作的实现算法。3)掌 握 链 接 存储线性表的表元素与存储单元的对应关系。单链表、双向链表和循环链表的存储结构和特点，基本操作的实现算法。4)理解字符串的存储结构，字符串的基本运算。5)掌握字符串简单匹配算法；理解字符串 KMP 匹配算法。6)具有用用线性表、字符串解决实际问题的能力。3、本章自测题：P36(115)。第三章栈和队列1、本章的知识结构：栈和队列的基本运算及其应用。2、本章的重点、难点、测评点：1)理解栈的定义和结构特点，掌握其存储方式(顺序存储与

8、链接存储)和基本操作的实现算法。2)理解队列的结构和特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算法。3)具有用队列和栈结构解决实际问题的能力。3、本章自测题：P56(18)。第四章串和数组1、本章的知识结构：串的概念和基本操作、串的存储结构、串的操作实现、数组、矩阵的压缩存储。2、本章的重点、难点、测评点：串的基本操作的几个函数、串的存储结构。数组及其存储结构。3、本章自测题：P74(112)。第五章树和二叉树1、本章的知识结构：树和二叉树。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -2、本章的重点、难点、测评点：1)理解树的结构和定义，掌握树的主要

9、概念。2)理解各种二叉树的结构，掌握其特点，具有运用二叉树解决实际问题的能力。3)掌握二叉树的三种遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题，掌握遍历的非递归实现方法。4)掌握线索化二叉树的结构和基本操作。5)理解树的存储结构，掌握树的遍历等方法的实现。6)理解霍夫曼编码的基本原理，掌握基于霍夫曼树生成霍夫曼编码的方法。3、本章自测题：P113(117)。第六章图和广义表1、本章的知识结构：图的基本概念和存储结构、图的遍历、生成树、最短路径、拓扑排序、关键路径、广义表。2、本章的重点、难点、测评点：图的遍历、生成树、最短路径、关键路径。3、本

10、章自测题：P148(111)。第七章排序1、本章的知识结构：插入排序；交换排序；选择排序；归并排序；基数排序。2、本章的重点、难点、测评点：理解各种排序方法的实现，掌握各种排序算法的时间复杂性，各种排序算法的特性。3、本章自测题：P167(113)。第八章查找名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -1、本章的知识结构：静态查找表、动态查找表、哈希表及哈希查找、2、本章的重点、难点、测评点：顺序查找、折半查找、分块查找、二叉排序树、二叉平衡树、哈希表的查找与删除。3、本章自测题：P186(17)。第九章文件1、本章的知识结构：文件的基本概念、顺序文件、索引文件、散列文件、多关键字文件。2、本章的重点、难点、测评点：1)理解文件的基本概念。2)理解顺序文件的概念。3)理解索引文件的概念。4)理解散列文件的概念。5)理解多关键字文件的概念。3、本章自测题：P201(15)。三、作业：各章自测题。四、复习要求：完成各章自测题。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -