数据结构总结

时间复杂度


$\Theta(N^2\log_2 N^2)=\Theta(N^2\log_2 N)$

D



线性表



线性表（线性表逻辑结构、顺序表、链表基本操作算法实现及效率分析）

逻辑结构及基本运算



物理结构


顺序存储的

线性表中结点存放在连续的空间（物理位置和逻辑位置是一致的）

数组实现。为了随时可以插入或者删除，采用动态数组。

需要三个变量：指向数组的指针，数组规模，数组中实际元素的个数。

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

template<classelemType>
seqList<elemType>::seqList(intinitSize)//构造函数
{
    data=new elemType[initSize];
    if(!data)throwIllegalSize(); //空间没有申请成功，抛出异常
    maxSize=initSize;
    currentLength=0;
}
template<classelemType>
intseqList<elemType>::length()const
{ return currentLength; }

template<classelemType>
int seqList<elemType>::search(constelemType&x)const
{ int i;
for(i=0;i<currentLength;i++)
if(data[i]==x)break;
if(i==currentLength)return -1;
elsereturni;
}
template<classelemType>
elemTypeseqList<elemType>::visit(int i) const
{
if(i<0 || i>=currentLength)
throw OutOfBound();
return data[i];
}
template<classelemType>
void seqList<elemType>::doubleSpace()
{ elemType*tmp=new elemType[maxSize*2];
if(!tmp)throw IllegalSize();
for(j=0;j<length;++j)tmp[j]=data[j];
delete[]data;
data=tmp;
maxSize=maxSize*2;
}
template<class elemType>
void seqList<elemType>::remove(int i)
{
    if(i<0 || i>=currentLength)
    throw OutOfBound();
    for(int j=i;j<currentLength-1;j++)
    data[j]=data[j+1];
    --currentLength;
}

链式存储的

将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的指针来给出。结点的存储单元在物理位置上可以相邻，也可以不相邻

单链表



如删除都是改变前一个结点中的指针值，使其指向欲删结点的下一结点，而不用考虑删除首结点的特殊性.








双链表



D.

线性表类的应用

STL（标准模版库）是C++中数据结构的实现。这些数据结构被称为集合或容器。

STL中线性表的实现有两种：

• Vector：线性表的顺序实现
• List：线性表的双链表的实现



完成函数changOrder()的定义如下：

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

template <class elemType>
void DlinkList<elemType>::changOrder() {
    if (head == NULL || head == tail || head->next == tail) {
        // 链表为空或只有一个结点，无需操作
        return;
    }
    
    // 计算链表长度
    int length = 0;
    node* current = head;
    while (current != tail) {
        length++;
        current = current->next;
    }
    length++; // 加上尾结点
    
    // 将前半段的结点移到后半段
    int moveCount = length / 2;
    current = head;
    for (int i = 0; i < moveCount; i++) {
        current = current->next;
    }
    // 重新连接链表
    tail->next = head;
    head->prior = tail;
    tail = current->prior;
    tail->next = NULL;
    current->prior = NULL;
    head = current;
}

该函数的实现思路如下：

1. 首先，判断链表是否为空，或者只有一个结点，或者只有两个结点。如果是，则无需进行操作，直接返回。
2. 计算链表的长度，可以遍历链表并计数，或者在插入和删除操作时维护一个长度变量，这里选择遍历计数的方式。
3. 确定需要将前半段的结点移动到后半段的数量。由于链表是双向循环的，因此可以通过将长度除以2来得到。
4. 通过遍历找到需要移动的起始位置，将current指针指向该位置。
5. 重新连接链表：将原先的尾结点的next指针指向原先的头结点，将原先的头结点的prior指针指向原先的尾结点，更新尾结点为current的前一个结点，将current的前一个结点的next指针置为NULL，将current的prior指针置为NULL，更新头结点为current。

完成上述操作后，双向循环链表的前半段结点已经全部移到后半段中。

链表怎么画

在一个长度为 n 的顺序表的任意位置插入一个新元素的时间复杂度为

O(n)

已知一个线性表中最常用的操作是删除第一个元素和在最后一个元素之后插入一个元素，则采用______存储方式最节省运算时间。

双链表

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

对线性表进行二分查找时，要求线性表必须

以顺序方式存储，且数据元素有序

$[\log_2 n]$

查找元素

已知如下代码的功能是在 带头结点 单链表中查找第一个值在[min, max]间的元素位置, 则空白处的代码分别是？假设首结点中元素满足条件则返回 0。

1
2
3
4
5
6
7
8
9
10
11
12

template<class elemType> 
int sLinkList<elemType>::findInDomain(const elemType &min, const elemType &max) 
{
    int i = 0; 
     node *p = head->next; 
     while(p){
        if(min <= p->data && p->data <=max)  return i; 
         i++; 
         p = p->next; 
     } 
     return -1; 
} 

求倒数第 k 个元素

已知一个带有表头结点的单链表，结点结构为：struct Node{ int data, Node *next}
假设该链表只给出了头指针 head。在不改变链表的前提下，请设计一个尽可能高效的算
法，查找链表中倒数第 k 个位置上的结点( k 为正整数)。
若查找成功，函数输出该结点的data 域的值，并返回 1；否则，返回 0。（5 分）

1
2
3
4
5
6
7
8
9
10

bool getK(Node *p,int k){
	static int cnt=0;
   	bool success=p->next==NULL?false:getK(p->next,k);
    cnt++;
    if (cnt==k){
        printf("%d\n",p->data);
		return true;
    }
    return success;
}



单链表创建元素应该也需要一定的时间。

栈

栈（栈特点、顺序栈、链式栈及其基本操作实现、栈的典型应用）

栈的概念




栈的顺序实现

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

template <class elemType>
class stack
{
private:
    elemType *elem;//首地址
    int top_p;//栈空=-1
    int maxSize;//数组规模
    void doubleSpace();
public:
	virtual bool isEmpty() const = 0;
	virtual elemType top() const = 0;
	virtual void push(const elemType &x) = 0;
	virtual elemType pop() = 0;
	virtual ~stack() {}
};
template <class elemType>
seqStack<elemType>::seqStack(int initSize)
{
	elem = new elemType[initSize];
	if (!elem)
		throw illegalSize();
	maxSize = initSize;
	Top = -1; // 注意从-1开始，数组从0开始
}
template <class elemType>
class seqStack<elemType>::~seqStack()
{
	delete[] elem;
}
template <class elemType>
bool seqStack<elemType>::isEmpty() const
{
	return (Top == -1);
}
template <class elemType>
void seqStack<elemType>::push(const elemType &x)
{
	if (Top == maxSize - 1)
		doubleSpace();
	elem[++Top] = x;
}
template <class elemType>
elemType seqStack<elemType>::top() const
{
	if (Top == -1)
		throw outOfBound();
	return elem[Top];
}
template <class elemType>
elemType seqStack<elemType>::pop()
{
    //这里没有释放空间的操作
	if (Top == -1)
		throw outOfBound();
	return elem[Top--];
}


