Skip to content

Latest commit

 

History

History
executable file
·
852 lines (731 loc) · 23.8 KB

algrithom.org

File metadata and controls

executable file
·
852 lines (731 loc) · 23.8 KB
Raw

data structure

链表 list structure.

struct node{ void * data; Node * next; }Node;

basic list operation

every list has a “head” so that through it, you could walk all the nodes in the list.

add to a list

Node* addtolist(Node * head, Node * tobeadd) // maybe return a new head which is different from the one in the first arg //add tobeadd to right after head , if head==NULL, then head will be tobeadd node. { Node *Hh = head; if(Hh) { tobeadd->next = Hh->next; Hh->next = tobeadd; } else { tobeadd->next = NULL; Hh= tobeadd; } return Hh; }

Node* removelist(Node *head, Node *tobermv) //maybe return a new head if tobermv is the only node, head==tobermv { if(head == tobermv) { head=NULL; } else { pre

} } }

Queue 队列

FIFO First In First out

循环队列

template <class DType> class Queue // FIFO, first in first out policy, a cirticulate queue in an array storage. { public: Queue(int size=3); ~Queue() { delete [] elem ;} void EnQueue(const DType &data); DType DeQueue(); int GetEleCount(); private: DType * elem; int maxSize; int curNum; int rear, front; // front is index fro dequeue, rear is for enque };

template <class DType> Queue<DType>::Queue(int size):curNum(0),front(0),rear(0), maxSize(size) { elem = new DType[maxSize]; assert( elem != 0); }

template <class DType> void Queue<DType>::EnQueue(const DType &data) { assert ( GetEleCount() < maxSize ); elem[ rear ] = data; rear = (rear + 1) % maxSize; curNum++; }

template <class DType> DType Queue<DType>::DeQueue() { // printf(“indsde dequeue and front is %d and rear is %d\n”,front, rear);

assert ( GetEleCount() > 0); DType tt = elem[front]; front = ( front + 1) % maxSize; curNum–; return tt ; }

template <class DType> int Queue<DType>::GetEleCount() { return curNum; }

linked list queue

usage example (Pascal Triagle)

stack

FILO First In Last Out ===================================================================== template <class DType> class Stack // FILO, first in last out policy { public: Stack(int size=10); ~Stack() { delete [] elem ;} void Push(const DType &data); DType Pop(); int GetEleCount(); private: DType * elem; int maxSize; int top; };

template <class DType> Stack<DType>::Stack(int size):top(-1), maxSize(size) { elem = new DType[maxSize]; assert( elem != 0); }

template <class DType> void Stack<DType>::Push(const DType &data) { assert( top < maxSize ); cout<< “input DType addr is ” << &data <<endl ; elem[++top] = data; cout<< “store element is ” << &elem[top]<<endl; }

template <class DType> DType Stack<DType>::Pop() { assert( top != -1 ); return elem[top–] ; }

template <class DType> DType Stack<DType>::Peek() { assert( top != -1 ); return elem[top] ; }

template <class DType> int Stack<DType>::GetEleCount() { return top; } template <class DType> bool Stack<DType>::IsEmpty() { return top== -1 ; }

==========================================================================================

usage example (post expression )

if there is a expression such as “A+B*(C-D)-E/F” then post expression is ABCD-*+EF/- then we could push ABCD- in the stack, then pop - D C to calc, and push the R1, then push * ,pop *, R1, B， R1 *，then R2, push R2,push +……… Thus express value could be generated.

二叉树 Binary Tree

二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现

一、基本概念

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。 性质： 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。

类型： 1.满二叉树：所有终端都在同一层次，且非终端结点的度数为2。 在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。 2.完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。 对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。

二、存储结构

顺序存储： 将数据结构存在一块固定的数组中。

[cpp] view plaincopyprint? 01.#define LENGTH 100 02.typedef char datatype; 03.typedef struct node{

  1. datatype data;
  2. int lchild,rchild;
  3. int parent;

07.}Node;

09.Node tree[LENGTH]; 10.int length; 11.int root;

虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储：

[cpp] view plaincopyprint? 01.typedef char datatype;

