《数据结构导论考点知识总结》由会员分享，可在线阅读，更多相关《数据结构导论考点知识总结（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构导论考点知识总结第_章概论 1、程序设计的实质是数据表示和数据处理。2、数据表示：将是数据从机外表示转向机内表示。3、数据处理：有适当的可执行语句编制程序，以便让计算机去执行对 数据的机内表示的各种操作，从而实现处理要求，得到所需的结果的工 作。4、凡是被计算机存储加工的对象通常称为数据。5、数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑 和处理。数据元素通常是数据项组成的。6、由-、数据的二I层次：数据项-数据元素-数据 7、逻辑关系：是指数据元素之间的关联方式或称“邻接关系”。8、数据元素之间逻辑关系的整体称为逻辑结构。9、数据的四类基本组成形式：集合中任何两个结点之间
2、都没有逻辑 关系，组成形式松散。线性结构中结点按逻辑关系一次排列形成一条 “锁链”。树形结构具有分支、层次特性，其形态有点像自然界中的 树。图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两 个结点都可以邻接。10、运算分成一下两种类型：1、加工型运算 如：删除、更新2、引 用型运算如：查找、读取、插入 11、四种基本存储方式：顺序存储方式（每个存储结点只含有一个数据 元素。按这种表示方式表示逻辑关系的存储结构叫顺序存储结构）、链 式存储方式（每个存储结点不仅含有一个数据元素，还包含已组指针。）、 觐存储方式（每个存储结点只含一个数据元素，所有存储结点连续存 放。按这种方式组织起来的存储
3、结构称为索引存储结构式、散列存储方 式（每个结点含有一个数据元素，各个结点均匀分布在存储区里，用散 列函数指示各结点的存储位置或位置区间端点。相应的存储结构称为散 列存储结构）。12、算法可分为以下三类：1、运行终止的程序可执行部分。2、伪语言 算法。3、非形式算法。13、评价算法的质量：正确性易读性健壮性高效性14、以算法在所有输入下的计算量的最大值作为算法的计算量，这种计 算量称为算法的最坏时间复杂性或最坏时间复杂度。15、以算法在所有输入下的计算量的加权平均值作为算法的计算量，这 种计算量称为算法的平均时间复杂性或者平均时间复杂度。16、最坏时间复杂性和平均时间复杂性通称时间复杂性（或时
4、间复杂度） 时间复杂性量级为O（n3）。17、算法的输入规模或问题的规模是指作为该算法输入的数据所含的数 据元素的数目，或与数目有关的其他参数。18、具有指数阶量级的算法是实现不可计算的，而量级低于平方阶的算 法是高效率的。19、数据结构的基本任务可以概括为数据结构的设计和实现。第二章线性表1、线性结构是n（n=0）个结点的有穷序列。2、每个结点至多只有一个之间前趋和一个直接后趋，在线性结构中这 种关系是1对1的。3、线性表的逻辑结构是线性结构。所含结点的个数称为线性表的长度 (简称表长)。表长为0的线性表为空表。4、顺序表是线性表的顺序存储结构，即按顺序存储方式构造的线性表 的存储结构。淤5
5、、第i个结点a.的存储地址为b+ (i1)XL(L为内存所占单元1/表长。6是顺序表的第一个存储结点的第一个单元的内存地址。)6、线性表采用链式存储结构时，要求内存中可用存储单元的地址连不连续都可以。7、求表长和读表元算法的时间复杂性为0(1)，从量级上来说已经达到最低水平即最高效率。8、顺序表要求占用连续的空间，为克服顺序表的这一缺点，可采用链接方式来存储线性表，通常我们将链接方式存储的线性表称为链表。9、线性表的常见链式存储结构有单链表、循环表和双链表，最简单的是单链表。10、插入算法的算法表示：P2 7Void insert_lklist(lklist head,datatype x,i
6、nt i)P=find_likist(head,i-1);If(p= =NULL)Error( 不存在第i个位置)ElseS=malloc(size);s-data=x;s-next=p-next;p-next=s;11、定位运算在顺序表和单链表上的实现算法的时间复杂性是同量级的，均为O(n)。12、线性表的结点是可以是任意的数据元素，当然也可以是字符。以字 符为数据元素、以线性结构为逻辑结构的的数据称为字符串。13、串是由零个或多个字符组成的有穷序列。含零个字符的串称为空串， 用0表示。14、常见的存储结构有顺序存储、链式存储和索引存储。在这里只讨论 前两种。第三章栈、队列和数组1、队列也可
7、以看成是一种运算受限的线性表，在这种线性表中允许插 入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出线 性表。2、队满的条件为：(队尾指针+1 ) %长度=队内指针 如：(sq.rear+1) %maxsize) = =sq.front队空的条件为：sq.rear=sq.front3、一个三维数组可以看成是数据元素为二维数组的线性表。一个n维 数组可视为其数据元素为n-1维的线性表。4、通常采用顺序存储结构来存放数组。5、在有的高级语言像C语言的编译器中，数组用的是以行为主序大的 存储方法，而有的高级语言像FORTRRAN语言，用的是以列为主序的存 储方法。淤6、二维数组中任意元素
8、的存储位置计算公式：loci,j=loc0,0 + n Xi+j Xk “n”可表示每行或没列的元素个数“i”表示行号或列号 “j”表示列号或行号“k”表示每个元素的占的字节数。(注：按行为 主序时用i为行号，j为列号，按列为主序时反之。)7、为节省空间矩阵采用压缩存储。第四章树1、二叉树通常有两类存储结构：顺序存储结构和链式存储结构。淤2、二叉树的性质:性质1：二叉树第i (iNl)层上之多有2i-i个结 点。性质二：深度为k (kN1)的二叉树至多有2k-1个结点。性质三：对任何二叉树，若2度结点数为n2,则叶子数n=n2+1。有两 种特殊情况：满二叉树：深度为k (kN1)且有2k-1个
9、结点。完全 二叉树：在一棵深度为k (kN1)的满二叉树上删去第k层上最右边的 连续j (0Wj1，则x 是双亲PARENT (X)的编号为|_i/2_|.若2i n，则结点无左孩子 (且无有孩子)，否则，x的左孩子LCHILD (X)的编号为2i。若2i+1 n，则结点X无右孩子；否则，X的右孩子RCHILD (X)的编号为2i+1。3、二叉树的存储结构:顺序存储结构和链式存储结构。4、二叉树链式存储结构类型定义：Typedef struct btnode * bitreptr ；Struct btnode datatype data；Bitreptr lchild,rchild；bitre
10、ptr poot；5、具有n个结点的二叉树中有2n个指针域，其中有n-1个用来指向结 点的左右孩子，其余的n+1个指针域为NULL。6、求二叉树的叶子数：算法如下Void countleaf(bitreptr t,int*count)if(t!=NULL)if(t-lchild= =NULL)&(t-rchild= =NULL)*count + +；countleaf(1-lchild,count)；countleaf(1-lchild,count)；7、树的三种常用存储结构是：孩子链表表示法、孩子兄弟链表表示法、 双亲表示法。8、树转化成二叉树以后右子树为空。淤9、树与森与二叉树之间的转换方
11、法：森林-二叉树。先将森林中的每棵树转换为二叉树，然后将各二叉树的根视为兄弟从左到右连子一 起，最后以原第一棵二叉树的根结点为基准旋转45。树一二叉树。 首先在所有兄弟结点间加一连线，然后对每个结点除保留与长子的连线 外，去掉该结点与其他孩子的连线，最后以根结点为基准旋转45 . 二叉树f树同二叉树一森林。首先将左孩子的所有右孩子与双亲相 连，然后去掉所有双亲到右孩子的连线。第五章图淤1、一个具有n个顶点的完全无向图的边数为C2jn （n-1） /2。一个 具有n个顶点的有向完全图的弧度数为P2n=n （n-1）。2、序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最 后一个顶点外，其
12、余顶点不重复的回路，称为简单回路或简单环。3、一个连通图的生成树，是含有该连通图的全部顶点的一个极小联通 子图。若连通图G的顶点个数为n，则G的生成树的边数为n-1。4、用来介绍图的两种主要存储结构是:邻接矩阵和邻接表。5、若一个无向图有n个顶点，e条边，则它的邻接表需n个头结点和 2e个表结点。在边稀疏的情况下，用邻接表表示比用邻接矩阵节省存储 空间。6、遍历图的基本方法有：深度优先搜索（DFS）和广度优先搜索（BFS）。7、任何一个无环有向图，其全部顶点可以排成一个拓扑序列。第六章查找表1、三种基本逻辑结构：线性结构、树形结构和图状结构。在集合这种_ 逻辑结构中，任何结点之间都不存在逻辑关
13、系。2、顺序查找算法的平均查找长度为：ASL=n+1/2 （n表示第n个元素）s淤3、二分查找的时间复杂度为：O （蛔2n）4、二分查找的时间性能比顺序查找好，但二分查找要求以有序表作为 存储表示。5、索引顺序表上的查找分为两个阶段：确定待查元素所在的块。 在块内查找待查的元素。第二阶段只能采用顺序查找法而第一阶段既可 采用顺序查找法，也可采用二分查找法。上述查找称为索引顺序表的分 块查找。6、中根遍历一棵二叉排序树所得的结点访问序列的键值是递增序列。7、平衡二叉排序树上任一结点的平衡因子只可能是-1、0或1。有一个 平衡因子不是-1、0或1，则此二叉排序树不是平衡的。8、“散列”既是一种存储
14、方式，又是一种查找方法，称散列查找。9、散列函数的构造法：数字分析法、除余法、平方取中法、基数转换 法、随机数法。10、构造后继散列地址序列的方法也是处理冲突的方法。构造散列地址 序列的方法是：线性探测法、二次探测法、多重散列法、公共溢出区法。11、开散列表利用链接方法（建立公共溢出区）存储同义词，不产生堆 积现象。第七章文件 1、记录作为文件的基本存取单位。2、文件的检索有三种方式：顺序存取、直接存取、按关键字存取。3、与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应顺序 存储，又适应随机存储。4、文件在外存储器上的组织结构有：顺序文件、散列文件、索引文件。5、顺序文件是文件的一种常见组成形式：其特点是：在顺序文件中， 所有逻辑记录在存储介质中的实际顺序与他们进入存储器的顺序一致。顺序文件适宜于顺序存取和成批处理。6、索引项是按关键字值（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件；否则称为索引非顺序文件。7、索引顺序存取方法型M是一种专为磁盘存取设计的索引顺序文件组 织方式。8、VSAM是虚拟存储存取方法的缩写，它是一种索引顺序文件的组织方 式，采用动态索引结构。VSAM文件结构由三部分组成：索引集、顺序集 和数据集。9、散列文件的优点;具有随机存放、记录不需进行排序、插入删