栈的链式实现

用单链表存储栈中元素，栈的操作都是在栈顶位置进行的，没有其他位置情 况，故不需要头结点（不需要没有数据的头结点，头指针还是有的）

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
58
59
60
61
62
63
64
65
66

template <class elemType>
class linkStack : public stack<elemType>
{
private:
	struct node
	{
		elemType data;
		node *next;
		node(const elemType &x, node *N = NULL)
		{
			data = x;
			next = N;
		}
		node() : next(NULL) {}
		~node() {}
	};
	node *Top; // 变量Top区别于函数top
public:
	linkStack();
	~linkStack();
	bool isEmpty() const;
	elemType top() const;
	elemType pop();
	void push(const elemType & x);
};
template <class elemType>
linkStack<elemType>::linkStack() { Top = NULL; }
template <class elemType>
linkStack<elemType>::~linkStack()
{ // 释放每个结点
	node *tmp;
	while (Top != NULL)
	{ // 两个指针协同法
		tmp = Top;
		Top = Top->next;
		delete tmp;
	}
}
template <class elemType>
bool linkStack<elemType>::isEmpty() const
{
	return Top == NULL;
}
template <class elemType>
elemType linkStack<elemType>::pop()
{
	if (Top == NULL)
		throw outOfBound();
	node *tmp = Top;
	elemType x = Top->data;
	Top = Top -> next;
	delete tmp;
	return x;
}
template <class elemType>
elemType linkStack<elemType>::top() const
{
	if (Top == NULL)
		throw outOfBound();
	return Top->data;
}
template <class elemType>
void linkStack<elemType>::push(const elemType &x)
{
	Top = new node(x, Top);
}

所有的操作都是对栈顶的操作，和栈中元素个数无关

所有运算的时间复杂度都是O(1)




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

bool parenMatch(const char *str) // 仅实现小括号
{
	linkStack<char> s; // 建立一个字符栈，放左括号
	while (*str != '\0')
	{
		switch (*str)
		{
		case '(':
			s.push(*str);
			break; // 注意break
		case ')':
			if (s.isEmpty()) // 读入闭括号，栈空，不匹配
			{
				cout << "An opening bracket '(' is expected!\n";
				return false;
			}
			else
				s.pop(); // 栈中都是开括号，弹出一个即可
			break;
		}
		str++;
	}
	if (!s.isEmpty()) // 式子读入结束，发现栈中还有多余的开括号
	{
		cout << "A closing bracket ')' is expected!\n";
		return false;
	}
	return true;
}


表达式计算







B


注意不是在结构体里。


