前言

教程：数据结构-青岛大学-王卓

课程截图：截图

去老电脑上把上课跟着敲的程序拷贝过来

数据结构分为逻辑结构与存储结构，根据逻辑结构和存储结构可以分成不同的数据结构，以下先根据逻辑结构划分大类，再根据存储结构进行细分（存储结构分为顺序存储与链式存储）

[TOC]

一、线性结构

与非线性的区别：线性结构是1对1，即最多只有一个前驱，一个后继，非线性则不一定

1、线性表

(LinearList-SequenceList、LinkList)

• 顺序表
• 链表
  • 设 L指针(指向链表头结点地址，用于标志一个链表)、length

2、栈(Stack)

是特殊的线性表，后进先出-FILO（栈和队列就是限定插入和删除只能在表的端点进行的线性表）

• 顺序栈
  • 设 top指针(指向栈顶元素之上位置的下标地址)、base指针(指向栈底元素)、stacksize表示栈最大可用容量、length表示实际元素个数
  • 空栈标志：base==top
  • 栈满标志：top-base==stacksize
  • 特点：简单、方便，但易产生溢出
  • 上溢：栈满了还要压入(push)
  • 下溢：栈空了还要弹出(pop)
  • ！一些方法及说明：---->还是看程序吧，程序里注释有
    • 顺序栈的初始化：分配stacksize空间，并指定top、base为首地址
    • 判断是否为空
• 链栈
  • 头指针设置为L
  • 链栈的操作只在链表的头部进行
  • ！链表头指针就是栈顶---头指针指向栈顶元素(而不是指向头结点的指针)，不是像顺序栈那样往上移一个元素
  • ？不需要头结点
  • 几乎不会满栈

3、队列(Queue)

是特殊的线性表，先进先出-FIFO

• 顺序队 一般使用循环顺序队-->单是顺序队没啥大问题，循环顺序队则多了不少考虑-->第一时间不会
  • 队首：front；队尾：rear；从队首出队，从队尾入队--->注意：rear同top一样，指向队尾元素的下一个位置
  • 注：rear在上(对应top)，front在下，即就地址来说，rear大，front小
  • queuesize:队所能容纳最大元素个数(注：为了区分队空队满，实际可用空间为queuesize-1)
  • 解决队空队满标志相同(front==rear)的方法：少用一个空间-->队空标志：front == rear；队满标志：front == (rear+1)%queuesize
• 链队(若用户无法估计所用队列的长度，宜使用链队)
  • 链队是需要头结点的，在初始化的时候队首、队尾指针均为指向头结点的指针
  • 注：头结点指针是front--front始终指向头结点，最后一结点指针是rear，数据从首元结点开始存储

4、串(string)

(不就是字符串嘛)：零个或多个任意字符组成的有限序列

• 以 '\n'结尾
• 几个术语：字串、主串、字符位置、子串位置(子串第一个字符在主串中的位置)、空格串(区分于空串、由一个或多个空格组成)、串相等(长度相等、字符相同)
• 串的存储模式：顺序存储、链式存储(存储密度低)、块链存储----->看后面的算法程序，好像用的都是最简单的顺序存储...
• 主要讨论串的模式匹配算法：确定 主串 中所含子串(模式串) 第一次出现的位置
  • BF(Brute-Force)算法-->时间复杂度O(n*m)
  • KMP算法(速度快)-->时间复杂度O(n+m)
    • 这个算法多复习几遍，因为不知道原理，靠死记的
    • 先算next[]，再算改进的nextval[]，最后再实现KMP

5、数组

6、广义表

二、非线性结构

1、树

• 二叉树

  • 树与二叉树的区别

  • 满二叉树的定义，完全二叉树的定义（见ppt）

    满二叉树是所有层都是满的，完全二叉树是在满二叉树的情况下连续去掉最后任意个结点形成的二叉树

  • 二叉树的性质：

    1. 第i层上至多个结点；第i层至少有一个结点

    2. 深度为k的二叉树至多有个结点；深度为k时至少有k个结点

    3. 对于二叉树T，叶子数为,度为2的结点数为，则

    4. 具有n个结点的完全二叉树深度为

    5. 有n个结点的完全二叉树，对任一结点i

       • i>1，其双亲结点为[i/2]

       • 2i>n，i为叶子结点(无左孩子结点)，否则，其左孩子结点为2i

       • 2i+1>n，i无右孩子结点，否则，右孩子结点为2i+1

  • 二叉树存储结构：顺序存储---浪费空间、链式存储(二叉链表、三叉链表)---比较灵活

    • n个结点的二叉链表中，有n+1个空指针域

  • 二叉树的相关算法：(up to 2021-11-30下面的都没有实现)

    • 1、遍历算法：先序、中序、后序
    • 2、中序遍历的非递归算法
    • 3、二叉树的层次遍历--->构建二叉树
    • 4、复制二叉树
    • 5、计算二叉树的深度
    • 6、计算二叉树结点总数--->计算二叉树叶子结点总数

  • 线索二叉树--->没太整明白

    • 线索(改变指向的指针)：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域指向其后继(前驱后继是指给定遍历次序后得到序列中的前驱后继)
    • 线索二叉树：加上了线索的二叉树
    • 线索化：对二叉树按照某种遍历次序使其变成线索二叉树

