数据结构与算法复习笔记

前言：数据结构与算法作为计算机经典的基础理论课程，同时作为计算机类专业考研课程，并且在校招面试时常被提及，其重要性可见一斑。除此之外，学习这门课程有助于我们用编程去解决、思考问题，设计出更简洁、效率更高的代码。

一.课程概述

数据结构课程研究什么？
- 内存中基本数据组织和数据处理的方法
- 非数值问题
通过学习数据结构获得什么？
- 经典数据结构和经典算法的基本原理
学习重点
- 数据结构的逻辑特性和存储结构设计
- 数据结构算法设计基本方法和分析方法
- 利用数据结构解决实际问题

二.基本概念与术语

数据
- 能输入到计算机中，被程序识别和处理的一切事物的符号化表示
数据元素
- 数据的基本单位
数据项
- 构成数据元素的最小单位
存储结构（由想法到算法）
- 顺序存储结构
- 链式存储结构
逻辑结构（由问题到想法）
- 一种逻辑结构可由多种存储结构实现
数据结构
- 逻辑结构
- 存储结构
- 数据运算

抽象数据类型（ADT）

ADT 抽象数据类型名{
	数据对象的定义
	数据元素之间的逻辑关系定义
	基本运算定义
}ADT

算法的定义
- 基于存储结构的运算实现的步骤
- 满足有穷性、确定性、可行性
- 有0个或多个输入，1个或多个输出
什么是好的算法
- 正确性：对于合法输入，算法能得出正确结果
- 健壮性：对于非法输入，算法能做出特别处理
- 可理解性：算法容易理解、实现
- 高效性：具有较短执行时间并占用较少空间
- 可修改、可拓展性

三.算法分析

时间复杂度
- 是算法求解问题规模n的函数，T(n)=F(n)，F(n)是基本语句的执行频度
- 增长率：忽略低次幂和最高次幂系数
分析规则
- 加法规则：针对并列程序段
- 乘法规则：针对嵌套程序段

例子

++x;  //复杂度O(1)

for(i=1;i<=n;++i)
++x;  //复杂度O(n)

for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
++x;  //复杂度O(n²)

常见的时间复杂度

1	O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!)

空间复杂度
- 除去输入输出占用空间，算法临时占用的存储空间
- S(n)=O(f(n))

四.线性表

线性表的逻辑结构

线性表：n(n>=0)个具有相同结构的数据元素的有限序列
a1为表头元素，an为表尾元素
直接前驱元素、直接后继元素

线性表的顺序存储

用一段地址连续的存储单元
用什么属性描述顺序表
- 存储空间的起始位置s
- 顺序表的容量
- 顺序表当前长度

声明顺序表

#define MaxSize 100 /*假设顺序表最多100个元素*/
typedef int ElemType; /*假设数据元素为int型*/
typedef struct
{
	ElemType data[MaxSize];	/*存放数据元素的数组*/
	int length;		/*线性表长度*/
}SqList;

定义顺序表

SqList *L;
L-> data[0]	//表头元素
L-> data[L->length-1] //表尾元素
L-> length	//表长

访问第i个元素（时间复杂度o(1)）

1 2	地址Loc(ai)=Loc(a1)+(i-1)*单位长度d 存取时间为O(1)

初始化顺序表

int initList(SqList *L)
{
	/*建立一个空表，成功返回1，否则返回0*/
	L=(SqList*)malloc(sizeof(SqList));
	if(!L) return 0; //分配失败
	L-> length = 0;
	return 1;
}

按值查找（时间复杂度o(n)）

int Locate(SqList *L, ElemType x)
{
  /*查找成功返回x，否则返回0*/
  int i=1;
  while(i<=L->length && L->data[i-1]!=x)
    i++;

  if(i>L->length)	return 0;
  else return i; /*返回存储位置*/
}

顺序插入（时间复杂度o(n)）

int Insert(SqList *L, int i, ElemType x)
{
	/*在表中第i个元素前插入x*/
	int m;
	if(L->length >= MaxSize){
		printf("上溢错误，插入失败\n");
		return 0;
	}
	if(i<1||i>L->length + 1){
		printf("位置错误，插入失败\n");
		return 0;
	}
	for(m=L->length; m>=i; m--)
		L->data[m] = L->data[m-1];
	L->data[i-1] = x;
	L->length++;
	return 1;
}

删除

int delete(SqList *L, int i, ElemType &e)
{
	/*删除表中第i个元素*/
	if(i<1||i>L->length){
		printf("位置错误，删除失败\n");
		return 0;
	}
	e=L->data[i-1];
	for(i;i<=L->length-1;i++)
		L->data[i-1] = L->data[i];	//结点前移
	L->length--;	//表长减1
	return 1;
}

线性表的链式存储

单链表的存储结构定义

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode;
LNode *L;
L->next	//表中第一个元素
L->next->data  //第一个元素值

单链表初始化

LNode *InitList(){
	LNode *L;
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	return L;
}

求单链表长

int Listlength(LNode*L){
	LNode *p;
	count=0; p=L;
	while(p->next != NULL){
		count++;
		p=p->next;
	}
	return count;
}

按位置查找

LNode*GetItem(LNode*L, int i){
	LNode*p=L->next;
	int count =1;
	while(p!=NULL&&count<i)
	{
		count++;
		p=p->next;
	}
	if(p==NULL){
		printf("位置错误，查找失败\n");
		return p;
	}
	else return p;
}

按值查找

LNode*Locate(LNode*L, ElemType x){
	LNode*p;
	p=L->next;
	while(p!=NULL && p->data!=x)
		p=p->next;
	return p;
}

插入

