数据结构c语言版重点知识汇总.docx

v 数据结构知识点概括第一章 概 论数据就是指能够被计算机识别、存储与加工处理的信息 的载体数据元素是数据的基本单位，可以由若干个数据项组成 数据项是具有独立含义的最小标识单位数据结构的定义：•逻辑结构：从逻辑结构上描述数据，独立于计算机•线 性结构：一对一关系•线性结构：多对多关系•存储结构：是逻辑结构用计算机语言的实现•顺序存 储结构：如数组•链式存储结构：如链表•索引存储结构：•稠密索引：每个结点都有索引项•稀疏索引：每组结点都有索引项•散列存储结构：如散列表•数据运算•对数据的操作定义在逻辑结构上，每种逻辑结构都有一个运算集合•常用的有：检索、插入、删除、更新、排序数据类型：是一个值的集合以及在这些值上定义的一组 操作的总称•结构类型：由用户借助于描述机制定义，是导出类型 抽象数据类型：•是抽象数据的组织与及之的操作 相当于在概念层上描述问题•优点是将数据与操作封装在一起实现了信息隐藏程序设计的实质是对实际问题选择一种好的数据结构， 设计一个好的算法算法取决于数据结构算法是一个良定义的计算过程，以一个或多个值输入， 并以一个或多个值输出评价算法的好坏的因素：•算法是正确的；•执行算法的时间；•执行算法的存储空间(主要是辅助存储空间)；•算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所 求解问题规模 n 的函数渐近时间复杂度：是指当问题规模趋向无穷大时，该 算法时间复杂度的数量级评价一个算法的时间性能时，主要标准就是算法的渐近 时间复杂度算法中语句的频度不仅及问题规模有关，还及输入 实例中各元素的取值相关时间复杂度按数量级递增排列依次为：常数阶 O(1) 、对数阶O (2n)、线性阶O (n)、线性对数阶O (2n)、平方阶O (nA2)>立方阶O (n^3)、……k次 方阶O (Mk)、指数阶O (2F)空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模 n 的函数算法的时间复杂度与空间复杂度合称算法复杂度第二章 线性表线性表是由n>0个数据元素组成的有限序列0 是空表；非空表，只能有一个开始结点，有且只能有 一个终端结点线性表上定义的基本运算：•构造空表：(L)•求表长：(L)•取结点：(L,i)•查找：(L, x)•插入：(L, x, i)•删除：(L,i)顺序表是按线性表的逻辑结构次序依次存放在一组 地址连续的存储单元中在存储单元中的各元素的物理 位置与逻辑结构中各结点相邻关系是一致的地址计算：(i) (1) +(1)*d;(首地址为1)在顺序表中实现的基本运算：•插入：平均移动结点次数为2;平均时间复杂度均为 O(n)。

•删除：平均移动结点次数为(1) /2;平均时间复杂 度均为 O(n)线性表的链式存储结构中结点的逻辑次序与物理次 序不一定相同，为了能正确表示结点间的逻辑关系，在 存储每个结点值的同时，还存储了其后继结点的地址信 息(即指针或链)这两部分信息组成链表中的结点结构 一个单链表由头指针的名字来命名单链表运算：•建立单链表•头插法： >；；生成的顺序及输入顺序相 反平均时间复杂度均为O (n)o•尾插法：；()；>;;平均时间复杂度均为O (n)•加头结点的算法：对开始结点的操作无需特殊处理， 统一了空表与非空表•查找•按序号：及查找位置有关，平均时间复杂度均 为 O(n)o•按值：及输入实例有关，平均时间复杂度均为O (n)o•插入运算：(L, 1); >>; >;平均时间复杂度均为O(n)•删除运算：(L, 1); >; >>; (r);平均时间复杂度均 为 O(n) 单循环链表是一种首尾相接的单链表，终端结点的指针 域指向开始结点或头结点链表终止条件是以指针等于 头指针或尾指针采用单循环链表在实用中多采用尾指针表示单循环 链表优点是查找头指针与尾指针的时间都是O（1）, 不用遍历整个链表。