• 树的存储结构

  • 1、双亲表示法：定义结构数组，存放树的结点，每个结点包含两个域：数据域(存放结点信息)、双亲域(指示本结点的双亲结点在数组中的位置)--->特点：找双亲容易，找孩子难
  • 2、孩子链表：把每个结点的孩子结点排列起来，看成一个线性表，用单链表存储。则n个结点有n个孩子链表(叶子的孩子链表为空表)。n个头指针又组成一个线性表，用顺序表存储。--->特点：找孩子容易，找双亲难
  • 3、孩子兄弟表示法：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点--->没去细想，反正知道有这种方式就行

• 树、森林与二叉树的转换

  • 树与二叉树的转换
    • 树转化为二叉树，用二叉树的算法来实现树的操作
    • 任意给定一棵树，都可以找到唯一的一棵二叉树与之对应
    • 树--->二叉树：
      • 1、加线：兄弟之间加一条线；
      • 2、抹线：对每个结点，除了其左孩子外，去除与其他孩子间的连线；
      • 3、旋转：以树的根节点为轴心，整树顺时针旋转45°
      • 即：兄弟相连留长子
    • 二叉树--->树：
      • 1、加线：若p结点是双亲结点的左孩子，则将p的右孩子、右孩子的右孩子...沿分支找到所有右孩子，都用p的双亲用线连起来
      • 2、抹线：抹掉原二叉树中双亲与右孩子之间的连线
      • 3、调整：将节点按层次排序，形成树结构
      • 即：左孩右右连双亲，去掉原来右孩线
  • 森林与二叉树的转换
    • 森林--->二叉树：
      • 1、将各树转换成二叉树
      • 2、将每棵树的根节点用线相连
      • 3、以第一棵树的根节点为二叉树的根，再以根节点为轴心，顺时针旋转。
      • 即：树变二叉根相连
    • 二叉树--->森林：
      • 1、抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
      • 2、将孤立的二叉树还原成树
      • 即：去掉全部右孩线，孤立二叉再还原

• 树与森林的遍历

  • 树的遍历：
    • 1、先根遍历
    • 2、后根遍历
    • 3、按层次遍历
  • 森林的遍历：(将森林看作由三部分组成：森林中第一棵树的根节点、森林中第一棵树的子树森林、森林中其他树构成的森林)
    • 1、先序遍历(实际效果：依次从左至右对森林中的每一棵树进行先根遍历)
    • 2、中序遍历(实际效果：依次从左至右对森林中的每一棵树进行后根遍历)

• 哈夫曼树

  • 一些基本概念：
    • 路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径
    • 结点的路径长度：两结点间路径上的分支数
    • 树的路径长度：从树根到每一个结点的路径长度之和。记作：TL--->一个结论：结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树(注意：完全二叉树路径最短，但反之，路径最短的不一定是完全二叉树！！！)
    • 权(weight)：将树中结点赋给一个有某种意义的数值，称为结点的权
    • 结点的带权路径长度
    • 树的带权路径长度：树中所有叶子结点的带权路径长度之和(注意，是叶子结点，不是所有结点)
  • 定义：哈夫曼树，即最优二叉树，指带权路径长度(WPL)最短的二叉树。[一个说明：哈夫曼树更一般的定义是指带权路径长度最短的树，但“带权路径长度最短”是在“度相同”的树中比较而得的，因此有最优二叉树、最优三叉树等]
  • 一些特点：
    • 满二叉树不一定是哈夫曼树
    • 哈夫曼树中权越大的叶子离根越近
    • ？具有相同带权结点的哈夫曼树不唯一
    • ！包含n个结点的哈夫曼树共有2n-1个结点
    • ！哈夫曼树的结点的度数为0或2，没有度为1的结点
  • 哈夫曼算法*(构造哈夫曼树的方法)
    • 1、构造森林全是根：根据n个给定的权值{w_1,w_2,...,w_n}构成n棵二叉树的森林F={T_1,T_2,...,T_n}，其中，T_i是只有一个带权为w_i的根节点
    • 2、选用两小造新树：在F中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
    • 3、删除两小添新人：在F中删除这两棵树，同时将新得到的二叉树加入森林中
    • 4、重复2、3剩单根
  • 哈夫曼树构造算法的实现
    • 采用顺序存储结构：一维结构(是一个三叉链表parent,lchiled,weight,rchild)数组，因哈夫曼树有2n-1个结点，不使用0下标，数组大小为2n
      • 前n个结点为已有结点，第n+1个为最小权值的两个结点之和，以此类推
    • 算法5.10(没实现呀...)
  • 哈夫曼编码(ppt中介绍的一个编码的关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符编码的前缀--->前缀编码)：哈夫曼编码使最短的前缀码
    • 方法：
      • 1、统计字符中每个字符在电文中出现的概率(概率越大，要求编码越短)
      • 2、每个字符的概率值作为权值，构造哈夫曼树
      • 3、在哈夫曼树的每个分支上标上1或0：左分支标0，右分支标1
      • 4、把从根到每个叶子结点的路径上的标号连接起来，作为该叶子代表的字符的编码
    • 哈夫曼方法的算法实现...ppt上的(未实现...)
    • 应用：文件的解码与编码

