第12週目プロジェクト1-図基本アルゴリズムライブラリ
7611 ワード
/* * Copyright(c)2015、煙台大学コンピュータと制御工学学院 *All rights reserved. * ファイル名:プロジェクト1.cpp * 作る李竹雅
*完成日:2015年11月
*バージョン番号:v 1.0 * 問題の説明: 図の隣接マトリクスと隣接テーブル記憶構造を定義し,その基本演算を実現し,テストを完了する.nbsp;
要求: 1、ヘッダファイルgraph.hでは、関連するデータ構造を定義し、基本演算を完了するための関数を宣言する.基本演算に対応する関数は次のとおりです.
void ArrayToMat(int *Arr, int n, MGraph &g);//通常の配列で図の隣接行列を構築する void ArrayToList(int *Arr, int n, ALGraph *&);//普通の配列で図の隣接表を構築する void MatToList(MGraph g,ALGraph *&G);//隣接マトリクスgを隣接テーブルG に変換する; void ListToMat(ALGraph *G,MGraph &g);//隣接テーブルGを隣接マトリクスg に変換する; void DispMat(MGraph g);//出力隣接マトリクスg void DispAdj(ALGraph *G);//出力隣接テーブルG 2、graph.cppではこれらの関数 を実現する.
3、mainを使います.cppのmain関数でテストを完了します. * 入力説明:なし *プログラム出力:テストデータ */
1.graph.hヘッダファイルコード:
2.graph.cppファイルコード:
3,.main.cppファイルコード:
実行結果:
知識ポイントのまとめ:
グラフィックスライブラリの定義の問題.
*完成日:2015年11月
*バージョン番号:v 1.0 * 問題の説明: 図の隣接マトリクスと隣接テーブル記憶構造を定義し,その基本演算を実現し,テストを完了する.nbsp;
要求: 1、ヘッダファイルgraph.hでは、関連するデータ構造を定義し、基本演算を完了するための関数を宣言する.基本演算に対応する関数は次のとおりです.
void ArrayToMat(int *Arr, int n, MGraph &g);//通常の配列で図の隣接行列を構築する void ArrayToList(int *Arr, int n, ALGraph *&);//普通の配列で図の隣接表を構築する void MatToList(MGraph g,ALGraph *&G);//隣接マトリクスgを隣接テーブルG に変換する; void ListToMat(ALGraph *G,MGraph &g);//隣接テーブルGを隣接マトリクスg に変換する; void DispMat(MGraph g);//出力隣接マトリクスg void DispAdj(ALGraph *G);//出力隣接テーブルG 2、graph.cppではこれらの関数 を実現する.
3、mainを使います.cppのmain関数でテストを完了します. * 入力説明:なし *プログラム出力:テストデータ */
1.graph.hヘッダファイルコード:
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#include <stdio.h>
#include <malloc.h>
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ,
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ,
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
#endif // GRAPH_H_INCLUDED
2.graph.cppファイルコード:
//
#include "graph.h"
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g)
{
int i,j,count=0; //count , 0
g.n=n;
for (i=0; i<g.n; i++)
for (j=0; j<g.n; j++)
{
g.edges[i][j]=Arr[i*n+j]; // Arr n×n ,Arr[i*n+j] Arr[i][j],
if(g.edges[i][j]!=0)
count++;
}
g.e=count;
}
void ArrayToList(int *Arr, int n, ALGraph *&G)
{
int i,j,count=0; //count , 0
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->n=n;
for (i=0; i<n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<n; i++) //
for (j=n-1; j>=0; j--)
if (Arr[i*n+j]!=0) // , Arr n×n ,Arr[i*n+j] Arr[i][j]
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=Arr[i*n+j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->e=count;
}
void MatToList(MGraph g, ALGraph *&G)
// g G
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0; i<g.n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<g.n; i++) //
for (j=g.n-1; j>=0; j--)
if (g.edges[i][j]!=0) //
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
// G g
{
int i,j;
ArcNode *p;
for (i=0; i<g.n; i++) //
for (j=0; j<g.n; j++)
g.edges[i][j]=0;
for (i=0; i<G->n; i++) // ,
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
g.n=G->n;
g.e=G->e;
}
void DispMat(MGraph g)
// g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("
");
}
}
void DispAdj(ALGraph *G)
// G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("-->%d/%d ",p->adjvex,p->info);
p=p->nextarc;
}
printf("
");
}
}
3,.main.cppファイルコード:
#include "graph.h"
int main()
{
MGraph g1,g2;
ALGraph *G1,*G2;
int A[6][6]=
{
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}
};
ArrayToMat(A[0], 6, g1); // , A[0], ,
printf(" g1 :
");
DispMat(g1);
ArrayToList(A[0], 6, G1);
printf(" G1 :
");
DispAdj(G1);
MatToList(g1,G2);
printf(" g1 G2:
");
DispAdj(G2);
ListToMat(G1,g2);
printf(" G1 g2:
");
DispMat(g2);
printf("
");
return 0;
}
実行結果:
知識ポイントのまとめ:
グラフィックスライブラリの定義の問題.