数据结构知识点

第 2 章 算法分析

$log^{k}N=O(N)$

第 3 章 基础 ADT

3.5 List

• Array-based lists
• Pointer-based lists(Linked lists)

Array Implementation

Insert

// insert element at the current position
void insert(const E& it) {
  Assert(listSize>=maxSize, “Exceed capacity”);
  //shift Elements up 
  for(int i=listSize; i>curr; i--)
      listArray[i] = listArray[i-1]; 
  listArray[curr] = it; // insert the element
  listSize++;  // increment list size
}

remove

// Remove and return the current element
E remove() {
  Assert((curr>=0)&&(curr<listSize), "no element");
  E it = listArray[curr]; // Copy the element
  for(int i=curr; i<listSize-1; i++)
    // Shift them down
       listArray[i] = listArray[i+1];
   listSize--;    // Decrement size
   return it;
 }

Pointer Implementation

// An implementation of a simple 
// singly-linked list node

template <typename E> 
class Link {
    public:
    E element;  //value for this node
    Link *next;   //Pointer to next node in list
    //Constructors
    Link(const E& elemval, Link* nextval =NULL)
    {	element = elemval;  next = nextval; }
    Link(Link* nextval =NULL)
    { next = nextval; }
};

//Class LList 
//inherit the abstract class List
	template <typename E> 
class LList: public List<E>{
	private:
  		Link<E>* head; //Pointer to list header
  		Link<E>* tail; //Pointer to last element
		Link<E>* curr; //access to current element
	 	int cnt;      //Size of list
		void init() //used by constructor 
    	{  curr = tail = head = new Link<E>; cnt =0;}		
		void removeall() //used by deconstructor
		{   while(head != NULL) { 
                 curr=head; head=head->next; delete curr;
              }
         }
}

insert

//Insert a node to current position
	public:
	  void insert(const E& it) {
		curr->next = new Link<E>(it, curr->next);  	
  		if (tail == curr) tail = curr->next; //new tail
		cnt++;
	  }
    //Append a node at the tail of the list
	  void append(const E& it) {
  		tail = tail->next = new Link<E>(it, NULL);
  		cnt++;
  	  }

remove

// Remove and return current element 删除curr指针后的节点
	E remove() {
		E it = curr->next->element;
		Link<E> *ltemp = curr->next;
		if (tail == curr->next) 
			tail =curr; // Reset tail
		curr->next = curr->next->next; //remove element
		delete ltemp;  //reclaim space
		cnt--;	   //decrement the list size
		return it;
	}
//Next – move curr one pos toward the tail
	void next() { // no change if already at end
 		if (curr != tail) { curr = curr->next;}
	}
//Prev – move curr one pos toward the head 
	void prev() {
     if (curr == head) return; // No previous element
     Link<E>* temp = head;
	  //march down list until the previous element
	  while (temp->next!=curr) temp=temp->next;
  	  curr = temp;
}

删除列表中除表头节点以外的所有其他节点

