線形テーブルとデュアルチェーンテーブルを実現する方法を簡単に紹介します

線形メーターは線形構造であり、同じタイプn（n≥0）のデータ要素を持つ限られたシーケンスです。

1。配列
アレイには上限と下限があり、アレイの要素は上限と下限で連続しています。

10、20、30、40、50 50の配列の概略図は次のとおりです。

配列の機能：データは連続しています。
やや複雑なアレイは、多次元配列と動的配列です。 C言語の場合、多次元配列も1つの次元配列によって実現されます。動的なアレイについては、動的に成長できるインデックスグループの容量の配列ですベクター。

第二に、1つのリンクリスト<br /> 1つのリンクリスト（単一のリンクリスト）は、各ノードに含まれるリンクリストの一種です。

単一のリンクリストの概略図は次のとおりです。

頭の頭は空で、頭の後継ノードは「ノード10」（データ10のノード）、「ノード10」の後継ノードは「ノード20」（データ10のデータ）です。 ..

シングルチェーン削除ノード

「ノード30」を削除します
削除する前：「ノード20」の後継ノードは「ノード30」であり、「ノード30」の後継ノードは「ノード40」です。
削除後：「ノード20」の後継ノードは「ノード40」です。

単一のリンクリストが追加されたノードが追加されました

「ノード10」と「ノード20」の間に「ノード15」を追加します
追加する前：「ノード10」の後継ノードは「ノード20」です。
追加後：「ノード10」の後継ノードは「ノード15」であり、「ノード15」の後継ノードは「ノード20」です。

単一のリンクリストの特徴は、ノードのリンク方向が配列と比較して、単一のチェーンリストのランダムアクセス速度が遅いことですが、単一リンクリストの削除/追加データが高くなっています。

第三に、2回のリンクリスト
2つのウェイリンクリスト（デュアルリンクリスト）は、リンクされたリストの一種です。単一のリンクリストと同様に、デュアルチェーンリストはノードにも構成されています。したがって、2つのウェイリンクリストの任意のノードから開始すると、フロントドライブノードとその後のノードに簡単にアクセスできます。一般的に、私たちは皆、2つの回路リンクリストを作成します。

デュアルリンクリストの概略図は次のとおりです。

ヘッダーは空で、ヘッドの後継ノードは「ノード10」です。後継者は、「ノード10」の後継ノードである「ノード30」で、「ノード30」のプリノードは「ノード20」です。 。

ダブルチェーンウォッチ削除ノード

「ノード30」を削除します
削除する前：「ノード20」の後継ノードは「ノード30」であり、「ノード30」のプレノードは「ノード20」です。 「ノード30」の後継ノードは「ノード40」であり、「ノード40」のプレノードは「ノード30」です。
削除後：「ノード20」の後継ノードは「ノード40」であり、「ノード40」のプレノードは「ノード20」です。

ダブルリンクリストノードの追加

「ノード10」と「ノード20」の間に「ノード15」を追加します
追加する前：「ノード10」の後継ノードは「ノード20」であり、「ノード20」の前のノードは「ノード10」です。
追加後：「ノード10」の後継ノードは「ノード15」であり、「ノード15」のプレノードは「ノード10」です。 「ノード15」の後継ノードは「ノード20」であり、「ノード20」の前のノードは「ノード15」です。

デュアルチェーンリストの実装を以下に紹介し、C/C ++/Javaの3つの実装をそれぞれ導入します。

1。Cデュアルリンクリストを実装します

コード2-ウェイリンクリストファイル（double_link.h）を実装する

＃ifndef_double_link_h＃define_double_link_h //「2つのウェイリンクリスト」を作成します。成功、それ以外の場合は、nullextern int create_dlink（）を返します。成功、それ以外の場合は、-1Extern int destroy_dlink（）に戻ります。空虚の場合は1に戻ります。 extern int dlink_is_empty（）;成功して、ノードポインターに戻ります。 extern void* dlink_get（int index）;成功して、ノードポインターに戻ります。 extern void* dlink_get_first（）;成功して、ノードポインターに戻ります。 extern void* dlink_get_last（）; //「値」をインデックス位置に挿入します。成功、それ以外の場合は-1を返します。 extern int dlink_insert（int index、void *pval）;成功、それ以外の場合は-1を返します。 extern int dlink_insert_first（void *pval）;成功、それ以外の場合は-1を返します。 extern int dlink_append_last（void *pval）;成功、それ以外の場合は、-1Extern int dlink_delete（int int index）に戻ります。成功、それ以外の場合は、-1Externにdlink_delete_first（）に戻ります。成功、0;

