3．5 循環・重連結リスト

番号 以下をクリックすると，該当箇所にジャンプします
（１） 循環リスト
（２） 重連結リスト(双方向リスト）
（３） 重連結リストにおける基本操作
（４） 例題
（１）循環リスト

末尾ノードに先頭ノードを指すポインタを入れることで
環状に並んだデータの並びを自然な形で表現できます。

このようなリストを循環リスト(circular list)と呼びます。



線形リストに，以下の赤字のような処理を追加することで，
循環リストを表現することができます。

　　　long P1,P2; 初期化(); DataP=-1;
　　　データ登録(1,"福　田　武　夫",40);
 　　　データ登録(2,"佐　藤　栄　二",20);
 　　　　・
 　　　　・
 　　　　・
 　　　データ登録(8,"澤　田　幸　一",30);
 　　　DataArea[last(DataP)].Next=DataP;
ボタン(button1)をクリックすると，リストボックスの選択位置が
変更されるようなプログラムを作って確認してみましょう。

なお，線形リストの最後の検出は，空ポインタで判定しますが，
循環リストでは，先頭ポインタと同じであれば最後として判定します。

［Program 3−5］　循環リストの確認プログラム

　　　

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();
}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 循環リスト
（２） 重連結リスト(双方向リスト）
（３） 重連結リストにおける基本操作
（４） 例題
（2）重連結リスト（双方向リスト）

後続ノードへのポインタだけでなく，先行ノードへのポインタをも持たせたリストを
重連結リスト（dubly linked list）または双方向リストと呼びます。

線形リストでは，先行するノードを見つけるには，
先頭からスキャンする必要がありますが，

重連結リストでは，直接見つけることができます。



データ構造上は，前方向へのポインタを追加します。

　　public struct ElementSet
　　{
　　　　public ElementData Element;
　　　　public long Befor;　// この部分を追加
　　　　public long Next;
　　 }

領域管理は，線形リストのときと同じです。

線形リストとの相違は以下のとおりです。

@）Beforに対する操作が増える。
A）操作における処理が異なるものがある。

番号 以下をクリックすると，該当箇所にジャンプします
（１） 循環リスト
（２） 重連結リスト(双方向リスト）
（３） 重連結リストにおける基本操作
（４） 例題
（３）重連結リストにおける基本操作

（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 replaceNext(long PB, long PN)
　{
　　　DataArea[PB].Next=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;
　}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 循環リスト
（２） 重連結リスト(双方向リスト）
（３） 重連結リストにおける基本操作
（４） 例題
（４）例題

線形リストで使った例題を重連結リストで表現してみます。
なお，ポインタを明示的に表示するために，
表示モードを切り替える処理を追加します。

［Program 3−6］

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 ポインタ表示();
}
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;
}
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);
　　}
}
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);
　　}
}
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;
}
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);
}
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);}
　}
}
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();
　}
}
private void button7_Click(object sender, System.EventArgs e)
{
　　表示モード=0;　表示();
}
private void button8_Click(object sender, System.EventArgs e)
{
　　表示モード=1;　表示();
}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 循環リスト
（２） 重連結リスト(双方向リスト）
（３） 重連結リストにおける基本操作
（４） 例題
1. 基本的なアルゴリズム

2. 基本的なデータ構造

3. 操作を伴うデータ構造

4. 探索

5. 再帰的アルゴリズム

6. ソート

7. 集合

8. 文字列処理

9. 色々なアルゴリズム


上のタイトルをクリックします