03.typedef struct BinNode{

  1. datatype data;
  2. struct BinNode* lchild;
  3. struct BinNode* rchild;

07.}BinNode;

09.typedef BinNode* bintree; //bintree本身是个指向结点的指针

三、二叉树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

前序遍历：根节点->左子树->右子树

中序遍历：左子树->根节点->右子树

后序遍历：左子树->右子树->根节点

例如：求下面树的三种遍历

a / \ b c / \ d f \ / e g

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

binary Tree Generation

create a binary tree from the array in preorder, 0 means the null point int input[]={1,2,3,0,0,4,0,0,5,6,0,0,0}; 1 / \ 2 5 / \ /\ 3 4 6 0 / \ / \ /\ 0 0 0 0 0 0

int CreateBiTree( BTNode ** rn) //Creation of a binary tree from an array in preorder, 0 means null point { static int sdep = 1; static int ind = -1; char ch = 0; ind ++; if(input[ind] == 0) { *rn = NULL; return 1; } *rn =(BTNode *) malloc(sizeof (BTNode)); if(! (*rn)) {return -1;} (*rn) ->data =input[ind]; CreateBiTree(&((*rn)->left) ); CreateBiTree(&((*rn)->right) ); }

int HeightofBTree(BTNode *rn) //Height of the tree { int h1, h2; if( rn == NULL) return 0; h1 = HeightofBTree(rn->left); h2 = HeightofBTree(rn->right); return (h1>h2?h1:h2) +1; }

BinaryTree output like a graphics(not perfect)

=============================== void LevelPrintBT(BTNode *rn, int level) { int j = 0; char dst[20]=” “; if( rn == NULL) { sprintf(buffer[level]+strlen(buffer[level]) ,”:%c%s”,’O’, &dst[14-14/(level+1)]); return ; } // printf(“the level is %d and dst is %s\n”,level,&dst[0]); sprintf(buffer[level]+strlen(buffer[level]) ,”:%d%s”,rn->data,&dst[14-14/(level+1)]); level++; MaxHeight = MaxHeight>level? MaxHeight :level; LevelPrintBT(rn->left , level ); LevelPrintBT(rn->right, level );

} void TrLePBT(BTNode *BRoot ) //print btree from left to right, from up to down. {

char dst[30]; LevelPrintBT(BRoot,0); printf(“Maxheight is %d \n”, MaxHeight); for(int i =0; i< MaxHeight+1; i++) { int j = 0; dst[0]=’\0’; while(j++ < MaxHeight - i) strcat(dst, ” “); printf(“%s%s\n”,dst , buffer[i]); } } =========== output

:1 :2 :5 :3 :4 :6 :O :O :O :O :O :O :O

递归实现遍历(以前序遍历为例，其他的只是输出的位置稍有不同)

void PreTranverseBT(BTNode *rnd) { if(rnd == NULL) return; else printf(“::%d”, rnd->data );

PreTranverseBT(rnd->left); PreTranverseBT(rnd->right); printf(“]]\n”, rnd->data ); }

void PostTranverseBT(BTNode *rnd) { if(rnd == NULL) return;

PostTranverseBT(rnd->left); PostTranverseBT(rnd->right); printf(“::%d”, rnd->data ); printf(“]]\n”, rnd->data ); }

void MidTranverseBT(BTNode *rnd) { if(rnd == NULL) return; else

MidTranverseBT(rnd->left); printf(“::%d”, rnd->data ); MidTranverseBT(rnd->right); printf(“]]\n”, rnd->data ); }

非递归的实现

因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。数量确定，以顺序栈存储。 Simulate the recursion function invoking with Stack (Push and Pop) push in root, then push root->left(not null), if it hasn’t been pushed yet. push root->right(not null), if root->left has been pop out just now. pop the root if(both root->right and root->left are null)

using p to record previous pop element

when pop, if its left child of root, pop one layer, root->left if its right child of root, pop two layer, root->right, root