template <class Type> void List<Type> :: MakeEmpty ( ) {
  ListNode<Type> *q;
  while (first->link!=NULL){
 q=first->link;
   first->link=q->link;
​     //将表头结点后第一个结点从链中摘下
​     delete q;    //释放它 
  }

在 p->prev 和 p 之间插入一个新节点

//{val ,head ,tail}
p->prev=p->prev->next = new Node{x,p->prev,p}；

删除 p 指向的节点

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

在 itr 前插入 x

iterator insert( iterator itr, Object && x){
    Node *p = itr.current;
    theSize++;
    return { p->prev = p->prev->next = new Node{std::move(x),p->prev,p};
}

删除在 itr 处的项

iterator erase( iterator itr){
    Node *p = itr.current
    iterator retVal{p->next};
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    theSize--;
    return retVal;
}

Comparison of List Implementations

假设

• n为链表中现有的元素数量
• p为指针所占用的大小
• e为数据元素所占用的大小
• d为数组最多能存储的元素个数

数组实现的链表所需要占用的空间是de，指针链表所需要的空间是n（p+e）

当n>de/(p+e)的时候，使用数组实现的链表更加节省空间

3.6 Stack

计算后缀表达式

使用一个栈，见到一个数时就把它推入栈中；在遇到一个运算符时该运算符就做用于从该栈弹出的两个数上，再将所得结果推入栈中
e.g. 6 5 2 3 + 8 * + 3 + * 每一次运算栈中的数字
6 5 2 3
6 5 5 8
6 45 3
6 48
288
时间复杂度为 O(N)

中缀到后缀的转换

当读到一个操作数的时候立即将其放到输出中。读到一个运算符的时候将运算符放到栈中，当遇到左圆括号时也要将其推入栈中。如果见到一个右括号就将栈元素弹出，直到遇到一个左括号为止，但是左括号只被弹出而不输出。
如果见到任何其他的符号，那么从栈中弹出栈元素并且写入输出直到发现优先级更低的元素为止（包括优先级相同的也要弹出并且输出），并且除非是处理“）”时，否则我们不从栈中移出“（”。当从栈中弹出元素的工作完成后，再将运算符压入栈中。
“（”在入栈的时候被认为有最高的优先级，在栈中时被认为具有最低的优先级，也就是说看到“（”就直接只入栈而不弹出其他运算符，并且除非看到“）”其不会被其他运算符出栈

数组实现

相当于是在数组实现的链表上加了一个限定的大小并进行了简化：只能在尾部进行操作

void clear() { top=0; } 	//Reinitialize

void push(const E& it) { 	// put “it” on stack
  Assert(top != maxSize, “Stack is full”);
  listArray[top++] = it; }

E pop() {//pop top element
  Assert(top != 0, “Stack is empty”);
  return listArray[--top]; }

const E& topValue() const { 	//return top element
  Assert(top != 0, “Stack is empty”);
  return listArray[top-1]; }

链表实现

//A linked stack 
template <typename E> class LStack: public Stack<E> {
private:
	Link<E>* top;	//pointer to first element
	int size; 		//number of elements
public:
     LStack(int sz = defaultSize){ 	//Constructor            
           top = NULL; size = 0;
    }
    ~LStack()  { clear(); }		//Destructor
 void clear() {			//reinitialize
	  while (top != NULL) { 	//delete link nodes
	      Link<E>* temp = top; top = top->next; delete temp;
	  }
	  size = 0;
 }
 void push(const E& it) { 	//put “it” on the stack
	   top = new Link<E>(it, top); size++;
 }
 E pop() { 				//remove “it” from stack
	  Assert(top != NULL, “Stack is empty”);
	  E it = top->element;
	  Link<E>* ltemp = top->next;
	  delete top;  top = ltemp;  size--; return it;
 }
 const E& topValue() const { 	//return top value
	  Assert(top != 0, “Stack is empty”);
	  return top->element;
 }

top指针指向第一个链表的节点

• push：手续爱你修改新创建的节点的next域，使其指向现在的栈的top指针指向的节点，然后移动top指针指向这个新的节点
• pop：将top指针指向现在所指向的节点的next，然后释放原来节点的空间并且返回其值

3.7 Queue

运用循环数组实现队列

这里可以去看王道的书

front指向队头，而rear指向下一个可以插入元素的位置，所以初始时front=rear

PPT上的实现和王道书上的不同

rear指向队尾元素，所以初始的时候rear+1==front

但图片大致是对应的，只有一个单元的差距

• front = rear 队列中只有一个元素

• front = rear + 1 怎么判断队列是空的还是满的
  Solution：
  1.显式的记录有多少个在队列中的元素
  2.让数组的大小为 n+1 但是只允许最多存储 n 个元素

• 当 front = rear+1 时，队列为空

• 当 front = rear+2 时，队列为满
  队列的长度为（（rear+maxSize）-front+1）%maxSize

  //Array-based Implementation (solution 2)
  template <typename E> class AQueue: public Queue<E> {
  private:
  int maxSize; // Maximum size of queue
  int front; // Index of front element
  int rear; // Index of rear element
  E *listArray; //Array holding queue elements
  public:
  AQueue(int size =defaultSize) { 
  // Constructor- Make list array one position
  // larger for empty slot
  	maxSize = size+1;
  	rear = 0; front = 1;
  	listArray = new E[maxSize];
  }
  ˜ AQueue() { delete [] listArray; }
  //reinitializeS
  void clear() {rear = 0;  front = 1;} 
  void enqueue(const E& it) {//put “it” in queue
    Assert(((rear+2) % maxSize) != front, 
  “Queue is full”);
    rear = (rear+1)%maxSize;
    listArray[rear] = it;
  }
  E dequeue() {//take element out
    Assert(length() != 0, “Queue is empty”);
    E it = listArray[front];
    front =(front+1)%maxSize; 
    return it;
  }
      //get front value
  const E& frontValue() const { 
    Assert(length()!=0, “Queue is empty”);
    return listArray[front];
  }
  
  //return length
  virtual int length() const  {
    return ((rear+maxSize)-front+1)%maxSize;
  }

第 4 章 Tree

一棵树中从根到每个节点恰好存在一条路径

构造一棵表达式树

将后缀表达式转换为表达式树
如果符号是操作数，就建立一个单节点树并且将指向它当指针推入栈
如果符号是操作符，那么从栈中弹出指向两棵树$T_{1},T_{2}$的两棵树的指针，先弹出的为 $T_{1}$并且形成一棵新的树，该树的根为操作数，其左右儿子分别为$T_{2}和 T_{1}$，然后将指向这棵新树的指针压入栈中

4.3 二叉查找树

4.3.4 remove

• 无儿子：直接删除
• 一个儿子：让其父节点直接指向其儿子
• 两个儿子的情况：
  用其右子树中的最小的数据代替该节点的数据并且，并且递归地删除该节点。
  由于右子树中最小的节点不可能有左儿子，所以第二次的 remove 会容易很多
  
  lazy remove：不实际删除节点而是只作了被删除的标记
  

4.4 AVL 树

每个节点的左右子树高度最多相差 1（空树的高度为-1）

4.4.1 单旋转

左侧双旋转为先左旋转再右旋转
右侧双旋转为先右旋转再左旋转

右旋转操作（WithLeftChild)

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/
void rotateWithLeftChild( AvlNode * & k2 ){
    AvlNode *k1 = k2->left; 
    k2->left = k1->right; //将 k1 的右子树移交给 k2
    k1->right = k2; /*由于最后需要把 k1 连接到父节点，所以父子关系需要改变，所以将 k1 的右子树连接到 k2 */
    k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
    k1->height = max( height( k1->left ), k2->height ) + 1;
    //k2->height 其实就是 k1 右子树的高
    k2 = k1;
    //让父节点指向 k1，因为在参数列表传递的是指针的引用，所以会对上一个节点传下来的指针进行改动
}

所有插入或者删除操作结束后都要记得加上 balance（t）
balance

void balance( AvlNode * & t ){
    if( t == nullptr )  return;
    if( height(t->left) - height(t->right) > IMBALANCE )
       if( height( t->left->left ) >= height( t->left->right ) )
           rotateWithLeftChild( t );
       else
          doubleWithLeftChild( t );
   else
   if( height( t->right ) - height( t->left ) > IMBALANCE )
       if( height( t->right->right ) >= height( t->right->left ) )
           rotateWithRightChild( t );
       else
          doubleWithRightChild( t );
  t->height = max( height( t->left ), height( t->right ) ) + 1;
}

4.5 splay

4.5.2 展开

• 如果是 zig-zag 情况就对应执行一次相应的双旋转
• 如果是 zig-zig 情况就进行两次方向相同的单旋转操作
  Insert 先正常插入后将 x splay 到根
  Delete：

1. 将 x splay 到根后将其删除
2. 将左子树的中的最大值splay 到左子树的根
3. 将右子树连接到左子树新的根上

4.7 B-Tree

阶为 M 的 B 树具有以下的性质：

• 数据项存储在树叶上
• 非叶子节点存储知道 M-1 个关键字以指示搜索的方向；关键字 i 代表子树 i+1 中的最小的关键字
• 树的根要么是一片树叶要么儿子数介于 2-M 之间
• 除根外所有非叶子节点的儿子数在 $\lceil M/2 \rceil$和 M 之间
• 所有的树叶都在相同的深度上，并且每片树叶拥有的数据项个数在$\lceil L/2 \rceil$和 L 之间
  插入叶子节点和插入内部节点有一些地方是不相同的

1. 首先是 L 和 M 的不同，叶子节点对应 L，内部节点对应 M
2. 其次叶子节点在分裂的时候分成两部分，$j=\lfloor {L+1}/2 \rfloor$个记录在左边叶子，剩下的在右边叶子，右边叶子的第一个记录被插入父节点。而内部节点将 j-1 个 keys放在左边，第 j 个 key 插入父节点，剩下的 keys 放在右边节点
   分裂完大部分都是右节点较重
   B 树具体的操作过程必须看笔记和 PPT牢记

Delete x

进行一次查找并且从叶子节点处进行删除

• 如果叶节点 underflow，可以从邻居处领养
• 如果叶节点 underflow 且不可领养，那么将节点进行合并，然后对父节点继续进行 delete，因为这会导致父节点的儿子数减少 1
  内部存储适合小阶数，例如 3/4
  磁盘中选择最大的 M，使得内部节点可以被存储在硬盘上的一个物理上的块之中

第 5 章 散列

5.3 分离链接法 separate chaining

将散列到同一个值的所有元素保留到一个链表中
装载因子：散列表中的元素个数对于该表大小的比值
Insert

bool insert( const HashedObj & x){
    auto & whichList = theLists[ myhash(x) ];
    if( find( begin ( whichList), end(whichList),x) != end(whichList ) )
        return false;
    whichList.push_back(x);
    if( ++currentSize > theLIsts.size() )
        rehash();
    return true;
}

分离链接法的一般法则是让 $\lambda\approx1$
$\lambda$就是所有链表的平均长度，所以访问一个项目的平均时间为$O(1)+O(\lambda)$

5.4 不用链表的散列表 Open Addressing

所有的 keys 都存在于表中
当我们寻找值 x 的时候，按顺序搜索位置 $h_{0}(x),h_{1}(x),…$直到

• 找到 x
• 发现了一个空的位置（说明 x 不存在）
  Insert 和 Search 所使用的应当是同一个 probe sequence 探测序列
  对于不使用分离链接法的散列表而言其装填因子应该低于 $\lambda = 0.5$
  这样的表叫做探测散列表（probing hash table）
  $h_{i}(X)=(Hash(X)+p(X,i)) mod TableSize$
  并且定义 $p（X，0）=0$
• Linear：$p(X,i)=i$
• Quadratic: $p(X,i)=i^{2}$
• Double Hashing: $p(X,i)=i*Hash_{2}(X)$
• Pseudo-random probing

5.4.1 线性探测法

$f(i)=i$ 即 $f 为 i 的线性函数$
即搜索序列为 $Hash(K),Hash(K)+1,Hash(K)+2,… mod TableSize$
当元素开始占据相邻的位置后，会形成一些区块，这种现象称为一次聚集（Primary Clustering）
Primary clustering：散列到不同位置的元素探测一系列同样的的替代位置
改进的方式是在 i 前乘一个常数 c，c 应当是一个与 M 互质的数字

Peseudo-random probing

• $p(K,i) = Perm[i-1]
• 第 i 个探测序列中探测的 slot 为$(h(K) + Perm[i-1]) % M$
• 所有的插入和查询操作都使用同样的 random permutation

5.4.2 平方探测法 Quadratic Probing

$f(i) = i^{2}$
$p(K,i) = c_{1}i^{2} + c_{2}i +c_{3}$
如果使用平方探测并且表的大小为素数的时候，那么当表至少有一半为空时，即 $\lambda \leq 0.5 $的时候总是能够插入一个新的元素
探测散列表中不能施行删除操作，因为很有可能该单元引起过冲突，而元素绕过该单元存在了别处，如果将该单元中的元素删除那么剩下的 find 操作会先找到一个空的位置导致 find 操作失败，所以只能标记该位置已经被删除

bool contains(const HashedObj & x) const
    {return isActive( findPos( x) );}
int findPos( const HashedObj & x) const{
    int offset=1; //初始的偏移量为 1
    int currentPos = myhash ( x );
    while( array[ currentPos ].info != EMPTY &&
             array[ currentPos ].element != x)
    {
        currentPos += offset; //计算第 i 次探测
        offset += 2;
        if( currentPos >= array.size() ) currentPos -= array.size();
    }
    return currentPos;
} 

$f(i)=f(i-1)+2i-1$这个公式说明下一个尝试的单元离上一个被试过的单元有一段距离，并且这个距离在连续探测中每次递增 2
虽然平方探测排除了一次聚集，但是散列到同一位置上的那些元素将探测相同的备选单元，叫做二次聚集（secondary clustering）
二次聚集的现象在伪随机和平方探测法中仍然存在

5.4.3 双散列 double hashing

$f(i)=ihash_{2}(x)$
探测位置$h_{1}(X),h_{1}(X)+h_{2}(X),h_{1}(X)+2h_{2}(X), … mod$ $TableSize$
$p(X,i) = i*h_{2}(K)$

优缺点

• 分离链接法简单但是浪费空间
• 线性探测法更好的利用了空间，在表为稀疏的时候比较快速
• 双散列高效利用了空间，也很快，但是需要很谨慎的实现
  $h_{2}(X)$不可以是 0 也不可以是 M 的因子

5.5 再散列

建立另外一个大约两倍大的表，并且使用一个相关的新散列函数，扫描整个原始散列表，计算每个为删除的元素的新散列值并将其插入到新表中
不可以只是从旧表中 copy 数据，因为表有一个新的散列函数
运行时间为 $O(N)$
可以表满到一半就再散列，也可以只有发生插入失败时才再散列
middle-of-the-road strategy：当散列表到达某一特定的装填因子时进行再散列（是目前最好的策略）
最好设计一个散列表系统永远不会超过半满
减少面对冲突时产生的开销：

• 如果两个记录被散列到同一个初始位置，被访问的频率更高的记录应该被放在初始位置
• 探测序列所访问的记录按照被访问频率进行排序

第 6 章 优先队列/堆

6.3 二叉堆

堆有两个性质，结构性和堆序性

6.3.1 结构性质

堆是一颗完全二叉树，除底层外都被填满，底层上的元素从左到右填入
因为完全二叉树的规律性，所以可以用一个数组表示
对于数组中任一位置$i$上的元素，其儿子在 $2i,2i+1$位置，其父亲在$\lfloor i/2 \rfloor$

6.3.2 堆序性质

任意节点都小于（或等于）其所有后裔
对于每一个节点 X，X 的父亲中的关键字小于或等于 X 中的关键字

6.3.3 基本的堆操作

Insert：precolate up
在下一个可用位置创建一个空穴，如果 X 可以放入空穴而不破坏堆序性质那么就直接放入，否则将空穴的父节点上的元素移入该空穴中，直到 X 能够被放入空穴中为止
percolate up

void insert ( const Comparable & x )
{
    if( currentSize == array.size() - 1 )
        array.resize( array.size() * 2);
        // 上滤
    int hole = ++currentSize;
    Comparable copy = x;
    
    array[ 0 ] = std::move( copy );
    //数组从位置 1 开始，所以放在 0 处防止越界
    for( ; x < array[ hole / 2]; hole /= 2)
        array[ hole ] = std::move( array [ hole / 2 ] );
    array[ hole ] = std::move( array[ 0 ] );
}

deleteMin

void deleteMIn( comparable & minItem )
{
    if ( isEmpty() ) throw UnderflowException{ };
    minItem = std::move( array[ 1 ] );
    array[ 1 ] = std::move( array[ currentSize-- ] );
    percolateDown( 1 );

void percolateDown( int hole )
{
    int child;
    Comparable tmp = std::move( array[ hole ] );
    for( ; hole * 2 <= currentSize; hole = child ){
        child = hole * 2;//左儿子
        if( child != currentSIze && array[ child + 1 ] <array [ child ] )
            ++child;//右儿子
        if( array[ child ] < tmp ) array[ hole ] = std::move( array[ child ] );//向下
        else
            break;
    }
    array[ hole ] = std::move( tmp );
}

6.3.4 其他的堆操作

buildHeap

void buildHeap(){
    for( int i = currentSize / 2; i > 0; --i）//从最右边的叶子节点的父亲开始向前的所有节点都执行下滤操作
        percolateDown(i);
}

$时间复杂度为 O（N）$

第 7 章 排序

稳定性

• 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法。
• 冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法。

选择排序

/*
*  Selection Sort
*  In the ith pass, the ith smallest key in the array is selected * and placed into position i
*/
template <typename E, typename Comp>
void selsort(E A[], int n) {
  for (int i=0; i<n-1; i++) { //select ith record
    int lowindex = i; //Remember its index
    for (int j=n-1; j>i; j--) //Find least value
    //找到从第 i+1 个数字到尾部数字中的最小值
    // 每次都将第 i 个最小的元素放在其应当放在的位置
    // 假如有两个相同大的数放在不同位置很显然其相对次序会被打乱，所以选择排序并不是稳定的
      if (Comp::lt(A[j], A[lowindex]))
        lowindex = j; // Put it in place
    swap(A, i, lowindex);
  }
}

比较操作的次数最好，最坏，平均都是$ \Omega(N^{2})$
交换操作的最少次数

• 最好情况为 0 次
• 最坏情况是 n-1 次
• 平均情况是$\Omega(N)$

7.2 插入排序

插入排序利用了已知位置 0 到位置 p-1 升的元素已经处于拍过序的状态的事实
插入排序

template <typename Comparable >
void insertionSort( vector<Comparable> & a )
{
    for( int p=1 ; p<a.size(); ++p ){
        Comparable tmp = std::move( a[p] );
        int j;
        for(j=p; j>0 && tmp < a[j-1]; --j ) a[j]=std::move( a[ j-1 ]);
        a[ j ] = std::move( tmp );
    }
}

/*
* Insertion sort
* Each record is inserted in turn at the correct position
* within a sorted list composed of those records already
* processed
*/
template <typename E, typename Comp>
void insertionSort(E A[], int n) {
  for (int i=1; i<n; i++) //insert i’th record
    for (int j=i; (j>0) && (Comp::prior(A[j], A[j-1])); j--)
    // A[ j ] < A[ j-1 ]，从 i 开始进行比较
      swap(A, j, j-1);// A[j] = A[j-1]
}

插入排序的性质

插入排序是原地排序并且是稳定的
插入排序的平均运行时间是 $O(N^{2})$
但如果输入数据已经预先排序，那么运行时间为 $O(N)$
最坏运行时间为$\Omega(N^{2})$，最好运行时间是$\Omega(N)$
交换操作次数：

• 最好情形为 0 次
• 平均以及最坏情况都是$\Omega(N^{2})$

7.3 一些简单排序算法的下界

定理 7.1 N 个互异元素的数组的平均逆序数是 $N(N-1)/4$

这个定理提供了任何只交换相邻元素的排序算法的一个很强的下界

定理 7.2.通过交换相邻元素进行排序的任何算法平均都需要$\Omega(N^{2})$时间

为了让一个排序算法以压二次时间运行，必须执行一些比较，特别是要堆相距较远的元素进行交换

7.4 希尔排序 diminishing increment sort（缩减增量排序）

亚二次时间界
增量序列：$h_{1},h_{2},h_{3},…$
只要$h_{1}=1$，任何增量序列都是可行的
在使用增量 $h_{k}$的一趟排序之后，对于每一个 $i 都有 a[i]\leq a[i+h_{k}]$
所有相隔$h_{k}$的元素都被排序，称文件是**$h_{k}-sorted$**的
一个$h_{k}-sorted$的文件（此后将是$h_{k-1}-sorted$）保持其$h_{k}$排序性
$h_{k}排序的的一般策略是对于$h_{k},h_{k}+1,..,N-1 中的每一个位置 i，把其上的元素放到 i,i-h_{k},i-2h_{k},..$中的正确位置上
希尔增量：$h_{t}=\lfloor N/2 \rfloor 和 h_{k}=\lfloor h_{k+1}/2\rfloor$
使用希尔增量的希尔排序例程

template <typename Comparable>
void shellsort( vector<Comparable> & a ){
    for( int gap = a.size() / 2; gap > 0; gap /= 2 )
        for( int i=gap; i < a.size(); ++i ){
            Comparable tmp = std::move( a[ i ] );
            int j=i;
            for( ; j>=gap && tmp < a[ j-gap ]; j -= gap )
                a[ j ] = std::move( a[ j- gap ] );
           a[ j ] = std::move ( tmp );
        }
}

希尔排序的修改版
就是对于差一个 gap 的位置上的一系列元素进行插入排序

// Modified version of Insertion Sort 
template <typename E, typename Comp>
void inssort2(E A[], int n, int incr) {
  for (int i=incr; i<n; i+=incr)
    for (int j=i; (j>=incr) && (Comp::prior(A[j], A[j-incr]));        
            j-=incr)
      swap(A, j, j-incr);
}
//Shellsort
template <typename E, typename Comp>
void shellsort(E A[], int n) { 
  for (int i=n/2; i>2; i/=2) //For each increment
    for (int j=0; j<i; j++) //Sort each sublist
      inssort2<E,Comp>(&A[j], n-j, i);
  //Normal insertion sort
  inssort2<E,Comp>(A, n, 1);
}

定理 7.3 使用希尔增量时希尔排序的最坏情形运行时间为$\Omega(N^{2})$

Hibbard 增量序列：1，3，7，…，$2^{k}-1$

相邻的增量之间没有公因子

使用 Hibbard 增量的希尔排序的最坏情形运行时间是$\Omega(N^{2})$

更好的增量序列是 Sedgewick’ s incerment(best in practice)

• 1，5，19，41，109，…，（$9 * 4^{i} - 9 * 2^{i} + 1 or 4^{i} - 3 * 2^{i} + 1$）

7.5 堆排序 heapsort

运行时间是 $O(NlogN)$
每次 deleteMin 之后堆会减少一个位置，所以位于堆中最后的单元可以用来存放刚刚删去的元素
堆排序

template <typename Comparable >
void heapsort( vector<Comparable> & a )
{
    for( int i = a.size( ) / 2 - 1; i>=0 ; --i ) // buildHeap
        percDown( a, i, a.size( ) );
    for( int j = a.size( ) - 1; j>0 ; --j ) // deleteMax
    {
        std::swap ( a[ 0 ], a[ j ] );
        percDown( a, 0, j ); 
    }
}

堆排序的性质

平均运行时间是 $O(NlogN)$，最坏运行情况是$\Omega(NlogN)$
堆排序是原地排序但是并不稳定，因为在上滤的过程中有可能会导致相同元素之间的相对位置发生变化

7.6 归并排序

最坏时间情形为 $O(NlogN)$

/**
*进行递归调用的内部方法，*a为Comparable项的数组.
*tmpArray 为放置归并结果的数组.
*left 为子数组最左元素的下标。
*right 为子数组最右元素的下标.
*/
template <typename Comparable>
void mergeSort(vector<Comparable> & a,
    vector<Comparable> & tmpArray, int left,int right)
{
    if( left < right){
    int center = ( left +right )/ 2;
    mergeSort( a,tmpArray,left, center );
    mergeSort( a,tmpArray, center + 1, right ); 
    merge( a,tmpArray,left,center + 1, right );
    }
}
/**
*合并子数组已排序两半部分的内部方法.
*a为Comparable项的数组.
*tmpArray 为放置归并结果的数组，
* leftPos 为子数组最左元素的下标，
* rightPos 为后半部分起点的下标，
* rightEnd 为子数组最右元素的下标。
*/
template <typename Comparable>
void merge( vector<Comparab1e> & a, vector<Comparable> & tmpArray,
int leftPos, int rightPos, int rightEnd )
{
    int leftEnd = rightPos -1;  //左半个数组的终点
    int tmpPos = leftPos; //复制到 tmpArray 的起点，从 leftPos 开始
    int numElements = rightEnd - leftPos + 1; //数组元素的个数
    // 主循环
    
    while( leftPos <= leftEnd && rightPos <= rightEnd )
    if( a[ leftPos ]<= a[ rightPos ])
        tmpArray[ tmpPos++]= std::move( a[ leftPos++]); 
    else
        tmpArray[ tmpPos++]= std::move( a[ rightPos++]);
    while( leftPos <= leftEnd ) // 复制前半部分的剩余元素
        tmpArray[ tmpPos++ ]= std::move( a[ leftPos++]);
    while( rightPos <= rightEnd)//复制后半部分的剩余元素
        tmpArray[ tmpPos++ ]= std::move( a[ rightPos++]);
    //将tmpArray复制回原数组a
    for( int i = 0; i< numElements;++i,--rightEnd )
        a[ rightEnd ]= std::move( tmpArray[ rightEnd ]);
}
// 归并排序的另一种实现方式
// 对于小数组使用插入排序，当两个子数组变为空的时候不需要进行额外的检查
template <typename E, typename Comp>
void mergesort(E A[], E temp[], int left, int right) {
  if ((right-left) <= THRESHOLD) { //small list
    insertionsort<E,Comp>(&A[left], right-left+1);
    return;
  }
  int i, j, k, mid = (left+right)/2;
  if (left == right) return;
  mergesort<E, Comp>(A, temp, left, mid);
  mergesort<E, Comp>(A, temp, mid+1, right);
  //Do the merge operation. First copy two halves to temp
  for (i=mid; i>=left; i--) temp[i] = A[i];
  for (j=1; j<=right-mid; j++) temp[right-j+1] = A[j+mid]; // reverse order
  //Merge sublists back to A
  for (i=left, j=right, k=left; k<=right; k++)
    if (Comp::prior(temp[i], temp[j])) A[k] = temp[i++];
    else A[k] = temp[j--];
}

归并排序的分析

时间复杂度为 $O(NlogN)$
需要$O(N)$的额外空间
归并排序是稳定的

7.7 快速排序

平均运行时间 $O(NlogN)$
快速排序算法由下列简单的 4 步组成

1. 如果 S 中元素个数为 0 或 1，则返回
2. 取 S 中任一元素 v，称之为 pivot
3. 将 S - {v}（即 S 中其余元素）划分成两个不相交的集合：$S_{1}$={$x \in S - {v} | x\leq v$},$S_{2}$={$ x \in S - {v} | x\geq v$}
4. 返回{quicksort($S_{1}$),后跟 v，继而再 quicksort($S_{2}$)}

#####三数中值分割法（Median-of-Three Partitioning）
使用左端，右端，中心位置上的三个元素的中值作为枢纽元

//  返回 left，center，right 三项的中值，将他们排序并隐匿枢纽元
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a,int left,int right )
{
   if( a[ center ] ‹ a[ left ])
        std:: swap ( a[ left ], a[ center ] );
    if a[right] < al left ] )
        std:: swap ( a[ left ], a[ right] );
    if a[right] < a[ center ] )
        std:: swap ( a[ center ], a[ right ] );
    // 将枢纽元置于 right-1处
    std:: swap ( a[ center ], al right - 1] );
     return a[ right - 1 ];
}

