学习指南(数据结构基础).doc

《数据结构基础》学习指南 《数据结构》是计算机、信息管理与信息系统等信息系统相关专业的一门重要的核心基础课程，主要任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及一些非数值运算的种类、方法和算法设计。通过学习，学生不仅要掌握数据的组织、存储和处理的常用方法，更重要的是能针对问题的应用背景分析、选择最佳的数据结构与算法，从而提高问题求解和软件的研发能力。作为核心基础课，数据结构与算法课程的内容比较成熟、稳定，是一门理论性与实践性都很强的课程。 学习的主要内容包括：数据结构的基本概念；算法的评价方法；数据的逻辑结构，包括线性表、堆栈、队列、树、图等常用数据结构；数据的存储结构，包括顺序存储和链式存储；以及各类操作的实现，包括插入、删除、查找、排序、输入输出、遍历等；在此基础上进行简单的应用，能用C语言写出存储结构及相应的算法，并上机通过。 一. 《数据结构》课程的难点 《数据结构》课程普遍反映难学。既有理论又有实践，尤其在刚开始学习时，由于与前驱程序设计课程的跨度比较大，学生往往是听听容易做做难，一时难以理解。 上机实现难 数据结构学习很重要的一方面就是上机实现，相比前期程序设计课程，无论是解决的问题、算法设计、程序调试还是代码量上，都有一个很大的提升。虽然有时候理解内容了，但是实现上面还是很困难。 原理知识难 数据结构是一门理论和实践都很强的课程，除了要清楚各种数据结构的特征外，还需要理解各种与结构有关的性质，如二叉树就具有多个相关性质。更重要的是理解算法的核心思想，切记不要把算法等同于程序，这是学习这门课的一个很简单的大忌，在理解思想的基础上再开始看算法。 与实际结合难 很多同学在学习数据结构时提出缺少与实际应用的结合。数据结构讲述的是现实生活中计算机所要处理的数据的逻辑关系、存储结构以及在此上的各种操作的实现。本身是一个基础课程，与实际问题的结合前提是先理解各种结构的特征、组织方式以及常有的操作算法。在此基础上，考虑与现实问题的结合。 二、《数据结构》课程的学习方法 与一般的课程类似，基本上就是课前看看书、课时仔细听课、课后认真复习、独立做习题、多上机实现。仔细看书与独立上机编程是学好数据结构课程的两大前提。 课堂中 课堂中讲解的一般都是些重点与难点，这些内容靠自己课后看会比较难理解，或者未能切中要点，故课堂中仔细听时前提，且数据结构是一门逻辑型很强的课程，稍不留神可能会难以跟上教师的思路。 课堂后 数据结构要反复看书，特别是算法思想以及设计技巧，量变引起质变，当看多了的时候，突然会茅塞顿开。很多同学上课听懂了但课后又不会做的主要原因就是课后未能有效看书。以理解为前提，切忌死记硬背。 习题 习题是检验课程内容掌握程度的最有效的方法，对每一个知识点必须做一定数量的习题，用以了解结题的思路、方法以及各种的变化，并加以独立的思考，多在纸上画画写写，可以相互讨论，但切忌为完成任务而抄袭。 实验 编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序、对算法的敏感。 不少同学在上机编程时照搬教材的原代码，不考虑为什么，不管方法的好坏，使得实验课变成打字课；其次，当碰到程序错误时，不知如何调试修改。比较好的方法是：事先看懂教材的算法或原代码，包括其设计的思想、设计的方法，然后独立编写相应的实验题，一旦碰到问题，可再参考教材的方法。第三，程序的错误必定会存在，但需要掌握自己的调试改错方法，清楚错误的原因、错误的地方、解决的方法等，在独立调试改错的过程中不断提高程序设计的能力与水平。 《数据结构基础》各章知识点概述 第一章 绪论 1.1 基本术语 数据是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。 数据元素可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是数据项。 数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类（称为数据的逻辑结构）：集合、线性结构、树形（层次）结构、图形（网状）结构。如图1.1所示。 a 线性结构 b 集合结构 c 树形结构 d 图形结构 图1.1 四种常见的数据结构 数据的存储结构是数据逻辑结构在计算机中的映像，由关系的两种映像方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它不仅仅包含数据元素本身的信息，并附加的指针信息（后继元素的存储地址）表示关系。 数据结构的操作是和数据结构本身密不可分的，两者作为一个整体可用抽象数据类型进行描述。抽象数据类型是一个数学模型以及定义在该模型上的一组操作，因此它和高级程序设计语言中的数据类型具有相同