void PostTraWithoutRecur(BTNode* head) { if (head == NULL) { return; } printf(“post oder is \n”); Stack<BTNode *> stack ; stack.Push(head); BTNode * p = head; while (!stack.IsEmpty()) { BTNode* next = stack.Peek(); if( p == next->right) { p = stack.Pop(); printf(“:%d:”,p->data); continue; } if( next->left != NULL && p != next->left ) { stack.Push(next->left); } else if(next->right != NULL) { stack.Push(next->right); } else { p = stack.Pop(); printf(“:%d:”,p->data); } } }

void PreTraWithoutRecur(BTNode* head) { if (head == NULL) { return; } printf(“\npre oder is \n”); Stack<BTNode *> stack ; stack.Push(head); printf(“:%d:”,head->data); BTNode * p = head; while (!stack.IsEmpty()) { BTNode* next = stack.Peek(); if( p == next->right) { p = stack.Pop(); continue; } if( next->left != NULL && p != next->left ) { stack.Push(next->left); printf(“:%d:”,next->left->data); } else if(next->right != NULL) { stack.Push(next->right); printf(“:%d:”,next->right->data); } else { p = stack.Pop(); // printf(“:%d:”,p->data); } } }

void MidTraWithoutRecur(BTNode* head) { if (head == NULL) { return; } printf(“mid oder is \n”); Stack<BTNode *> stack ; stack.Push(head); BTNode * p = head; while (!stack.IsEmpty()) { BTNode* next = stack.Peek(); if( p == next->right) { p = stack.Pop(); continue; } if( next->left != NULL && p != next->left ) { stack.Push(next->left); } else if(next->right != NULL) { stack.Push(next->right); printf(“:%d:”,next->data); } else { p = stack.Pop(); printf(“:%d:”,p->data); } } }

层次遍历：即每一层从左向右输出

元素需要储存有先进先出的特性，所以选用队列存储。

01.#define MAX 1000

03.typedef struct seqqueue{

  1. bintree data[MAX];
  2. int front;
  3. int rear;

07.}seqqueue;

10.void enter(seqqueue *q,bintree t){

  1. if(q->rear == MAX){
  2. printf(“the queue is full!\n”);
  3. }else{
  4. q->data[q->rear] = t;
  5. q->rear++;
  6. }

17.}

19.bintree del(seqqueue *q){

  1. if(q->front == q->rear){
  2. return NULL;
  3. }else{
  4. q->front++;
  5. return q->data[q->front-1];
  6. }

26.}

void level_tree(bintree t){ seqqueue q; bintree temp; q.front = q.rear = 0; if(!t){ printf(“the tree is empty\n”); return ; } enter(&q,t); while(q.front != q.rear){ t=del(&q); printf(“%c “,t->data); if(t->lchild){ enter(&q,t->lchild); } if(t->rchild){ enter(&q,t->rchild); } } }

利用前序遍历的结果生成二叉树

01.//递归调用，不存点，想的时候只关注于一个点，因为还会回来的，不要跟踪程序运行，否则容易多加循环

03.void createtree(bintree *t){

  1. datatype c;
  2. if((c=getchar()) == ‘#’)
  3. *t = NULL;
  4. else{
  5. *t = (bintree)malloc(sizeof(BinNode));
  6. (*t)->data = c;
  7. createtree(&(*t)->lchild);
  8. createtree(&(*t)->rchild);
  9. }

13.}

二叉树的查找

01.bintree search_tree(bintree t,datatype x){

  1. if(!t){
  2. return NULL;
  3. }
  4. if(t->data == x){
  5. return t;
  6. }else{
  7. if(!search_tree(t->lchild,x)){
  8. return search_tree(t->rchild,x);
  9. }
  10. return t->lchild;
  11. }

13.}

统计结点个数

01.int count_tree(bintree t){

  1. if(t){
  2. return (count_tree(t->lchild)+count_tree(t->rchild)+1);
  3. }
  4. return 0;

06.}

比较两个树是否相同

01.int is_equal(bintree t1,bintree t2){

  1. if(!t1 && !t2){ //都为空就相等
  2. return 1;
  3. }
  4. if(t1 && t2 && t1->data == t2->data){ //有一个为空或数据不同就不判断了
  5. if(is_equal(t1->lchild,t2->lchild))
  6. if(is_equal(t1->rchild,t2->rchild)){
  7. return 1;
  8. }
  9. }
  10. return 0;

12.}

BST(Binary Search Tree)二叉搜索树 creation

all left child value < root value > all right child value ==================================================== int input[]={12,21,23,10,60,74}; typedef struct _BTNode { int data; _BTNode *left; _BTNode *right;

}BTNode;

int InsertBinarySearchTree( BTNode ** rnd, int ind) //BST *create the bST tree * { // static int ind = -1; if(*rnd == NULL) { *rnd =(BTNode *) malloc(sizeof (BTNode)); if(! rnd) {return -1;} ( *rnd)->left = NULL; ( *rnd)->right = NULL; ( *rnd)->data = input[ind ]; // printf(“add index %d data %d\n”,ind, input[ind]); return 1; } if( (*rnd)->data > input[ind]) InsertBinarySearchTree( &((*rnd)->left) , ind ); else InsertBinarySearchTree( &( (*rnd)->right) , ind ); } ====================================================

Heap(Maximum/Minimum)

a Binary Tree has these feature called Heap K={k0,….kn-1} //K0 and Kn-1按照完全二叉树的顺序生成一颗完全二叉树 if Ki<=K2i+1 && Ki<=K2i+2, then this is a Heap K0 i=0 / \ 2i+1 ,2i +2 K1 K2 i=1 / \ / \ K3 K4 K5 K6 i=2

MinHeap(int arr[],int n){ heap = new int[maxSize>n ? maxSize: n]; heap = arr; curSize = n; int curPos = (CurSize -2)/2; // from the up level of the deepest leaf node while( curPos >= 0) // loop to top of the tree root to get a filterDown heap each time { FilterDown(curPos, CurSize -1); } }

FilterDown(const int start, const int end) { int i = start, j=2*i+1; int temp=heap[i]; // filterDown the start’s value to assure start’s value < left but > right while(j<=end) { if(j< end && heap[j].key > heap[j+1].key) j++; //j is smaller one of the two children if(temp.key <= heap[j].key) break; // if start’s value less than children’s value, no loop else { heap[i] = heap[j]; i=j; j=2*i+1;} // else override root’s value with children’s less one } heap[i]=temp; }

Heap sort

void HeapSort(datalist<Type> & list) { MinHeap(array, size); for(i= list.curSize-1; i >=1 ; i–) { Swap(list.Vector[0], list.Vector[i]); // i is the selected minimum one. Vecotr[0] is the minimum one FilterDown (0, i-1); // next, FilterDown(0, i-1), then Vector[0] is the minimum one } } }

函数的递归调用

函数的调用实际是压栈和出栈的过程，对于需要压栈多次的算法，可以用函数递归来实现。 在现实生活中，递归的方法更象是分治法。

函数的递归举例

#include <stdio.h> #define N 3 #define I 2 //2的3次方 int b[8][N]; int a[N]; void fr(int n) { int i=0; static int j=0; for(i=0; i<I; i++) { if(n == 0) { int k =0; for (k=0; k<N; k++) { b[j][k] = a[k]; printf(“%d -“, a[k] ); } printf(“\n”); j++; return; } a[N-n] = i; fr(n-1);

}

} main() { int c,d; fr(N); for( c=0; c< 8; c++) { printf(“===========”); for ( d=0; d<N; d++) printf (“%d “,b[c][d]); } } ===================================== 这个例子给出了排列组合的所有情形。这里a[N]记录了一次压栈的完整过程，b记录了所有的数据组合形式。 如果需要先探底到栈底，可以把a[N]放到fr(n-1)后面。这个算法也适应于下棋的穷举法。

排序

插入排序

直接插入排序

插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。 assuming there’s a sorted list v[0],…v[i-1] is a sorted array, and when add v[i], then v[0],…v[i-1], v[i] are a sorted array also. void InsertionSort(datalist<Type> &list) { for(int i =1; i<list.CurrentSize; i++) Insert(list,i); }

void Insert(datalist<Type> &list, int i) { Type tmp = list.Vector[i]; int j=i; whiel(j>0&& tmp.getKey()<list.Vector[j-1].getKey()) { list.Vector[j] = list.Vector[j-1]; j–;} // move the pre value to upper index to make the room insert list.Vector[j]= tmp; }

希尔排序(Shell sorting)

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 void Shellsort(datalist<Type> & list) { int gap= list.CurrentSize/2; while(gap) { ShellInsert(list, gap); gap= gap==2 ? 1:(int)gap/2; // decrease the gap } void ShellInsert(datalist<Type> & list, const int gap) { for (int i=gap; i<list.CurrentSize; i++){ Type tmp = list.Vector[i]; int j=i; // while loop is a insertsort while(j>=gap && tmp.getKey() < list.Vector[j-gap].getKey() ){ list.Vector[j] = list.Vector[j-gap]; j -= gap; } list.Vecotr[j]=tmp; }// for loop is for different group devided by gap }

交换排序

sort by exchange two vaule in the storage

冒泡排序

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。

template <class T> void bubble_sort( T a[], int n ) { // 稳定的排序

// 交换标志exchanged,我们希望用这个标志减少不必要的扫描. // 当它为真时,表明交换之前数组无序,但我们也不能确保在交换之后数组每一个 // 元素都排到有序状态下的正确位置了,所以再对数组进行扫描是必要的. // 当它为假时,表明数组有序了,不必再对数组进行扫描了. bool exchange = true; // 算法开始前,自然假设数组无序 for( int i = n - 1; i > 0 && exchange; –i ) { // 最多做n-1趟扫描 exchange = false; // 在一趟扫描开始前,我们总假设这趟扫描是不必要的 for( int j = 0; j < i; ++j ) { // 对当前无序区a[0:i]进行扫描 if( a[j+1] < a[j] ) { std::swap( a[j+1], a[j] ); // 大的往下沉,而小的往上冒 exchange = true; // 发生了交换,故将交换标志置为真 } } } }

快速排序

快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1） 如果不多于1个数据，直接返回。 （2） 一般选择序列最左边的值作为支点数据。 （3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4） 对两边利用递归排序数列。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 快速排序的思想就是在一个数的集合中随意挑选一个基准数，把所有比它大的数放在左边，把所有比它小的数放在右边。 其实快速排序是利用一趟排序的时间，把这个基准数放在相应的位置，实际是挑出这个数在有序数列中的正确位置。 然后以这个位置为界，左边和右边的集合再进行一次快排。

递归快排（非随机）

void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // 从右向左找第一个小于x的数 j–; if(i < j) s[i++] = s[j];

while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j–] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // 递归调用 quick_sort(s, i + 1, r); } }

选择排序

直接选择排序( 时间复杂度 O(n^2))

Vector V[n] ={}; V[i]~V[n-1] To select a minimum value from the set V[i] to V[n-1] and only change the minum value ‘s position with index i’s position. then next to select V[i+1]~V[n-1] for the smae rule, loop from i=0 to i=n-1 ================================================= template <class T> void selection_sort( T a[], int n ) { // 不稳定; 反例: { 2, 2, 1 } int min; for( int i = 0; i < n - 1; ++i ) { // 最多做n-1趟排序 min = i; // 先假设a[i]最小 for( int j = i + 1; j < n; ++j ) // 在当前无序区a[i:n-1]中查找最小值 if( a[j] < a[min] ) min = j; // min记下当前无序区最小值所在位置 if( min != i ) // 找到比当前a[i]更小者 std::swap( a[i], a[min] ); } } ================================================ 效率差不多吧，选择排序的查找和交换过程跟冒泡的次数差不多的吧 冒泡排序是每一次都可能要交换 而选择排序是在比较时记下a[i]的位置 最后来交换 所以他们的交换过程是不一样的 而查找的过程是一样的 效率不会比冒泡的低…

锦标赛排序 ( 时间复杂度 O(n*log2n))

堆排序 ( 时间复杂度 O(n*log2n))

堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

归并排序

归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。