int insert(LNode*L,int i,ElemType x){
	LNode *s=NULL, *p=L;
	int count = 0;
	while(p!=NULL&&count<i-1) //查找第i-1个结点
	{
		p=p->next;
		count++;
	}
	if(p == NULL){
		printf("位置错误,插入失败");
		return 0;
	}
	else{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}

删除

int Delete(LNode*L, int i, ElemType &e){
	LNode *p=L, *q=NULL;int count=0;
	while(p->next!=NULL&&count<i-1)
	{
		p = p->next;
		count++;
	}
	if(p == NULL||count>i-1){
		printf("位置错误，删除失败\n");
		return 0;
	}
	else{
		q = p->next; e = q->data;//存储被删结点与被删元素值
		p->next = q->next;
		free(q);
		return 1;
	}
}

建立单链表

头插入法

LNode*CreateList(ElemType a[], int n){
	LNode *s = NULL;
	LNode *L = (Lnode*)malloc(sizeof(LNode));
	L->next = NULL;
	for(int i=0;i<n;i++){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=a[i];
		s->next = L->next;
		L->next = s;
	}
	return L;
}

尾插入法

LNode*CreateList(ElemType a[], int n){
	LNode*s = NULL, *rear = NULL;
	LNode*first = (Lnode*)malloc(sizeof(LNode));
	rear = first;
	for(int i=0;i<n;i++){
		s = (LNode*)malloc(sizeof(LNode));
		s->data=a[i];
		rear->next = s;
		rear = s;
	}
	rear->next = NULL;	//尾端结点指针域置空
	return first;
}

顺序表与链表时间复杂度

五.栈与队列

栈的定义
- 是一种特殊的线性表，限定在表的一端插入和删除
- 允许插入、删除的一端为栈顶，另一端为栈底

栈的基本运算

InitStack(&s)     栈的初始化
DestoryStack(&s)  销毁栈s
Push(&s,e)        进栈
Pop($s)           出栈
GetTop(S)         取栈顶元素
IsEmpty(S)        判栈空否

栈中元素逻辑关系与线性表相同，可采用与线性表相同的存储结构
1、2、3、4个元素进栈，出栈组合分别有1、2、5、14种

顺序栈

利用一组地址连续的存储单元依次存放栈元素

附设指针top指示栈顶位置

/*存储空间初始分配量*/
#define StackInitSize 100
typedef int SElemtype;
typedef struct{
	SElemtype data[StackInitSize];
	int top;	/*栈顶指针*/
}SeqStack;

入栈

//当top=maxsize-1，栈满，再入栈则上溢
void Push(SeqStack *s, SElemType x){
	if(s->top == StackInitSize){
		printf("栈满，上溢!\n");
		exit(0);
	}
	s->data[++s->top] = x;
}

出栈

//若栈空，再出栈则下溢
SElemtype Pop(SeqStack *s)
{
	SElemtype temp;
	if(s->top==-1){
		printf("栈空，下溢！\n");
		exit(0);
	}
	else{
		temp=s->data[s->top--];
		return temp;
	}
}

链栈

存储结构

typedef int SElemtype;
typedef struct node{
	SElemtype data;	/*存放栈元素的数据域*/
	struct node *next;	/*存放下一个结点地址*/
}LinkStack;
LinkStack *top;

入栈

LinkStack *Push(LinkStack *top, SElemtype x)
{
	LinkStack *p;
	p=(LinkStack*)malloc(sizeof(LinkStack));
	if(p){
		p->data=x;
		p->next=top;
		top=p;
		return top;
	}
	else{
		printf("内存空间不足，运行终止！\n");
		exit(0);
	}
}

出栈

LinkStack *Pop(LinkStack *top, SElemtype *elem){
	LinkStack *temp;
	if(top){
		temp=top;
		*elem=top->data;	/*保存栈顶元素*/
		top=top->next;	/*栈顶指针下移*/
		free(temp);
		return top;
	}
}

顺序栈与链栈异同

时间复杂度均为O(1)
空间性能有差异，顺序栈有元素个数限制和空间浪费问题，而链栈则是每个元素需要一个指针域，产生结构性开销

栈的应用举例

后放入数据需要先处理，使用栈
如十进制转换为二进制问题

队列

一种运算受限的线性表，只允许在一端删除，另一端插入
允许删除的一端叫队头
允许插入的一端叫队尾

先进先出原则

1 2	队列中元素逻辑关系与线性表相同可采用与线性表相同的存储结构

循环队列

队列的顺序存储：利用地址连续存储单元依次存放队列各元素
设front,rear分别指示队头、队尾位置

存储结构定义

define MaxSize 100
typedef struct{
	Elemtype data[MaxSize];
	int front;	/*队头指针*/
	int rear;		/*队尾指针*/
}SqQueue;

入队
- 元素入队
- rear+1 改为 (rear+1)%MaxSize
出队
- 元素出队
- front+1 改为(front+1)%MaxSize
队空条件：front == rear
队满条件：front == (rear+1)%MaxSize
队列长度：(MaxSize+rear-front)%MaxSize

初始化

SqQueue Init_SqQueue()
{
  SqQueue Q;	/*申请存储空间*/
  Q.base=(QElemtype*)malloc(Maxsize*sizeof(QElemtype));
  if(!Q.base)
  	exit(overflow);
  Q.front = Q.rear =0;
  return Q;
}

入队

SqQueue EnSqQueue(SqQueue Q,Elemtype x)
{
	if(Q.front == (Q.rear+1)%MaxSize)
		return Error;	/*栈满不能入队*/
	else{
		Q.data[Q.rear] = x;	/*插入元素存入队尾*/
		Q.rear = (Q.rear+1)%MaxSize;
	}
	return Q;
}

出队

SqQueue DeSqQueue(SqQueue Q,Elemtype &e)
{
	if(Q.front == Q.rear)
		return Error;	/*队空*/
	else{
		e=Q.data[Q.front];	/*取出队头元素*/
		Q.front = (Q.front+1)%MaxSize;	/*修改头指针，出队完成*/
	}
	return Q;
}

链式队列

存储特点
- 队头在链头，队尾在链尾

结点存储结构定义

typedef struct Qnode
{
	QElemtype data;
	struct Qnode* next;
}Qnode,*Queueptr;

初始化链式队列

Queueptr InitQueue()
{
  LinkQueue Q;
  /*申请头尾指针结点*/
  Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode));
  Q.front->next=NULL; /*头结点指针域置空*/
  return Q;
}

