いっぱんせんけいひょう

基礎概念と用語
リニア・テーブルは、同じ特性を持つデータの有限シーケンスです.例えばa 1,a 2,a 3,an.ここでnは表長,a 1は表頭,anは表尾と呼ぶ.表の要素は、ヘッダーと末尾を除いて1つの前駆者と後続しかありません.論理構造ろんりこうぞう:線形秩序せんけい秩序
ちくじひょう
シーケンスストレージで実装される線形テーブルをシーケンステーブルと呼ぶ.物理構造の隣接を用いて論理的隣接を示した.作成時に最大数のMaxsizeを指定する必要があります.例えば、1 2 3 4 5 6 7ランダムアクセス(O(1))が可能であり、記憶密度が大きいことが特徴である.C言語では配列を使用してノードを格納します.次のように表示できます.

#define Maxsize 50
typedef struct Node{
	ElemType data[Maxsize];
	int length;
}ListNode;

配列は静的であっても動的であってもよい.

//    
#define Maxsize 50
ElemType data[Maxsize];

//    
#define initsize 50
ElemType *data;
data=new ElemType[initsize];

その各操作の平均時間複雑度は、シーケンス番号で検索:O(1)値で検索:O(n)平均アクセス(1+2+…+n)/n=n+1/2回データ挿入:O(n)/平均移動(0+1+2+…n)/(n+1)=n/2回データ、挿入位置下標0~n削除:O(n)/平均移動0+1+2+…+n-1/n=n-1/2回データ、削除位置下標0~n-1
チェーンテーブル
チェーン・ストレージを使用するリニア・テーブルをチェーン・テーブルと呼び、「チェーン」によってデータ・ノード間の論理関係を確立します.最大容量を考慮することなく、より柔軟に作成できます.しかし、チェーンテーブルの記憶密度は低い.たとえば、L->1->2->3->4->5->6では、Lがヘッダポインタであり、チェーンテーブルの最初のノードを指します.C言語でのストレージ構造は、以下のように表すことができる.

typedef struct Node{
	ElemType data;
	struct Node *next;
}List;

その各種操作の時間複雑度は以下の通りである:値で検索する:O(n)//検索1+2+3+...+n=1+n/2回順番にO(n)//必要なi回挿入を検索する:O(1)削除する:O(1)
チェーンテーブルが空の場合に挿入を削除するなどの操作の変更を考慮して,ヘッダノードの前にヘッダノードを加えることができる.このとき、チェーンテーブルは、L->head->1->2->3->4->5->6 headノード要素の数を空または保存できます.ヘッドポインタの利点:ヘッドポインタを加えた後の空のテーブルの処理と非空のテーブルの処理が統一されている(Lはいずれも非空のノードを指す).次に,ヘッダノードと他のノードに対する操作も統一された.チェーンテーブルが空の場合L->next=NULLとなります.
削除ノードP削除ノードpは、pの前駆ノードがpの後続ノードを指し、pを解放する.従ってpをp->nextとすることができる.

// p  q=p->next  q->next
q=p->next;
p->data=q->next;
p-next=q->next;
free(q);

ノードを挿入する2つの方法
ヘッドプラグほう
新しいノードをヘッダノードに挿入すると、L=Head->2->3のように、データが4のノードを挿入するとL=Head->4->2->3になります.

p=new(List);
p->data=i;
p->next=L->next->next;
L->next=p;

特徴:入力シーケンスの逆置きを実現できます.入力シーケンスが1,2,3の場合、ヘッドプラグ法で作成されたチェーンテーブルは、L=Head->3->2->1です.
テールプラグほう
新しいノードがテールノードに挿入されると、通常、テールポインタrが設定されます.

q=new(List);
q->data=i;
r->next=q;
q->next=null;
r=q;

特徴:元のシーケンスと同じシーケンスで、元のシーケンスの順序は変更されません.
シングルチェーンテーブルの変形
循環単一チェーンテーブル
エンドノードのnextポインタはNULLではなく、ヘッダノードLを指す.L=head->2->4->Lのように、ヘッダノードではなくテールノードが一般的に設定される.これは、テールノードを介してO(1)の下でヘッダとテーブルテールを位置決めすることができるからである.チェーンテーブルが空の場合L->next=Lです.
にほうこうチェーンテーブル
単一チェーンテーブルで前駆ノードを検索するときに最初から順番にアクセスできる不足を考慮して、各ノードにポインタpriorを追加して前駆ノードを指します.

typedef struct EListNode{
	ElemType data;
	struct EListNode *prior,*next;
}EListNode;

双方向チェーンテーブルのチェーンテーブルが空の条件は、L->next=NULLの単一チェーンテーブルと同じです.
にほうこうじゅんかんチェーンテーブル
双方向チェーンテーブルのループ表示.すなわち、最後のノードのnextポインタはLを指し、Lのpriorポインタは最後のノードを指す.双方向ループチェーンテーブルが空の場合、L->next=L->prior=NULLがあります.
静的チェーンテーブル
静的チェーンテーブルは配列によってチェーンテーブル機能を実現する.ノードのポインタドメインは、ノードの相対アドレス、すなわち配列の下付きであり、カーソルとも呼ばれる.次のようになります.
2
b
6
a
1
d
-1
c
3
チェーンテーブルはL=a->b->c->d静的チェーンテーブルnext=-1を終了のフラグとすることができる.