全数据结构知识点考点全总结.docx

《全数据结构知识点考点全总结.docx》由会员分享，可在线阅读，更多相关《全数据结构知识点考点全总结.docx（55页珍藏版）》请在第一文库网上搜索。

1、数据结构知识点考点全总结第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。数据结构的定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。线性结构：一对关系。线性结构：多对多关系。 存储结构：是逻辑结构用计算机语言的实现。顺序存储结构：如数组。 链式存储结构：如链表。 索引存储结构：稠密索引：每个结点都有索引项。 稀疏索引：每组结点都有索引项。 散列存储结构：如散列表。数据运算。对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 常用的有：检索、插入、删除、更新、排序。数据类型：是一

2、个值的集合以及在这些值上定义的一组操作的总称。 结构类型：由用户借助于描述机制定义，是导出类型。抽象数据类型ADT:是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：算法是正确的； 执行算法的时间；执行算法的存储空间（主要是辅助存储空间）；算法易于理解、编码、调试。时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。渐近时间复杂度：是指当问题规模趋向无

3、穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(og2n)、线性阶0()、线性对数阶0(n1og2n)、平方阶0(n2)、立方阶。(3)k次方阶0(nk)、指数阶。(2n)o空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。算法的时间复杂度和空间复杂度合称算法复杂度。第二章线性表线性表是由n0个数据元素组成的有限序列。n=0是空表年空表,只能有一个开始结点,有且只能有一个终端结点。线性表上定义的基本运算:

4、构造空表：Init1ist(1) 求表长:1ist1ength(1) 取结点：GetNode(1J) 查找:1ocateNode(1,x) 插入:Insert1ist(1,xzi),删除:De1ete(1J)顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：1OCa(i)=1OCa(1)+(i-1)*d;(首地址为1)在J顺序表中实现的基本运算： 插入：平均移动结点次数为n/2;平均时间复杂度均为O(n)o删除：平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)o线性表的链式存储结构中结点的逻

5、辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。单链表运算：建立单链表头插法：s-next=head;head=s;生成的顺序与输入顺序相反。平均时间复杂度均为。(n)。尾才由法head=rear=nu11Mhead=nu11)head=s;e1ser-next=s;r=s;平均时间复杂度均为O(n) 加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。 查找按序号：与查找位置有关，平均时间复杂度均为O(n)o 按值：与输入实例有关，平

6、均时间复杂度均为O(n)o寸函入运算:P=GetNode(1zi-1);s-next=p-next;p-next=s;平均时间复杂度均为。(n),删除运算：p=GetNode(1zi-1);r=p-next;p-next=r-next;free(r);平均时间复杂度均为0(n)单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是。（1）,不用遍历整个链表。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不

7、同方向的链。由头指针head惟一确定。双链表也可以头尾相链接构成双（向）循环链表。双链表上的插入和删除时间复杂度均为0（1）。顺序表和链表的上匕较：基于空间：顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。链表的存储空间是动态分配，存储密度1；适于线性表长度变化大时采用。 基于时间： 顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。 以插入和删除操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。第三章栈和队列栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称

8、为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为1IFO表(1astInFirstOut)通常栈有顺序栈和链栈两种存储结构。栈的基本运算有六种：构造空栈：InitStack(S) 判栈空：StackEmpty(S) 判栈满:StackFuII(S) 进栈：Push(Szx)退栈：Pop(S) 取栈顶元素：StackTop(S)在JI质序栈中有上溢和下溢的现象。上溢是栈顶指针指出栈的外面是出错状态。下溢可以表示栈为空栈，因此用来作为控制转移的条件。顺序栈中的基本操作有六种:构造空栈判栈空判栈满进栈退栈,取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部

9、附加头结点，只要有链表的头指针就可以了。链栈中的基本操作有五种:构造空栈判栈空进栈退栈取栈顶元素队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front),允许插入的一端称为队尾(rear),队列的操作原则是先进先出的，又称作FIFO表(FirStInFirstOut).队列也旬I1页序存储和链式存储两种存储结构。队列的基本运算有六种：置空队：InitQueue(Q) 判队空：QueueEmpty(Q) 判队满：QueueFuII(Q) 入队：EnQueue(Q,x) 出队：DeQueue(Q)取队头元素：QUeUeFrOnt(Q

10、)顺序队列的假上溢现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了上溢现象。为了克服假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方法有三种：一种是另设一个布尔变量来判断；第二种是少用一个元素空间,入队时先测试(rear+1)%m=front)?满：空;第三种就是用一个计数器记录队列中的元素的总数。队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在

11、链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第四章串串是零个或多个字符组成的有限序列。 空串：是指长度为零的串，也就是串中不包含任何字符(结点)。 空白串：指串中包含一个或多个空格字符的串。 在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串。 子串在主串中的序号就是指子串在主串中首次出现的位置。 空串是任意串的子串，任意串是自身的子串。串分为两种：串常量在程序中只能引用不能改变; 串变量的值可以改变。串的基本运算有：求串长str1en(char*s),串复制strcpy(char*to,char*from)串联接StrCat

12、(char*to,char*from)串比较CharCmP(char*s1,char*s2),字符定位StrChr(char*s,chare)串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为J1质序串。J1褥串又可按存储分配的不同分为：静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、链接操作。动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。为了解决存储密度低的状况

13、，可以让一个结点存储多个字符，即结点的大小。顺序串上子串定位的运算：又称串的模式匹配或串匹配，是在主串中查找出子串出现的位置。在串匹配中,将主串称为目标(串),子串称为模式(串)。这是比较容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是O(n-m+1)m),假如m与n同阶的话则它是O(n2)o链串上的子串定位运算位移是结点地址而不是整数第五章多维数组数组一般用JI质序存储的方式表示。存储的方式有：有优先顺序，也就是把数组逐行依次排列。PASCA1.C列优先顺序，就是把数组逐列依次排列。FORTRAN地址的计算方法：按行优先

14、顺序排列的数组：1OCa(ij)=1OCa(11)+(r1)*n+(j-1)*d.按列优先顺序排列的数组：1OCa(ij)=1OCa(11)(j-1)*n+(i-1)*d.矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。特殊矩阵的类型：对称矩阵：满足a(ij)=a(ji)。元素总数n(n+1)2.I=max(iJ),J=min(i,j)z1OCa(ij)=1OC(saO)+(I+1)2+J)*d. 三角矩阵:上三

15、角阵:k=i*(2n-i+1)2j-i,1OCa(ij)=1OC(sa0)+k*d. 下三角阵:k=i*(i+1)2+j,1OCa(ij)=1OC(saO)+k*d. 对角矩阵:k=2i+j,1OCa(ij)=1OC(saO)+k*d.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。第六章树树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。根是开始结点；结点的子树数称度；度为0的结点称叶子(终端结点)；度不为0的结点称分支结点(非终端结点)；除根外的分支结点