算法设计与分析基础 chap1 introduction

算法是问题的程序化解决方法。

伪代码的基本结构

1. 表达式
2. 标准的数学符号及逻辑运算符号
   1. 左箭头←属值运算符
   2. 在逻辑表达式中，= 或 == 代表相等关系运算

3. 判断结构

   if (condition is true)  
      true-actions
   else
      false-actions 
   

4. 循环运算结构

   1. while-loops

      while (condition is true)
          do
      Actions

   2. repeat-loops

      repeat/do
          Actions
      until (condition is true)

   3. for-loops

      for (v from initial value to end value, increase-step)
          do 
      actions

5. 数组下标

   1. A[i] 表示数组A的第i个元素
   2. A[0..n] 表示元素为A[0]到A[n]的数组
6. 方法应用
   object.method(args)
7. 返回值
   return value

重要问题类型

• 排序
• 查找
• 字符串处理
• 图问题
• 组合问题
• 几何问题
• 数值问题

基本数据结构（C++ STL介绍）

C++ STL
主要的13个头文件：

• 容器： <vector>、<list>、<stack>、<queue>、<deque>、<set>、<map>
• 算法：<algorithm>、<functional>、<numeric>
• 迭代器： <iterator>;
• 其他：<memory>、<utility>

基本数据结构：

• 一维数组
  n个相同数据类型的元素构成的序列，它们连续存储在计算机的存储器中，我们只要指定数组的下标就能够访问这些元素。
  C++ STL 类：std::array
  C++ STL 类：std::vector (大小可动态变化的数组)
  std::vector 示例

#include <iostream>
#include <vector>
int main ()  {   
   vector<string> SS;
   SS.push_back("The number is 10");
   SS.push_back("The number is 20");
   SS.push_back("The number is 30");
   SS.push_back("The number is 40");

   SS.pop_back();    //删除最后一个元素      
   SS.erase ( SS.begin()+1,  SS.begin()+2);    //删除第二个元素 

   for (vector<string>::iterator  it=SS.begin();  it!=SS.end();  ++it)
        std::cout  << *it << '\n'; 
   return 0;
}

• 链表
  链表（linked list）是0个或者多个称为节点的元素构成的序列，每个节包含两类信息：一些数据，以及一个或多个称为指针的链接，指向链表中其他元素。
  C++ STL 类：std::forward_list
  另一种扩展结构被称为双链表(double-linked list )，其中除了第一个和最末一个节点，每一个节点都既包含指向前趋的指针又包含指向后继的指针。
  C++ STL 类：std::list

• 队列
  队列（queue）也是一种列表，只是删除元素在列表的队头进行；插入元素在表的队尾进行。因此队列是按照一种『先进先出』（FIFO）方式运行的。
  C++ STL 类：std::queue
  双向队列（Double-ended queue）是双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素。
  C++ STL 类：std::deque

• 栈
  栈 (Stack) 是一种插入和删除操作都只能在尾端进行的列表，这一端被称为栈顶。该结构按照一种『后进先出』（LIFO）的方式运转。
  C++ STL 类：std::stack
  栈使用的容器是双向队列

template<
    class T, class Container = std::deque<T>
> class stack;

示例：

#include <stack>
#include <vector>
#include <list>
#include <cstdio>
using namespace std;
int main() {
	//可以使用list或vector作为栈的容器，默认是使用deque的。
	stack<int, list<int>>      a;
	stack<int, vector<int>>   b;
	
	for (int i = 0; i < 10; i++)  {
		a.push(i);
		b.push(i);
	}

	printf("%d %d\n", a.size(), b.size());  //栈的大小

	//取栈项数据并将数据弹出栈
	while ( !a.empty() ) {
		printf("%d ", a.top());
		a.pop();
	}
	putchar('\n');
	return 0;
}

• 优先队列（priority queue）
  优先队列（priority queue）是一个数据项的集合，这些数据项都来自于一些全序域。对优先队列的主要操作是找到最大元素、删除最大元素和插入一个新元素。其主要优点是能高效的得到最大元素（总在队头）。
  C++ STL 类：std::priority_queue (用堆来实现)

template<
  class T,
  class Container = std::vector<T>,
  class Compare = std::less<typename Container::value_type> 
>class priority_queue;

示例:

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
    
int main() {
    std::priority_queue<int> q;
    for(int n : {1,8,5,6,3,4,0,9,3,2})
        q.push(n);
     
    print_queue(q);
     
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
    for(int n : {1,8,5,6,3,4,0,9,3,2})
        q2.push(n);
     
    print_queue(q2);
}