链尾插入元素（入队）

Queueptr EnQueue(LinkQueue Q, QElemtype x){
  P = (Queueptr)malloc(sizeof(Qnode));
  if(!P)
    exit(overflow);
  P->data = x;
  P->next = NULL;
  Q.rear->next = P;
  Q.rear = P;
  return Q;
}

出队

Queueptr DeQueue(LinkQueue Q, QElemtype &e){
  if(Q.front == Q.rear)
    return ERROR;	 /*队列为空*/
  P = Q.front -> next;	/*P指向队头结点*/
  e = P->data;
  Q.front->next = P->next;
  if(Q.rear == P)		/*P为队中最后一个结点*/
    Q.rear = Q.front
  free(P);
  return Q;
}

若元素个数变化大，用链式队列，否则用 循环队列 。

四.数组和矩阵的压缩存储

4.1 数组的定义和实现

数组：可看成是特殊的线性表，特殊在于表中的数据元素本身又可以是一个线性表
一维数组：可以看成是一个具有相同类型的数据元素构成的线性表，在计算机内存放在一块连续的存储单元中，适合随机存取
一维数组a[n]，第一个元素a0的存储地址是Loc(a0) ，也可以用a表示，每个元素占用存储空间大小为l，则第i个元素ai的地址是：

$Loc(a_i)=a+i*l$
若数组A[m][n]按行优先顺序存储，则aij地址为 Loc(a00)+i*n+j
若数组A[m][n]按列优先顺序存储，则aij地址为 Loc(a00)+j*m+i
二维数组（矩阵）：当一维数组中的数据元素再存放一个一维数组
二维数组通常有两种顺序存储方式：
- 行优先顺序
- 列优先顺序

4.2 矩阵的压缩存储

对称矩阵的压缩存储

一个n阶方阵中，若元素满足下述性质：aij=aji(0≤i, j≤n-1)，则其为对称矩阵
依次存储在sa[n(n+1)/2]中
在aij和sa[k]中找对应关系，注意这里i和j均以0开始，转换的k也是从0开始
- 若i≥j，则k=i*(i+1)/2+j 0≤k≤n(n+1)/2
- 若i＜j，则k=j*(j+1)/2+i 0≤k≤n(n+1)/2

稀疏矩阵的压缩存储

矩阵阶数很大，非零元素个数较少，零元素较多，这类矩阵称为稀疏矩阵

使用三元组压缩矩阵

struct triple{
	int i,j;	//行号、列号
	int v;		//值
};
triple data[100];	//三元组表

五.递归

5.1 递归的定义

若一个过程直接或间接的调用自己，则称这个过程为递归过程
例如阶乘、斐波那契数列等都可以用递归计算
许多数据结构是递归的：链表

5.2 递归的工作原理和实现形式

每个函数通常包含返回地址、局部变量、形式参数、返回值，包含这些信息的结构位于运行栈中，称为这个函数的活动记录
函数调用时的运行栈

5.3 分治法与递归思想

一个问题若可以用分治法解决，那么就可以用递归算法实现
前面所学的阶乘函数、幂函数、单链表遍历、汉诺塔等问题都可以用分治法解决

六.树和二叉树

6.1 树的定义与基本概念

树的基本概念

是n(n＞0)个结点（数据元素）的有限集合，有且仅有一个称为根的结点
树中的各子树互不相交（结点不能属于多个子树，子树之间不能有关系）
基本术语
- 结点的度：结点所拥有的子树的个数
- 树的度：树中各结点度的最大值
- 叶子结点：度为0的结点，也称为终端结点
- 分支结点：度不为0的结点，称为非终端结点
- 孩子、双亲
- 兄弟结点：具有同一个双亲的结点
- 路径、路径长度
- 祖先、子孙
- 森林：m(m≥0)棵互不相交的树的集合
- 结点层数：若某结点在k层，孩子结点在k+1层
- 树的深度（高度）：树中所有结点最大层数
- 树的宽度：树中每层结点个数最大值
线性结构与树结构比较
- 线性结构：表头无前驱，表尾无后继，其他元素有一个前驱和一个后继
- 树结构：根节点无双亲，叶子结点无孩子，其他结点有一个双亲和多个孩子

树的抽象数据类型定义

ADT Tree
{
	InitTree: 初始化一棵树
	DestroyTree: 销毁一棵树
	PreOrder: 前序遍历树
	PostOrder: 后序遍历树
	LeverOrder：层序遍历树
}ADT Tree

树的性质
- 1.树的结点数=分支数+1
- 2.度为k的树中第i层上最多有k^(i-1)个结点（i≥1）
- 3.高度为h的k叉树最多有(k^h-1)/(k-1)个结点
- 4.具有n个结点的k叉树最小高度为
  
  $log_k(n(k-1)+1)$

树的存储结构

双亲表示法：用连续的空间存储树的结点，每个结点增设指示器指示双亲结点位置（双亲在数组中的下标）

查找双亲 o(1)

查找孩子 o(n)
1
2
3
4
5
6
7
8
/*定义树的双亲表示法*/
#define MaxSize 100
typedef char DataType;
typedef struct{
DataType data;
int parent;
}PNode;
PNode tree[MaxSize];

孩子表示法：每个结点设多个指针指向各个孩子

方案一：指针域的个数等于树的度，缺点：浪费空间，可能存在空指针

方案二：指针域的个数等于该结点的度，缺点：结点结构不一致

改进：孩子链表表示法，将结点的所有孩子构成一个单链表