/**
* 进行递归调用的内部快速排序方法，
* 使用三数中值分割法，以及截止范围是10的截止技术.
* a 是Comparable 项的数组.
* left 为子数组最左元素的下标。
* right 为子数组最右元素的下标.
*
template <typename Comparable>
void quicksort( vector<Comparable> & a,int left,int right)
{
    if( left + 10 <= right )
    {
        const Comparable & pivot = midian3( a, left, right )
        //开始分割
       int i = left, j = right -1;
        for( ; ; )
        {
            //因为 left，right，center 三者已经排序，所以 left 处的元素一定小于 等于pivot，right 处元素一定大于等于 pivot，而 right-1 存放的是 pivot，所以 j 从 right-1 处开始，++i，--j 直接从 1 和 right-2 开始进行比较
            while( a[ ++i ] < pivot ){}
            while( pivot < a[ --j ] ){}
            if( i < j )
                std::swap( a[ i ],a[ j ] );
           else    
                break;
        }
        //i 最后指向第一个大于等于 pivot 的位置，因为 pivot 在 right-1 所以必须要找到偏大一点的分界点而不是 j 所代表的偏小的分界点
        std::swap( a[ i ],a[ right - 1 ] );//恢复枢纽元
        quicksort( a, left, i-1 );
        quicksort( a, i + 1, right );
    }
    else
        insertionSort( a, left, right );
}
// 另一种实现方式

template <typename E, typename Comp>
int partition(E A[], int l, int r, E& pivot) {
  do {
     //Move the bounds inward until they meet
     //Move l right and r left
     while (Comp::prior(A[++l], pivot));
     while ((l<r) && Comp::prior(A[--r],pivot));
     // Swap out-of-place values
     swap(A, l, r); 
  } while (l < r); // Stop when they cross
  swap(A, l, r);   // Reverse last swap[最后一次交换是多余的]
  return l; //Return 1st position in right part
}

快速排序的性质

最坏情形运行时间为 $O(N^{2})$
最好情形运行时间 $\Omega(NlogN)$
平均情形运行时间$O(NlogN)$
不是稳定的算法
虽然是原地排序但是由于递归所以需要$O(logN)$的额外空间

7.7.6 选择问题的线性期望时间算法

快速选择算法

1. 如果｜S｜=1，那么 k=1 并且将 S 中的元素作为答案返回，如果正在使用小数组的截止方法且｜S｜$ \leq CUTOFF$，则将 S 排序并且返回第 k 个元素
2. 选取一个枢纽元$v \in S$
3. 将集合$S-{v}$ 分割成 $S_{1}和 S_{2}$，过程就像在快速排序中所做的一样
4. 如果 $k \leq | S_{1} |$，那么第 k 个最小元必然在$S_{1}$中，所以返回 quickselect($S_{1}$,k)。如果 k=1+ | $S_{1}$ |，那么枢纽元就是第 k 个最小元，将其作为答案返回。否则这第 k 个最小元就在 $S_{2}$中，它是$S_{2}$中的第（k- | $S_{1}$ |-1 ）的最小元，返回 quickselect($S_{2}$,k- | $S_{1}$ | - 1)。
   但是快速选择的平均运行时间为 $O(N)$

7.8 桶排序

/** 
* Bucket Sort
* Allow for duplicate values among keys
* Allow for a set of N records falling in a range larger 
* than N ([0,MaxKeyValue-1])
**/
template <typename E, class getKey>
void bucketsort(E A[], int n) {
  List<E> B[MaxKeyValue]; //An array of linked lists
  E item;
  //assign records to bins 
  for (i=0; i<n; i++)
    //All records with key value i are placed in bin B[i]
    B[getKey::key(A[i])].append(getKey::key(A[i]));
  //process MaxKeyValue bins to output records
  for (i=0; i<MaxKeyValue; i++)
    for (B[i].setStart(); B[i].getValue(item); B[i].next())
      output(item);
}

