《数据结构C语言耿国华》复习计划大纲

?数据结构C语言耿国华版?复习方案纲领?数据结构C语言耿国华版?复习方案纲领?数据结构C语言耿国华版?复习方案纲领.第一章绪论数据：人们利用文字符号、数字符号及其余规定的符号对现实世界的事物及其活动的描绘。凡是能被计算机输入、储蓄、办理和输出的全部信息都叫数据。数据元素：数据的根本单位，在计算机程序中平常作为一个整体进行考虑和办理。数据元素的构成：一个数据元素平常由一个或假定干数据项构成。数据项：指拥有独立含义的最小表记单位。数据对象：性质同样的数据元素的会合，是数据的一个子集。数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的互相关系和所定义的算法在计算机上运转的学科。算法：是对待定问题求解步骤的一种描绘，是指令的有限序列。算法应知足以下性质：1)输入性：拥有零个或假定干个输入量；2)输出性：最少产生一个输出；有穷性：每条指令的履行次数是有限的；确立性：每条指令的含义明确，无二义性；可行性：每条指令都应在有限的时间内达成。6.谈论算法利害的主要指标：履行算法后，计算机运转所耗费的时间，即所需的机器时间；履行算法时，计算机所占储蓄量的大小，即所需的储蓄空间；所设计的算法能否易读、易懂，能否简单变换成其余可运转的程序语言。7.会预计某一算法的总履行时间和时间复杂度。8.熟习习题P32:3(5)-(9)、4(2)(3)第二章线性表线性表(P7)：是性质同样的一组数据元素序列。线性表的特色：数据元素在线性表中是连续的，表中数据元素的个数能够增添或减少，但调整后数据元素仍必然是连续的，即线性表是一种线性结构。数据元素在线性表中的地点仅取决于自己在表中的序号，并由该元素数据项中的重点字(key)加以表记。线性表中全部数据元素的同一数据项，其属性是同样的，数据种类也是一致的。线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。线性表的序次储蓄结构及特色(就是把表中相邻的数据元素寄存在内存毗邻的储蓄单元，这类储蓄方法叫做序次分派，又称序次映像。其特色：逻辑上相邻的数据元素，它们的物理序次也是相邻的。)，储蓄地点的计算方式(Loc(ai)=Loc(a0)+i*s)。线性表的查找、插入和删除熟习线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。理解线性表的序次储蓄结构的优弊端。熟习线性链表的储蓄结构(P43)线性链表(由假定干结点链接而成的一种储蓄结构。)、结点(由寄存数据元素值的局部—数据域和寄存另一元素储蓄地点的局部—指针域或链域两局部信息构成的储蓄结构。)、单链表(线性链表)的见解。熟习线性链表的成立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法；了然什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表经过链指针成为一个环形，这类形式的链表称为循环链表。)？了然双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；认识双向链表的插入和删除的算法。理解链表的优弊端(P48)。熟习习题P68：1、2第三章限制性线性表----栈和行列栈和行列明确什么是栈及其特色(只赞成在一端进行插入和删除的线性表。赞成插入和删除’..的一端称，不允插入和除的一端称底。的插入，称的除出。的特色：后先出，因此又称后先出表，称LIFO表。)。了然什么是序〔用序存构表示的〕，熟习序算法和出算法〔空，判断条件，指移〕。了然什么是(用表表示的。)，熟习(；出)的算法。明确什么是列及其特色(全部的插入( )均限制在表的一端行，全部的除(出)被限制在表的另一端。允插入的一端称尾(rear)，允除的一端称(front)。列构特色：先的元素先出，故也称先先出表，称FIFO表。)。认识循列及其和出的算法〔循列空判断条件，指移〕。了然什么是列(采纳表表示列。)？熟习列(、出)的算法。熟习P102：1、3、12第四章串掌握串的根本见解：串(是由零个或多个字符成的有限序列。一般：s=""(n>=0)。)、串的度(串中字符的数目n。)、空串(零个字符的串，其度零。)、空格串(含有空格字符的串，它的度串中空格符的个数。)、子串(串中随意个的字符成的子序列)、主串(包括子串的串)、字符在串中的地点(字符在序列中的序号)、子串在主串的地点(以子串第一个字符在主串中的地点来表示)、两个串相等(当且当两个串的相等。也就是，只有当两个串的度相等，而且各地点的字符都相等才相等。)熟习串的根本运算：串的运算(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))的功能。了然串的存构(P81)：串的静存构(是将串定成字符型数，从串名可直接到串，串的存空分派是在达成的，不可以够改正)、串的存构〔是串的存空分派是在程序运转分派的〕；串的静存构采纳序存构；串的存构有两种方式：一种是采纳式存构，另一种是堆构的存方式。熟习子串定位函数的算法(P112)。熟习(P119)1。第五章数和广表数(P125)：一数、二数存地点的算(一P125公式，或Loc(ai)=Loc(a0)+i*s；二P125公式，或Loc(aij)=Loc(a00)+(i*n+j)*s)。2.上三角矩、下三角矩、状矩的存，会求随意元素aij在一数中的地点。罕见矩：指全局部元素零的矩。罕见矩的表示方法—三元表中各元素所表示的意。认识广表的见解，广表的度，广表的表，广表的表尾。熟习(P145)1、3、9。第六章掌握一般的见解：一般的定(是n(n>=0)个点的有限会合。当n=0称空，否，在任一棵非空中：①有一个且有一个称根(Root)的点；②其余点可分m(m>=0)个互不订交的有限会合T1，T2，⋯，Tm，且每个会合自己又是一棵，并称之根的子(Subtree)。的定是一种定)；的点(指一个数据元素及假定干指向其子的分支。)、点的度(指点有子的数目。)、叶子点(指度零的点。)、分支点(指度不零的点。)、的度(指中各点度的最大。)、有序(将中点的各子看作从左到右是有序次的，称有序，否称无序。)、丛林(m(m>=0)棵互不订交的的会合。)的存构：多重表表示法(每个点由一个数据域和假定干指域成。每个指域将指向点的一个孩子。)，多重表又分：定点的多重表和不定点的多重表；二重表示法(即孩子兄弟表示法，中每个点置三个域：数据’..域、子指域和次弟指域。)掌握二叉的见解二叉(点的有限会合，它或许是空集，或许由一个根点和两个互不订交的根的左子和右子成，左右子也是一棵二叉，然也是一个定。)；二叉是有序的(二叉中的点即便只有一棵子，也要划分它是左子是右子)；两种特别形的二叉：二叉(假如一棵深度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的点数的关系)2。注符号表示不大于性4拥有n个点的完满二叉的深度n+1xx的最大整数，x表示不小于x的最小整数)log(性5假如将一棵有n个点的完满二叉，任一点(1<=i<=n)有：1)假定i=1，i是根点无双；假定i>1，i的双点是i/2。假定2i<=n，i的左孩子是2i；假定2i>n，i无左孩子。假定2i+1<=n，i的右孩子是2i+1；假定2i+1>n，i无右孩子。认识二叉的存：二叉平常有两存构：序存构和式存构。3.掌握二叉的先序遍的算法；认识中序遍、后序遍的算法。出一棵，会写出的先序中序后序序列。了然点的路径度(从中一个点到另一个点之的分支构成两个点之的路径，路径上的分支个数即是点的路径度)、的路径度(从根到每一个点的路径度之和称的路径度，一般作pl。)、路径度(假定n二叉的每个端点以，进而构成的路径度。其算方法：wpl=wili)、哈夫曼(路径度wpl最小的称做最二叉或哈夫曼)；熟习哈夫曼i1的算法，出数据序列，会结构哈夫曼。认识一般化二叉和二叉原一般。熟习(P194)2、3、4、7、9、11第七章熟习的根本：(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')，假如V’V且E’E，称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是通。)、度(就是依赖于点的数。)、入度和出度(在有向中，以某点，即止于点的弧的数目称点的入度；以某点尾，即初步点的弧的数目称点的出度。点的入度和出度之和称点的度。)熟习的存构(接矩和接表)，认识成立接矩或接表的算法：接矩(是用一个二数来表示中点的有关系。G={V,E}有n≥1个1,假定(Vi,Vj)或Vi,VjE(G)cost[i][j]=，反之)、接表(由接矩改而来的一种0’.握希尔排序的算法思想，能依据给出的重点字序列，序结束时的重点字状态。.链接结构，它包括两个局部，一局部是向量，另一局部是链表。链表局部共有n个链表，即每个极点一个链表。每个链表由一个表头结点和假定干个表结点构成。向量局部为一个数组，用来储蓄n个表头结点，向量的下标指示了极点的序号。)熟习遍历图的算法:深度优先搜寻法和广度优先搜寻法。认识最小生成树、最短路径、拓扑排序和重点路径的见解和用途。给出一个无向图，会用普利姆算法和克鲁斯卡尔算法手工结构最小生成树。给出一个有向图，会用迪杰斯特拉算法求某一极点到其余各极点的最短路径，用弗洛伊德算法求随意一对极点间的最短路径。熟习习题(P244)1、4、14、15第八章查找熟习查找表(由同一数据种类的数据元素(或记录)构成的会合。)、重点字(数据元素(或记录)中某个数据项的值，用它可表记(鉴识)一个数据元素(或记录)。假定此重点字能够独一地表记，那么称此重点字为主重点字。)、查找(依据给定的某个重点字的值，在查找表中确立一个其重点字等于给定值的数据元素(或记录)。)的见解。熟习序次查找〔P249〕、折半查找〔P250-251〕的算法，及其均匀查找长度。认识分块查找的原理。了然二叉排序树的见解(二叉排序树的定义：它或许是一个空树，或许是一个拥有以下性质的二叉树：(1)假定它有左子树，那么左子树上有全部结点的数据均小于根结点的数据；(2)假定它有右子树，那么右子树上全部结点的数据均大于根结点的数据；(3)左，右子树自己又各是一棵二叉树排序树。)；熟习二叉排序树的算法，给出数据序列，会结构二叉排序树。认识什么是哈希法、哈希表和哈希函数(存取过程中需要在记录储蓄地点和它的重点字之间成立一个确立的对应关系H，使每个重点字与结构中一个独一的储蓄地点相对应。查找时，只需依据这个对应关系H，就能够找到需要的重点字及其对应的记录。这类方法称为哈希法(也称为散列法、杂凑法)，其储蓄空间称为哈希表(或散列表)，其对应关系H称为哈希函数。)，认识哈希函数的结构方法(结构哈希函数时应依据的根本源那么：1)算法简单，运算最小；2)均匀散布，减少矛盾。直接定址法、(熟习)除留余数法、平方取中法、折迭法、数字分析法)，认识解决矛盾的方法(开放地点法和链地点法)6.熟习习题(P295)1、5(1)、12第九章排序了然排序的分类(依据待排序记录数目的不同样分红两类：a.内部排序，指记录的排序是在主储蓄器中进行；b.外面排序，当待排序的记录好多时，需要借助外储蓄器方能进行的排序。)、排序的根本操作(排序的根本操作：1)比较两个重点字的大小；2)依据比较结果，将记录由一个地点移到另一个地点。)和记录的储蓄形式(记录的储蓄形式有：1)用一组连续的单元寄存，这类储蓄方式排序后需要挪动记录地点；2)使用静态链表，排序后只需要改正指针不需要挪动元素。)掌握插入排序中的直接插入排序的算法(P300)，认识希尔排序的算法(P303)，掌手工履行希尔排序，写出每一趟排掌握选择排序中的简单项选择择排序的算法(P312)，认识堆排序的算法(P315-318，堆的调整算法和堆的整体排序算法)，掌握堆