数据结构笔记（c++版，期末复习）

 文章来源地址https://www.toymoban.com/news/detail-517510.html

目录

一、绪论

1.数据结构基本概念

2.算法定义与特征

二、线性表

1.线性表的定义

2.顺序表的存储结构

3.链式存储结构

三、栈和队列

1、栈的基本概念

2.队列的基本概念

3.循环队列 

四、字符串和多维数组

1.字符串的基本概念

2.串的简单模式匹配

3.多维数组

3.1数组的定义

3.2数组的特点

3.4数组的存储结构与寻址——一维数组

3.5数组的存储结构与寻址——二维数组

4.矩阵的压缩存储

4.1.概念

4.2对称矩阵

4.3三角矩阵

4.4对角矩阵

 4.5稀疏矩阵

5.广义表

5.1概念

5.2题目                                   

五、树和二叉树

1.树的逻辑结构

1.1树的基本概念

1.2树的基本术语

1.3树的遍历操作

2.树的存储结构

2.1 双亲表示法

2.2孩子表示法

 2.3孩子兄弟表示法

小结

3.二叉树的逻辑结构

3.1二叉树基本概念

3.2二叉树的性质

3.3二叉树的存储结构

3.4二叉树的遍历

4. 树、森林与二叉树的转换

5.最优二叉树——哈夫曼树

六、图

1.图的定义

2.图的存储结构

2.1邻接矩阵法o(n^2)

2.2邻接表法o(n+e)

2.2.1邻接表存储的基本思想：

2.2.1邻接表构建

3.图的遍历

1.深度优先遍历(dfs)

2.广度优先遍历（bfs)

4.最小生成树

1.prim算法

2.Kruskal算法:

5.最短路径

6.aov网与拓扑排序

1.概念

2.拓扑排序算法

7.关键路径

七、查找

 1.基本概念

2.查找算法的性能

3.顺序表查找

4.折半查找

5.二叉排序树

6.平衡二叉树

7.散列表查找技术

八、排序

1.选择排序

2.冒泡排序

3.插入排序

4.快速排序

5.归并排序

一、绪论

1.数据结构基本概念

（1）数据：对客观事物的符号表示。（是计算机中可以操作的对象，是能被计算机识别，并 输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符 及声音、图像、视频等非数值类型。）

（2）数据元素：组成数据的基本单位。（人类中，人就是是数据元素。）

（3）数据项：数据项是数据不可分割的最小单位。一个数据元素可以由若干个数据项组成，数据项是数据的最小单位。 但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。

（比如人这样的数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据项，也可以有姓 名、年龄、性别、出生地址、联系电话等数据项）

（4）数据对象：具有相同性质的数据元素的集合，是数据的子集。（比如，还是刚才的 例子，人都有姓名、生日、性别等相同的数据项）

（5）数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构由逻辑结构和存储结构（物理结构）和基本操作组成。

逻辑结构：是指数据对象中数据元素之间的相互关系。包括四种结构：集合结构、线性结构、树形结构、图形结构。

存储结构（物理结构）：是指数据的逻辑结构在计算机中的存储形式。有两种：顺序存储和链式存储。

2.算法定义与特征

 1.概念：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。

2.五个基本特性：输入、输出、有穷性、确定性和可行性。

3.什么是好算法：好的算法，应该具有正确性、可读性、健壮性、高效率和低存储量的特征。

4.算法分析：目的是分析算法效率以求改进，两个主要方面是时间性能和空间性能。

常用时间复杂度所耗费的时间从小到大依次是： 

我们所求的时间复杂度一般在没有特殊说明的情况下，都是指最坏时间复杂度。

二、线性表

1.线性表的定义

（1）线性表：零个或多个具有相同数据类型的数据元素的有限序列。

第一个元素无前驱，最后一个元素无后继。

2.顺序表的存储结构

  (1)顺序表：顺序存储的线性表，其基本思想是用一段连续的存储单元依次存储线性表的数据元素。

（2）特点：随机存储，逻辑上相邻的元素其存储的物理位置也是相邻的

（3）设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为：

　　　LOC ( a i ) = LOC ( a 1 ) ＋ ( i － 1 ) × c

（4）顺序存储的实现：一维数组存储顺序表中的数据。

插入操作：o(n)      删除操作：o(n)    按值查找、按位查找

（5）缺点：插入或删除运算不方便，其效率较低，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。

