01 链表

1、结点（node）：数据元素的存储映像。由数据域和指针域两部分组成。

数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置

2、链表：n个结点由指针链组成的一个链表

头指针：是指向链表中第一个结点的指针
首元结点：是链表中存储第一个数据元素$ a_1 $的结点
头结点：是在链表的首元结点之前附设的一个结点

1.1 单链表

结点只有一个指针域的链表，称为单链表或线性链表

单链表有两种形式，一种是带头结点的单链表，一种是不带头结点的单链表

1、不带头结点
头指针（head）直接存放第一个元素的地址

2、带头结点
头指针（head）指向头结点，头结点的指针域再来存放首元结点的位置

带头结点的作用：

便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理；
便于空表和飞控表的统一处理：无论链表是否为空，头指针dou’shi指向头结点的非空指针，因此空表和非空表的也就统一了。

带头结点的单链表

单链表的存储结构

typedef struct Lnode{
    ElemType data;  // 数据域
    struct Lnode *next;  // 结构域
}Lnode, *LinkList  // LinkList为指向结构体Lnode的指针类型

定义链表和定义结点指针p

//定义链表
LinkList L;
//定义结点指针p
LinkList p;//不常用
Lnode *p;//常用

1.1.1 单链表的初始化

Sratus lintList_L(LinkList &L){
    //C++
    L = new LNode;
    //C
    L = (LinkList)malloc(sizeof(Lnode))

    L->next = NULL;
}

1.1.2 单链表的基本操作

1、判断链表是否为空

bool isListNull(LinkList L){
    if(L->next == NULL)return true;
    else return false;
}

2、单链表的销毁

Status DestroyList(LinkList &L){
    Lnode *p;  // 或LinkList p;
    while(L){
        p = L;
        L = L->next;
        delete p;
        //C: free p;
    }
}

3、清空单链表

Status ClearList(LinkList &L){
    Lnode *p, *q;
    p = L->next;
    while(p){
        q = p->next;
        free p;
        p = q;
    }
    L->next = NULL;
}

4、求链表的表长

从首元结点开始，依次计数所有结点

int ListLength(LinkList L){
    LinkList p;
    p = L->next;
    i = 0;
    while(p){
        i++;
        p = p->next;
    }
}

1.1.3 单链表的重要操作

取值：取单链表中第i个元素的内容
查找：
- 按值查找：根据指定的数据获取数据所在的位置（地址）
- 按值查找：根据指定的数据获取数据所在的位置序号
插入：在第i个结点前插入新节点
删除：删除第i个结点
单链表的建立
- 头插法
- 尾插法

1.1.3.1 取值

Status GetElem_L(LinkList L, int i, ElemType &e){
    p = L->next;
    int j = 1;
    while(p && j < i){  // 向后扫描，直到p指向第i个元素或p为空
        p = p->next;
        j++;
    }
    if(!p || j > i){
        return ERROR;
    }
    return p->data;
}

1.1.3.2 查找

1、返回地址

Lnode *LocateElem_L(LinkList L, Elemtype e){
    p = L->next;
    while(p->data != e && p){
        p = p->next;
    }
    return p;
}

2、返回位置序号

int LocateELem_L(LinkList L, Elemtype e){
    p = L->next;
    int j = 1;
    while(p->data != e && p){
        p = p->next;
        j++;
    }
    if(p)
        return j;
    else
        return 0;
}

1.1.3.3 插入

Status ListInset_L(LinkList &L, int i, ElemType e){
    Lnode *p = L->next;
    j = 1;
    while(p && j < i - 1){
        p = p->next;
        j++;
    }
    if(!p || j > i-1)return ERROR;
    if(p){
        Lnode *s = (LinkList)malloc(sizeof(Lnode));
        s->data = e;
        s->next = p->next;
        p->next = s;
    }
}

1.1.3.4 删除

Status ListDelete_L(LinkList &L, int i, ElemType &e){
    Lnode *p = L->next;
    int i, j = 1;
    Lnode *q = (LinkList)malloc(sizeof(Lnode));
    while(p->next && i < i-1){
        p = p->next;
        j++;
    }
    if(!(p->next) || j > i-1)return ERROR;
    q = p->next;
    e = q->data;
    p->next = (p->next)->next; // 或p->next = q->next;
    free q;
}

1.1.3.5 单链表的建立

1、头插法

void CreatList_H(LinkList &L, int n){
    L = (LinkList)malloc(sizeof(Lnode));
    L->next = NULL;
    for(i = 0; i < n; i++){
        Node *p = (LinkList)malloc(sizeof(Lnode));
        scanf("%d", &(p->data));
        p->next = L->next;
        L->next = p;
    }
}

2、尾插法