双链表就是双向链表，就是在单链表的每个结点里 再增加一个指向其直接前趋的指针域，形成两条不同方 向的链由头指针惟一确定双链表也可以头尾相链接构成双（向）循环链表双链表上的插入与删除时间复杂度均为 O （1）顺序表与链表的比较： •基于空间：•顺序表的存储空间是静态分配，存储密度为1;适于 线性表事先确定其大小时采用•链表的存储空间是动态分配，存储密度V1；适于线性表长度变化大时采用•基于时间：•顺序表是随机存储结构，当线性表的操作主要是查找 时，宜采用•以插入与删除操作为主的线性表宜采用链表做存储结 构•若插入与删除主要发生在表的首尾两端，则宜采用尾 指针表示的单循环链表第三章 栈与队列栈（）是仅限制在表的一端进行插入与删除运算的 线性表，称插入、删除这一端为栈顶，另一端称为栈底 表中无元素时为空栈栈的修改是按后进先出的原则进 行的，我们又称栈为表（ ）通常栈有 顺序栈与链栈两种存储结构栈的基本运算有六种：•构造空栈：（S）•判栈空：（S）•判栈满：（S）•进栈：（S, x）•退栈：（S）•取栈顶元素：（S）在顺序栈中有“上溢”与“下溢”的现象•“上 溢”是栈顶指针指出栈的外面是出错状态。

•“下溢”可以表示栈为空栈，因此用来作为控制转移的 条件顺序栈中的基本操作有六种：•构造空栈 •判栈 空•判栈满•进栈•退栈•取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满链 栈不需要在头部附加头结点，只要有链表的头指针就可 以了链栈中的基本操作有五种：•构造空栈•判栈空•进 栈•退栈•取栈顶元素队列（）是一种运算受限的线性表，插入在表的一端进 行，而删除在表的另一端进行，允许删除的一端称 为队头（），允许插入的一端称为队尾（） ，队列的操 作原则是先进先出的，又称作表（）.队列也有顺序存储与链式存储两种存储结构队列的基本运算有六种： •置空队：（Q）•判队空：（Q）•判队满：（Q）•入队：（Q, x）•出队：（Q）•取队头元素：（Q）顺序队列的“假上溢”现象：由于头尾指针不断前 移,超出向量空间这时整个向量空间及队列是空的却 产生了“上溢”现象为了克服“假上溢”现象引入循环向量的概念，是把 向量空间形成一个头尾相接的环形，这时队列称循环队 列判定循环队列是空还是满，方法有三种：•一种是另设一个布尔变量来判断；•第二种是少用一个元素空间，入队时先测试（（1）= ）？ 满：空；•第三种就是用一个计数器记录队列中的元素的总数。

队列的链式存储结构称为链队列，一个链队列就是一个 操作受限的单链表为了便于在表尾进行插入（入队） 的操作，在表尾增加一个尾指针，一个链队列就由一个头 指针与一个尾指针唯一地确定链队列不存在队满与上 溢的问题在链队列的出队算法中，要注意当原队中只有 一个结点时，出队后要同进修改头尾指针并使队列变空 第四章 串 串是零个或多个字符组成的有限序列•空串：是指长度为零的串，也就是串中不包含任何字符（结点）•空白串：指串中包含一个或多个空格字符的串•在一个串中任意个连续字符组成的子序列称为该串的 子串，包含子串的串就称为主串•子串在主串中的序号就是指子串在主串中首次出现的位置•空串是任意串的子串，任意串是自身的子串串分为两种：•串常量在程序中只能引用不能改变;•串变量的值可以改变串的基本运算有：•求串长（*s）•串复制（*，*）•串联接（*, *）•串比较（*s1,*s2）•字符定位（*s,）串是特殊的线性表（结点是字符），所以串的存储结构 及线性表的存储结构类似串的顺序存储结构简称为顺 序串顺序串又可按存储分配的不同分为： •静态存储分配：直接用定长的字符数组来定义优点 是涉及串长的操作速度 快）但不适合插入、链接操作。

