正文

实验报告

exp1

主要学习了一下递归函数的非递归写法

随机生成一棵树写得我很爽

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<stack>
using namespace std;

int FLAG;
struct BT{
    char data;
    BT *lch, *rch;
    int process;//记录当前递归到左子树还是右子树 
};

void Free_BT(BT *rt){
    if(rt == NULL) return;
    Free_BT(rt->lch);
    Free_BT(rt->rch);
    free(rt);
}

BT *Generate_BT(int now, int mind, int maxd){//随机生成一棵二叉树 
    BT *rt = NULL;
    if((rand()%10 > 3)&&(now <= maxd) || (now < mind) ){
        rt = (BT*) malloc(sizeof(BT));
        rt->data = (rand()%26) + 'a'; 
        rt->lch = Generate_BT(now+1, mind, maxd);
        rt->rch = Generate_BT(now+1, mind, maxd);
    }
    return rt;
}

void Print_Manu(){
    printf("1.采用二叉链式存储创建二叉树B1\n");
    printf("2.采用先序序列化显示输出序列，并存储到文件中\n");
    printf("3.从文件中读出序列，并反序列化的递归方法构造二叉树B2\n");
    printf("4.从文件中读出序列，并反序列化的非递归方法构造二叉树B3\n");
    printf("5.使用非递归的方法输出二叉树的中序遍历序列\n");
    printf("6.使用非递归的方法输出二叉树的后序遍历序列\n");
    printf("7.销毁释放二叉树B1,B2,B3\n");
    printf("0.退出\n\n");
}

void Dot_f(FILE *f){
    if(FLAG){
        printf(",");
        fprintf(f, ",");
    }else FLAG = 1;
}

void Dot(){
    if(FLAG){
        printf(",");
    }else FLAG = 1;
}

char Read_node(FILE *f){
    char c;
    do{
        fscanf(f, "%c", &c);
    }while(c == ',');
    return c;
}

void Pre_Order(BT *rt, FILE *f){//先序遍历显示输出序列 
    Dot_f(f);
    if(rt == NULL){
        printf("#");
        fprintf(f, "#");
        return;
    }
    printf("%c", rt->data);
    fprintf(f, "%c", rt->data);

    Pre_Order(rt->lch, f);
    Pre_Order(rt->rch, f);

}

BT *Deserialize_RE(FILE *f){//递归反序列化 
    BT *rt = NULL;
    char c = Read_node(f);
    if(c == '#') return rt;
    rt = (BT*) malloc(sizeof(BT));
    rt->data = c;
    rt->lch = Deserialize_RE(f);
    rt->rch = Deserialize_RE(f);
    return rt;
}

BT *Deserialize_NOT(FILE *f){//非递归反序列化 
    stack<BT*> mystack;
    BT *rt = NULL;
    BT *ret;
    char c = Read_node(f);
    if(c == '#') return rt;
    rt = (BT*) malloc(sizeof(BT));
    rt->process = 1;
    rt->data = c;
    mystack.push(rt);

    while(mystack.empty() == 0){
        BT *t = mystack.top();
        if(t->process == 0){//验证该结点是否存在 
            t->data = Read_node(f);
            if(t->data == '#'){//结点不存在 
                free(t);
                ret = NULL;
                mystack.pop();
                continue;
            }else{//结点存在 
                t->process += 1;
                continue;
            }

        }else if(t->process == 1){//左子树 
            t->lch = (BT*) malloc(sizeof(BT));
            mystack.push(t->lch);
            t->lch->process = 0;
            t->process += 1;
            continue;
        }else if(t->process == 2){//右子树
            t->lch = ret;
            t->rch = (BT*) malloc(sizeof(BT));
            mystack.push(t->rch);
            t->rch->process = 0;
            t->process += 1;
            continue;
        }else{//返回 
            t->rch = ret;
            mystack.pop();
            ret = t;
            continue;
        }
    }
    return rt;
}

void In_Order(BT *rt){
    stack<BT*> mystack;
    BT *p;
    p = rt;
    while(mystack.empty()==0 || p!=NULL){
        while(p != NULL){//循环找到最左边的叶子 
            mystack.push(p);
            p = p->lch;
        }

        Dot();
        printf("#,");

        if(mystack.empty() == 0){//输出该叶子并且回退，然后找到最邻近的右儿子 
            p = mystack.top();
            mystack.pop();

            printf("%c", p->data);
            p = p->rch;
        }
    }
    Dot();
    printf("#");
}

void Post_Order(BT *rt){
    stack<BT*> mystack;
    BT *p;
    if(rt == NULL){
        printf("#");
        return;
    }

    mystack.push(rt);
    rt->process = 0;
    while(mystack.empty() == 0){
        p = mystack.top();
        if(p->process == 0){
            if(p == NULL){
                Dot();
                printf("#");
                mystack.pop();
                continue;
            }else{
                if(p->lch == NULL){
                    Dot();
                    printf("#");
                }else{
                    mystack.push(p->lch);
                    p->lch->process = 0;
                }
                p->process += 1;
                continue;
            }
        }else if(p->process == 1){
            if(p->rch == NULL){
                Dot();
                printf("#");
            }else{
                mystack.push(p->rch);
                p->rch->process = 0;
            }
            p->process += 1;
            continue;
        }else{
            Dot();
            printf("%c", p->data);
            mystack.pop();
            continue;
        }
    }
}

