本文最后更新于:2024年12月27日 下午
树的遍历
递归
1 2 3 4 5
| Void PreOrder(Tree T){ Visit(T); PreOrder(T->lchild); PreOrder(T->rchild); }
|
非递归
层次遍历
1 2 3 4 5 6 7 8 9 10 11
| Void LevelOrder(Tree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)){ DeQueue(Q,p); visit(p); if(p->lchild!=NULL) EnQueue(Q,p->lchild); if(p->rchild!=NULL) EnQueue(Q,p->rchild); } }
|
图的遍历
BFS
DFS
图的应用
Prim
Kruskal
Dijkstra
拓扑排序
排序
插入排序
1 2 3 4 5 6 7 8 9 10 11
| Void InsertSort(ElemType A[], int n){ for(int i = 2;i < n;i++){ for(int j = i - 1;j >= 0;j--){ if(A[j] < A[i]){ int swap = A[i]; A[i] = A[j]; A[j] = swap; } } } }
|
折半插入排序
1 2 3
| void InsertSort(ElemType A[], int n){ }
|
希尔排序
冒泡排序
1 2 3 4 5 6 7 8 9 10 11 12
| Void BubbleSort(ElemType A[], int n){ int swap = 0; for(int i = 0;i < n;i++){ for(int j = i;j < n;j++){ if(A[i] > A[j]){ swap = A[i]; A[i] = A[j]; A[j] =swap; } } } }
|
快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| Void QuickSort(ElemType A[], int low, int high){ if(low < high){ int pivotpos = Partition(A, low, high); QuickSort(A, low, pivotpos - 1); QuickSort(A, pivotpos, high); } else QuickSort(A, high, low); } int Partition(ElemType A[], int low, int high){ ElemType pivo = A[low]; while(low < high){ while(low < high && A[high] >= pivot) --high; A[low] = A[high]; while(low<high && A[low] <= pivot) ++low; A[high] = A[low]; } }
|
简单选择排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| Void SeletSort(ElemType A[],int n){ int swap = 0; for(int i = 0;i < n;i++){ min = i; for(j = i + 1;j < n;j++){ if(A[j] < A[min]) min = j; } if(min != i){ swap = A[i]; A[i] = A[min]; A[min] = swap; } } }
|
归并排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| Void Merge(ElemType A[], int low, int mid, int high){ int n = high - low + 1; int k; ElemType *B = (ElemType *)malloc((n+1) * sizeof(ElemType)); for(int i = low;i <= high;i++) B[i] = A[i]; for(int i = low, j = mid+1, k = i;i <= mid&&j <= high;k++){ if(B[i]<B[j]) A[k] = B[i++]; else A[k] = B[j++]; } while(i<=mid) A[k++] = B[i++]; while(j<=high) A[k++] = B[j++]; }
void MergeSort(ElemType A[], int low, int high){ if(low < high){ int mid = (low + high) / 2; MergeSort(A,low,mid); MergeSort(A,mid,high); Merge(A,low,mid,high); } else MerSort(A,high,low); }
|
操作系统
semaphore
生产者消费者问题
一组生产者和一组消费者共享初始为空,大小为n的缓冲区
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
| semaphore mutex = 1; semaphore empty = n; semaphore full = 0; producer(){ while(1){ 生产; P(empty); P(mutex); 把数据放进缓冲区; V(mutex); V(full); } }
consumer(){ while(1){ P(full); P(mutex); 拿东西; V(mutex); V(empty); 消费; } }
|
读者写者问题
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
| int count = 0; semaphore mutex = 1; semaphore rw = 1; semaphore w = 1; writer(){ while(1){ P(w); P(rw); writing; V(rw); V(w); } } reader(){ while(1){ P(w); P(mutex); if(count == 0) P(rw); count++; V(mutex); V(w); reading; P(mutex); count--; if(count == 0) V(rw); V(mutex); } }
|
哲学家进餐问题
要同时拿起两个筷子才能吃,注意防止饥饿
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| semaphore chopsticks[5] = {1, 1, 1, 1, 1}; semaphore mutex = 1; Pi(){ do{ P(mutex); P(chopsticks[i]); P(chopsticks[(i+1)%5]); V(mutex); eat; V(chopsticks[i]); V(chopsticks[(i+1)%5]); think; } while(1); }
|
吸烟者问题
轮流抽烟,这个是个同步问题
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 31 32 33 34 35
| int num = 0; semaphore offer1 = 0; semaphore offer2 = 0; semaphore offer3 = 0; process P1(){ while(1){ num++; num = num % 3; if(num == 0) V(offer1); else if(num == 1) V(offer2); else V(offer3); P(finish); } } process P2(){ while(1){ P(offer1); 抽; V(finish); } } process P3(){ while(1){ P(offer2); 抽; V(finish); } } process P4(){ while(1){ P(offer3); 抽; V(finish); } }
|
根据指针p所指节点找双亲节点
1 2 3 4 5 6 7 8
| BTree* getParent(BTree* t, Btree* p){ if(t == null) return NULL; if(t == p) return NULL; if(t->lchild == p || t->rchild == p) return p; BTree* parent = getParent(t-lchild, p); if(parent != NULL) return parent; else return getParent(t-rchild, p); }
|
循环移位
即把后p个移动到前面
$$
思路是这样的,目标是ab变成ba,所以先a^{-1}b,再a^{-1}b^{-1},然后整体交换变成ba
$$
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void Reverse(int R[], int from, int to){ int temp for(int i = from;i<(to-from+1)/2;i++){ temp = R[from + i]; R[from + i] = R[to - i]; R[to - i] = temp; } }
void Converse(int R[], int n, int p){ Reverse(R, 0, p - 1); Reverse(R, p, n - 1); Reverse(R, 0, n - 1); }
|
一定要注意标准化语言
给出将一个正整数字符串转化为对应的整数值的递归描述
递归出口:
- 若子串为空串,返回一个标记表示无法转化
- 若子串长度等于1,则直接返回对应的整数
递归:
- 将子串最末尾的字符转换为整数
- 递归地将除末尾字符的字符的子串转换为整数,并加转换结果乘10加上末尾字符整数返回。