データ構造の復習

データ構造復習期末速成#

著者:itsbrqs

前言#

本ノートは 2023 年のデータ構造期末試験内容に特化した復習まとめであり、試験のポイントの時効性と正確性は保証されていません。itsbrqs によって編纂整理されました。本ノートは itsbrqs が期末試験に備えて作成したものです。

知識点と試験ポイント#

試験ポイントまとめ#

第 1 章序論：
- 抽象データ型
- 時間計算量
第 2 章線形表：
- 順序表
- 後向き単方向リスト
第 3 章スタックとキュー
- スタックとキューの構造的特徴
- スタックとキューの基本操作
第 5 章配列と一般表
- アドレス計算式
- 三元組の格納構造
第 6 章木と二分木
- 二分木の性質
- 二分木の遍歴アルゴリズムとその応用
- 二分木とスレッド二分木の遍歴
- 木と森の変換
- 木と森の遍歴アルゴリズム（列はどのように書くか）
第 7 章グラフ
- グラフの性質
- グラフの格納構造
  - 隣接行列
  - 隣接リスト
- グラフの遍歴
  - 遍歴列の書き方
  - 深さ優先遍歴と幅優先遍歴
- 最小生成木
- グラフの応用
  - トポロジカルソート
  - 关键路径
  - 最短路径

問題形式#

選択問題 5 問 + 空欄問題 5 問 + 応用大問 4 問 + アルゴリズム記述 2 問

第 1 章序論#

知識点 1 データ構造の定義#

学科の定義：データ構造は非数値計算のプログラム設計問題におけるコンピュータの操作対象とそれらの関係や操作などを研究する学科である。
データ構造の定義：データ要素とそれらの相互関係。
データ構造の簡単な分類：論理構造と格納構造。

知識点 2 4 つの基本論理構造#

集合：データ要素間には「同じ集合に属する」という関係以外には他の関係はない。
線形構造：データ要素間には一対一の関係が存在する。
木構造：データ要素間には一対多の関係が存在する。
グラフ構造：データ要素間には多対多の関係が存在する。

その中で集合構造、木構造、グラフ構造は非線形構造に属する。

非線形構造：木、二分木、有向グラフ、無向グラフ、集合。

線形構造：線形表、スタックとキュー、配列、一般表。

知識点 3 データ#

定義：コンピュータ分野において、コンピュータに入力され、コンピュータによって処理されるすべての記号の総称であり、コンピュータプログラムが加工する「原料」である。それには数値、文字、画像、音声などが含まれる。
操作：入力、出力、ソート、検索、挿入、削除。

知識点 4 データ構造の分類#

論理構造：データ要素間の論理関係、相互関係。
物理構造（格納構造）：コンピュータにおけるデータ構造の表現。格納構造は順序格納構造と連鎖格納構造に分かれる。

知識点 5 データ格納構造#

定義：データオブジェクトがコンピュータ内で格納される表現をデータの格納構造と呼び、物理構造とも呼ばれる。
コンピュータ内のデータ要素には 2 つの基本的な格納構造があり、それぞれ順序格納構造と連鎖格納構造である。

順序格納構造

定義：順序格納構造は、ストレージ内の要素の相対位置を利用してデータ要素間の論理関係を表現し、通常はプログラム設計言語の配列型を用いて記述される。
隣接格納、ストレージ内の要素の相対位置を利用してデータ要素間の論理関係を表現する。
利点：占有するストレージスペースが少なく、ストレージ密度が高い。欠点：フラグメンテーションが発生し、挿入や削除時に要素を移動する必要がある。

連鎖格納構造#

順序格納構造はすべての要素が連続したストレージスペースに順次格納されることを要求するが、連鎖格納構造は必ずしも一つのストレージスペースを占有する必要はない。しかし、ノード間の関係を表現するために各ノードにポインタフィールドを追加する必要があり、後続要素のストレージアドレスを格納するために、連鎖格納構造は通常プログラム設計言語のポインタ型を用いて記述される。
非隣接格納、要素のアドレスを格納するポインタを利用してデータ要素間の論理関係を表現する。
利点：空間利用率が高く、操作が簡単。欠点：占有するストレージスペースが多く、データ密度が低い。

2 つの構造の関係：データの論理構造と物理構造は切り離せない 2 つの側面であり、アルゴリズムの設計は選択された論理構造に依存し、アルゴリズムの実装は採用された格納構造に依存する。

知識点 6 抽象データ型#

抽象データ型は一般にユーザーが定義した、アプリケーション問題を表す数学モデルと、このモデル上に定義された一連の操作の総称を指し、具体的には 3 つの部分から構成される：データオブジェクト、データオブジェクト上の関係の集合、およびデータオブジェクトの基本操作の集合。

知識点 7 アルゴリズム#

アルゴリズムは特定の問題を解決するために規定された有限の操作シーケンスである。

アルゴリズムが満たすべき 5 つの特性：

有限性
確定性：各状況において実行すべき操作がアルゴリズム内で明確に規定されており、二義性が生じず、アルゴリズムの実行者や読者がその意味と実行方法を明確に理解できる。
実行可能性
入力
出力

知識点 8 アルゴリズムの評価#

正確性
可読性
頑健性
効率性：効率性には時間と空間の 2 つの側面があり、時間効率はアルゴリズムの設計が合理的で、実行効率が高いことを指し、時間計算量で測定できる；空間効率はアルゴリズムが合理的なストレージ容量を占有することを指し、空間計算量で測定できる。時間と空間の計算量はアルゴリズムの 2 つの主要な指標である。