/*定义树的孩子表示法*/
#define MaxSize 100
typedef char DataType;
typedef struct ChildNode{
  int child;
  struct ChileNode *next;
}ChildNode;
typedef struct{
  DataType data;
  ChildNode *first;
}TreeNode;
TreeNode tree[MaxSize];

孩子兄弟表示法：链表中的每个结点包括数据域和分别指向该结点第一个孩子和右兄弟的指针

typedef char DataType;
typedef struct CSNode{
	DataType data;
	struct CSNode*firstchild, *rightsib;
}CSNode;
CSNode *root;

6.2 二叉树

二叉树及其存储

定义：n(n≥0)个结点的有限集合，该集合或者为空集，或者由一个根节点和两颗互不相交的、分别称为根的左子树和右子树的二叉树组成
满二叉树

一棵深度为k且有2^k-1个结点的二叉树（每层结点数都达到最大值）
完全二叉树

设二叉树高度为h，除第h层外各层都满，第h层从右向左连续缺失若干结点
性质
- 1.若二叉树层次从1开始，二叉树第i层上最多有2^(i-1)个结点(i≥1)
- 2.一棵深度为k的二叉树最多有2^k-1个结点
- 3.在任何一棵二叉树中，若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1
- 4.具有n个结点的完全二叉树深度为log2n+1

二叉树抽象数据类型定义

ADT BiTree{
    InitBiTree:初始化一棵空的二叉树
    CreateBiTree:建立一棵二叉树
    DestroyBiTree:摧毁一棵二叉树
    PreOrder:前序遍历二叉树
    InOrder:中序遍历二叉树
    PostOrder:后序遍历二叉树
    LevelOrder:层序遍历二叉树
}ADT BiTree;

二叉树的顺序存储

用一组连续存储单元依次存储元素，由存储位置表示元素间德逻辑关系

存储方式：对一棵二叉树，按照与其等深度的完全二叉树层序编号方式进行编号，将各结点的值存放在一个一维数组中，如下图所示：

二叉链表存储结构

二叉树的每个结点对应一个链表结点，链表结点存放结点的数据信息和指示左右孩子的指针

/*二叉链表数据类型定义*/
typedef char DataType;
typedef struct BiNode{
  DataType data;
  struct BiNode *lchild, *rchild;
}BiNode;

三叉链表：在二叉链表的结点基础上添加parent指针域
思考：n个结点的二叉链表有几个空指针域？

可以这样理解，n个结点的二叉链表共有2n个指针域，即2n条线段。而树中线段数+1=结点数，因此树中线段数=n-1，空指针域个数=2n-(n-1)=n+1个

二叉树的遍历

从根节点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次

二叉树的前序遍历

过程：DLR

访问根节点(D)

前序遍历左子树(L)

前序遍历右子树(R)

void PreOrder(BiNode *root){
  if(root==NULL){
    return;
  }
  else{
    printf("%c",root->data);	/*在这访问*/
    PreOrder(root->lchild);
    PreOrder(root->rchild);
  }
}

二叉树的中序遍历

过程：LDR

中序遍历左子树(L)

访问根结点(D)

中序遍历右子树(R)

void InOrder(BiNode *root){
  if(root==NULL){
    return;
  }
  else{
    InOrder(root->lchild);
    printf("%c",root->data);	/*在这访问*/
    InOrder(root->rchild);
  }
}

二叉树的后序遍历

过程：LRD

后序遍历左子树(L)

后续遍历右子树(R)

访问根节点(D)

void PostOrder(BiNode *root){
  if(root==NULL){
    return;
  }
  else{
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%c",root->data);	/*在这访问*/
  }
}

二叉树的创建

BiNode * CreateBiTree(){
  BiNode *root;
  char ch;
  scanf(ch);
  if(ch=='#') root=NULL;	/*递归结束，建立一棵空树*/
  else{
    root=(BiNode*)malloc(sizeof(BiNode));
    root->data=ch;
    root->lchild=CreateBiTree();	/*递归建立左子树*/
    root->rchild=CreateBiTree();	/*递归创建右子树*/
  }
  return root;
}

6.3 线索二叉树

定义：为了保留结点在某种序列的直接前驱和直接后继的位置信息，可利用二叉链表存储结构的n+1个空指针域来指示。这些指向直接前驱和直接后继结点的指针被称为：线索 (thread)，加了线索的二叉树称为 线索二叉树。
如何区别指针域内放的是指针还是线索？

为每个结点增设两个标志位ltag和rtag即可，如下图所示
二叉树的线索化——穿线

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

树转换为二叉树

以二叉树的孩子兄弟表示法为基础进行转换，即树的兄弟关系 ↔ 二叉树的双亲和右孩子，双亲和长子 ↔ 双亲和左孩子

步骤如下

（1）加线——树中所有相邻兄弟之间加一条线

（2）去线——对树的每个结点，只保留它与第一个孩子之间的连线，删去它与其他孩子结点间的连线

（3）层次调整——以根节点为轴心，将树顺时针转动一定角度，使之层次分明

森林转换为二叉树

步骤如下

（1）将森林中的每棵树转换为二叉树

（2）将每棵树的根节点视为兄弟，在所有根结点之间加上连线

（3）按照二叉树结点之间的关系进行层次调整

二叉树转换为森林

步骤如下

（1）加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子（的右孩子…）全部与结点y连线

（2）去线——删去所有双亲结点与右孩子结点的连线

（3）层次调整——整理由(1)(2)所得到的树（森林），使之层次分明

树的遍历

树的先根(前序)遍历：若树非空，则先访问根，然后从左到右先根遍历每棵子树（等价于二叉树的前序遍历）
树的后根(后序)遍历：若树非空，则先从左到右依次后根遍历每棵子树，再访问根（等价于二叉树的中序遍历）

森林的遍历

先根次序遍历规则：若森林F为空，返回；否则：

访问F的第一棵树的根结点

先根遍历第一棵树的子树森林

先根遍历其它树组成的森林

（等价于二叉树的前序遍历）
中根次序遍历规则：若森林F为空，返回；否则：

