数据结构知识点总结

1、数据结构知识点概述第一章概论数据是指能够通过修正计算机进行识别、记忆、加工处理的信息的载体。数据元素是数据的基本单位，可以由多个数据项组成。 数据项是具有独立意义的最小识别单位。数据结构定义：逻辑结构：从逻辑结构描述数据，独立于修正计算机。 线性结构：一对一的关系。线性结构：多对多的关系。存储结构：逻辑结构用修正机语言的实现。 顺序存储结构，如数组。链式存储结构：链表等。索引存储结构：稠密索引：每个节点都有一个索引项。稀疏索引：每个节点集都有一个索引条目。散列存储结构：散列表等。数据运算。对数据的操作。 在逻辑结构中定义，每个逻辑结构都有一个运算集。常用的是搜索、插入、删除、更新和排序。数据类

2、型：值的集合以及为这些值定义的一系列操作的总称。结构类型：用户通过描述机制定义的导出类型。抽象数据型adt :抽象数据的组织及其操作。 相当于在概念层面记述问题。通过封装数据和操作，具有可以实现信息隐藏的优点。编程的本质是为实际问题选择好的数据结构并设定修正好算法。 算法依赖于数据结构。算法是一个很好的定义校正过程，作为一个或多个值输入，作为一个或多个值输出。评价算法好坏的要素：算法是正确的运行算法的时间运行算法的存储空间(主要是辅助存储空间)算法易于理解、编码和调试。时间复杂度：是某算法的时间消耗，是该算法求解的问题规模n的函数。渐近时间复杂度：当问题规模趋向无穷大时，是该算法的时间复杂度的

3、顺序。在评估一种算法的时间性能时，主要标准是算法的渐近时间复杂度。算法中的句子频率不仅与问题的规模有关，也与输入事例中各要素的可取值有关。时间复杂度依次为常数次数o(1)、对数次数o(log2n )、线性次数o(n )、线性对数次数o(nlog2n )、平方次数o(n2)、立方次数o(n )空间复杂度：是某算法的空间消耗，是该算法求解的问题规模n的函数。算法的时间复杂度和空间复杂度合称为算法复杂度。第二章线性表线性表是由n0个数据元素组成的有限序列。n=0是一个空表。 非空表只有一个起始节点，一个终止节点。线性表中定义的基本运算：建立空白表格： initlist(l )求表长度： listle

4、ngth(l )取得节点： getnode(l，i )搜索：定位节点(l，x )插入列表(l，x，i )删除：删除(l，i )顺序表按线性表的逻辑结构顺序将一系列地址顺序存储在连续的存储单元中。 存储单元内各要素的物理位置和逻辑结构中各节点的邻接关系一致。 地址校正运算： loca(i)=loca(1) (i-1)*d。 (起始地址为1 )在顺序表中实现的基本运算：插入：平均移动节点次数为n/2平均时间复杂度全部为o(n )。删除：平均移动节点次数为(n-1)/2； 平均时间复杂度均为o(n )。在线性表的链存储器结构中，节点的逻辑顺序和物理顺序不一定相同，为了能够正确表现节点间的逻辑关系，存

5、储各节点的值，并且还存储其后续节点的地址信息(即指针、链)。 这两个信息构成链表中的节点结构。一个单链接表具有一个标题指针的名称。单链表运算：创建单链表标头插件： s-next=head； 头=s； 生成的顺序与输入顺序相反。 平均时间复杂度均为o(n )。尾插法： head=rear=null； if (头=空)头=s。 下一步=s； r=s； 平均时间复杂度均为o(n )附加节点的算法：开始节点的操作不需要特别处理，将空表和非空表统一了。搜索顺序：与搜索位置相关，平均时间的复杂性均为o(n )。按值：与输入例程相关，平均时间复杂度均为o(n )。插入运算： p=getnode(l，i-1)

6、: s-next=p-next； 下一个=s； 平均时间复杂度均为o(n )删除运算： p=getnode(l，i-1 )； r=下一个； 下一个=下一个； 自由(r )； 平均时间复杂度均为o(n )单循环链表是一个成功连接的单链表，末端节点的指针字段指向起始节点或报头节点。 链接表的结束条件是指针与开头指针或者末尾指针相等。采用单循环链表在实用上经常用尾部指针表示单循环链表。 优点在于，寻找头指针和尾指针的时间都是o(1)，不使用扫描整个链接表。双链路表是双向链路表，通过向单链路表的每个节点添加另一个直接前向的指针域prior来形成两种不同的方法朝向的链条。 由头部指针head唯一决定。在

