定义

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的 逻辑结构 和数据的 物理结构 以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为 逻辑结构 和 存储结构 。

数据的 逻辑结构 和 物理结构 是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的 逻辑结构 ，而算法的实现依赖于指定的 存储结构 。

数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是 分解 与 抽象 。通过 分解 可以划分出数据的3个层次；再通过 抽象 ，舍弃数据元素的具体内容，就得到 逻辑结构 。类似地，通过 分解 将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为 数据结构 。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到 存储结构 和 实现运算 ，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。

生活中的例子

例子1： 如何在书架上摆放图书？

关于数据组织

方法1：随便放
操作1：新书怎么插入？
哪里有空放哪里，一步到位。
操作2：怎么找到某本指定的书？
……累死

方法2：按照书名的拼音字母顺序排放
操作1：新书怎么插入？
新买进一本《阿Q正传》
操作2：怎么找到某本指定的书？
二分查找！

方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放
操作1：新书怎么插入？
先定类别，二分查找确定位置，移出空位
操作2：怎么找到某本指定的书？
先定类别，再二分查找
问题：空间如何分配？类别应该分多细？

解决问题方法的效率，跟数据的组织方式有关

例子2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印1到N的全部正整数

关于空间使用

代码块1：使用for循环实现

1
2
3
4
5
6
7
8
void PrintN(int N)
{
  int i;
  for(i = 1;i<=N;i++){
    printf("%d\n",i);
  }
  return;
}

代码块2：使用递归实现

1
2
3
4
5
6
7
void PrintN(int N){
  if(N){
    PrintN(N-1);
    printf("%d\n",N);
  }
  return;
}

解决问题方法的效率，跟空间的利用效率有关

例子3：写程序计算给定多像是在给定点x处的值

$f(x)=a_0+a_1x+\cdots + a_{n-1}x^{n-1}+a_nx^n.$

代码块:

1
2
3
4
5
6
7
8
double f(int n,double a[],double x)
{
  int i;
  double p = a[0];
  for(i =1; i<=n;i++)
    p+=(a[i]*pow(x,i));
  return p;
}

使用秦九韶算法改良：
每一次把公因子提出来
$f(x)=a_0+x(a_1+x(\cdots(a_{n-1}+x(a_n))\cdots))$

1
2
3
4
5
6
7
8
double f(int n,double a[],double x)
{
  int i;
  double p = a[n];
  for(i=n;i>0;i--)
    p=a[i-1]+x*p;
  return p;
}

clock(): 捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟打点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <time.h>

/* clock_t是clock()函数返回的变量类型 */
clock_t start,stop;
/* 记录被测函数运行时间，以秒为单位 */
double duration;
/* 不在测试范围内的准备工作写在clock()调用之前 */
int main()
{
  /* 开始计时 */
  start = clock();
  /* 把被测函数加在这里 */
  MyFunction();
  /* 停止计时 */
  stop = clock();
  duration = ((double)(stop-start))/CLK_TCK;

  /* 其他不在测试范围的处理写在后面，例如输出duration的值 */
  return 0;
}

例子4： 写程序计算给定多项式$f(x)=\sum_{i=0}^9 i\bullet x^i$ 在给定点$x=1.1$处的值$f(1.1)$

代码块1：

1
2
3
4
5
6
7
8
double f1(int n,double a[],double x)
{
  int i;
  double p = a[0];
  for(i=1;i<=n;i++)
    p += (a[i] * pow(x,i));
  return p;
}

代码块2：

1
2
3
4
5
6
7
8
double f2(int n,double a[],double x)
{
  int i;
  double p = a[n];
  for(i=n;i>0;i--)
    p=a[i-1]+x*p;
  return p;
}

实测代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <time.h>
#include <math.h>
clock_t start,stop;
double duration;
/* 多项式最大项数，即多项式阶数+1 */
#define MAXN 10

/* 被测函数最大重复调用次数 */
#define MAXK 1e7

double f1(int n,double a[],double x)
{
  int i;
  double p = a[0];
  for(i=1;i<=n;i++)
    p += (a[i] * pow(x,i));
  return p;
}

double f2(int n,double a[],double x)
{
  int i;
  double p = a[n];
  for(i=n;i>0;i--)
    p=a[i-1]+x*p;
  return p;
}