桶排序的时间消耗包括：

• $\Omega(N)$的时间将所有的 N 条记录放入桶中
• 扫描$MaxKeyValue$个桶去输出 N 个记录
  如果 $MaxKeyValue$是$\Omega(N^{2})$的，那么总时间消耗将是$\Omega(N^{2})$的
  有一个限制是桶排序只对一个有限制的 key 的范围有效
  桶排序也可以对于一个 key 的最右边最低有效位开始对于每一个数位进行排序，直到对于最后一个最高有效位进行排序，最后会产生一个排序了的列表
  这样的时间复杂度为$\Omega(N)$

7.9 基数排序 radix sort

根据 radix 或者 base 对于 keyValue 的计算结果将数字放入桶中
根据 key 的数位从最右边的数位到最左边数位的顺序将记录安排到桶中
$b 为 base,r 为在 base 为 b 的情况下最大数字的位数$
一共会进行 r 轮，keys 被按顺序从桶中取出并且再次被放入桶中
总的运行时间是$O(r(N+b))$
Radix Sort

/*
* Radix sort an array of Strings.
* Assume all characters are ASCII, residing in the first 256 
* positions of the Unicode character set.
* Assume all have same length(stringLen).
*/
void radixSortA( vector<string> & arr, int stringLen ){
    const int BUCKETS = 256;
    vector<vector<string>> buckets( BUCKETS );
    for( int pos = stringLen - 1; pos >= 0; --pos ){
        for( string & s : arr )
            //Adds s at the end of the buckets[ s[ pos ] ]
           buckets[ s[ pos ] ].push_back( std::move( s ) );
        int idx = 0;
        for( auto & thisBucket : buckets ){
            for( string & s : thisBucket )
                 arr[ idx++ ] = std::move( s );
            thisBucket.clear( );
       }
    }
}