括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool CheckMatch(const char* str) 
{
    char ch; 
    seqStack<char> stk; 
    while (ch = *str++) 
    {
        switch (ch) 
        { 
            case '(': 
                stk.push('('); 
                break; 
            case ')': 
                if (stk.empty()) return false; 
                stk.pop(); 
        break; 
    } 
} 
return true;

队列

（队列的定义及相关概念、基本操作、顺序队列、顺序循环队列及其基本操作的实现、链式队列及其基本操作的实现、队列的应用。）

顺序结构

三种组织方式：

• 队头位置固定

  

• 队头位置不固定

  

• 循环队列

  

循环队列：

• 出队后队列变空

  

• 入队后队列满

  

• 解决方案：规定front指向的单元不能存储队列元素，只起到标志作用，表示后面一个是队头元素。即当尚余一个空单元时，队列就算满了。

  • 队列满的条件是：(rear + 1) % MaxSize == front
  • 队列空的条件是front == rear。

链式结构

• 由于队列的操作是在队列的两端进行的，不会对队列中的其他元素进行操作，用不带头结点单链表就够了。
• 
• 队列要对表的两端作操作，为方便两端操作，可以采用空间换时间的方法，同时记住头、尾结点的位置。

队头、队尾的选择：将单链表的表头作为队头，单链表的表尾作为队尾。

特点：

• 链接队列不会出现队列满的情况，但队列为空的情况依然存在。
• 队列为空时，单链表中没有结点存在，即首、尾指针都为空指针。
• 保存一个链接队列只需要两个指向单链表结点的指针front和rear，分别指向首尾结点。
• 队列的基本运算实现简单，都是 $O(1)$ 的时间复杂度。
• 析构函数是 $O(n)$

顺序实现和链接实现的比较：

• **时间：**两者都能在常量的时间内完成基本操作，但顺序队列由于采用回绕，使入队和出队的处理比较麻烦。
• **空间：**链接队列中，每个结点多一个指针字段，但在顺序队列中有大量的尚未使用的空间。


队头出队，队尾入队。


A.

如果 end1 指向队头元素，end2 指向队尾元素，那么 end1==(end2+1) mod M，而且 end1==(end2+1) mod M 才能判断。注意这里队列满是 M-1 个元素，如果 M 个元素满无法判断。

树


• 树的高度：$h$，只有根的高度为 $1$.
• 结点的高度：叶节点高度为 $0$.

二叉树的基本概念

定义：二叉树（Binary Tree）是结点的有限集合。

• 它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，其左、右子树又都是二叉树。

• 注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。

• 满二叉树：每一层都最大值。

- 完全二叉树：在满基础上从右到左去掉若干个节点。


• 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为 完全二叉树。

• 具有 $n$ 个结点的完全二叉树的高度 $k=[\log_2 n]+1$。

• 对于一棵非空二叉树，如果叶子节点数为 $n_0$，度数为 $2$ 的节点数为 $n_2$，则有 $n_0=n_2+1$ 成立。

​ 证明：总结点数为 $n=n_0+n_1+n_2$，而边的数目为 $n-1=n_1+2n_2$。得到 $n_0=n_2+1$。

• 给完全二叉树依次编号：如果 $i=1$，为根结点；如果 $i>1$，则其父亲结点的编号为 $[i/2]$
  • 有n个结点，高度为n的不同二叉树个数为 $2^{n-1}$
• 二叉树叶结点个数 $a$，非叶结点个数 $b$，则 $a=b+1$
  • 完全二叉树结点个数 $m$，叶结点个数 $n$ ：$m=2n-1$
  • 任意形式的树中结点数 $=$ 所有结点度数和 $+1$
  • 一棵有 $n$ 个叶结点的完全二叉树，最多有 $2n$ 个结点


类似的分析方法，假设结点个数为 $n$，则有 $n-50$ 个结点有两个孩子……


C


B. 一条链。


规律：一棵有 $n$ 个叶结点的完全二叉树，最多有 $2n$ 个结点。

已知一个二叉树的前序+后序遍历，不能唯一确定这棵二叉树。

已知二叉树的前序+中序遍历，能唯一确定这棵二叉树。

已知二叉树的后序+中序遍历，能唯一确定这棵二叉树。




B

顺序实现

特点：

• 存储空间的浪费。
• 一般只用于一些特殊的场合，如静态的并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。

链式结构

遍历二叉树

遍历：前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层次遍历

• 根据暂存工具的不同选择：队列-层次遍历 栈-前序、中序和后序遍历

前序遍历的非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

template<class T>
void binaryTree<T>::preOrder()const
{
    linkStack<Node*> s;
    Node *current;
    
    cout << "前序遍历：";
    s.push(root);
    while(!s.isEmpty())
    {
        current = s.pop();
        cout << current->data;// LRN
        if(current->right != NULL) s.push(current->right);
        if(current->left != NULL) s.push(current->left);
    }
}




中序遍历的非递归实现

需要在binaryTree类中定义一个能够计算入栈次数的私有内嵌类StNode。

1
2
3
4
5
6

struct StNode
{
    Node *node;
    int TimesPop;
    StNode(Node *N = NULL):node(N), TimesPop(0){}
};

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

template<class T>
void binaryTree<T>::midOrder()const
{
    linkStack<StNode> s;
    StNode current(root);
    
    cout << "中序遍历：";
    s.push(root);
    while(!s.isEmpty())
    {
        current = s.pop();
        if(++current.TimesPop == 2)
        {
            cout << current.node->data;
            if(current.node->right != NULL)
                s.push(StNode(current.node->right));
        }
        else
        {
            s.push(current);
            if(current.node->left != NULL)
                s.push(StNode(current.node->left));
        }
    }
}

后序遍历的非递归实现

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

template<class T>
void binaryTree<T>::postOrder()const
{
    linkStack<StNode> s;
    StNode current(root);
    
    cout << "后序遍历：";
    s.push(root);
    while(!s.isEmpty())
    {
        current = s.pop();
        // LRN 第三个是 N
        if(++current.TimesPop == 3)//第三次出栈
        {
            cout << current.node->data;
            continue;
        }
        s.push(current);
        if(++current.TimesPop == 1)//第一次出栈
        {
            if(current.node->left != NULL)
                s.push(StNode(current.node->left));
        }
        else//第二次出栈
        {
            if(current.node->left != NULL)
                s.push(StNode(current.node->left));
        }
    }
}

层次遍历二叉树

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

#include <queue>

template <class Type>
void BinaryTree<Type>::layorder(Node<Type> *&t) const {
    if (t == NULL)
        return;

    std::queue<Node<Type> *> q;
    q.push(t);

    while (!q.empty()) {
        Node<Type> *current = q.front();
        q.pop();

        // 处理当前节点
        // 可以根据需求进行相应操作，比如输出节点值
        // std::cout << current->data << " ";

        // 将当前节点的左右子节点入队
        if (current->left != NULL)
            q.push(current->left);
        if (current->right != NULL)
            q.push(current->right);
    }
}

在上面的代码中，我们使用了一个队列来实现按层次遍历。首先，我们将根节点入队。然后，从队列中取出一个节点，处理它（可以根据需求进行相应操作，比如输出节点值），并将其左右子节点入队。重复这个过程，直到队列为空。

你可以在// 处理当前节点的位置添加相应的代码来处理每个节点。这里我注释掉了输出节点值的部分，你可以根据需要取消注释并根据实际情况进行修改。

请注意，上面的代码是对给定的BinaryTree类进行了一些假设，并使用了std::queue。你可能需要根据你的实际情况进行一些调整和修改，以使其适应你的代码和环境。

哈夫曼算法（最优二叉树）

• 最优二叉树也被称为哈夫曼树
• 哈夫曼编码：左枝为0，右枝为1
  • 每个字符的编码是根节点到该字符的路径
• 前缀编码可被唯一解码
  • 字符只放在叶结点中
  • 由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀




• 在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为 $2$ 的节点。
• 一旦给定了要编码的元素个数，可知哈夫曼树的大小为 $2n-1$
• 哈夫曼树可以用一个大小为 $2n$ 的数组来存储。$0$ 节点不用，根存放在节点 $1$ 。叶结点依次放在 $n$ 到 $2n-1$ 下标位置。
• 每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置






D

求二叉树高度

二叉树的结点类说明如下：

1
2
3
4
5
6

struct Node { //二叉树结点 
    Node *left , *right ; 
    T data; 
    Node() : left(NULL), right(NULL) { } 
    ~Node() {} 
}; 

编写函数 int binaryTree<T>::height (binaryTree<T>::Node *t) const 求给定二叉树的高度， 只包含根结点的二叉树高度定义为 1。

1
2
3
4

int binaryTree<T>::height (binaryTree<T>::Node *t) const{
	if (t==NULL) return 0;
    return std::max(height(t->left),height(t->right))+1;
}

二叉树合并

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

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
	TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2)
	{
		if (t1 && t2)
		{
			int sum = t1->val + t2->val;
			TreeNode *rt = new TreeNode(sum);
			rt->left = mergeTrees(t1->left, t2->left);
			rt->right = mergeTrees(t1->right, t2->right);
			return rt;
		}
		else if (t1)
		{
			TreeNode *rt = new TreeNode(t1->val);
			rt->left = mergeTrees(t1->left, NULL);
			rt->right = mergeTrees(t1->right, NULL);
			return rt;
		}
		else if (t2)
		{
			TreeNode *rt = new TreeNode(t2->val);
			rt->left = mergeTrees(t2->left, NULL);
			rt->right = mergeTrees(t2->right, NULL);
			return rt;
		}
		else
		{
			return NULL;
		}
	}
};

孩子兄弟法表示树

要计算使用孩子兄弟表示法表示的树的高度，可以使用非递归的方式进行遍历并记录树的深度。

以下是一个使用迭代方式计算孩子兄弟表示法树高度的函数：

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

#include <stack>
#include <algorithm>

struct node {
    int data;
    node *left, *right;
};

int getLen(node *root) {
    if (root == nullptr) { // 注意判断特殊情况
        return 0; // 空树高度为0
    }

    int height = 0;
    std::stack<node *> nodeStack;
    std::stack<int> depthStack;
    nodeStack.push(root);
    depthStack.push(1);

    while (!nodeStack.empty()) {
        node *current = nodeStack.top();
        nodeStack.pop();

        int currentDepth = depthStack.top();
        depthStack.pop();
        
        height = std::max(height, currentDepth);

        if (current->right) {
            nodeStack.push(current->right);
            depthStack.push(currentDepth);
        }

        if (current->left) {
            nodeStack.push(current->left);
            depthStack.push(currentDepth + 1);
        }
    }

    return height;
}

