データ構造--図の深さ優先検索、広さ優先検索、木の辺集合を生成する.

一、 実験の目的
ツリーと図は2種類の応用が極めて広いデータ構造であり、この課程の重点でもある.それらの特徴は非線形性にある.まばらな行列の十字チェーンの記憶構造も図の記憶構造である.この章の実験はデータ構造と操作のプログラム設計の観点を引き続き強調していますが、このような構造の非線形性の特徴によって、操作は遍歴操作にさらに集中します.論理的(または記号形式の)構造を巡回して、アクセス動作は任意の動作です.今回の実験は学生に各種の記憶構造の特徴をよく知ってもらいたいと思います.また、どのように図構造を使って具体的な問題を解決しますか?
 
二、 実験の内容
1) 巡回したプレゼンテーション
[問題説明]
多くの図上で動作するアルゴリズムは図のエルゴード動作に基づいている.プログラムを試してみて、図なしの巡回操作を実証します.
[基本要求]
隣接テーブルを格納構造とし、接続無方向図の深さ優先と広さ優先エルゴードを実現する.ユーザによって指定された接合点を起点として、それぞれの巡回されたノードアクセスシーケンスと、対応する生成されたツリーのエッジセットが出力される.
[試験データ]
学生がソフトウェアエンジニアリングのテスト技術に基づいて自分で確定します.単一のノードのような境界データをテストします.
[実装ヒント]
図の結点が30個を超えないようにします.各結点は一つの番号で表します.図のすべてを入力しながら一つの図を入力することによって、一つの辺は一つの数ペアで、側の入力順序に対してある種類の制限ができます.なお、木を生成する端は、端があり、端が逆さまにならないようにしてください.
 
三、 実験環境
Visual Studio 2013
Windows 10

#include
#include

int visited[20];

typedef struct ArcNode{
	int adjvex;  //     
	struct ArcNode * nextarc;  //             
};

typedef struct VNode{ //     
	int data;  //     
	ArcNode *firstarc;   //                
}VNode, AdjList[20];

typedef struct{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

typedef struct{
	int start;
	int end;
}Arc;

Arc BSet[20];    //             
Arc DSet[20];   //             
int b = 0;  //         index
int d = 0;  //         index

void createGraph(ALGraph &G){
	printf("          。
");
	scanf_s("%d", &G.vexnum);
	printf("         。
");
	scanf_s("%d", &G.arcnum);
	printf("        。
");
	for (int i = 0; iadjvex = a;
		s->nextarc = G.vertices[b].firstarc;
		G.vertices[b].firstarc = s;
		s = (ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex = b;
		s->nextarc = G.vertices[a].firstarc;
		G.vertices[a].firstarc = s;
	}
	printf("       。
");
}

//      
void DFS(ALGraph G, int i){
	// i       
	printf("%d   ", i);
	ArcNode *p,*q;
	visited[i] = 1; //0  ，1  
	p = G.vertices[i].firstarc;
	while (p){
		if (!visited[p->adjvex]){
			DSet[d].start = i;
			DSet[d].end = p->adjvex;
			d++;
			DFS(G, p->adjvex);
		}
		p = p->nextarc;
	}
}

void DFSTraverse(ALGraph G){
	int j, i;
	printf("                 。
");
	scanf_s("%d", &j);
	printf("           ：");
//	DSet[d] = j;
	for (i = 0; inext = NULL;  //         next     null 
	//	printf("success in initializating.
");
	return 0;
}

int enQue(LinkQue &Q, int e){
	QNode *p = (QNode*)malloc(sizeof(QNode));
	if (!p) return -1;
	p->data = e;
	p->next = NULL;  //   null
	Q.rear->next = p;
	Q.rear = p;
	return 0;
}

int deQue(LinkQue &Q, int &e){
	if (Q.front == Q.rear){
		printf("The queue is empty now.
");
		return -1;
	}
	QNode* p = Q.front->next;  //Q.front                 
	e = p->data;
	//printf("The data is %d
",e);
	Q.front->next = p->next;
	if (Q.rear == p) Q.rear = Q.front; //               rear             rear       
	free(p);
	return 0;
}

void BFS(ALGraph G, int i){
	printf("%d  ", i);
	visited[i] = 1;
	LinkQue Q;
	int e;
	Init(Q);
	enQue(Q, i);
	while (Q.front != Q.rear){
		deQue(Q, i);
		ArcNode *p = G.vertices[i].firstarc;
		while (p){
			if (!visited[p->adjvex]){
				printf("%d  ", p->adjvex);
				visited[p->adjvex] = 1;
				enQue(Q, p->adjvex);
				BSet[b].start = i;
				BSet[b].end = p->adjvex;
				b++;
			}
			p = p->nextarc;
		}
	}
}

void BFSTraverse(ALGraph G){
	int i, j;
	printf("                 。
");
	scanf_s("%d", &j);
	printf("           ：
");
	for (i = 0; i

デバッグプロセス
1. プログラムはいつも最後にフラッシュバックが現れて、一つのgetarを加えました.だめです.引き続き一つのgetarを追加します.成功しました.
2. 最初の深さ優先検索では毎回最初の巡回点が出力されません.その原因は初めてDFSに入る時にvisitedはもう1に置かれましたが、自分の出力ミスはif構造に書いてあります.これは最初のエルゴードポイントが出力されなくなり、最後に出力文をDFSに入る位置に置いて運行に成功しました.
3. ツリーを生成するサイドセットを保存する際の最初の考えは、DFS関数に入る時にスタート地点を順次保存し、DFS関数を終了する時に終点を順次保存し、一つのグローバルのindexを使って制御しますが、メモリアクセス衝突のエラーが発生したため、ポリシーを変更し、スタートはi、終点はp-advexです.
4. 最初は、遍歴の始点を指定することができませんでしたので、trverse関数では、前後の順序があるforサイクルを二つ並べて実行します.
5. 最初は問題を間違えて、アルファベットのノードを入力して、その後番号に対応して、小さなエラーが出ました.問題によって頂点を直接番号で表すべきです.
実行結果
 
テストデータは8つのノードで、10つの辺です.
頂点は0,1,2,3,4,5,6,7です.
辺は(0,1)(0,2)(1,3)(1,4)(2,5)(2,6)(3,7)(4,7)(5,7)(6,7)