javascriptはデータ構造を実現します.線形表--簡単な例と線形表の順序表現と実現

リニアテーブルは最も一般的で簡単なデータ構造です.一つの線形表はn個のデータ要素の有限なシーケンスである.やや複雑な線形表では、一つのデータ要素はいくつかのデータ項目から構成されてもよい.
その中:

データ要素の個数nは、表の長さ=「リスト」と定義されています.length()(「リスト」.length()=0(表裏に要素がない)の場合は、空テーブルと呼ばれます.

は、(a[0],a[1],a[2],…,a[n-1]

と、空ではない線形表(n]=0)を記載する.

データ要素a[i](0≦i≦n-1)は抽象的な記号であり、その具体的な意味は異なる場合には

と異なることができる.
一つのデータ要素はいくつかのデータ項目から構成されます.データ要素は記録と呼ばれ、大量の記録を含む線形テーブルはまたファイルと呼ばれます.このような構造は以下の特徴があります.唯一の前駆者がないデータ要素があります.唯一の後継者がいない(後尾)があります.データ要素;また、各データ要素は直接前駆者と直接後継データ要素である. 
 
リニアテーブルの記憶構造

順序表

チェーン？メーター

チェーン？テーブル

ダイナミックチェーンテーブル

静的チェーンテーブル

二重リンク計

循環リンク表

単循環リンク

ダブルサイクルチェーン

 
この場合、データ要素を記録と呼び、大量の記録を含む線形表をファイルと呼ぶことが多い.
1.2つのリニアテーブルLAとLBでそれぞれ2つのセットAとBを表すと仮定して、新しいセットA＝AUBを要求します.これはリニアテーブルLAを拡大して、線形テーブルLBに存在しなくてもいいです.
リニアテーブルLAのデータ要素はリニアテーブルLAに挿入されます.ラインテーブルLBからデータ要素ごとに順次取得し、値に従って線形テーブルLAで検索します.存在しない場合は挿入します.
以下はアルゴリズム記述(ここではjsの配列で線形表を表す)である.

 1 //       b      a        a 

 2 

 3   var a = [1, 2, 3, 4, 5];

 4   var b = [1, 3, 5, 7, 9];

 5 

 6   function union(a, b) {

 7     var elem, equal;

 8 

 9     for (var i = 0, bLen = b.length; i < bLen; i++) {

10       elem = b[i];

11       equal = false;

12 

13       for (var j = 0, aLen = a.length; j < aLen; j++) {

14         if (elem === a[j]) {

15           equal = true;

16           break;

17         }

18       }

19 

20       if (!equal) a.push(elem);

21     }

22   }

23 

24   union(a, b);

25   console.log(a);

26   // [1, 2, 3, 4, 5, 7, 9]

27 

28   //      ：O(aLen * bLen)

2.リニアテーブルLAとLBのデータ要素は値によって不順に配列されていることが知られていますが、ここではLAとLBを新たなリニアテーブルLCとしてまとめる必要があります.LCのデータ要素は値によって不順に配列されています.
2つの変数をそれぞれLAとLBのインデックスを保存し、対応する要素を比較します.

 1  1 //     a   b             

 2  2   //   a b      c，c             

 3  3   var a = [3, 5, 8, 11];

 4  4   var b = [2, 6, 8, 9, 11, 15, 20];

 5  5 

 6  6   function mergeList(a, b) {

 7  7     var c = [], aElem, bElem;

 8  8     var i = 0, j = 0, k = 0;

 9  9     var aLen = a.length;

10 10     var bLen = b.length;

11 11 

12 12     while (i < aLen && j < bLen) {

13 13       aElem = a[i];

14 14       bElem = b[j];

15 15 

16 16       if (aElem < bElem) {

17 17         c[k++] = aElem;

18 18         i++;

19 19       } else {

20 20         c[k++] = bElem;

21 21         j++;

22 22       }

23 23     }

24 24 

25 25     while (i < aLen) {

26 26       c[k++] = a[i++];

27 27     }

28 28 

29 29     while (j < bLen) {

30 30       c[k++] = b[j++];

31 31     }

32 32 

33 33     return c;

34 34   }

35 35 

36 36   var c = mergeList(a, b);

37 37   console.log(c);

38 38   // [2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20]

39 39 

40 40   //      ： O(aLen + bLen)

 
一次表の順序表示と実現
一次表の順序は、一組のアドレスで連続する記憶手段で一度にリニアテーブルを記憶するデータ要素を表します.
リニアテーブルの各要素は、l個の記憶ユニットを一時的に使用し、第一ユニットの記憶アドレスを左データ要素の記憶位置とすると、リニアテーブルのi 1番目のデータ要素の記憶位置LOC(a(i＋1)と、i番目の要素の記憶位置LOC(a(i))との間で次の関係が満たされる.
LOC(a(i+1)=LOC(a(i)+l
線形テーブルのこのような表現は、線形テーブルと呼ばれる順序記憶構造または順序マッピング(sequential mapping)を表しています.通常、このような記憶構造の線形表を順序表といいます.その特徴は、テーブルの中の隣接する要素a(i)とa(i＋1)に隣接する記憶位置LOC(a(i))を割り当てていることです.
とLOC(a(i＋1)です.つまり、コンピュータ内の要素は「物理的位置が隣接している」ということです.を選択して、線形テーブルのデータ要素間の論理関係を表します.各データ要素の記憶位置は、線形テーブルの開始位置とは1つの違いとデータ要素が線形テーブルのビット順に比例する定数です.これにより、線形テーブルを記憶する開始位置が決定されれば、線形テーブルの任意のデータ要素はランダムにアクセスできるので、線形テーブルの順序記憶構造は、1つのタイプです.ランダムアクセスの記憶構造.
高度なプログラム設計言語における配列タイプもランダムアクセスの特性があるので、データ構造における順序記憶構造を配列で記述するのが一般的である.
線形表の順序表現をより明確にするために、jsの擬似配列をシミュレートし、要素を挿入し、削除します.

 1 //                                 

 2   var a = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5};

 3   a.length = 6;

 4 

 5   function insert(a, i, elem) {

 6     if (!elem) return;

 7 

 8     var len = a.length;

 9     if (i >= len) {

10       while (len < i) {

11         a[len++] = undefined;

12         a.length++;

13       }

14       a[i] = elem;

15     } else {

16       while (len > i) {

17         a[len--] = a[len];

18       }

19       a[i] = elem;

20     }

21     a.length++;

22   }

23 

24   insert(a, 3, 8);

25   insert(a, 10, 10);

26   console.log(a);

27 

28   //                                 

29 

30   function del(a, i) {

31     var temp = a[i];

32     var j = i + 1;

33     var len = a.length;

34 

35     while (j < len) {

36       a[j - 1] = a[j++];

37     }

38     a.length--;

39     delete a[len - 1];

40 

41     return temp;

42   }

43 

44   del(a, 3);

45   console.log(a);

46   del(a, 10);

47   console.log(a);

48 

49   //      ： O(a.length)

 線形テーブルの順序記憶構造の特徴は、論理関係に隣接する2つの要素が物理的な位置にも隣接しているため、ランダムアクセステーブルのいずれかの要素を格納することができます.その記憶位置は簡単で直感的な数式で表現できます.また、この特徴は、このような記憶構造の弱点をもたらします.挿入または削除操作を行う際には、大量に移動する必要があります.元素です.この問題の解決方法、チェーン式記憶構造について次のセクションで議論します.