int main()
{
  int i;
  /* 存储多项式的系数 */
  double a[MAXN];
  for(i = 0;i < MAXN;i++)
    a[i] = (double) i;

  start = clock();
  /* 重复调用函数以获得充分多的时钟打点数 */
  for(i = 0;i< MAXK;i++)
    f1(MAXN-1,a,1.1);
  stop = clock();
  /* 计算函数单次运行的时间 */
  duration = ((double)(stop - start))/CLK_TCK/MAXK;
  printf("ticks1=%f\n",(double)(stop - start));
  printf("duration1=%6.2e\n",duration);

  start = clock();
  for(i = 0;i< MAXK;i++)
    f2(MAXN-1,a,1.1);
  stop = clock();
  duration = ((double)(stop - start))/CLK_TCK/MAXK;
  printf("ticks1=%f\n",(double)(stop - start));
  printf("duration1=%6.2e\n",duration);

  return 0;
}

如果测试出来的结果都是 0，可能是程序运行得太快，clock相隔时间太短。
可以让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可。

解决问题方法的效率，跟算法的巧妙程度有关

什么是数据结构

数据对象在计算机中的组织方式

  • 逻辑结构
  • 物理存储结构

数据对象与算法

  • 数据对象必定与一系列加在其上的操作相关联
  • 完成这些操作所用的方法就是算法

抽象数据类型(Abstract Data Type)

数据类型

  • 数据对象集
  • 数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

例子5：“矩阵”的抽象数据类型定义

类型名称：矩阵(Matrix)
数据对象集：一个M × N的矩阵$A_{M×N}=(a_{ij})(i=1,\cdots,M;j=1,\cdots,N)$由M × N 个三元组<a,i,j>构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。

操作集：对于任意矩阵$A、B、C\in Matrix,$以及整数$i、j、M、N$

  • Matrix Create(int M,int N): 返回一个M × N 的空矩阵；
  • int GetMaxRow(Matrix A): 返回矩阵A的总行数；
  • int GetMaxCol(Matrix A): 返回矩阵A的总列数；
  • ElementType GetEntry(Matrix A,int i,int j): 返回矩阵A的第i行、第j列的元素；
  • Matrix Add(Matrix A,Matrix B): 如果A和B的行、列数一致，则返回矩阵C=A+B,否则返回错误标志；
  • Matrix Multiply(Matrix A,Matrix B): 如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；
  • ……

算法(Algorithm)

  • 一个有限指令集
  • 接受一些输入(有些情况下不需要输入)
  • 产生输出
  • 一定在有限步骤之后终止
  • 每一条指令必须
    • 有充分明确的目标，不可以有歧义
    • 计算机能处理的范围之内
    • 描述应不依赖于任何一种计算机语言以及具体的实现手段

例子1：选择排序算法的伪码描述

1
2
3
4
5
6
7
8
9
10
11
12
void SelectionSort(int List[] , int N)
{
  /* 将N个整数List[0] ...List[N-1]进行非递减排序 */
  for(i = 0;i< N;i++){
    /* 从List[i]到List[N-1]中找到最小元，并将起位置赋给MinPosition */
    MinPosition = ScanForMin(List,i,N-1);

    /* 将未排序部分的最小元换到有序部分的最后位置 */
    Swap(List[i],List[MinPosition]);

  }
}

什么是好的算法？

空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行的结果。

计算机的加减运算比乘除运算快很多，所有尽量使用加减法，少用乘除法

例子 1

1
2
3
4
5
6
7
void PrintN(int N){
  if(N){
    PrintN(N-1);
    printf("%d\n",N);
  }
  return;
}

这是个递归算法，如果取 N=10000 时，将会与占用内存的数量成正比。

所以尽量少用递归，递归可能导致空间复杂度显著提高。
空间复杂度 $S(N)=C\cdot N$

例子 2

1
2
3
4
5
6
7
8
double f1(int n,double a[],double x)
{
  int i;
  double p = a[0];
  for(i=1;i<=n;i++)
    p += (a[i] * pow(x,i));
  return p;
}

上述算法中因为存在幂函数，幂函数的算法相当于幂的次方数，所以上述算法中转化之后存在 $(1+2+\cdots+n)=(n^2+n)/2$ 次乘法.
时间复杂度 $T(n)=C_1n^2+C_2n$