该函数使用两个栈：一个存储节点指针，一个存储节点所在的深度。

函数从根节点开始遍历，每次弹出一个节点时，将其右孩子（如果存在）入栈，并将其左孩子（如果存在）入栈。同时，记录节点的深度，并在遍历过程中更新树的最大深度。

最后，返回计算出的树的高度。

请注意，函数假设孩子兄弟表示法中，左孩子指针指向节点的第一个子节点，右孩子指针指向节点的下一个兄弟节点。如果使用不同的表示方法，可能需要进行适当的修改。

优先队列

（优先队列、二叉堆、基于二叉堆的优先队列实现）




堆的结构

是完全二叉树，可以以数组下标 $1\sim n$ 表示。每个节点存有一个元素。

（大根）堆性质：父亲的权值不小于儿子的权值。最大值在树根。

堆性质比较弱，二叉堆不是唯一的。

堆操作

取最大值

插入操作

先将这个节点放在堆最后（完全二叉树的末尾），然后 向上调整。

向上调整的过程：如果这个节点的权值大于父亲的权值，就交换，重复此过程直到不满足或到根。

这样的操作只会影响最后一个节点到根这条链，而经过插入操作，插入节点的祖先保持不变，而插入节点和其之下的那条链元素全部增大，但是保持大小关系，因此满足堆性质。

完全二叉树的深度是 $\log n$ 级别的，因此插入操作是 $O(\log n)$ 的。

1
2
3
4
5
6

void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}

增加某个点的权值

同插入操作，向上调整即可。

删除操作

删除操作只能删除堆中最大的元素，即优先队列的 pop_front 操作。

删除操作的过程是将堆的最大元素和最后一个节点直接交换，然后删掉最后一个节点，通过 向下调整 来维持堆性质。

向下调整的过程：在节点的儿子中，找一个最大的，与该节点交换，如果满足堆性质，即当前节点比两个儿子节点都大，则结束，重复此过程直到底层。

向下调整不能完全说是向上调整的逆过程，因为向下调整明明那条路径都行，凭什么要选择儿子最大的路径？

是因为交换之后，交换上去的节点要成为现在节点的父亲，也要满足堆性质，因此一定要选择儿子最大的路径。

1
2
3
4
5
6
7
8
9

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;//选择最大的儿子
    if (h[t] <= h[x]) break;//当前节点比两个儿子节点都大，则结束
    std::swap(h[x], h[t]);
    x = t;
  }
}

建堆

可以直接对元素从大到小排序，也可以依次向上调整。

可视化如下。

堆的应用

对顶堆

动态维护一个序列上第 $k$ 大的数，$k$ 的值可以变化，但是每次变化的量级是常数。

题目


B


画图分析。



动态中位数问题。

第 $k$ 大的元素是从大到小第 $k$ 个。首先建大根堆 $O(n)$，然后 $k$ 次出队。

第二个函数建立小根堆，其中一直有 $K$ 个元素，如果来了一个元素比根结点大，则出队替换。


集合与静态查找



静态查找：无序表的查找


只能做到 $O(N)$.


$\frac{n+1}{2}$

静态查找：有序表的查找

顺序查找、二分查找 、插值查找、分块查找

顺序查找


二分查找


设有序顺序表里面有 $n$ 个数据元素，则利用二分查找法查找数据元素 $X$ 的最多比较次数不超过：

$\log_2 n+1$

插值查找


估计较为精确，访问磁盘次数少。数据有序且分布均匀。


分块查找




动态查找

集合中数据是动态的，有频繁的插入、删除操作，则称为动态查找表。既要支持快速查找，又要支持插入删除，可以使用什么样的结构？

（动态查找，二叉查找树的定义及基本操作实现、二叉平衡查找树的定义及基本操作算法、哈希法、哈希函数、哈希冲突解决方法及实现。）

动态查找表的抽象类



D.




$\frac{1}{4}\times 1+\frac{1}{8}\times 2+\frac{1}{8}\times 3+\frac{1}{2}\times 3$


二叉查找树


• 公有的成员函数：find、insert和remove 以及构造、析构函数.
• 二叉查找树的插入、删除和查找都是通过递归实现的，而这三个公有函数的参数表中并不需要包含递归参数。为此，对于每个公有的成员函数都定义了一个对应的带有递归参数的私有的成员函数.



查找操作

• 如果树为空，失败。
• 如果根结点的关键字等于查找的关键字，成功。
• 否则，若关键字值小于根结点，查左子树；若关键字值大于根节点，查其右子树。




1
2

return t;
t=t->rchild

插入操作

• 如果二叉树为空，则插入的节点成为根结点。
• 如果二叉树非空。首先执行查找算法，如果树中已有待插入的元素，则不必插入，否则，一直走到叶子结点，作为父亲节点。


递归实现比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template <class T> 
void binarySearchTree<T>::insert(T x) //非递归实现
{ 
     if (root == NULL){ 
         root = new Node(x); 
         return; 
     } 
     Node *t = root; 
     while (true){ 
         if (x == t->data) 
         	return; 
         if ((x < t->data && t->left == NULL) || (x > t->data && t->right == NULL)) 
         	break; //找到可以插入的父节点
         else if (x > t->data) 
        	t = t->right; 
         else 
         	t = t->left; 
     } 
     if (x<t->data) 
     	t->left = new Node(x); 
     else 
     	t->right = new Node(x); 
} 


删除操作

• 删除叶结点 直接删除。
• 删除有一个子结点的结点 将此孩子取代被删节点的位置。
• 删除有两个子结点的结点 选取替身取代被删节点。使用左子树中最大的节点或者右子树中最小的节点。左子树一直往右走，直到没有右子树，然后把下面的子树接上，并且替代被删节点的位置。




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

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL)
	{
	}
};
class Solution
{
public:
	TreeNode *Function(DataNode *pRoot, unsigned int k)
	{
		if (pRoot == NULL)
			return NULL; //这棵树为空
		TreeNode *ObjNode = NULL;
		Function(pRoot, &ObjNode, k);
		return ObjNode;
	}
	void Function(TreeNode *pRoot, TreeNode **ObjNode, unsigned int &k)
	{
		if (pRoot->left != NULL)
			Function(pRoot->left, ObjNode, k);
		if (*ObjNode == NULL)
		{
			if (k == 1)
			{
				*ObjNode = pRoot;
			}
			k--;
		}
		if (*ObjNode == NULL && pRoot->right != NULL)
			Function(pRoot->right, ObjNode, k);
	}
}