知識点 9 時間計算量#

アルゴリズムの効率を測定する方法には主に 2 つのタイプがある：事後統計法と事前推定法。事後統計法は、アルゴリズムを実装した後にその時間と空間のコストを測定する必要がある。この方法の欠点は明らかであり、アルゴリズムを実行可能なプログラムに変換する必要があり、また時空コストの測定結果はコンピュータのソフトウェアやハードウェアなどの環境要因に依存し、アルゴリズム自体の優劣を隠す可能性がある。そのため、一般的に採用される方法は事前分析推定法であり、アルゴリズムの漸近的複雑度を計算することによってアルゴリズムの効率を測定する。

アルゴリズムの時間計算量の求め方#

最も深いループの回数を探し、最高次の項を求めるだけである。

アルゴリズムの時間計算量分析の例#

定数階 O (1)
```
{x ++ ;}
```

線形階 O (n)

for( int i = 0 ; i < n ; i ++ ) 
    s ++ ;

二次階 O (n^2)

#バブルソートも二次階
for (i = 0; i < size-1;i ++)//size-1は自分と比較しないため、比較する数が1つ少なくなる
	{
		int count = 0;
		for (j = 0; j < size-1 - i; j++)	//size-1-iは毎回1つの数が比較されなくなるため
		{
			if (arr[j] > arr[j+1])//これは昇順のソートで、前の数と後の数を比較し、前の数が大きければ後の数と位置を交換する
			{
				tem = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tem;
				count = 1;
			}
		}
		if (count == 0)			//もしある一回のループで位置が交換されなければ、すでにソートされていることを示し、ループを直接終了する
				break;	
	}

第 2 章線形表#

線形表： n (n≥0) 個のデータ特性が同じ要素から構成される有限の列。

線形表の格納構造：順序格納構造と連鎖格納構造。

データ構造の基本演算：修正、挿入、削除、検索、ソート。

知識点 10 順序格納空間動的割り当て線形表#

順序表の格納構造の利点と欠点：

利点：論理的に隣接し、物理的に隣接している；任意の要素にランダムにアクセスできる；ストレージスペースの使用がコンパクト；

欠点：挿入、削除操作には大量の要素を移動する必要がある；

格納構造#

typedef struct{
	ElemType *elem;//首アドレス
     int length;//現在の長さ
     int listsize;//現在占有しているストレージ容量
}

初期化#

/*アルゴリズムの考え方
*1.空間の割り当て
*2.割り当てが成功したかどうかの判断
*3.他のパラメータの初期化
*/
status Initlist_sq(Sqlist &L){
    //空間の割り当て
    L.elem=(ElemType)* malloc(L * sizeof(ElemType));
   //割り当てが成功したかどうかの判断 
    if(!L.elem) retrun -2;
   //他のパラメータの初期化
    L.length=0;
    L.listszie=0;
    return 0;
}

挿入#

/*アルゴリズムの考え方
*1.i値の合法性をチェック
*2.空間のオーバーフローとオーバーフロー空間の再割り当てをチェック
*3.再割り当てが成功したかどうかをチェック
*4.挿入位置の要素を取得し、全体を後ろに移動
*5.表の長さを1増やす
*/
status ListInsert_sq(Sqlist* L,int i,int e){
    int* newbase,q,p;
    //i値の合法性をチェック
    if(i<1||i>(L->length+1))
    	return ERROR;
	//長さが制限を超えた場合、新しいメモリを割り当てて格納する
	if(L->length>=L->listsize){
		newbase=(int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*
		sizeof(int));
     //ストレージが割り当てられなかったかどうかをチェック
     if(!newbase)
		return (OVERFLOW);
	L->elem=newbase;
	L->listsize+=LISTINCREMENT;
	}
     q=&(L->elem[i-1]);//qは挿入位置
    if(L->length>0){
		for(p=&(L->elem[(L->length)-1]); p>=q; --p){
		*(p+1)=*p;
        }
    }
	*q=e;
	++(L->length);
	return OK;
};

挿入

q=&(L->elem[i-1]);//qは挿入位置の要素
    if(L->length>0){//空であるかどうかをチェック
		for(p=&(L->elem[(L->length)-1]); p>=q; --p){
		*(p+1)=*p;//要素全体を後ろに移動
        }
    }
*q=e;//挿入要素

削除#

/*アルゴリズムの考え方
*1.i値の合法性をチェック
*2.削除される要素の位置を取得
*3.削除される要素をeに代入
*4.削除される要素の要素を取得し、全体を前に移動
*5.表の長さを1減らす
*/
//コアコード： 削除移動
q=&(L->elem[i-1]);//削除される要素の位置を取得
*e=*p;//削除される要素をeに代入
q=L->elem+L->length-1;//表の末尾
for(++p;p<=q;++p)
	*(p-1)=*p;//前に移動

知識点 11 連鎖格納後項単方向線形表#

単方向リストの特徴：

それは動的構造であり、全体のストレージスペースは複数のリストで共有される；事前に空間を割り当てる必要はない；ポインタは追加のストレージスペースを占有する；ランダムアクセスはできず、検索速度が遅い。

格納構造#

typedef struct LNode{
	Elemtype data;//データ域
	struct LNode *next;//ポインタ域
}

初期化#

