一、線形リストの抽象データ型の説明#
タイプ名：線形リスト（List）
データオブジェクト集合：線形リストは n (>=0) 個の要素から構成される順序列 (a1,a2,……,an)
操作集合：線形リスト L∈List, 整数 i は位置を示し、要素 X∈ElementType
二、順序リスト#
1. 定義#
struct LNode {
ElementType Data[MAXSIZE];//最大でMAXSIZE個の要素を格納できる配列
int Last;//最後の要素のインデックス！
};
typedef struct LNode *List;
インデックス i の要素にアクセスする：L.Data [i] または PtrL->Data [i]
線形リストの長さ：L.Last+1 または PtrL->Last+1;
2. 操作#
基本操作は以下の通りです
1.List MakeEmpty ();// 空の線形リストを初期化
2.ElementType FindKth (int K, List Ptrl);// インデックス K の要素を返す
3.int Find (ElementType X, List Ptrl);// 線形リスト L で X の最初の出現位置を探す
4.void Insert (ElementType X, int i, List Ptrl);// 位置 i の前に新しい要素 X を挿入
5.void Delete (int i, List Ptrl);// 指定された位置 i の要素を削除
6.int Length (List Ptrl);// 線形リストの長さ n を返す**
以下、順に確認していきましょう
(1) 空のリストを作成#
List MakeEmpty() {
List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL -> Last = -1;
return PtrL;
}
(2) インデックス K の要素を探す#
インデックス K の要素を返します。
ElementType FindKth(int K, List Ptrl) {
return Ptrl->Data[K];
}
(3) 要素 X を探す#
インデックスを返し、見つからなければ - 1 を返します。
int Find(ElementType X, List Ptrl) {
int i = 0;
while(i <= PtrL->Last && PtrL->Data[i] != X)
i++;
if(i > PtrL->Last) return -1;//見つからなければ-1を返す
else return i;//見つかった場合は格納位置、すなわちインデックスを返す
}
(4) 挿入#
i (1 ≤ i ≤ n+1) の位置に値 X の新しい要素を挿入します。
void Insert(ElementType X, int i, List Ptrl) {
int j;
if(Ptrl->Last == MAXSIZE-1) {//リストが満杯の場合、挿入できません
printf("リストが満杯です");
return;
}
if(i < 1 || i > Ptrl->Last+2) {//入力が妥当か確認
printf("位置が不正です");
return;
}
for(j = Ptrl->Last; j >= i-1; j--) //ここは前から後ろに順序を変えてはいけません
Ptrl->Data[j+1] = Ptrl->Data[j];
Ptrl->Data[i-1] = X;
Ptrl->Last++;//lastは最後の要素を指し続けます！
return;
}
(5) 削除#
i 番目の要素を削除します（インデックスは i-1）。
void Delete(int i, List Ptrl) {
int j;
if(i < 1 || i > Ptrl->Last+1) {//入力が妥当か確認
printf("%d番目の要素は存在しません",i);
return;
}
for (j = i; j <= Ptrl->Last; j++) //削除操作は前から後ろに行う必要があります
Ptrl->Data[j-1] = Ptrl->Data[j];
Ptrl->Last--;
return;
}
(6) 線形リストの長さ n を返す#
i 番目の要素を削除します（インデックスは i-1）。
int Length(List Ptrl){
return Ptrl->Last + 1;
}
3. 完全なコードのデモ#
//順序リスト
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定義部分
struct LNode {
ElementType Data[MAXSIZE]; //最大でMAXSIZE個の要素を格納できる配列
int Last; //最後の要素のインデックス！
};
typedef LNode *List;
// 2.操作関数
//(1) 空の線形リストを作成
List MakeEmpty() {
List Ptrl; //作成
Ptrl = new struct LNode; //最初のノードのためのメモリを割り当て
Ptrl->Last = -1; //まだデータを格納していないので、-1に設定
return Ptrl; //ポインタを返す
}
//(2) インデックスKの要素を探す インデックスKの要素を返す
ElementType FindKth(int K, List Ptrl) {
return Ptrl->Data[K];
}
//(3) 要素Xを探す インデックスを返し、見つからなければ-1を返す
int Find(ElementType X, List Ptrl) {
int i = 0;
while (i <= Ptrl->Last && Ptrl->Data[i] != X) {
i++;
}
if (i > Ptrl->Last)
return -1;
else
return i;
}
//(4) 要素Xを挿入 i(1 ≤ i ≤ n+1)の位置に値Xの新しい要素を挿入します。
void Insert(ElementType X, int i, List Ptrl) {
if (Ptrl->Last == MAXSIZE - 1) { //リストが満杯の場合、挿入できません
printf("リストが満杯です");
return;
}
if (i < 1 || i > Ptrl->Last + 2) { //入力が妥当か確認
printf("位置が不正です");
return;
}
int j;
for (j = Ptrl->Last; j >= i - 1; j--) //ここは前から後ろに順序を変えてはいけません
Ptrl->Data[j + 1] = Ptrl->Data[j];
Ptrl->Data[i - 1] = X;
Ptrl->Last++; // lastは最後の要素を指し続けます！
return;
}
//(5) 削除 i番目の要素を削除します（インデックスはi-1）。
void Delete(int i, List Ptrl) {
int j;
if (i < 1 || i > Ptrl->Last + 1) { //入力が妥当か確認
printf("%d番目の要素は存在しません", i);
return;
}
for (j = i; j <= Ptrl->Last; j++) //削除操作は前から後ろに行う必要があります
Ptrl->Data[j - 1] = Ptrl->Data[j];
Ptrl->Last--;
return;
}
//(6) 線形リストの長さnを返す
int Length(List Ptrl){
return Ptrl->Last + 1;
}
int main() {
List P;
P = MakeEmpty();
for(int i = 0; i < 10; i++){
Insert(i,i+1,P);
}
cout << "この順序リストの長さは：" << Length(P) << endl;
cout << "5番目の要素は：" << FindKth(4,P) << endl;
cout << "--4番目の要素を削除--" << endl;
Delete(4,P);
cout << "削除後の5番目の要素は：" << FindKth(4,P) << endl;
cout << "リストに要素3はありますか（あればそのインデックス、なければ-1を表示）：" << Find(3,P) << endl;
cout << "リストに要素5はありますか（あればそのインデックス、なければ-1を表示）：" << Find(5,P) << endl;
delete [] P;
return 0;
}
出力結果：
この順序リストの長さは：10
5 番目の要素は：4
--4 番目の要素を削除 --
削除後の 5 番目の要素は：5
リストに要素 3 はありますか（あればそのインデックス、なければ - 1 を表示）：-1
リストに要素 5 はありますか（あればそのインデックス、なければ - 1 を表示）：4
三、線形リストの連鎖的ストレージ#
重要！！連結リストは、論理的に隣接する 2 つの要素が物理的に隣接する必要はなく、「リンク」によってデータ要素間の論理関係を構築します。
その挿入と削除はデータ要素を移動する必要はなく、リンクを変更するだけです。
1. 定義#
typedef struct LNode *List;
struct LNode {
ElementType Data;
List Next;//次のノードを指すポインタを格納
}L;
List PtrL;
2. 操作#
基本操作は以下の通りです
1.List Insert (ElementType X, int i, List PtrL) ;// 挿入（i-1 (1<=i<=n+1) 番目のノードの後に値 X の新しいノードを挿入）
2.List FindKth (int K, List PtrL) ;// 順序で探す、連結リストの K 番目の要素を探す
List Find (ElementType X, List PtrL) ; // 値で探す：要素 K を探す
3.List Delete (int i, List PtrL);// 削除操作（連結リストの i 番目の位置のノードを削除）
4.int Length (List PtrL)// リストの長さを求める
(1) 挿入操作#
i-1 (1 ≤ i ≤ n+1) 番目のノードの後に値 X の新しいノードを挿入します。
(1) まず新しいノードを構築し、s を指します //malloc でメモリを割り当て、s のデータ Data に X を代入
(2) 次に連結リストの i-1 番目のノードを見つけ、p を指します
(3) 次にポインタを変更し、ノードを挿入します（p の後に新しいノード s を挿入）
// まず p の元の next を s の next ポインタに設定し、次に p の next ポインタを s に設定します。
List Insert(ElementType X, int i, List PtrL) {
List p, s;
if(i == 1) {//新しいノードをリストの先頭に挿入
s = (List)malloc(sizeof(struct LNode));//ノードを割り当て、データを設定
s->Data = X;
s->Next = PtrL;
return s; //新しいリストの先頭ポインタを返す
}
p = Find(i-1,PtrL); //i-1番目のノードを探す
if(p == NULL) { //i-1番目が存在しないので挿入できない
printf("パラメータiが間違っています");
return NULL;
} else {
s = (List)malloc(sizeof(struct LNode)); //ノードを割り当て、データを設定
s->Data = X;
s->Next = p->Next; //新しいノードをi-1番目のノードの後に挿入
p->Next = s;
return PtrL;
}
}
(2) 探す#
見つかればそのノードを指すポインタを返し、見つからなければ NULL を返します。
1. 値で探す：Find#
値で探す：要素 K を探します。
List Find(ElementType X, List PtrL) {
List p = PtrL;
while(p != NULL && p->Data != X)
p = p->Next;
if(p == NULL) {
cout << "その要素は見つかりません" << endl;
return NULL;
} else return p;
}
2. 順序で探す：FindKth#
順序で探す：連結リストの K 番目の要素を探します。
List FindKth(int K, List PtrL) {
List p = PtrL;
int i = 1;
while (p != NULL && i < K) {
p = p->Next;
i++;
}
if(i == K) return p;//K番目を見つけたらポインタを返す
else { //そうでなければNULLを返す
cout << "その要素は見つかりません" << endl;
return NULL;
}
}
(3) 削除操作#
連結リストの i 番目の位置のノードを削除します。
(1) まず連結リストの i-1 番目のノードを見つけ、p を指します；//Find (i-1,PtrL);
(2) 次にポインタ s を削除されるノード（p の次のノード）を指します //s = p->Next;
(3) 次にポインタを変更し、s が指すノードを削除します //p->Next = s->Next;
(4) 最後に s が指すノードのメモリを解放します！ //free (s)
List Delete(int i, List PtrL) {
List p, s;
if( i == 1) { //リストの最初のノードを削除する場合
s = PtrL; //sは最初のノードを指します
if (PtrL != NULL) PtrL = PtrL->Next; //連結リストから削除
else return NULL;
free(s); //削除されたノードを解放
return PtrL;
}
p = FindKth(i-1, PtrL); //i-1番目のノードを探す
if (p == NULL) {
printf("%d番目のノードは存在しません", i-1);
return NULL;
} else if (p->Next == NULL) {
printf("%d番目のノードは存在しません",i);
return NULL;
} else {
s = p->Next; //sはi番目のノードを指します
p->Next = s->Next; //連結リストから削除
free(s); //削除されたノードのメモリを解放
return PtrL;
}
}
(4) リストの長さを求める#
int Length(List PtrL) {
List p = PtrL;//pはリストの最初のノードを指します
int j = 0;
while(p) {
p = p->Next;
j++;
}
return j;
}
3. 完全なコードのデモ#
//連結リスト
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定義部分
struct LNode;
typedef LNode *List;
struct LNode {
ElementType Data;
List Next; //次のノードを指すポインタを格納
};
List Insert(ElementType X,int i,List PtrL);
//挿入（i-1(1<=i<=n+1)番目のノードの後に値Xの新しいノードを挿入）
List FindKth(int K, List PtrL); //順序で探す、連結リストのK番目の要素を探す
List Find(ElementType X, List PtrL); //値で探す：要素Kを探す
List Delete(int i, List PtrL); //削除操作（連結リストのi番目の位置のノードを削除）
int Length(List PtrL); //リストの長さを求める
// 2.操作関数
//(1) 挿入操作 i-1(1 ≤ i ≤ n+1)番目のノードの後に値Xの新しいノードを挿入します。
List Insert(ElementType X, int i, List PtrL) {
List p, s;
if (i == 1) { //新しいノードをリストの先頭に挿入
s = new struct LNode; //ノードを割り当て、データを設定
s->Data = X;
s->Next = PtrL;
return s; //新しいリストの先頭ポインタを返す
}
p = Find(i - 1, PtrL); //i-1番目のノードを探す
if (p == NULL) { //i-1番目が存在しないので挿入できない
printf("パラメータiが間違っています");
return NULL;
} else {
s = new struct LNode; //ノードを割り当て、データを設定
s->Data = X;
s->Next = p->Next; //新しいノードをi-1番目のノードの後に挿入
p->Next = s;
return PtrL;
}
}
//(2) 探す 見つかればそのノードを指すポインタを返し、見つからなければNULLを返します。
List Find(ElementType X, List PtrL) {//値で探す：要素Xを探します。
List p = PtrL;
while(p != NULL && p->Data != X)
p = p->Next;
if(p == NULL) {
cout << "その要素は見つかりません" << endl;
return NULL;
} else return p;
}
List FindKth(int K, List PtrL) {//順序で探す：連結リストのK番目の要素を探します。
List p = PtrL;
int i = 1;
while (p != NULL && i < K) {
p = p->Next;
i++;
}
if(i == K) return p;//K番目を見つけたらポインタを返す
else { //そうでなければNULLを返す
cout << "その要素は見つかりません" << endl;
return NULL;
}
}
//(3) 削除 削除連結リストのi番目の位置のノードを削除します。
List Delete(int i, List PtrL) {
List p, s;
if( i == 1) { //リストの最初のノードを削除する場合
s = PtrL; //sは最初のノードを指します
if (PtrL != NULL) PtrL = PtrL->Next; //連結リストから削除
else return NULL;
delete [] s; //削除されたノードを解放
return PtrL;
}
p = FindKth(i-1, PtrL); //i-1番目のノードを探す
if (p == NULL) {
printf("%d番目のノードは存在しません", i-1);
return NULL;
} else if (p->Next == NULL) {
printf("%d番目のノードは存在しません",i);
return NULL;
} else {
s = p->Next; //sはi番目のノードを指します
p->Next = s->Next; //連結リストから削除
delete [] s; //削除されたノードのメモリを解放
return PtrL;
}
}
//(4) リストの長さを求める
int Length(List PtrL) {
List p = PtrL;//pはリストの最初のノードを指します
int j = 0;
while(p) {
p = p->Next;
j++;
}
return j;
}
int main() {
List P = NULL;
for (int i = 0; i < 10; i++) {
P = Insert(i, 1, P);// 先頭挿入法でリストの先頭に要素を挿入
}
List s;
cout << "この連結リストの長さは：" << Length(P) << endl;
cout << "4番目の要素は：";
s = FindKth(4, P);
if(s) cout << s->Data << endl;
cout << "--4番目の要素を削除--" << endl;
Delete(4, P);
cout << "削除後の4番目の要素は：" ;
s = FindKth(4, P);
if (s) cout << s->Data << endl;
cout << "リストに要素6はありますか：" ;
s = Find(6, P);
if (s) cout << s->Data << endl;
cout << "リストに要素5はありますか：" ;
s = Find(5, P);
if (s) cout << s->Data << endl;
delete[] P;
return 0;
}
出力結果：
この連結リストの長さは：10
4 番目の要素は：6
--4 番目の要素を削除 --
削除後の 4 番目の要素は：5
リストに要素 6 はありますか：その要素は見つかりません
リストに要素 5 はありますか：5