以下为《《数据结构(c语言版)》知识点概括》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

]Y大学术菌 QQ***3 数据结构知识点概括 第一章 概 论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小 标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型 ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问 题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于 数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模 n 的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶 O（1）、对数阶 O（log2n）、线性阶 O（n）、线性对数阶 O（nlog2n）、平方阶 O（n^2）、立方阶 O（n^3）、……k 次方阶 O （n^k）、指数阶 O（2^n）。 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模 n 的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 第二章 线性表 线性表是由 n≥0 个数据元素组成的有限序列。 n=0 是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。 线性表上定义的基本运算： ·构造空表：Initlist（L） ·求表长：Listlength（L） ·取结点：GetNode（L，i） ·查找：LocateNode（L，x） ·插入：InsertList（L，x，i） ·删除：Delete（L，i） 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储 单元中的各元素的物理位置和 逻辑结构中各结点相邻关系是一致的。地址计算：LOCa（i）=LOCa（1）+（i-1）*d； （首地址为 1） 在顺序表中实现的基本运算： ·插入：平均移动结点次数为 n/2；平均时间复杂度均为 O（n）。 ·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为 O（n）。 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示 结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指 1 ]Y大学术菌 QQ***3 针或链）。这两部分信息组成链表中的结点结构。 一个单某某由头指针的名字来命名。 单某某运算： ·建立单某某·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时 间复杂度均为 O（n）。 ·尾插法：head=rear=null；if（head=null） head=s；else r->next=s；r=s； 平均时间复 杂度均为 O（n） ·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。 ·查找·按序号：与查找位置有关，平均时间复杂度均为 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，形成两条不同方 向的链。由头指针 head 惟一确定。 双链表也可以头尾相链接构成双（向）循环链表。 双链表上的插入和删除时间复杂度均为 O （1）。 顺序表和链表的比较： ·基于空间： ·顺序表的存储空间是静态分配，存储密度为 1；适于线性表事先确定其大小时 采用。 ·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。 ·基于时间： ·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。 ·以插入和删除操作为主的线性表宜采用链表做存储结构。 ·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 第三章 栈和队列 栈（Stack）是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这 一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进 行的，我们又称栈为 LIFO 表（Last In First Out）。通常栈有 顺序栈和链栈两种存储结构。 栈的基本运算有六种： ·构造空栈：InitStack（S） ·判栈空： StackEmpty（S） ·判栈满： StackFull（S） ·进栈： Push（S，x） ·退栈： Pop（S） ·取栈顶元素：StackTop（S） 在顺序栈中有“上溢”和“下溢”的现象。 ·“上溢”是栈顶指针指出栈的外面是 出错状态。 ·“下溢”可以表示栈为空栈，因此用来作为控制转移的条件。 顺序栈中的基本操作有六种：·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取 栈顶元素 链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只 要有链表的头指针就可以了。 链栈中的基本操作有五种：·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素 队列（Queue）是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端 进行，允许删除的一端称 为队头（front），允许插入的一端称为队尾（rear） ，队列的操作原则是先进先出的， 又称作 FIFO 表（First In First Out） .队列也有顺序存储和链式存储两种存储结构。 队列的基本运算有六种： ·置空队：InitQueue（Q） ·判队空：QueueEmpty（Q） 2 ]Y大学术菌 QQ***3 ·判队满：QueueFull（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）。链串上的子串定位运算位移是结点地址而不是整数 第五章 多维数组 数组一般用顺序存储的方式表示。 存储的方式有： ·行优先顺序，也就是把数组逐行依次排列。PASCAL、C ·列优先顺序，就是把数组逐列依次排列。FORTRAN 地址的计算方法： ·按行优先顺序排列的数组：LOCa（ij）=LOCa（11）+（（i-1） *n+（j-1））*d. 3 ]Y大学术菌 QQ***3 ·按列优先顺序排列的数组：LOCa（ij）=LOCa（11）+（（j-1） *n+（i-1））*d. 矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。 特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩 阵称为稀疏矩阵。 特殊矩阵的类型： ·对称矩阵：满足 a（ij）=a（ji）。元素总数 n（n+1）/2.I=max （i，j），J=min（i，j），LOCa（ij）=LOC（sa[0]）+（I*（I+1）/2+J）*d. ·三角矩阵： ·上三角阵：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d. ·下三角阵：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d. ·对角矩阵：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d. 稀疏矩阵的压缩存储方式用XX组表把非零元素的值和它所在的行号列号做为一 个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去 随机存储功能。加入行表记录每行的非零元素在XX组表中的 起始位置，即带行表的XX组表。 第六章 树 树是 n 个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形 成 m 个不相交的子集，并称 根的子树。 根是开始结点；结点的子树数称度；度为 0 的结点称叶子（终端结点）；度不为 0 的结点称分支结点（非终端结 点）；除根外的分支结点称内部结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是 m 个 互不相交的树的集合； 树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表 表示法。 二叉树的定义：是 n≥0 个结点的有限集，它是空集（n=0）或由一个根结点及两棵 互不相交的分别称作这个根的 左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，与度数为 2 的有序树不同。 二叉树的 4 个重要性质： ·二叉树上第 i 层上的结点数目最多为 2^（i-1）（i≥1）。； ·深度为 k 的二叉树至多有（2^k）-1 个结点（k≥1）； ·在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1； ·具有 n 个结点的完全二叉树的深度为 int（log2n）+1. 满二叉树是一棵深度为 k，结点数为（2^k）-1 的二叉树；完全二叉树是满二叉树在 最下层自右向左去处部分结点； 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单 元中。（存储前先将其画成完全 二叉树） 树的存储结构多用的是链式存储。BinTNode 的结构为 lchild|data|rchild，把所有 BinTNode 类型的结点，加上一个指向根结点的 BinTree 型头指针就构成了二叉树的链 式存储结构，称为二叉链表。它就是由根指针 root 唯一确定的。 共有 2n 个指针域，n+1 个空指针。 根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历 （或中根遍历）、后序遍历（或 后根遍历）。时间复杂度为 O（n）。 利用二叉链表中的 n+1 个空指针域来存放指向某种遍历次序下的前趋结点和后继结点 的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索 使得查找中序前趋和中序后继变得简单有效，但对于查找指结.定 点的前序前趋和后序后继并没有什么作用。 树和森林及二叉树的转换是唯一对应的。 转换方法： ·树变二叉树：兄弟相连，保留长子的连线。 ·二叉树变树：结点的右孩子与其双亲连。 ·森林变二叉树：树变二叉树，各个树的根相连。 树的存储结构：·有双亲链表表示法：结点 data | parent，对于求指结.定点的双亲或祖先 十分方便，但不适于求指结.定 点的孩子及后代。 ·孩子链表表示法：为树中每个结点 data | next 设置一个孩子链表 firstchild，并将 data 4 ]Y大学术菌 QQ***3 | firstchild 存放在一个向量中。 ·双亲孩子链表表示法：将双亲链表和孩子链表结合。 ·孩子兄弟链表表示法：结点结构 leftmostchild |data | rightsibing，附加两个分别指向 该结点的最左孩子和右邻兄弟的 指针域。 树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树 的中序遍历一致。 树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小 的二叉树就称为最优二叉树 （即哈夫曼树）。 在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。 哈夫曼树有 n 个叶结点，共有 2n-1 个结点，没有度为 1 的结点，这类树又称为严 格二叉树。 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码 可能使解码产生二义性。如 00、01、0001 这三个码无法在解码时确定是哪一个，所以 要求在字符编码时任一字符的编码都不是其他字符编码的 前缀，这种码称为前缀码（其实是非前缀码）。 哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率 分布的最优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左 路径上写代码 0，右路径上写代码 1，然后从上到下到叶结 点的相应路径上的代码的序列就是该结点的最优前缀码。 第七章 图 图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两 个结点之间之间都可能相关。 图 GraphG=（V，E），V 是顶点的有穷非空集合，E 是顶点偶对的有穷集。 有向图 Digraph：每条边有方向；无向图 Undigraph：每条边没有方向。 有向完全图：具有 n*（n-1）条边的有向图；无向完全图：具有 n*（n-1）/2 条边的无 向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径； 简单回路是开始和终端重 的简单路径； 网络：是带权的图。 图的存储结构： ·邻接矩阵表示法：用一个 n 阶方阵来表示图的结构是唯一的，适合稠密图。 ·无向图：邻接矩阵是对称的。 ·有向图：行是出度，列是入度。 建立邻接矩阵算法的时间是 O（n+n^2+e），其时间复杂度为 O（n^2） ·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。 ·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。 ·无向图称边表； ·有向图又分出边表和逆邻接表； ·邻接表结点结构为 adjvex | next， 时间复杂度为 O（n+e）。，空间复杂度为 O（n+e）。。 图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历 时经过的边和图的所有顶点 构成的子图称作该图的生成树。 最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值 最小的生成树称为最小生成树 （MST）。 构造最小生成树的算法： ·Prim 算法的时间复杂度为 O（n^2）与边数无关适于 稠密图。 ·Kruskal 算法的时间复杂度为 O（lge），主要取决于边数，较适合于稀疏图。 最短路径的算法：·Dijkstra 算法，时间复杂度为 O（n^2）。·类似于 prim 算法。 拓扑排序：是将有向无环图 G 中所有顶点排成一个线性序列，若∈E（G）， 则在线性序列 u 在 v 之前， 这种线性序列称为拓扑序列。 5 ]Y大学术菌 QQ***3 拓扑排序也有两种方法： ·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的 序列即拓扑序列。 ·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得 到的序列是逆拓扑序列。 第八章 排序 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。 排序是使文件中的记录按关键字递增（或递减）次序排列起来。 ·基本操作：比较关键字大小；改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方 法是稳定的，否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若 存在数据的内外存 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 文件的插入、删除和修改只能通过复制整个文件实现。 索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记 录之间一一对应的关系，它和主文件一起构成索引文件。 索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。 若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静 态索引。 索引顺序文件常用的有两种： ·ISAM 索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。 ·VSAM 虚拟存储存取方法：采用 B+树作为动态索引结构，由索 引集、顺序集、数据集组成。 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。 散列文件 ·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要 索引区，节省存储空间。 ·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问， 需要重新组织文件。 多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一 个链表并将链表头指针、长度、次关键字作为索引表的索引项。 倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。 14 [文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

1. TDOA定位的Chan算法MATLAB源代码
2. 二级公共基础知识复习资料
3. 数据结构专升本模拟试题及参考答案
4. 第2节生命活动的主要承担者蛋白质课件
5. 《数据结构》实验报告模板
6. 《地球的圈层结构》教案
7. 学位论文中流程图的制作规范
8. 企业展示空间设计案例
9. 人身保险伤残评定标准
10. 《数据结构》考试大纲
11. 植物体的结构层次教学设计
12. 地球的圈层结构教学设计
13. 《结构素描》课件
14. DNA分子的结构教学反思
15. 5.1 生态系统结构 课件 (共25张PPT)
16. 网络数据挖掘笔记
17. 数学建模（cumcm）历届竞赛赛题基本解法
18. 详细设计说明书（GB8567——88）
19. 数据结构ch01第1章绪论
20. 选择题高频考点随身学—二级MS Office高级应用

以上为《《数据结构(c语言版)》知识点概括》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。