Counting Radix Sort

/*
* Counting radix sort
* B[] is array for buckets
* cnt[i] stores numbers of records in bucket[i]
* b is numbers of buckets(base), r is number of passes
*/
template <typename E, typename getKey>
void radix(E A[], E B[], int n, int r, int b, int cnt[]) {
  int j;
  for (int i=0, btoi=1; i<r; i++, btoi*=b) {//for r digits
    for (j=0; j<b; j++) cnt[j] = 0; 
    //Count # of records for each buckets on this pass
    for(j=0; j<n; j++) cnt[(getKey::key(A[j])/btoi)%b]++;
    //Index B: cnt[j] will be index for last slot of bucket j.
    for (j=1; j<b; j++) cnt[j] += cnt[j-1] ;
    /*Put records into buckets, from bottom of each bucket.*/
    for (j=n-1; j>=0; j--) 
      B[--cnt[(getKey::key(A[j])/btoi)%b]] = A[j];
    for (j=0; j<n; j++) A[j] = B[j]; //Copy B back to A.
  }
}

Radix Sort 的性质

总的时间复杂度是 $\Omega (r(N+b))$
摊还时间复杂度为$\Omega(NlogN)$
基数排序是稳定的，但不是原地排序

7.10 排序问题的下界

• 任何排序问题都不可能被任何算法以小于$\Omega(N)$的时间解决
• 任何基于比较的算法在最坏情况下都不可能优于$\Omega(NlogN)$
  决策树是一棵二叉树，可以模拟任何作出二项选择的过程
  决策树中最深节点的深度对应算法的最坏情况

一棵有$L$个叶子节点的二叉树至少有 $\lceil logL \rceil$的深度
所以任何基于比较的算法最坏情况都是$\lceil log(N!) \rceil=\Omega(NlogN)$
因为 N 个数字的排序有 N！种可能

选择问题的决策树下界

找到第 k 小的数字需要 N-k+$\lceil log \binom{N}{k-1} \rceil$

找到第 k 小元素的决策树至少有 $\binom{N}{k-1}2^{N-k}$个树叶