3.链式存储结构

   3.1  链式存储分配的特点：

  根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题 

3.2  链式存储结构的实现

  单链表

  双向链表

          循环链表等  

3.3   单链表

（1）结点由数据域和指针域两部分组成。

L1,L2是头指针，也是链表的名字，我们设立头节点只是为了运算更加方便。

 （2）头指针和头节点的异同

 （3）单链表的实现和操作

单链表的构造：头插法和尾插法

支持操作：按值查找、按位查找、删除操作，插入操作：o(n) 

遍历

template <typename T>
void LinkList<T>::PrintList()
{

      Node<T>*p=first->next;//工作指针p初始化
      while(p!=nullptr)
      {
          cout<<p->data<<"\t";
          p=p->next;
      }
}

按位查找

template <typename T>
T LinkList<T>::Get(int i)
{
   Node<T>*p=first->next;
   int count=1;
   while(p!=nullptr&&count<i)
   {
      p=p->next;
      count++:
   }
  if(p==nullptr)throw"查找位置错误"
  else return p->data;
}

插入操作

template <typename T>
void LinkList<T>::Insert(int i,T x)
{
   Node<T>*p=first->next,*s=nullptr;
   int count=1;
   while(p!=nullptr&&count<i-1)
   {
      p=p->next;
      count++:
   }
  if(p==nullptr)throw"插入位置错误";
 else 
  {
    s=new Node<T>;
    s->data=x;
    s->next=p->next;
    p->next=s;
  }
}

删除操作

T LinkList<T>::Delete(int i)//删除第i个结点
{ 
   T x;
   Node<T>*p=first->next,q=nullptr;
   int count=1;
  while(p!=nullptr&&count<i-1)
  {
     p=p->next;
     count++;
   }
  if(p==nullptr||p->next==nullptr)throw"删除位置错误"
 else 
  {
    q=p->next;
    x=q->data;
    p->next=q->next;
    delete q;
    return x;
  }
}

3.4双向链表

结点由三部分构成：前驱指针域，数据域，后继指针域。

优点：更方便数据的插入和删除

3.5循环链表

特点：首尾相接的链表。

优点：可以从任一节点出发，访问链表中的所有节点。

判断循环链表中尾结点：

                   q->next==first。

3.6循环双链表

优点：删除最后一个结点或在最后一个结点之后插入结点十分快。o(1)

3.7顺序表与单链表比较

 若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。

对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。

当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

三、栈和队列

1、栈的基本概念

（1）栈：只允许在一端进行插入和删除操作的线性表

（2）空栈：不含任何数据元素的栈

（3）栈顶：允许插入和删除的一端。

插入：入栈、进栈、压栈

删除：出栈、弹栈

（4）栈底：另一端。

（5）特性：先进后出

（6）n个不同元素进栈，出栈元素不同排列的个数为

逐一进行模拟即可。 

链栈对比顺序栈的优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。

（7）用处：栈能适用于递归算法、表达式求值、括号匹配。

（8）两栈共享空间判满：top1+1==top2为栈满

2.队列的基本概念

(1)队列：只允许在表的一端插入，另一端删除的线性表。

允许插入的一端叫队尾， 允许删除的一端叫队头。

（2）特性：先进先出

(3)队列的顺序存储

初始状态：q.front==q.rear==0

判空操作：q.front==q.rear==0

进队操作：队不满时，先送值到队尾元素，在将rear++;

出队操作：队不空时，先取队头元素值，再将front++;

无法判满，因为会假溢出

3.循环队列 

（1）初始：q.front=q.rear=0;

（2）队首指针进1：q.front=(q.front+1)%maxsize

   (3)队尾指针进1：q.rear=(q.rear+1)%maxsize

（4）队列长度：(q.rear+maxsize-q,front)%maxsize

  (5)队空条件：q,front=q,rear=0;

（6）队满条件：(q.rear+1)%maxsize==q.front

需要牺牲一个空间，只能存储maxsize-1个元素

（7）时间复杂度：链队列和循环队列都是o(1)

空间复杂度：循环队列会产生空间浪费，链队列不会.

四、字符串和多维数组

1.字符串的基本概念

(1)字符串（简称串）：是由零个或多个字符组成的有限序列。

串的长度：串中字符的个数

子串：字符串中任意个连续的字符组成的子 序列。

主串：包含子串的串

字符在串中的位置：该字符在串中的序号

