- 最优置换算法(OPT)
最优置换(OPTimal replacement)，顾其名，知其义，这是一种最优的算法，因为对于任一页面请求序列，其产生的缺页中断次数时最少的，但，这只是理论上的最优。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。其最优性是容易证明的。
但是最优页面置换算法的实现是困难的，因为它需要我们预先就知道一个进程整个运行过程中页面走向的全部情况，而这几乎时不可能的。所以，这个算法主要还是用来衡量其他算法的优劣的。
Posts Tagged ‘算法’
November 4, 2009
November 3, 2009
常见处理机调度算法：
- 先来先服务(FCFS)
- 短作业优先调度(SJF)
- 优先级调度
- 静态优先级
- 动态优先级
- 高响应比优先调度
- 时间片轮转
- 多级队列调度算法
- 多级反馈队列调度算法
August 24, 2009
没啥好说的，只是要注意防止m = (r + l) / 2;时m会发生上溢。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | template <class T> int BSearch(T *a, size_t n, T v) { assert(a != NULL && n > 0); //! a == NULL || n <= 0 就坏了:-( size_t l = 0, r = n -1, m = l + (r - l) / 2; //! 勿用m=(l+r)/2; while(l <= r) { if(a[m] == v) return (int)m; else if(a[m] < v) l = m + 1; else r = m - 1; } return -1; } |
August 23, 2009
归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列，然后对两个子序列分别进行排序，最后进行合并操作，将两个子序列合成有序的序列。在合成的过程中，一般的实现都需要开辟一块与原序列大小相同的空间，以进行合并操作。这里介绍一种不需要开辟新的空间就可以进行归并操作的原地归并算法。代码来说事儿：
1 2 3 4 5 6 7 8 9 | //~ 原地归并 while(l < r && r < size) //~ 核心算法 { while(v[l] <= v[r] && l < r) ++l; //~ 找到左面第一个比v[r]大的v[l] size_t to_mv = 0; //~ 计数器 while(v[r] < v[l] && r < size) ++r, ++to_mv; //~ 右侧找到to_mv个比v[l]小的数 Exchange(v+l, r-l-to_mv, r-l);//~ 将此to_mv个数移到v[l]前面 l += to_mv; //~ 改变l，继续下一轮循环 }//~ l >-r 或者 r >= size时归并结束 |
August 17, 2009
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void reverse(Node * T) { assert(T); //~ 表头非空 Node* p = T->next, *t; if(p) { //~ 将第一个结点，即未来的表尾next域置空 t = p->next; p->next = NULL; p = t; } while(p) { //~ 将余下结点依次插入表头 t = p->next; p->next = T->next; T->next = p; p = t; } } |
August 16, 2009
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | template <class T> class Queue { public: Queue(int size = 30); ~Queue(); void EnQueue(T value); T DeQueue(); T GetFirst(); bool IsEmpty(); bool IsFull(); void ClearQueue(); private: T *queue; int front; int rare; int MaxSize; int CurLen; }; |
一个堆栈类模板，和用到此模板的一个表达式计算器。
输入四则运算表达式（可含括号），输出计算结果，暂未提供盛放运算和浮点数功能。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Stack { public: Stack(int stack_size = 30); ~Stack(); void Push(T value); T Pop(); T Top(); bool IsEmpty(); bool IsFull(); void ClearStack(); private: int top; T* stack; int size; }; |
一种遍历算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | int main() { string word; cin>>word; int len = word.length()-1; long psb = 1; for (int i = 0;i < len;i++) { psb *= 2; } int *flags = new int[len]; for (int i = 0;i < psb;i++) { int temp = i; for (int j = 0;j < len;j++) { flags[j] = temp%2; temp = temp/2; } if(i>0) { for (int j = 0;j < len;j++) { cout<<word[j]; if(flags[j] == 1)cout<<"-"; } cout<<word[word.length()-1]<<endl; } } } |
August 14, 2009
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* * pre存放先序序列， * in存放中序序列， * n为结点个数， * 返回二叉树根指针 */ BTree CreateBT(Type * pre, Type * in, int n) { if(n <= 0) return NULL; BTree bt = new BTNode; Type * p; int k; bt->data = *pre; for(p = in; p < in + n; ++p) if(*pre == *p) break; k = p - in; bt->lchild = CreateBT(pre+1, in, k); bt->rchild = CreateBT(pre+k+1, p+1, n-k-1); return bt; } |
August 12, 2009
严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