中根次序遍历第一棵树的子树森林

访问F的第一棵树的根结点

中根次序遍历其它树组成的森林

（等价于二叉树的中序遍历）

6.5 哈夫曼树及其应用

哈夫曼Huffman树

什么是最优二叉树？

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

二叉树的带权路径长度：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和
因此最优二叉树定义如下

给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树
最优二叉树特点

（1）权值越大的叶子结点越靠近根结点

（2）只有度为0和度为2的结点，不存在度为1的结点
哈夫曼树构造方法(略，见离散数学课本)

如何存储哈夫曼树？

哈夫曼树共有 2n-1个结点

typedef struct{
  int weight; /*假定权值为整数*/
  int parent, lchild, rchild;
}HTNode;
HTNode HT[2n-1];

哈夫曼算法

void HuffmanTree(HTNode HT[], int w[], int n){
  int i, s1, s2;
  for(i=0;i<2*n-1;i++){	/*初始化，所有结点没双亲和孩子*/
    HT[i].parent=-1;
    HT[i].lchild=-1;
    HT[i].rchild=-1;
  }
  for(i=0;i<n;i++){		/*构造n棵只含有根结点的二叉树*/
    HT[i].weight=w[i];
  }
  for(i=0;k<2*n-1;i++){	/*n-1次合并*/
    Select(HT,s1,s2);	/*权值最小的两个根结点下标为i1和i2*/
    HT[i].weight=HT[s1].weight+HT[s2].weight;
    HT[i].lchild=s1;
    HT[i].rchild=s2;
    HT[s1].parent=i;
    HT[i2].parent=i;
  }
}

哈夫曼树应用举例

数据通讯问题

字符–(编码)–>二进制位串(电文)–(解码)–>字符
等长编码

优点：好译码；缺点：电文长，不利于传输实时数据
非等长编码：让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长编码

优点：缩短总电文长度；缺点：译码困难，可能存在多义性

要解决译码困难问题，要保证一组编码的任意字符编码都不是其他任何字符编码的前缀
利用哈夫曼树设计最优前缀编码

例：已知一段原文 CAS;CAT;SAT;AT ，为其设计最优编码

字符集合是{A,C,S,T, ;}，各个字符出现的频度为w={4,2,2,3,3}

七.图

7.1 图的定义与基本术语

定义

图示由顶点集合及顶点间的关系集合组成的一种数据结构，Graph=(V,E)，其中V是某个数据对象中的顶点有限非空集合，E为顶点之间关系的有限集合
图的逻辑结构

任意两个顶点之间都可能有关系，逻辑关系表现为邻接
图的术语
- 有向图：若用箭头表明了边有方向，称为有向图，否则称为无向图
  
  边<x,y> <y,x>不同，用< >表示，有向边也称为弧，如<x,y>中的x为弧尾，y为弧头
- 无向图：没有箭头指明边有方向
  
  边(x,y) (y,x)相同，用( )表示
- 完全无向图：具有n个顶点，n(n-1)/2条边的无向图
- 完全有向图：具有n个顶点，n(n-1)条弧的有向图，称为完全有向图
- 以上两种图统称为完全图，当一个图接近完全图时，称为稠密图，当一个图的边或弧较少，称为稀疏图
- 在图的边或弧上给出相关数值，称为权，带权图称为网络
- 若有两个图G1和G2，G1=(V1,E1)，G2=(V2,E2)，满足如下条件：V2⊆V1，E2⊆E1，即V2为V1的子集，E2为E1的子集，称图G2是图G1的子图
- 度：一个顶点依附的边的数目
- 入度：有向图中，指向顶点的弧的数目称为该顶点的入度
- 路径、回路（环）
- 连通图：任意两个顶点能连通（单向即可）；强连通图：任何一对顶点相互之间都有路径连接（必须双向）
结论

若图有n个顶点，e条边或弧，则有e=1/2∑di （di为顶点i的度）

7.2 图的存储结构

邻接矩阵表示法

首先，在图中任意两个顶点都可能存在关系（边），因此无法采用顺序结构存储图
用一个矩阵，若<i,j>有关系，则在矩阵中的i,j坐标上标1
无向图邻接矩阵特点

1.矩阵对称

2.第i行或第i列1的个数为顶点i的度

3.矩阵中1的个数的一半为图中边的数目
有向图邻接矩阵特点

1.矩阵不对称

2.第i行1的个数为顶点i的出度

3.第i列1的个数为顶点的入度

图的邻接矩阵存储结构

#define INFINITY INT_MAX	/*最大值*/
#define MAX_VERTEX_NUM 20	/*最大顶点数*/
typedef enum {DG,DN,AG,AN} GraphKind;	/*{有向图 有向网 无向图 无向网}*/

typedef struct Arc{
  VRType adj;	/*VRType是顶点关系类型*/
  InfoType *info;	/*指向边或弧所代表的信息的指针*/
}Arc, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
  VertexType vertex[MAX_VERTEX_NUM];	/*顶点数组*/
  AdjMatrix arcs;	//邻接矩阵
  int vexnum, arcnum;	//定点数、弧边数
  GraphKind kind;	//图的种类
}Graph;

建立无向图的邻接矩阵 - 算法复杂度o(n²) - 适合稠密图

void CreateAG(Graph &G){
  for(i=0; i<n; i++){
    cin>>G.vertex[i];	/*构造顶点*/
  }
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      G.arcs[i][j] = {0,NULL};	/*邻接矩阵初始化*/
    }
  }
  for(i=0; i<e; i++){
    cin>>i>>j>>info;	/*输入边i,j和所代表的信息*/
    G.arcs[i][j]=G.arcs[j][i]={1,info};
  }
}

邻接表表示法

边链表：顶点v的所有邻接点链接成的单链表
顶点表：所有边表的头指针和存储顶点信息的一维数组
无向图邻接表特点

1）第i个链表中的结点数等于顶点i的度

