数据结构期末考点

• ​线性结构

  • ​顺序存储实现线性表（p58）

    • ​查找成功的平均比较次数为(1+2+...+n)/n=(n+1)/2

    • ​平均时间复杂度为O(n)

    • ​访问节点的时间复杂度为O(1)

  • ​表达式求值

    • 中缀转后缀(P82)

      • ​

  • ​队列

    • ​判断循环队列的空与满（P85）

      • ​Front指针与Rear指针的变化

        • ​方法一：增加一个变量

        • ​方法二：少用一个元素空间

        • 方法二判断代码：​return((Q->Rear+1)%Q->MaxSize==Q->Front);

• ​图

  • ​基本概念

    • ​在一个含有n给顶点的无向完全图中，共有n(n-1)/2条边  P204

    • ​有n个顶点的图，如果边的数量小于n-1，那么它必定是不连通的，所以n-1是连通图所需的“极小”的边的数量  P204 

  • ​图的存储结构

    • ​有向图的邻接矩阵表示  P207

      • 

  • ​深度优先搜索(DFS)P219

    • ​

  • ​构造最小生成树的Kruskal算法P232

    • ​Kruskal算法是一种按照网图边的权值递增的顺序构造最小生成树的方法

    • • • • ​P233

            • • • • 

  • ​单源最短路径

    • 

• ​树

  • ​二叉树(P107)

    • ​最小深度一定是一颗完全二叉树，（16<17<32,二叉树17的最小深度为4+1.

    • ​深度为k的二叉树有最大节点总数2^k  - 1,k>=1.

    • ​任何非空二叉树T，n0表示叶节点个数，n2为度为2的非叶节点个数

      • ​1,n=n0+n1+n2

      • ​2,n=1+n1+2n2

      • ​n0=n2+1(公式1-公式2得)

    • ​用中序和后序遍历构造二叉树(P119)

  • ​平衡二叉树（AVL树）P134

    • ​平衡二叉树定义

      • ​平衡因子BF(T) = h1-h2

      • ​根节点左，右子树高度差的绝对值不超过1

      • ​任一节点的左，右子树均为AVL树

    • ​平衡二叉树的调整

      • ​左单旋示意图

        • 

      • ​左单旋算法P141

        • ​具体实现,四句代码：

          • ​lc = p->lchild；

          • ​ p->lchild=lc->rchild;

          • lc->rchild=p;

          • ​ p=lc;

• 排序

  • ​堆排序P266

    • ​首先将一个无序的序列生成一个最大堆

    • ​最大堆的调整

      • ​

  • 快速排序P273

    • 1.设置一个主元，​设置两个指针Low，High。初始位置分别指向第一和倒数第二个元素

    • ​2.Low从指向的位置向右扫描遇到比主元大的元素，则停止，High从指向的位置向右扫描遇到比主元小的元素，则停止。

    • ​3.若Low与High没有错位，则交换所指元素的位置，

    • ​4.重复操作2.3直到Low与High错位，以主元为边界划分成两个子序列

    • ​5，递归对两个子序列进行同样方法快排

    • ​快速排序示例：

      • ​

  • ​排序算法效率比较P287

    • ​

• ​散列查找

  • ​线性探测法（P177）

    • ​公式：h i(key) =(h(key)+d i)mod TableSize （1<= i <TableSize

    • ​表格（散列地址，关键词，冲突次数

      • ​

    • 过程

      • ​

        • ​将说明中得到的冲突值记到该数字下面的冲突次数