Double_link.cは2回のリンクリストのリストです

#include <stdio.h> #include <malloc.h>/*** c Lingleの2つのリンクリストは任意のデータを保存できます。 ** @author skywang @日付2013/11/07ヘッドの値は要素値を保存しないことに注意してください！交差点交差点staticノード *phead = null; static count = 0; //新しい「ノード」を作成します。成功して、ノードポインターに戻ります。 static node *create_node（void *pval）{node *pnode =（node *）malloc（sizeof（node））; "）; return null;} //デフォルト、最初のノード、およびPNodeの後者のノードはそれ自体のpnode-> prev = pnode-> next = pnode; //ノードの値はpvalpnode-> p =ですpval; /「2回のリンクリスト」を作成します。成功、それ以外の場合は-1を返します。 int create_dlink（）{// fead = create_node（null）; return count == 0;} //「2つのウェイリンクリスト」に戻るint dlink_size（）{return count;} //「2つの方向リンクリストのインデックス位置のノード」を取得します。 node（node（int index）{ifx <0 || index> = count）{printf（ "％s failed or bound！/n"、__func __）;} // if（count/2））{int i = 0; int j = 0; node "static node * g et_first_node（）（）return get_node（0）;} //" last node "static node * get_last_node（）{return get_node（count-）;} //取得双方向リンクリストで」。成功、returnノード値、return -1。 void * dlink_get（int index）{node * pindex = get_node（！pindex）; 1个元素的值” void* dlink_get_first（）{return dlink_get（0）;} // 「PVal」をインデックス位置に挿入します。成功、それ以外の場合は-1を返します。 int dlink_insert（int index、void * pval）{//ヘッダーを挿入if（index == 0）return dlink_insert_first（pvalt（pval）; //挿入する位置に対応するノードノードを取得します。 if！pindex）return -1; // - > prev> pnode-> prev = pnode+1count ++;} {node e = create_node（！pnode）; ++; ; pnode-> pehead-> phead-> pret = pnode;}ウェイリンクリスト」。成功、それ以外の場合は-1を返します。 int dlink_delete（int index）{node *pindex = get_node（！pindex）; > next-> prev = pindex->​​ prev; pindex->​​ prev-> next = pindex->​​ next; free（pindex）; count-; return 0;} // dlink_delete（0）;} // delete a node int dlink_delete_last（）{return dlink_delete（count-）;} // revisit "2方向リンクリスト" "。成功、それ以外の場合は-1を返します。 int destroy_dlink（）{if（！phead）{printf（ "％s failed！dlink is null！/n"、__func __）; while（pnode）{pnode-> free;}

2つのウェイリンクリストテストプログラム（dlink_test.c）

 #include <stdio.h> #include "double_link.h"/*** c言語2ウェイリンクリストテストプログラムを実装します。 **（01）int_test（）* 2回のリンクリストで「int data」を示します。 *（02）string_teest（）* 2回のリンクリストで「strine data」を示します。 *（03）object_teest（）* 2回のリンクリストで「オブジェクト」を示します。 ** @author skywang* @date 2013/11/07* /// 2ウェイリンクリスト操作int void int_teest（）{4] = {10、20、30、40}; n -----％s ------ "、__func __）; create_dlink（）; //双方向リンクリストdlink_insert（0、＆iarr [0]）; //データdlink_insertを挿入する（＆＆ig＆＆＆ig＆＆＆＆1]）; data printf（ "dlink_is_empty（）=％d/n"、dlink_is_empty（））; 2つのウェイリンクリストINT Iのサイズ *P =（I ++）; ）DLINK_GET（I）; Twenty "、" 30 "、" fringf（ "/n ----％s  - /n"、__func __）; 0、SARR [0]）; 2つのリンクリスト。 n "、dlink_size（））; // 2つのウェイリンクリストのサイズ0; i <sz; tag_stu {int id [20];} stu; {40、{40、{40、{40、 "dan"}、};＃define arr_stu_size "、__func __）; create_dlink（）; // 2 -wayリンクリストdlink_insert（0、＆arr_stu [0]を作成する）//データdlink_insert（0、＆arr_stu [1]）は、2つのリンクリストdlink_insert（0、＆arr_stu [2]）に挿入します。 "dlink_is_empty（）=％d/n"、dlink_is_empl（））; 2つのリンクリスト// 2つのリンクリストint sz = dlink_size（）for; ）dlink_get（i）; "dlink_get（％d）= [％d、％s]/n"、i、p-> p-> name）;} destroy_dlink（）;} int main（）{int_test（ ）; string_test（）; object_test（）; 0;}