2）所有链表的结点数目的一半为图的边数

3）占用存储单元n+2e
有向图邻接表特点

1）第i个链表的结点数等于顶点i的出度

2）所有链表中的结点数目为图中弧数

3）占用存储单元n+e
注意：邻接表不唯一，n个顶点的无向图的邻接表最多有n(n-1)个表结点，适合稀疏图的存储

7.3 图的遍历

图的深度优先遍历（DFS）

图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，使图中某个顶点仅被访问一次的过程

深度优先遍历（DFS）

即选取某一顶点，按照某种顺序（例如上右下左）访问该结点的邻接点，若有则继续向下搜索，若没有需回溯

void DFS(Graph G, int v){	/*从顶点v出发*/
  visited[v] = TRUE;
  visit(v);	/*访问结点*/
  for(w=FirstAdjVex(G, v); w!=0; 2=NextAdjVex(G,v,w)){
    /*对v未访问的邻接点w递归调用DFS*/
    if(!visited[w])	DFS(G,w);
  }
}

深度优先遍历结果不唯一，但如果具有特定的存储结构，则遍历结果唯一！
时间复杂度分析

图的邻接表：共有2e个边结点，扫描边的时间为o(e)，对所有顶点递归访问1次，遍历图的时间复杂度为o(n+e)

图的邻接矩阵：查找每一个顶点的所有的边，所需时间为o(n)，遍历图中所有顶点所需时间o(n²)

图的广度优先遍历（BFS）

选取某一初始点v，访问v所有未被访问过的邻接点v1,v2,…,vn，然后按照v1,v2,…,vn的顺序，依次再访问每个结点所有未被访问的邻接点
体现了先进先出的特点，可用队列实现
广度优先遍历结果不唯一，但如果给定图的存储结构，则从某一顶点出发遍历结果唯一
时间复杂度分析

邻接表：o(e)

邻接矩阵：o(n²)

7.4 图的生成树与最小生成树

生成树相关概念

生成树概念

给定一个无向连通图G(V,E)，它的一个连通子图G’=(V,F)，如果包含G中所有顶点的树，则该子图为G的生成树

同时，生成树也是包含全部顶点的一个极小连通子图（不构成回路即可）
最小生成树概念

无向连通图的所有生成树中，必有一棵边的权值总和最小的生成树，称为最小生成树（MST）

Prim算法

步骤如下

1）从连通图G=(V,E)中的某一顶点u0出发，初始化生成树顶点集合U={u0}，集合V-U

2）找一条边，该边是集合U到集合V-U中的任意一个点最短边

3）重复步骤2，知到图中所有顶点都加入到图中

总结：以点为起始点出发找边，与边数无关，时间复杂度o(n²)，适用于稠密图采用邻接矩阵存储

Kruskal算法

步骤如下

1）先构造一个只有n个顶点的，没有边的非连通图，则每个顶点都是一个连通分量

2）选取一条最小权值边，若该边落在两个不同的连通分量，则保存，否则舍去再选一条权值最小的边

3）重复步骤2，直到所有顶点都在同一个连通分量上为止

总结：找最小权值边连接不同连通分量，与边数有关，时间复杂度o(eloge)，适用于稀疏图采用邻接表存储

7.5 拓扑排序

定义

将一个有向图中所有顶点在不违反先决条件的情况下，排列成一个线性序列的过程称为拓扑排序
AOV网：在一个有向图中，顶点表示活动，弧表示活动的先后关系，这种有向图叫AOV网，但AOV网 不一定是有向无环图 ，若存在环则无法形成拓扑序列
拓扑排序算法

1）在AOV网中选一个没有前驱（入度为0）的顶点并输出

2）删除该顶点和它的出弧（出弧所指向的顶点入度减1）

3）重复以上两个步骤，直到全部定点均输出，形成拓扑序列

7.6 最短路径

最短路径问题和Dijkstra算法

单源最短路径问题

给定一个带权的有向网络G和G上的一个出发点（源点），求从这个源点到其他各顶点之间的最短路径
Dijkstra算法（时间复杂度o(n²)）

Floyd算法

求每一对顶点之间的最短路径问题

若用Dijkstra算法和Floyd算法，时间复杂度均为o(n³)
Floyd算法

略

八. 查找

8.1 查找的基本概念

查找

在相同类型的记录构成的集合中找出满足给定条件的记录，其中又分为动态查找（涉及插入和删除）和静态查找
查找结构

面向查找操作的数据结构
查找基于的数据模型——集合

1）线性表：适用于静态查找、顺序查找、折半查找等技术

2）树表：适用于动态查找、二叉排序树的查找技术

3）散列表：静态查找和动态查找均适用，采用散列技术
评判查找算法的效率——平均查找长度

查找算法进行的关键码比较次数的数学期望值

8.2 线性表的查找

顺序查找

基本思想

从线性表一端到另一端逐个进行对比
适用的数据结构

顺序表、线性链表
改进—设置"哨兵"，免去每次比较要判断查找位置是否越界
查找性能 / 插入删除性能

时间复杂度O(n) / O(1)
优点

1）顺序存储和链接存储都可以使用

2）记录是否按关键码有序都可以使用
缺点

集合元素较多时，性能较差

折半查找（二分查找）

基本思想

在有序表中取中间记录作为比较对象，若相等则查找成功，否则查找左半侧或右半侧的中间记录…
适用的数据结构

顺序存储的有序表
查找性能 / 插入删除性能

时间复杂度O(log2n) / O(n)
优点

查找效率高
缺点

需要先排序，而排序本身需要耗费时间，仅适合经建立后很少改动、但需经常查找的线性表

分块查找

基本思想

1）将长度为n的查找表R[n]分成b块，要求每一块中元素不一定有序，但前一块最大关键字要小于后一块最小关键字

2）建立索引表ID[b]，其中ID[i]存放第i块中的最大关键字及该块的起始位置下标