7、双链表中，头尾相链也可以构成双(朝向)循环链表。双链表上的插入和删除时间的复杂性都是o (1)。顺序表与链表的比较：基于空间：序列表中的存储区域是静态分配的，存储密度为1。线性时间校正适合预先确定其大小。链表的存储空间是动态分配的，适合在存储密度1线性时间校正的长度变化大时采用。基于时间：顺序表是随机存储器结构，适用于线性表的操作主要是检索的情况。以插入和删除操作为中心的线性表建议使用链接表创建存储结构。如果插入和删除主要发生在表的开头和末尾，则最好使用由末尾指针表示的单循环链表。第三章堆栈和队列“堆栈”(stack )是一种线性表，它只对表的一端限制插入和删除运算，插入、删除的一端称为堆栈顶

8、部，另一端称为堆栈底部。 如果表没有元素，则为空堆栈。 栈的修改按照先进先出的原则进行，我们也把栈称为lifo表(last in first out )。 通常是有堆栈的序列堆栈和链式堆栈两种存储结构。堆栈的基本运算有6种：结构空堆栈： init堆栈(s )判定堆栈空：堆栈空(s )堆栈完整：堆栈完整(s )到堆栈：推(s，x )堆叠回复： pop(s )取堆栈的顶部元素：堆栈顶部(s )顺序堆栈有“上溢”和“下溢”现象。 溢位(overflow )是堆叠顶端指针，表示堆叠外部为错误状态。下溢(underflow )可以表示堆叠是空的堆叠，因此用作控制转移的条件。序列堆栈中的基本操作是构建空堆

9、栈判断堆栈空判断堆栈以填满堆栈的前导元素链接堆栈没有溢出限制，请不要判断堆栈已满。 链堆栈不需要在头部附加报头节点，只要有链表的报头指针即可。链堆栈中的基本操作包括五个操作：空堆栈确定堆栈构建空堆栈并提取堆栈的顶部元素“队列”(queue )是插入到表的一端、删除到表的另一端并允许删除的一侧的名称对于“队列”(front )，允许插入的一侧称为“队列”(rear )，队列的操作原则是先进先出，也称为fifo表(first in )first out ) .队列还具有顺序存储和链存储两种存储结构。队列的基本运算有6种：放置空队列： initqueue(q )判定队空：队列实力(q )客满：排队满

10、(q )入队：入队(q，x )出队时间： dequeue(q )伫列头元素：伫列前端(q )序列时滞的“假溢出”现象：因为头尾指针不断前进，超过了向量空间。 此时，向量空间及队列整体为空而产生“上”溢出现象。为了克服“假溢出”现象而导入循环向量的概念，将向量空间形成头尾相邻的环状，在这种情况下，将队列称为循环队列。有三种方法可以确定循环队列是空的还是已满的一是设置另一个布尔变量进行判断二是不使用一个元素空间，排队时首先进行测试(rear 1)%m=front )？ 满：空第三，队列中元素的总数由一个计数器记录。队列的链存储结构称为链队列，链队列是操作受到限制的单链表。 为了便于向脚注中插入(排

11、队)的操作将脚注指针添加到脚注中，并且链队列由标头指针和脚注指针唯一确定。 链队列中不存在队列满和溢出的问题。 请注意，在链队列的出队算法中，如果原始队列中只有一个节点，则在出队后修改头尾指针以将队列清空。第四章字符串字符串是由零个或多个字符组成的有限序列。空字符串表示长度为零的字符串，即字符串不包含字符(节点)。空白字符串：指字符串中包含一个或多个空白字符的字符串。由一个串中的任意连续字符构成的子序列被称为该串的子串，而包含该子串的串被称为主串。子串在主串中的编号是指子串在主串中首次出现的位置。空列是任意列的部分列，任意列是其自己的部分列。字符串分为两类。 字符串常数只能在程序内参照，不能变