ランニング結果

---- int_test ---- dlink_is_empty（）= 0dlink_size（）= 3dlink_get（0）= 30d_get（1）= 20dlink_get 0dlink_size（）= 3dlink_get（0）= thirtydlink_get（1）= Twentydlink_get（2）= Ten-- -  object_test ---- dlink_is_empty（）= 0dlink_size（）= 3dlink_get（0）= [30、vic] dlink_get（1）= [20、jody] dlink_get（2）= [10、空]

2。C++はデュアルチェーンリストを実現します

コード2-ウェイリンクリストファイル（doublelink.h）を実装する

#ifndef define define double_link_hxx prev、dnode）{this> this> prev = next;} size（）get_first（）; int delete_last（）; ）{//「速度」を作成します。注：頭にストレージデータはありません！ phead = new dnode <t>（）; phead-> phead- = phead; > :: 〜doughlink {//すべてのノードdnode <t>* pnode = phead-> next; ; ptmpを削除します;} //「head」delete phead = null;}チェーンリスト为空テンプレート<クラスt> int doublelink <t> :: is_empty（）{return count == 0;} //获取第インデックス<class t> dnode <t>* doublelink <t>： ：get_node（int index）{//判断パラメーターの有効性（index <0 || index> = cout）{node failed！ / IF（index <= count/ 2）{int i = 0; ;} / / revers int j = 0; ; / /インデックス位置のノードの値<クラスt> t doublelink <t> :: get（int index）{return get_node（index） - > value;} //最初のノードの値を取得しますTemple <class t> trivelink <t> :: get_first（）{return get_node（0） - > value;} //最後のノードの値を取得します;} //ノードを挿入しますテンプレート前のインデックス位置<クラスT> int doublelink <t> :: insert（int index、t t）{ifx == 0）return insert_first（t）;; > prev） - > pindex->​​ pnode ++;テンプレート<クラスT> int doublelink <t> :: insert_fring（t）{dnode <t>* new dnode <t>（t、phead-> next-> phead- > pnode ++;} > prev = pnode ++;} > next> prev = pindex->​​ next = pindex->​​ count;} // t> int doublelink <t> :: delete_first（）{return del（0）;} // #endif

2つのウェイリンクリストテストファイル（dlinktest.cpp）

 #include <iostream> #include "doublelink.h" userspace std; --- "<< endl; //双方向リンクリストを作成しますdoubleLelink <int>* pdlink = new doublelink <int>（）; pdlink-> insert（0、20）; //最初の位置に20を挿入しますpdlink-> append_last（10）; << "is_empty（）=" << pdlink-> is_empty（）<< endl; << endl;すべてのデータ= pdlink-> size（）; - > get（i）<< endl;} void string_test（）{string sarr [4] = {"Ten"、 "Twenty"、 "30、" forty "}; --- "" << endl;最初のpdlink-> append_last（sarr [0]）への2番目の要素。 ）ポジション//双方向のリンクリストが空であるかどうか<< "<< pdlink-> is_empty（）<< endl; （）= "<< pdlink-> size（）<< endl; //すべてのデータint sz = pdlink-> size（）; for（int i = 0; i <sz; i ++）" <"） = "<< pdlink-> get（i）<< endl;} struct stu {int id; char name [20];}; static stu arr_stu [] = {10、" sky "}、{20 20、" jody "}、{30、" vic "}、{40、" dan "}、}; Way Linked List doublelink <Stu>* pdlink = new Doublelink <Stu>（）; > append_last（arr_stu [0]）;最初の位置へ//双方向リンクリストが空であるかどうか<< "is_empty（）=" << pdlink-> is_empty（）<< endl; = "<< pdlink-> size（）<< endl; //すべてのデータint sz = pdlink-> size（）を双方向リンクリスト; = 0; i <sz; i ++）{p = pdlink-> get（i）; main（）{int_teest（）; string_test（）; object_test（）; 0;}

例の説明

上記の例では、ヘッダーファイルに2つのウェイリンクリストの「ステートメント」と「実装」を配置します。プログラミングの仕様は私たちに警告します：クレームの宣言と実装を分離し、ヘッダーファイル（.hファイルまたは.hpp）の金額にはステートメントのみが含まれ、実装ファイル（.cppファイル）での実装の責任がありました。
では、なぜこれをするのですか？これは、2回のリンクリストの実装では、テンプレートが採用されているためです。簡単に言えば、doublelink.hで宣言され、doublelink.cppで実装されている場合。特定の理由から、「C ++コンパイラがテンプレートの個別のコンパイルをサポートできない理由」を参照できます。