3）查找索引表以确定待查结点在哪个分块，然后在块中顺序查找
优点

把线性表分为若干个逻辑子表，提高查找效率
缺点

增加了索引存储空间，需要将表分块

8.3 树表的查找

二叉排序树

二叉搜索树

1）每个结点都有一个关键码，所有结点关键码互不相同

2）左子树上所有结点关键码小于根结点关键码

3）右子树上所有结点关键码大于根结点关键码

4）左子树和右子树也是二叉搜索树

简单来说，二叉搜索树中结点值左<根<右（中序遍历可得有序序列）

BiNode *SearchBST(BiNode *root, int k){
  if(root==NULL)	return NULL;
  if(root->data==k) return root;
  else if(root->data>k) return SearchBST(root->lchild, k);
  else if(root->data<k) return SearchBST(root->rchild, k);
}

二叉排序树的插入

void InsertBST(BiNode *root, int x){
  if(root==NULL){
    BiNode *s = (BiNode*)malloc(sizeof(BiNode));
    s->data = x;
    s->lchild = s->rchild =NULL;
    root = s;
  }else if(root->data > x){
    InsertBST(root->lchild, x);
  }else{
    InsertBST(root->rchild, x);
  }
}

二叉排序树的删除（设p是f的左孩子，待删除结点为p）

1）被删除结点是叶子结点

操作：将双亲结点中相应指针域值改为空

2）被删除的结点只有左子树或右子树

操作：f->lchild=p->lchild，即将双亲结点中相应指针域指向被删除结点左(右)子树

3）被删除结点左右孩子均有

最好方案：用左子树中最右元素替换p结点，如下图所示

void DeleteBST(BiNode *p, BiNode*f){
  BiNode *par=p, *s=p->lchild;
  if((p->lchild)==NULL && (p->rchild)==NULL){
    //p结点为叶子
    f->lchild=NULL;	free(p); return;
  }
  if(p->rchild==NULL){
    //p只有左子树
    f->lchild=p->lchild; free(p); return;
  }
  if(p->lchild==NULL){
    //p只有右子树
    f->rchild=p->rchild; free(p); return;
  }else{
    //p左右子树都有
    s=p->lchild;
    while(s->rchild!=NULL){par =s; s=s->rchild;}
    p->data = s->data;
    if(par==p) par->rchild=s->lchild;
    else par->lchild=s->lchild;
    free(s);
  }
}

二叉排序树性能分析

插入、删除、查找时间复杂度相同，与树的深度有关

最坏情况：变为线性查找

最好情况：折半查找

平均情况时间复杂度：O(n)~O(log2n)

平衡的二叉排序树

结点的平衡因子：任一结点的左子树深度减去右子树深度所得的高度差
平衡二叉树：或者是一棵空的二叉排序树，或者是具有以下性质的二叉排序树：

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

2）根结点的左子树和右子树也是平衡二叉树
最小不平衡子树：以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树

调整：LL、RR型调整一次，LR、RL型调整两次
性能分析

AVL树查找性能优于一般的二叉排序树，不会出现二叉排序树最坏O(n)的情况，而是O(log2n)，但插入时要进行平衡化，可将平衡因子适当放大

B树的插入

B树

一棵m阶的B树是一棵平衡的m叉搜索树，它或者为空树，或者满足下列特性

1）每个结点至多有m棵子树（即最多有m-1个关键字）

2）根结点至少有2棵子树

3）除根结点和叶子结点外，所有结点至少有m/2棵子树

4）结点中按关键字大小顺序排序

5）叶子结点都在同一层
B树的查找

1）顺指针查找结点

2）在结点中查找关键码

3）重复上两步
B树的高度

含有n个关键码的m阶B树，最坏情况下的深度？

第k+1层至少有2*[m/2]^(k-1)个结点

最大深度log[m/2](n+1)/2+1

最小深度logmn+1
B树的插入

1）定位：确定关键码key应该插入哪个叶子结点并返回指针，若p中关键码个数不超过m-1个则可插入key

2）分裂——提升：若父结点关键码个数溢出，则继续执行分裂。

B树的删除

确定关键码key在哪个结点并返回该结点指针，分两种情况：

1）删除叶子结点中关键码（又分3种情况）
- 1.1）如果叶子结点中关键码个数大于[m/2]-1，直接删去
- 1.2）若叶子结点中关键码个数等于[m/2]-1，而其左右兄弟结点关键字个数大于[m/2]-1，则向兄弟结点借一个关键码
- 1.3）如果在第二种情况，兄弟关键字也不大于[m/2]-1，则执行 “合并” 兄弟的操作
2）删除非叶子结点中关键码

非叶子结点的直接后继找最小元素代替即可
B+树

是B树的一种变形，其差异在于：

1）有m棵子树的结点中含有m个关键码

2）所有的叶子结点中包含了全部关键码信息，及指向含有这些关键码记录的指针

3）所有非终端结点可以看成索引部分
B+树的删除仅在叶结点上进行

8.4 散列表的查找

散列函数

散列基本思想：在记录的关键码和存储地址间确定一个对应关系
散列表：采用散列技术存储查找集合的连续存储空间
散列函数：将关键码映射到散列表中适当存储位置的转换函数
散列地址：由散列函数所得的存储地址
散列函数设计原则

1）函数适用：定义域需包括存储的全部关键字，若散列表允许有m个地址，值域需在0到m-1之间

2）地址均匀

3）计算简单：散列函数的运算尽可能简单
常见的散列函数

1）直接定址法

H(key) = a*key + b（a，b为常数）

适用于事先知道关键码，且关键码不大、连续性较好

2）数字分析法

关键码由d位数字组成，每一位有r种不同符号，r种符号在各位上出现的频率不一定相同。因此可以根据散列表大小，选取其中各种符号分布均匀的若干位作为散列地址

适用于事先明确知道可能出现的关键码

3）平方取中法

对关键码平方后，按散列表大小，取中间的若干位作为散列地址