12、更。您可以更改字符串变量的值。串的基本计算确定串长度strlen(char*s )字串复本strcpy(char*to，char*from )串联连接strcat(char*to，char*from )字符串比较charcmp(char*s1，char*s2)文字定位strchr(char*s，charc )由于串是特殊的线性表(节点是字符)，所以串的存储结构类似于线性表的存储结构。 串的顺序存储结构简称为顺序串。根据存储分配，序列列可以分为以下几类静态存储分配：由固定长度的字符数组直接定义。 串长的操作速度快，但有不适合插入、链接操作的优点。动态存储分配：在定义字符串时不分配存储空间，而是根

13、据需要按字符串长度分配存储单元。串的链存储是指将串值存储在单链表中，串的这种链存储结构简称为串。 链列和单链表的区别只是其结点数据字段为一个字符。为了解决“存储密度”低的情况，一个节点可以存储多个字符，即节点的大小。序列上部分列定位的运算：也称为字符串的“模式匹配”或“字符串匹配”，在主列中查找部分列出现的位置。 在串匹配中，主串被称为目标(串)，而子串被称为模式(串)。 这相对容易理解，字符串匹配的问题是发现模式列p首次出现在目标列t中的有效位移或者所有有效位移。 在最坏的情况下，假定时间复杂度是o(n-m 1)m )并且m是与n相同的电平那是o(n2)。 链列上的子列定位运算位移是节点地址

14、，而不是整数第五章多维数组数组通常以按顺序存储的方式表示。存储方法是按行的优先顺序，即按行顺序排列排列。 帕斯卡尔，c列的优先顺序是按列顺序排列数组。 福特兰地址的校正方法：按行优先顺序排列的数组： loca (ij )=loca (11 ) (i-1 ) * n (j-1 ) ) * d按列的优先级排列： loca (ij )=loca (11 ) (j-1 ) * n (i-1 ) ) * d矩阵压缩存储：为同一个非零元素分配一个存储空间；不为零元素分配空间。特殊矩阵的概念：特殊矩阵是非零元素或零元素分布具有一定规则的矩阵。稀疏矩阵的概念：如果一个矩阵中非零元素的数量远少于零元素的数量，则

15、该矩阵称为稀疏矩阵。满足特殊矩阵的类型：对称矩阵： a(ij)=a(ji )。 元素总数n(n 1)/2.i=max(i，j )、j=min(i，j )、loca(ij)=loc(sa0 )三角矩阵：上三角矩阵： k=i*(2n-i 1)/2 j-i、loca(ij)=loc(sa0) k*d。下三角阵： k=i*(i 1)/2 j、loca(ij)=loc(sa0) k*d。对角矩阵： k=2i j、loca(ij)=loc(sa0) k*d。稀疏矩阵的压缩存储方式是将零以外的要素的值和存在它的行号列编号作为节点用三元组表存储，用由这些节点组成的线性表表示。 但是，这种压缩存储方式会丢失随机

16、存储功能。 添加一个行表，其中每个行的非零元素是三个组表的具有起始位置，即行表的三个组表。第六章树树是n个节点的有限集合，如果不是空的话必须满足：称为根的节点只有一个，其自己节点形成了m个不相交的子集并且一起说根子树。根是开始节点将节点的子树数的称呼度为0的节点称为叶(终端节点)，将度不为0的节点称为分支节点(非终端节点)点)； 除去根的分支节点称为内部节点有序树是子树有左，右分的树无序树是子树有左，右分的树森林是m个互不相交的树的集合树的四种不同表示方法：树的表示方法嵌套集合表示法凹入表示法广义表示法。二叉树的定义： n0个节点的有限集合，它将空集合(n=0)或者1个根节点和2个相互不交叉的

17、节点分别称为这个根由左子树和右子树的二叉树构成。二叉树不是树的特殊情况，与频数2的有序树不同。二叉树的4个重要性质：二叉树上第i层上的结点数最大为2(i-1)(i1 )。深度为k的二叉树最多为(2k)-1个节点(k1 )。在任意一个二叉树中，如果将终端节点的个数设为n0、将度设为2的节点数设为n2，则n0=n2 1具有n个节点的完全二叉树的深度是int(log2n) 1满二叉树是深度k、结点数(2k)-1的二叉树的完全二叉树是满二叉树在最下层从右向左的部分的节点二叉树的顺序记忆结构是将二叉树的所有节点按层次顺序存储在连续的记忆单元中。 (请在保存前完全绘制二叉树)树的存储结构以链式存储为多。 bintnode的构造是lchild|data|rchild，通过在所有的bintnode类型的节点上，添加到根节