找到最小元素至少需要 N-1次比较

7.11 外部排序 External Sorting

用于处理很大的输入，因为输入太大为无法被放入内存中

• 记录被储存在磁带中，只能被顺序的进行访问
• 假设算法有至少三条磁带用于执行
• 假设内存最多同时可以存储并且排序 M 条记录
  算法一共需要$\lceil log(N/M) \rceil$轮
  如果使用 k-way merge 也就是在 k 条记录中选取最小值那么这个数字可以变为$\lceil log_{k}(N/M) \rceil$

Replacement selection

replacement selection 可以平均让每一轮的长度为 2M
这是一种堆排序的变式

• 读取 M 条数据到内存中，设置 last=m-1（指向堆数组中最后一个元素）
• 将 M 个数据放入最小堆
• 重复以下步骤直到堆为空

1. deleteMin 并且将最小值写到输出磁带上
2. 让 R 为下一个输入磁带中读取的记录，如果 R 大于刚才的输出就将 R 放在 root 处，否则就用 LAST 处的数据放在 root 处并且将 R 放在 LAST 位置，将 LAST 设置为 LAST-1（堆的大小减少 1）
3. 重新排序堆（保持堆序）

第 8 章 不相交集类（并查集）

并查集类是一个在线的问题，因为 find 解决的的合并问题是在合并操作之间进行的

构造函数

DisjSets::DisjSets( int numElements ) : s{ numElements, -1 }

任意合并：使第二棵树成为第一棵树的子树

普通的任意合并对于一系列操作的时间复杂度可能达到$\Omega(MN)$

void DisjSets::unionSets( int root1, int root2 )
{
    s[ root2 ] = root1;
}

/**
  * Perform a find.
  * Error checks omitted again for simplicity.
  * Return the set containing x.
*/
int DisjSets::find( int x ) const
{
    if( s[ x ] < 0 )
        return x;
    else
        return find( s[ x ] );
}

union by size 将大小小的树合并到大小较大的树上

如果所有 union 都以按照大小合并进行，那么可以保证任何节点的深度都不会超过 $O(logN)$
对于按大小合并的算法，find 的运行时间是 $O(logN)$
由于实际上只使用一个数组，所以可以让每个座位数组元素的根包含它的树大小的负值，这样初始时树的数组表示就都是-1。
当执行一次 union 的时候，要检查树的大小并更新为两棵旧的树的和，如果使用按大小求并则 连续 M 次 union 运算需要$O(M)$平均时间

union by height/rank 使得高度较小的树成为高度较高的树的子树

同样保证所有的树的深度最多就是$O(logN)$
这是一种平缓的算法，因为只有两棵相等深度的树求并的时候树的高度才会增加
由于开始的时候高度是 0 不是负数，所以我们实际上存储高度的负值并且减去一个附加的 1
union by height/rank

void DisjSets::unionSets( int root1, int root2 )
{
    if( s[ root2 ] < s[ root1 ] )
        s[ root1 ] = root2;
    else
    {
        if( s[ root1 ] == s[ root2 ] )
            --s[ root1 ];
        s[ root2 ] = root1;
    }
}

路径压缩

路径压缩在一次 find 操作期间执行，而与用来执行 union 的方法无关
假设 find（x），路径压缩的效果就是从 x 到根的路径上的每一个节点都使他的父节点变成根

执行 find（14）后产生的树

路径压缩

int DisjSets::find( int x )
{
    if( s[ x ] < 0)
        return x;
    else
        return s[ x ] = find( s[ x ] );
}

按秩合并和路径压缩的最坏情形都是$\Omega(M\alpha(M,N)),其中\alpha(M,N)是一个增长极为缓慢的函数，最大也只能达到 5$

第 9 章 图论算法

9.1 定义

简单路径：其上的所有顶点互异，但第一个顶点和最后一个顶点可能相同
有向无环图简称为 DAG

• 强连通：有向图中从每一个顶点到每一个其他节点都存在一条路径
• 弱连通：有向图不联通，但是其基础图是连通的
• 完全图：其每一对顶点之间都存在一条边

9.2 拓扑排序

先找出任意一个入度为 0 的顶点，然后显示出该顶点，并将它和它的边一起从图中删除。对其余部分继续应用这样的方法。
拓扑排序

void Graph::topsort( )
{
    Queue<Vertex> q;
    int counter = 0;
    
    q.makeEmpty( );
    for each Vertex v
        if( v.indegree == 0 )
            q.enqueue( v );
    while( !q.isEmpty( ) )
    {
        Vertex v = q.dequeue( );
        v.topNum = ++counter //分配下一个拓扑编号

        for each Veertex w adjacent to v
            if( --w.indegree == 0 )
                q.enqueue( w );
    }
    if( counter != NUM_VERTICES )
        throw CycleFoundException{ };
}

// 计算入度
for each Vertex v
    for each Vertex w adjacent to v
        w.indegree++;

9.3 最短路径算法

当出现负值圈的时候，最短路径问题就是不确定的

无权最短路径（BFS）

 void Graph::unweighted( Vertex s )
{
    Queue<VErtex> q;
    for each Vertex v
        v.dist = INFINITY;
    
    s.dist = 0;//源点
    s.enqueue( s );

    while( !q.isEmpty( ) )
    {
        Vertex v = q.dequeue( );
        for each Vertex w adjacent to v
            if( w.dist == INFINITY )
            {
                w.dist = v.dist + 1;
                w.path = v;
                q.enqueue( w );
            }
    }  
}

Dijkstra 算法

在每个阶段，Dijkstra 算法选择一个在所有 unknown 顶点中具有最小的$d_{v}$的顶点，同时声名从 s 到 v 的最短路径是 known 的，阶段的其余部分由 $d_{w}$的更新工作组成。
和 bfs 是一样的，如果所有的边都是正权边那么第一次遇到顶点并处理的时候一定得到最小的距离，所以在第二次遇到的时候如果节点已经声明为 known 那么就不做任何修改。
Dijkstra

void Grapgh::dijkstra( Vertex s )
{
    for each Vertex v
    {
        v.dist = INFINITY;
        v.known = false;
    }
    s.dist = 0;
    while( ther is an unkonwn distance vertex )
    {
        Vertex v = samllest unknown distance vertex;
        v.known = true;
        for each Vertex w adjacent to v
            if( !w.known )
            {
                DistType cvw = cost of from v to w;
                if( v.dist + cvw < w.dist )
                {
                    decrease( w.dist to v.dist + cvw );
                    w.path = v;
                }
            }
    }
}

生成树

一个图的生成树点集和原来相同，边集是原来边集的子集且是联通的，并且在生成树的边集中没有环

DFS的路径就是一颗生成树

DFS算法也可以用来找联通块

每个联通块都有相同的标号，不同的联通块之间的标号不相同

Main {
i : integer
for i = 1 to n do M[i] := 0;  //initial label is zero
label := 1;
for i = 1 to n do
  if M[i] = 0 then DFS(G,M,i,label); //if i is not labeled
  label := label + 1;                            //then call DFS
}
DFS(G[]: node ptr array, M[]: int array, i,label: int) {
  v : node pointer; 
  M[i] := label;
  v := G[i];  // first neighbor //
  while v != null do  // recursive call (below)
    if M[v.index] = 0 then DFS(G,M,v.index,label);
    v := v.next;  // next neighbor //
}

时间复杂度和空间复杂度都是$O(n+m)$

dfs

void DFS(Graph* G, int v) {
  PreVisit(G, v);  // Take some actions
  G->setMark(v, VISITED); //mark v
  for (int w=G->first(v); w<G->n(); w=G->next(v,w))
    if (G->getMark(w) == UNVISITED)
      DFS(G, w);
  PostVisit(G, v); // Take some actions
}

bfs