Status InitList_L(LNode *L){
    L->next=NULL;//頭ノードのnext域を空にすることは非常に重要
    return OK;
};

C++ の参照パラメータを使用せず、構造体ポインタを渡しているため、空間を割り当てる必要はありません。

挿入#

/*アルゴリズムの考え方
*1.挿入前のノードを取得
*2.i値をチェック
*3.挿入ノードを生成
*4.古いノードを切断し、挿入ノードを挿入
*/
Status ListInsert_L(LNode *L,int i,Elemtype e){
    int j=0;
    LNode *p;
    p=L;
    while(p&&j<i-1){
    p=p->next;
    j++;
    }
    if(!p||j>i-1){
    return ERROR;//i値の検証、負値または表の長さ+1を超える値
    }
    
    LNode *s;
    s=(LinkLIst) malloc(sizeof(LNode));//空間割り当て！！！挿入ノードを生成
    s->data=e;
    //挿入開始
    s->next=p->next;//中部挿入時は必須
    p->next=s;
    return OK;
};

示意図は以下の通り：

削除#

/*アルゴリズムの考え方
*1.削除値の前のノードを取得
*2.i値をチェック
*3.削除ノードを生成
*4.古いノードのリンクを切断し、削除値の後のノードを削除
*5.削除値を返し、削除ノードを解放
*/
Status ListDelete_L(LNode *L,int i,Elemtype *e){
    int j=0;
    LNode *p;
    p=L;
    
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1){
        return ERROR;//i値の検証、負値または表の長さ+1を超える値
    }
    
    LNode *q;
    q=(LinkLIst) malloc(sizeof(LNode));//空間割り当て！！！
    
    q=p->next;//削除されるノードを取得
    p->next=q->next;//削除されるノードを越えて削除を実現
    
    *e=q->data;
    free(q);
    return OK;
};

示意図は以下の通り：

第 3 章スタックとキュー#

データ構造の観点から見ると、スタックとキューも線形表であり、その操作は線形表操作のサブセットであり、操作が制限された線形表である。しかし、データ型の観点から見ると、それらは線形表とは大きく異なる重要な抽象データ型である。

知識点 12 スタックの構造、定義と操作#

** 定義：** 表の末尾でのみ挿入または削除操作を行う線形表。

構造：

typedef struct stack{ 
    int stacksize; //スタックの容量 
    struct stack *head; //スタックトップポインタ 
    struct stack *base; //スタック底ポインタ
}

操作：

スタックに入れるpushのコツ：スタックポインタ top「先に押して後に加える」 : S[top++]=an+1

スタックから出すpopのコツ：スタックポインタ top「先に減らして後に弾く」 : e=S[--top]

//挿入 Push
Status Push(SqStack *S,SElemType e){
    if(S->top-S->base>S->stacksize){
        S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));//スタックが満杯のときに追加の空間を割り当てる
        if(!S->base)return -2;//割り当て失敗
        S->top=S->base+S->stacksize;//スタックトップポインタを移動
        S->stacksize+=STACKINCREMENT;
    }
    *(S->top)++=e;//挿入後スタックトップポインタを上に移動、ここでは実際に2つの操作
}
//削除 Pop
Status Pop(SqStack *S,SElemType *e){
    if(S->base==S->top){
        printf("error: SqStack NULL");
        return 0;//スタック空
    }
    *e=*(S->top-1);
    S->top--;
    return 1;
}

** 特徴：** 後入れ先出し、表に要素がないときは空スタックと呼ばれる。

知識点 13：キューの構造定義と操作#

** 定義：** 表の一端（キューの頭）でのみ挿入を行い、もう一端（キューの尾）で要素を削除する。先入れ先出し。

構造：

typedef struct QNode{
    QElemType data;
    struct QNode *next;   
}QNode,*QueuePtr;

typedef struct 
{
    QueuePtr front;//キューの頭ポインタ
    QueuePtr rear;//キューの尾ポインタ
    int len;
}LinkQueue;

操作：

キューに入れるEnQueue（尾部挿入）：rear->next=S; rear=S;

キューから出すDEQueue（頭部削除）：front->next=p->next;

//挿入EnQueue 削除DEQueue
Status EnQueue(LinkQueue *Q,QElemType e){
    QNode *p=(QueuePtr)malloc (sizeof(QNode));
    p->data=e;
    p->next=NULL;
    if(Q->front==NULL){
        Q->front=Q->rear=p;
    }else{
        Q->rear->next=p;
        Q->rear=p;
    }
    Q->len++;
    return 1;
    }
Status DeQueue(LinkQueue *Q,QElemType *e){
    int isEmpty=QueueEmpty(Q);
    if(!isEmpty){
    QNode *p=Q->front;
    Q->front=p->next;
    printf("info: Queue delete head elem %d success\n",p->data);
    free(p);
    return 1;
    }{
    printf("error:Queue Empty \n");
    return 0;
    }
    Q->len--;
}

** 特徴：** 先入れ先出し、空の連鎖キューの特徴：front=rear。連鎖キューが空である条件は首尾ポインタが等しいことであり、循環キューが満杯である条件の判定には、尾を 1 増やしたものが頭に等しいか、マークを設定する 2 つの方法がある。

知識点 14：線形表、スタック、キューの共通点と相違点：#

共通点：

論理構造が同じで、すべて線形である；
順序格納または連鎖リスト格納を使用できる；
スタックとキューは 2 つの特殊な線形表であり、すなわち制限された線形表（挿入、削除操作に制限を加えただけ）。