查找第 $k$ 大的元素，时间复杂度 $O(n)$。

编写函数 Node* find(int value, Node *t)，实现在二叉查找树上进行查找的递归算法。

1
2
3
4
5
6

Node * find(int value, Node *t){
	if (t->data==value) return t;
    if (value<t->data) return find(value,t->left);
    else return find(value,t->right);
}
//调用使用 find(value,t.root)


AVL 树

结点的平衡度=结点的左子树的高度－右子树的高度

子树的高度定义为子树的根节点距离最远的叶节点的距离。

每个结点的平衡因子都为 ＋1、－1、0

也就是每个结点的左右子树的高度最多差1

可以证明高度是 log 级别。$S_h=S_{h-1}+S_{h-2}$。

引起不平衡的情况


只用关心哪个子树多出来了。


哈希法/散列法


散列表（哈希表）：通过将关键字直接映射到表中的某个位置（key->位置）将关键字对应的数据元素存储在对应的位置（位置存数据）它的时间复杂性为 O(1)，优于任何其它的查找算法。但它不支持有关有序操作。



每个数据在表中的存储位置是由一个函数确定，该函数 以数据的关键字值为参数，计算出该关键字对应的存储位置，该函数称为哈希函数/散列函数

哈希函数的选择标准

• 散列地址尽可能均匀，使得冲突(不同关键字哈希到相同位置)机会尽可能的少
• 计算速度快

常用哈希函数

• 直接地址法 $H(key)=key,H(key)=a\times key+b$
• 除留取余法 $H(key)=key \pmod{p}(+c)$. 通常 $p$ 为小于可用空间的最大质数。
• 数字分析法 对关键字集合中的所有关键字，分析每一位上数字分布。取数字分布均匀的位作为地址的组成部分。即差别越大，造成的区分度越大。
• 平方取中法 如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大。由于中间各位和每一位数字都有关系，因此均匀分布的可能性较大。$321 * 321 = 10{\color{red}30}41$
• 折叠法 选取一个长度后，将关键字按此长度 分组相加，再取长度那么长的数字。如 $542242241\Rightarrow 542+242+241=1025\Rightarrow 25$.

冲突问题

当两个以上的关键字映射到一个存储单元时，称为冲突或碰撞

闭散列表

散列表必须支持的三个操作：插入、查找和删除。

散列表的用户在使用散列表时必须提供一个函数，从数据元素中提取出关键字字段并把它转换成整型数。为此，需要一个数据成员key，它是一个指向函数的指针.

• 线性探测法 当散列发生冲突时，探测下一个单元，直到发现一个空单元。查找 的方法：1. 计算关键字哈希后的地址 2. 如果地址不为空，如果等于要查找的关键字而且没有做删除标记，则查找成功，否则继续查找下一位置（称为探测） 3. 该地址为空，查找失败。删除 的方法：1. 找到该元素，做删除标记。插入 的方法：1. 计算关键字哈希后的地址 2. 如果地址不为空而且没有删除标记，则向后一位插入。

  

  $\frac{n(n-1)}{2}$

  

• 二次探测法 线性探查法，如果很多数据被哈希到同一位置，会极大降低效率，出现冲突时，地址序列为 H(key) = (key + i^2) MOD M。

  如果采用二次探测法，并且表的大小是一个素数，那么，如果表至少有一半是空的，新的元素总能被插入。而且，在插入过程中，没有一个单元被探测两次。

  设 $M$ 是表的大小，假设 $M$ 是一个大于 $3$ 的质数，只需要说明前 $\lceil M/2\rceil$ 个替换单元是不同的。设这些单元中的某两个单元是 $H+i^2 \pmod {M}$ 和 $H+j^2 \pmod{M}$，其中 $0\le i,j \le \lceil M/2\rceil$，那么可以说明 $(i+j)(i-j)=kM$。$i+j,i-j$ 中一个可以被 $M$ 整除，不成立。结论：如果前 $\lceil M/2 \rceil$ 个替换单元是不同的，而且保证如果表至少有一半是空的，一定能被插入（抽屉原理）不要让哈希表太满。

• 再次散列法，采用两个散列函数，$H_1$ 代表起始位置，$H_2$ 代表探测步长，即一步走的距离。$H_1(x)+iH_2(x)\pmod M$.


 利用哈希表长度和哈希函数进行构造



=0 代表后面没有了，所以之后都不用看了。




开散列表 将碰撞的结点存放在散列表外的各自的线性表中（拉链法）怎么画？

• 开散列表是将所有散列到同一地址的元素链成一个单链表
• 散列表保存在一个数组中，数组的每个元素是一个指针，指向对应的单链表的首地址
• 开散列表的行为除了构造函数和析构函数之外，还支持插入、删除和查找操作






特殊讨论删除第一个节点的情况。



1
2

hashtable[i]=NULL;
hashtable[i]=s;

内排序

（内排序中的插入排序算法、选择排序算法、交换排序算法、归并排序、基数排序）

定义

排序：把集合中的数据元素按照它们的关键字的非递减或非递增 序排成一个序列

稳定与非稳定排序 如果在待排序列中存在多个关键字值相同的数据元素，如果经过排序后，这些数据元素的相对次序保持不变，即在原序列中 $K_i=K_j$ 且 $i<j$， 那么在排序后 $R_i$ 依然在 $R_j$ 的前面，则称为稳定，否则是不稳定的。

为什么需要考虑排序的稳定性？


内排序与外排序 内排序在内存之中，元素较少，外排序在磁盘（外部存储器），元素较多。

https://www.cnblogs.com/nicaicai/p/12689403.html


A.

插入排序

直接插入排序

从第一个元素起，将之后的元素依次插入到已排序 的序列中，保持有序，直至结束。稳定（如果插入在相同元素的末尾处）


最差情况：输入逆序，计算复杂度最高；最优情况：输入已经排序，运行时间 $O(N)$.

适用于排序元素少，且几乎已经有序。

二分插入排序

可以提升查找的速度，不能解决元素移动的次数。

希尔排序

直接插入排序的高代价主要是由大量的移动产生。如何避免大量的数据移动？比较离得较远的元素，然后比较离得较近的元素。



证明，一个 $h_k-$ 有序的数组经过 $h_{k-1}-$ 排序之后也是 $h_k-$ 有序的。其中 $h_{k-1} < k_k$