2、图

• 图的定义与术语
  • 表示法：G=(V,E)即Gragh=(Vertex,Edge)
  • 无向图：每条边都是无方向的--->对比于有向图
  • 完全图：任意两个点都有一条边相连
    • 无向完全图：n个顶点，有n(n-1)/2条边(组合数Cnm=n!/(n-m)!m!)
    • 有向完全图：n个顶点，有n(n-1)条边
  • 稀疏图：有很少边、弧的图(e<nlogn)--->注：边：无向图；弧：有向图
  • 稠密图：有较多边
  • 网：边/弧带权的图--->权：图中边/弧所具有的相关数
  • 邻接：有边/弧相连的两个顶点之间的关系
    • 存在(v_i,v_j)，则称v_i,v_j互为邻接点
    • 存在<v_i,v_j>，则称v_i邻接到v_j，v_j邻接于v_i--->注：(a,b)偶对，无方向；<a,b>序偶，有方向
  • 关联(依附)：边/弧与顶点之间的关系(边关联于顶点)
  • 顶点的度：与该顶点相关联的边的数目，记为TD(v)
    • 在有向图中，顶点的度等于入度与出度之和--->入度，记作ID(v)；出度，记作OD(v)
  • 路径：接续的边构成的顶点序列
  • 路径长度：路径上边/弧的数目或权值之和
  • 回路(环)：第一个顶点和最后一个顶点相同的路径
  • 简单路径：除路径起点与终点可以相同外，其余顶点均不相同的路径
  • 简单回路(简单环)：除路径起点与终点相同外，其余顶点均不相同的路径
  • ！连通图(强连通图)：在无(有)向图中，若对任意两个顶点v、u都存在从v到u的路径，则称G是连通图(强连通图)--->不懂看ppt
  • 子图：边与顶点都属于母图
  • 连通分量：无向图G的极大连通子图称为G的连通分量--->极大的意思：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通
  • 强连通分量：有向图的极大连通子图称为G的强连通分量
  • 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图将不再连通
  • 生成树：包含无向图G所有顶点的极小连通子图
  • 生成森林：对非连通图，由各个连通分量的生成树的集合
• 对图的操作：
  • CreatGraph(&G,V,VR)--->初始条件：V是图的顶点集，VR是图中弧的集合；操作结果：按V和VR的定义构造图G
  • DFSTraverse(G)--->初始条件：图G存在；操作结果：对图进行深度优先搜索
  • BFSTraverse(G)--->初始条件：图G存在；操作结果：对图进行广度优先搜索
• 图的逻辑结构：多对多

附：一些C++笔记

1、new

  首先，new数组：int* a=new int[5]/delete a[]
  其次，由上面的式子可以看出，new的作用是分配指定大小的空间，返回的分配空间的首地址，它不对类型进行匹
配(等号左边为int类型，右边为数组) -->这句话不对，我去试了，new的char指针不能赋值给int类型的指针

2、指向数组元素的指针

  设有p、q指向数组元素，则p-q代表pq之间的元素个数，p++代表p指向下一个元素

3、递归

• 递归的一般形式
• 递归优缺点、递归->非递归
• 一个例子

4、字符串尾部

字符串尾部添加的是'\0'，而不是'\n'...有点搞笑

5、define与typedef

• define

  文章不错：C语言宏#define(精通详解) - 知乎 (zhihu.com))

  简单宏定义：

  #define <宏名/标识符> <字符串>
  
  eg:#define PI 3.1415926
  

  带参数的宏定义：

  #define <宏名>(<参数表>) <字符串>
  
  eg:#define S(a,b) a*b
  

• typedef

  C++ typedef的详细用法 - 知乎 (zhihu.com)

  typedef char* pCHAR;
  pCHAR pa,pb;