• 图
  按照简单定义，一个图G=<V,E>由两个集合来定义：
  一个有限集合V，它的元素被称为顶点；
  另一个的限集合E，它的元素是由一对顶点，被称为边。图分为无向图和有向图。
  任意两个顶点之间都有边相连的图称为完全图。如果完全图具有 |V| 个顶点，它的标准符号是 K|V|。
  如果图中所缺的边数量相对较少，我们称它为稠密图；如果图中所缺的边数量相对较多，我们称为稀疏图。我们处理的是稀疏图还是稠密图，可能会影响图的表示方式，从而影响我们所设计或使用的算法的运行时间。
  图主要有两种表示方式：

  1. 邻接矩阵
     n 个顶点的邻接矩阵是一个n*n的布尔矩阵，图中每个顶点都用一行和一列来表示，如果从第i个顶点到第j个顶点之间有连接边，则矩阵中第i行第j列的元素等于1，如果没有这样的边，则等于0。
  2. 邻接链表
     图的邻接链表是链表的一个集合，其中每一个顶点用一个链表表示，该链表包含了和这个顶点邻接的所有顶点（即所有和该顶点有边相连的顶点）。通常，这样一个表由一个表头开始，表头指出该链表表示的是哪一个顶点。
     一图解惑：
     

  图有两个特性对于大量的应用是非常重要的：连通性和无环性。两者都基于路径的概念。

  从顶点u到顶点v的路径可以这样定义：它是图G中始于u止于v的邻接（以一条边连接）顶点序列。
  如果一条路径上所有顶点都是互不相同的，我们说这条路径是简单路径。
  有向路径是一个顶点的序列，序列中的每一对连续顶点都被一条边连接起来，边的方向等于从第一个顶点指向下一个顶点的方向。

  • 连通性
    如果对于图中的每一对顶点u和v，都有一条从u到v的路径，我们说该图是连通的。
    如果图是非连通的，这样一个模型会包含多个自我连通的部分，称为该图的连通分图。
  • 无环性
    回路（环）是起点和终点都是同一顶点的简单路径。不包含回路的图称为无环图。

• 树
  树(tree)就是连通且无回路的图。
  无回路但不一定连通的图称为森林：它的每一个连通分图都是一棵树。
  树具有其他图没有的一些重要特性：树的边数总是比它的顶点少一：|E|=|V|-1
  

• 有根树
  树的另一个非常重要的特性就是：树的任意两个顶点之间总是恰好存在一条从一个顶点到另一个顶点的简单路径。
  这个性质使得以下做法成为可能：任选自由树中的一个顶点，将它作为树的根。有根的树称为有根树。

• 有序树
  有序树是一棵有根树，且树中每一顶点的所有子女都是有序的。
  方便起见，我们可假设在这种树的示意图中，所有的子女都是从左到右有序排列的。

• 二叉树
  也可以把二叉树定义为一棵有序树，其中所有顶点的子女个数都不超过两个，并且每个子女不是父母左子女就是父母的右子女。
  一棵子树的根如果是某顶点的左（右）子女，该子树称为该顶点的左（右）子树。
  对于高度为h，具有n个顶点的二叉树，我们有以下不等式：
  $$\lfloor log_2n\rfloor\le h \le n-1$$

  • 二叉查找树
    分配给每个父结点的数字都比它左子树中的数字大，比右子树中的数字小。这种树被称为二叉查找树。
    
• 集合
  集合（Set）概念在数学中扮演了一个中心角色。我们可以这样描述集合；它是互不相同的集合元素的无序组合。
  多重集 （Multiset）和集合类似，只是容许有相同的元素存在。
  C++ STL 类：std::unordered_set (用哈希表实现)
  C++ STL 类：std::unordered_multiset (用哈希表实现)
  有序集合（Sorted Set）
  C++ STL 类：std::set (用红黑树实现平衡二叉查找树)
  C++ STL 类：std::multiset (用红黑树实现)
• 字典
  字典是一种包含元素都为（key, value）对的集合，又称为Map。和集合有很类似的性质。
  C++ STL 类：std::unordered_map (用哈希表实现)
  C++ STL 类：std::map (用红黑树实现)
  C++ STL 类：std::multimap (用红黑树实现)
  在计算中，我们对集合或者字典做的最多的操作是
  • 查找一个给定元素 find
  • 增加新元素 insert
  • 删除一个元素 erase

STL中的集合和字典类都包含上述的三种方法
例子：

#include <string>
#include <iostream>
#include <map>
#include <utility>
using namespace std;

int main()  {
   map<int, string> Employees;
   Employees[5234] = "Mike C.";
   Employees[3374] = "Charlie M.";
   Employees[1923] = "David D.";
   Employees[7582] = "John A.";
   Employees[5328] = "Peter Q.";

   cout << "Employees[3374]=" << Employees[3374] << endl;

   cout << "Map size: " << Employees.size() << endl;

   for( map<int,string>::iterator ii=Employees.begin(); ii!=Employees.end(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }
}

课后习题