子串在主串中的位置以子串的第一个字符在主串中的位置来表示，当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

空格串：由一个或多个空格组成的串。

（2）特性：从数据结构来看，串是一种特殊的线性表，特殊性体现在数据元素可以是一个字符。

2.串的简单模式匹配

  (1)模式匹配：子串的定位操作，它求的是子串在主串中的位置。

（2）匹配算法：bf算法，kmp算法

kmp算法一般要求求next数组，在选择题里

T="abcabc"

next[i]的值表示前0~i个字符串中最大公共前后缀的前缀的最后一个元素的下标，并且规定next[0]=-1

3.多维数组

（1）（多维）数组：线性表中的数据元素可以是线性表，但所有元素的类型相同。

（2）广义表：线性表中的数据元素可以是线性表，且元素的类型可以不相同。

3.1数组的定义

数组是由一组类型相同的数据元素构成的有序集合，每个元素受n(n≥1)个线性关系的约束，并称该数组为 n 维数组。

3.2数组的特点

（3）二维数组是数据元素为线性表的线性表。

3.4数组的存储结构与寻址——一维数组

Loc(ai)＝Loc(al)＋(i－l)×c

3.5数组的存储结构与寻址——二维数组

（1）按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

4.矩阵的压缩存储

4.1.概念

(1)压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是为了节省存储空间。特殊矩阵才能进行压缩存储。

（2）特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定的规律性的矩阵。

常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。

4.2对称矩阵

将内存映射到一维数组 

元素个数=1+2+...+n=n(n+1)/2

在从0开始的一维数组中的下标=n(n+1)/r

下三角中的元素aij(i≥j), 在一维数组中的下标k与i、j的关系为： 

aij是第几个数  =1+2+...+（i-1）+j=i(i-1)/2 +j；

由于一维数组下标从0开始

所以k＝i×(i-1)/2＋j-1

上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：

k＝j×(j-1)/2＋i -1

注意题目要求的是下标还是第几个值，行优先还是列优先

4.3三角矩阵

下三角矩阵的压缩存储和对称矩阵类似，不同之处在于除了存储下三角中的元素个数，还要存储对角线上方的常数，因为是同一个常数，所以只存储一个即可。 