相違点：

演算規則が異なる：
- 線形表はランダムアクセスが可能；スタックは一端でのみ挿入と削除操作を許可するため、後入れ先出し表 LIFO；
- キューは一端でのみ挿入し、もう一端で削除操作を許可するため、先入れ先出し表 FIFO。
用途が異なる、線形表は比較的汎用的；スタックは関数呼び出し、再帰、設計の簡素化などに使用される；キューは離散イベントのシミュレーション、OS のジョブスケジューリング、設計の簡素化などに使用される。

第 5 章配列と一般表#

知識点 15 配列アドレス計算式#

20190201170604387

ji は n 次元配列の中でその要素の i 次元における座標
ai は n 次元配列の中でその i 次元の起点座標
bi は i 次元の長さ
L は 1 つの要素が占めるバイト数

例：順序表の最初の要素の格納アドレスが 100 で、各要素の長さが 2 の場合、5 番目の要素のアドレスは108。

1 次元の場合、上記の式はloc(j1)=loc(a1)+L*(j1-a1)。

loc=100+2*(0+(5-1))=108。

例：2 次元配列の各要素の長さが 4 バイトで、行インデックス i が 1 から 8、列インデックスが 1 から 10、首アドレス SA から行順に連続して格納されている場合、要素A[8][6]の起点アドレスはSA+300。

公式？犬も使わない、直接数えて第何個か、A[8][6]は 76 番目の要素。

loc=SA+4*(76-1)=SA+300。

首アドレス SA から列順に連続して格納されている場合、要素A[8][6]の起点アドレスはSA+168。

列数に従ってA[8][6]は 48 個の要素。

まとめ：2 次元配列A[X][Y]について、行要素の個数を a、列要素の個数を b、首要素のアドレスを A、要素の長さを s とすると、行順の場合のアドレスはA+s*((X-1)*b+Y-1)、列順の場合のアドレスはA+s*((Y-1)*a+X-1)。

知識点 16 三元組の格納構造#

typedef struct
{
    int i,j;
    ElemType e;
}Triple
#三元組順序表のC言語記述,疎行列
#define MAXSIZE 125000
typedef struct
{
Triple data[MAXSIZE+1];//行列が含む三元組表、data[0]は未使用
int mu,nu,t;//mu行数nu列数tu非0要素数
}TSMatrix

第 6 章木と二分木#

知識点 17 木#

木の概念と用語
- 木：n（n≥0）個のノードの有限集合。n＝0 のとき、空の木と呼ぶ；任意の非空の木は以下の条件を満たす：
  - 特定のノードが 1 つだけあり、それを根ノードと呼ぶ；
  - n＞1 のとき、根ノードを除く残りのノードは m（m>0）個の互いに交わらない有限集合 T1,T2,… ,Tm に分けられ、それぞれの集合はまた木であり、この根ノードの子木と呼ぶ。
- ノードの度：ノードが持つ子木の個数。
  
  木の度：木中のすべてのノードの度の最大値。
- 葉ノード：度が 0 のノード、終端ノードとも呼ばれる。
  
  分岐ノード：度が 0 でないノード、非終端ノードとも呼ばれる。
- 子、親：木のあるノードの子木の根ノードはこのノードの子ノードと呼ばれ、このノードはその子ノードの親ノードと呼ばれる；
  
  兄弟：同じ親を持つ子ノードは互いに兄弟と呼ばれる。
- パス：木のノード列 n1, n2, …, nk が以下の関係を持つ場合：ノード ni は ni+1 の親（1<=i<k）であるとき、n1, n2, …, nk を n1 から nk へのパスと呼ぶ；パス上を通過する辺の個数をパスの長さと呼ぶ。
- 祖先、子孫：木の中で、ノード x からノード y へのパスが存在する場合、x は y の祖先と呼ばれ、y は x の子孫と呼ばれる。
- ノードの所在層数：根ノードの層数は 1；他の任意のノードについて、あるノードが第 k 層にある場合、その子ノードは第 k+1 層にある。木の深さ：木中のすべてのノードの最大層数、または高さとも呼ばれる。
- 層序番号：木中のノードを上層から下層、同層から左から右の順に順次 1 から始まる連続自然数で番号を付ける。
- 有序木、無序木：もし木の中のノードの各子木が左から右に順序付けられている場合、この木は有序木と呼ばれる；逆に、無序木と呼ばれる。データ構造で議論されるのは一般に有序木である。
- 木は通常、前序（根）遍歴、後序（根）遍歴、層序（次）遍歴の 3 つの方法がある（木ではなく二分木であり、中序遍歴はない）。

木の高さと深さについて

木の深さは根ノードからこのノードまでに経過する辺の個数であるため、高さは深さに 1 を加えたものである。

知識点 18 二分木の定義と性質#

二分木の定義#

二分木は n（n≥0）個のノードの有限集合であり、この集合は空集合（空の二分木と呼ばれる）であるか、1 つの根ノードと 2 つの互いに交わらない、左子木と右子木と呼ばれる二分木から構成される。

満二分木：ある二分木の中で、すべての分岐ノードが左子木と右子木を持ち、すべての葉ノードが同じ層にある場合。

（満二分木の特徴：葉は最下層にしか出現できない；度が 0 と度が 2 のノードしか存在しない。）

完全二分木：n 個のノードを持つ二分木が層序番号を付けられた場合、番号 i（1≤i≤n）のノードが同じ深さの満二分木の中で番号 i のノードと完全に一致する位置にある場合。