1
2
3
4
5
6
7
8
double f2(int n,double a[],double x)
{
  int i;
  double p = a[n];
  for(i=n;i>0;i--)
    p=a[i-1]+x*p;
  return p;
}

上述算法中只存在 n 次乘法.
时间复杂度 $T(n)=C\cdot n$

  • 在分析一般算法的效率时，我们经常关注下面两种复杂度
    • 最坏情况复杂度 $T_{worst}(n)$
    • 平均复杂度 $T_{avg}(n)$
      $$T_{avg}(n)\le T_{worst}(n)$$

复杂度的渐进表示法

  • $T(n)=\Omicron(f(n))$ 表示存在常数 $C\gt 0,n_0\gt 0$ 使得当 $n\gt n_0$ 时有 $T(n)\le C \cdot f(n)$ ，即是 上界
  • $T(n)=\Omega (f(n))$ 表示存在常数 $C\gt 0,n_0\gt 0$ 使得当 $n\gt n_0$ 时有 $T(n)\ge C \cdot g(n)$ ，即是 下界
  • $T(n)=\Theta(h(n))$ 表示同时有 $T(n)=\Omicron(h(n))$ 和 $T(n)=\Omega (h(n))$ ，即是 既是上界也是下界

太大的上界和太小的下界对于分析算法问题没有太大的帮助。

输入规模n有关的函数复杂度

函数复杂度增长趋势图

每秒10亿指令计算机的运行时间表

复杂度分析小窍门

  • 若两段算法分别有复杂度 $T_1(n)=O(f_1(n))$ 和 $T_2(n)=O(f_2(n))$,则
    • $T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))$
    • $T_1(n)$ × $T_2(n)=O(f_1(n)$ × $f_2(n))$
  • 若 $T(n)$ 是关于 n 的 k 阶多项式，那么$T(n)=\Theta(n^k)$
  • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

算法应用实例

最大子列和问题

例子 1:给定N个整数的序列{$A_1,A_2,\cdots,A_N$},求函数 $f(i,j)=max$ { ${0,\sum_{k=i}^jA_k}$ } 的最大值。

算法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int MaxSubseqSum1(int A[],int N)
{
  int ThisSum,MaxSum = 0;
  int i,j,k;
  for(i = 0;i< N;i++)
  {/* i是子列左端位置 */
    for(j = i;j <  N;j++)
    {/* j是子列右端位置 */
      ThisSum=0;/* ThisSum是从A[i]到A[j]的子列和 */
      for(k=i;k<=j;k++)
      {
        ThisSum += A[k];
      }
      if(ThisSum > MaxSum)/* 如果刚得到的这个子列和更大 */
      {
        MaxSum = ThisSum;/* 则更新结果 */
      }
    }/* j循环结束 */
  }/* i循环结束 */
  return MaxSum;
}

算法1的时间复杂度为 $T(N)=O(N^3)$

算法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int MaxSubseqSum2(int A[],int N)
{
  int ThisSum,MaxSum = 0;
  int i,j;
  for(i=0;i< N;i++)
  {/* i是子列左端位置 */
    ThisSum = 0;/* ThisSums是从A[i]到A[j]的子列和 */
    for(j = i;j< N;j++)
    {/* j是子列右端位置 */
      ThisSum += A[j];
      /* 对于相同的i,不同的j，只要在j-1次循环的基础上累加1项即可 */
      if(ThisSum>MaxSum)
      {/* 如果刚得到的这个子列和更大 */
        MaxSum = ThisSum;/* 则更新结果 */
      }
    }/* j循环结束 */
  }/* i循环结束 */
  return MaxSum;
}

算法2的时间复杂度为 $T(N)=O(N^2)$

算法3：分而治之

分而治之

算法4： 在线处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int MaxSubseqSum4(int A[],int N)
{
  int ThisSum,MaxSum;
  int i;
  ThisSum = MaxSum = 0;
  for(i=0;i< N;i++)
  {
    ThisSum += A[i];/* 向右累加 */
    if(ThisSum > MaxSum)
    {
      MaxSum = ThisSum;/* 发现更大和则更新当前结果 */
    }else if(ThisSum < 0){/* 如果当前子列和为负 */
      ThisSum = 0;/* 则不可能使后面的部分和增大，则抛弃之 */
    }
  }
  return MaxSum;
}

