数据结构导论考点知识总结

1、数据结构导论考点知识总结第一章概论 1、程序设计的实质是数据表示和数据处理。2、数据表示：将是数据从机外表示转向机内表示。3、数据处理：有适当的可执行语句编制程序，以便让计算机去执行对 数据的机内表示的各种操作，从而实现处理要求，得到所需的结果的工 作。4、凡是被计算机存储加工的对象通常称为数据 5、数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑 和处理。数据元素通常是数据项组成的。6、数据的三个层次：数据项-数据元素-数据 7、逻辑关系：是指数据元素之间的关联方式或称“邻接关系” 8数据元素之间逻辑关系的整体称为逻辑结构。9、数据的四类基本组成形式：集合中任何两个结点之间都没有逻

2、辑 关系，组成形式松散。线性结构中结点按逻辑关系一次排列形成一条“锁链”。树形结构具有分支、层次特性，其形态有点像自然界中的 树。图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两 个结点都可以邻接。2、引、链10、运算分成一下两种类型：1、加工型运算 女口：删除、更新 用型运算 女口：查找、读取、插入 11、四种基本存储方式：顺序存储方式（每个存储结点只含有一个数据 元素。按这种表示方式表示逻辑关系的存储结构叫顺序存储结构）式存储方式（每个存储结点不仅含有一个数据元素，还包含已组指针。）、索引存储方K每个存储结点只含一个数据元素，所有存储结点连续存放。按这种方式组织起来的存储结构称为索

3、引存储结构。）、散列存储方 式（每个结点含有一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各结点的存储位置或位置区间端点。相应的存储结构称为散 列存储结构）。12、算法可分为以下三类：1、运行终止的程序可执行部分。2、伪语言 算法。3、非形式算法。13、评价算法的质量：正确性易读性健壮性高效性 14、以算法在所有输入下的计算量的最大值作为算法的计算量，这种计 算量称为算法的最坏时间复杂性或最坏时间复杂度。15、以算法在所有输入下的计算量的加权平均值作为算法的计算量，这 种计算量称为算法的平均时间复杂性或者平均时间复杂度16、最坏时间复杂性和平均时间复杂性通称时间复杂性（或时间复杂度）

4、 时间复杂性量级为0 （n3）。17、算法的输入规模或问题的规模是指作为该算法输入的数据所含的数 据元素的数目，或与数目有关的其他参数。18、具有指数阶量级的算法是实现不可计算的，而量级低于平方阶的算 法是高效率的。佃、数据结构的基本任务可以概括为数据结构的设计和实现。第二章线性表 1、线性结构是n（n=0）个结点的有穷序列。2、每个结点至多只有一个之间前趋和一个直接后趋，在线性结构中这 种关系是1对1的。3、线性表的逻辑结构是线性结构。所含结点的个数称为线性表的长度(简称表长)。表长为0的线性表为空表。4、顺序表是线性表的顺序存储结构，即按顺序存储方式构造的线性表 的存储结构。厶、第i个结点

5、ai的存储地址为b+ (i - 1)x L ( L为内存所占单元/表长。b是顺序表的第一个存储结点的第一个单元的内存地址。)6、线性表采用链式存储结构时，要求内存中可用存储单元的地址连不连续都可以。7、求表长和读表元算法的时间复杂性为0( 1)，从量级上来说已经达到最低水平即最高效率。8顺序表要求占用连续的空间，为克服顺序表的这一缺点，可采用链接方式来存储线性表，通常我们将链接方式存储的线性表称为链表。9、线性表的常见链式存储结构有单链表、循环表和双链表，最简单的是单链表。10、插入算法的算法表示：P27Void in sert_lklist(lklist head,datat ype x,i

6、 nt i)P=fin d_likist(head,i-1);lf(p= =NULL)Error(不存在第i个位置)ElseS=malloc(size);s-data=x;s-n ext=p-next;p-n ext=s;11、定位运算在顺序表和单链表上的实现算法的时间复杂性是同量级的，均为0 (n)。12、线性表的结点是可以是任意的数据元素，当然也可以是字符。以字符为数据元素、以线性结构为逻辑结构的的数据称为字符串。13、串是由零个或多个字符组成的有穷序列。含零个字符的串称为空串， 用？表示。14、常见的存储结构有顺序存储、链式存储和索引存储。在这里只讨论前两种。第三章栈、队列和数组1、队列

7、也可以看成是一种运算受限的线性表，在这种线性表中允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出线 性表。2、队满的条件为：(队尾指针+1)%长度=队内指针 女口：(sq.rear+1 ) %maxsize) = =sq.front队空的条件为：sq.rear= =sq.fr ont 3、一个三维数组可以看成是数据元素为二维数组的线性表。一个数组可视为其数据元素为 n-1维的线性表。4、通常采用顺序存储结构来存放数组。5、在有的高级语言像 C语言的编译器中，数组用的是以行为主序大的存储方法，而有的高级语言像FORTRRA语言，用的是以列为主序的存储方法。探6、二维数组中任意元

