《数据结构(c语言版)》重点知识汇总

v数据结构知识点综述第一章概述数据是计算机可以识别、存储和处理的信息的载体。数据元素是数据的基本单位，可以由多个数据项组成。数据项是具有独立含义的最小标识单位。定义数据结构：逻辑结构：在独立于计算机的逻辑结构中描述数据。线性结构：一对一关系。线性结构：多对一多重关系。存储结构：逻辑结构用计算机语言实现。顺序存储结构：例如，阵列。链存储结构：链接的列表。索引存储结构：密集索引：每个节点都有索引条目。稀疏索引：每个节点集都有索引条目。散列存储结构：例如，散列表。数据计算。使用数据。在逻辑结构中定义，每个逻辑结构都有一组运算。通常是搜索、插入、删除、更新、排序。数据类型：值集合及其值中定义的工作集的通用术语。结构类型：说明机制并由用户定义的导出类型。抽象数据类型ADT:抽象数据的组织和操作。就像在概念级别说明问题一样。其优点是封装数据和操作，实现了信息隐藏。编程的本质是对实际问题选择好的数据结构，设计好的算法。算法取决于数据结构。算法是输入为一个或多个值，输出为一个或多个值的定义完善的计算过程。评价算法好坏的因素：算法是正确的。算法运行的时间；执行算法的存储空间(主要是辅助存储空间)；算法易于理解、编码和调试。时间复杂性：算法所花费的时间，它是算法解决的问题大小n的函数。渐近时间复杂度：当问题规模无限增长时算法的时间复杂性量。评估算法的时间性能时，主要标准是算法的渐近时间复杂性。在算法中，语句的频率不仅与问题大小有关，而且与输入实例中每个元素的值有关。时间复杂性包括常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性代数阶O(nlog2n)、平方阶o (n 2)和立方阶o (n 3)、k阶o (n k)，指数阶o (2 n)。空间复杂性：算法的空间消耗，该算法是解决问题大小n的函数。算法的时间复杂性和空间复杂性称为算法的复杂性。第二章路线表线性表是由n0数据元素组成的有限序列。N=0是空表格。非空表格，仅可以有一个起始节点和一个端子节点。线表格中定义的预设运算：空表配置：Initlist(L)寻找表格长度：Listlength(L)导入节点：GetNode(L，I)查找：LocateNode(L，x)插入：InsertList(L，x，I)删除：Delete(L，I)顺序表按线性表的逻辑结构顺序按一系列地址依次存储在存储单元中。存储单元中每个元素的物理位置和逻辑结构中节点的相邻关系是相同的。地址计算：loc(I)=loc(1)(I-1)* d；(第一个地址是1)在顺序表中实现的基本操作：插入：平均移动节点数为n/2。平均时间复杂度为O(n)。删除：移动节点的平均数量为(n-1)/2。平均时间复杂度为O(n)。线性表的链存储结构中节点的逻辑顺序和物理顺序不一定相同，存储每个节点值以正确表示节点之间的逻辑关系的同时，还存储后续节点的地址信息(即指针或链)。这两部分中的信息构成了连接列表的节点结构。单个链接列表以标题指针的名称命名。单链路列表计算：创建单个链接列表头插入方法：s-next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度为O(n)。尾插值方法：head=rear=nullif(if(head=null)head=s；=s；else r-next=s；r=s；平均时间复杂性全部O(n)Headline节点算法：集成了空表和非空表，没有启动节点操作的特殊处理。查找顺序号：相对于查找位置，平均时间复杂性为O(n)。按值：与平均时间复杂性为O(n)的输入实例相关。插入操作：p=GetNode(L，I-1)；s-next=p-next；p-next=s；平均时间复杂性全部O(n)删除操作：p=GetNode(L，I-1)；r=p-next；p-next=r-next；free(r)；平均时间复杂性全部O(n)单回路链列表是单个链接的列表，其中结束节点的指针字段指向起始节点或头节点。关联的列表退出条件是指针与头指针或尾指针相同。使用单循环链接列表实际上更多地使用尾部指针来表示单循环链接列表。优点是头指针和尾指针都不能用O(1)定位遍历整个关联列表。双链路列表是双向链接，通过向单个链路列表中的每个节点添加直接指向方向的指针域prior，创建两个不同的正方形朝向的链条。头指针头唯一的决定。双链接列表还可以将双(方向)循环链接配置为头和尾链接。双链路列表的插入和删除时间复杂性为O (1)。与顺序表格相关的清单比较：以空间为基础：顺序表的存储空间是静态分配，存储密度为1。定线表格适用于预先确定大小。连接列表的存储空间为动态分配，存储密度1；适合在定线表格长度发生重大变更时使用。基于时间：顺序表是随机存储结构，行表操作主要是查询时应采用。以插入和删除操作为主的线性表格必须使用关联的列表作为存储结构。主要发生在表格两端的插入和删除是用尾部指针表示的单循环链接表。第三章堆栈和队列堆叠(Stack)是限制在表格一端插入和删除的线性表格。也就是说，“插入”、“删除”是堆栈顶部，另一端称为堆栈底部。如果表格中没有元素，则为空堆叠。堆栈的更改基于LIFO表(也称为LIFO表)。通常堆栈如下顺序堆栈和链堆栈两种存储结构。堆栈的基本操作有六种：空堆栈配置：InitStack(S)堆栈空判断：StackEmpty(S)堆栈总体判断：StackFull(S)堆栈：推送(S，x)堆栈：Pop(S)堆栈顶部元素：StackTop(S)顺序堆栈具有“溢出”和“底流”现象。溢出是堆栈顶部的指针，指示堆栈外部处于错误状态。溢出是堆栈为空堆栈，因此可以用作控制变换的条件。顺序堆栈有六个基本操作：空堆栈构造堆栈空堆栈完整堆栈堆栈堆栈堆栈顶部元素链堆栈没有溢出限制，因此不要填充堆栈。链堆栈不需要将头节点连接到头部，只需要连接列表的头指针。链堆栈的基本操作有五种。空堆栈堆栈空堆栈构建堆栈顶层元素队列是具有有限操作的线性表，插入表的一端，另一端允许删除，从而删除一侧对于队列头，可以插入的一端称为到达，队列的工作原理也称为FIFO表First Out)。队列还有两种存储结构：顺序存储和链存储。伫列有六个基本动作：空队列：InitQueue(Q)团队空：QueueEmpty(Q)团队已满：队列池(q)入队：EnQueue(Q，x)取消伫列：DeQueue(Q)队列标头元素：QueueFront(Q)顺序队列中的溢出现象：避头尾指针继续向前移动，超出了矢量空间。这将使整个向量空间和队列为空，但生成“向上”“过”现象。为了克服“假溢出”现象，引入循环向量的概念是使向量空间成为头尾相接的圆形。此时队列称为循环队列。通过以下三种方法确定循环队列是空的还是已满的：一种是设置另一个布尔变量进行判断。第二种是使用较少的元素空间并入队时先测试(rear 1)%m=front)？全部：空；第三种是使用计数器记录队列中元素的总数。队列的链存储结构称为链队列，一个链队列是操作受限的单个链接表。为了便于在表末尾插入(入队)操作，向尾部添加尾部指针时，链队列由头部指针和尾部指针唯一确定。链队列中没有队列已满或超出的问题。链队列的出队算法要求如果原始组中只有一个节点，则必须将其出队，然后使用相同的修改头和尾指针将队列留空。第四章字符串字符串是由零个或多个字符组成的有限序列。空字符串：零长度字符串。也就是说，字符串不包含字符(节点)。空格字符串：表示字符串中包含一个或多个空格字符的字符串。由一个字符串中任意连续字符组成的子序列称为该字符串的子字符串，包含子字符串的字符串称为主字符串。在主字符串中，子字符串的序号表示子字符串在主字符串中的第一个位置。空字符串是任何字符串子字符串，任何字符串是自己的子字符串。字符串分为两种类型：不能在程序中更改字符串常量。您可以变更字串变数的值。字符串的基本运算如下：字符串长度strlen(char*s)字符串复制strcpy(char*to，char*from)Strcat连接(char * to，char*from)字符串比较charcmp(char*s1，char*s2)文字位置strchr(char*s，charc)因为字符串是特殊的线性表(节点是文字)，所以字符串的存储结构类似于线性表的存储结构。字符串的顺序存储结构简单地称为顺序字符串。序列字符串可以根据存储分配进行不同的划分。静态存储分配：直接定义为固定长度的字符数组。包含长字符串的操作速度快，但不适合插入、链接操作。动态存储分配：定义字符串时不分配存储空间，而是根据需要按字符串长度分配存储单元。字符串链存储是将字符串值存储为单个链接表。这种链存储结构简单地称为链字符串。链字符串和单个链接列表之间的区别只是节点。点数据字段是单个字符。要解决低存储密度问题，可以让一个节点存储多个字符，即节点的大小。在顺序字符串中定位子字符串：“模式匹配”(也称为字符串)或“字符串匹配”(在基本字符串中查找子字符串的具体值)的操作。在字符串匹配中，主字符串称为目标(字符串)，子字符串称为模式(字符串)。字符串匹配问题是查找指定模式字符串p在指定目标字符串t中首次发生的有效位移或整体有效位移。最差情况下，时间复杂性为O(n-m 1)m)，m等于n的阶在此例中为o (n 2)。链字符串的子字符串定位操作位移是节点地址，而不是整数第五章多维数组数组通常以按顺序存储的方式表示。存储行优先级，即按行存储数组。帕斯卡，c列优先级是按列顺序排列数组。fortran地址计算方法：按行优先级排列：loc(ij)=loc(11)(I-1)* n(j-1)* d按列优先级排列的数组：loc(ij)=loc(11)(j-1)* n(I-1)* d矩阵的压缩存储：为多个非零元素分配一个存储空间。不为零元素分配空间。特殊矩阵的概念：所谓特殊矩阵表示非零元素或零元素分布不变的矩阵。稀疏矩阵的概念：非零元素数远小于零元素数的矩阵称为稀疏矩阵。特殊矩阵的类型：对称矩阵：满足a(ij)=a(ji)。元素总数n(n 1)/2。I=max(i，J)，J=min(i，J)，loc (ij)=loc (sa 0) (I * (I 1)/2 j三角矩阵：上方三角形阵列：k=i*(2n-i 1)/2 j-i，loc (ij)=loc (sa 0) k * D向下三角形阵列：k=i*(i 1)/2 j，loc (ij)=loc (sa 0) k * D .对角矩阵：k=2i j，loc (ij)=loc (sa 0) k * D .稀疏矩阵的压缩存储方案包括三个组表，其中将非零元素的值和该元素所在的行号列号显示为由每个节点组成的单个线性表。但是，此压缩存储方法将失去随机存储功能。添加行表将每行的非零元素写入三元表起始位置，即包含行表的三元组表。第六章树树是n个节点的有限集合，非空时必须满足。只有一个节点，称为根。其馀节点构成m个不相交的子集根的子树。根是起始节点。节点的子树数；度为零的节点称为叶(终端节点)。非零度节点称为分支节点(不是端子接合)点)；根外的分支节点称为内部节点。对齐的树是子树左右两边的树。无序的树是没有子树左边，右边部分的树。森林是不相交的m棵树的集合。树的四种不同表达：树的表达；巢状集合表现法；买入表示广义表表示。二叉树的定义：n0节点的有限集合，空集合(n=0)或两个不与根节点相交的节点称为根由左侧子树和右侧子树的二进制树组成。与阶数为2的排序树不同，二叉树不是树的特殊情况。二叉树的四个重要特性：二叉树的I层中的节点数最大为2 (I-1) (I 1)。深度为k的二叉树最大(2k1)；-1节点(k 1)。在任意一个二叉树中，如果终端节点数为n0，度为2的节点数为N2，则n0=N2 1；具有n个节点的整个二进制树的深度为int(log2n) 1 .完整的二进制树是深度为k、节点数为(2 k)-1的二进制树。完整的二进制树是从下到左的完整的二进制树。二进制树的顺序存储结构是将二进制树的所有节点按分层顺序存储在连续存储设备上。(保存前完全绘制二叉树)树的存储结构大部分是链存储。BinTNode的结构是lchild|data|rchild，它将所有BinTNode类型的节点与指向根节点的BinTree标头指针一起构成称为