适用于事先不知道关键码分布且关键码位数不大

4）折叠法

把关键码自左向右分成位数相等的几部分，每一部分位数对应与散列表地址位数相同，只有最后一部分位数可以短一些。把这部分数据叠加起来，得到该关键码对应的散列地址。（移位法、分界法）

适用于关键字位数多，且关键字每一位上字符分布较均匀

5）除留余数法

H(key) = key mod p (p≤m)

p一般选小于或等于散列表长度m的最大素数

适用于最简单、最常用、不要求事先知道关键码的分布

处理冲突策略

处理冲突：为发生地址冲突的记录找到一个空的Hash地址
如何寻找一个空的散列地址？

1）线性探测法

从冲突位置的下一个位置起，依次寻找空的散列地址，但容易出现堆积现象

Hi=(H(key)+di)%m (di=1)

2）二次探测法

以冲突位置为中心，跳跃式寻找空的散列地址

Hi=(H(key)+di)%m (di=1²,-1²,2²,-2²,…,q²,-q² (q≤m/2))

能一定程度减少堆积现象，但缺点是不能探测到所有单元

3）链地址法（开散列法）

计算散列地址j=H(key)，将key对应的记录插入到同义词子表j中
查找分析

影响冲突的因素：散列函数是否均匀、处理冲突的方法、散列表的装填因子（表中填入记录/散列表长度）

开散列表与闭散列表比较

	闭散列表	开散列表
空间比较	1）受数组空间限制 2）存储效率较高	1）没有记录个数限制，但子表过长降低查找效率 2）指针的结构性开销大
时间比较	1）有堆积现象，降低查找效率 2）仅适用于静态查找	1）不产生堆积现象，效率较高 2）适用于静态、动态查找

九.内部排序

9.1 排序的基本概念

对一个记录的集合，顺序化是操作数据最有效的方式
排序：将一个记录的集合按相应 关键字(key) 的值递增或递减次序排列的过程
排序最优算法不会优于O(nlogn)
稳定排序：键值一样的单元经稳定排序算法后，相对位置不变
排序算法的评价

时间复杂度、空间复杂度、稳定性
根据存储器可分为

内部排序：在内存实现，数据对象全部存放在内存，无内外存数据交换，适合少量数据，速度快

外部排序：排序期间对象太多，不能同时放内存，适合大量数据，速度慢
按排序算法复杂度分为

简单排序方法：O(n²) 简单排序

先进排序方法：O(nlogn) 堆排序、快速排序

基数排序方法：O(dn) 基数排序

9.2 插入排序

直接插入排序

基本思想

准备一个输入集合及一个输出集合，将输入集合的记录依次取出，按key值顺序插入到输出集合
优化：不另外准备输出，直接在源地址排序

将输入序列分为两个部分，用一个指针指示分界；前面排好序的部分为S1，后面待排序部分为S2，取S2的第一条记录并插入到S1正确位置；当S2为空时算法结束

对于基本数值集合的实现

void insertSort(int*array, int size){
  for(int i=1;i<size;i++){
    for(int j=i; j>0&&array[j-1]>array[j]; j--){
      int tmp = array[j];
      array[j] = array[j-1];
      array[j-1] = tmp;
    }
  }
}

直接插入排序评价

最好情况（正序）：O(n)

最坏情况（逆序）：O(n²)

空间复杂度：可只使用一个额外的辅助空间

稳定性：直接插入排序是一种稳定的排序方法

特点：对于几乎所有集合，效率高

希尔排序

基本思想

先取一个小于n的整数d1作为第一个增量，把全部记录分组。所有距离为d1的倍数的记录放在同一个组中，先在组内进行直接插入排序

算法实现

void shellInsert(int array[], int n, int gap){
  int i,j,temp;
  for(i=gap;i<n;i++){	//分别向每组有序区域插入
    temp=array[i];
    for(j>i-gap;(j>=i%gap)&&array[j]>temp;j-=gap){
      array[j+gap]=array[j];
    }
    if(j!=i-gap)	array[j+gap]=temp;	//插入
  }
}

void shellSort(int array[], int n){
  for(int gap=n>>1;gap>0;gap>>1)
    shellInsert(array,n,gap);
}

时间复杂度分析

与增量序列相关，最坏情况是O(n²)

9.3 交换排序

冒泡排序

基本思想

两两比较，将较大元素排在后面一个，重复多次循环

算法实现

void bubble_sort(int *array, int n){
  for(int i=0;i<n-1;i++){	//共n-1轮
    for(int j=0;j<n-i-1;j++){
      if(array[j]>array[j+1]){
        int temp = array[j+1];
        array[j+1] = array[j];
        array[j] = temp;
      }
    }
  }
}

时间复杂度分析

最好情况（正序）：只比较，不移动对象

最坏情况（逆序）：执行n-1趟起泡，第i趟做了n-i次关键字比较，执行n-i次对象交换

平均O(n²)
稳定性：稳定

快速排序

基本思想

通过一趟排序，将待排序记录分割为两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。
时间复杂度

最差：输入已排好序的序列，O(n²)，对近似有序序列输入的优化可以通过随机函数选取分割单元

平均O(nlog(n))

9.4 选择排序

简单选择排序

基本思想

把顺序存储的n个待排序的记录看成由一个有序区和一个无序区组成。初始时，有序区为空。

在一趟选择排序中，从无序区选出一个关键字最小的记录（遍历），把他放在有序区尾部，经过n-1次排序

简单选择排序举例

算法实现

void select_sort(RecordType*array, int len){
  if(len<0) return;
  int min_pos=find_min(array,len); //找到最小位置
  swap(&(array[0]), &(array[min_pos])); //将其置换到序列头部
  select_sort(array+1, len-1);
}
int find_min(RecordType *array, int len){
  int result =0;
  for(int i=1;i<len;i++){
    if(array[i].key<array[result].key) result=i;
  }
  return result;
}