算法4的时间复杂度为 $T(N)=O(N)$

“在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

运算时间比较(秒)

线性结构

线性表及其实现

多项式的表示

[例]一元多项式及其运算
一元多项式：$f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}+a_nx^n$
主要运算：多项式的相加、相减、相乘等

【分析】如何表示多项式？
多项式的关键数据：

  • 多项式项数n
  • 各项系数$a_i$及指数i

方法1：顺序存储结构直接表示
数组各分量对应多项式各项：
$a[i]$ : 项$x^i$的系数$a_i$

例如： $f(x)=4x^5-3x^2+1$

多项式用数组表示

两个多项式相加： 两个数组对应分量相加
问题： 如何表示多项式 $x+3x^{2000}$ ?

导致空间复杂度增大，浪费内存

方法2： 顺序存储结构表示非零项
每个非零项 $a_ix^i$ 涉及两个信息：系数 $a_i$ 和指数 i
可以将一个多项式看成是一个 $(a_i,i)$ 的二元组的集合。

用结构数组表示： 数组分量是由系数 $a^i$、指数i组成的结构，对应一个非零项。

例如： $P_1(x)=9x^P{12}+15x^8+3x^2$ 和 $P_2(x)=26x^19-4x^8-13x^6+82$

顺序存储结构表示非零项

按照指数大小有序存储!

相加过程： 从头开始，比较两个多项式当前对应项的指数

$P1:(9,12), (15,8), (3,2)$

$P2:(26,19), (-4,8), (-13,6), (82,0)$

$P3:(26,19), (9,12), (11,8), (-13,6), (82,0)$

$P_3(x)=26x^{19}+9x^{12}+11x^8-13x^6+x^2+82$

方法3： 链表结构存储非零项
链表中每个 结点 存储多项式中的一个 非零项 ，包括 系数 和 指数 两个数据域以及一个 指针域

1
2
3
4
5
6
typedef strut PolyNode *Polynomial;
struct PolyNode{
  int coef;
  int expon;
  Polynomial link;
}

例如：
$P_1(x)=9x^{12}+15x^8+3x^2$
$P_2(x)=26x^{19}-4x^8-13x^6+82$
链表存储形式为:

链表存储形式

什么是线性表

多项式表示问题的启示：

  1. 同一个问题可以有不同的表示（存储）方法
  2. 有一类共性问题： 有序线性序列的组织和管理

“线性表(Linear List)”: 由同类型数据元素构成有序序列的线性结构

  • 表中元素个数成为线性表的长度
  • 线性表没有元素时，成为空表
  • 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述

类型名称： 线性表 (List)

数据对象集： 线性表是 $n(\ge0)$ 个元素构成的有序序列 $(a_1,a_2,\cdots,a_n)$

操作集： 线性表 $L\in List$, 整数 i 表示位置，元素 $X \in ElementType$,
线性表基本操作主要有：

  1. List MakeEmpty(): 初始化空线性表L;
  2. ElementType FindKth(int K,List L): 根据位序K，返回相应元素；
  3. int Find(ElementType X,List L): 在线性表L中查找X的第一次出现位置；
  4. void Insert(ElementType X,int i,List L): 在位序i前插入一个新元素X；
  5. void Delete(int i,List L): 删除指定位序i的元素；
  6. int Length(List L): 返回线性表L的长度n。

线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

线性表的链式存储实现

广义表

多重链表

堆栈

什么是堆栈？

[例] 算术表达式5+6/2-34。 正常理解：
$$5+6/2-34=5+3-34=8-34=8-12=-4$$

  • 由两类对象构成的：
    • 运算数，如2\3\4
    • 运算符号，如+、-、×、/
  • 不同运算符号优先级不一样

后缀表达式

  • 中缀表达式： 运算符号位于两个运算数之间。如，a+b*c-d/e
  • 后缀表达式： 运算符号位于两个运算数之后。如，abc*+de/-

[例] 62/3-42*+=?

