複雑なデータ構造と最短のパスを求めるアルゴリズム
6853 ワード
一、複雑なデータ構造(木)
1.階層関係構造:(ツリー)
(1)ツリーの定義:nノードの集合、集合の中にルートノードと呼ばれる特殊なノードがある.
① 一本の木の中には、一つのノードだけが前駆者ではなく、このノードが木のルートノードである.
② ルートノードを除いて、残りの各点は一つの前駆者だけあります.
③ 各ノードは、任意の複数の後続を有してもよい.
(2).関連用語:
① 親ノード、子ノード、兄弟ノード
② ノードの度、数の度
③ リーフノードとブランチノード
④ ノードの層数
⑤ 木の深さ
⑥ 秩序樹と無秩序樹、森
2.二叉樹と木の違い
(1)ツリー中のノードの最大度ツリーは制限されず、二叉ツリーノードの最大度は2である.
(2)木のノードには左右の区別がないが、二叉のツリーノードには左右の区別がある.
3.特別なタイプの二叉樹:
満二叉樹、完全二叉樹
(1)二叉の木は完全に二叉の木に違いないが、完全に二叉の木は必ずしも二叉の木ではない.
4.二叉樹の保存
(1)順序格納:
① 順序格納データ定義:
(2).チェーンストア:
1つのノードは、ノード要素と、左右のツリーをそれぞれ指す2つのポインタから構成されてもよい(2つのツリー・チェーン構造).
二叉チェーン構造:
a) 二叉木チェーン構造を定義します.
c)ノードをダブルツリーに追加する:
d)二叉樹の左右の木を取得する
e) 二叉の木の状態を取得します.二叉の木が空かどうか、二叉の木の深さを求めます.
f) 二叉ツリーでの検索:二叉ツリーでデータを検索するときは、各ノードのデータを逐一比較して、二叉ツリーの各ノードを巡回して、その後、ノードのポインタを参照する必要があります.
g)二叉樹をクリア:
(1).まず、ルートノードを訪問し、左サブツリーを順に遍歴し、最後に順に右サブツリーを巡回します.
(3)左のサブツリーを後から順に巡回し、その後右のサブツリーを巡回して、最後にルートノードを訪問します.
7.スレッド二叉樹
(1)スレッド二叉ツリーの表示:各ノードの空きのためのポインタと右ポインタをそれぞれポインタノードの前駆と後続に使用すると、スレッド二叉ツリーが得られます.
(2).分類:まず手がかりの二叉樹、中順スレッドの二叉樹、後続スレッドの二叉樹
(3)スレッドマークエリアを追加した後、二叉チェーンの構造は以下の通りです.
(5)操作スレッドの二叉ツリー:
a)後続ノードを検索する:
i. 親ノードPの右サブツリーが空であれば、p−＞rightは右スレッドであり、直接pの中間シーケンスを指して後続する.
ii. 親ノードpの右サブツリーが空でない場合、pの中間シーケンスの後続は、その右サブツリーの中で最初に巡回されたノードである必要がある.
b)前駆ノードを検索する:
i.親ノードpの左サブツリーが空であれば、p−leftは左スレッドであり、直接にpの中序前駆ノードを指す.
ii.親ノードpの左サブツリーが空でない場合は、pの左サブツリーから、そのサブツリーの右ポインタチェーンに沿って下を検索し、右サブツリーのないノードがあるまでは、このおよびエッはpの中間順にノードを前駆する.
c) スレッドを巡回しました.二叉の木はスレッド化されていますので、巡回中に後続のポインタによって素早く完成できます.再帰的な呼び出しを使わずに完了します.
8.最適な二叉樹(ハフマンツリー)
(1).決定権値を有するリーフツリーのセットについて、最小のリーフパス長を有する2つのツリーを意味する.
(2).基本概念:ノードの権利、経路、経路の長さ、ツリーの経路長、ノードの帯域権経路長、ツリーの帯域権経路長(WPL)
(3)ハフマンツリーを作成する手順:
a)まずN個の重みのノードに基づいてN本の二叉樹を構成し、各ノードは二叉樹であり、その権利値はルートノードに保持され、ここでは左右のサブツリーはすべて空である.
b) このN本の二叉の木の中から二つのルートノードの権利値が一番小さい木を見つけ、二つの木を左右のツリーとして新しい二叉の木を作り、左右のサブツリーのルートノードの権利値を加算して、新しい二叉のツリーノードの権利値とします.
c)前のステップで見つけた2つの重みの最小値の2つのツリーを次の検索から除外し、新たに作成された2つのツリーを検索範囲に追加します.
d)検索範囲が1本の木だけになるまで、ステップbとcを繰り返す.
(4)ハフマン符号:まずメモリに連続領域を割り当て、ハフマンの二叉樹を保存するために使用され、この部分のメモリを一つの仮想配列として使用し、その後、配列の下標記を通じて異なる二叉樹ノードにアクセスすることができる.
(5)ハフマンコードのいくつかの操作:
a)ハーフマンツリーを作成する
b)ハフマンツリーの各文字によるハフマンの符号化
c)ハフマンコードに基づいて文字列を符号化し、符号化された文字列を得る.
d)サブ文字列からバイナリコードを一つずつ取得し、ハフマンツリーで検索し、復号作業を完了します.
二、ネット関係:図(Graph)
要素間の関係は任意で、各データ要素は他のデータ要素と関連しています.
1.図の保存:
(1)隣接行列:(2つの配列で)
a)最初の配列:n個の要素を持つ1次元配列で、図中の頂点の情報を保存します.
b)2番目の配列:n＊nの2次元配列(行列)は、頂点間の隣接関係を保存するために使用されます.
(2)隣接表:隣接マトリクスを改良した接続構造であり、その特徴値は隣接マトリックス中の非ゼロ要素を考慮して隣接マトリクス保存図よりも省スペースである.隣接表は、図中の各頂点に対して隣接関係の単一チェーンテーブルを作成し、隣接行列の各ラインは単一チェーンテーブルに対応して、各シングルチェーンテーブルの表ヘッドポインタを一つの配列に保存し、任意の頂点チェーンテーブルにランダムにアクセスすることができる.
2.作成図:
(1)隣接マトリックスを用いる:
a)隣接マトリックスデータ構造の作成
b)隣接マトリックスの作成
c)隣接マトリックスの内容を出力します.
(2)隣接表で図を保存する
a)隣接テーブルデータ構造を定義する(頂点を定義するデータ構造)
b)図のデータ構造を定義する
c)隣接図の作成
d)出力隣接図
3.図の巡回:
広さ優先法と深さ優先法
(1) 広さ優先遍歴:広さ優先遍歴は再帰的過程ではない.巡回中に、まず訪問された頂点の近くの接点も先にアクセスされ、アルゴリズムの実現には訪問された頂点を一回記憶するためのキューを設定する必要があります.
(2)深さ優先エルゴード:深さ優先エルゴードは再帰的プロセスである.
a)isTrav配列からアクセスされていない頂点Viを選択し、アクセス済みとしてマークする.
b)次いで、Viのうちの一つの未アクセスの隣接点から深さ優先巡回を行う.
c)図中のすべての経路と共通の頂点がアクセスされるまで、ステップbを繰り返す.
d)aからcまでの手順を繰り返します.すべての頂点がアクセスされるまで.
4.最小ツリーを生成する:
N個の頂点を有する接続図については、N−1個のエッジが生成される.1つの権利値付きの連結図については、ツリーが異なるため、ツリー内の各辺の総和も異なり、権利値が一番小さい生成ツリーを図の最小生成ツリーといいます.
(1)ツリーを生成するための一般的なアルゴリズムprmを構築する:primアルゴリズムを実現するには、サブアレイが必要である.
a)配列1:tmpvertexは、対応する位置に隣接する頂点情報を保存する.
b)配列2:weightは、前の配列に対応する隣接辺の値を保存します.
5.最短経路(Dijkstraアルゴリズム)
頂点から別の頂点までの最短ルートを求めます.
実装するプロセスは、3つの配列が必要であり、(セットUは頂点セットであり、求められた最短経路の頂点をセットUに追加する)
一つ目は、頂点セットを保存するためのもので、diagramの重みが1の場合、対応する頂点をUセットに追加します.
第二は、一時的な計算を保存します.
第三:対応する辺があるかどうかを示す.
実装コードは以下の通りです.
1.階層関係構造:(ツリー)
(1)ツリーの定義:nノードの集合、集合の中にルートノードと呼ばれる特殊なノードがある.
① 一本の木の中には、一つのノードだけが前駆者ではなく、このノードが木のルートノードである.
② ルートノードを除いて、残りの各点は一つの前駆者だけあります.
③ 各ノードは、任意の複数の後続を有してもよい.
(2).関連用語:
① 親ノード、子ノード、兄弟ノード
② ノードの度、数の度
③ リーフノードとブランチノード
④ ノードの層数
⑤ 木の深さ
⑥ 秩序樹と無秩序樹、森
2.二叉樹と木の違い
(1)ツリー中のノードの最大度ツリーは制限されず、二叉ツリーノードの最大度は2である.
(2)木のノードには左右の区別がないが、二叉のツリーノードには左右の区別がある.
3.特別なタイプの二叉樹:
満二叉樹、完全二叉樹
(1)二叉の木は完全に二叉の木に違いないが、完全に二叉の木は必ずしも二叉の木ではない.
4.二叉樹の保存
(1)順序格納:
① 順序格納データ定義:
#define MAXSIZE 100
typedef int PADA;
typedef DATA SeqBinTinree[MAXSIZE];
SeqBinTree SBT;(2).チェーンストア:
1つのノードは、ノード要素と、左右のツリーをそれぞれ指す2つのポインタから構成されてもよい(2つのツリー・チェーン構造).
二叉チェーン構造:
typedef structChainTree //
{
DATA data; //
struct ChainTree *left; //
struct ChainTree *right; //
}ChainBinTree;a) 二叉木チェーン構造を定義します.
typedef structChainTree //
{
DATA data; //
struct ChainTree *left; //
struct ChainTree *right; //
}ChainBinTree;c)ノードをダブルツリーに追加する:
d)二叉樹の左右の木を取得する
e) 二叉の木の状態を取得します.二叉の木が空かどうか、二叉の木の深さを求めます.
f) 二叉ツリーでの検索:二叉ツリーでデータを検索するときは、各ノードのデータを逐一比較して、二叉ツリーの各ノードを巡回して、その後、ノードのポインタを参照する必要があります.
g)二叉樹をクリア:
if(bt)
{
BinTreeClear(bt->left); //
BinTreeClear(bt->right);//
free(bt);//
bt=NULL;
}(1).まず、ルートノードを訪問し、左サブツリーを順に遍歴し、最後に順に右サブツリーを巡回します.
BinTree_DLR（BinTree）{
If( )
{
；
BinTree_DLR（left）；//
BinTree_DLR（right）；//
}
}(3)左のサブツリーを後から順に巡回し、その後右のサブツリーを巡回して、最後にルートノードを訪問します.
7.スレッド二叉樹
(1)スレッド二叉ツリーの表示:各ノードの空きのためのポインタと右ポインタをそれぞれポインタノードの前駆と後続に使用すると、スレッド二叉ツリーが得られます.
(2).分類:まず手がかりの二叉樹、中順スレッドの二叉樹、後続スレッドの二叉樹
(3)スレッドマークエリアを追加した後、二叉チェーンの構造は以下の通りです.
typedef enum
{
SubTree,
Thread
}NodeFlag; // SubTree( ) Thread( ) 0，1
typedef struct ThreadTree //
{
DATA data; //
NodeFlag lflag; //
NodeFlag rflag; //
struct ThreadTree *left; //
struct ThreadTree *right; //
}ThreadBinTree;(5)操作スレッドの二叉ツリー:
a)後続ノードを検索する:
i. 親ノードPの右サブツリーが空であれば、p−＞rightは右スレッドであり、直接pの中間シーケンスを指して後続する.
ii. 親ノードpの右サブツリーが空でない場合、pの中間シーケンスの後続は、その右サブツリーの中で最初に巡回されたノードである必要がある.
b)前駆ノードを検索する:
i.親ノードpの左サブツリーが空であれば、p−leftは左スレッドであり、直接にpの中序前駆ノードを指す.
ii.親ノードpの左サブツリーが空でない場合は、pの左サブツリーから、そのサブツリーの右ポインタチェーンに沿って下を検索し、右サブツリーのないノードがあるまでは、このおよびエッはpの中間順にノードを前駆する.
c) スレッドを巡回しました.二叉の木はスレッド化されていますので、巡回中に後続のポインタによって素早く完成できます.再帰的な呼び出しを使わずに完了します.
8.最適な二叉樹(ハフマンツリー)
(1).決定権値を有するリーフツリーのセットについて、最小のリーフパス長を有する2つのツリーを意味する.
(2).基本概念:ノードの権利、経路、経路の長さ、ツリーの経路長、ノードの帯域権経路長、ツリーの帯域権経路長(WPL)
(3)ハフマンツリーを作成する手順:
a)まずN個の重みのノードに基づいてN本の二叉樹を構成し、各ノードは二叉樹であり、その権利値はルートノードに保持され、ここでは左右のサブツリーはすべて空である.
b) このN本の二叉の木の中から二つのルートノードの権利値が一番小さい木を見つけ、二つの木を左右のツリーとして新しい二叉の木を作り、左右のサブツリーのルートノードの権利値を加算して、新しい二叉のツリーノードの権利値とします.
c)前のステップで見つけた2つの重みの最小値の2つのツリーを次の検索から除外し、新たに作成された2つのツリーを検索範囲に追加します.
d)検索範囲が1本の木だけになるまで、ステップbとcを繰り返す.
(4)ハフマン符号:まずメモリに連続領域を割り当て、ハフマンの二叉樹を保存するために使用され、この部分のメモリを一つの仮想配列として使用し、その後、配列の下標記を通じて異なる二叉樹ノードにアクセスすることができる.
(5)ハフマンコードのいくつかの操作:
a)ハーフマンツリーを作成する
b)ハフマンツリーの各文字によるハフマンの符号化
c)ハフマンコードに基づいて文字列を符号化し、符号化された文字列を得る.
d)サブ文字列からバイナリコードを一つずつ取得し、ハフマンツリーで検索し、復号作業を完了します.
二、ネット関係:図(Graph)
要素間の関係は任意で、各データ要素は他のデータ要素と関連しています.
1.図の保存:
(1)隣接行列:(2つの配列で)
a)最初の配列:n個の要素を持つ1次元配列で、図中の頂点の情報を保存します.
b)2番目の配列:n＊nの2次元配列(行列)は、頂点間の隣接関係を保存するために使用されます.
(2)隣接表:隣接マトリクスを改良した接続構造であり、その特徴値は隣接マトリックス中の非ゼロ要素を考慮して隣接マトリクス保存図よりも省スペースである.隣接表は、図中の各頂点に対して隣接関係の単一チェーンテーブルを作成し、隣接行列の各ラインは単一チェーンテーブルに対応して、各シングルチェーンテーブルの表ヘッドポインタを一つの配列に保存し、任意の頂点チェーンテーブルにランダムにアクセスすることができる.
2.作成図:
(1)隣接マトリックスを用いる:
a)隣接マトリックスデータ構造の作成
b)隣接マトリックスの作成
c)隣接マトリックスの内容を出力します.
(2)隣接表で図を保存する
a)隣接テーブルデータ構造を定義する(頂点を定義するデータ構造)
b)図のデータ構造を定義する
c)隣接図の作成
d)出力隣接図
3.図の巡回:
広さ優先法と深さ優先法
(1) 広さ優先遍歴:広さ優先遍歴は再帰的過程ではない.巡回中に、まず訪問された頂点の近くの接点も先にアクセスされ、アルゴリズムの実現には訪問された頂点を一回記憶するためのキューを設定する必要があります.
(2)深さ優先エルゴード:深さ優先エルゴードは再帰的プロセスである.
a)isTrav配列からアクセスされていない頂点Viを選択し、アクセス済みとしてマークする.
b)次いで、Viのうちの一つの未アクセスの隣接点から深さ優先巡回を行う.
c)図中のすべての経路と共通の頂点がアクセスされるまで、ステップbを繰り返す.
d)aからcまでの手順を繰り返します.すべての頂点がアクセスされるまで.
4.最小ツリーを生成する:
N個の頂点を有する接続図については、N−1個のエッジが生成される.1つの権利値付きの連結図については、ツリーが異なるため、ツリー内の各辺の総和も異なり、権利値が一番小さい生成ツリーを図の最小生成ツリーといいます.
(1)ツリーを生成するための一般的なアルゴリズムprmを構築する:primアルゴリズムを実現するには、サブアレイが必要である.
a)配列1:tmpvertexは、対応する位置に隣接する頂点情報を保存する.
b)配列2:weightは、前の配列に対応する隣接辺の値を保存します.
5.最短経路(Dijkstraアルゴリズム)
頂点から別の頂点までの最短ルートを求めます.
実装するプロセスは、3つの配列が必要であり、(セットUは頂点セットであり、求められた最短経路の頂点をセットUに追加する)
一つ目は、頂点セットを保存するためのもので、diagramの重みが1の場合、対応する頂点をUセットに追加します.
第二は、一時的な計算を保存します.
第三:対応する辺があるかどうかを示す.
実装コードは以下の通りです.
void Dijkstra(MatrixGraph G)
{
int weight[VERTEX_MAX];//
int path[VERTEX_MAX];//
int tmpvertex[VERTEX_MAX];//
int i,j,k,v0,min;
printf("
:");
scanf("%d",&v0);
v0--; // 1( 0 )
for(i=0;i0) //
path[i]=v0; //
tmpvertex[i]=0; //
}
tmpvertex[v0]=1; // v0 U
weight[v0]=0; // 0
for(i=0;i