下载频道  >  u014535119的资源
  • 数据结构最大堆代码

    最大堆数据结构实现c++版,实现排序功能。

    2014-04-20
    4
  • 数据结构管道铺设课程设计含画图

    弗洛伊德算法找出超市最佳选址位置 #include<iostream> #include <iomanip> using namespace std; const int maxv=20; #include<time.h> #include <math.h> #include<conio.h> #include <stdlib.h> #include <graphics.h> struct point { char name[10]; int id; int x; int y; //int dst[5]; }; struct node { char src[10]; char dst[10]; int cost; }; /////最小生成树 struct mintree//结构体记录最小生成树的相关信息 { int begin,end;//起点 终点 int length;//边的权值 }; const int maxweight=9999; class Graphm//图的矩阵表式 { public: int map[maxv][maxv]; //某点到某点两点间的的距离 int mark[maxv]; //加入进来的点的集合 point Vert[maxv];//顶点信息 int Edge[maxv][maxv];//存放边的信息 int numV;//顶点数 int numE;//边数 int path[maxv][maxv];//每对顶点之间路劲 int dist[maxv][maxv];//c每对顶点之间的路径 void shortpath(int n); mintree tree[maxv]; Graphm(); char* findbyid(int i); int findbyname(char m[]); void CreatG();//创建无向图 void print();//矩阵显示图的信息 void draw(); void Prim(); node Node[maxv]; int edgenumE; int minx(int x,int y); }; int Graphm::minx(int x,int y) { if(x<y) return x; else return y; } Graphm::Graphm()//矩阵初始化 { for(int i=0;i<maxv;i++) for(int j=0;j<maxv;j++) { if(i==j) Edge[i][j]=0; else Edge[i][j]=maxweight;} numV=0; numE=0; } int Graphm::findbyname(char m[]) { int j; for(j=0;j<numV;j++) { if(strcmp(Vert[j].name,m)==0) return Vert[j].id; } } char* Graphm::findbyid(int i) { int j; for(j=0;j<numV;j++) { if(Vert[j].id==i) return Vert[j].name; } } void Graphm::CreatG()//创建无向图 { FILE *fp;//定义文件流指针,用于打开读取的文件 int i,k; if((fp=fopen("data.txt","rb")) == NULL ) { /* 打开文件 */ printf("Cannot open file !"); return ; }//只读方式打开文件text.txt fscanf(fp,"%d",&numV);//读入点数 fscanf(fp,"%d",&numE); cout<<numV<<endl; cout<<numE<<endl; char q,z; for(i=0;i<numV;i++)//从文件中读取信息 显示到屏幕 { fscanf(fp,"%s",&Vert[i].name);//读取d顶点信息 Vert[i].id=i+1; cout<<Vert[i].name<<endl; } for(k=0;k<numE;k++)//从文件中读取信息保存到矩阵中 { int dis; char i[10],j[10]; fscanf(fp,"%s""%s""%d",i,j,&dis); strcpy(Node[k].src,i); strcpy(Node[k].dst,j); Node[k].cost=dis; int n=findbyname(i); int m=findbyname(j); cout<<i<<" "<<j<<" "<<dis<<endl; Edge[n-1][m-1]=dis; Edge[m-1][n-1]=dis; } printf("\n"); fclose(fp);//关闭文件text.txt,有打开就要有关闭 } void Graphm::print()//矩阵显示图 { int i; cout<<endl; int j; cout<<"图的矩阵输出显示"<<endl; cout<<" "; for(i = 0; i<numV;i++)cout<<setw(5)<<findbyid(i+1)<<" ";cout<<endl; for( i = 0; i <numV; i++){cout<<findbyid(i+1) <<" ";//初始化为0 cout<<j; for ( j=0; j <numV; j++) cout<<setw(5)<< Edge[i][j]<<" ";if(j==numV)cout<<endl; } } void Graphm::Prim()//计算最小生成树 { cout<<"最小生成树"<<endl; cout<<"Prim 算法"<<endl; cout<<"begin end length"<<endl; int n=numV;int m; mintree e; for(int i=1;i<n;i++) { tree[i-1].begin=1; tree[i-1].end=i+1; tree[i-1].length=Edge[0][i]; } for(int k=0;k<n-1;k++) { int min=maxweight; for(int j=k;j<n-1;j++) if(tree[j].length<min){min=tree[j].length;m=j;} e=tree[m];tree[m]=tree[k];tree[k]=e; int v=tree[k].end; for(j=k+1;j<n-1;j++) { int d=Edge[v-1][tree[j].end-1]; if(d<tree[j].length){tree[j].length=d;tree[j].begin=v;} } }//k edgenumE=n-1; for(int jj=0;jj<n-1;jj++) cout<<endl<<setw(3)<<findbyid(tree[jj].begin)<<" "<<setw(3)<<findbyid(tree[jj].end)<<" "<<setw(3)<<tree[jj].length; //return tree; cout<<endl<<endl; } void Graphm::draw() { initgraph(1024, 680);//---------------------------a图形界面 rectangle(20,20,650,600); outtextxy(40,100,"根据文件中信息构造无向图"); outtextxy(40,150,"红色线条标注最小生成树路径"); Vert[0].x=400;Vert[0].y=50; Vert[1].x=200;Vert[1].y=200; Vert[2].x=400;Vert[2].y=400; Vert[3].x=600;Vert[3].y=200; for(int i=0;i<numV;i++) { circle(Vert[i].x,Vert[i].y,30);outtextxy(Vert[i].x,Vert[i].y,Vert[i].name); } int c,d; for(int k=0;k<numE;k++) { line(Vert[findbyname(Node[k].src)-1].x,Vert[findbyname(Node[k].src)-1].y,Vert[findbyname(Node[k].dst)-1].x,Vert[findbyname(Node[k].dst)-1].y); char cst[10]; sprintf(cst,"%d",Node[k].cost); //sprintf(cst,) c=minx(Vert[findbyname(Node[k].src)-1].x,Vert[findbyname(Node[k].dst)-1].x); d=minx(Vert[findbyname(Node[k].src)-1].y,Vert[findbyname(Node[k].dst)-1].y); outtextxy(abs(Vert[findbyname(Node[k].src)-1].x-Vert[findbyname(Node[k].dst)-1].x)/2+c,abs(Vert[findbyname(Node[k].src)-1].y-Vert[findbyname(Node[k].dst)-1].y)/2+d,cst); } int begin,end,cost; Sleep(1000); setlinecolor(RED); for(int n=edgenumE-1;n>=0;n--) { begin=tree[n].begin; end=tree[n].end; cost=tree[n].length; Sleep(800); line(Vert[begin-1].x,Vert[begin-1].y,Vert[end-1].x,Vert[end-1].y); } settextcolor(GREEN); outtextxy(650,150,"WRITTEN BY YUN HE!"); getch(); closegraph(); } void main() { Graphm g1; int edgcount; g1.CreatG();//顶点数目 边数 g1.print(); g1.Prim(); g1.draw(); system("pause"); }

    2014-04-03
    6
img
u014535119

关注 私信