后缀表达式求值策略： 从左往右“扫描”，逐个处理运算数与运算符号

  1. 遇到运算数怎么办?如何“记住“目前还不未参与运算的数？
  2. 遇到运算符号怎么办？对应的运算数是什么？

启示： 需要有种存储方法，能够顺序存储运算数，并在需要是“倒序”输出！

堆栈（stack）：具有一定操作约束的线性表

  • 只在一端（栈顶，Top）做 插入、删除

  • 插入数据： 入栈（Push）

  • 删除数据： 出栈（Pop）

  • 后入先出：Last In First Out (LIFO)

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

[例]请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。

【分析】一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

1
2
3
4
5
6
7
8
#define MaxSize <存储数据元素的最大个数>
struct DStack{
ElementType Data[MaxSize];
int Top1;/* 堆栈1的栈顶指针 */
int Top2;/* 堆栈2的栈顶指针 */
}S;
S.Top1 = -1;
S.Top2 = MaxSize;
1
2
3
4
5
6
7
8
9
10
11
void Push(struct DStack *PtrS,ElementType item,int Tag)
{
  if(PtrS->Top2 - PtrS->Top1 == 1){/*堆栈满*/
    printf("堆栈满");
    return;
  }
  if(Tag == 1)
    PtrS->Data[++(PtrS->Top1)] = item;
  else
    PtrS->Data[--(PtrS->Top2)] = item;
}

中缀表达式如何转换为后缀表达式

  • 从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

①运算数：直接输出；
②左括号：压入堆栈；
③右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
④运算符：

  • 若优先级大于栈顶运算符时，则把它压栈；
  • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；

⑤若各对象处理完毕，则把堆栈中存留的运算符一并输出。

堆栈的其他应用：

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法

树

树(Tree): $n(n\ge0)$ 个结点构成的有限集合。
当 $n=0$ 时，称为空树；
对于任一颗非空树 $n>0$ ,它具备以下性质：

  • 树中有一个称为“根(Root)”的特殊结点，用r表示；
  • 其余结点可分为m(m>0)个互不相交的有限集 $T_1,T_2,\cdots,T_m$ ,其中每个集合本身又是一棵树，称为原来树的“子树(SubTree)”

注意：树没有回路

  • 子树是不想交的；
  • 除了根结点外，每个结点有且仅有一个父结点；
  • 一颗N个结点的树有N-1条边

静态查找

方法1：顺序查找

顺序查找的一种实现(无”哨兵”)

1
2
3
4
5
6
7
8
9
int SequentialSearch(List Tb1,ElementType K)
{
  /* 在Element[1]~Element[n]中查找关键字为K的数据元素 */
  int i;

  for(i=Tb1->Length;i>0&&Tb1->Element[i]!=k;i--);
  /* 查找成功返回所在单元下标；不成功返回 0 */
  return i;
}

顺序查找的一种实现(“哨兵”)

1
2
3
4
5
6
7
8
9
10
int SequentialSearch(List Tb1,ElementType K)
{
  /* 在Element[1]~Element[n]中查找关键字为K的数据元素 */
  int i;
  /* 建立哨兵 */
  Tb1->Element[0]=k;  
  for(i=Tb1->Length;Tb1->Element[i]!=k;i--);
  /* 查找成功返回所在单元下标；不成功返回 0 */
  return i;
}
1
2
3
4
5
typedef struct LNode *List;
struct LNode{
  ElementType Element[MAXSIZE];
  int Length;
}

顺序查找算法的时间复杂度为 O(n)

方法2：二分查找(Binary Search)

假设n个数据元素的关键字满足有序(比如：小到大)
$k_1<k_2<\cdots<k_n$
并且是连续存放(数组)，那么可以进行二分查找。

二分查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int BinarySearch(List Tbl,ElementType K)
{
  /* 在表Tb1中查找关键字为K的数据元素 */
  int left,right,mid,NoFound=-1;
  /* 初始化左边界 */
  left = 1;
  /* 初始化右边界 */
  right=Tbl->Length;
  while(left<=right)
  {
    /* 计算中间元素坐标 */
    mid=(left+right)/2;
    if(K<Tbl->Element[mid])
      /* 调整右边界 */
      right = mid -1;
    else if(K > Tbl->Element[mid])
      /* 调整左边界 */
      left = mid +1;
    else  
      /* 查找成功，返回数据元素的下标 */
      return mid;
  }
  /* 查找不成功，返回-1 */
  return NotFound;
}
  • 二分查找算法具有对数的时间复杂度 $O(logN)$