例如，对于 9 4 2 8 7 5 3 6 ，进行一次 $3-$ 排序之后，得到 3 4 2 8 6 5 9 7，比较的序列为 3 8 9, 4 6 7, 2 5，再进行一次 $2-$ 排序之后，得到 2 4 3 5 6 7 9 8，这是 $3-$ 有序的，比较的序列为 2 5 9, 4 6 8, 3 7。

引理

若序列 $X(x_1 \cdots x_{m+r}),Y(y_1,\cdots,y_{n+r})$ 满足

$\forall i = 1\cdots r, x_{i}\le y_{n+i}$

则对 $X,Y$ 分别升序排列后，仍然有上述关系存在。

对于任意的 $y_{n+k}$ 只要证明序列 $X$ 中存在 $k$ 个 $x$，使得 $y_{n+k} \ge x$，则经过排序这些 $x$ 都会到前面，也就是说，如果 $y_{n+k} > x_k$，则说明 $x_{k}$ 及之后都不满足 $y_{n+k} \ge x$，因此和条件矛盾。

如何证明这件事呢，观察到排序后 $y_{n+1} \le \cdots \le y_{n+k}$，因此，对于这些 $y$，必然能找到对应原来的位置，使得某个 $x_i \le y_{j}$，因此，得证。

主体证明

观察到

$a_1 \quad a_{1+k} \quad... \quad a_{1+nk} \\ a_2 \quad a_{2+k}\quad ... \quad a_{2+nk} \\ a_i \quad a_{i+k} \quad ... \quad a_{i+nk} \\$

是有序的。

取局部序列

$a_i \quad a_{i+h} \quad a_{i+2h} \cdots a_{i+nh}\\ a_{i+k} \quad a_{i+k+h} \quad a_{i+k+2h} \cdots a_{i+k+nh}$

对于上下两个项，满足小于等于的关系，因此排序后，仍然满足这个关系。


B.


选择排序

基本思想：每次从未排序的序列中选出最小元素，直到只剩一个元素。把得到的元素排成一列，即得到非递减序列。


直接选择排序

1. 选最小，得到下标。
2. 交换下标，而不是整体后移。



不是稳定排序方法。

如果一直选择最前面的，是不是稳定排序方法？也不是，例如 5,5,2 的序列，第一次得到 2,5,5，交换的是最后一个元素和第一个元素，因此不稳定。

堆排序

直接选择排序在 $n$ 个元素中选出最小元素需要 $n-1$ 次比较。而利用基于堆的优先队列选出最小元素只需要 $O(\log N)$ 的时间。

排序 $N$ 个元素，步骤如下：

• 建堆 buildHeap $O(N)$.
• 出堆 deleteMin $O(N\log N)$.

每次 deQueue 之后，堆缩小 1。因此在堆的最后那个位置可以用来存储刚才被删除的元素。从小到大排序使用最大堆方便，因为每次删去放到最后的应该是最大值。

不是稳定的排序


交换排序

比较待排序的元素的关键字，如果逆序，则交换。交换排序的特点：通过交换，将关键字较大的数据元素向序列的尾部移动。常用的交换排序：冒泡排序，快速排序。

冒泡排序

加上优化之后，冒泡排序适合于原本数据就非常有序的数据，冒泡排序是稳定的排序。





1
2

n-i
r[j+1]=r[j]

快速排序



快速排序的过程始终有一个空位没有补上，最后补上 $a[mid]$。

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

template <class KEY,class OTHER>
int divide(SET<KEY,OTHER>a[],int low,int high){
	SET<KEY,OTHER>k=a[low];
	do{
		while(low<high&&a[high].key>=k.key)high--;
		if(low<high){
			a[low]=a[high];
			low++;
		}
		while(low<high&&a[low].key<=k.key)low++;
		if(low<high){
			a[high]=a[low];
			high--;
		}
	}while(low!=high);
	a[low]=k;
	return low;
}
template<class KEY,class OTHER>
void quickSort(SET<KEY,OTHER>a[],int low,int high){
	int mid;
	if(low>=high)return;
	mid=divide(a,low,high);
	quickSort(a,low,mid-1);
	quickSort(a,mid+1,high);
}

不是稳定的排序。

快速排序的性能分析

$T(0)=T(1)=1\\ T(N)=T(i)+T(N-i-1)+cN$

最坏情况：$T(N)=T(N-1)+cN$。

最好/平均情况：$T(N)=2T(N/2)+cN,T(N)=O(N\log N)$。





归并排序

合并两个已经排序的有序表。

需要额外存储空间。





15 25 35 50

20 40 80 85

36 70

基数排序



按照“口袋”进行排序。


? 看最大位数。


关键字必须是整数。

总结

总结，学了哪些排序

• 插入排序 和初始数据相关，不稳定
  • 直接插入排序
  • 二分插入排序
  • 希尔排序（每趟排序内部使用的是插入排序）
• 选择排序 不稳定
  • 直接选择排序（一定 $O(N^2)$）
  • 堆排序
• 交换排序
  • 冒泡排序，和初始数据相关，如果比较有序，那么交换次数比较少
  • 快速排序，不稳定
• 归并排序，稳定
• 基数排序，稳定，时间复杂度 $O(最大数的位数\times N)$。

题目

一趟归并是指合并相邻的两个序列。



外部排序和查找

（B树、B+树的定义及基本操作实现、外排序中的置换选择预处理，二路、多路、多阶段归并）

上面的各种查找都是基于数据元素能够全部载入内存来讨论的。这里我们需要建立索引文件来处理较大的数据量。索引文件，通常按照关键字顺序存储了关键字和所属数据在原始文件中地址的对应关系，查找时首先在索引文件中按关键字查找，找到待查找关键字后，通过对应的地址信息，到数据文件就能读取目标数据。

主存储器与外存储器

处理外存储器时重点考虑减少访问次数。

内存 主存储器， 存储正在运行的程序代码及处理数据。时间复杂度是计算次数。

外存 用于储存长期保存的信息。优点是价格较低、存储量大和保存时间长，缺点是访问速度慢。时间复杂度：访问外存次数。

外部查找

10,000,000条记录，放不下内存，利用二叉查找树存在硬盘中，假设1秒钟可进行6次磁盘访问，平均情况，一次成功的查找需要1.38logN≈𝟑𝟑𝟑𝟑次磁盘访问，也就是5秒。

解决方法 依然利用树的结构，降低磁盘访问次数

• 增加树的分叉，降低树的高度
• 采用 $M$ 叉查找树
• 平衡 $M$ 叉查找树，高度 $O(\log _M N)$.

B 树

B 树是一种存储在外存储器中的动态查找表，$M$ 阶的 B 树必须满足如下定义：

1. 或者为空，或者只有一个根节点，或者除了根还有多个节点。
2. 根节点如果有儿子，至少有两个儿子，至多有 $M$ 个儿子。
3. 除了根节点外，每个非叶子节点至少有 $\lceil M/2 \rceil$ 个儿子，至多有 $M$ 个儿子。

