《数据结构(C语言-耿国华版)》复习大纲.doc

第一章 绪论1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素的组成：一个数据元素通常由一个或若干数据项组成。数据项：指具有独立含义的最小标识单位。3.数据对象：性质相同的数据元素的集合，是数据的一个子集。4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质：1)输入性：具有零个或若干个输入量；2)输出性：至少产生一个输出；3)有穷性：每条指令的执行次数是有限的；4)确定性：每条指令的含义明确，无二义性；5)可行性：每条指令都应在有限的时间内完成。6.评价算法优劣的主要指标：1)执行算法后，计算机运行所消耗的时间，即所需的机器时间；2)执行算法时，计算机所占存储量的大小，即所需的存储空间；3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。7.会估算某一算法的总执行时间和时间复杂度。8.熟悉习题P32:3(5)-(9)、4(2)(3)第二章 线性表 1.线性表(P7)：是性质相同的一组数据元素序列。线性表的特性：1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。其特点：逻辑上相邻的数据元素，它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(ai)=Loc(a0)+i*s)。2.线性表的查找、插入和删除熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。3.理解线性表的顺序存储结构的优缺点。4.熟悉线性链表的存储结构(P43)线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分数据域和存放另一元素存储地址的部分指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法；6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一个环形，这种形式的链表称为循环链表。)？7.明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；了解双向链表的插入和删除的算法。8.理解链表的优缺点(P48)。9.熟悉习题P68：1、2第三章 限定性线性表-栈和队列1.栈和队列明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，不允许插入和删除的一端称为栈底。栈的插入为进栈，称栈的删除为出栈。栈的特性：后进先出，所以又称后进先出表，简称LIFO表。)。2. 明了什么是顺序栈（用顺序存储结构表示的栈），熟悉顺序栈进栈算法和出栈算法（栈空，栈满判定条件，指针移动）。3.明了什么是链栈(用链表表示的栈。)，熟悉链栈(进栈；出栈)的算法。4.明确什么是队列及其特点(所有的插入(进队)均限制在表的一端进行，所有的删除(出队)被限制在表的另一端。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队列结构特点：先进队的元素先出队，故也称为先进先出表，简称FIFO表。)。5.了解循环队列及其进队和出队的算法（循环队列队空队满判定条件，指针移动）。6. 明了什么是链队列(采用链表表示队列。)？熟悉链队列(进队、出队)的算法。7.熟悉习题P102：1、3、12第四章 串 1.掌握串的基本概念：串(是由零个或多个字符组成的有限序列。一般记为：s=""(n>=0)。)、串的长度(串中字符的数目n。)、空串(零个字符的串，其长度为零。)、空格串(仅含有空格字符的串，它的长度为串中空格符的个数。)、子串(串中任意个连续的字符组成的子序列)、主串(包含子串的串)、字符在串中的位置(字符在序列中的序号)、子串在主串的位置(以子串第一个字符在主串中的位置来表示)、两个串相等(当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。)2.熟悉串的基本运算：串的赋值运算(assign(a，b)、串的联接运算(concat(a，b)、求串长(length(s)、求子串(substr(s，start，len)、判断两个串是否相等(equal(a，b)；了解求子串在主串中的序号(index(a，b)、替换运算(replace(a，b，c)、插入运算(insert(a,i,b)、删除运算(delete(a,i,k)的功能。3.明了串的存储结构(P81)：串的静态存储结构(是将串定义成字符型数组，从串名可直接访问到串值，串的存储空间分配是在编译时完成的，不能更改)、串的动态存储结构（是串的存储空间分配是在程序运行时动态分配的）；串的静态存储结构采用顺序存储结构；串的动态存储结构有两种方式：一种是采用链式存储结构，另一种是堆结构的存储方式。4.熟悉子串定位函数的算法(P112)。5.熟悉习题(P119)1。第五章 数组和广义表1.数组(P125)：一维数组、二维数组存储地址的计算(一维P125公式，或Loc(ai)=Loc(a0)+i*s；二维P125公式，或Loc(aij)= Loc(a00)+(i*n+j) *s)。2.上三角矩阵、下三角矩阵、带状矩阵的压缩存储，会求任意元素aij在一维数组中的位置。3.稀疏矩阵：指大部分元素为零的矩阵。稀疏矩阵的表示方法三元组表中各元素所表示的意义。4.了解广义表的概念，广义表的长度，广义表的表头，广义表的表尾。5.熟悉习题(P145) 1、3、9。第六章 树 1.掌握一般树的概念：一般树的定义(树是n(n>=0)个结点的有限集合。当n=0时称为空树，否则，在任一棵非空树中：有一个且仅有一个称为该树根(Root)的结点；其余结点可分为m(m>=0)个互不相交的有限集合T1，T2，Tm，且每个集合本身又是一棵树，并称之为根的子树(Subtree)。树的定义是一种递归定义)；树的结点(指一个数据元素及若干指向其子树的分支。)、结点的度(指结点拥有子树的数目。)、叶子结点(指度为零的结点。)、分支结点(指度不为零的结点。)、树的度(指树中各结点度的最大值。)、有序树(将树中结点的各子树看成从左到右是有次序的，称为有序树，否则称为无序树。)、森林(m(m>=0)棵互不相交的树的集合。)树的存储结构：多重链表表示法(每个结点由一个数据域和若干指针域组成。每个指针域将指向该结点的一个孩子。)，多重链表又分为：定长结点的多重链表和不定长结点的多重链表；二重链表示法(即孩子兄弟表示法，树中每个结点设置三个域：数据域、长子指针域和次弟指针域。)2.掌握二叉树的概念二叉树(结点的有限集合，它或者是空集，或者由一个根结点和两个互不相交的该根的左子树和右子树组成，左右子树也是一棵二叉树，显然这也是一个递归定义。)；二叉树是有序的(二叉树中的结点即使只有一棵子树，也要区分它是左子树还是右子树)；两种特殊形态的二叉树：满二叉树(如果一棵深度为K的二叉树，共有2K-1结点，则称为满二叉树。)、完全二叉树(如果深度为k，有n个结点的二叉树，能够与深度为k的顺序编号满二叉从1到n标号的结点相对应。)了解二叉树的性质,会灵活运用性质：性质1 在二叉树的第i层上最多有2i-1个结点(i>=1)。 性质2 高度为h的二叉树最多有2h-1个结点(h>=1)。(可用图5-7a)解释)性质3 对任何二叉树T，设n0、n1、n2分别表示度数为0、1、2的结点数，则有n0= n2+1。(叶子结点数与度数为2的结点数的关系)性质4 具有 n 个结点的完全二叉树的深度为 +1。(注符号表示不大于x的最大整数，则表示不小于x的最小整数) 性质5 如果将一棵有n个结点的完全二叉树，则对任一结点(1<=i<=n)有：1)若 i=1，则i是根结点无双亲；若i>1，则i的双亲结点是 。2)若2i<=n，则i的左孩子是2i；若2i>n，则i无左孩子。3)若2i+1<=n，则i的右孩子是2i+1；若2i+1>n，则i无右孩子。了解二叉树的存储：二叉树通常有两类存储结构：顺序存储结构和链式存储结构。3.掌握二叉树的先序遍历的算法；了解中序遍历、后序遍历的算法。给出一棵树，会写出树的先序中序后序序列。4.明了结点间的路径长度(从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支个数即是结点间的路径长度)、树的路径长度(从树根到每一个结点的路径长度之和称为树的路径长度，一般记作pl。)、带权路径长度(若给二叉树的每个终端结点赋以权值，从而构成的带权路径长度。其计算方法为：wpl=)、哈夫曼树(带权路径长度wpl最小的树称做最优二叉树或哈夫曼树)；熟悉哈夫曼树的算法，给出数据序列，会构造哈夫曼树。5.了解一般树转化为二叉树和二叉还原为一般树。6.熟悉习题(P194) 2、3、4、7、9、11第七章 图1.熟悉图的基本术语：图(G由顶点的集合V(G)和边的E(G)集合组成，记做：G = (V，E)，其中V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。)、有向图(如果图中每条边都是有方向的，即在图示时每条边都用箭头表示方向，则称此图为有向图。)、无向图(如果图中每条边都是顶点无序对，则称为无向图。)、无向完全图(若一个无向图有n个顶点，而每一个顶点与其它n-1个顶点之间都有边，这样的图称为无向完全图，即共有n(n-1)/2条边。)、有向完全图(在有n个顶点的有向图中，若有n(n-1)条弧，即任意两顶点之间都有双向相反的两条弧连接，则称为有向完全图。)、子图(设有两个图G=(V，E)和G'=(V'，E')，如果VV且EE，则称G为G的子图。)、路径(在图G中，从顶点Vp到Vq的一条路径是顶点序列(Vp，Vi1，Vi2，Vin，Vq)且(Vp，Vi1)，(Vi1，Vi2)，(Vin，Vq)是E(G)中的边，路径上边的数目称之为该路径长度。)、连通图(在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。)、强连通图(在有向图G中，若任意两个顶点Vi和Vj都连通的，即从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。)、度(就是依附于该顶点的边数。)、入度和出度(在有向图中，以某顶点为头，即终止于该结点的弧的数目称为该顶点的入度；以某顶点为尾，即起始该顶点的弧的数目称为该顶点的出度。顶点的入度和出度之和称为顶点的度。)2.熟悉图的存储结构(邻接矩阵和邻接链表)，了解建立邻接矩阵或邻接链表的算法：邻接矩阵(是用一个二维数组来表示图中顶点的相邻关系。设图G=V,E有n1个顶点，则G的邻接矩阵是按如下定义的n阶方阵：costij=)、邻接链表(由邻接矩阵改进而来的一种链接结构，它包含两个部分，一部分是向量，另一部分是链表。链表部分共有n个链表，即每个顶点一个链表。每个链表由一个表头结点和若干个表结点组成。向量部分为一个数组，用来存储n个表头结点，向量的下标指示了顶点的序号。)3.熟悉遍历图的算法:深度优先搜索法和广度优先搜索法。4.了解最小生成树、最短路径、拓扑排序和关键路径的概念和用途。5.给出一个无向图，会用普利姆算法和克鲁斯卡尔算法手工构造最小生成树。6.给出一个有向图，会用迪杰斯特拉算法求某一顶点到其余各顶点的最短路径，用弗洛伊德算法求任意一对顶点间的最短路径。7.熟悉习题(P244)1、4、14、15第八章 查找 1.熟悉查找表(由同一数据类型的数据元素(或记录)构成的集合。)、关键字(数据元素(或记录)中某个数据项的值，用它可标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识，则称此关键字为主关键字。)、查找(根据给定的某个关键字的值，在查找表中确定一个其关键字等于给定值的数据元素(或记录)。)的概念。2.熟悉顺序查找（P249）、折半查找（P250-251）的算法，及其平均查找长度。3.了解分块查找的原理。4.明了二叉排序树的概念(二叉排序树的定义：它或者是一个空树，或者是一个具有如下性质的二叉树：(1)若它有左子树，则左子树上有所有结点的数据均小于根结点的数据；(2)若它有右子树，则右子树上所有结点的数据均大于根结点的数据；(3)左，右子树本身又各是一棵二叉树排序树。)；熟悉二叉排序树的算法，给出数据序列，会构造二叉排序树。5.了解什么是哈希法、哈希表和哈希函数(存取过程中需要在记录存储位置和它的关键字之间建立一个确定的对应关系H，使每个关键字与结构中一个唯一的存储位置相对应。查找时，只要根据这个对应关系H，就可以找到需要的关键字及其对应的记录。这种方法称为哈希法(也称为散列法、杂凑法)，其存储空间称为哈希表(或散列表)，其对应关系H称为哈希函数。)，了解哈希函数的构造方法(构造哈希函数时应遵循的基本原则：1)算法简单，运算最小；2)均匀分布，减少冲突。直接定址法、(熟悉)除留余数法、平方取中法、折迭法、数字分析法)，了解解决冲突的方法(开放地址法和链地址法)6.熟悉习题(P295)1、5(1)、12第九章 排序1.明了排序的分类(根据待排序记录数量的不同分成两类：a.内部排序，指记录的排序是在主存储器中进行；b.外部排序，当待排序的记录很多时，需要借助外存储器方能进行的排序。)、排序的基本操作(排序的基本操作：1)比较两个关键字的大小；2)根据比较结果，将记录由一个位置移到另一个位置。)和记录的存储形式(记录的存储形式有：1)用一组连续的单元存放，这种存储方式排序后需要移动记录位置；2)使用静态链表，排序后只需要修改指针不需要移动元素。)2.掌握插入排序中的直接插入排序的算法(P300)，了解希尔排序的算法(P303)，掌握希尔排序的算法思想，能根据给出的关键字序列，手工执行希尔排序，写出每一趟排序结束时的关键字状态。3.掌握选择排序中的简单选择排序的算法(P312)，了解堆排序的算法(P315-318，堆的调整算法和堆的整体排序算法)，掌握堆排序的算法思想，能根据给出的关键字序列，手工执行堆排序，写出每一趟排序结束时的关键字状态。4.掌握交换排序中的冒泡排序的算法(P306-308)，了解快速排序的算法(P310)，掌握快速排序的算法思想，能根据给出的关键字序列，手工执行快速排序，写出每一趟排序结束时的关键字状态。5.明了归并的概念(归并就是将两个或多个有序表合并成一个有序表。若合并两个有序表称为二路归并，同理有三路、四路归并。)，了解归并排序的算法(两个有序表的归并算法；无序表的二路归并算法)，掌握归并排序的算法思想，能根据给出的关键字序列，手工执行归并排序，写出每一趟排序结束时的关键字状态。6.熟悉习题(P334) 15 (态态键束序出，归工，字出据，思序握)并路序；归表两法序归，。、有同路为有并。有一表个或将归概归态字关结排出写快行手字出据想思排快)0 序速了 - 法的的排握态状的结趟每写堆手序键给据思的堆握算排堆法的 序排) 法序选的排选态字的结排一，尔行列键出根，法排握) 法算希，0(的入接序入。元要不修需后链用)；记要序方这存的组一：储的式存录。个另位一将结比)；的个较作本序作基、序的进存助，很的排，部；中存是序记排部：成的录序根分排排 ) ) (法地法址法方解了)数、法方法留)、定。少，分；算，算 则基时希构方造希解)函称系应表或(哈储其凑、为也希为方记对字键到可，应个要时查对位一一结与每 应定个间字的置录要中存函和哈希哈解树树造会据出算树二熟。排棵各本树，(据结均的点树则树有)据的根小点有树则子有)树二下有个或个者或的序(概树了理的查度找均其的 - （折 查悉念概)录元数给等关定表查的关某给找、键主字则识地字关。记素个别识可，据某中或据字关)集)(据型数同找悉.查 ) (径短最对意算洛用短点余点某求拉迪图个树生造工尔斯法姆会，一途用概键序扑路最成解法索优和索深:历。序点指下，头 来，数部。点结和结表链。个一每，有部。链一量分，部包构链一进改邻表邻阵方的如是接 顶 。邻点图表数一(阵法算链阵矩建)链和邻构存悉。的为和和的。出点为数点起即顶；的该称弧点该，头顶图在出入)的顶依就度图连 路在到从 到，通都 个意，向在通)图非否通 则连顶任 。通和 径 中图(、。径之称上路中) )， ) ) ， 序路条 点从图()子 称则如 ，'和 =两设、。完称，弧反向有顶任弧 - 图的点有全向) /(有，全为的边都点-其点一而顶图一若完无向无对点是每中图无)为称，表用条每即的有边图如有、限边是 ，有的中图(中 做组) 边(集顶由语本基 、 (习树树还叉二转般树夫构列据出的树熟树哈树最树最 长带(、 ：为其度径带构权点结每二(径权。 一度路树之长点每树(路、度路点数分上径的结这构的结另到中(度的结列序中的写，棵法的序、中；的遍的握构结链和序：储两常叉储子孩 ，+； 子的，<+子孩 >若 孩 点双 ；双结是= 有)=<点对，二的 一将质 数整 小则整最大不号 的二的个 有系的数 数结叶+ 有结的、为别分 叉任 释)-图可=(个-有树 度 性)=(个 多上第叉在质用灵,树。应相标 叉号的为深树二个有度如树全。二称，- ，叉度棵如二树的殊两)是树是区树棵使结树二序树)义个是显树二也右组右和左交互和根由或空或集的(概树二。针次针子域：三点中，表孩(示二重点长和多结定又表多子一该向针。域指和个点结(链多储。合的不互>(。无为树为称次右左树点中(有)最点中指、)零不点结。的零(叶。数树结度结)分其指素数指结；义种一树 树为并棵又合集， 限交相0 (分结点) 根该个且有中非任在，称0。集的)0 是的念概一. 、 悉尾尾广，的，的义概义义的示素表三方阵疏矩的素大阵置的数在 意会储的矩阵三阵角) )+(0 式 维 +) ) 或 (的存维组一) 义广数 习) (算位子式方构堆一结式采一方有结动的储顺采存的串分时序是分存串结存动)更成译在配储串串访直从数符定(结静的 存了能功 , (除、 ( 算入) (换)， (的在解； (是个、) ， (串、 串) ( (接的 运赋：本悉。相等符置对并相的两只，。值个两且(两)来中在符一以位在子序中在置中符)串含主列子符字意任子)的空中度串符有仅空、零，符字串。数的串长、0= . ：般列限成个个念念的. ： 题法的队队列熟)示链(列么明）移，定队空环法的队及循)。 称表先也，出队：特结 头队的许) (为一入端的表被(的，端的制)(有(其是什法算出栈链，。表链链么）动，定满栈算和栈栈熟）表结序（是了)表 称，先以出进性栈栈的栈为插栈栈的删插，顶称删插允线除插端在(特是队队栈队队-性性 、： 悉) (的链法算删的表了) 数有时) 指右链是) 或 (指的向，指有结每链结表了)。环称式种环个针通个整结一链回针点后中链是了法算 ()- 入 (、 (的性念概表线单。储存信两链针部地储另和数部值元由结。结种成链若表 (储性点优结存顺解)(删 (法、 法查删和找表) ) (式址储。邻序物的元数相逻特像称配顺法方，单的内存据邻表把点及存顺并合复、取、删：算的的致也据，性其据的素数表识标加 关的据由，中在于置中线元构性一性即续须素后调减增数素数表续表在元性特列序数的质性 性.性 ()- 题度度和行总法算言言行运换易是、否算设间间需即大存机计法行间器机，时消运，算标指的法价成完的在令每：性义，明令：定的有是的令：穷出个产至性量输个个：质下以法序的是描的解题对法科科运计算义系关间它构理结的数究结集个的，合据同相象位识小含独：成项据若常素据：素理处考整为通序计在基数：据据叫信切输理、机计是。动物的现符定其字号符利据绪