int main(){
    srand(time(NULL));

    BT *b1 = NULL;
    BT *b2 = NULL;
    BT *b3 = NULL;
    int Choice;
    FILE *f;
    Print_Manu();
    while(1){
        printf("Input your choice:");
        scanf("%d", &Choice);
        if(!Choice) break;
        switch(Choice){

            case 1:{
                int mind, maxd;
                printf("Input the minimum depth:");
                scanf("%d", &mind);
                printf("Input the maximum depth:");
                scanf("%d", &maxd);
                if(mind > maxd){
                    printf("Invalid!\n\n");
                    continue;
                }
                Free_BT(b1); //把之前储存的树销毁
                b1 = Generate_BT(1, mind, maxd);
                printf("Binary tree generated.\n\n");
                break;
            }
            case 2:{
                f = fopen("tree.txt", "w");
                printf("serialization_pre_order:");
                FLAG = 0;
                Pre_Order(b1, f);
                fclose(f);
                printf("\n\n");

                break;
            }
            case 3:{
                f = fopen("tree.txt", "r");
                b2 = Deserialize_RE(f);
                fclose(f);
                printf("Succeeded to load in_order tree to b2.\n\n");

                break;
            }

            case 4:{
                f = fopen("tree.txt", "r");
                b3 = Deserialize_NOT(f);
                fclose(f);
                printf("Succeeded to load post_order tree to b3.\n\n");

                break;
            }

            case 5:{
                printf("serialization_in_order:");
                FLAG = 0;
                In_Order(b2);
                printf("\n\n");
                break;
            }

            case 6:{
                printf("serialization_post_order:");
                FLAG = 0;
                Post_Order(b3);
                printf("\n\n");
                break;
            }

            case 7:{
                Free_BT(b1);
                Free_BT(b2);
                Free_BT(b3);
                b1 = b2 = b3 = NULL;
                printf("Succeeded to free b1,b2,b3!\n\n");

                break;
            }
        }   
    }
}

exp2

dijkstra算法以及Floyd算法保存最短路径的方法

dijkstra：在每次加入新点到集合中时，把这些点的father记为上一个点，最后一起逆序输出

Floyd：在进行三重循环的时候，如果找到了最短路（i到j中有一个k结点），

那么就把"path(i)(j)"改为"path(i)(k)"，意味着从i到j的最短路上，i的下一个结点是 i到k的最短路上i的下一个结点

这句话好好理解一下（是一种递归定义，无限递归后，最终path(i)(j)就是i到j最短路上i的下一个节点）

参考资料：https://blog.csdn.net/weixin_39956356/article/details/80620667

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<stack>
#include<iostream>
#define MAX 500
#define INF 1e9+7 
using namespace std;

int map[MAX+1][MAX+1], n;
int shortest[MAX+1][MAX+1];
int dist[MAX+1],path[MAX+1][MAX+1]; //path数组负责记录从u到v，以u为起点的下一个结点的位置 
char name[MAX+1][20];
int fa[MAX+1];//用于在dijkstra里面保存某个结点的前一个结点 

void Print_Manu(){
    printf("1.Import a map.(and store it in the disk)\n");
    printf("2.Calculate the shortest distance from a to b.\n");
    printf("3.Calculate the shortest route of all.(and store it in the disk)\n");
    printf("4.import the map from disk and output the shortest route between two locations.\n");
    printf("0.Quit.\n");
}

void Input_Map(int n){
    printf("input names:\n");
    for(int i = 1; i <= n; i++){
        printf("No.%d:", i);
        scanf("%s", name[i]);
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            map[i][j] = INF;

    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            int t;
            printf("From %s to %s (-1 stands for infinite):", name[i], name[j]);
            scanf("%d",&t);
            if(t == -1) continue;//距离无限远 
            map[i][j] = map[j][i] = t;
        }
        map[i][i] = 0;
    }
}

int Search_Id(char str[]){
    for(int i = 1; i <= n; i++)
        if(strcmp(name[i], str)==0)
            return i;
    return -1;
}

int Dijkstra(int s, int t){
    for(int i = 1; i <= n; i++)
        map[i][i] = 0;//要把所有的结点首先剔除S集合 
    map[s][s] = 1;

    for(int i = 1; i <= n; i++){//将s的邻接点加入dist 
        dist[i] = INF;
        fa[i] = i;
        if(map[s][i] < INF){
            dist[i] = map[s][i];
            fa[i] = s;
        }
    }

     for(int i = 1; i <= n-1; i++){//循环n-1次 
        int MIN = INF, u = 0;
        for(int j = 1; j <= n; j++){//在剩下的点中找一个与S集合邻接的，距离s点最短的点 
            if(map[j][j] == 0 && dist[j]<MIN){
                u = j;
                MIN = dist[j];
            }
        }
        map[u][u] = 1;//加入这个点到S集合中 
        for(int j = 1; j <= n; j++)
            if(map[j][j] == 0)//找到了u点，接下来把与u点邻接的所有边更新一下 
                if(map[u][j] < INF && dist[u] + map[u][j] < dist[j]){
                    dist[j] = dist[u] + map[u][j];
                    fa[j] = u;//把j的父亲设为u 
                }

     }

     return dist[t];//返回距离 
}