•动态存储分配：是在定义串时不分配存储空间）需要 使用时按所需串的长度分配存储单元串的链式存储就是用单链表的方式存储串值）串的这 种链式存储结构简称为链串链串及单链表的差异只是 它的 结点数据域为单个字符为了解决“存储密度”低的状况）可以让一个结点存储 多个字符）即结点的大小顺序串上子串定位的运算：又称串的“模式匹配” 或“串匹配”）是在主串中查找出子串出现的位置在串 匹配中）将主串称为目标（串））子串称为模式（串） 这是比较容易理解的）串匹配问题就是找出给定模式串 P 在给定目标串 T 中首次出现的有效位移或者是全部有 效位移最坏的情况下时间复杂度是O （（1） m）,假如 m 及 n 同阶的话则它是O （n^2）链串上的子串定位运算位移是结 点地址而不是整数第五章 多维数组 数组一般用顺序存储的方式表示 存储的方式有： •行优先顺序）也就是把数组逐行依次 排列C•列优先顺序，就是把数组逐列依次排列地址的计算方法：•按行优先顺序排列的数组：() (11)+((1)*(1))*d.•按列优先顺序排列的数组：()(11) + ((1) *(1)) *d.矩阵的压缩存储：为多个相同的非零元素分配一个存储 空间；对零元素不分配空间。

特殊矩阵的概念：所谓特殊矩阵是指非零元素或零 元素分布有一定规律的矩阵稀疏矩阵的概念：一个矩阵中若其非零元素的个数 远远小于零元素的个数，则该矩阵称为稀疏矩阵特殊矩阵的类型：•对称矩阵：满足a ()()元素总数 n(1)/2(i，j)，(i，j)，()([0])+(I*(1 /2)*d.•三角矩阵：•上三角阵：* (21) /2, () ([0]) *d.•下三角阵：* (1) /2, () ([0]) *d.•对角矩阵：2, () ([0]) *d.稀疏矩阵的压缩存储方式用三元组表把非零元素的 值与它所在的行号列号做为一个结点存放在一起，用这 些结点组成的一个线性表来表示但这种压缩存储方式 将失去随机存储功能加入行表记录每行的非零元素在 三元组表中的起始位置，即带行表的三元组表第六章 树树是 n 个结点的有限集合，非空时必须满足：只有 一个称为根的结点；其余结点形成m个不相交的子集， 并称 根的子树根是开始结点；结点的子树数称度；度为 0 的结点 称叶子(终端结点)；度不为0的结点称分支结点(非终端结点）；除根外的分支结点称内部结点有序树是子树有左，右之分的树；无序树是子树没有 左，右之分的树；森林是m个互不相交的树的集合；树的四种不同表示方法：•树形表示法；•嵌套集合 表示法；•凹入表示法•广义表表示法。

二叉树的定义：是n>0个结点的有限集，它是空 集（0）或由一个根结点及两棵互不相交的分别称作这个 根的左子树与右子树的二叉树组成二叉树不是树的特殊情形，及度数为2 的有序树不 同二叉树的4个重要性质：•二叉树上第i层上的结 点数目最多为2八（1） （i>1）o；•深度为k的二叉树至多有（2Ak） -1个结点（k>1）；•在任意一棵二叉树中，若终端结点的个数为n0,度为2的结点数为n2,则n02+1;•具有n个结点的完全二叉树的深度为（2n） +1.满二叉树是一棵深度为k,结点数为（2八妆）-1的二 叉树；完全二叉树是满二叉树在最下层自右向左去处部 分结点；二叉树的顺序存储结构就是把二叉树的所有结点按照 层次顺序存储到连续的存储单元中存储前先将其画成 完全 二叉树）树的存储结构多用的是链式存储的结构为，把所有 类。