void BFS(Graph* G, int start, Queue<int>*Q) {
  int v, w;
  Q->enqueue(start);        // Initialize Q
  G->setMark(start, VISITED);

  while (Q->length() != 0) { // Process Q
    v = Q->dequeue();
    PreVisit(G, v);   // Take some actions

    for(w=G->first(v); w<G->n(); w=G->next(v,w))
      if (G->getMark(w) == UNVISITED) {
        G->setMark(w, VISITED);
        Q->enqueue(w);
      }
	}
}

Topological Sort

bfs实现

//Queue-based topological sort
void topsort(Graph* G, Queue<int>* Q) {
    int InDgree[G->n()];  //the size is the number of vertices
    int v, w;
    for (v=0; v<G->n(); v++) InDgree[v] = 0; //initialize
    //compute indgree for every vertex
    for (v=0; v<G->n(); v++) // Process every edge
         for (w=G->first(v); w<G->n(); w=G->next(v,w))
             InDgree [w]++;   // Add to w's InDgree

    for (v=0; v<G->n(); v++) // Initialize Queue Q
         if (InDgree[v] == 0) // enqueue v with no prerequisites
              Q->enqueue(v);
  
    while (Q->length() != 0) { //process vertices in Q
         v = Q->dequeue();  
         printout(v);     // output v
    
        for (w=G->first(v); w<G->n(); w=G->next(v,w)) {
             InDgree[w]--;    // One less prerequisite
             if (InDgree[w] == 0) //vertex v is now free
                 Q->enqueue(w);
        }
    }
}

dfs实现

• 当一个节点已经被访问过的时候，什么也不做
• 当一个递归pop back回原来节点的时候将该节点输出
• 这个算法将以逆序输出拓扑排序的结果

void topsort(Graph* G) { 
    int i;
    for (i=0; i<G->n(); i++) // Initialize Mark
        G->setMark(i, UNVISITED);
    for (i=0; i<G->n(); i++) // Process vertices
        if (G->getMark(i) == UNVISITED)
            tophelp(G, i);       // Call helper
}

void tophelp(Graph* G, int v) { // Process v
    G->setMark(v, VISITED);
    for (int w=G->first(v); w<G->n(); w=G->next(v,w))
        if (G->getMark(w) == UNVISITED)
            tophelp(G, w);
  printout(v);    // output v
}

Shortest-Path Algorithms

无权最短路使用BFS就可以解决

Distance[s] := 0
Enqueue(Q,s); 
Mark(s); //After a vertex is marked once 
               // it won’t be enqueued again
while queue is not empty do
    X := Dequeue(Q);
   for each vertex Y adjacent to X do
       if Y is unmarked then
           Distance[Y] := Distance[X] + 1;
           Previous[Y] := X; //if we want to record paths
           Enqueue(Q,Y); 
           Mark(Y);

Dijkstra

//Implementation of Dijkstra’s algorithm
//compute shortest path dists from “s”
void Dijkstra(Graph* G, int* D, int s) {
  int i, v, w;
  for (int i=0; i<G->n(); i++) // Initialize
      D[i] = INFINITY;
  D[s] = 0;
  for (i=0; i<G->n(); i++) { //process vertices
    //find the unvisited vertex with min dist
    v = minVertex(G, D); 
    if (D[v] == INFINITY) return; //v is unreachable

	  G->setMark(v, VISITED);
    //update the distance of v’s neighbors
    for (w=G->first(v); w<G->n(); w = G->next(v,w))
        if (G->getMark(w) == UNVISITED)
		 	if (D[w] > (D[v] + G->weight(v, w)))
        		D[w] = D[v] + G->weight(v, w);
  }
}

问题在于如何实现minVertex函数，找到距离最小的未访问节点

1. 扫描一遍所有|V|个节点找到最小值

   int minVertex(Graph* G, int* D) {
     int i, v = -1; 
    
     //initialize v to some unvisited vertex
     for (i=0; i<G->n(); i++)
       if (G->getMark(i) == UNVISITED) { 
           v = i; 
           break; }
     
     // Now find smallest D value
     for (i++; i<G->n(); i++)
       if ((G->getMark(i) == UNVISITED) && (D[i] < D[v]))
         v = i;
     return v;
   }

   最后会导致总的时间复杂度变为$\Omega(|V|^{2})$

2. 将所有未处理过的节点都放入一个优先队列中（小根堆）并且按照距离排序

   下一个距离值最小的节点可以在$\Omega(logN)$时间内找到

   当每一次对D（x）进行更新之后

   • 在堆中删除D（x）并且将新的D（x）重新插入
   • 或者在堆中插入一个更小的新距离值D（x）作为一条新的记录，后面较大的那条记录自然会被忽视，因为距离小的这条记录将会使节点变为VISITED

// Implementation using the priority queue
// Class for elements in the heap
Class DijkElem {
Public:
  int vertex, distance;
 
  DijkElem() {vertex = -1; distance = -1;}
 
  DijkElem(int v, int d) {vertex = v; distance = d};
};
//Implementation of Dijkstra’s algorithm 
void Dijkstra(Graph* G, int* D, int s) {
    int i, v, w;       // v is current vertex
    DijkElem temp;  DijkElem E[G->e()]; // Heap array  

    for (int i=0; i<G->n(); i++) // Initialize
       D[i] = INFINITY;
    D[s] = 0;
    
    // Initialize heap array
    temp.distance = 0; temp.vertex = s; 
    E[0] = temp;     
    heap<DijkElem, DDComp> H(E, 1, G->e()); 

    // get an unvisited vertex with smallest distance
    for (i=0; i<G->n(); i++) {
        do { 
            if(H.size() == 0) return; // Nothing to remove
            temp = H.removefirst(); //delmin
      v = temp.vertex;
        } while (G->getMark(v) == VISITED);

        G->setMark(v, VISITED);  //mark the vertex

        if (D[v] == INFINITY) return; //unreachable
   
        for(w=G->first(v); w<G->n(); w=G->next(v,w))
            if (G->getMark(w) == UNVISITED)
               if (D[w] > (D[v] + G->weight(v, w))) { 
                 //update D      
                  D[w] = D[v] + G->weight(v, w);
                  temp.distance = D[w]; temp.vertex = w;
                 // Insert new distance in heap
                  H.insert(temp); 
               }
    }
}

时间复杂度为$\Omega((|V|+|E|)log(|E|))$

多源最短路稀疏图可以跑|V|次Dijkstra，稠密图直接用Floyd就可以

具有负边值的图

在每一个阶段让一个顶点 v 出队，找出所有邻接到 v 使得$d_{w}>d_{v}+C_{v,w}$的顶点 w，并且更新$d_{w}和 p_{w}$，并在 w 不在队列中的时候将 w 放在队列中
Bellman-Ford

void Graph::wightedNegative ( Vertex s )
{
    Queue<Vertex> q;
    for each Vertex v
        v.dist = INFINITY;
    s.dist = 0;
    q.enqueue( s );
    while( !q.isEmpty( ) )
    {
        Vertex v = q.dequeue( );
        for each Vertex w adjacent to v
            if( v.dist + cvw < w.dist )
            {
                w.dist = v.dist + cvw;
                w.path = v;
                if (w is not already in q )
                    q.enqueue( w );
            }
    }
}

书上部分习题代码

Josephus problem 击鼓传花删除人问题

#include <iostream>
#include <list>
using namespace std;
int main()
 {
  int i,j, n, m, mPrime, numLeft;
  list <int > L;
  list<int>::iterator iter; 
//Initialization
  cout<<"enter N (# of people) & M (# of passes before elimination):";
  cin>>n>>m;
  numLeft = n;
  mPrime = m % n;
  for (i =1 ; i <= n; i++)
      L.push_back(i);
  iter = L.begin();
// Pass the potato
  for (i = 0; i < n; i++)
  {
   mPrime = mPrime % numLeft;
   if (mPrime <= numLeft/2) // pass forward
    for (j = 0; j < mPrime; j++)
      {
iter++;
if (iter == L.end())
   iter = L.begin();
}
    else // pass backward
      for (j = 0; j < mPrime; j++)
      	{
  if (iter == L.begin())
   iter = --L.end();
  else
   iter--;
    	}
   cout<<*iter<<" ";
   iter= L.erase(iter);
   if (iter == L.end())
      iter = L.begin();
   }
  cout<<endl;
  return 0;
}

