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

《数据结构基础》学习指南《数据结构》是计算机、信息管理与信息系统等信息系统相关专业的一门重要的核心基础课程，主要任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及一些非数值运算的种类、方法和算法设计。通过学习，学生不仅要掌握数据的组织、存储和处理的常用方法，更重要的是能针对问题的应用背景分析、选择最佳的数据结构与算法，从而提高问题求解和软件的研发能力。作为核心基础课，数据结构与算法课程的内容比较成熟、稳定，是一门理论性与实践性都很强的课程。学习的主要内容包括：数据结构的基本概念；算法的评价方法；数据的逻辑结构，包括线性表、堆栈、队列、树、图等常用数据结构；数据的存储结构，包括顺序存储和链式存储；以及各类操作的实现，包括插入、删除、查找、排序、输入输出、遍历等；在此基础上进行简单的应用，能用C语言写出存储结构及相应的算法，并上机通过。一.《数据结构》课程的难点《数据结构》课程普遍反映难学。既有理论又有实践，尤其在刚开始学习时，由于与前驱程序设计课程的跨度比较大，学生往往是听听容易做做难，一时难以理解。1．上机实现难数据结构学习很重要的一方面就是上机实现，相比前期程序设计课程，无论是解决的问题、算法设计、程序调试还是代码量上，都有一个很大的提升。虽然有时候理解内容了，但是实现上面还是很困难。2．原理知识难数据结构是一门理论和实践都很强的课程，除了要清楚各种数据结构的特征外，还需要理解各种与结构有关的性质，如二叉树就具有多个相关性质。更重要的是理解算法的核心思想，切记不要把算法等同于程序，这是学习这门课的一个很简单的大忌，在理解思想的基础上再开始看算法。3．与实际结合难很多同学在学习数据结构时提出缺少与实际应用的结合。数据结构讲述的是现实生活中计算机所要处理的数据的逻辑关系、存储结构以及在此上的各种操作的实现。本身是一个基础课程，与实际问题的结合前提是先理解各种结构的特征、组织方式以及常有的操作算法。在此基础上，考虑与现实问题的结合。二、《数据结构》课程的学习方法与一般的课程类似，基本上就是课前看看书、课时仔细听课、课后认真复习、独立做习题、多上机实现。仔细看书与独立上机编程是学好数据结构课程的两大前提。1．课堂中课堂中讲解的一般都是些重点与难点，这些内容靠自己课后看会比较难理解，或者未能切中要点，故课堂中仔细听时前提，且数据结构是一门逻辑型很强的课程，稍不留神可能会难以跟上教师的思路。2．课堂后数据结构要反复看书，特别是算法思想以及设计技巧，量变引起质变，当看多了的时候，突然会茅塞顿开。很多同学上课听懂了但课后又不会做的主要原因就是课后未能有效看书。以理解为前提，切忌死记硬背。3．习题习题是检验课程内容掌握程度的最有效的方法，对每一个知识点必须做一定数量的习题，用以了解结题的思路、方法以及各种的变化，并加以独立的思考，多在纸上画画写写，可以相互讨论，但切忌为完成任务而抄袭。4．实验编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序、对算法的敏感。不少同学在上机编程时照搬教材的原代码，不考虑为什么，不管方法的好坏，使得实验课变成打字课；其次，当碰到程序错误时，不知如何调试修改。比较好的方法是：事先看懂教材的算法或原代码，包括其设计的思想、设计的方法，然后独立编写相应的实验题，一旦碰到问题，可再参考教材的方法。第三，程序的错误必定会存在，但需要掌握自己的调试改错方法，清楚错误的原因、错误的地方、解决的方法等，在独立调试改错的过程中不断提高程序设计的能力与水平。《数据结构基础》各章知识点概述第一章绪论1.1基本术语数据是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。数据元素可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是数据项。数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类（称为数据的逻辑结构）：集合、线性结构、树形（层次）结构、图形（网状）结构。如图1.1所示。a)线性结构b)集合结构c)树形结构d)图形结构图1.1四种常见的数据结构数据的存储结构是数据逻辑结构在计算机中的映像，由关系的两种映像方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它不仅仅包含数据元素本身的信息，并附加的指针信息（后继元素的存储地址）表示关系。数据结构的操作是和数据结构本身密不可分的，两者作为一个整体可用抽象数据类型进行描述。抽象数据类型是一个数学模型以及定义在该模型上的一组操作，因此它和高级程序设计语言中的数据类型具有相同含义，而抽象数据类型的范畴更广，它不局限于现有程序设计语言中已经实现的数据类型，但抽象数据类型需要借用固有数据类型表示并实现。抽象数据类型的三大要素为数据对象、数据关系和基本操作，同时数据抽象和数据封装是抽象数据类型的两个重要特性。1.2算法和算法的量度算法是进行程序设计的不可缺少的要素。算法是对问题求解的一种描述，是为解决一个或一类问题给出的一种确定规则的描述。一个完整的算法应该具有下列五个要素：有穷性、确定性、可行性、有输入和有输出。一个正确的算法应对苛刻且带有刁难性的输入数据也能得出正确的结果，并且对不正确的输入也能做出正确的反映。算法设计的原则主要包含以下几个方面：正确性、可读性、健壮性以及高效率与低存储量需求。算法的时间复杂度是比较不同算法效率的一种准则，算法时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。常见的时间复杂度，按数量级递增排列依次为：常数阶(1)O、对数阶2(log)On、线性阶()On、线性对数阶2(log)Onn、平方阶2()On、立方阶3()On、指数阶(2)nO、阶层阶((!)On)、指数阶(()nOn)。算法空间复杂度可作为算法所需存储量的一种量度，它主要取决于算法的输入量和辅助变量所占空间，若算法的输入仅取决于问题本身而和算法无关，则算法空间复杂度的估算只需考察算法中所用辅助变量所占空间，若算法的空间复杂度为常量级，则称该算法为原地工作的算法。1.3实践1）自定义类型为了使程序便于理解，应该把一些数据类型名与要说明的对象性质建立某些语义上的对应关系，可以用typedef向用户提供了一种自定义类型说明符，一般形式为：typedef类型定义名；使用typedef定义数据类型新名字既照顾了用户编程使用词汇的习惯，又增加了程序的可读性，便于程序的移植。用typedef定义类型，只定义了一个数据类型的新名字而不是定义一种新的数据类型。2）输入输出语句使用包含文件语句#includeiostream.h后，可使用以下关键字进行输入/输出：cin代表标准输入设备（键盘）流对象，后面跟“”运算符，“”是C++的输入运算符；cout代表标准输出设备（屏幕）流对象，后跟“”运算符，“”是C++的输出运算符；cerr代表标准错误输出设备（屏幕）流对象，后跟“”运算符。3）引用参数在C语言中，可以使用指针参数达到修改形参所指向的变量的值，但指针的间接性给人一种不实在感。C++引入引用的主要目的是建立某种类型的虚实体，这种虚实体不占有实际的存储空间。它作为函数参数时，从实参得到相应的地址，与实参共用相同的存储空间，也就是被调用函数中形参的变化会导致所对应实参的变化。使用方法是在形式参数之前插入“&”符号。4）动态存储分配C++的new运算符和delete运算符提供了动态分配内存的功能。new的功能是给程序实体动态地分配存储空间，delete运算符的功能是将用new运算符动态分配的空间回收。new和delete运算符都是单目运算符，new运算符不能对动态分配的存储区进行初始化。第二章线性结构2.1线性表的定义和抽象数据类型线性表是最简单、最常用的一类数据结构。简单地说，线性表是n（n≥0）个相同类型数据元素a1,a2,…,ai,…,an构成的有限序列，通常表示为(a1,a2,…,ai,…,an)。线性表中元素的个数n称为线性表的长度，n=0时称为空表。线性表的第一个元素a1称为表头元素，最后一个元素an称为表尾元素。线性表中的元素是按照前后位置线性有序的，通常把第i个元素ai称为第i+1个元素ai+1的前驱，元素ai+1称为元素ai的后继。线性表是一种线性结构，用二元组表示为：Linear_list=(D,R)其中，D={ai|ai∈ElemType,i=1,2,...,n,n≥0}R={r}r={ai,ai+1|ai,ai+1∈ElemType,i=1,2,...,n-1}线性表相当灵活，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以在任意位置进行插入和删除等。线性表的抽象数据类型定义如下：ADTLinearListisData:n（n≥0）个相同类型数据元素a1,a2,…,an构成的有限序列，用类型名ListType表示。Operation:voidInitList(ListType&L);//初始化L为空voidClearList(ListType&L);//清除L中所有元素intLenthList(ListTypeL);//返回L的长度boolEmptyList(ListTypeL);//判断L是否为空，若空返回1，否则返回0ElemTypeGetList(ListTypeL,intpos);//返回L中第pos个元素的值voidTraverseList(ListTypeL);//遍历输出L中的所有元素boolFindList(ListTypeL,ElemTypeitem);//从L中查找元素item，若查找成功返回1，否则返回0boolInsertList(ListType&L,ElemTypeitem,intpos);//向L插入元素item，并返回是否插入成功。1≤pos≤n时插在第pos位置；//pos=-1时插在表尾；pos=0时插在有序表的适当位置，使保持有序boolDeleteList(ListType&L,ElemType&item,intpos);//从L删除元素，被删元素赋给item,并返回是否删除成功。//1≤pos≤n时删除第pos位置上的元素；pos=-1时删除表尾元素；//pos=0时删除指定元素itemvoidSortList(ListType&L);//对L中的元素进行排序endLinearList这里列出的线性表的基本操作是线性表中一些常见的基本操作，读者可以根据需要添加一些别的基本操作。2.2线性表的顺序存储表示线性表的存储结构主要有两种，即顺序存储和链接存储。线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表的各个数据元素。其特点是逻辑上相邻的元素在物理存储上也相邻。假设线性表的每个元素需占用b个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i个数据元素的存储位置LOC(ai)为：LOC(ai)=LOC(a1)+(i-1)*b其中：LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称为线性表的起始位置。线性表的顺序存储结构示意图如图2.1所示，其中MAXSIZE为顺序存储的线性表允许的最大空间量。存储地址内存状态数据元素在线性表中序号a1a2…ai…an空闲Loc(a1)+(MAXSIZE-1)b…Loc(a1)+nb……Loc(a1)+(i-1)bLoc(a1)+bLoc(a1)n…i21…图2.1线性表的顺序存储结构示意图通常把顺序存储结构的线性表称为顺序表。顺序表可以使用数组来实现，数组的基本类型就是线性表中元素的类型，数组的大小（又称数组长度）要大于等于线性表的长度。顺序表的存储结构类型定义可描述为：typedefstruct{ElemTypelist[MaxSize];//数组名为listintsize;//存储当前元素的个数，最后一个元素的数