非叶子节点结构如下（连续储存）：$K$ 代表关键字，$R$ 代表数据在原始文件中的地址，$A$ 代表树的子节点。$n$ 代表关键字的数量，代表中间空隙 $n+1$ 个孩子。所以关键字个数为 $\lceil M/2\rceil -1 \sim M-1$。

$(n,A_0,K_1,R_1,A_1,K_2,R_2,A_2,\cdots,K_n,R_n,A_n)$

4. 叶子节点都在同一层底层上，而且不携带任何信息，可以视为空节点，表示查找失败。



B 树的查找

B 树每层只查找一个结点，如果 B 树作为原始数据文件的索引文件驻留在外存储器上，走向下一层时，只需根据指向的地址将 B 树中的一个结点读入内存，即对应着一次磁盘的访问，因此 B 树中一个结点的大小通常也取 一次磁盘读取的数据量（称一个数据块）。

外存储器访问速度比内存访问速度要慢得多，降低 B 树的层次就能减少读取外存储器的次数。B 树因为是多路搜索树，孩子的数量大于 2，所以它比二叉查找树 高度要少。

B 树的插入

首先找到最后一层空结点位置（和二叉查找树类似，插入总在最底层），在其父结点处插入一个关键字，如果父结点中关键字个数在插入前已达上限（$M-1$），就需逐级向上进行结点 分裂，直到某层结点中关键字个数少于上限。树的高度，就是在所有结点逐个插入的过程中分裂结点并向上建立新结点形成的。

分裂的过程

• 待分裂节点的关键字排序
• 取中间位置，把 $M$ 个关键字分为左、中、右三部分。
  • 左部分 所含 $\lceil M/2 \rceil -1$ 个关键字放在旧节点中。
  • 中间位置 1个关键字连同新结点存储位置插入到父节点中（父节点关键字个数+1）
  • 右部分 所含 $M-\lceil M/2\rceil$ 关键字放在新创建节点中。
• 如果父节点关键字数 $=M$（子树数目=$M+1$）再向上分裂。
• 直到关键字数目满足要求，或者到根节点，如果该过程一直到根节点，则树高 +1.

B 树的删除

• 删除元素在最底层结点，则直接删除。
• 删除非底层结点，先找替身，为右子树最左面的关键字或左子树最右面的关键字，然后删除最底层结点关键字
• 删除最底层的关键字，有以下几种情况：
  • 若删除关键字之后，结点的关键字的个数满足B树的结点的定义，删除结束
  • 若删除后，关键字个数小于下限 $\lceil M/2\rceil -1$，即 $\lceil M/2\rceil -2$：
    • 若该结点的左或右兄弟结点关键字数 $>\lceil M/2\rceil -1$，向结点的左或者右兄弟节点借一个关键字过来。
    • 若该结点的左或右兄弟结点的关键字的个数正好为下限 $\lceil M/2 \rceil-1$，则合并兄弟结点。




B+ 树

B 树是一棵 多线索查找树，所有的数据关键字都挂在了树的非叶子结点中，每个关键字右侧字段（空心箭头）标明了其对应数据记录在原始数据文件中的具体地址，因此根据关键字和作为索引的B树的帮助，就能非常方便地在数据文件中找到它。

B树的缺点也是明显的，因每个关键字都在B树上，造成B树过于庞大；另外如果要按关键字大小顺序访问所有数据，B树没有任何优势。为了解决这个问题，引入了B+树的概念。

B树可以提供随机查找，可用于索引文件，如果要按序访问文件的所有记录，则时间复杂度高：文件不是按照顺序存储，按序访问需要遍历 B 树。

B+树是既能提供随机查找，也能提供顺序访问的存储结构。叶子结点指向数据，其他层皆为索引

$M$ 阶 B+ 树的定义如下：

1. 根或者是叶子，或者是有 $2$ 到 $M$ 个孩子。
2. 除了根之外的所有非叶结点的孩子数为 $\lceil M/2\rceil$ 到 $M$ 之间。或者相当于在 $\lfloor (M+1)/2\rfloor$ 到 $M$ 之间。
3. 非叶子节点结构如下：$(n,A_0,K_1,A_1,K_2,A_2,\cdots,K_n,A_n)$ 其中 $n$ 为关键字个数，$A_i$ 为关键字小于等于 $K_i$ 的孩子节点地址。有 $k$ 个孩子的结点存 $k-1$ 个键引导查找，键 $i$ 表示子树 $i+1$ 中键的最小值。
4. 叶子节点和中间节点不同，它存储了数据关键字和它在原始数据文件中的地址信息，而不存放孩子节点，所有叶子包含了全部关键字信息，它的关键字最少 $\lceil M/2\rceil$ 个，最多 $M$ 个。所有叶子结点形成一个单链表，方便顺序读取。


B+ 树的插入

• 叶结点不满：把新结点插入叶子，重新调整该叶子中数据的顺序

• 叶子已经装满 ：通过分裂该叶子，形成两个半满的叶子来插入一个新的项 。

  • 更新父结点
  • 如果父亲的儿子数量已经满了，我们就继续分裂父亲。最坏情况要分裂根。

B+ 树的删除

• 删除操作首先查找到要删除的项，然后删除它
• 如果此时它所在的叶子的元素数量正好满足要求的最小值，删除该项就会使它低于最小值
  • 如果邻居不是最少的情况，就借一个过来；
  • 如果邻居也处于最少的情况，就把两个结点合并成一个满的结点。合并后父结点元素少1，继续看父亲结点情况，一直向上。

时间复杂度比较 B 树查找可以停在非叶子节点的任何节点中，因此消耗小于树的高度，而 B+ 树一定消耗树的高度。



$2,\lceil M/2 \rceil$.


D. 除了根节点之外的所有非叶结点都有 $\lceil M/2 \rceil \sim M$ 个子节点。

C. 叶节点的深度一定相同。分裂操作可以保证叶节点处于同一层，只有根节点分裂的时候树才会长高。

A. 如果只有根节点一个节点。

外排序

• 最简单的方法是按照内存的容量尽可能多地读入数据记录，然后在内存进行排序，排序的结果写入文件，形成一个已排序片段。
• 每次读入的记录数越少，形成的初始的已排序片段越多。而已排序片段越多，归并的次数也越多。
• 每次归并都必须访问文件的所有记录。

置换排序

外排序由两个阶段组成

• 预处理阶段 生成尽可能长的有序数组
• 归并阶段 将这些有序片段逐步归并成一个有序文件
• 每次读入的记录数越少，形成的初始的已排序片段越多
• 已排序片段越多，归并的次数也越多，外存访问次数多，因此有序片段的长度需要尽可能长。

