３．操作を伴うデータ構造
３．１ スタック
（１）データを一時的に蓄えるデータ構造のひとつ
（２）最後に入れたデータが最初に取り出される。
（３）後入れ先出し（LIFO:Last In First Out）方式とも呼ばれる。
［操作］
Ｐｕｓｈ
Ｐｏｐ
Ｐｏｐ
確認用プログラム
［画面］
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("スタックが空です");
else
{
label2.Text = Stack[--StackPointer] ;
表示();
}
}
３．２ 待ち行列（キュー）
（１）データを一時的に蓄えるデータ構造のひとつ。
（２）最初に入れたデータが最初に取り出される。
（３）先入れ先出し（FIFO:First In First Out）方式とも呼ばれる。
（４）タスクや通信等の処理待ち行列，離散系シミュレーション等，
様々な場面に使われる。
［操作］
エンキュー
(enque）
末尾
先頭
デキュー
(deque）
配列による待ち行列の実現
エンキューで最後尾に入れて，
デキューで先頭を取り出して，配列をずらす
エンキュー N
データ
3
2 1 0
デキュー
データ
確認用プログラム
［画面］
Name:label1
Text:空文字列
Name: button2
Text: Deque
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 0
デキュー
データ
データ
単純な配列では，データを取り出すたびに
配列の内容をずらす必要がある。
改良の余地がある
サイクリックな待ち行列
ポインタを進める際にＮより大なら０に戻す。
…
N
3
プログラム上の配列
終了ポインタ
待ち行列の概念的なイメージ
（サイクリックなＱｕｅ）
開始ポインタ
2 1 0
待ち行列のプログラム上の処理
［エンキュー］
①終了ポインタをカウントアップ
②終了ポインタが配列数よりおおきければ，終了ポインタを０とする。
③終了ポインタが開始ポインタと同じであれば，満杯とみなし，エラー。
④終了ポインタが示す領域にデータを設定する。 ［EnQue］
［デキュー］
①終了ポインタと開始ポインタが同じであれば,空とみなす。
②開始ポインタをカウントアップ。
③開始ポインタが配列数よりおおきければ，開始ポインタを０とする。
④開始ポインタが示す領域からデータを取り出す。
N
…
3
終了ポインタ
開始ポインタ
2 1 0
プログラム(その１）
// 宣言分部
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
氏名：浜崎拓哉
点数：７８
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;
}
番号：11048
氏名：矢田淳一
点数：８７
② 先頭要素を取り出す（GetElement)
ポインタ
（２）基本的な操作
先頭ノード
番号：11001
氏名：浅田仁志
点数：９５
末尾ノード
番号：11012
氏名：君田康司
点数：６７
番号：11025
氏名：白江雄二
点数：７６
番号：11001
氏名：浅田仁志
点数：９５
private ElementData getElement(long P)
{
return DataArea[P].Element;
}
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
（２）基本的な操作
③ 次の要素（Next)
ポインタ
先頭ノード
番号：11001
氏名：浅田仁志
点数：９５
末尾ノード
番号：11012
氏名：君田康司
点数：６７
private long next(long P)
{
return DataArea[P].Next;
}
番号：11025
氏名：白江雄二
点数：７６
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
④ 次のポインタの置き換え（ReplaceNext)
（２）基本的な操作
先頭ノード
番号：11001
氏名：浅田仁志
点数：９５
対象ポインタ
（ＰＢ）
末尾ノード
番号：11012
氏名：君田康司
点数：６７
番号：11021
氏名：佐多憲二
点数：８８
番号：11025
氏名：白江雄二
点数：７６
置き換えるポインタ
（ＰＮ）
private void replaceNext(long PB, long PN)
{
DataArea[PB].Next=PN;
}
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
（２）基本的な操作
⑤ 要素を置き換え
先頭ノード
対象ポインタ
（Ｐ）
置き換える
データ
（Ｅ）
番号：11001
氏名：浅田仁志
点数：９５
末尾ノード
番号：11012
氏名：君田康司
点数：６７
番号：11025
氏名：白江雄二
点数：７６
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11001
氏名：浅田信二
点数：９７
先頭ノード
対象ポインタ
（Ｐ）
番号：11048
氏名：矢田淳一
点数：８７
番号：11001
氏名：浅田信二
点数：９７
末尾ノード
番号：11012
氏名：君田康司
点数：６７
番号：11025
氏名：白江雄二
点数：７６
番号：11033
氏名：浜崎拓哉
点数：７８
private void replaceElement(long P, ElementData E)
{
DataArea[P].Element=E;
}
番号：11048
氏名：矢田淳一
点数：８７
（２）基本的な操作
⑥ 最後の要素
ＬａｓｔＰ
対象ポインタ
（Ｐ）
先頭ノード
番号：11001
氏名：浅田仁志
点数：９５
末尾ノード
番号：11012
氏名：君田康司
点数：６７
番号：11025
氏名：白江雄二
点数：７６
private long last(long P)
{
long PB = -1; long PP =P;
while(P>=0){ PB=P;P=next(P); }
return PB;
}
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
（３）基本的な操作を使って
①リストの生成
(Ncons dt0)
Cons dt0,-1⇒ Cons dt1,0⇒ Cons dt2,1⇒ Cons dt3,2⇒ Cons dt4,3
４
３
番号：11001
氏名：浅田仁志
点数：９５
②リストの挿入
Cons dt5,2
ReplaceNext 3,5
２
番号：11012
氏名：君田康司
点数：６７
番号：11025
氏名：白江雄二
点数：７６
５
番号：11012
氏名：君田康司
点数：６７
1
番号：11033
氏名：浜崎拓哉
点数：７８
0
番号：11048
氏名：矢田淳一
点数：８７
（３）基本的な操作を使って
③値の削除
ReplaceNext 3,2
４
３
番号：11001
氏名：浅田仁志
点数：９５
５
番号：11012
氏名：君田康司
点数：６７
２
番号：11012
氏名：君田康司
点数：６７
1
番号：11025
氏名：白江雄二
点数：７６
0
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
④要素を入れ替える⇒順序を変える
（要素のデータ量が多いとき有効）
４
番号：11001
氏名：浅田仁志
点数：９５
３
番号：11012
氏名：君田康司
点数：６７
２
番号：11025
氏名：白江雄二
点数：７６
1
0
番号：11033
氏名：浜崎拓哉
点数：７８
番号：11048
氏名：矢田淳一
点数：８７
［フォーム定義］
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)
{
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:
textBox1
Name:button3
Name:
listBox1
Name:button5
Name:button6
Name:button7
Name:button8
Name:button4
２ボタンを追加
①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）,
遠いノード／葉を子（child)，
共通の親を持つ子を兄弟（sibling）と呼ぶ
葉
葉
根
葉
節
葉
葉
葉
葉
節
節
節
上下反転
葉
葉
葉
節
葉
節
節
葉
節
葉
節
節
根
葉
葉
葉
葉
葉
３．６ 木構造
（１）木構造の用語
順序木 （ordered tree） ：兄弟関係で順序関係を持つ木
無順序木（unordered tree）：兄弟関係で順序関係を持たない木
以下の木は，順序木とみなせば異なる木であり，
無順序木とみなせば，同一の木である。
２
1
１
３
２
３
左の子（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
40
5
3
10
8
30
15
26
50
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(P < 0) return -1;
ElementData E = element(P);
if(string.Compare(氏名,E.氏名) == 0) return P;
long PL = 氏名探索(left(P),氏名);
if( PL >= 0) return PL;
return 氏名探索(right(P),氏名);
}
［フォーム定義］
Name:
textBox2
Name:
textBox1
Name:
listBox1
Name:textBox3 Name:button1
プログラム（１）
Name:button4
Name:button2
Name:button3
Name:button5
プログラム（１）
private void 表示()
{
listBox1.Items.Clear(); 要素表示(DataP,"");
}
private void 未使用領域表示()
{
listBox1.Items.Clear();
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
{
DataP =登録(DataP,50, "山 田
DataP =登録(DataP,20, "三 枝
DataP =登録(DataP,30, "相 田
DataP =登録(DataP,80, "徳 田
DataP =登録(DataP,10, "白 江
DataP =登録(DataP,25, "山 本
DataP =登録(DataP,45, "相 馬
DataP =登録(DataP,70, "原 口
DataP =登録(DataP,60, "幸 田
DataP =登録(DataP,55, "君 田
表示();
}
sender, System.EventArgs e)
孝 雄",
光 一",
昌 枝",
修 二",
幸太郎",
和 久",
栄 三",
健 一",
一 雄",
美智代",
73);
64);
50);
30);
55);
70);
60);
80);
90);
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;
}
領域がもったいないならば，
待ち行列として実装する。
Ａ
Ｂ Ｇ
Ｄ Ｈ Ｋ
［凡
例］
横型探索／幅優先探索の処理
Ｇ Ｃ Ｄ
Ｈ Ｋ Ｅ Ｆ
Ｃ Ｄ Ｈ Ｋ
Ｋ Ｅ Ｆ
：探索対象ノード
Ｉ
Ｊ

有限要素法とその誤差解析入門

第13章 工具材料 - 小山工業高等専門学校

Girls and Dragon!! - 4号館に置かれた木の机はカードゲームしやすそう

ｽｽﾞｷ ｿｳ

retry - アリエル・ネットワーク

FX-LN-MG-EBD FXコート2刃リブ溝用 FX-RB-EBD

独習Javaゼミ第10回

VLBI位相遅延を使った飛翔体の位置計測観測 ー位相接

プログラムの制御構造 選択・繰り返し

プログラミング演習I

1．1 オートマトンと状態遷移図