* 输出格式控制
+ 成员函数: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();}
相关资源：c++实现的二叉树各种操作
