3．４ 線形リスト

番号 以下をクリックすると，該当箇所にジャンプします
（１） 線形リストとは
（２） 基本的な操作
（３） 応用的な操作
（４） 例題
（１）線形リストとは

データが順序付けられて並んだデータ構造をリストと
呼びます。

配列の場合，データを挿入したり削除するとき，
元のデータをずらす必要がありますが，
リストを使うと，ポインタを付け替えるだけ挿入や削除ができます。

線形リストとは，リスト構造の中で最も簡単な構造で，
各要素に１個だけのポインタを持つ構造です。



なお，本実装では，本来の意味のポインタ（アドレス）ではなく，
ポインタを配列の添え字で表していますので，
この場合のポインタをカーソル(cursor)と呼ぶこともあります。

番号 以下をクリックすると，該当箇所にジャンプします
（１） 線形リストとは
（２） 基本的な操作
（３） 応用的な操作
（４） 例題
（2）基本的な操作

リスト構造を扱う際，最も基本的な操作について以下に示します。
リスト構造の色々な操作は，
基本的には以下の操作を組み合わせることで行うことができます。

（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].Next = Next;
　　　return P;
　}

（b）先頭要素を取り出す（Lispのcarに相当)



[プログラム処理]

　private ElementData getElement(long P)
　{
　　　return DataArea[P].Element;
　 }


（c）次のリスト（Lispのcdrに相当)



[プログラム処理]

　private long next(long P)
　{
　　　return DataArea[P].Next;
　}

（d）次のポインタの置き換え（Lispのreplacdに相当)



[プログラム処理]

　private void replaceNext(long PB, long PN)
　{
　　　DataArea[PB].Next=PN;
　}


（e）要素を置き換え（Lispのreplacaに相当)



[プログラム処理]

　private void replaceElement(long P, ElementData E)
　{
　　　DataArea[P].Element=E;
　}


（f）最後のポインタ（Lispのlastに相当)



[プログラム処理]

　private long last(long P)
　{
　　　long PB = -1; long PP =P;
　　　while(P>=0){ PB=P;P=next(P); }
　　　return PB;
　}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 線形リストとは
（２） 基本的な操作
（３） 応用的な操作
（４） 例題
（3）応用的な操作

（a）要素の削除
　
　　　@）先頭要素の削除　　　：　next(P)　(Pが不要なら，Pを領域返却）
　　　A）ポインタPの後を削除 ：　P2=next(P); replaceNext(P, next(P2));
　　　　　　　　　　　　　　　　　　　　（P2が不要なら，P2を領域返却）

（b）リストの連結
　
　　P1とP2を連結
　　@）P1＝空のとき　：　P2
　　A）P1≠空のとき　：　replaceNext(last(P), P2)

（c）リストの挿入
　
　　P1の後にP2を挿入
　　@）replaceNext(P2, cdr(P1))
　　A）replaceNext(P1, P2)

番号 以下をクリックすると，該当箇所にジャンプします
（１） 線形リストとは
（２） 基本的な操作
（３） 応用的な操作
（４） 例題
（４）例題

学籍番号，氏名，点数を入力し，そのデータの登録，
氏名を検索，登録削除，成績順のソート等を行う
プログラム例を示します。

なお，動的領域管理や基本的な操作関数については，
以前に示したものを使用する。

［Program 3−4］

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;

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 登録(ElementData Element)
{
　　long PB=-1; long P=DataP;
　　ElementData tempElement; tempElement.番号=-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);
　　 　　}
　　 }
}
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);
}

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 P2=cons(Element,-1);
　　if(P2>=0)
　　{
　　　　PB=last(DataP);
 　　　　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);
　　表示();
}
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;
　　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); }
　　 }
}
private void button6_Click(object sender, System.EventArgs e)
{
　　線形リストによる単純挿入ソート();　表示();
}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 線形リストとは
（２） 基本的な操作
（３） 応用的な操作
（４） 例題
1. 基本的なアルゴリズム

2. 基本的なデータ構造

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

4. 探索

5. 再帰的アルゴリズム

6. ソート

7. 集合

8. 文字列処理

9. 色々なアルゴリズム


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