《数据结构》学习指南

国家精品课程西北大学《数据结构》学习指南学习指南（课程导学）一、课程的性质与目标“数据结构”是计算机科学与技术本科各专业的统设必修、学位课程。本课程4学分，理论课72学时，上机实验28学时。“数据结构”是计算机科学与技术专业的一门重要专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据、正确有效地设计算法并能对算法的时空性能进行分析和评价。通过本课程的学习，使学生较深入地理解数据的逻辑结构和物理结构，掌握有关算法和基本的程序设计技能，能编制高效且有一定难度的程序，为学习后续课程奠定基础。课程以C语言作为数据结构和算法的描述工具。教学环节包括理论教学和上机实验，教学中注重基础，突出应用，强化数据结构基本知识和程序设计基本能力的双基训练。二、为什么要学习数据结构在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须考虑数据的组织结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题变得越来越重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据元素之间的相互关系更为复杂。因此，解决这类问题的关键是要设计出合适的组织数据、存储数据的方法，在此基础上设计出处理数据的操作算法，才能有效地解决问题。例如，学生管理信息系统需要将全校各院系、各专业、各年级学生的信息有效地组织到一起，并提供查询、增删、更新、排序等操作。类似的还有图书管理系统、库存管理系统、人力资源管理系统等。另外，在描述各种分类问题时，需要用到树状结构，而更复杂的问题需要用到网状结构或图结构。综上所述，描述这类非数值计算问题的求解模型不再是数学方程，而是诸如表结构、树结构、图结构之类的数据结构，以及定义在这些数据结构上的有关操作。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的操作对象以及它们之间的关系和操作的学科。数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构及其相关操作算法。因此，要想更好地运用计算机来解决实际问题，要想有效地使用计算机、充分发挥计算机的性能，需要学习和掌握好数据结构的有关知识。课程中所学习的基本的线性表、树、图等数据结构，以及查找、排序等算法，是从事计算机技术研究与应用的基本工具。B_树、B+树、散列表等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等后续课程的重要基础。人工智能中的各种知识表示都是以现有数据结构为基础，搜索技术是以栈、队列、优先队列等为基础，人工智能语言是以递归定义的广义表为基础，所以递归处理是其基本方法。所以学好数据结构这门课程，可以为学习计算机专业的后续课程打下坚实基础。图1表示了本课程在计算机学科中与其他课程的关系。图1“数据结构与算法”与其他课程的关系三、数据结构的知识体系“数据结构与算法”课程介绍基本数据结构、基本算法设计技术、排序、检索和索引技术。常用的基本数据结构包括线性表、栈和队列、串、数组和广义表、树和二叉树、图等，针对每种基本数据结构，分别讨论相应的存储结构和操作算法，并对算法做时间、空间效率分析，介绍时空权衡的原则。基本算法设计技术包括递归法、分治法、回溯法、贪心算法、基于栈和队列的程序设计技术等。常用的经典算法包括各种内部排序算法和查找算法，在介绍算法的时，将深入讨论其时间和空间效率。另外，还将介绍文件管理和外部排序技术，以及有关索引技术。图2给出了“数据结构与算法”课程的知识体系图。图2“数据结构与算法”知识体系图四、各章的学习目标、重点和难点1绪论1.1学习目标熟练掌握数据结构和算法的基本概念(数据的逻辑结构，数据的存储结构，算法定义，算法设计的要求、算法描述规范要点、算法设计风格)；熟练掌握抽象数据类型的抽象描述方法和具体实现方法；熟练掌握算法性能评价的有关概念和基本的算法复杂度分析方法；熟练掌握问题求解的基本过程。1.2重点数据结构（逻辑结构、存储结构）抽象数据类型（定义、实现）算法（定义、设计要求、高级语言要点、复杂度分析）问题求解的基本过程1.3难点抽象数据类型的逻辑定义与物理实现；算法的渐进时间复杂度分析方法；问题求解的基本过程。2线性表2.1学习目标熟练掌握线性表的顺序存储结构和相应的操作实现；熟练掌握线性表的链式存储结构和相应的操作实现，包括单链表、循环链表、双向链表；了解静态链表；能熟练运用线性表解决实际问题。2.2重点线性表的抽象数据类型定义用顺序结构实现线性表用链表结构实现线性表（单链表、循环链表、双向链表）线性表应用实例。2.3难点头结点的作用，单指针、双指针、多指针的用法，指针初始化指向的确定处理时判断当前结点与判断当前结点的后继结点的不同用处指向头指针的指针，指针保留技术，链表复制与链表重组的区别。3栈与队列3.1学习目标熟练掌握栈和队列的定义与特点；熟练掌握栈和队列的存储结构（顺序结构和链式结构）和相应的操作实现；初步掌握栈与递归技术（递归定义、递归算法特征、递归的实现机制、递归到非递归的转换）；能较熟练运用栈和队列解决实际问题。3.2重点栈和队列的特性；栈和队列的典型应用；递归算法的设计与分析；栈与递归的实现机制；递归程序转化为非递归程序的方法。3.3难点利用栈和队列解决实际问题的方法；递归算法的设计与分析；栈与递归的实现机制；递归程序转化为非递归程序的通用方法。4字符串4.1学习目标熟练掌握字符串的存储结构（定长顺序串、堆串）与操作实现；熟练掌握串的模式匹配、基本的串编辑应用技术。4.2重点本章重点包括：堆串存储结构的特点；定长顺序串、堆串操作实现的异同；串的模式匹配；串的应用。4.3难点串的替换操作；串的模式匹配；串的应用。5数组和广义表5.1学习目标熟练掌握普通数组的顺序存储和高维数组地址计算；熟练掌握特殊矩阵的压缩存储存储和地址计算（规则分布矩阵及稀疏矩阵），包括规则分布矩阵的规律表示、稀疏矩阵表示（用三元组表、十字链表），以及在相应的压缩表示结构下实现转置等典型矩阵运算方法；初步掌握广义表的存储结构和表头表尾等基本操作。5.2重点数组的存储结构与地址计算，特殊矩阵的压缩存储稀疏矩阵（分别用三元组表、十字链表实现转置、加减法等矩阵运算）广义表的存储结构，广义表的基本操作。5.3难点多维数组的存储结构与地址计算，特殊矩阵压缩存储公式推导用三元组表实现矩阵的快速转置十字链表的结构与操作，广义表的存储结构6树形结构及其应用6.1学习目标熟练掌握二叉树的性质；二叉树的存储结构（顺序表示、二叉链表表示）；二叉树运算，重点是二叉树的遍历算法及其应用（递归遍历、非递归遍历算法、递归到非递归的转换算法、由遍历序列确定二叉树等）；熟练掌握树的存储结构（树的双亲表示法、树的孩子表示法、树的二叉链表即孩子兄弟链表法）；熟练掌握树、森林与二叉树的关系，树的遍历方法；树和二叉树的转换方法（重点理解树的孩子兄弟链表存储结构与二叉树的二叉链表存储结构间的关系）；熟练掌握哈夫曼树及其应用。6.2重点二叉树的遍历算法及其应用（递归遍历算法、非递归遍历算法、递归遍历算法到非递归遍历算法的转换方法、由遍历序列确定二叉树等）树的存储结构与操作实现，树、森林及其与二叉树的对应关系哈夫曼树及其应用。6.3难点二叉树的非递归遍历算法，递归遍历算法到非递归遍历算法的转换方法二叉树不同遍历方法的灵活应用，线索二叉树的建立和使用用树的孩子兄弟链表实现树的基本操作。7图结构及其应用7.1学习目标熟练掌握图的存储结构（邻接矩阵、邻接表）；熟练掌握图的遍历方法与应用（深度搜索与广度搜索）；熟练掌握图的典型算法（最小生成树、拓扑排序、关键路径、最短路径）。7.2重点图的存储结构（邻接矩阵、邻接表）图的遍历方法与应用（深度优先搜索与广度优先搜索）图的典型算法（最小生成树、拓扑排序、关键路径、最短路径）。7.3难点图的遍历方法与应用图的典型算法（最小生成树、关键路径、最短路径）8常用查找技术8.1学习目标熟练掌握顺序查找、折半查找，了解分块查找；熟练掌握二叉排序树，初步掌握平衡二叉排序树、B-树方法；熟练掌握哈希表查找（构建哈希函数、解决冲突的方法）；熟练掌握基本的查找性能分析方法。8.2重点折半查找二叉排序树计算散列式查找查找性能分析方法8.3难点二叉排序树的删除操作各种查找方法的性能分析平衡二叉排序树B-树方法9内部排序9.1学习目标熟练掌握典型排序算法的思想和实现过程；能够通过理论分析，比较各种排序算法的优缺点，比较他们在最坏、最好、平均情况下的复杂度；能够通过上机验证，直观比较各种排序算法的排序速度；能够根据不同情况，选择合适的排序算法；能够判断排序算法的稳定性；9.2重点直接插入排序，希尔排序冒泡排序，快速排序简单选择排序，堆排序稳定排序与不稳定排序，多种排序方法的综合比较9.3难点希尔排序，堆排序排序算法的时间复杂度分析典型排序算法的综合比较10外部排序与文件组织技术简介10.1学习目标初步掌握外存信息特性、外排序的基本方法；初步掌握索引文件、多重表、倒排表。10.2重点外排序的基本方法索引文件多重表倒排表10.3难点败方树索引文件多重表倒排表五、考评方式与标准“数据结构与算法”是理论与实践并重的课程，采用理论知识考核与实验考核相结合的考核方式。理论知识考核采用平时考核、期中考试、期末考试相结合的考核方式，满分为100分。平时成绩（20%）平时成绩包括书面作业完成情况（10%）、学习态度（3%）、学习纪律（3%）、课堂表现（3%）、课堂测试成绩（1%）。其中书面作业完成情况包括完成作业数量（4%），完成作业质量（5%），书写是否认真（1%）等方面。学习纪律包括考勤，是否按时提交作业等。课堂表现包括上课时是否做与课堂无关的事等，听课是否认真专注，是否主动向教师提出问题，回答教师提问时的表现等。学习态度表现在各个教学环节，包括是否经常迟到、早退、旷课，是否经常在课堂上做与上课无关的事，是否经常不按时提交作业，是否经常抄袭作业（有抄袭痕迹，如将b抄写为6），是否经常有作业潦草的情况等。期中考试成绩（20%）期中考试采用闭卷考试的形式，考查学生对前六章基本概念和基本方法的掌握程度。答题时间120分钟，卷面分数100分，试卷题型与期末考试相同。期末考试成绩（60%）期末考试采用闭卷考试的形式，考查学生对全书基本概念和基本方法的掌握程度和综合运用能力。重点考查后五章内容，其中前六章内容不少于30%。答题时间120分钟，卷面分数100分。试卷题型包括简答题、选择题、填空题、构造题、算法设计题，完整试卷参所附样卷。实验考核采用上机表现、程序质量、实验报告质量相结合的考核方式，满分为100分。上机表现（30%）包括出勤情况（5%）、调试表现（10%）、当面验收表现（15%）等。其中调试表现包括是否做与要求题目无关的事情，上机准备是否充分（概要设计、详细设计），调试时是否认真专注，与辅导老师的交流情况等。当面验收时，教师针对分析、概要设计、详细设计、编码和调试等环节随机提出若干问题，考察学生对实验技能的掌握情况。程序质量（40%）包括程序的正确性（15%）、程序的健壮性（5%）、算法的时空性能（10%）、程序逻辑结构的合理性（15%）、以及程序设计风格和程序的可读性（5%）。其中程序的正确性分三个层次：（1）算法对于几组输入数据能够得出满足要求的结果，（2）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果，（3）算法对于一切合法的输入数据都能产生满足要求的结果。达到第二个层次即可。程序逻辑结构的合理性涉及ADT类型定义的合理性，常量的合理使用，是否使用了全局变量，函数原型的声明，主函数功能的合理界定，子函数的合理划分，函数参数的合理确定，传值和传地址的合理使用，返回值类型的合理定义，返回值方式的合理使用，局部变量的设置与定义位置是否合理，顺序语句的先后顺序是否自然，分支语句的结构是否清晰，循环语句的选用是否自然等方面。良好的程序设计风格首先要求程序具有良好的逻辑结构，此外还涉及代码的缩进格式，括号的位置，合理的换行，是否有充分的注释，函数名称、参数名称、变量名称、类型名称、常量名称等标示符名称的合理性等方面。实验报告质量（30%）包括需求分析（3%）、模块划分（7%）、数据结构与ADT设计（7%）、算法设计（7%）、调试分析（3%）、总结（3%）等。六、学习方法建议“数据结构与算法”的先修课程包括离散数学，计算机导论，高级语言程序设计等，其中高级语言程序设计与课程学习的关系最为密切。教材中数据存储结构的定义和算法描述通常采用某种高级语言（最常用的是C语言），如果高级语言程序设计不熟练，看书学习和上机调试就会比较困难。高级语言程序设计基础较差的同学，要利用课余时间从最简单的程序开始调试，遇到问题向书本请教，向同学请教，还可以向网络提问。高级语言程序设计基础较好的同学，要利用课余时间加强那些与数据结构关系密切的高级语言知识点，如C语言的指针、结构体、自定义类型、函数定义、参数传递与结果返回方法等。上课时注意体会老师讲解时使用的形象图解、生动比喻、动画演示等，并尝试运用到学习中去，给出自己的形象图解、生动比喻、动画演示创意等，将抽象的知识变成形象地、有趣的知识。课后应借助本课程的网络教学平台和教材附带的光盘自主学习，巩固并拓展课堂所学内容。此外，还有大量其它的网络资源可以参考，应尽量选择正规的网站，并注意把握好时间。要重视书面作业。书面作业是消化掌握课堂知识的重要环节，是培养计算思维的重要手段，是上机训练的前提条件。如果书面算法逻辑混乱、效率低下，上机调试就会事倍功半。除了完成要求的作业，还要尽量多看一些习题指导类的资料，包括网上资源。数据结构和算法问题通常没有一个绝对正确的标准答案，不同的方法有不同的优缺点和适用范围。学习中既要独立思考，也要多和大家交流。互相启发思想，开阔思路，但坚决反对盲目照搬照抄。平时要多看好的参考书，加深对教材内容的理解，把书本越读越厚。然后通过归纳理出要点，提纲携领，总结提高，使书本越读越薄。要重视上机实验。数据结构是理论学习与上机训练并重的课程，实验是学好本课程的重要环节，是对学生的全面综合训练。