C++算法与二叉树的实现

* 输出格式控制
  + 成员函数:width fill pricision setf/unsetf
  + 格式控制符:endl/flush/setw/setf/sefpricision
  + 文件打开方式:ios::out/ios::in/ios::app/ios::binary(for windows)
  + open ofstream fout;fout.open(文件名);//不提倡这么写
  + is_open();//判断打开否?if(!fout.isopen())//if(!fout)一样.一般不用if

(!fout.isopen())这类形式.

* 异常
  + try{  throw 数据; } catch(类型 e){ /*code*/ }
catch(子类 e){ /*code*/ }catch(父型 e){ /*code*/ }
catch(...){ /*code*/ }
  + 如果有未处理异常,此异常会向调用方传递.

* 链表
  + struct Node{
T data;
Node* next;
    };//链表结点
  + Node* p = head;p = p->next;
  + 尾结点的标志是:p->next == NULL;
  + 创建空链表:head = NULL;
  + 释放,思路是从头到尾依次释放.
  + 增删改查.
- 头插法:p->next = head; head = p;
- 当查找时,找到了返回索引号,如未找到则返回-1
- 当删除时要返回删除结点的前一个结点.getPointer(pos-1)
pre->next = cur->next;
delete cur;//释放很重要,不要忘了此步
  + 附加操作: size(),empty(){ /*head是否为空*/ },getHead/*有无头?

getTail/*getPointer(size()-1))*/
======================================================
* 双向链表

struct Node{
	T data;
	Node* prev;
	Node* next;
};

赋值时要多给一个指针prev赋值
定义时不但要定义一个头指针还要定义一个尾指针.
------------------------------------------------------
* 栈,队列

栈(LIFO/FILO)又称线性表,只允许在同一端进行插入和删除.
组合也可以达到代码重用的目的.但是组合优于继承.
+ QUEUE

class Queue{
	List l;
public:
	void push(const T& t){ }	//数据入队
	void pop(){ } 			//删除队首元素
	T front(){ }			//取得队首元素
	T back(){ } 			//取得队尾元素
	bool empty(){ } 		//判断队列是否为空
	int size(){ } 			//返回队列元素个数
	void clear(){ }			//清空整个队列
};// The end of class Queue

//用数组来实现栈
#include <iostream>
using namespace std;
typedef int T;

class Stack{
        T a[10];
        int num;//已经放的元素个数
public:
        void push(const T& t){
                if(full())
                        throw "Exception:stack over";
                a[num++] = t;
        }
        void pop(){
                if(empty())
                        throw "Exception:stack empty";
                num --;
        }
        T top(){
                if(empty())
                        throw "Exception:stack empty";
                return a[num]-1;
        }
        bool empty(){
                return num==0;
        }
        bool full(){
                return num==10;
        }
        int size(){
                return num;
        }
        void clear(){
                num = 0;
        }
        int capacity(){
                return 10;
        }
        Stack():num(0){  }
};
int main()
{
        Stack s;
        for(int i=0;i<10;i++)
                s.push(i+1);
        while(!s.empty()){
                cout << s.top() << ' ';
                s.pop();
        }
        cout << endl;
        for(int i=0;i<10;i++)
                s.push(i);
        cout << "full?" << s.full() << endl;
        try{
                s.push(100);
        }
	//注意异常处理时,要严格的类型匹配
        catch(const char* e)/*捕获字符串类型异常*/{
                cout << e << endl;
        }
        catch(...){
                cout << "Unknow Exception" << endl;
        }
        cout << "Finish" << endl;
}

--------------------------------------------
* Binary Tree
处理树时一般会用到递归.
树的分支互不交叉,有统一的根
+ binary search tree(BST):二叉查找树或叫二叉排序树.
   - 左子树:A node's left child must have a key less than its paren.
   - 右子树:A node's right child must have a key greater than or equal

to its parent

//树的节点定义
struct Node{
	T data;
	Node* left;  //指向左子树的根节点
	Node* right; //指向右子树的根节点
	Node(const T& t):data(t),left(NULL),right(NULL){}
};// end of struct tree node

要管理二叉树需要:Node* root = NULL;

//对树的遍历
void travel(Node* tree){
	if(!tree) return;
	travel(tree->left);//先访问
	cout << tree->data << ' ';
	travel(tree->right);
}

遍历顺序:根左右:前序遍历,先根遍历
左根右:中序遍历,中根遍历(用的最多的遍历方式)
左右根:后序遍历,后根遍历

//清空
void clear(Node*& tree){
	if(!tree) return;
	clear(tree->left);
	clear(tree->right);
	delete tree;
	tree = NULL;
}
//把问题想简单点
//返回二叉树的节点数
int size(Node* tree){
	if(!tree) return 0;
	return size(tree->left)+size(tree->right)+1;
}

bool empty(Node* tree){}//EASY
+ 增加

void insert(Node*& tree,Node* p){
	if(tree==NULL) tree = p;
	else if(p==NULL) return;
	else if(p->data<tree->data)
		insert(tree->left,p);
	else	insert(tree->right,p);
}

+ 查找

Node*& find(Node*& tree, const T& t){
	if(tree==NULL) return tree/*tree为NULL*/;
	if(tree->data==t) return tree;//此时tree定不是NULL
	if(t<tree->data) return find(tree->left,t);
	else return find(tree->right,t);
}