11个元素的二分查找判定树

  • 判定树上每个结点需要的查找次数刚好为该结点所在的层数；
  • 查找成功时查找次数不会超过判定树的深度
  • n个结点的判定树的深度为 $[log_2N]+1$
  • $ASL = (44+43+2*2+1)/11 = 3$

树的一些基本术语

  1. 结点的度(Degree):结点的子树个数
  2. 树的度:树的所有结点中最大的度数
  3. 叶结点(Leaf):度为0的结点
  4. 父结点(Parent):有子树的结点是其子树的根结点的父结点
  5. 子结点(Child):若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
  6. 兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点。
  7. 路径和路径长度:从结点$n_1$到$n_K$的路径为一个结点序列$n_1,n_2,\cdots,n_k,n_i$是$n_{i+1}$的父结点。路径所包含边的个数为路径的长度。
  8. 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
  9. 子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙。
  10. 结点的层次(Level):规定根结点在1层，其他任一结点的层数是其父结点的层数加1;。
  11. 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度。

儿子-兄弟表示法

儿子-兄弟表示法

二叉树

二叉树T：一个有穷的结点集合。
这个集合可以为空
若不为空，则它是由根结点和称为其左子树$T_L$和右子树$T_R$的两个不相交的二叉树组成。

  • 二叉树具体五种基本形态

二叉树具体五种基本形态

  • 二叉树的子树有左右顺序之分

二叉树的子树有左右顺序之分

特殊二叉树

  • 斜二叉树(Skewed Binary Tree)

斜二叉树

  • 完美二叉树(Perfect Binary Tree)
    满二叉树(Full Binary Tree)

完美二叉树/满二叉树

  • 完全二叉树(Complete Binary Tree)
    有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为 $i(1\le i\le n)$ 结点与满二叉树中编号为i结点在二叉树中位置相同
符合完美二叉树 不符合完美二叉树
符合完美二叉树 不符合完美二叉树

二叉树几个重要性质

  • 一个二叉树第i层的最大结点数为：$2^{i-1},i\ge1$ 。
  • 深度为K的二叉树有最大结点总数为：$2^{k}-1,k\ge1$ 。
  • 对任何非空二叉树T，若 $n_0$ 表示叶结点的个数、 $n_2$ 是度为2的非叶结点个数，那么两者满足关系 $n_0=n_2+1$ 。

二叉树的抽象数据类型定义

类型名称：二叉树
数据对象集：一个有穷的结点集合。
若不为空，则由根结点和其左、右二叉子树组成。

操作机：$BT \in BinTree,Item \in ElementType,$ 重要操作有：

  1. Boolean IsEmpty(BinTree BT): 判别BT是否为空；
  2. void Traversal(BinTree BT): 遍历，按某顺序访问每个结点；
  3. BinTree CreatBinTree(): 创建一个二叉树。

常用的遍历方法有：

  • void PreOrderTraversal(BinTree BT): 先序—-根、左子树、右子树；
  • void InOrderTraversal(BinTree BT): 中序—-左子树、根、右子树；
  • void PostOrderTraversal(BinTree BT): 后序—-左子树、右子树、根；
  • void LevelOrderTraversal(BinTree BT): 层次遍历，从上到下、从左到右

二叉树的存储结构

1.顺序存储结构
完全二叉树：按从上至下、从左到右顺序存储，n个结点的完全二叉树的结点父子关系：

  • 非根结点(序号i>1)的父结点的序号是[ i/2 ]；
  • 结点(序号为i)的左孩子结点的序号是2i，(若 $2i\le n,$ 否则没有左孩子)；
  • 结点(序号为i)的右孩子结点的序号是 2i+1,(若$2i+1\le n$,否则没有右孩子)；

队列及实现

队列(Queue): 具有一定操作约束的线性表

  • 插入和删除操作： 只能在一端插入，而在另一端删除。

  • 数据插入：入队列（AddQ）

  • 数据删除：出队列（DeleteQ）

  • 先来先服务

  • 先进先出：FIFO

to be continued…