（a)  k=n(n+1)/2   i>j  

  (b)  k=n+(n-1)+...+(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2 +(j-i)。

4.4对角矩阵

（1）对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

（2）

 共有n+n-1+n-1=3n-2个元素

aij序号=前i-1行元素个数+第i行元素个数

=2+3（i-2）+j-i+2

=2i+j-2

下标=2i+j-3

 4.5稀疏矩阵

（1）概念：矩阵中非零元素的个数r远远小于矩阵元素个数s。零元素的分布无规律

将非零元素及其行和列构成一个三元组（行标、列标、值）

（2）稀疏矩阵的存储方法：三元组顺序表、十字链表

5.广义表

5.1概念

广义表（列表）：  n ( >=0 )个表元素组成的有限序列，记作：

LS = (a0, a1, a2, …, an-1)

  LS是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。

  n为表的长度。n = 0 的广义表为空表。

长度：广义表LS中的直接元素的个数；

深度：广义表LS中括号的最大嵌套层数。

表头：广义表LS非空时，称第一个元素为LS的表头；

表尾：广义表LS中除表头外其余元素组成的广义表

5.2题目                                   

A ＝( )                空表 ，长度0，深度1

B ＝(e)               只有一个单元素，长度1，深度1

C ＝(a, (b，c，d))    有一个单元素和一个子表，长度2，深度2

D ＝(A, B, C)      有三个子表，长度3，深度3

E ＝(a, E)       递归表，长度2 ，深度无限

        F ＝(( ))      只有一个空表，长度1，深度2

五、树和二叉树

1.树的逻辑结构

1.1树的基本概念

（1）树：n（n≥0）个结点的有限集合。

当n=0时，称为空树。

树中的每个元素只可能有一个直接前驱，但可以有多个直接后继

（2）任意一棵非空树满足以下条件：

 有且仅有一个特定的称为根的结点；

 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

（3）树的定义是采用递归方法

1.2树的基本术语

结点的度：结点所拥有的子树的个数。

树的度：树中各结点度的最大值。

叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。

孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；

兄弟：具有同一个双亲的孩子结点互称为兄弟。

祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。

路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2, …, nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。

结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。

树的深度：树中所有结点的最大层数，也称高度。

层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。

有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。

森林：m (m≥0)棵互不相交的树的集合

1.3树的遍历操作

前序遍历：根左右   ABDEHIFCG

后序遍历：左右根   DHIEFBGCA

层序遍历：自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。ABCDEFGHI

2.树的存储结构

2.1 双亲表示法

基本思想：

用一维数组来存储树的各个结点（一般按层序存储），

数组中的一个元素对应树中的一个结点，

每个结点记录两类信息：结点的数据信息以及该结点的双亲在数组中的下标。

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在 数组中的下标。

2.2孩子表示法

这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表。

为了便于进行查找采用顺序存储存储每个链表的头指针。

最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。

 2.3孩子兄弟表示法

firstchild：指针域，指向该结点第一个孩子；

data：数据域，存储该结点的数据信息；

rightsib：指针域，指向该结点的右兄弟结点。

小结

顺序存储：本质上是静态指针

双亲表示法

双亲、孩子表示法

链式存储：

多重链表示法

孩子链表表示法

孩子兄弟表示法 

3.二叉树的逻辑结构

3.1二叉树基本概念

1.定义：二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2.特点：

⑴ 每个结点最多有两棵子树；

⑵ 二叉树是有序的，其次序不能任意颠倒。

注意：二叉树和树是两种树结构。

3.几个特殊的二叉树：

（1）满二叉树

 在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上

对于编号为i的结点，他的左孩子为2i，右孩子为2i+1

（2）完全二叉树

在满二叉树的基础上，在最后一层的叶子结点，从右往左减去一些结点

i<=n/2时，说明该节点是一个分支节点

最多只有一个度为1的结点

3.2二叉树的性质

（1）在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。

 证明·：树中结点数目=度数之和+1

n0+n1+n2=0*n0+1*n1+2*n2+1

可得 n0=n2+1

(2)非空二叉树上第k层上至多有2^（k-1）个结点

(3)高度为h的二叉树最多有2^h -1个结点。

（4）具有n个结点的完全二叉树的深度为 log2n  +1。

（5）

 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有：

（1）如果i＞1，

  则结点i的双亲结点的序号为  i/2；如果i＝1，

  则结点i是根结点，无双亲结点。

(2)如果2i≤n，

  则结点i的左孩子的序号为2i；

  如果2i＞n，则结点i无左孩子。

(3)如果2i＋1≤n，

  则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点 i无右孩子。

题目1

已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是(   )

      A．39  B.52  C.111  D.119   

解：保证结点最多，说明一共有7层才对，由性质3可以得知，前6层共有结点2^6-1=63个，第6层有2^(6-1)=32个结点，减去8个叶子结点，分支结点还有24个，要保证最多，这24个结点应该全都有两个孩子，所以最多=前6层+第7层=63+24 x 2=111。本题选c

 

题目2

一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点,10个度为1的结点，则树T的叶节点个数是(   )

      A：41   B：82   C：113   D：122

解：叶子结点就是度数为1的结点，假设有n0个

根据树的性质 结点数=度数之和+1

n0+20+10+1+10=0 x n0+20x4+10x3+1x2+10x1+1

n0=82

选b

3.3二叉树的存储结构

（1）顺序存储

二叉树的顺序存储结构一般仅存储完全二叉树

（2）链式存储

基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。

在含有 n个结点的二叉链表中，含有n+1个空指针，含有n-1个非空指针。

3.4二叉树的遍历

前序遍历 ：根左右

递归算法

void   BiTree::PreOrder(BiNode<T> *root) 
{
        if (root == nullptr)  return;     
        else {
            cout<<root->data;         
            PreOrder(root->lchild );    
            PreOrder( root->rchild);    
        }
 }

中序遍历：左根右

void BiTree::InOrder (BiNode<T> *root)
{
         if (root== nullptr) 
               return;     
         else {
               InOrder(root->lchild); 
               cout<<root->data; 
               InOrder(root->rchild);
         }
}

后序遍历：左右根

void BiTree::PostOrder(BiNode<T> *root)
{ 
    if (root== nullptr)
     return; 
    else {
         PostOrder(root->lchild); 
         PostOrder(root->rchild); 
         cout<<root->data;          
    }
}

二叉树的建立

1.按扩展前序遍历序列输入结点的值

2.如果输入结点值为“#”,则建立一棵空的子树

3.否则，根结点申请空间，将输入值写入数据域中，

4.以相同方法的创建根结点的左子树

5.以相同方法创建根结点的右子树

递归方法

template <class T>
BiNode<T> * BiTree ::Creat(){
     BiNode<T> *root; char ch;
    cin>>ch;
    if (ch=='# ')     root= nullptr; 
    else {
        root=new BiNode<T>; 
        root->data=ch;
        root->lchild=creat(); 
        root->rchild= creat(); 
    }  
  return root
}

求树结点的数目

template<class T>
int BiTree<T>::count(BiNode<T>* root){
	int number=0;

	if (root== nullptr)
		number=0;
	else
		number=count(root->lchild)+count(root->rchild)+1;
	return number;
}

求叶子结点数目

template<typename T> 
void BiTree<T>:: countleaf(BiTreeNode<T> * root){
	if (root) {
		if (root->lchild== nullptr && root->rchild== nullptr)
			leafcount=leafcount+1;
		else
		{
			countleaf(root->lchild);
			countleaf(root->rchild);
		}
	}
	return;
}

1.已知一颗二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果是（）。

首先构建二叉树

前序遍历首先遍历根节点，所以A为根节点，对应中序遍历，分为CB（左子树） EDF（右子树）。前序遍历根左右，所以V、B是根，C是B的·左子树，对于EDF，在前序中，D是根，则E是D的左孩子，F是有孩子。所以后序遍历 CBEFDA

题目

1.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其根节点左子树的结点数目为（4）。

后序遍历最后访问的是根节点，前序最先访问根节点，我们在遇到这种问题时，首先考虑前序和后续找到根节点。

 

注意！由前序和后序遍历，后序和中序遍历序列，可以唯一确定一颗二叉树，但由前序和后序却不能唯一确定一颗二叉树，因为他们俩的根节点不一定相同。

4. 树、森林与二叉树的转换

1.树转化为二叉树

（1）在兄弟结点之间加一条线

（2）对每个结点，只保留他与第一个孩子的连线，抹去与其他孩子的连线。

（3）以树根为轴心，顺时针旋转45度，

由树转化为二叉树，其根节点的右子树总是空的

2.森林转化为二叉树

(1)把森林中的每颗二叉树转换成相应的二叉树

（2）每颗树的根也可以视为兄弟节点，在每颗树的树根之间加一条连线

（3）以第一颗树的树根为根节点，顺时针选择45度

 转化为二叉树，是没有右儿子的，但是变成森林以后，第二三课树都成为了第一棵树的右儿子。D

3.二叉树转化为森林或树

⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；

⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；

⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

4.森林的遍历

森林有两种遍历方法：

⑴前序（根）遍历：前序遍历森林中的每一棵树。（一颗一颗来）

⑵后序（根）遍历：后序遍历森林中的每一棵树。  

5.最优二叉树——哈夫曼树

1、叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

2、二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 记为：

lk是从根结点到第k个叶子的路径长度

wk第k个叶子的权值

3.哈夫曼树：带权路径长度最小的二叉树。

给定n个权值分别为w1,w2，···，w,的结点，构造哈夫曼树的算法描述如下!

(1) 将这n 个结点分别作为n棵仅含一个结点的二叉树，构成森林F

(2)构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，(小的在左，大的在右），且将新结点的权值置为左、右子树上根结点的权值之和。

(3)从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

(4) 重复步骤 (2) 和(3)，直至F中只剩下一棵树为止。

4.哈夫曼树的特点：

1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

 

 1 。对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该哈弗曼树的叙述中，错误的是（ ）.

      A：该树一定是一棵完全二叉树

      B：树中一定没有度为1的结点

      C：树中两个权值最小的结点一定是兄弟结点

      D：树中任一非叶结点的权值一定不小于下一层任一结点的权值

答：选A，不一定是一颗完全二叉树

 选D

哈夫曼树不存在度数为1的点

选C，10是110的前缀子串，不符合

 

六、图

1.图的定义

（1) 有向图：若E是有向边(弧) 的有限集合时，则图G为有向图。弧是顶点的有序对记为<v,w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧。

(2)无向图：若E是无向边 (边) 的有限集合时，则图G为无向图。边是顶点的无序对记为(v,w)或(w,v)，因为两者相等，其中v,w是顶点，顶点v,w互为邻接点。边(v,w)依附于顶点v,w，或者边(v,w)和顶点v,w相关联。

（3）简单图：一个图G若满足: 不存在重复边; 不存在顶点到自身的边，则称图G为简单图。

(4)多重图：若图G中某两个结点之间的边数多于一条，又允许顶点通过一条边和自己关联，则图G为多重图。

（5）完全图 (简单完全图)：对于无向图，任意两个顶点之间都存在边5)对于有向图，任意两个顶点之间都存在方向相反的两条弧。

