一歩一歩アルゴリズムを書く(図の追加と削除)

原文:
一歩一歩アルゴリズムを書く(図の追加と削除)
【声明:著作権所有、転載歓迎、商業用途に使用しないでください.連絡ポスト:[email protected]】
前述した図のデータ構造、図の作成について、今日は図にエッジを追加および削除する方法について説明します.エッジの追加と削除は複雑ではありませんが、小さな関数に基づいて大きな関数を構築する必要があります.そうしないと、エラーが発生しやすいことを覚えておく必要があります.
一、エッジの作成
エッジの作成は、一般的に次のステップに分けられます.
1)現在の図にノードがあるかどうかを判断し、ない場合はpGraph->headにエッジを追加すればよい
2)現在の図にノードがある場合、start点で始まるノードがあるかどうかを判断し、頂点とエッジが作成されず、図のheadに挿入する
3)現在の有ノードstartでは,endのエッジが既に存在するか否かを判断する.endエッジが存在する場合、エラーが返されます.そうでなければpVectex->neighbourにエッジを追加します
4)追加中の注意点の個数と辺の個数の処理

STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight)

{

	VECTEX* pVectex;

	LINE* pLine;



	if(NULL == pGraph)

		return FALSE;



	if(NULL == pGraph->head){

		pGraph->head = create_new_vectex_for_graph(start, end, weight);

		pGraph->head->number ++;

		pGraph->count ++;

		return TRUE;

	}



	pVectex = find_vectex_in_graph(pGraph->head, start);

	if(NULL == pVectex){

		pVectex = create_new_vectex_for_graph(start, end, weight);

		pVectex->next = pGraph->head;

		pGraph->head = pVectex;

		pGraph->head->number ++;

		pGraph->count ++;

		return TRUE;

	}



	pLine = find_line_in_graph(pVectex->neighbor, end);

	if(NULL != pLine)

		return FALSE;



	pLine = create_new_line(end, weight);

	pLine->next = pVectex->neighbor;

	pVectex->neighbor = pLine;

	pVectex->number ++;

	return TRUE;

}

    
二、エッジの削除
エッジの削除を行う前に、チェーンテーブルのサブノードを処理し、delete小関数を構築する必要があります.これにより、エッジ削除関数で使用できます.

STATUS delete_old_vectex(VECTEX** ppVectex, int start)

{

	VECTEX* pVectex;

	VECTEX* prev;



	if(NULL == ppVectex || NULL == *ppVectex)

		return FALSE;

	

	pVectex = find_vectex_in_graph(*ppVectex, start);

	if(NULL == pVectex)

		return FALSE;



	if(pVectex == *ppVectex){

		*ppVectex = pVectex->next;

		free(pVectex);

		return TRUE;

	}

	

	prev = *ppVectex;

	while(pVectex != prev->next)

		prev = prev->next;



	prev->next = pVectex->next;

	free(pVectex);

	return TRUE;

}



STATUS delete_old_line(LINE** ppLine, int end)

{

	LINE* pLine;

	LINE* prev;



	if(NULL == ppLine || NULL == *ppLine)

		return FALSE;



	pLine = find_line_in_graph(*ppLine, end);

	if(NULL == pLine)

		return FALSE;

	

	if(pLine == *ppLine){

		*ppLine = pLine->next;

		free(pLine);

		return TRUE;

	}

	

	prev = *ppLine;

	while(pLine != prev->next)

		prev = prev->next;

	

	prev->next = pLine->next;

	free(pLine);

	return TRUE;

}

    
一般に、エッジの削除とエッジの追加は可逆的であり、プロセスは次のようになります.
1)図中にノードが存在するか否かを判断し、存在しない場合はエラーを返す
2)図中のノードstartが存在するか否かを判断し、存在しない場合はエラーを返す
3)ノードstartにendエッジが存在するか否かを判断し,存在しない場合はエラーを返す.
4)対応するエッジを削除
5)当該ノードの辺計数numberが0であるか否かを判断し、0であればノードの削除を継続する
6)削除中の注意エッジと頂点の個数処理

STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight)

{

	VECTEX* pVectex;

	LINE* pLine;

	STATUS result;



	if(NULL == pGraph || NULL == pGraph->head)

		return FALSE;



	pVectex = find_vectex_in_graph(pGraph->head, start);

	if(NULL == pVectex)

		return FALSE;



	pLine = find_line_in_graph(pVectex->neighbor, end);

	if(NULL != pLine)

		return FALSE;



	result = delete_old_line(&pVectex->neighbor, end);

	assert(TRUE == result);

	pVectex->number --;



	if(0 == pVectex->number)

		result = delete_old_vectex(&pGraph->head, start);



	assert(TRUE == result);

	pGraph->count --;

	return TRUE;

}

注意事項:
(1)小さな関数を書くことに注意して、更に複雑な機能はすべて無数の小さい機能が構築したので、関数は50行を超えないほうがいいです
(2)従来のルール、コードは必ずテストする