３．操作を伴うデータ構造 ３．１ スタック （１）データを一時的に蓄えるデータ構造のひとつ （２）最後に入れたデータが最初に取り出される。 ３．操作を伴うデータ構造 ３．１　スタック （１）データを一時的に蓄えるデータ構造のひとつ （２）最後に入れたデータが最初に取り出される。 （３）後入れ先出し（LIFO:Last In First Out）方式とも呼ばれる。 ［操作］ Ｐｕｓｈ Ｐｏｐ Ｐｏｐ

確認用プログラム Name: textBox1 Name: button1 Text: Push Name: button2 ［画面］ Name: textBox1 Name: button1 Text: Push Name: button2 Text: Pop Name: label2 Name: listBox1

プログラム(その１） //宣言分部 private const int MAXSTACK = 500; private string[] Stack = new string[MAXSTACK]; private int StackPointer; //初期設定 private void Form1_Load(object sender, System.EventArgs e) { label2.Text=""; StackPointer=0; } //内容表示 private void 表示() listBox1.Items.Clear(); for(int i=StackPointer-1;i>=0;i--) listBox1.Items.Add(Stack[i]);

プログラム(その２） private void button1_Click(object sender, System.EventArgs e) { if(StackPointer>=MAXSTACK) MessageBox.Show("スタックが満杯です"); else Stack[StackPointer++]=textBox1.Text ; 表示(); } private void button2_Click(object sender, System.EventArgs e) if(StackPointer<=0) MessageBox.Show("スタックが空です"); label2.Text = Stack[--StackPointer] ;

３．２ 待ち行列（キュー） （１）データを一時的に蓄えるデータ構造のひとつ。 （２）最初に入れたデータが最初に取り出される。 ３．２　待ち行列（キュー） （１）データを一時的に蓄えるデータ構造のひとつ。 （２）最初に入れたデータが最初に取り出される。 （３）先入れ先出し（FIFO:First In First Out）方式とも呼ばれる。 （４）タスクや通信等の処理待ち行列，離散系シミュレーション等，様々な場面に使われる。 ［操作］ エンキュー (enque） 末尾 先頭 デキュー (deque）

配列による待ち行列の実現 エンキューで最後尾に入れて， デキューで先頭を取り出して，配列をずらす N 3 2 1 エンキュー デキュー エンキュー デキュー データ データ

確認用プログラム Name: button2 Name:label1 Text: Deque Text:空文字列 Name:listBox1 ［画面］ Name: button2 Text: Deque Name:label1 Text:空文字列 Name:listBox1 Name:textBox1 Text：空文字列 Name: button1 Text: Enque

プログラム(その１） //宣言分部 private string[] Que=new string[10]; private int QuePointer=0; // deque private string Deque() { if(QuePointer==0) { 　 　　MessageBox.Show("キューが空です."); 　　return ""; } else { string R=Que[0]; QuePointer--; for(int i=0;i<QuePointer;i++) Que[i]=Que[i+1]; 　　　　　　　　　　　　　　　　　　　　　　　　// すべての要素をずらす return R;

プログラム(その２） // enque private void Enque(string V) { if (QuePointer>=Que.Length) MessageBox.Show("キューが満杯です．"); else Que[QuePointer++]=V; } private void 表示() listBox1.Items.Clear(); for(int i=0;i<QuePointer;i++)listBox1.Items.Add(Que[i]); private void button1_Click(object sender, System.EventArgs e) Enque(textBox1.Text); 表示(); private void button2_Click(object sender, System.EventArgs e) string R=Deque(); label1.Text=R; 表示();

改良 配列の内容をずらすのは無駄な処理？ N 3 2 1 デキュー データ データ 単純な配列では，データを取り出すたびに エンキュー デキュー データ データ 単純な配列では，データを取り出すたびに 配列の内容をずらす必要がある。 改良の余地がある

サイクリックな待ち行列 ポインタを進める際にＮより大なら０に戻す。 … 開始ポインタ 終了ポインタ 1 2 3 N プログラム上の配列 1 2 3 N プログラム上の配列 待ち行列の概念的なイメージ （サイクリックなＱｕｅ）

待ち行列のプログラム上の処理 ［エンキュー］ ①終了ポインタをカウントアップ ②終了ポインタが配列数よりおおきければ，終了ポインタを０とする。 ③終了ポインタが開始ポインタと同じであれば，満杯とみなし，エラー。 ④終了ポインタが示す領域にデータを設定する。 ［EnQue］ ［デキュー］ ①終了ポインタと開始ポインタが同じであれば,空とみなす。 ②開始ポインタをカウントアップ。 ③開始ポインタが配列数よりおおきければ，開始ポインタを０とする。 ④開始ポインタが示す領域からデータを取り出す。 … N 3 2 1 終了ポインタ 開始ポインタ

プログラム(その１） // 宣言分部 private const int MAXQUE = 10; private string[] QUE=new string[MAXQUE]; private int StartPointer; private int EndPointer; // 初期設定 private void Form1_Load(object sender, System.EventArgs e) { StartPointer=0; EndPointer=0; }

プログラム(その２） // 待ち行列内容の表示 private void 表示() { int i; listBox1.Items.Clear(); if(EndPointer==StartPointer) for(i=0;i<MAXQUE;i++)listBox1.Items.Add("----"); else if(EndPointer<StartPointer) for(i=0;i<EndPointer;i++)listBox1.Items.Add(QUE[i]); for(i=EndPointer;i<StartPointer;i++)listBox1.Items.Add("----"); for(i=StartPointer;i<MAXQUE;i++)listBox1.Items.Add(QUE[i]); } else for(i=0;i<StartPointer;i++)listBox1.Items.Add("----"); for(i=StartPointer;i<EndPointer;i++)listBox1.Items.Add(QUE[i]); for(i=EndPointer;i<MAXQUE;i++)listBox1.Items.Add("----");

プログラム(その３） private string Deque() { string SR=""; if(StartPointer!=EndPointer){ SR=QUE[StartPointer]; StartPointer=CountP(StartPointer); } else MessageBox.Show("キューが空です."); return SR; private void Enque(string V) int P = CountP(EndPointer); if(P!=StartPointer) QUE[EndPointer]=V; EndPointer=P; else MessageBox.Show("キューが満杯です．");

プログラム(その４） private int CountP(int P) { P++; if(P>=MAXQUE) P= 0; return P; } private void button1_Click(object sender, System.EventArgs e) Enque(textBox1.Text); 表示(); private void button2_Click(object sender, System.EventArgs e) label1.Text=Deque(); 表示();

３．３　動的な領域管理 ＣやＣ++では，calloc関数，free関数を使って，領域の確保・開放を行い，ポインタでデータを参照することがよく行われる。 しかし，Ｃ＃では，ポインタの使用は推奨されていない。 次のようにunsafeを指定する必要がある。 　　unsafe 　　{ char* p=stackalloc char[256]; for (int i=0; i<256;i++) *(p+i)=(char)i; int* values = stackalloc int[20]; 　 　　int* a= & values[1]; 　　int* b= & values[15]; 　　MessageBox.Show 　　　　　　　(string.Format(" a - b = {0} \n b - a = {1}",a-b,b-a)); 　　}

動的な領域が必要となるとき リスト構造等を扱うとき，頻繁にデータ確保，開放を行う必要がある。 領域確保・開放をシステム任せにしたくないとき 領域確保は，最初のみ。 領域を分割して，領域確保・開放を行う。

動的な領域が必要となるとき 例えば，次のような要素データがあるものとすると， public struct ElementData { public long 番号; public string 氏名; public int 点数; } このデータを格納する領域を動的に管理するには，次のように未使用領域を管理できるように，各要素データを連結するための領域を用意します。 public struct ElementSet public ElementData Element; public long Next; public ElementSet[] DataArea = new ElementSet[500]; public long ErasedP;　//　未使用領域の先頭領域 public long DataP; //　格納しているデータの先頭

動的な領域が必要となるとき 最初，たとえば次のように連結しておきます。（空ポインタを-1とする） private void 初期化() { 　{ 　　　for(int i=0;i<DataArea.Length-1;i++) DataArea[i].Next=i+1; 　　　DataArea[DataArea.Length-1].Next=-1; 　 ErasedP=0; } 未使用ポインタ 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素

領域確保 ⅰ）未使用ポインタを関数値とする ⅱ）未使用ポインタが指しているポインタを未使用ポインタとする。 未使用ポインタ 未使用要素 　ⅱ）未使用ポインタが指しているポインタを未使用ポインタとする。 未使用ポインタ 未使用要素 未使用要素 未使用要素 未使用要素 この値を関数値とする 未使用要素 未使用要素 未使用要素 未使用要素 未使用ポインタ 使用領域 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素 未使用要素

領域確保 private long GetArea() { long R = ErasedP; ErasedP = DataArea[ErasedP].Next; return R; }

領域返却 ⅰ）未使用ポインタの内容を返却領域のポインタとする。 ⅱ）未使用ポインタを返却領域へのポインタとする。 未使用ポインタ 使用領域 　ⅱ）未使用ポインタを返却領域へのポインタとする。 未使用ポインタ 使用領域 使用領域 ⅰ） 返却領域 使用領域 未使用要素 未使用要素 未使用要素 未使用要素 未使用ポインタ 使用領域 ⅱ） 使用領域 返却領域 ⅰ） 使用領域 未使用要素 未使用要素 未使用要素 未使用要素

領域返却 private void FreeArea(long P) { if(P<0) return; 　 DataArea[P].Next=ErasedP; ErasedP = P; 　}

デバッグ時に返却ポインタをチェックする場合 private void FreeArea(long P) { if(P<0) return; // ***以下，チェック用*** 　 long PP = ErasedP; while(PP>=0) { if(PP==P) MessageBox.Show("領域"+P.ToString() +"はフリーエリアです"); return; } PP=next(PP); // ****チェックここまで*** DataArea[P].Next=ErasedP; ErasedP = P;

３．４ 線形リスト （１）線形リストとは ⅰ）データが順序付けられて並んだデータ構造 ３．４　線形リスト （１）線形リストとは ⅰ）データが順序付けられて並んだデータ構造 ⅱ）データを挿入したり削除するには，ポインタを付け替えるだけでよい。 　　（比較：配列の場合は，データをずらす処理が必要） ⅲ）線形リストは，リスト構造の中で最も単純なリスト 番号：11030 氏名：滝山和秀 点数：８２ 先頭ノード 末尾ノード 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ （注）本実装では，本来の意味のポインタ（アドレス）ではなく， 　　　ポインタを配列の添え字で表しているので， 　　　この場合，カーソルと呼ぶこともある。

（２）基本的な操作 ① 要素を先頭に付ける（cons) 番号：11030 氏名：滝山和秀 点数：８２ 先頭ノード 末尾ノード ポインタ 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ private long cons(ElementData Element, long Next) { long P=GetArea(); if(P<0) { MessageBox.Show("consで領域オーバしました．"); return -1; } DataArea[P].Element = Element; DataArea[P].Next = Next; return P;

（２）基本的な操作 ② 先頭要素を取り出す（GetElement) ポインタ 先頭ノード 末尾ノード 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ 番号：11001 氏名：浅田仁志 点数：９５ private ElementData getElement(long P) { return DataArea[P].Element; }

（２）基本的な操作 ③ 次の要素（Next) private long next(long P) { ポインタ 先頭ノード 末尾ノード 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ private long next(long P) { return DataArea[P].Next; }

（２）基本的な操作 ④ 次のポインタの置き換え（ReplaceNext) 先頭ノード 末尾ノード 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ 置き換えるポインタ （ＰＮ） 対象ポインタ （ＰＢ） 番号：11021 氏名：佐多憲二 点数：８８ private void replaceNext(long PB, long PN) { DataArea[PB].Next=PN; }

（２）基本的な操作 ⑤ 要素を置き換え private void replaceElement(long P, ElementData E) 先頭ノード 末尾ノード 対象ポインタ （Ｐ） 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ 置き換える データ （Ｅ） 番号：11001 氏名：浅田信二 点数：９７ 先頭ノード 末尾ノード 対象ポインタ （Ｐ） 番号：11001 氏名：浅田信二 点数：９７ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ private void replaceElement(long P, ElementData E) { DataArea[P].Element=E; }

（２）基本的な操作 ⑥ 最後の要素 private long last(long P) { 対象ポインタ （Ｐ） ＬａｓｔＰ 先頭ノード 末尾ノード 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ private long last(long P) { long PB = -1; long PP =P; while(P>=0){ PB=P;P=next(P); } return PB; }

（３）基本的な操作を使って ①リストの生成 (Ncons dt0) Cons dt0,-1⇒ Cons dt1,0⇒ Cons dt2,1⇒ Cons dt3,2⇒ Cons dt4,3 ４ ３ ２ 1 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ ５ ②リストの挿入 Cons dt5,2 番号：11012 氏名：君田康司 点数：６７ ReplaceNext 3,5

（３）基本的な操作を使って ③値の削除 ReplaceNext 3,2 ④要素を入れ替える⇒順序を変える （要素のデータ量が多いとき有効） ４ ３ ５ ２ 1 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７ ④要素を入れ替える⇒順序を変える 　　（要素のデータ量が多いとき有効） ４ ３ ２ 1 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７

（３）プログラム Name: textBox2 Name:textBox3 Name:button1 Name:button2 Name: ［フォーム定義］ Name: textBox2 Name:textBox3 Name:button1 Name:button2 Name: textBox1 Name:button3 Name: listBox1 Name:button4 Name:button5 Name:button6

（４）ソースプログラム ①データの宣言 public struct ElementData { public long 番号; public string 氏名; public int 点数; } public struct ElementSet public ElementData Element; public long Next; public ElementSet[] DataArea = new ElementSet[500]; public ElementData Element = new ElementData(); public long ErasedP; public long DataP;

（４）ソースプログラム ② Form1_Load private void Form1_Load(object sender, System.EventArgs e) { 初期化(); DataP=-1; データ登録(1,"福　田　武　夫",40); データ登録(2,"佐　藤　栄　二",20); データ登録(3,"中曽根　幹　雄",60); データ登録(4,"山　崎　恵　子",50); データ登録(5,"相　馬　剛　司",90); データ登録(6,"金　子　祐次郎",40); データ登録(7,"幸　田　美　咲",70); データ登録(8,"澤　田　幸　一",30); 表示(); }

（４）ソースプログラム ④表示とデータ登録 private void 表示() { 　long P=DataP; ElementData Element; listBox1.Items.Clear(); while(P>=0){ Element = getElement(P); listBox1.Items.Add(Element.番号.ToString("000000")+"\t"+ Element.氏名+"\t"+Element.点数.ToString()); P = next(P); } private void データ登録(long 番号, string 氏名, int 点数) ElementData Element; Element.番号=番号; Element.氏名=氏名; Element.点数=点数; 登録(Element);

（４）ソースプログラム ⑤button1, button2のクリックイベントハンドラ private void button1_Click(object sender, System.EventArgs e) { データ登録(long.Parse(textBox1.Text), textBox2.Text, int.Parse(textBox3.Text)); 表示(); } private void 先頭に追加(ElementData Element) long P2=cons(Element,DataP); if(P2>=0) DataP=P2; private void button2_Click(object sender, System.EventArgs e) ElementData Element; Element.番号=long.Parse(textBox1.Text); Element.氏名=textBox2.Text; Element.点数=int.Parse(textBox3.Text); 先頭に追加(Element);

（４）ソースプログラム ⑥ button3のクリックイベントハンドラ private void 最後に追加(ElementData Element) { long PB = -1; long P =DataP; while(P>=0){ PB=P;P=next(P); } long P2=cons(Element,-1); if(P2>=0){ if(PB<0) DataP = P2; else replaceNext(PB,P2); } private void button3_Click(object sender, System.EventArgs e) ElementData Element; Element.番号=long.Parse(textBox1.Text); Element.氏名=textBox2.Text; Element.点数=int.Parse(textBox3.Text); 最後に追加(Element); 表示();

（４）ソースプログラム ⑦ button4のクリックイベントハンドラ private long 氏名検索(string 氏名) { long P=DataP; while(P>=0) { if(string.Compare(getElement(P).氏名,氏名)==0) break; P=next(P); } return P; private void button4_Click(object sender, System.EventArgs e) ElementData E; string S; long P=氏名検索(textBox2.Text); if(P<0) S="見つかりませんでした"; else { E=getElement(P); S="Pointer = " + P.ToString() + " 番号 = " + E.番号.ToString() + " 点数 = " + E.点数.ToString(); MessageBox.Show(S);

（４）ソースプログラム ⑦ button4のクリックイベントハンドラ private void 氏名検索後削除(string 氏名) { long PB=-1; long P=DataP; while(P>=0) { if(string.Compare(getElement(P).氏名,氏名)==0) break; PB = P; P = next(P); } if(P<0) return; if(PB<0) DataP=next(P); else replaceNext(PB,next(P)); FreeArea(P); private void button5_Click(object sender, System.EventArgs e) 氏名検索後削除(textBox2.Text); 表示();

（４）ソースプログラム ⑧ソート処理に対するリスト構造の利用 private void 線形リストによる単純挿入ソート() { 　　long P1=DataP; long NP1;　if(P1<0) return; 　　long PB1=P1; P1=next(P1); while(P1>=0) { ElementData E1=getElement(P1); long P2=DataP; long PB2=-1; bool flag=false; while(P1 != P2) { ElementData E2=getElement(P2); if(E1.点数<E2.点数){ flag=true; break;} PB2=P2; P2=next(P2); } if(flag){ NP1=next(P1); replaceNext(PB1,NP1); replaceNext(P1,P2); if( PB2<0) DataP=P1; else replaceNext(PB2,P1); P1=NP1; else {PB1=P1;P1=next(P1);

（４）ソースプログラム ⑨ button6のクリックイベントハンドラ private void button6_Click(object sender, System.EventArgs e) { 線形リストによる単純挿入ソート();　表示(); }

３．５ 循環・重連結リスト （１）循環リスト ⅰ）末尾ノードに先頭ノードを指すポインタを入れたもの。 ３．５　循環・重連結リスト （１）循環リスト ⅰ）末尾ノードに先頭ノードを指すポインタを入れたもの。 ⅱ）環状に並んだデータの並びを自然な形で表現できる。 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７

プログラム例 ［Form形式］ Name:textBox1 Name:button1 Name:listBox1

ソースプログラム private void Form1_Load(object sender, System.EventArgs e) { long P1,P2; 初期化(); DataP=-1; データ登録(1,"福　田　武　夫",40); データ登録(2,"佐　藤　栄　二",20); データ登録(3,"中曽根　幹　雄",60); データ登録(4,"山　崎　恵　子",50); データ登録(5,"相　馬　剛　司",90); データ登録(6,"金　子　祐次郎",40); データ登録(7,"幸　田　美　咲",70); データ登録(8,"澤　田　幸　一",30); DataArea[last(DataP)].Next=DataP; 循環表示(); int P=int.Parse(textBox1.Text); listBox1.SelectedIndex=P; }

ソースプログラム private void 循環表示() { long P=DataP; ElementData Element; listBox1.Items.Clear(); do Element = getElement(P); listBox1.Items.Add(Element.番号.ToString("000000")+ "\t"+Element.氏名+"\t"+Element.点数.ToString()+ "\t Pointer = "+P.ToString()+"\t Next =” + DataArea[P].Next.ToString()); P = next(P); } while(P != DataP); } private void button1_Click(object sender, System.EventArgs e) long P=long.Parse(textBox1.Text); long Pnext=DataArea[P].Next; listBox1.SelectedIndex=(int)Pnext; textBox1.Text=Pnext.ToString();

（２）重連結リスト ⅰ）先行ノードへのポインタをも持たせたリスト。 ⅱ）先行ノードを直接見つけることができる。（線形リストとの比較） ⅲ）重連結リスト（doubly linked list）または双方向リストと呼ばれる。 番号：11001 氏名：浅田仁志 点数：９５ 番号：11012 氏名：君田康司 点数：６７ 番号：11025 氏名：白江雄二 点数：７６ 番号：11033 氏名：浜崎拓哉 点数：７８ 番号：11048 氏名：矢田淳一 点数：８７

（３）データ構造 データ構造上は，前方向へのポインタを追加します。 public struct ElementSet { 　　{ 　　　　public ElementData Element; 　　　　public long Befor;　// この部分を追加 　　　　public long Next; 　　 } 領域管理は，線形リストのときと同じです。

基本的な操作（１） ⅰ）Beforに対する操作が増える。 ⅱ）操作における処理が異なるものがある。 （a）要素を先頭に付ける（Lispのconsに相当) [プログラム処理] 　private long cons(ElementData Element, long Next) 　{ 　　long P=GetArea(); 　　if(P<0){ MessageBox.Show("consで領域オーバしました．"); return -1; } 　　DataArea[P].Element = Element; 　　DataArea[P].Befor = -1; 　　DataArea[P].Next = Next; 　　if(Next>=0) DataArea[Next].Befor= P; return P; 　}

基本的な操作（２） （b）先頭要素を取り出す（Lispのcarに相当) （この処理は線形リストと同じ） [プログラム処理] 　　（この処理は線形リストと同じ） [プログラム処理] 　private ElementData getElement(long P) 　{ 　　　return DataArea[P].Element; 　 } （c）次のリスト（Lispのcdrに相当) 　private long next(long P) 　　　if(P<0) return -1; 　　　return DataArea[P].Next; 　}

基本的な操作（３） （ｄ）前のリスト （この処理は追加） [プログラム処理] private long befor(long P) { 　　（この処理は追加） [プログラム処理] 　private long befor(long P) 　{ 　　　if(P<0) return -1; 　　　return DataArea[P].Befor; 　} （e）次のポインタの置き換え（Lispのreplacdに相当) 　　（この処理は線形リストと同じ） 　private void replaceNext(long PB, long PN) 　　　DataArea[PB].Next=PN;

基本的な操作（４） （f）先行ポインタの置き換え （この処理は追加） [プログラム処理] 　　（この処理は追加） [プログラム処理] 　private void replaceBefor(long PB, long PN) 　{ 　　　DataArea[PB].Befor=PN; 　} （ｇ）要素を置き換え（Lispのreplacaに相当) 　　（この処理は線形リストと同じ） 　private void replaceElement(long P, ElementData E) 　　　DataArea[P].Element=E;

基本的な操作（５） （ｈ）最後のポインタ（Lispのlastに相当) （この処理は線形リストと同じ） [プログラム処理] 　　（この処理は線形リストと同じ） [プログラム処理] 　private long last(long P) 　{ 　　　long PB = -1; long PP =P; 　　　while(P>=0){ PB=P;P=next(P); } 　　　return PB; 　}

基本的な操作（６） （ｉ）N番目（LispのNthに相当) （この処理は線形リストと同じであるが，ここで新たに示す） [プログラム処理] 　　（この処理は線形リストと同じであるが，ここで新たに示す） [プログラム処理] 　private long Nth(long P, int N) 　{ 　　　long PP = P; 　　　for(int i=1;i<=N-1;i++) 　　　{ 　　　　　if(PP<0)return(-1); 　　　　　PP=next(PP); 　　　} 　　　return PP; 　}

プログラム Name: textBox2 Name:textBox3 Name:button1 Name:button2 ［フォーム定義］（線形リストのフォームに追加） Name: textBox2 Name:textBox3 Name:button1 Name:button2 Name:button3 Name: textBox1 Name:button4 Name: listBox1 Name:button5 Name:button6 Name:button7 Name:button8 ２ボタンを追加

①Form_Load private void Form1_Load(object sender, System.EventArgs e) { 初期化();DataP=-1; データ登録(1,"福　田　武　夫",40); データ登録(2,"佐　藤　栄　二",20); データ登録(3,"中曽根　幹　雄",60); データ登録(4,"山　崎　恵　子",50); データ登録(5,"相　馬　剛　司",90); データ登録(6,"金　子　祐次郎",40); データ登録(7,"幸　田　美　咲",70); データ登録(8,"澤　田　幸　一",30); 表示モード=0; 表示(); }

②登録処理 private void 登録(ElementData Element) { long P=DataP; ElementData tempElement; tempElement.番号=-1; long PB=-1; while(P>=0){ tempElement=getElement(P); if(tempElement.番号>=Element.番号) break; PB=P; P=next(P); } if(tempElement.番号==Element.番号) replaceElement(P,Element); else{ long P2=cons(Element,P); if(P2>=0) { if(PB<0) DataP=P2; else replaceNext(PB,P2); if(P>=0) replaceBefor(P,P2); if(P2>=0)replaceBefor(P2,PB);

③ポインタ表示 private void ポインタ表示() { long P=DataP; ElementData Element; listBox1.Items.Clear(); while(P>=0) Element = getElement(P); listBox1.Items.Add("Pointr=" +P.ToString()+ "\t番号="+ Element.番号.ToString()+ 　　　　　　　　　　"\tBefor="+DataArea[P].Befor+ 　　　　　　　　　　"\tNext="+DataArea[P].Next.ToString()); P = next(P); }

④一覧表示と表示モードの判別 private void 一覧表示() { 　　long P=DataP; ElementData Element; 　　listBox1.Items.Clear(); 　　while(P>=0) 　　{ Element = getElement(P); listBox1.Items.Add(Element.番号.ToString("000000") + "\t” + Element.氏名 + "\t” + Element.点数.ToString()); P = next(P); } private void 表示() if(表示モード==0) 一覧表示(); else ポインタ表示();

⑤データ登録，button1_Click，先頭に追加する処理 private void データ登録(long 番号, string 氏名, int 点数) { ElementData Element; Element.番号=番号; Element.氏名=氏名; Element.点数=点数; 登録(Element); } private void button1_Click(object sender, System.EventArgs e) データ登録(long.Parse(textBox1.Text), textBox2.Text, int.Parse(textBox3.Text)); 表示(); private void 先頭に追加(ElementData Element) long P2=cons(Element,DataP); if(P2>=0) DataP=P2;

⑥button2_Click，最後に追加する処理 private void button2_Click(object sender, System.EventArgs e) { ElementData Element; Element.番号=long.Parse(textBox1.Text); Element.氏名=textBox2.Text; Element.点数=int.Parse(textBox3.Text); 先頭に追加(Element); 表示(); } private void 最後に追加(ElementData Element) long PB =last(DataP); long P2=cons(Element,-1); if(P2>=0) if(PB<0) DataP = P2; else replaceNext(PB,P2); replaceBefor(P2,PB);

⑦button2_Click，最後に追加する処理 private void button2_Click(object sender, System.EventArgs e) { ElementData Element; Element.番号=long.Parse(textBox1.Text); Element.氏名=textBox2.Text; Element.点数=int.Parse(textBox3.Text); 先頭に追加(Element); 表示(); } private void 最後に追加(ElementData Element) long PB =last(DataP); long P2=cons(Element,-1); if(P2>=0) if(PB<0) DataP = P2; else replaceNext(PB,P2); replaceBefor(P2,PB);

⑧button3_Click，氏名検索 private void button3_Click(object sender, System.EventArgs e) { ElementData Element; Element.番号=long.Parse(textBox1.Text); Element.氏名=textBox2.Text; Element.点数=int.Parse(textBox3.Text); 最後に追加(Element); 表示(); } private long 氏名検索(string 氏名) long P=DataP; while(P>=0) 　　if(string.Compare(getElement(P).氏名,氏名)==0) break; 　　 P=next(P); return P;

⑨button4_Click private void button4_Click(object sender, System.EventArgs e) { ElementData E; string S; long P=氏名検索(textBox2.Text); if(P<0) S="見つかりませんでした"; else { E=getElement(P); S="Pointer = " + P.ToString() + " 番号 = " + E.番号.ToString() + " 点数 = " + E.点数.ToString(); } MessageBox.Show(S);

⑩氏名検索後削除, Button5_Click private void 氏名検索後削除(string 氏名) { long PB=-1; long P=DataP; while(P>=0) { if(string.Compare(getElement(P).氏名,氏名)==0) break; PB = P; P = next(P); } if(P<0) return; 　　long NP=next(P); 　　if(PB<0) DataP=next(P); 　　else replaceNext(PB,NP); 　　if(NP>=0) replaceBefor(NP,PB); 　　FreeArea(P); private void button5_Click(object sender, System.EventArgs e) { 氏名検索後削除(textBox2.Text); 表示();

⑪ソート private void 線形リストによる単純挿入ソート() { long P1=DataP; long NP1; if(P1<0) return; long PB1 =P1; P1=next(P1); while(P1>=0) { ElementData E1=getElement(P1); long P2=DataP; bool flag=false; long PB2 =-1; while(P1 != P2) { ElementData E2=getElement(P2); if(E1.点数<E2.点数){ flag=true; break;} PB2 = P2 ; P2=next(P2); } if(flag) { 　 NP1=next(P1); replaceNext(PB1,NP1); replaceBefor(NP1,PB1); replaceNext(P1,P2); replaceBefor(P1,PB2); if( PB2<0) DataP=P1; else replaceNext(PB2,P1); replaceBefor(P1,PB2); replaceBefor(P2,P1); P1=NP1; else {PB1=P1;P1=next(P1);}

⑫button6_Click, listBox1_SelectedIndexChanged private void button6_Click(object sender, System.EventArgs e) { 線形リストによる単純挿入ソート();　表示(); } private void listBox1_SelectedIndexChanged 　　　　　　　　　　(object sender, System.EventArgs e) int ID=listBox1.SelectedIndex; if(ID>=0) long L=Nth(DataP,ID+1); ElementData E=DataArea[L].Element; textBox1.Text=E.番号.ToString(); textBox2.Text=E.氏名; textBox3.Text=E.点数.ToString();

⑬Button7_Click, Button8_Click private void button7_Click(object sender, System.EventArgs e) { 表示モード=0;　表示(); } private void button8_Click(object sender, System.EventArgs e) 表示モード=1;　表示();

３．６ 木構造 （１）木構造の用語 階層的な関係を表現する。 ３．６　木構造 （１）木構造の用語 階層的な関係を表現する。 根（root），節（node），枝（edge/branch），葉（leaf/terminal node） 葉 葉 葉 枝 枝 節 単純化 葉 葉 枝 葉 葉 節 葉 枝 葉 節 節 枝 枝 節 根

３．６ 木構造 （１）木構造の用語 通常は，根Rootを上にして反転して図示される。 根に近いノードを親（parent）, ３．６　木構造 （１）木構造の用語 通常は，根Rootを上にして反転して図示される。 根に近いノードを親（parent）, 遠いノード／葉を子（child)， 共通の親を持つ子を兄弟（sibling）と呼ぶ 葉 節 根 葉 節 根 上下反転

３．６ 木構造 （１）木構造の用語 順序木 （ordered tree） ：兄弟関係で順序関係を持つ木 ３．６　木構造 （１）木構造の用語 順序木　（ordered tree）　：兄弟関係で順序関係を持つ木 無順序木（unordered tree）：兄弟関係で順序関係を持たない木 以下の木は，順序木とみなせば異なる木であり， 無順序木とみなせば，同一の木である。 ３ 1 ２ １

３．６ 木構造 （２）２分木 左の子（left child）と右の子（right child)の ３．６　木構造 （２）２分木 左の子（left child）と右の子（right child)の ２つの子を持つ木を２分木（binary tree）と呼ぶ。 ただし，左の子だけのノード，右の子だけのノード， 子を持たないノード（leaf/terminal node）はありうる。 Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ I J Ｌ

（３）探索方法 横型探索／幅優先探索（breadth-first search） ルートに近い点から横方向に探索。兄弟関係方向を優先して探索する方法 　　　ＡＢＧＣＤＨＫＥＦＩＪＬ Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ｉ Ｊ Ｌ

縦型探索／深さ優先探索（depth-first search） 深さ方向を優先して探索する方法 Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ｉ Ｊ Ｌ

３種類の深さ優先探索 三種類のたどり方 ■行きがけ順（ノード処理 → 左へ → 右へ） ■通りがけ順（左へ → ノード処理 → 右へ） ■行きがけ順（ノード処理　→　左へ　→　右へ） ■通りがけ順（左へ　→　ノード処理　→　右へ） ■帰りがけ順（左へ　→　右へ　→　ノード処理） 行きがけ順 （pre_order） 帰りがけ順 (post_order) 通りがけ順 (in_order)

３種類のたどり方 行きがけ順：ＡＢＣＤＥＦＧＨＩＪＫＬ 通りがけ順：ＣＢＥＤＦＡＩＨＪＧＬＫ 帰りがけ順：ＣＥＦＤＢＩＪＨＬＫＧＡ Ａ Ｂ

（４）２分探索木（binary search tree） 左部分木のすべてのキー値は，対象ノードのキー値より小さい。 右部分木のすべてのキー値は，対象ノードのキー値より大きい。 20 5 40 3 10 30 50 8 15 26 35 44

２分探索木の実装 線形リストと同様，次のように宣言する。 public struct ElementData { public long 番号; public string 氏名; public int 点数; } public struct DataSet public ElementData Element; public long Left; public long Right; public DataSet[] DataArea = new DataSet[500]; public long ErasedP; public long DataP; public ElementData[] tempData;

２分探索木の実装 領域管理でのフリーリストは， 便宜上，Rightポインタで連結する。すなわち， private void 初期設定() { long N = DataArea.Length - 1; long i = 0; while(i < N) DataArea[i].Right = ++i; DataArea[N].Right = -1; ErasedP = 0; } private long getArea() long P = ErasedP; if(P >= 0) ErasedP = right(P); else MessageBox.Show("領域を確保できません"); return P; private void freeArea(long P) if(P < 0) return; DataArea[P].Right = ErasedP; ErasedP = P;

基本操作（１） private ElementData element(long P) { return DataArea[P].Element; } private long right(long P) 　　return DataArea[P].Right; private long left(long P) return DataArea[P].Left;

基本操作における基本処理 処理の基本 当該ノードの処理 Ａ 右部分木の処理 左部分木の処理 Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ｉ Ｊ Ｌ

基本操作（２） private long count(long P) { if(P<0) return 0; 　return count(left(P))+count(right(P))+1; } private void freeAll(long P) 　if(P<0) return ; freeAll(left(P)); freeAll(right(P)); freeArea(P);

基本操作（３） private long 木を配列に移動(long P, long ID) { if(P<0) return ID; 　 long ID1 = 木を配列に移動(left(P), ID); 　 tempData[ID1].番号 = DataArea[P].Element.番号; 　 tempData[ID1].氏名 = DataArea[P].Element.氏名; 　 tempData[ID1].点数 = DataArea[P].Element.点数; 　 ID1++; 　 long ID2 = 木を配列に移動(right(P), ID1); return ID2; }

基本操作（４） 配列を木に変換

基本操作（４） private long 配列を木に変換(long Left, long Right) { 　　if(Right < Left) return -1; 　　long Center = (Left+Right)/2; 　　long PL = 配列を木に変換(Left,Center-1); 　　long PR = 配列を木に変換(Center+1,Right); 　　long P = getArea(); 　　if(P < 0) { freeAll(PL); freeAll(PR);} 　　else 　　{ DataArea[P].Element.番号 = tempData[Center].番号; DataArea[P].Element.氏名 = tempData[Center].氏名; DataArea[P].Element.点数 = tempData[Center].点数; DataArea[P].Left=PL; DataArea[P].Right=PR; 　　} 　　return P; }

基本操作（５） private long 木の再構築(long P) { long N = count(P); 　　tempData = new ElementData[N]; 木を配列に移動(P, 0); freeAll(P); long X = 配列を木に変換(0, N - 1); 　　tempData = new ElementData[0]; return X; }

基本操作（６） private long 番号探索(long P,long 番号) { if(P < 0) return -1; ElementData E = element(P); if(番号 == E.番号) return P; else if(番号 < E.番号) return 番号探索(left(P),番号); else return 番号探索(right(P),番号); } private long 氏名探索(long P,string 氏名) if(string.Compare(氏名,E.氏名) == 0) return P; long PL = 氏名探索(left(P),氏名); if( PL >= 0) return PL; return 氏名探索(right(P),氏名);

プログラム（１） Name: textBox2 Name:textBox3 Name:button1 Name:button4 Name: ［フォーム定義］ Name: textBox2 Name:textBox3 Name:button1 Name:button4 Name: textBox1 Name:button2 Name: listBox1 Name:button3 Name:button5

プログラム（１） private void 表示() { listBox1.Items.Clear(); 要素表示(DataP,""); } long P = ErasedP; long PP; 　while(P>=0) 　{ PP=right(P); 　　　listBox1.Items.Add(P.ToString() + "\t" + PP.ToString()); 　　　P=PP; 　}

プログラム（２） private void 要素表示(long P, String S) { if(P<0) return; 　要素表示(DataArea[P].Left, S + " "); 　ElementData E = DataArea[P].Element; listBox1.Items.Add(S+E.番号.ToString("0000")+"\t"+ 　　　　　　E.氏名.ToString()+"\t"+E.点数.ToString()); 　要素表示(DataArea[P].Right, S + " "); } private void Form1_Load(object sender, System.EventArgs e) 初期設定();DataP=-1; 表示();

プログラム（３） private long 登録(long P,long 番号, string 氏名, int 点数) { 　　if(P < 0){ long PP = getArea();if(PP < 0) return -1; DataArea[PP].Element.番号 = 番号; DataArea[PP].Element.氏名 = 氏名; DataArea[PP].Element.点数 = 点数; DataArea[PP].Left = -1; DataArea[PP].Right = -1; return PP; 　　} else if(番号 == DataArea[P].Element.番号) { DataArea[P].Element.氏名 = 氏名; DataArea[P].Element.点数 = 点数; } else if(番号 < DataArea[P].Element.番号) DataArea[P].Left = 登録(DataArea[P].Left ,番号,氏名,点数); else DataArea[P].Right = 登録(DataArea[P].Right,番号,氏名,点数); 　　return P;

プログラム（４） private void button1_Click(object sender, System.EventArgs e) { 　try 　{ 　　　DataP = 登録(DataP,　long.Parse(textBox1.Text), 　　　　　　　　textBox2.Text, int.Parse(textBox3.Text)); 表示(); } catch(Exception E) MessageBox.Show(E.Message);

プログラム（５） private long 木の再構築(long P) { long N = count(P); 　　tempData = new ElementData[N]; 木を配列に移動(P, 0); 　　listBox1.Items.Clear(); 　　for(int i = 0;i < N; i++) 　　{ ElementData E = tempData[i]; listBox1.Items.Add(E.番号.ToString() + "\t” + 　　　　　　　　　　E.氏名 + "\t"+E.点数.ToString()); 　　} 　　MessageBox.Show("一次元配列に変換しました"); freeAll(P); long X = 配列を木に変換(0, N-1); 　　tempData = new ElementData[0]; return X; }

プログラム（６） private void button2_Click(object sender, System.EventArgs e) { 　　DataP = 木の再構築(DataP); 表示(); } private string 先頭文字列(String S) string SS = S; string R = ""; int i = 0; while(i < S.Length && S[i] ==' ') i++; while(i < S.Length && S[i] !=' ' && S[i]!='\t') R = R + S[i].ToString(); i++; 　　 return R;

プログラム（７） private void listBox1_SelectedIndexChanged 　　　　　　　　　　　　(object sender, System.EventArgs e) { string S = 先頭文字列(listBox1.Text); long N = long.Parse(S); long P = 番号探索(DataP,N); if(P >= 0) ElementData E = element(P); textBox1.Text = E.番号.ToString(); textBox2.Text = E.氏名; textBox3.Text = E.点数.ToString(); }

プログラム（８） private void button3_Click(object sender, System.EventArgs e) { long P = 番号探索(DataP,long.Parse(textBox1.Text)); 　　if(P < 0) MessageBox.Show("検索失敗"); 　　else 　　{ ElementData E = element(P); MessageBox.Show("\nP =” + P.ToString()+ "\nE =” + E.番号.ToString()+ “\n氏名=” + E.氏名+ “\n点数=” + E.点数.ToString()+ "\nLeft=” + left(P).ToString()+ "\nRight=” + right(P).ToString()); 　　} }

プログラム（９） private void button4_Click(object sender, System.EventArgs e) { 　 DataP =登録(DataP,50, "山　田　孝　雄", 73); 　 DataP =登録(DataP,20, "三　枝　光　一", 64); 　 DataP =登録(DataP,30, "相　田　昌　枝", 50); 　 DataP =登録(DataP,80, "徳　田　修　二", 30); 　 DataP =登録(DataP,10, "白　江　幸太郎", 55); 　 DataP =登録(DataP,25, "山　本　和　久", 70); 　 DataP =登録(DataP,45, "相　馬　栄　三", 60); 　 DataP =登録(DataP,70, "原　口　健　一", 80); 　 DataP =登録(DataP,60, "幸　田　一　雄", 90); 　 DataP =登録(DataP,55, "君　田　美智代", 75); 　 表示(); }

プログラム（１０） private void button5_Click(object sender, System.EventArgs e) { long P=氏名探索(DataP,textBox2.Text); if(P<0) MessageBox.Show("検索失敗"); else ElementData E=element(P); MessageBox.Show("\nP ="+ P.ToString()+ "\nE ="+E.番号.ToString()+ "\n氏名="+E.氏名+ "\n点数="+E.点数.ToString()+ "\nLeft="+left(P).ToString()+ "\nRight="+right(P).ToString()); }

横型探索／幅優先探索の処理 訪問するノード番号を入れる表を用意する。 探索すべきノード番号をこの表に入れる。 Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ｉ Ｊ Ｌ

横型探索／幅優先探索の処理 領域がもったいないならば， 待ち行列として実装する。 Ａ Ａ Ｂ Ｇ Ａ Ｂ Ｇ Ａ Ｂ Ｇ Ｃ Ｄ Ａ Ｂ Ｇ Ｈ Ｋ Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ （Ｃの子はない） Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ａ Ｂ Ｇ Ｃ Ｄ Ｈ Ｋ Ｅ Ｆ Ｉ Ｊ

横型探索／幅優先探索（breadth-first search） (a) N=0，I = 0，訪問ノード表[N++]=ルートとする。 (b) I < Nの間，以下を繰り返す。 　　(b-1) 訪問ノード表[I]が探索すべきノードのとき検索終わり。 　　(b-2) leftが空でなければ，leftを訪問ノード表に追加。 　　　　　（追加したとき，Ｎカウントアップ） 　　(b-3) rightが空でなければ，rightを訪問ノード表に追加。 　 (b-4) Iをカウントアップ。

横型探索／幅優先探索（breadth-first search） private long 横型探索(long P,string 氏名) { 　　long PP, PX; long Num=count(P); long [] P_Array=new long[Num]; N=0:P_Array[N++]=P; int i=0; while (i < N) PP=P_Array[i]; ElementData E=element(PP); if(string.Compare(氏名,E.氏名) == 0) return PP; PX=left(PP) ;if(PX>=0) P_Array[N++]=PX; PX=right(PP);if(PX>=0) P_Array[N++]=PX; i++; }

横型探索／幅優先探索（breadth-first search） private void button6_Click(object sender, System.EventArgs e) { long P=横型探索(DataP,textBox2.Text); 　　　　if(P<0) MessageBox.Show("検索失敗"); 　　　　else 　　　　{ ElementData E=element(P); 　　　　MessageBox.Show("\nP ="+ P.ToString() + "\nE ="+E.番号.ToString()+ "\n氏名="+E.氏名+ "\n点数="+E.点数.ToString()+ "\nLeft="+left(P).ToString()+ "\nRight="+right(P).ToString()); }

横型探索／幅優先探索（breadth-first search） private void Enque(long V,ref int N, ref long[] PA) { PA[N]=V; N++; } private long Deque(ref int N,ref long[] PA) { 　long R=PA[0];N--; for(int k=0;k<N;k++)PA[k]=PA[k+1]; return R; } private long 横型探索(long P,string 氏名) long PP,PX;string S; long Num=count(P); long [] P_Array=new long[Num]; int N=0;Enque(P,ref N,ref P_Array); int i=0; while (N>0) { PP=Deque(ref N,ref P_Array); ElementData E=element(PP); if(string.Compare(氏名,E.氏名) == 0) return PP; PX=left(PP);if(PX>=0) Enque(PX,ref N,ref P_Array); PX=right(PP);if(PX>=0) Enque(PX,ref N,ref P_Array); return -1;

横型探索／幅優先探索の処理 領域がもったいないならば， 待ち行列として実装する。 Ａ Ｂ Ｇ Ｇ Ｃ Ｄ Ｃ Ｄ Ｈ Ｋ Ｄ Ｈ Ｋ Ｈ Ｋ Ｅ Ｆ Ｋ Ｅ Ｆ Ｉ Ｊ ［凡例］ ：探索対象ノード