+ 删除
1,合并左右分支
2,让指针指向合并后的分支
3,释放要删除的节点

void erase(Node*& tree,const T& t){
	Node*& p = find(tree,t);
	if(p==NULL) return;
	insert(p->right,p->left);
	Node* q = p;
	p = p->right;
	delete q;
}

+ 改

//注意不能直接更改数据
void update(const T& o, const T& n){
	Node *& p = find(tree,o);
	if(p==NULL) return;
	erase(root,o);
	p = new Node(n);
	insert(root,p);
}

==================================================
* 什么是算法?
算法是在有限步骤内求解某一问题所使用一组定义明确的规则.
通俗的说算法就是计算机解题的过程 .
算法有五个重要的特征:有穷性,确切性,输入,输出,可行性.
每个算法都有一个复杂度(/性)complexity,又分为时间复杂度和空间复杂度.
现在的空间基本上都不是问题,所以最主要还是时间上的问题.
时间是一个重要的标志.我们关心一个算法的效率主要是关心他的时间复杂度
* 算法分析
  - 确定与检验程序正确与否
  - 运行速度
  - 程序的复杂性
  - 程序的可靠性(健壮性)
- 野指针,垃圾数据,局部变量的引用或指针
- 使用已经delete 的空间,越界访问数组
- 没有错误检查.
  - 使用内存的大小
  - 代码的size

设计出复杂性尽可能低的算法.
--------------------------------------------------
* 程序的性能
hardware
The programming language used
The compiler used
The OS

* 运行效率
平均运行时间
最佳与最差的运行情况
大O表示法:表示算法的效率
O(最多多少次)
A linear search(线性查找): O(N)
A binary search(二分查找,折半查找): O(log(2)N)

* 算法设计策略
蛮力法(暴力法) ----- 穷举所有可能性.
递归技术 ----- 最常用的算法设计思想,体现于许多优秀算法中.(效率虽低,但低不

到哪去,所以尽管放心用)
分治法 ------ 分而制之的算法思想,体现了一分为二的哲学思想.
以上为常见的算法策略
-------------------------------------------------
不常见的:
模拟法 -------- 用计算机模拟实际场景
贪心算法 ------ 贪心正常,每个人都会有贪念
优化法 ------- 利用生物学优先原理.
=================================================
* 常用的重要排序方法.
+ 选择排序
最直接的排序方法,每次选择一个最大(最小)的元素放到应该的位置.

//排序
#include <iostream>
using namespace std;

typedef int T;
void sort(T a[], int n){ // 可写成T* a 
	for(int i=0;i<n-1;i++){
		int pos = i;
		for(int j=i+1;j<n;j++){
			if(a[j]<a[pos])
				pos = j;
		swap(a[pos],a[i]);
	}
}
int main()
{
	const int N=10240;
	int a[N];
	for(int i=0;i<N;i++)
		a[i] = N-i;
	for(int i=0;i<10;i++)
		cout << a[i] << ' ';
	cout << endl;
}

//二叉树完整例子
#include <iostream>
using namespace std;

typedef int T;
class BanaryTree {
        struct Node {
                T data;
                Node* left;
                Node* right;
                Node(const T& t):data(t),left(NULL),right(NULL){ }
        };//end of struct Node

        Node* root;
        int n;
public :
        BanaryTree():root(NULL),n(0){ }
        ~BanaryTree() {
                clear(root);
                cout << "~BanaryTree()" << endl;
        }
        int size() { return n; }

        void add(const T& t){
                Node* p = new Node(t);
                insert(root,p);
                n ++ ;
        }
        void show(const Node* tree){
                if(tree==NULL) return;
                show(tree->left);
                cout << tree->data << ' ';
                show(tree->right);
        }
        void travel(){
                show(root);
                cout << endl;
        }
        void clear(Node*& tree){
                if(!tree) return;
                clear(tree->left);
                clear(tree->right);
                delete tree;
                tree = NULL;
        }
        bool isHave(const T& t){
                if(find(root,t)) return true;
                else return false;
        }
        void erase(const T& t){
                Node*& p = find(root,t);
                if(!p) throw "Exception:no this element";
                Node* q = p;
                insert(p->right,p->left);
                p = p->right;
                delete q;
                q = NULL;
        }
        void update(const T& o, const T& n){
                erase(o);
                add(n);
        }
private:
        void insert(Node*& tree, Node* p){
                if(tree==NULL) tree = p;
                else if(!p) return;
                else if(p->data<tree->data) insert(tree->left,p);
                else insert(tree->right,p);
        }
        Node*& find(Node*& tree, const T& t){
                if(!tree) return tree;
                else if(tree->data==t) return tree;
                else if(t<tree->data) return find(tree->left,t);
                else return find(tree->right,t);
        }
};
int main()
{
        BanaryTree b;
        for( int i=1;i<10;i++)
                b.add(i);
        b.add(18);
        b.add(100);
        b.add(-5);
        cout << "size():" << b.size() << endl;
        b.travel();
        cout << "isHave(3):" << b.isHave(3) << endl;
        cout << "isHave(0):" << b.isHave(0) << endl;
        try{
                b.erase(8);
        }catch(const char* e) { cout << e << endl; }
        b.travel();
        b.update(-5,-199);
        b.travel();
}