0%

期末大作业_二叉树的存储与图的最短路径

正文

实验报告

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