计算机组成原理考研笔记

树的遍历

递归

Void PreOrder(Tree T){
    Visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

非递归

层次遍历

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

Void BFS()

DFS

图的应用

Prim

Kruskal

Dijkstra

拓扑排序

排序

插入排序

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;
            }
        }
    }
}

折半插入排序

void InsertSort(ElemType A[], int n){
    
}

希尔排序

冒泡排序

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;
            }
        }
    }
}

快速排序

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];
    }
}

简单选择排序

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;
        }
    }
}

归并排序

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的缓冲区

semaphore mutex = 1; //临界区互斥变量
semaphore empty = n; //空闲缓冲区
semaphore full = 0; //缓冲区初始为0
producer(){
    while(1){
        生产; //生产数据
        P(empty); //获取缓冲区单元
        P(mutex); //进入临界区
        把数据放进缓冲区; //将数据放进缓冲区
        V(mutex); //离开临界区，释放互斥信号量
        V(full); //慢缓冲区数加1
    }
}

consumer(){
    while(1){
        P(full);
        P(mutex);
        拿东西;
        V(mutex);
        V(empty);
        消费;
    }
}

读者写者问题

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);
    }
}

哲学家进餐问题

要同时拿起两个筷子才能吃，注意防止饥饿

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);
}

吸烟者问题

轮流抽烟，这个是个同步问题

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所指节点找双亲节点

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
$$

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. 若子串为空串，返回一个标记表示无法转化
2. 若子串长度等于1，则直接返回对应的整数

递归：

1. 将子串最末尾的字符转换为整数
2. 递归地将除末尾字符的字符的子串转换为整数，并加转换结果乘10加上末尾字符整数返回。