void CreateList_R(LinkList &L, int n){
    L = (LinkList)malloc(sizeof(Lnode));
    L->next = NULL;
    Lnode *r = L;
    int i;
    for(i =  0; i < n; i++){
        Lnode *p = (LinkList)malloc(sizeof(Lnode));
        scanf("%d", &(p->data));
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

1.1.3.6 单链表翻转

#include <stdio.h>
#include <stdlib.h>

typedef struct Lnode {
	int data;
	struct Lnode* next;
}Lnode, * LinkList;

void CreatList_R(LinkList L, int n) {
	L->next = NULL;
	Lnode* r = L;
	int i;
	for (i = 0; i < n; i++) {
		Lnode* p = (LinkList)malloc(sizeof(Lnode));
		scanf("%d", &(p->data));
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

void PrintList(LinkList L) {
	Lnode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	return;
}

void ReverseList(Lnode* L) {
	if (L == NULL || L->next == NULL || L->next->next == NULL)return;
	Lnode* pre = L->next->next;
	L->next->next = NULL;
	Lnode* temp;
	while (pre) {
		temp = pre->next;
		pre->next = L->next;
		L->next = pre;
		pre = temp;
	}
	return;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	LinkList La = (LinkList)malloc(sizeof(Lnode));
	CreatList_R(La, n);
	ReverseList(La);	
	PrintList(La);
	return 0;
}

1.2 双链表

结点有两个指针域的链表，称为双链表

1.3 循环链表

首尾相接的链表称为循环链表

02 栈和队列

栈：后进先出，先进后出
队列：后进后出，先进先出

2.1 栈的定义和特点

栈(stack)是一个特殊性线性表，是限定仅在一端进行插入和删除的操作

栈是仅在表尾进行插入和删除操作的线性表
表尾称为栈顶Top，表头称为栈底Base

插入元素到栈顶的操作，称为入栈
从栈顶删除最后一个元素的操作，称为出栈

2.2 栈的表示与实现

栈有两种存储方式

顺序存储方式
链式存储方式

顺序栈的表示

typdef struct{
    SElemType *base;  // 栈底指针
    SElemType *top  // 栈顶指针
    int stacksize;  // 栈可用最大容量
}SqStack;

2.2.1 顺序栈的初始化

define MAXSIZE 100;
typdef struct{
    SElemType *base;  // 栈底指针
    SElemType *top  // 栈顶指针
    int stacksize;  // 栈可用最大容量
}SqStack;

Status InitStack(SqStack &S){
    S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
    if(!S.base)exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return;
}

2.2.2 顺序栈的基本操作

2.2.2.1 顺序栈判断栈是否为空

Status StackEmpty(SqStack S){
    if(S.top == S.base)return true;
    else return false;
}

2.2.2.2 顺序栈的长度

1
2
3

int StackLength(SqStack S){
    return S.top-S.base;
}

2.2.2.3 清空顺序栈

1
2
3

Status ClearStack(Sqtack& S){
    if(S.base)S.top == S.base;
}

2.2.2.4 销毁顺序栈

Status DestroyStack(SqStack& S){
    if(S.base){
        free S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return;
}

2.2.3 顺序栈的重要操作

2.2.3.1 顺序栈的入栈

Status Push(SqStack& S, SElemType e){
    if(S.top-S.base==S.stacksize){
        return;
    }
    *S.top = e;
    S.top++;
}

2.2.3.2 顺序栈的出栈

Status Pop(SqStack& S, SElemType& e){
    if(S.top==S.base)return;
    S.top--;  // --S.top
    e = *S.top; // e = *--S.top;
}

2.2.2 链栈的表示

特点：

链表的头指针就是栈顶
不需要头结点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

2.2.2.1 链栈的初始化

typedef struct StackNode{
    SElemType data;
    struct StackNode* next;
}StackNode, *LinkStack;
LinkStack S;
void InitStack(LinkStack& S){
    S = NULL;
    return;
}

2.2.2.2 判断链栈是否为空

Status StackEmpty(LinkStack S){
    if(S==NULL)return true;
    else return false;
}

2.2.2.3 链栈的入栈

void PushStack(LinkStack& S, SElmType e){
    p = (LinkStack)malloc(sizeof(StackNode));  // 分配内存
    p->data = e;  // 输入数据
    p->next = S;  // 将新节点插入栈顶
    S = p;  // 修改栈顶指针
    return;
}

2.2.2.4 链栈的出栈

void PopStack(LinkStack& S, SElmType &e){
    if(S==NULL)return;
    e = S->data;
    LinkStack p = S;
    S = S->next;
    free p;
    return;
}

2.2.2.5 取栈顶元素的值

SElemType GetTop(LinkStack S){
    if(S!=NULL){
        return S->data;
    }
    return;
}

2.2.3 栈与递归

递归的定义：

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。
若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

递归定义的数学函数：

阶乘函数：
$Fact(n)=\left\{\begin{matrix} 1 & 若n=0 & \\ n\cdot Fact(n-1) & 若n>0 & \end{matrix}\right. \$
2阶Fibonaci数列
$Fib(n)=\left\{\begin{matrix} 1 & 若n=1或2 & \\ Fib(n-2)+ Fib(n-1) & 若n>2 & \end{matrix}\right.$
递归问题-用分治法求解
分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同的或类似的子问题来求解

必备的三个条件：

1、能将一个问题转变成一个新的问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
2、可以通过上述转化而使问题简化
3、必须有一个明确的递归出口，或称递归的边界

2.2 队列的定义和特点

队列(queue)是一种先进先出的线性表，再一端（表尾）插入，再另一端（表头）删除

插入元素称为入队，删除元素称为出队

队列的存储结构分为链式存储（链队）和顺序存储结构（顺序队），常用循环顺序队

2.3 队列表示与实现

2.3.1 顺序队的部分问题的解决方法

#define MaxN 100
typedef struct{
    QElemType *base;  // 初始化的动态分配存储空间
    int front;  // 头指针
    int rear;  // 尾指针
}SqQueue;

解决假溢出：引入循环队列

利用%运算

插入元素：

1 2	Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MaxN;

删除元素：

1 2	x=Q.base[Q.front]; Q.front=(Q.front+1)%MaxN;

队空：front==rear
队满：front==rear

解决方法：

1、另设一个标志以区别队空、队满
2、另设一个变量来记录元素个数
3、少用一个元素空间

循环队列解决队满时判断方法—少用一个元素空间

队空：front==rear
队满：(rear+1)%MaxN==front

2.3.2 顺序队的基本操作

2.3.2.1 顺序队的初始化

Status InitQueue(SqQueue& Q){
    Q.base = (*SqQueue)malloc(MaxN*sizeof(QElemType));
    if(!Q.base)exit(OVERFLOW);
    Q.front = Q.rear = 0;
}

2.3.2.2 顺序循环队的长度

循环队列

1
2
3

int QueueLength(SqQueue Q){
    return(Q.rear-Q.front+MaxN)%MaxN
}

2.3.2.3 顺序循环队列入队

Status EnQueue(SqQueue& Q, QElemType e){
    if((Q.rear+1)%MaxN==Q.front)return;  // 判断是否队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1)%MaxN;
    return;
}

2.3.2.4 顺序循环队列出队

Status DeQueue(SqQueue& Q, QElemType& e){
    if(Q.front==Q.rear)return;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MaxN;
    return;
}

2.3.2.5 取队头元素

SElemType GetHead(SqQueue Q){
    if(Q.front!=Q.rear)
        return Q.base[Q.front];
}

2.3.3 链队的基本操作

#define MaxN 100
typedef struct Qnode{
    QElemType data;
    struct Qnode* next;
}QNode, *QueuePtr;

typedef struct{
    QueuePtr front;  // 队头指针
    QueuePtr rear;  // 队尾指针
}LinkQueue;

2.3.3.1 链队列的初始化

Status InitQueue(LinkQueue& Q){
    Q.front = Q.rear  = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);
    Q.front->next = NULL;
    return;
}

2.3.3.2 链队列的销毁

Status DestroyQueue(LinkQueue& Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
}

2.3.3.3 链队列入队

Status EnQueue(LinkQueue& Q, QElemType e){
    LinkQueue p = (QueuePtr)malloc(sizeof(QNode));
    if(!p)exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return;
}

2.3.3.4 链队列的出队

Status DeQueue(LinkQueue& Q, QElemType& e){
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear==p)Q.rear=Q.front;
    free(p);
    return;
}

2.3.3.5 链队列的对头元素

Status GerHead(LinkQueue Q, QElemType& e){
    if(Q.front==Q.rear)return;
    e=Q.front->next->data;
    return;
}

03 串、数组和广义表

3.1 串

3.1.1 串的定义

串（String）—-零个或多个任意字符组成的有限序列

例：$ S = “a_1 a_2 … a_n” $

S 串名
$ a_1 a_2 … a_n $ 串值
n 串长

当n=0时，称为空串

子串：串中任意个连续字符组成的子序列（包含空串）称为该串的子串

真子串：不包含本身的字串

主串：包含子串的串相应地称为主串

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

子串位置：子串第一个字符在主串中的位置

空格串：由一个或多个空格组成的串，与空串不同

串相等：当且仅当两个串的长度相同并且各个对应的位置上的字符都相同时，这两个串才是相等的

3.1.2 串的类型定义

存储方式

顺序存储结构
链式存储结构

串的顺序存储结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];
    int length;
}SString;

串的链式存储结构—块链结构

#define CHUNKSIZE 80
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct{
    Chunk *head, *tail;  // 串的头指针和尾指针
    int curlen;  // 串的当前长度
}LString;

3.1.2 串的模式匹配算法

算法目的：确定主串中含子串（模式串）第一次出现的位置（定位）

算法种类：

BF算法
KMP算法

3.1.2.1 BF算法

Brute-Force简称BF算法，亦称简单匹配算法。采用穷举法的思路。

int Index_BF(SString S, SString T, int pos){
    int i = pos, j = 1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else{
            i = i-j+1;  // i = i - j + 2
            j = 1;
        }
    }
    if(j>T.length)return i-T.length
    else return 0;
}

3.1.2.2 KMP算法

3.2 数组

数组：按一定格式排列起来的，具有相同类型的数据元素的集合

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组

一维数组的逻辑结构：线性结构。定长的线性表

声明结构：数据类型变量名称[长度]

二维数组：若一维数组中的数据元素又是一组数组结构，则称为二维数组。

二维数组的逻辑结构

非线性结构：每一个数据元素既在一个行表中，又在一个列表中。
线性结构：该线性表的每一个元素也是一个定长的线性表

3.2.1 数组的顺序结构

数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

3.2.2 特殊矩阵的压缩存储

矩阵：一个由m x n个元素排成的m行n列的表

矩阵的常规存储的特点：可以对其元素进行随机存取；矩阵运算非常简单；存储的密度为1。

不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布；零元素多。

矩阵的压缩存储：为多个相同的非零元素只非分配一个存储空间；对零元素不分配空间。

压缩存储：若多个数据元素的值相同，则只分配一个元素的值的存储空间，且零元素不占存储空间

一些特殊矩阵才采用压缩存储，例如：对称矩阵、对角矩阵、三角矩阵、稀疏矩阵等

稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）

3.2.2.1 对称矩阵的压缩

特点：在$ nxn $的矩阵中，满足如下性质：

$a_(ij) = a(ji) \$

存储方法：只存储下（或者上）三角（包括主对角线）的数据元素。共用$ n(n+1)/2 $个元素空间

3.2.2.2 三角矩阵的压缩

特点：对角线以下（或者以上）的数据元素（不包括对角线）全部都为常数C

存储方法：重复元素C共享一个元素存储空间，共占用$ n(n+1)/2 + 1 $个元素

3.2.2.3 稀疏矩阵的压缩存储

三元组法$ (i, j, a_(ij)) /$唯一确定一个非零元素

顺序存储：

链式存储：十字链表

3.3 广义表

广义表通常记作：$ LS = (a_1, a_2, …, a_n) $，其中: $ LS $为表名，$ n $为表的长度，每一个$ a_i $为表的元素。

习惯上，一般用大写字母表示广义表，小写字母为原子

表头：若$ LS $非空，则其第一个元素$ a_1 $就是表头，记作$ head(LS) = a_1 $，表头可以是原子，也可以是子表
表尾：除表头外的其他元素组成的表，记作 $ tail(Ls) = (a_2,…, a_n) $。

表尾不是最后一个元素，而是一个子表

深度：为该广义表展开后所含括号的重数。

04 树和二叉树

树形结构和图形结构都是非线性结构

4.1 树的定义

树是n个结点的有限集

若n=0，称为空树
若n>0，则它满足如下条件
- 1）有且仅有一个特定的称为根的结点
- 2）其余结点可分为m(m>=0)个互不相交的有限集$ T_1, T_2, T_3, …, T_m $，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。

4.1.1 树的基本术语

树的深度：树的最大层数

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）

无序树：树中结点的各子树无次序

森林：是$ m(m>=0) $ 棵互不相交的树的集合

树一定是森林，森林不一定是树

4.2 二叉树的定义

普通树（多叉树）若不转化为二叉树，则运算很难实现

二叉树的结构最简单，规律性强，所有树都可以转为唯一对应的二叉树，不失一般性

二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中的复杂性

二叉树是$ n(n>=0) $个结点的有限集，它或者是空集$ (n=0) $，或者由一个根结点及两棵互不相交的分别称作为这个根的左子树和右子树的二叉树组成

特点：

1、每个结点最多两个孩子（二叉树中不存在度大于2的结点）
2、子树有左右之分，其次序不能颠倒
3、二叉树可以是空集，根可以有空的左子树或空的右子树

性质：

1、在二叉树的第i层上至多有$ 2^(i-1) $个结点，至少有1个结点
2、深度为k的二叉树至多有$ 2^k - 1 $个结点，至少有k个结点
3、对任何一棵二叉树T，如果叶子数位$ n_0 $，度为2的结点数为$ n_2 $，则$ n_0 = n_2 + 1 $。
4、具有n个结点的完全二叉树的深度为$ \left \lfloor log_2n\right \rfloor + 1 $
5、如果对一棵有n个结点的完全二叉树(深度为$ \left \lfloor log_2n\right \rfloor + 1 $的结点按层序编号)，则对任一结点，有
- 1）如果i = 1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点$ \left \lfloor i/2\right \rfloor + 1 $
- 2）如果$ 2i > n $，则结点i为叶子结点，无左孩子，否则，其左孩子是结点$ 2i $
- 3）如果$ 2i + 1 > n$，则结点i无右孩子；否则，其右孩子是结点$ 2i + 1 $

4.3 二叉树的存储结构

4.3.1 顺序存储

使用数组存储，适合完全二叉树和满二叉树

4.3.2 链式存储

二叉链表

typedef struct BiNode{
    TElemTyp data;
    struct BiNode *lchild, *rchild;
}BiNode, *BiTree;

三叉链表

typedef struct TriTNode{
    TelemType data;
    struct TriTNode *lchild, *parent, *rchild;
}TriTNode, *TriTree;

4.4 二叉树的遍历

遍历定义：顺着某一条搜索路劲巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次

遍历目的：得到树中所有结点的一个线性排列

遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心

若规定先左后右，则只有三种遍历情况

DLR—先（根）序遍历
LDR—中（根）序遍历
LRD—后（根）序遍历

由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以唯一确定一棵二叉树

4.4.1 二叉树先序遍历算法

Status  PreOrderTraverse(BiTree T){
    if(T == NULL) return;
    else{
        visit(T);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

4.4.2 二叉树中序遍历算法

Status InOrderTraverse(BiTree T){
    if(T == NULL) return;
    else{
        InOrderTraverse(T->lchild);
        visit(T);
        InOrderTraverse(T->rchild);
    }
}

4.4.3 二叉树的后序遍历算法

Status PostOrderTraverse(BiTree T){
    if(T == NULL) return;
    else{
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        visit(T);
    }
}

4.4.4 二叉树复杂度

时间：$ O(n) $ //每个结点只访问一次
空间：$ O(n) $

4.4.5 二叉树的非递归算法

以中序遍历为例，使用栈

Status InOrderTraverse(BiTree T){
    BiTree p;
    InitStack(S);
    p = T;
    while(p || !StackEmpty(S)){
        if(p){
            Push(S, p);
            p = p->lchild;
        }
        else{
            Pop(S, q);
            printf("%c", q->data);
            p = q->rchild;
        }
    }
    return;
}

4.4.6 二叉树的层次遍历算法

从上到下，从左到右

使用队列

typedef struct{
    BTNode data[MaxSize];
    int font, rear;
}SqQueue;

void LevelOrder(BTNode *b){
    BTNode *p;
    SqQueue *qu;
    InitQueue(qu);
    enQueue(qu, b);  // 根结点进入队列
    while(!QueueEmpty(qu)){
        deQueue(Qu, p)  // 出队结点p
        printf("%c", p->data);
        if(p->lchild != NULL)
            enQueue(qu, p->lchild); // 入队
        if(p->rchild != NULL)
            enQueue(qu, p->rchild);
    }
}

4.5 二叉树的基本操作

4.5.1 二叉树的建立

使用先序遍历进行建立

Status CreateBiTree(BiTree& T){
    scanf(&ch);
    if(ch == '#') T = NULL;
    else{
        T = (BiNode*)malloc(sizeof(BiTNode));
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return;
}

4.5.2 二叉树的复制

使用先序遍历

void Copy(BiTree T, BiTree& NewT){
    if(T == NULL){
        NewT = NULL;
        return;
    }
    else{
        NewT = (BiTree)malloc(sizeof(BiTNode));
        NewT-> data = T->data;
        Copy(T->lChild, NewT->lchild);
        Copy(T->rChild, NewT->rchild);
    }
}

4.5.3 二叉树的深度

int Depth(BiTree T){
    if(T == NULL) return 0;
    else{
        m = Depth(T->lChild);
        n = Depth(T->rChild);
        if(m > n) return (m+1);
        else return (n+1)；
    }
}

4.5.4 二叉树结点的总数

int NodeCount(BiTree T){
    if(T == NULL)return 0;
    else{
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    }
}

4.5.5 二叉树的叶子结点数

int NodeCount(BiTree T){
    if(T == NULL)return 0;
    if(T->lchild == NULL && T->rchild == NULL)return 1;
    else{
        return NodeCount(T->lchild) + NodeCount(T->rchild);
    }
}

4.6 线索二叉树

二叉树链表中空指针域的数量：
具有n个结点的二叉树链表中，一共有2n个指针域；因为n个结点中n-1个孩子，即2n个指针域中，有n-1个用来指示结点的左右孩子，其余n+1个指针域为空。

利用二叉树中的空指针域：

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱
如果某个结点的右孩子为空，则将空的右孩子指针域改位指向其后继

为区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标指域ltag和rtag，并约定

ltag = 0 则 lchild 指向该结点的左孩子
ltag = 1 则 lchild 指向该结点的前驱
rtag = 0 则 rchild 指向该结点的右孩子
rtag = 1 则 rchild 指向该结点的后继

typedef struct BiThrNode{
    int data;
    int ltag, rtag;
    struct BiThrNode *lchild, *rchild;
}BiThrNode, *BiThrTree;

4.7 树和森林

树是n个结点的有限集

森林：是m棵互不相交的树的集合

4.7.1 树的存储结构

双亲表示法

#define MAX_TREE_SIZE 100
typedef struct PTNode{
    TElemType data;
    int parent;  // 双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;  // 根结点的为止和结点个数
}PTree;

孩子链表表示法

typedef struct CTNode{
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct{
    TElemType data;
    ChildPtr fistchild;
}CTBox;

typedef struct{
    CTBox nodes[Max];
    int n, r;
}CTree;

孩子兄弟表示法（二叉树表示法，二叉链表表示法）
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

4.8 树与二叉树的转换

将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。

由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系

4.9 哈夫曼树

哈夫曼树又称最优二叉树

4.9.1 哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
结点的路径长度：两结点间路径上的分支数。
树的路径长度：从树根到每一个结点的路径长度之和。记作TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径最短的二叉树不一定是完全二叉树

权：将树中的结点赋给一个有某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度：从根节点到该结点之间的路径长度与该结点的权乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL

哈夫曼树：最优树，带权路径长度（WPL）最短的树

哈夫曼树：最优二叉树，带权路径长度（WPL）最短的二叉树

满二叉树不一定是哈夫曼树，具有相同带权结点的哈夫曼树不唯一

4.9.2 哈夫曼树的构造算法

哈夫曼树中权越大的叶子离根越近

哈夫曼树的结点的度数为0或2，没有度为1的结点

包含n个叶子结点的哈夫曼树中共有2n-1个结点

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点

typedef struct{
    int weight;
    int parent, lch, rch;
}HTNode, *HuffmanTree;

哈夫曼算法实现：

令所有的结点的parent和lch、rch都为0，然后输入权重

void CreateHuffmanTree(HuffmanTree HT, int n){
	if(n <= 1)return;
    int m = 2*n-1;
    HT = (HuffmanTree*)malloc((m+1)*sizeof(HTNode));//0单元不用
    for(int i = 1; i < m; i++){
        HT[i].lch = 0;
        HT[i].rch = 0;
        HT[i].parent = 0;
	}
    for(int i = 1; i <=n; i++){
        cin >> HT[i].weight;
	}
    for(int i = n + 1; i < m; i++){
        Selet(HT, i-1, s1, s2);//再HT中选择两个其双亲为0，且权值最小的结点，并返回他们在HT的序号s1和s2
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lch = s1;
        HT[i].rch = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

4.9.3 哈夫曼编码

哈夫曼编码方法:

1、统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。
2、利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短；
在哈夫曼树的每一个分支上标上0或1：
- 结点的左分支标0，右分支标1
- 把从根到每个叶子的路径上的标号连起来，作为该叶子代表的字符编码

void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
    HC = new char*[n+1];
    cd = new char[n];
    cd[n-1] = '\0';
    for(int i = 1; i <= n; i++){
        start = n-1;
        c = i;
        f = HT[i].parent;
        while(f != 0){
            --start;
            if(HT[f].lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            c = f;
            f = HT[f].parent;
        }
        HC[i] = new char[n-start];
        strcpy(HC[i], &cd[start]);
    }
    delete cd;
}

05 图

5.1 图的定义和术语

图：G=(V, E)

V：顶点（数据元素）的有穷非空集合（Vertex）
E：边的有穷集合（Edge）

无向图：每条边都是无方向的

有向图：每条边都是有方向的

完全图：任意两个点都有一条边相连

无向完全图中n个顶点，有n(n-1)/2条边

有向完全图中n个顶点，有n(n-1)条边

网：边/弧带权的图

顶点的度：与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度（ID）和出度（OD）之和

路径：接续的边构成的顶点序列

路径长度：路径上边或弧的数目/权值之和

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

简单路径：除了路径起点和终点可以相同外，其余顶点均不相同的路径

连通图（强连通图）：在无（有）向图中，若任意两个顶点都存在路径，则成为连通图（强连通图）

有向图->强连通，无向图->连通图

生成树：包含无向图所有顶点的最小连通图

5.2 图的存储结构

图是没有顺序结构的，但是可以借助二维数组来表示元素间的关系

数组表示法（邻接矩阵）

重点介绍：邻接矩阵（数组）表示法和邻接表（链式）表示法

5.2.1 邻接矩阵

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）

无向图的邻接矩阵：

分析1：无向图的邻接矩阵是对称的
分析2：顶i点i的度 = 第i行（列）中1的个数
特别：完全图的邻接矩阵中，对角都是0，其余都是1

有向图的邻接矩阵：

分析1：有向图的邻接矩阵是可能不对称的
分析2：顶点的出度 = 第i行元素的和
分析3：顶点的入度 = 第i列元素的和

网

5.2.1.1 邻接矩阵的存储表示

#define MaxInt 32767  // 表示无穷（网中使用）
#define MVNum 100  // 最大顶点数
typedef char VerTexType;  // 顶点类型
typedef int ArcType;  // 边权值的类型

typedef struct{
    VerTexType vexs[MVNum];  // 顶点表
    ArcType arcs[MVNum][MVNum];  // 邻接矩阵
    int vexnum, arcnum;  // 图的当前点数和边数
}AMGraph;

5.1.1.2 邻接矩阵创建无向网

// 在图重查找顶点
int LocateVex(AMGraph G, VertexType u){
    int i;
    for(i = 0; i < G.vexnum; i++){
        if(u == G.vexs[i])
            return i;
    }
    return -1;
}

Status CreateUDN(AMGraph &G){
    cin >> G.vexnum >> G.arcnum;  // 输入总顶点数，总边数
    for(int i = 0; i < G.vexnum; i++){
        cin >> G.vexs[i];  // 依次输入点的信息
    }
    for(int i = 0; i < G.vexnum; i++){
        for(int j = 0; j < G.vexnum; i++){
            G.arcs[i][j] = MaxInt;  // 边的权值均置为极大值
        }
    }
    for(int k = 0; k < G.arcnum; k++){  // 构造邻接矩阵
        cin >> v1 >> v2 >> w;  // 输入一条边所依附的顶点及边的权值
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);  // 确定v1和v2在G中的位置
        G.arcs[i][j] = w;  // 边<v1, v2>的权值置为w
        G.arcs[j][i] = G.arc[i][j];  // 对称
    }
    return OK;
}

如果是有向网，则只需对G.arcs[i][j]赋值，无需对G.arcs[j][i]赋值

5.2.2 邻接表

特点：

邻接表不唯一
若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。

5.3 图的遍历

图常用的遍历

深度优先搜索（DFS）
广度优先搜索（BFS）

5.3.1 深度优先遍历（DFS）

void DFS(AMGraph G, int v){
    cout << v << endl;
    visited[v] = true;
    for(int w = 0; w < G.vexnum; w++){
        if((G.arcs[v][w]!=0)&&(!visited[w])){
            DFS(G, w);
        }
    }
}

5.3.1 广度优先遍历（BFS）

void BFS(Graph G, int v){
    Queue Q;
    cout << v << endl;
    visited[v] = true;
    InitQueue(Q);
    EnQueue(Q, v);
    while(!isQueueEmpty(Q)){
        DeQueue(Q, v);
        for(int i = 0; i < G.vexnum; i++){
            if(G.arcs[v][i] == 1 && visited[i] == 0){
                cout << G.vexs[i] << endl;
                visited[i] = true;
                EnQueue(Q, i);
            }
        }
    }
}

5.4 图的应用

5.4.1 最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路
- 生成树的顶点个数与图的顶点个数相同
- 生成树是图的极小连通子图
- 一个n个顶点的连通图的生成树由n-1条边
- 在生成树中再加一条边必然形成回路
- 生成树中任意两个顶点间的路径是唯一的
最小生成树：给定一个无向网络，在该网络的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树

5.4.1.1 构造最小生成树（MST）

06 查找

6.1 查找的概念

查找表：是由同一类型的数据元素构成的集合，由于集合中的数据元素之间存在松散的关系，因此查找表是一种应用灵便的结构
关键字：用来标识一个数据元素的某个数据项的值
- 主关键字：可唯一地标识一个记录的关键字
- 次关键字：用以识别若干记录的关键字
静态查找表：仅作“查询”操作的查找表
动态查找表：作“插入”和“删除”操作的查找表

查找算法的评价指标：

关键字的平均比较次数，也称平均查找长度ASL（Average Search Length）

关键字比较次数的期望

ASL = p_1*c_1 + … + p_i*c_i

n：记录的个数

p_i：查找第i个记录的概率（通常为1/n）

c_i：找到第i个记录所需要比较的次数

6.2 线性表的查找

6.2.1 顺序查找（线性查找）

应用范围：

顺序表或线性链表的静态查找表
表内元素之间无序

typedef struct {
    KeyType key;  // 关键字域
    ...           // 其他域
}ELemType;

typedef struct {
    ElemType *R;  // 表基址
    int length;   // 表长
}SSTable;
SSTable ST;  // 定义顺序表ST

int Search_Seq(SSTable ST, KeyType key) {
    for(int i = ST.length; i >= 1; i--) {
        if(St.R[i].key == key) return i;
    }
    return 0;
}

改进：把待查关键字key存入表头，从后往前比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度

int Search_Seq(SSTable ST, KeyType key) {
    ST.R[0].key = key;
    for(int i = ST.length; ST.R[i].key != key; i--);
    return i;
}

6.2.1.1 时间效率分析

比较次数与key位置有关：

查找第i个元素，需要比较n+1-i次
查找失败，需比较n+1次

时间复杂度：O(n)

ASL(n) = (1 + 2 + … + n)/n = (n + 1)/2

空间复杂度——-O(1)

6.2.1.2 顺序查找的特点

优点：算法简单，逻辑次序无要求，且不同存储结构均适用
缺点：ASL太长，时间效率低

6.2.2 折半查找（二分或对分查找）

折半查找：每次将待查记录所在区间缩小一半

设表长为n，low、high和mid分别指向待查元素区间的上界、下界和中点，key为给定要查找的值
初始时，令low = 1，high = n，mid = int((low+hight)/2)
让k与mid指向的记录比较
- 若key == R[mid].key，查找成功
- 若key < R[mid].key，则high = mid - 1
- 若key > R[mid].key，则low = mid + 1
重复上述操作，直至low > high时，查找失败

int Search_Bin(SSTable ST, KeyType key) {
    low = 1;
    high = ST.length;
    while(low <= high) {
        mid = (low + high) / 2;
        if(ST.R[mid].key == key) return mid;
        else if(key < ST.R[i].key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return 0;
}

递归算法

int Search_Bin(SSTable ST, KeyType key, int low, int high) {
    if(low > high) return 0;
    mid = (low + high) / 2;
    if(key == ST.elem[mid].key) return mid;
    else if(key < ST.elem[mid].key)
        Search_Bin(ST, key, low, mid - 1);
    else
        Search_Bin(ST, key, mid + 1, high);
}

6.2.2.1 时间效率分析

平均查找长度ASL（成功时）：

设表长 $ n = 2^h - 1 $，则 $ h = log_2(n+1) $此时，判定树的深度 = h 为满二叉树，且表中每个记录的查找概率相等：$ P_i = 1/n $

则：

$ASL_{bs} = log_2(n+1) -1 （n > 50）$

时间复杂度：O(lgn)

6.2.2.2 折半查找的特点

优点：效率比顺序查找高

缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）

6.2.3 分块查找

条件：

1、将表分成几块，且表或者有序，或者分块有序

2、建立索引表

查找过程：

先确定待查记录所在块（顺序或折半查找），再在这块内查找（顺序查找）

6.2.3.1 时间效率分析

查找效率：ASL = L_b + L_w

$ASL_{bs} = log_2(n/s + 1) + s/2 (log_2n <= ASL_{bs} <= (n+1)/2)$

L_b：对索引表查找的ASL

L_w：对块内查找的ASL

s：每块内部的记录个数，n/s即为块的个数

6.2.3.2 分块查找的特点

优点：插入和删除比较容易，无需进行大量移动

缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算

适用情况：如果线性表既要快速查找又要经常动态变化，则可采用分块查找

6.2.4 查找方法的比较

	顺序查找	折半查找	分块查找
ASL	最大	最小	中
表结构	有序表、无序表	有序表	分块有序
存储结构	顺序表、线性链表	顺序表	顺序表、线性链表

6.3 树表的查找

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录

改用动态查找表———几种特殊的树

对于给定的key

若表中存在，则成功返回

否则，插入关键字等于key的记录

二叉排序树
平衡二叉树
红黑树
B-树
B+树
键树

6.3.1 二叉排序树

又称二叉搜索树、二叉排序树

定义：

二叉排序树或是空树，或是满足如下性质的二叉树

1、若其左子树非空，则左子树所有结点的值均小于根结点的值
2、若其右子树非空，则右子树所有结点的值均大于等于根结点的值
3、其左右子树本身又各是一棵二叉排序树

性质：

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序的序列

6.3.1.1 二叉排序树的查找操作

存储结构

typedef struct {
    KeyType key;         // 关键字项
    InfoType otherinfo;  // 其他数据域
}ElemType;

typedef struct BSTNode {
    ElemType data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

BSTree T;

算法思想:

1）若二叉排序树为空，则查找失败，返回空指针。

2）若二叉排序树非空，将给定值key与根结点的关键字T->data.key比较：

① 若key等于T->data.key，则查找成功，返回根节点地址
② 若key小于T->data.key，则进一步查找左子树
③ 若key大于T->data.key，则进一步查找右子树

BSTree SearchBST(BSTree T, KeyType key) {
    if((!T) || key == T->data.key) return T;
    else if(key < T->data.key)
        return SearchBST(T->lchild, key);
    else
        return SearchBST(T->rchild, key);
}

6.3.1.2 二叉排序树的插入删除操作

插入算法思想：

若二叉排序树为空，则插入结点作为根结点插入空树中
否则，继续在其左、又子树上查找
- 树中已有，不再插入
- 树中没有
  - 查找直至某个叶子结点的左子树或右子树为空为止，则插入

删除算法思想：

被删除的结点时叶子结点：直接删去改结点
被删除的结点只有左子树或者只有右子树，用其左子树或右子树替换他
被删除的结点既有左子树，也有右子树
- 以其中序前驱值替换之（值替换），然后删除该前驱结点，前驱结点是左子树中最大的结点
- 也可以用其后继结点替换（值替换），然后再删除该后继节点，后继节点是右子树中最小的结点

6.3.1.3 时间效率分析

含有n个结点的二叉排序树的平均查找长度和树的形态有关

最好情况：

$ASL = log_2(n+1)-1$

树的深度：int( log_2n + 1 )
时间复杂度：O(log_2n)

最坏情况：

$ASL = (n + 1)/2$

树的深度：n
时间复杂度：O(n)

6.3.2 平衡二叉树

定义：

又称AVL树
一棵平衡二叉树或者是空树，或者居有下列性质的二叉排序树：
- 左子树与右子树的高度只差的绝对值小于等于1
- 左子树和右子树也是平衡二叉排序树

为了方便其间，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）

$平衡因子 = 结点左子树高度 - 结点右子树高度$

根据平衡二叉树的定义，平衡二叉树所有结点的平衡因子只能是-1，0或1。

对于一颗有n个结点的AVL树，其高度保持在O(log_2n)数量级，ASL也保持在O(log_2n)量级

6.3.2.1 失衡二叉排序树的分析与调整

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点

具体看P152

6.3.3 哈希表（散列表）

散列方法(杂凑法)
- 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；
- 查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比对，确定查找是否成功
散列函数(杂凑函数)
- 散列方法中使用的转换函数
散列表(杂凑表)
- 按照散列方法构造的表
冲突
- 不同的关键码映射到同一个散列地址
同义词
- 具有同样函数值的多个关键字，即冲突的元素

6.3.3.1 散列函数的构造

1）构造好的散列函数

所选函数尽可能简单，以便提高转换速度；
所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费；

2）制定一个好的解决冲突的方案

查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律的查询其他相关单元。

有

直接定址法
数字分析法
平方取中法
折叠法
残留余数法
随机数法

6.3.3.1.1 直接定值法

Hash(key) = a*key + b (a,b为常数)

优点：以关键码key的某个线性函数值为散列地址，不会产生冲突

缺点：要占用连续地址空间，空间效率低

6.3.3.1.2 残留余数法

Hash(key) = key mod p (p是一个整数)

关键：如何选取合适的p？

技巧：设表长为m，取p<=m且为质数

6.3.3.2 处理冲突的方法

开放定址法（开地址法）
链地址法（拉链法）
再散列法（双散列函数法）
建立一个公共溢出区

6.3.3.2.1 开放定址法

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

6.3.3.2.2 链地址法

基本思想：相同散列地址的记录链成一个单链表

m个散列地址就设m个单链表，然后将m个单链表的表头至臻存储起来，形成一个动态结构

6.3.3.3 哈希表的查找

07 排序

7.1 基本概念和排序方法的概述

排序：将一组杂乱无章的数据按照一定的规律顺次排列起来

如果参加排序的数据结点包含多个数据域，那么排序往往针对某个域而言。

按照存储介质可分为：

内部排序：数据量不大，数据在内存，无需内存外交换数据
外部排序：数据量大，数据在外存

按比较器个数可分为：

串行排序：单处理机（同一时刻比较一对数据元素）
并行排序：多处理机（同一时刻比较多对数据元素）

按照主要操作可分为：

比较排序：用比较的方法
- 插入排序、交换排序、选择排序、归并排序
基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置

按辅助空间可分为：

原地排序：辅助空间用量为O(1)的排序方法
非原地排序：辅助空间用量超过O(1)的排序方法

按稳定性可分为：

稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
非稳定性排序：不是稳定排序的方法
排序的稳定性只对结构类型数据排序有意义

按自然性可分为：

自然排序：输入数据越有序，排序的速度越快的排序方法
非自然排序：不是自然排序的方法

#define MAXSIZE 20
typedef int KeyType;

typedef struct {
    KetType key;
    InfoType otherinfo;
}RedType;

typedef struct {
    RedType r[MAXSIZE + 1];
    int length;
}SqList;

7.2 插入排序

基本思想：

每一步将一个待排序的对象，按其关键码大小，插入到已经排好序的一组对象的适当位置上，直到对象全部插入为止。

插入排序分为

顺序法定位插入位置———直接插入排序
二分法定位插入位置———二分插入排序
缩小增量多遍插入排序—-希尔排序

7.2.1 直接插入排序

void InsertSort(SqList &L) {
    int i, j;
    for(i = 2; i <= L.length; i++) {
        if(L.r[i].key < L.r[i-1].key) {
            L.r[0] = L.r[i];
            for(j = 1; L.r[0].key < L.r[j].key; j--) {
                L.r[j+1] = L.r[j];
            }
            L.r[j+1] = L.r[0];
        }
    }
}

7.2.1.1 性能分析

最好的情况（关键字在记录序列中顺序有序）

“比较”的次数为n-1次

“移动”的次数为：0

最坏的情况（关键字在记录序列中逆序有序）

“比较“的次数为[(n+2)(n-1)]/2次

“移动”的次数为[(n+4)(n-1)]/2次

平均情况：

比较：[(n+2)(n-1)]/4次

移动：[(n+6)(n-1)]/4次

原始数据越接近有序，排序速度越快

7.2.2 折半插入排序

void BInsertSort(SqList& L) {
    for(int i = 2; i < L.length; i++) {
        int low = 1, hight = i - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if(L.r[0].key < L.r[mid].key) {
                high = mid - 1;
            }
            else {
                low = mid + 1
            }
        }
        for(int j = i - 1; j >= high + 1; j--) {
            L.r[j + 1] = L.r[j];
        }
        L.r[high + 1] = L.r[0];
    }
}

7.2.2.1 性能分析

这般查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快
它所需要的关键码比较次数与待排序对象序列的初始排列无关，进依赖于对象的个数，在插入第i个对象时，需经过int(log_2i) + 1次关键码比较
当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好的情况要差
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
平均性能优于直接插入排序

7.2.3 希尔排序

基本思想：

先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。

一次移动，移动位置较大，跳跃式地接近排序后的最终位置
最后一次只需要少量移动
增量序列必须是递减的，最后一个必须是1
增量序列应该是互质的

void ShellSort(SqList& L, int dlta[], int t) {
    for(int k = 0; k < t; k++) {
        ShellInsert(L, dlta[k]);
    }
}

void ShellInsert(SqList& L, int dk) {
    for(int i = dk + 1; i <= L.length; i++) {
        if(L.r[i].key < L.r[i - dk].key) {
            L.r[0] = L.r[i];
            for(int j = i - dk; j > 0 && (L.r[0].key < L.r[j].key); j = j-dk)
                r[j + dk] = r[j];
            r[j + dk] = r[0];
        }
    }
}

7.3 交换排序

常见的交换排序：

冒泡排序：O(n^2)
快速排序：O(n*log_2n)

基本思想：每趟不断将记录两两比较，并按”前小后大“规则交换

7.3.1 冒泡排序

n个记录，总共需要n-1趟
第m趟，需要比较n-m次

void bubble_sort(SqList& L) {
    int m, i, j;
    RedType x;
    for(m = 1; m < n - 1; m++) {
        for(j = 1; j < n - m; j++) {
            if(L.r[j].key > L.r[j + 1].key) {
                x = L.r[j];
                L.r[j] = L.r[j + 1];
            }
        }
    }
}

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；

改进的冒泡排序算法

void bubble_sort(SqList& L) {
    int m, i, j, flag = 1;
    RedType x;
    for(m = 1; m <= n - 1 && flag == 1; m++) {
        flag = 0;
        for(j = 1; j <= m; j++) {
            if(L.r[j].key > L.r[j + 1].key) {
                flag = 1;
                x = L.r[j];
                L.r[j] = L.r[j + 1];
                L.r[j + 1] = x;
            }
        }
    }
}

7.3.2 快速排序

基本思想：

任取一个元素为中心
所有比它小的元素一律前放，比它大的元素一律后放，形成两个子表
对各子表重新选择中心元素并依次规则调整
知道每一个子表的元素只剩一个
通过一趟排序，将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
具体实现：选定一个中间数作为参照，所有元素与之比较，小的调到其左边，大的调到其右边
中间数：可以是第一个元素，也可以区最后一个，也可以中间一个，也可以随机一个

void main() {
    QSort(L, 1, L.length);
}  

void QSort(SqList& L, int low, int high) {
    if(low < high) {
        pivotloc = Partition(L, low, high);  // 将L.r[low..high]一分为二，pivotloc为枢轴元素排好序的位置
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
    }
}

int Partition(SqList& L, int low, int high) {
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while(low < high) {
        while(low < high && L.r[high].key >= pivotkey) high--;
        L.r[low] = L.r[high];
        while(low < high && L.r[low].key <= pivotkey) low++;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}

时间复杂度

Qsort()：O(log_2n)
Partition()：O(n)
平均计算时间：O(n*log_2n)

实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序算法中最好的一个

快速排序不是原地排序

空间复杂度：

平均情况下：O(logn)
最坏情况下：O(n)

快速排序是一种不稳定的排序方法

快速排序不适用于对原本有序或基本有序的记录序列进行排序

划分元素的选取是影响时间性能的关键
输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法

7.4 选择排序

7.4.1 简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置

基本操作：

首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一次记录交换
再通过n-2次关键字比较，从n-1个记录中找出关键字次小的记录，将它与第二个位置交换
重复上述操作，共进行n-1趟排序后，排序结束

void SelectSort(SqList& K) {
    for(int i = 1; i < L.length; i++) {
        int k = i;
        for(int j = i + 1; j <= L.length; j++) {
            if(L.r[j].key < L.r[k].key) k = j;
        }
        if(k!=i) {
            RedType temp = L.r[i];
            r[i] = L.r[k];
            r[k] = temp;
        }
    }
}

7.4.2 堆排序

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它孩子的结点

若在输出堆顶的最小值（最大值）后，使得剩余的n-1个元素的序列重新又建成一个堆，则得到n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程称为堆排序。

小根堆

输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为”筛选“

大根堆

输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中大者进行交换；
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为”筛选“

void HeapAdjust(elem R[], int s, int m) {
    rc = R[s];
    for(j = 2 * s; j <= m; j *= 2) {
        if(j < m && R[j] < R[j + 1])
            j++;
        if(rc >= R[j])
            break;
        R[s] = R[j];
        s = j;
    }
    R[s] = rc;
}

7.4.2.1 堆的建立

1
2
3

for(i = n/2; i >= 1; i--) {
    HeapAdjust(R, i, n);
}

7.4.2.2 堆排序

void HeapSort(elem R[]) {
    int i;
    for(i = n/2; i >= 1; i--)
        HeapAdjust(R, i, n);
    for(i = n; i > 1; i--) {
        Swap(R[1], R[i]);
        HeapAdjust(R, 1, i-1);
    }
}

7.5 归并排序

基本思想：将两个或两个以上的有序序列”归并“为一个有序序列

在内部排序中，通常采用的是2-路归并排序

即将两个位置相邻的有序子序列R[I…m]和R[m+1…n]归并成为一个有序序列R[I…n]

整个归并排序仅需log_2n上界

7.6 基数排序

基本思想：分配+收集

也叫桶排序或箱排序

基数排序：数字是有范围的，均由0-9这十个数字组成，则需设置十个桶，相继按个、十、百…进行排序

7.7 外部排序

7.8 各种排序方法的比较

类别	排序方法	时间复杂度			空间复杂度	稳定性
		最好情况	最坏情况	平均情况	辅助存储
插入排序	直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
	希尔排序	O(n)	O(n^2)	O(n^1.3)	O(1)	不稳定
交换排序	冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
	快速排序	O(n*logn)	O(n^2)	O(n*logn)	O(n*logn)	不稳定
选择排序	直接选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定/稳定
	堆排序	O(n*logn)	O(n*logn)	O(n*logn)	O(1)	不稳定
归并排序		O(n*logn)	O(n*logn)	O(n*logn)	O(n)（最大）	稳定
基数排序	k:待排序元素的维数；m:基数的个数	O(n+m)	O(k*(n+m))	O(k*(n+m))	O(n+m)	稳定

7.8.1 时间性能

1、按平均的时间性能来分，由三类排序方法

时间复杂度为O(n*logn)的方法有：
- 快速排序（最好）
- 堆排序
- 归并排序
时间复杂度为O(n^2)的有：
- 直接插入排序（最好，对关键字序列本身有序的）
- 冒泡排序
- 简单选择排序
时间复杂度为O(n)的排序方法只有：基数排序

2、当待排序记录序列按关键字有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快排而言，这是最不好的情况，此时的时间性能退化为O(n^2)，因此是应该尽量避免这种情况。

3、简单选择排序、堆排序和归并排序的时间性能不随记录序列中的关键字的分布而改变

7.8.2 空间性能

指的是排序过程中所需的辅助空间的大小

1、所有简单排序方法（包括：直接插入、冒泡和简单选择）和堆排序的空间复杂度都为O(n)

2、快速排序为O(logn)，为栈所需的辅助空间

3、归并排序所需辅助空间最多，其空间复杂度为O(n)

4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

7.8.3 排序方法的稳定性能

稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和排序之后，没有改变
当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法
对于不稳定的排序方法，只要能举出一个示例说明即可
快速排序h额堆排序是最不稳定的排序方法

7.8.4 关于”排序方法的时间复杂度的下限“

本章讨论的各种排序方法，除基数排序之外，其他方法都是基于”比较关键字“进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(n*logn)
可以用一棵判定树来描述这类基于”比较关键字“进行排序的排序方法