计算后缀表达式的值

double evalPostFix( )
{
  stack<double> s;
  string token;
  double a, b, result;
  cin>> token;
  while (token[0] != ’=’)
  {
  result = atof (token.c_str());
  if (result != 0.0 )
     s.push(result); 
   else if (token == "0.0")
     s.push(result);
   else
  switch (token[0])
   {
     case ’+’ : a = s.top(); s.pop(); b = s.top();
                s.pop(); s.push(a+b); break;
     case ’-’ : a = s.top(); s.pop(); b = s.top();
                s.pop(); s.push(a-b); break;
     case ’*’ : a = s.top(); s.pop(); b = s.top();
                s.pop(); s.push(a*b); break;
     case ’/’ : a = s.top(); s.pop(); b = s.top();
                s.pop(); s.push(a/b); break;
     case ’^’ : a = s.top(); s.pop(); b = s.top();
                s.pop(); s.push(exp(a*log(b))); break;
    }
     cin>> token; 
   }
   return s.top();
}

将中缀表达式转换成后缀表达式

void inToPostfix()
 {
   stack<char> s;
   char token;
   cin>> token;
   while (token != ’=’)
   {
    if (token >= ’a’ && token <= ’z’)
      cout<<token<<" ";
    else
      switch (token)
      {
       case ’)’ : while(!s.empty() && s.top() != ’(’)
                  { cout<<s.top()<<" "; s.pop();}
                  s.pop(); break;
       case ’(’ : s.push(token); break;
        case ’^’ : while(!s.empty() && !(s.top()== ’^’ || s.top() == ’(’))
                   {cout<<s.top(); s.pop();}
                   s.push(token); break;
        case ’*’ :
        case ’/’ : while(!s.empty() && s.top() != ’+’ && s.top() != ‘-‘ && s.top() != ‘(‘)
                   {cout<<s.top(); s.pop();}
                   s.push(token); break;
        case ‘+’ :
        case ‘-‘ : while(!s.empty() && s.top() != ‘(‘ )
                   {cout<<s.top()<<’’ ‘‘; s.pop();}
                    s.push(token); break;
      }
      cin>> token;
   }
   while (!s.empty())
      {cout<<s.top()<<’’ ‘‘; s.pop();}
   cout<<ˇ = \nˇ;
  }

用一个数组实现两个栈可以

• 让一个栈从数组的左边向右边递增增长
• 另一个栈从数组的右边向左边递减增长

双端队列的实现（其实就是将list包装了一下）

list是一个双向循环列表

This requires a doubly linked list with pointers to the head and the tail In fact it can be implemented
with a list by just renaming the list operations.

template <typename Object>
class deque
{
public:
  deque() { l();}
  void push (Object obj) {l.push_front(obj);}
  Object pop (); {Object obj=l.front(); l.pop_front(); return obj;}
  void inject(Object obj); {l.push_back(obj);}
  Object eject(); {pop_back(obj);}
private:
  list<Object> l;
}; //

自调整表的数组和链表实现

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

#define MAX 10
typedef struct node
{
    int* A;
    int length;
    int Max;
}*List,List1;//qnode,*pnode;
void init(List L)
{
    L->A=(int*)malloc(MAX*sizeof(int));
    L->Max=MAX;
    L->length=0;
    for(int i=0;i<L->Max;i++)
        L->A[i]=-1;
}
void Insert(List L,int x)
{
    int i;
    if(L->Max<=L->length)
        printf("out of space!");
    else
    {
        if(L->A[0]==-1)
        {
            L->A[0]=x;
            L->length++;
        }
        else 
        {
            for(i=L->length-1;i>=0;i--)//把所有数字往后移动一个位置
                L->A[i+1]=L->A[i];
            L->A[0]=x;
            L->length++;
        }
    }
}
void PrintList(List L)
{
    for(int i=0;i<L->length;i++)
        printf("%d",L->A[i]);
    
}
void Find(List L,int x)
{
    int i=0;
    while(L->A[i]!=x&&L->A[i]!=-1)
        i++;
    if(L->A[i]==x)
    {
       for(int j=i;j>=0;j--)
            L->A[j]=L->A[j-1];
        L->A[0]=x; 
    }
    else{
        printf("out of space!");}
}
int main()
{
    List1 L;
    init(&L);
    Insert(&L,1);
    Insert(&L,2);
    Insert(&L,3);
    Insert(&L,4);
    Insert(&L,5);
    Insert(&L,6);
    Find(&L,2);
    Find(&L,7);
    PrintList(&L);
    return 0;
}
 

#include <stdio.h>
#include <stdlib.h>
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
 struct Node
{
    int Element;
    Position next;
};
List init()
{
    List L;
    L=(List)malloc(sizeof(struct Node));
    L->next=NULL;
    return L;
}
void Insert(List L,int x)
{
    Position pos,head;
    head=L;
    pos=(List)malloc(sizeof(struct Node));
    pos->Element=x;
    if(head->next==NULL)
    {
        head->next=pos;
        pos->next=NULL;
    }
    else
    {
        pos->next=head->next;
        head->next=pos;
    }
}
void PrintList(List L)
{
    Position pos=L->next;
    while(pos!=NULL)
    {
        printf("%d",pos->Element);
        pos=pos->next;
    }
}
Position FindPrevious(List L,int x)
{
    Position pos;
    pos=L;
    while(pos->next!=NULL&&pos->next->Element!=x)
        pos=pos->next;
    return pos;
}
Position Find(List L,int x)
{
    Position pos,head,previous;
    head=L;
    previous=FindPrevious(L,x);
    if(previous->next!=NULL)
    {
	    pos=previous->next;
	    previous->next=pos->next;
	    pos->next=head->next;
	    head->next=pos;
	    return pos;
    }
    else
    	return NULL;
}
int main()
{
    List L;
    L=init();
    Insert(L,1);
    Insert(L,2);
    Insert(L,3);
    Insert(L,4);
    Insert(L,5);
    Insert(L,6);
    L=Find(L,2);
    L=Find(L,6);
    PrintList(L);
    return 0;
}
 

王道考研真题复习

1.算法与算法评价

算法原地工作的含义是所需的辅助空间是常数

在相同规模的n下$O(n)$的算法在时间上总是优于复杂度为$O(2^{N})$的算法

• 因为时间复杂度指的是渐进时间复杂度，不要去为n赋予特殊值

假设$T(n)=\begin{cases} 1& \text{n=1} \ 2T(n/2)+n & \text{n>1}\end{cases} $

设n是2的正整数次幂

解:假设n=$2^{k}$,则$T(2^{k})=2T(2^{k-1})+2^{k}=2^{k}T(2^{0})+k2^{k}=2^{k}(k+1)$

显然是$O(nlog_{2}n)$级别的

2.线性表

线性表中除最后一个/第一个元素之外,每个元素都只有一个前驱/后继元素

在带头结点L的链表中删除一个最小值节点的算法

LinkList Delete Min(LinkList &L){
//1是带头结点的单链表，本算法删除其最小值结点
INode *pre=L，*p=pre->next;//p为工作指针，pze指向其前驱
    LNode *minpre=pre,*minp=p;//保存最小值结点及其前驱
    while(p!-NULL){
		if(p->data<minp->data){
			minp=p;//找到比之前找到的最小值结点更小的结点
			minpre=pre;
    	}
		pre=p;
		p=p->next;//继续扫描下一个结点
	}
    minpre->next=minp->next;//剥除最小值结点
	free(minp);
	return L;
}