如果输入文件中的下一个元素比刚刚输出的元素大，它能被放入这个已排序片段 是置换排序的核心。

置换选择过程：

• 初始时，将M个元素读入内存，用一个 buildHeap 有效地放入一个优先级队列。
• 执行一次 deQueue，把最小的元素写入输出文件。
• 从输入磁带读入下一个元素。
  • 如果它比刚才写出去的元素大，则把它加入到优先级队列；
  • 否则，它不可能进入当前的已排序片段。因为优先级队列比以前少了一个元素，该元素就被放于优先级队列的空余位置，
• 继续这个过程，直到优先级队列的大小为0，此时该已排序片段结束。通过一个 buildHeap 操作重新构建一个优先级队列，开始了一个新的已排序片段，此时用了所有存放在空余位置中的元素。


18 27 35


归并

两路归并

• 归并时，每次将两个有序文件归并成一个有序文件
• 如果生成的有序片段数是M，则归并次数为$⌈\log_2M⌉$

磁带上的两路归并：

• 需要四条磁带A1,A2,B1和B2，两个用于输入，两个用于输出。开始时数据在A1上

• 内存一次能排序M个记录

• 工作过程：

  • 从输入磁带上一次读入M个记录，对它们进行内排序，然后把已排序片段轮流写到B1和B2。回绕所有的磁带 。
  • 取每条磁带上的第一个已排序片段，把它们归并起来，并把结果写到A1。然后，从每条磁带上取下一个已排序片段，把它们归并起来，结果写到A2。继续这个过程，轮流把结果写到A1和A2，
  • 回绕四条磁带，重复同样的步骤，这次使用A磁带作为输入，而B磁带作为输出。
  • 重复步骤二和三，直到剩下一个长度为N的已排序片断
  • 例：
  

  经过二轮归并后完成了外排序。

  如果在预处理阶段不用置换选择，将会生成 $7$ （即20/3）个已排序片段。在归并阶段，将需要三轮归并。

多路归并

• 同时将 $k$ 个有序文件归并成一个
• 优点：减少归并次数，需要$⌈\log_kM⌉$ 次归并
• 缺点：归并时找最小元素的操作复杂，通常可以将每个文件的第一个记录组成一个优先级队列。

磁带上的多路归并 ：

• $k$ 路归并需要 $2k$ 条磁带。$A_1$ 到 $A_k$ 和 $B_1$ 到 $B_k$。归并数据在 $A$ 上。

多路归并示意。

多阶段归并

• 磁带上的K路归并策略需要用2K条磁带，这可能限制了它在某些应用中的使用。
• 可以仅用$K+1$根磁带实现$K$路归并，这称为多阶段归并

如何分布初始片断：

• 如果已排序片段的数目是一个斐波纳契数$F_N$，那么分布最好的方法把它们分解成两个斐波纳契数$F_{N-1}$和$F_{N-2}$。
• 否则，为了将已排序片段数增加到一个斐波纳契数，必须在磁带上填充虚拟的已排序片段。
• 如果 $K=3$ 那就是递推数列 $F_{n}=F_{n-1}+F_{n-2}+F_{n-3}$ 罢！


B. 多阶段归并是为了尽量减少磁带的个数，可以将 $2K$ 条磁带减少到 $K+1$ 条磁带。

图

定义、术语、邻接矩阵和邻接表存储、基本操作、图的遍历、图遍历的应用（无向图和有向图的连通性、拓扑排序、欧拉回路、关键路径


C


D


C



深度优先搜索森林



广度优先搜索森林


欧拉回路

非加权图的最短路


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

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge> :: unweightedShortDistance(TypeOfVer start, TypeOfEdge noEdge) const
{
	LinkQueue<int> q;
	TypeOfEdge *distance = new TypeOfEdge[Vers];
	int *prev = new int[Vers];
	int u, sNo;
	edgeNode *p;

	for (int i = 0; i < Vers; ++i)
		distance[i] = noEdge; // 初始化
	// 寻找起始结点的编号
	for (sNo = 0; sNo < Vers; ++sNo)
		if ( verList[sNo].ver==start )
			break;
	if (sNo == Vers)
	{
		cout << ''起始结点不存在'' << endl;
		return;
	}
	// 寻找最短路径
	distance[sNo] = 0;
	prev[sNo] = sNo;
	q.enQueue(sNo);
	while (!q.isEmpty())
	{
		u = q.deQueue();
		for (p = verList[u].head; p != NULL; p = p->next)
			if (distance[p->end] == noEdge)
			{
                distance[p->end]=distance[u]+1;
				prev[p->end]=u;
				q.enQueue(p->end);
			}
	}
}

AOE


拓扑排序


算法的原理：拓扑排序，必须是有向无环图，利用队列进行广度优先搜索，每次入队入度为 0 的节点。

时间复杂度：$O(|V|+|E|)$。

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

struct edgeNode { //存储边的结点类 
    int end; //终点 
    edgeNode *next; 
    edgeNode(int e, edgeNode *n = NULL) { end = e; next = n;} 
}; 

struct verNode { //存储顶点的结点类 
    TypeOfVer ver; //顶点值 
    edgeNode *head; //对应的单链表的头指针 
    verNode( edgeNode *h = NULL) { head = h;} 
}; 
//请补充代码，完成图的拓扑排序。 
template <class TypeOfVer, class TypeOfEdge> 
void adjListGraph<TypeOfVer, TypeOfEdge>::topSort( ) const 
{
    linkQueue<int> q; 
    edgeNode *p; 
    int current, *inDegree = new int[Vers];
    for (int i = 0; i < Vers; ++i) inDegree[i] = 0; 

    for ( i = 0; i < Vers; ++i) 
        for (p = verList[i].head; p != NULL; p = p->next) 
        	++inDegree[p->end]; 

    for (i = 0; i < Vers; ++i) if (inDegree[i] == 0) q.enQueue(i);

    cout << "拓扑排序为：" << endl; 
    while( !q.isEmpty( ) ){ 
        current = q.deQueue( ); 
        cout << verList[current].ver << '\t'; 
        for (p = verList[current].head; p != NULL; p = p->next) 
            if(--inDegree[p->end]=0) q.enQueue( p->end ); 
    } 
    cout << endl; 
} 




1
2
3
4
5
6

0
j,i
0
inDegree[i]==0
edge[vex][i]&&inDegree[i]
inDegree[i]==0

强连通分量

有向图的极大强连通子图，称为强连通分量。


$4,5,[0,1,3],2$ 四个强连通分量。

最小生成树