第三次数据结构实验报告(2)

[1][i]; //初始化 prevex[i]=1; //顶点未加入到最小生成树中 } lowcost[1]=0; //标志顶点1加入 U 集合 for(i=2;i<=n;i++) //形成 n-1条边的生成树 { min=inf; k=0; for(j=2;j<=n;j++) //寻找满足边的一个顶点在 U,另一个顶点在 V 的最小边 if((lowcost[j]<min)&&(lowcost[j]!=0)) { min=lowcost[j]; k=j; } printf("(%d,%d)%d\t",prevex[k]-1,k-1,min); lowcost[k]=0; //顶点 k 加入 U for(j=2;j<=n;j++) //修改由顶点 k 到其他顶点边的权值 if(g[k][j]<lowcost[j]) { lowcost[j]=g[k][j]; prevex[j]=k; } printf("\n"); } return 0; }

中国矿业大学数据结构课程实验报告

int acrvisited[100];//kruscal 弧标记数组 int find(int acrvisited[],int f) { while(acrvisited[f]>0) f=acrvisited[f]; return f; } void kruscal_arc(MGraph_L G,algraph gra) { edg edgs[20]; int i,j,k=0; for(i=0;i!=G.vexnum;++i) for(j=i;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=10000) { edgs[k].pre=i; edgs[k].bak=j; edgs[k].weight=G.arcs[i][j].adj; ++k; } } int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;++i) acrvisited[i]=0; for(j=0;j!=G.arcnum;++j) { m=10000; for(i=0;i!=G.arcnum;++i) { if(edgs[i].weight<m) { m=edgs[i].weight; x=edgs[i].pre; y=edgs[i].bak; n=i; } } // cout<<x<<y<<m; // cout<<endl; buf=find(acrvisited,x); edf=find(acrvisited,y); // cout<<buf<<" "<<edf<<endl;

中国矿业大学数据结构课程实验报告

edgs[n].weight=10000; if(buf!=edf) { acrvisited[buf]=edf; cout<<"("<<x<<","<<y<<")"<<m; cout<<endl; } } } void main() { algraph gra; MGraph_L G; int i,d,g[20][20]; char a='a'; d=creatMGraph_L(G); creatadj(gra,G); vnode v; cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl <<" 最小生成树不存在,则显示为非法值。"<<endl<<endl; cout<<"…………………菜单……………………"<<endl<<endl; cout<<"0、显示该图的邻接矩阵……………………"<<endl; cout<<"1、显示该图的邻接表……………………"<<endl; cout<<"2、深度优先遍历…………………………"<<endl; cout<<"3、广度优先遍历…………………………"<<endl; cout<<"4、最小生成树 PRIM 算法…………………"<<endl; cout<<"5、最小生成树 KRUSCAL 算法………………"<<endl; cout<<"6、该图的连通分量………………………"<<endl<<endl; int s; char y='y'; while(y='y') { cout<<"请选择菜单："<<endl; cin>>s; switch(s) { case 0: cout<<"邻接矩阵显示如下："<<endl; ljjzprint(G); break; case 1: cout<<"邻接表显示如下："<<endl; adjprint(gra);

中国矿业大学数据结构课程实验报告

break; case 2: cout<<"广度优先遍历："; bfstra(gra); cout<<endl; break; case 3: for(i=0;i!=gra.vexnum;++i) { visited[i]=0; } cout<<"深度优先遍历："; dfstra(gra); cout<<endl; break; case 4: for(i=0;i!=G.vexnum;++i) for(int j=0;j!=G.vexnum;++j) g[i+1][j+1]=G.arcs[i][j].adj; cout<<"prim:"<<endl; prim(g,d); break; case 5: cout<<"kruscal:"<<endl; kruscal_arc(G,gra); break; case 6: cout<<"连通分量:"; bfstra_fen(gra); break; } cout<<endl<<"是否继续？y/n:"; cin>>y; if(y=='n') break; } }

中国矿业大学数据结构课程实验报告

加强题 1、试写出中序遍历二叉树的递归和非递归程

序并调试。 #include<stdio.h> #include<stdlib.h> #include<iostream.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef struct BiTNode{ char data; struct BiTNode *lchild, *rchild;// 左、右孩子指针 }BiTNode, *BiTree; int CreateBiTree(BiTree &T){ // 按中序输入二叉树中结点的值(一个字符),#字符表示空树 // 构造二叉链表表示的二叉树 T。 char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); CreateBiTree(T->lchild); T->data=ch;// 生成根结点 CreateBiTree(T->rchild); } return 0; }

中国矿业大学数据结构课程实验报告

void InTraverse(BiTree &T) //中序遍历 { if(T){ //非空二叉树 InTraverse(T->lchild); //递归遍历左子树 printf("%c",T->data); //访问 D InTraverse(T->rchild); //递归遍历右子树 } } int main(){ BiTree T; CreateBiTree(T); InTraverse(T); return 0; } 2、写出中序线索二叉树的中序遍历程序并调试。 提高题 1、实现霍夫曼编、解码 (1)输入一系列字符及其出现频率并以此构造霍夫曼树进行编码并输出码表，另输 入一段文字，对其进行霍夫曼编码。例：CASTCASTSATATATASA (2) 1 中已构成的霍夫曼树的基础上， 在 输入一段 01 编码， 要求输出其解码的原文。 例：111011001110110011001001001001100 2、校园导游咨询。要求： (1)设计一个校园的平面图，所含景点不少于 8 个。以图中的顶点表示校内各景点， 存放景点名称、代号、简介等信息。以边表示路径，存放路径长度等相关信息。 (2)为来访客人图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最 短路。实验感悟： 数据结构很有用，但是也很难把握，这次试验我尝试着完全自己编程序，第一题没有参考他 人的程序，自己编出的程序总是问题百出，我花了一个下午的时间才调试好，真心不容易。 考虑到时间紧任务重， 后面两道题参考了网上的程序， 其中第二道基础题网上的程序比较复 杂，我也是看了很久才弄明白，其实数据结构是应该好好研究的，这门课的内容在以后的编 程中经常会用到，数据结构的实验让我明白了自己的差距，给我指明了努力的方向。

教师评价

优

良

中

及格

不及格

教师签名

日期