含有n个顶点的无向完全图有n×(n-1)/2条边。

含有n个顶点的有向完全图有n×(n-1)条边。

(6) 子图：若图G=（V，E），G'=（V'，E'），如果: V'是V 的子集且E' 是 E 的子集，则称图G'是G的子图。

(7)连通、连通图
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

若图G中任意两个顶点都是连通的，则称图G是连通图

连通分量：非连通图的极大连通子图称为连通分量。

强连通图：在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。

强连通分量：非强连通图的极大强连通子图。

生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

（点不变，边是n-1条，还连通）

（8）稀疏图：称边数很少的图为稀疏图；

       稠密图：称边数很多的图为稠密图。

（9）顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。

         顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；

         顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

（10）权：是指对边赋予的有意义的数值量。

          网：边上带权的图，也称网图。

（11）回路（环）：第一个顶点和最后一个顶点相同的路径。

           简单路径：序列中顶点不重复出现的路径。

           简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

 1.一个n个顶点的连通无向图，其边的个数至少为(n-1)条

 2.要连通具有n个顶点的有向图，至少需要（  n  ）条边

 3.无向图中，所有顶点的度数之和等于边数的两倍。

 

若无向图G=(V,E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是

( )

      A ：6   B：15  C：16   D：21

分析：要想保证在任何情况下都连通，其中6个顶点组成完全图。包含6个顶点的完全图中包含6*5/2=15个条边。第7个顶点和其他6个顶点之间有一条边，就能保证图是联通的。因此，至少需要16条边

2.图的存储结构

2.1邻接矩阵法o(n^2)

2.1.1基本思想：

（1）用一个一维数组存储图中顶点的信息

（2）用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。

假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

2.1.2无向图的邻接矩阵的特点？

（1）主对角线为 0 且一定是对称矩阵。

（2）顶点i的度数=邻接矩阵的第i行（或第i列）非零元素的个数。

（3）求顶点 i 的所有邻接点，将数组中第 i 行元素扫描一遍，若arc[i][j]为1，则顶点 j 为顶点 i 的邻接点。

2.1.3有向图邻接矩阵

（1）有向图的邻接矩阵不一定对称。

（2）顶点 i 的出度=邻接矩阵的第 i 行元素之和。

（3）顶点 i 的入度=邻接矩阵的第 i 列元素之和。

2.1.4

创建无向图邻接矩阵代码

1.确定图的顶点个数和边的个数；

2.输入顶点信息存储在一维数组vertex中；

3.初始化邻接矩阵；

4.依次输入每条边存储在邻接矩阵arc中；

     4.1 输入边依附的两个顶点的序号i, j；

     4.2 将邻接矩阵的第i行第j列的元素值置为1；

     4.3 将邻接矩阵的第j行第i列的元素值置为1；

template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
    vertexNum=n; arcNum=e;
    for (i=0; i<vertexNum; i++) 
        vertex[i]=a[i];
    for (i=0; i<vertexNum; i++)    //初始化邻接矩阵
	   for (j=0; j<vertexNum; j++)
           arc[i][j]=0;             
    for (k=0; k<arcNum; k++) {
        cin>>i>>j;     //边依附的两个顶点的序号
        arc[i][j]=1;  arc[j][i]=1;  //置有边标志    
    }
}