完全二分木の特徴：

満二分木の中で、最後のノードから任意の数のノードを連続して削除すると、完全二分木になる。
葉ノードは最下層の 2 層にしか出現せず、最下層の葉ノードはすべて二分木の左側に集中する。
完全二分木に度が 1 のノードがある場合、それは 1 つだけであり、そのノードには左の子しかない。
深さ k の完全二分木は k-1 層で必ず満二分木である。
満二分木は必ず完全二分木であるが、完全二分木は必ずしも満二分木ではない。言い換えれば、満二分木はより厳格である。

二分木の性質#

性質 1：二分木の第 i 層には最大で 2i-1 個のノードが存在する（i≥1）。
性質 2：深さ k の二分木には最大で 2^k-1 個のノードが存在し、最小で k 個のノードが存在する。深さ k で 2^k-1 個のノードを持つ二分木は必ず満二分木である。
性質 3：ある二分木において、葉ノード数を n0、度が 2 のノード数を n2 とすると、n0＝n2 ＋1 である。（ノードの度はその放出する射線の数を指す）
性質 4：n 個のノードを持つ完全二分木の深さは log2n +1 である。
性質 5：n 個のノードを持つ完全二分木で層序番号が 1 から始まる場合、任意の番号 i（1≤i≤n）のノード（ノード i と呼ぶ）について：
- （1）i＞1 の場合、ノード i の親ノードの番号は i/2 である；i＝1 の場合、ノード i は根ノードであり、親ノードは存在しない。
- （2）2i≤n の場合、ノード i の左の子の番号は 2i である；2i＞n の場合、ノード i には左の子が存在しない。
- （3）2i＋1≤n の場合、ノード i の右の子の番号は 2i＋1 である；2i＋1＞n の場合、ノード i には右の子が存在しない。

知識点 19 二分木の遍歴#

前序遍歴は、木の任意のノードに対して、まずこのノードを印刷し、次に左の子木を印刷し、最後に右の子木を印刷することを指す。
中序遍歴は、木の任意のノードに対して、まず左の子木を印刷し、次に自分自身を印刷し、最後に右の子木を印刷することを指す。
後序遍歴は、木の任意のノードに対して、まず左の子木を印刷し、次に右の子木を印刷し、最後にこのノード自身を印刷することを指す。

層次遍歴は、各層を左から右に順に遍歴することを指す。

知識点 20 二分木の格納#

/*------二分木の二分連結リスト格納構造------*/
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode* left;
    struct BiTNode* right;
}BTNode,*BiTree;

知識点 21 スレッド二分木と格納#

二分木を作成する際、2 つのポインタ域が存在することがわかります。空のポインタ域は構造体を指していないため、多くの空間が浪費されます。したがって、これらの空のアドレスを利用して、特定の遍歴順序における前駆と後続ノードのアドレスを格納するという対策を講じます。この前駆と後続を指すポインタをスレッドと呼び、スレッドの二分連結リストをスレッドリストと呼び、対応する二分木をスレッド二分木と呼びます。

以下の図は中序遍歴スレッド二分木であり、中序遍歴は 1、3、6、8、10 です。

スレッドは二分木の操作の一種であり、二分木をスレッド化することを意味し、その目的はスレッド化された二分木が遍歴しやすい特徴を持つこと、すなわち再帰やスタックを使用せずにスレッド化された木を中序遍歴できるようにすることです。

特定の順序で二分木を遍歴してスレッド二分木に変換するプロセスをスレッド化と呼びます。

スレッド二分木の格納

struct Tree
{
    char  data;        //格納するデータ 
    int num;
    int LisThread;//左右のフラグ、値は0または1
    int RisThread; 
    struct Tree *lchild,*rchild;    //左と右の子のポインタ
};

知識点 22 二分木の応用 - ハフマン木とハフマン符号#

ハフマン木の基本概念：#

ハフマン木：確定した重みを持つ葉ノードの集合から、重み付きパスの長さが最小の二分木。

ハフマン木の特徴：#

重みが大きい葉ノードは根ノードに近く、重みが小さい葉ノードは根ノードから遠くなる。
度が 0（葉ノード）と度が 2（分岐ノード）のノードのみが存在し、度が 1 のノードは存在しない。

ハフマン木の遍歴：#

ハフマン木を構築する手順（すなわちハフマンアルゴリズム）：#

(1) 与えられた n 個の重み { w1, w2, …, wn } から n 棵の二分木の集合 F = { T1, T2, …, Tn }（すなわち森林）を構成し、各棵の二分木 Ti には重み wi の根ノードが 1 つだけ存在し、その左右の子木は空である。

(2) F の中から根ノードの重みが最小の 2 棵の木を選び、左右の子木として新しい二分木を構築し、新しい二分木の根ノードの重みはその左右の子木の根ノードの重みの合計とする。

(3) F の中からこの 2 棵の木を削除し、新しく得られた二分木を F に追加する。

(4) (2) と (3) を繰り返し、F に 1 棵の木だけが残るまで続ける。この木がハフマン木である。

重み付きパスの長さ（WPL）の計算#

重み付きパスの長さ = 葉ノードの重み × パスの長さ、上の図のハフマン木の葉ノードは 7、8、5、3、11、23 であり、WPL=7*4+8*4+3*4+5*4+11*3+23*2=167。

ハフマン符号の計算#

ハフマン符号の定義