8、素的存储位置计算公式：loci,j=loc0,0+n“i ”表示行号或列号X i+j X k “ n”可表示每行或没列的元素个数“j ”表示列号或行号 “ k”表示每个元素的占的字节数。(注：按行为主序时用i为行号，j为列号，按列为主序时反之。)号,7、为节省空间矩阵米用压缩存储。1、第四章树叉树通常有两类存储结构：顺序存储结构和链式存储结构。探2、二叉树的性质：性质 1： 二叉树第i ( i 1)层上之多有2i-1个结点。性质二：深度为k (k 1)的二叉树至多有2k-1个结点。性质三：对任何二叉树，若 2度结点数为n2,贝y叶子数n0=n2+1。有两种特殊情况：满二叉树：深度为 k ( k

9、 1)且有2k-1个结点。完全二叉树：在一棵深度为 k (k 1)的满二叉树上删去第 k层上最右边的连续j (OWj V 2k-1)个结点，就得到一棵深度为k的完全二叉树。性质四：具有n个结点的完全二叉树的深度为|_log 2n+1.其中“ L”表示向下取整，例如：3.8向下取整得3，反之向上取整得4. 性质五：(完全二叉树某结点的双亲结点或孩子结点的编号之间 的关系)如果将一棵有n个结点的完全二叉树按层编号，则对任一编号 为i ( K i w n)的结点x有：若i=1，则结点x是根；若i 1,则x是双亲PAREN(X)的编号为|_ i/2. 若2i n,则结点无左孩子(且无有孩子),否则，x

10、的左孩子LCHILD(X)的编号为2i。若2i+1 n,则结点X无右孩子；否则，X的右孩子RCHILD(X)的编号为2i+1。3、叉树的存储结构：顺序存储结构和链式存储结构。4、叉树链式存储结构类型定义:Typ edef struct btnode * bitre ptrStruct btnode datat ype dataBitre ptr lchild,rchild bitre ptr poot 5、具有n个结点的二叉树中有2n个指针域，其中有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。6、求二叉树的叶子数：算法如下Void coun tleaf(bitre ptr

11、t,i nt*co unt) if(t!=NULL)if(t-lchild= =NULL)&(t-rchild= =NULL)*co unt + + coun tleaf(1-lchild,co unt) coun tleaf(1-lchild,co unt)7、树的三种常用存储结构是：孩子链表表示法、孩子兄弟链表表示法、双亲表示法。8树转化成二叉树以后右子树为空。探9、树与森与二叉树之间的转换方法：森林f二叉树。先将森林中的每棵树转换为二叉树，然后将各二叉树的根视为兄弟从左到右连子起，最后以原第一棵二叉树的根结点为基准旋转45。 树f二叉树。45 .首先在所有兄弟结点间加一连线，然后对每个结

12、点除保留与长子的连线 外，去掉该结点与其他孩子的连线，最后以根结点为基准旋转 二叉树f树 同 二叉树f森林。首先将左孩子的所有右孩子与双亲相 连，然后去掉所有双亲到右孩子的连线。第五章图探1、一个具有n个顶点的完全无向图的边数为C2n=n (n-1 ) /2。一个具有n个顶点的有向完全图的弧度数为P2n=n (n-1 )。2、序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为简单回路或简单环。3、一个连通图的生成树，是含有该连通图的全部顶点的一个极小联通子图。若连通图G的顶点个数为n,则G的生成树的边数为n-1。4、用来介绍图的两种主要存储结构是

13、：邻接矩阵和邻接表。5、若一个无向图有n个顶点，e条边，则它的邻接表需 n个头结点和 2e个表结点。在边稀疏的情况下，用邻接表表示比用邻接矩阵节省存储空间。6、遍历图的基本方法有：深度优先搜索(DFS和广度优先搜索(BFS。7、任何一个无环有向图，其全部顶点可以排成一个拓扑序列。第六章查找表1、三种基本逻辑结构：线性结构、树形结构和图状结构。在集合这种逻辑结构中，任何结点之间都不存在逻辑关系。2、顺序查找算法的平均查找长度为：ASL= n+1/2 (n表示第n个元素)探3、二分查找的时间复杂度为：O(log 2n)4、分查找的时间性能比顺序查找好，但二分查找要求以有序表作为存储表示。5、索引顺

14、序表上的查找分为两个阶段：确定待查元素所在的块。在块内查找待查的元素。第二阶段只能采用顺序查找法而第一阶段既可采用顺序查找法，也可采用二分查找法。上述查找称为索引顺序表的分块查找。6、中根遍历一棵二叉排序树所得的结点访问序列的键值是递增序列。7、平衡二叉排序树上任一结点的平衡因子只可能是-1、0或1。有一个平衡因子不是-1、0或1，则此二叉排序树不是平衡的。8 “散列”既是一种存储方式，又是一种查找方法，称散列查找。9、散列函数的构造法：数字分析法、除余法、平方取中法、基数转换法、随机数法。10、构造后继散列地址序列的方法也是处理冲突的方法。构造散列地址序列的方法是：线性探测法、二次探测法、多

15、重散列法、公共溢出区法。是：11、开散列表利用链接方法(建立公共溢出区)存储同义词，不产生堆积现象。第七章文件1、记录作为文件的基本存取单位。2、文件的检索有二种方式：顺序存取、直接存取、按关键字存取。3、与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应顺序存储，又适应随机存储。4、文件在外存储器上的组织结构有：顺序文件、散列文件、索引文件。5、顺序文件是文件的一种常见组成形式：其特点是：在顺序文件中，所有逻辑记录在存储介质中的实际顺序与他们进入存储器的顺序一致。顺序文件适宜于顺序存取和成批处理。6、索引项是按关键字值（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺

16、序文件；否则称为索引非顺序文件。7、索引顺序存取方法ISAM是一种专为磁盘存取设计的索引顺序文件组织方式。8 VSAM是虚拟存储存取方法的缩写，它是一种索引顺序文件的组织方式，采用动态索引结构。VSAM文件结构由三部分组成：索引集、顺序集 和数据集。9、散列文件的优点；具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。10、多关键字文件时指同时对主关键字和次关键字两部分建立索引的文件组织形式。第八章排序1、内部排序主要有：插入排序、交换排序、选择排序、归并排序等。探2、排序要求掌握各种排序方法的同时记住以下这张表:内排序方法的性能比较排序方法最好时间复杂度平均时间复