2.2邻接表法o(n+e)

2.2.1邻接表存储的基本思想：

对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表）

所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

2.2.1邻接表构建

vertex：数据域，存放顶点信息。

firstedge：指针域，指向边表中第一个结点。

adjvex：邻接点域，边的终点在顶点表中的下标。

next：指针域，指向边表中的下一个结点。

有向图构建步骤

1. 确定图的顶点个数和边的个数；

 

2. 输入顶点信息，初始化该顶点的边表；

3. 依次输入边的信息并存储在边表中；

     3.1  输入边所依附的两个顶点的序号i和j；

     3.2  生成邻接点序号为j的边表结点s；

     3.3 将结点s插入到第i个边表的头部；

template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{   
    vertexNum=n; arcNum=e; 
    for (int i=0; i<vertexNum; i++)   
    {
       adjlist[i].vertex=a[i];
       adjlist[i].firstedge= NULL; //初始化链表头     
    } 
   
     for (int k=0; k<arcNum; k++)   
     {
         cin>>i>>j; //输入i-j这条边   
         s=new ArcNode;
         s->adjvex=j;  	        
         s->next=adjlist[i].firstedge; //头插法
         adjlist[i].firstedge=s;
     }
}

3.图的遍历

1.深度优先遍历(dfs)

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。