ハフマン符号は、ハフマン木の左分岐を 0、右分岐を 1 とし、根ノードから各葉ノードまでに通過する分岐に対応する 0 と 1 で構成される列がそのノードに対応する文字の符号となる。このような符号をハフマン符号と呼ぶ。ハフマン符号は前置きのない符号である。デコード時に混乱することはない。主にデータ圧縮、暗号化などの場面で使用される。

知識点 23 木と森の変換#

木から二分木への変換#

線を加える：木のすべての隣接兄弟に線を加える。
線を取り去る：木の各ノードについて、最初の子ノードとの間の連線のみを保持し、他の子ノードとの連線を削除する。
回転：木の根ノードを軸にして、全体の木を時計回りに一定の角度回転させ、構造の層を明確にすることで二分木を得る。

森と二分木の相互変換#

二分木から森への変換

線を加える：二分木の各ノードとその左の子ノードの右の子ノードを連結する。
線を取り去る：木の各ノードと右の子ノードとの連線を取り去る。
回転：木の根ノードを軸にして、全体の木を反時計回りに一定の角度回転させ、構造の層を明確にすることで森を得る。

森から二分木への変換

線を加える：森のすべての隣接兄弟に線を加える。
線を取り去る：森の各ノードについて、最初の子ノードとの間の連線のみを保持し、他の子ノードとの連線を削除する。
回転：木の根ノードを軸にして、全体の木を時計回りに一定の角度回転させ、構造の層を明確にすることで二分木を得る。

知識点 24 木と森の遍歴#

木の遍歴#

木には前序、後序、層次遍歴があり、中序遍歴はない。

前序遍歴

二分木と同様に、先に根を訪問し、次に左に行き、最後に右に行く。優先度は次第に低下する。木が空でない場合、まず根ノードを訪問し、次に左から右の順に、根ノードの各子木を前序遍歴する。（木に対して二分木の前序遍歴のようなものを行う）上の図の木の前序遍歴は A B E F C D G I H。

後序遍歴

木が空でない場合、左から右の順に、根ノードの各子木を後序遍歴し、最後に根ノードを訪問する。（木に対して二分木の後序遍歴の手順を行う）上の図の木の後序遍歴は E F B C I G H D A。

森の遍歴#

二分木の先序遍歴をそのまま行うこともできるし、二分木に変換してから遍歴することもできる。

上の図の森の前序遍歴は A B C D E F G H J I。

第 7 章グラフ#

知識点 25 グラフの定義と性質#

グラフの定義：グラフ (Graph)：グラフ G は 2 つの集合 V (G) と E (G) から構成され、記号として G=(V,E) と表される。

ここで、V (G) は頂点の非空有限集合；E (G) は辺の有限集合であり、辺は頂点の無序対または有序対である。

有向グラフ、無向グラフ

頂点の度：

無向グラフでは、頂点の度は各頂点に接続されている辺の数である；

有向グラフでは、頂点の度は入度と出度に分かれる。

** 入度：** その頂点を頭とする弧の数。

** 出度：** その頂点を尾とする弧の数。

パス：パスは頂点の列。

パスの長さ：パスに沿った辺の数またはパスに沿った各辺の重みの合計。

ループ：最初の頂点と最後の頂点が同じであるパス。

単純パス：列中の頂点が重複して出現しないパス。

単純ループ：最初の頂点と最後の頂点を除いて、他の頂点が重複して出現しないループ。

連結：頂点 V から頂点 W にパスがある場合、V と W は連結している。

連結グラフ：グラフ中の任意の 2 つの頂点が連結している。

連結成分：非連結グラフの各連結部分。

強連結グラフ：有向グラフにおいて、任意の 2 つの頂点 Vi,Vj!=V, Vi!=Vj に対して、Vi から Vj へのパスと Vj から Vi へのパスが存在する場合、G は強連結グラフと呼ばれる。

知識点 26 グラフの格納構造#

隣接行列#

グラフの隣接行列表現法は、配列表現法とも呼ばれる。2 つの配列を使用してグラフを表現する：

1、頂点情報を格納する 1 次元配列；

2、グラフ中の頂点間の関連関係を格納する 2 次元配列、これを隣接行列と呼ぶ。

無重みグラフの隣接行列

有重みグラフの隣接行列

#グラフ構造隣接行列格納構造コード実装
#define MAXVEX 20					//頂点最大数
#define INFINITY 65535 				//代指無限大 
typedef struct
{
	datatype data[MAXVEX];			//頂点表 
	edgetype arc[MAXVEX][MAXVEX];	//辺の重みを格納する隣接行列 
	int numVertexes,numEdges;		//頂点数,辺または弧の個数 
}MGraph;//グラフ構造隣接行列
int visited[MAXVEX]; //訪問配列

隣接リスト#

隣接リスト表現法はグラフの一種の連鎖格納構造であり、基本的な考え方はグラフ中に存在する辺の情報のみを格納することである。

#define MAX_VERTEX_NUM 20 /* 最大頂点個数 */
typedef enum{DG, DN, UDG, UDN} GraphKind; /* グラフの種類 */
 
/* 頂点のヘッダーノードの型を定義 */
typedef struct VertexNode {
    VertexData data;    //データ域、頂点情報を格納
    ArcNode * firstarc; //ポインタ域、辺表中の最初のノードを指す
} VertexNode;
 