ランニング結果

---- int_test ---- is_empty（）= 0size（）= 3pdlink（0）= 30pdlink（1）= 20pdlink（2）= 10 ----- string_test ----- empty（）0size（） = 3pdlink（0）= thirtypdlink（1）= twentypdlink（2）= ten ---- object_teest ---- is_empty（）= 0size（）= 3pdlink（0）= [30、vic] pdlink（1）= [ 20 20、jody] pdlink（2）= [10、空]

3。Javaはデュアルチェーンリストを実現します

doublelink.javaの実装

/*** Javaの2つのリンクリスト。 *注：Javaのコレクションパッケージには、2つのウェイリンクリストがあります。Java.util.linkedList** @author skywang* @date 2013/11/07*/public class doublelink {/ / TOP HEADPATE <T> mhead。 {this.value = value; prev = next;}注：頭にストレージデータはありません！ mhead = new dnode <t>（null、null、null）; return mcount;} //リンクされたリストが空であるかどうかisempty（）{return mcount == 0;} //ノードプライベートdnode <t> getNode（int index）{ifx）{index <0 || Mcount）は、IFを検索します;} // dnode <t> rnode = mhead.prev; int rindex = mcount -1; /インデックス位置の値を取得します。} //最後のノードの値を取得します。 <t>、mhead.next.prev = node;;; t>（inode.prev、inode.prev.next = tnode;} //ノードを挿入します。 public void insertFirst（t t）{insert（0、t）;} // public void appendlast（t）のリンクリストの最後にノードを追加します{dnode <t> new dnode <t>（t、mhead。 prev mhead.prev.node.prev = node;} .next = inext.next.prev = inode = null;}ノードpublic void deletelast（）{del（mcount-）;}}

テストプログラム（dlinktest.java）

 /*** Javaの2つのリンクリスト。 *注：Javaに付属の2つのウェイリンクリストがあります。Java.util.linkedList** @author skywang* @date 2013/11/07*/public class {// 2つのリンクテーブル操作INT Private void int_teest（）{10、20、30、40} = new doublelink <integer>（）;最初の位置// 2つのウェイリンクリストが空のsystem.out.printf（ "isempty（）=％b/n"、dlink.isempty（））; d/n "、dlink.size（））; //すべてのノードを（int i = 0; i <dlink.size（）; i ++）system.out .println（" dlink（ "+i+"））のすべてのノードを印刷します。 = "+dlink.get（i））;} private static void string_test（）{] sarr = {" ten "、" thirty "、" forty ""}; /n ---- string_test ---- "）; // 2ウェイリンクリストを作成しますdoublelink <string> dlink = new doublelink <string>（）; [1]）; // sarrに2番目の要素を挿入します最初の位置にdlink.appendlast（sarr [0]）;最初の位置// 2つのウェイリンクリストが空のsystem.out.printf（ "isempty（）=％b/ n"、dlink.isempty（））;// system.out.printf（ "size（） =％d/ n "、dlink.size（））; //すべてのノードを（int i = 0; i <dlink.size（）; i ++）system.out.println（" dlink（ "+i+ "）="+dlink.get（i））;} // Internal Class Private Static Class Student {int id、string name）{this.id = id;}@ ouverridepublic string toString（）{"+id+"、 "+name+"] ";} tudent [] studers = new Student [] {new Student（10、" Sky "）、New Student（20、" Jody "）、new学生（30、 "vic"）、新しい学生（40、dan "）、};双方向のリンクリスト<Student> dlink = new DoubleLink <Student> [1]）; dlink.insertfirstの最初の要素（学生[学生[2]）; printf（ "isempty（）=％b/n"、dlink.isempty（））;ノード（int i = 0; i <dlink.size（））; system.out.println（ "dlink（"+i+"）="+dlink.get（i））;}} public static void main（string [] arts）{int_test（）; string_test（）; object_test（）; }}

ランニング結果

---- int_test ---- isempty（）= falsesize（）= 3dlink（0）= 30dlink（1）= 20dlink（2）= 10 ----- string_test —-- isempty（）= falsesize（）= 3dlink（0）= thirtydlink（1）= twentydlink（2）= 10 ---- object_teest --- isempty（）= falsesize（）= 3dlink（0）= [30、vic] dlink（1）= [20 20 、jody] dlink（2）= [10、空]

上記は、この記事のすべての内容です。