类似前序遍历

数据结构：stack
优势：空间:o(h)
劣势：不具最短路
每一个dfs对应一个树
重要：顺序（暴搜）
知识点：
{
回溯：往回走的过程，记得恢复现场
递归：同上
剪枝：提前判断，不合适直接跳过
}

基本思想：

⑴ 访问顶点v；

⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；

⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

邻接矩阵dfs

int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v){
     cout<<vertex[v]; 
     visited [v]=1;
     for (j=0; j<vertexNum; j++)
         if (arc[v][j]==1 && visited[j]==0)
            DFSTraverse( j );
}

2.广度优先遍历（bfs)

类似层序遍历

数据结构：队列

缺点：空间:o(2^h)
优点:具有最短路性质
但是只有当所有的边权都一样时，才能用bfs求最短路

基本思想：

⑴ 访问顶点v；

⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；

⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

邻接矩阵bfs

int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){     
    front=rear=-1;   //假设采用顺序队列且不会发生溢出
   int Q[MaxSize]; cout<<vertex[v]; visited[v]=1;  Q[++rear]=v; 
    while (front!=rear)    {
         v=Q[++front];   
         for (j=0; j<vertexNum; j++)
            if (arc[v][j]==1 && visited[j]==0 ) {
                  cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
            }
      }
}

4.最小生成树

所谓的最小成本，就是n个顶点，用n-1条边把 一个连通图连接起来，并且使得权值的和最小。

最小生成树不一定唯一

1.prim算法

时间复杂度o(n^2)

（1）任取一顶点(或题中已告知顶点)，去所有边
（2）选择一个与当前顶点集合距离最近的顶点，并将该顶点和相应的边加入进来，同时不形成回路
（3)   重复2，直至图中所有顶点都并入。

2.Kruskal算法:

时间复杂度 o(eloge)

（1）去掉所有边
（2）选边(权最小，且不构成回路)

（3）一直重复第（2）步，直至图中所有顶点都并入

5.最短路径

1.dijkstra算法

基本思想：

1. 设置一个集合 S 存放已经找到最短路径的顶点 ， S 的初始状态只包含源点 v ，

2. 对 v i ∈ V - S ，假设从源点 v 到 v i 的有向边为最短路径（从 v 到其余顶点的最短路径的初值）。

3. 以后每求得一条最短路径 v , …, v k ，就将 v k 加入集合 S 中，并将路径 v , …, v k , v i 与原来的假设相比较，取路径长度较小者为最短路径。

重复上述过程，直到集合V中全部顶点加入到集合S中。

6.aov网与拓扑排序

1.概念

1.AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样 的有向图为顶点表示活动的网，我们称为AOV网（ActivityOn Vertex Network）。 AOV网中的弧表示活动之间存在的某种制约关系。

2.设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，……，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶 点序列为一个拓扑序列。

2.拓扑排序算法

时间复杂度：O(n+e)

对AOV网进行拓扑排序

基本思路是：

（1）从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧。

（2）继续重复（1）步骤，直到输出全部顶点或者 AOV网中不存在入度为0的顶点为止。

7.关键路径

1.AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。

2.AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

始点：该顶点所代表的事件无任何先决条件，可首先开始。

终点：表示一项工程的结束。

正常的AOE网只有一个始点和一个终点。

3.AOE网的性质：

⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；

⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

4.关键路径：

在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动称为关键活动。

计算描述

⑴ 事件的最早发生时间ve[k]

ve[1]=0

ve[k]=max{ve[j]+len<vj, vk>} (<vj, vk>∈p[k])                      

p[k]表示所有到达vk的有向边的集合

⑵ 事件的最迟发生时间vl[k]

 