/* 辺ノードの型を定義 */
typedef struct ArcNode {
    AdjType adjvex;           //隣接点域、辺の終点が頂点表中のインデックス
    OtherInfo info;           //データ域、他の関連情報を格納
    struct ArcNode * nextarc; //ポインタ域、辺表中の次のノードを指す
} ArcNode;

隣接リストと隣接行列の違いは何か？#

関連：隣接リストの各連鎖は隣接行列の 1 行に対応し、連鎖中のノードの個数は 1 行中の非ゼロ要素の個数に等しい。
違い：任意の確定した無向グラフに対して、隣接行列は唯一である（行列番号と頂点番号が一致する）が、隣接リストは唯一ではない（リンクの順序は頂点番号に依存しない）。
用途：隣接行列は密なグラフの格納に多く使用され、隣接リストは疎なグラフの格納に多く使用される。

知識点 27 グラフの遍歴#

グラフの深さ優先遍歴（DFS）#

方法：グラフのある頂点 V0 から出発し、この頂点を訪問する；次に、V0 の未訪問の隣接点から出発し、深さ優先でグラフを遍歴し、V0 と接続されているすべての頂点が訪問されるまで続ける；この時、グラフ中に未訪問の頂点が残っている場合、グラフ中の未訪問の頂点を選んで起点とし、上記のプロセスを繰り返す。すべての頂点が訪問されるまで続ける。

いわゆる DFS は、起点から始めて、正しい方向を見つけて行けなくなるまで進み、元の道を戻り、次に行ける場所を見つけて続けるという考え方である。

深さ優先遍歴の結果は： A B E F C D G H I。

必ず説明しなければならないのは、ストレージ構造が指定されていない場合、深さ優先遍歴の結果は一意ではない。なぜなら、どの頂点が最初の隣接点であるかは不確定だからである。ストレージ構造が指定された後、深さ優先遍歴の結果は一意である。

グラフの幅優先遍歴（BFS）#

幅優先遍歴は次のように定義される：まず出発点 v を訪問し、次に v のすべての隣接点 w1、w2......wt を順に訪問し、次に w1、w2......wt に隣接するすべての未訪問の頂点を順に訪問する。このプロセスを繰り返し、グラフ中のすべての頂点が出発点 v と接続されているまで続ける。この時、v から始まる探索プロセスが終了する。

幅優先遍歴の結果は： A B C D E F G H I。

幅優先遍歴は層次的に最近のノードを優先的に探索し、層ごとに外側に探索する。

知識点 28 グラフの応用 - 最小生成木#

最小生成木（MST）の性質は次の通りである：U 集合が V の非空部分集合であり、(u0, v0) が最小重みの辺であり、u0 が U に属し、v0 が V-U に属する場合、(u0, v0) は最小生成木に必ず存在する。

MST を求める最も一般的な方法は以下の 2 つである：Kruskal（クラスカル）アルゴリズム、Prim（プリム）アルゴリズム。

Kruskal アルゴリズムの特徴：辺を結合し、疎なネットワークの最小生成木を求めるのに適している。

Prim アルゴリズムの特徴：頂点を結合し、辺の数に依存しないため、密なネットワークに適している。

Prim アルゴリズム（逐点加入）#

Prim アルゴリズムは密なグラフ（点が少なく辺が多い）により適している。

プロセスの図解

Kruskal アルゴリズム（逐辺加入）#

連結グラフの最小生成木は一意ではないが、最小生成木の辺の重みの合計は一意である。Prim と Kruskal のアルゴリズムを熟知し、特に手動でステップごとに生成木の生成プロセスをシミュレートすることが重要である。

知識点 29 グラフの応用 - トポロジカルソート#

トポロジカルソートは ** 有向非循環グラフ（有向グラフ、弧が閉じることはない）** のすべての頂点の線形列である。この線形列中では、グラフの各頂点は 1 回だけ出現し、頂点 A から頂点 B の間に有向弧 <v1,v2> が存在する場合、頂点 A は必ず頂点 B の前にある。

グラフの頂点を訪問する際、毎回訪問する頂点の前に他の頂点がないこと（入度が 0）を保証し、訪問する頂点は弧の弧頭としてのみ機能する。トポロジカルソートの前提条件：グラフに環がないこと。

入度が 0 のノード A を選び、A を出力する。AB AC の辺を削除する（B の入度は 1-1=0、C の入度は 2-1=1）。
1. 入度が 0 のノード B を選び、B を出力する。BC、BE の辺を削除する（C の入度は 1-1=0、E の入度は - 1）。
2. 入度が 0 のノード C を選び、C を出力する。C から始まる辺を削除する（C から始まる辺の入度 - 1）。

このプロセスを繰り返すことでトポロジカルソート ABCDEF（または ABCEDF）を得る。

注：トポロジカルソートの結果は一意ではない（同時に入度が 0 のものが複数あるため）、したがって問題はすべてのトポロジカルソートを記述するように要求することができる。

知識点 30 グラフの応用 - クリティカルパス#

クリティカルパス：有向グラフの各頂点がイベントを表し、各有向辺が活動の持続時間を表す場合、このグラフは活動辺ネットワーク、略して AOE ネットワークと呼ばれる。AOE ネットワークのクリティカルパスは、ネットワーク全体を完了するのに必要な最短時間、すなわち最長パスである。AOE ネットワークでは、いくつかの活動が平行に行われることが多いため、開始頂点から最後の頂点までの最長パスがクリティカルパスと呼ばれる。