void Floyd(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            path[i][j] = j;//初始化path数组 
    memcpy(shortest, map, sizeof(map));
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(shortest[i][j] > shortest[i][k] + shortest[k][j]){
                    shortest[i][j] = shortest[i][k] + shortest[k][j];
                    path[i][j] = path[i][k];//代表i到j的路径上，i的下一个结点为k 
                    //重要 这段代码值得好好理解 
                }
}

int main(){
    Print_Manu();
    int Choice;
    FILE *f;

    do{
        printf("\n\ninput optcode:");
        scanf("%d", &Choice);
        switch(Choice){
            case 1:{
                printf("\ninput n:");
                scanf("%d", &n);
                Input_Map(n);
                printf("Succeeded to import a map!\n\n");
                break;
            }
            case 2:{
                printf("input two names(separate with a space):\n");
                char name1[20], name2[20];
                int s, t;
                scanf("%s%s", name1, name2);
                s = Search_Id(name1);
                t = Search_Id(name2);

                if(s < 0 || t < 0)
                    printf("Invalid name!\n");
                else{
                    int res = Dijkstra(s, t);
                    printf("The shortest distance is %d\n", res);
                    if(res == INF)
                        printf("which means no path.\n");
                    else{
                        printf("path: ");
                        int k = t;
                        stack <int> mystack;
                        while(k != s){
                            mystack.push(k);
                            k = fa[k];
                        }

                        printf("%s ", name[s]);
                        while(mystack.empty() != 1){
                            printf("-> %s ", name[mystack.top()]);
                            mystack.pop();
                        }
                        printf("\n");
                    }
                }

                break;
            }

            case 3:{
                f = fopen("AllPath.dat", "w");
                Floyd();
                printf("All the shortest distance:\n");

                fprintf(f, "%d\n", n);
                for(int i = 1; i <= n; i++)
                    fprintf(f, "%s ", name[i]);
                fprintf(f, "\n");

                for(int i = 1; i <= n; i++)
                    for(int j = i+1; j <= n; j++){
                        printf("from %s to %s: %d\n", name[i], name[j], shortest[i][j]);
                        fprintf(f, "%s %s %d\n", name[i], name[j], shortest[i][j]);
                        if(shortest[i][j] == INF)//没有路径 
                            printf("which means no path.\n");
                        else{
                            printf("path: ");
                            int k = i;
                            while(k != j){
                                printf(" %s ->", name[k]);
                                k = path[k][j];
                            }
                            printf(" %s\n",name[j]);
                        }   
                    }

                //以下是记录两个节点的最短路径与之间的距离 
                for(int i = 1; i <= n; i++){
                    for(int j = 1; j <= n; j++)
                        fprintf(f, "%d ", map[i][j]);
                    fprintf(f, "\n");
                }

                for(int i = 1; i <= n; i++){
                    for(int j = 1; j <= n; j++)
                        fprintf(f, "%d ", path[i][j]);
                    fprintf(f, "\n");
                }

                fclose(f);

                break;
            }

            case 4:{
                char name1[20], name2[20];
                int t;
                f = fopen("AllPath.dat", "r");
                fscanf(f, "%d", &n);
                for(int i = 1; i <= n; i++)
                    fscanf(f, "%s", name[i]);
                for(int i = 1; i <= n*(n-1)/2; i++){
                    fscanf(f, "%s %s %d", name1, name2, &t);
                    shortest[Search_Id(name1)][Search_Id(name2)] = t;
                    shortest[Search_Id(name2)][Search_Id(name1)] = t;
                }

                //以下是读取两个节点的最短路径与之间的距离 
                for(int i = 1; i <= n; i++)
                    for(int j = 1; j <= n; j++)
                        fscanf(f, "%d ", &map[i][j]);

                for(int i = 1; i <= n; i++)
                    for(int j = 1; j <= n; j++)
                        fscanf(f, "%d ", &path[i][j]);

                printf("All the locations:\n");
                for(int i = 1; i <= n; i++)
                    printf("%s ",name[i]);
                printf("\ninput two locations:");
                scanf("%s%s",name1,name2);
                int u = Search_Id(name1);
                int v = Search_Id(name2);
                if(u==-1 || v==-1)
                    printf("Invalid name!\n");
                else printf("from %s to %s is %d\n", name1, name2, shortest[u][v]);

                if(shortest[u][v]==INF)
                    printf("which means no path.\n");
                else{
                    printf("path: ");
                    int k = u;
                    while(k != v){
                        printf(" %s ->(%d)-> ", name[k], map[k][path[k][v]]);
                        k = path[k][v];
                    }
                    printf(" %s\n",name[v]);
                }
                fclose(f);
                break;
            }
        }   
    }while(Choice);
}