vl[n]=ve[n]

vl[k]=min{vl[j]-len<vk , vj>}（<vk, vj>∈s[k]）

s[k]为所有从vk发出的有向边的集合

⑶ 活动的最早开始时间e[i]

 

若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：

       e[i]=ve[k]                                           

⑷ 活动的最晚开始时间l[i]

 

活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。

若ai由弧<vk，vj>表示，

则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

因此，有：      l[i]=vl[j]-len<vk, vj>   

七、查找

 1.基本概念

列表：由同一类型的数据元素组成的集合。

关键码：数据元素中的某个数据项，可以标识列表中的一个或一组数据元素。

键值：关键码的值。

主关键码：可以唯一地标识一个记录的关键码。

次关键码：不能唯一地标识一个记录的关键码。          

静态查找 ：不涉及插入和删除操作的查找 。

动态查找 ：涉及插入和删除操作的查找。

 线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。

树表：适用于动态查找，主要采用二叉排序树的查找技术。

散列表：静态查找和动态查找均适用，主要采用散列技术

2.查找算法的性能

查找频率与算法无关，取决于具体应用

平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：

            n：问题规模，查找集合中的记录个数；

            pi：查找第i个记录的概率；

            ci：查找第i个记录所需的关键码的比较次数。

也可以计算为=总查找次数/n

3.顺序表查找

（1）优点

算法简单而且使用面广。

对表中记录的存储结构没有任何要求，顺序存储和链接存储均可；

4.折半查找

（1）适用条件：

int BinSearch(int a[],int n,int k)
{

    int l=1,r=n;
    int mid=l+r>>1;
   while(l<=r)
   {
     if(a[mid]>k)r=mid-1;
     else if(a[mid]<k)l=mid+1;
     else return mid;
   }
return 0;
}

6.平衡二叉树

1.平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：

⑴ 根结点的左子树和右子树的深度最多相差1;

⑵ 根结点的左子树和右子树也都是平衡二叉树。

void select(int n,int a[])
{
	int min=0;
	for(int i=0;i<n-1;i++)
	{
		min=i;
		for(int j=i+1;j<n;j++)
		{
			if(a[j]<a[min])
			{
				min=j;
			}
		}
		if(i!=min)
		{
			int t=a[i];
			a[i]=a[min];
			a[min]=t;
		}
	}
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	cout<<endl;
}

#include<iostream>
using namespace std;
int main()
{
  int a[5]={3,2,7,4,1};
  for(int i=0;i<5;i++)
  {
  	for(int j=0;j<5-i-1;j++)
  	{
  		if(a[j+1]<a[j])
  		{
  			int t=a[j+1];
  			a[j+1]=a[j];
  			a[j]=t;
		  }
	  }
  }
  for(int i=0;i<5;i++)cout<<a[i]<<" ";
}

#include<iostream>
using namespace std;
int main()
{
    int a[5]={4,2,8,1,0};
    for(int i=0;i<5-1;i++)
    {
        int end=i;//记录最后一个有序元素的下标
        int t=a[end+1];//待插入元素
        while(end>=0)
        {
            if(t<a[end])//
            {
                a[end+1]=a[end];
                end--;
            }
            else break;//找到第一个小于他的数，停止循环
        }
        a[end+1]=t;
    }
    for(int i=0;i<5;i++)cout<<a[i]<<" ";
}

void quick_sort(int q[],int l,int r)
{
    if(l>=r)return;
    int i=l-1,j=r+1,x=q[(l+r)/2];
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
        else break;
    }
    quick_sort(q,l,j),quick_sort(q,j+1,r);
}

void merge_sort(int a[],int l,int r)
{
  if(l>=r)return;
  int temp[10000],mid=(l+r)/2;//向下取整
   merge_sort(a,l,mid);
   merge_sort(a,mid+1,r);
   int i=l,j=mid+1,k=0;
   while(i<=mid&&j<=r)
   {
       if(a[i]<a[j])
       {
           temp[k++]=a[i++];
       }
       else
       {
           temp[k++]=a[j++];
       }
   }
   while(i<=mid)
   {
       temp[k++]=a[i++];
   }
   while(j<=r)
   {
       temp[k++]=a[j++];
   }
   for(int i=l,j=0;i<=r;i++,j++)
   {
       a[i]=temp[j];
   }
}

到了这里，关于数据结构笔记（c++版，期末复习）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！