特に説明は不要で、直接リストを作成し、イベントの最早発生時間 ve（最大）とイベントの最遅発生時間 vl（差が最小）を記述する。

まずトポロジカルソートを記述する。

正トポロジカルソート v1 v2 v3 v5 v4 v6

逆トポロジカルソート V6 V5 V4 V2 V3 V1

次に頂点 ve、vl を計算する。

ve は正トポロジカルソートを使用してルートと最大を計算する。

vl は逆トポロジカルソートを使用してルートの差を最小に計算する。

イベント	v1	v2	v3	v4	v5	v6
ve(i)	0	3	2	6	6	8
vl(i)	0	4	2	6	7	8

最後に辺（イベント）の弧尾頂点の最早開始時間は活動の最早開始時間 e、辺（イベント）の弧頭頂点の活動の最遅開始時間から重みを引いたものが活動の最遅開始時間（最遅であれば倒して求める）、l 時間余剰 l-e。

活動	a1	a3	a4	a5	a6	a7	a8
e(i)	0	3	3	2	2	6	6
l(i)	1	4	4	2	5	6	8-1
d(i)	1	1	1	0	3	0	1

クリティカルパスは v1 v3 v4 v6 である。

時間余剰が 0 であることはクリティカル活動 a2 a5 a7 を示す。

知識点 31 グラフの応用 - 最短パス#

Dijkstra（ダイクストラ）アルゴリズムは典型的な単源最短パスアルゴリズムであり、1 つのノードから他のすべてのノードへの最短パスを計算するために使用される。主な特徴は、起点を中心にして外側に層を広げていき、最終的に終点に達するまで続けることである。Dijkstra アルゴリズムは非常に代表的な最短パスアルゴリズムである。

アルゴリズムの思想：#

グラフ G=(V,E) が重み付き有向グラフであるとし、グラフ中の頂点集合 V を 2 つのグループに分ける。最初のグループは最短パスが求められた頂点集合（S と表す、初期状態では S には 1 つの源点のみが含まれ、以後最短パスが求められるたびにこの集合に追加され、すべての頂点が S に追加されるまでアルゴリズムは終了しない）、2 つ目のグループは未確定の最短パスの頂点集合（U と表す）である。最短パスの長さが増加する順に、未確定の頂点を次々に S に追加していく。追加する過程で、常に源点 v から S 中の各頂点への最短パスの長さが、源点 v から U 中の任意の頂点への最短パスの長さよりも大きくならないように保つ。また、各頂点には距離が対応しており、S 中の頂点の距離は v からこの頂点への最短パスの長さであり、U 中の頂点の距離は v からこの頂点への最短パスの長さであり、S 中の頂点を中間頂点としている。

解法の手順：#

単源点の非負重みの最短パスを求めるアルゴリズム Dijkstra ダイクストラアルゴリズム、動画プロセスリンク。

起点	終点	パス	距離
u	a	u	2
	b	a	5
	c	u	1
	d	a	3
	v	d	5

上の表に基づいて、u-v の最短パスは u-a-d-v であり、最短距離は 5 である。

超星問題選択#

スタックとキューの部分#

スタックの最大長さが推定できない場合、スタックは最も良い（連鎖）格納構造を採用する。
スタック構造で通常採用される 2 つの格納構造は順序格納構造と連鎖格納構造である。
スタックは再帰関数呼び出しを実現するためのデータ構造として使用できる。
式 a*(b+c)-d の後置式は (abc+*d-) である。

注：式を前後置式に変換する考え方：

a+b-a*((c+d)/e-f)+g を例に

後置式：

括弧法（推奨）：

①演算子の優先度に従って、すべての演算単位に括弧を加える。

これにより：(((a+b)-(a*(((c+d)/e)-f)))+g) となる。

②最も内側の括弧から始めて、順次演算子を対応する括弧の後ろに移動させる。

これにより：(((ab)+(a (((cd)+e)/f)-)*)-g)+

③最後に、すべての括弧を取り除く。

これにより：ab+acd+e/f-*-g + となる。

基于堆栈的算法：

左から右に遍歴する。

運算数に出会ったら、直接出力する。

左括弧 '(' に出会ったら、直接スタックに押し込む（括弧は最高優先度であり、比較する必要はない；スタックに入れた後は優先度が最低になり、他のシンボルが正常にスタックに入ることを保証する）。

右括弧 ')' に出会ったら、括弧が終了したことを意味する。スタックのトップの演算子を順次ポップして出力し、左括弧に出会うまで続ける。この左括弧はポップするが出力しない。

演算子（'+'、'-'、'*'、'/'）に出会った場合、3 つのケースがある。

①スタックが空であれば、直接スタックに押し込む。

②スタックのトップ要素が左括弧 '(' であれば、直接スタックに押し込む。

③スタックのトップ要素が演算子であれば、比較を行う必要がある。

1 - 優先度がスタックのトップ演算子より大きければ、スタックに押し込む；

2 - 優先度がスタックのトップ演算子より小さいか等しい場合、スタックのトップ演算子をポップして出力し、新しいスタックのトップ演算子と比較し、優先度がスタックのトップ演算子より大きくなるまで続けるか、スタックが空になるまで続け、新しい演算子をスタックに押し込む。

対象が処理されたら、スタック中のすべての演算子を順次ポップして出力する。

前置式：

括弧法（推奨）：

①演算子の優先度に従って、すべての演算単位に括弧を加える。

これにより：(((a+b)-(a*(((