Data-structures-algorithms-array-insertion-algorithm
提供:Dev Guides
配列挿入
前のセクションでは、挿入操作の仕組みを学習しました。 配列の最後に要素を挿入する必要は必ずしもありません。 以下は、配列挿入の状況になる可能性があります-
- 配列の先頭への挿入
- 配列の指定されたインデックスでの挿入
- 配列の指定されたインデックスの後の挿入
- 配列の指定されたインデックスの前に挿入
配列の先頭への挿入
挿入が最初に行われると、既存のすべてのデータ項目が1ステップ下に移動します。 ここでは、配列の先頭に要素を挿入するアルゴリズムを設計および実装します。
アルゴリズム
*A* は *N* 要素の配列であると仮定します。 格納できる要素の最大数は *MAX* で定義されます。 まず、配列に要素を格納するための空のスペースがあるかどうかを確認し、挿入プロセスを進めます。
begin
IF N = MAX, return
ELSE
N = N + 1
For All Elements in A
Move to next adjacent location
A[FIRST] = New_Element
end
Cでの実装
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {2, 3, 4, 5};
int N = 4; //number of elements in array
int i = 0; //loop variable
int value = 1; //new data element to be stored in array
//print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
//now shift rest of the elements downwards
for(i = N; i >= 0; i--) {
array[i+1] = array[i];
}
//add new element at first position
array[0] = value;
//increase N to reflect number of elements
N++;
//print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
このプログラムは、次の出力を生成する必要があります-
出力
Printing array before insertion −
array[0] = 2
array[1] = 3
array[2] = 4
array[3] = 5
Printing array after insertion −
array[0] = 0
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
配列の指定されたインデックスでの挿入
このシナリオでは、新しいデータ要素(値)を挿入する必要がある配列の正確な位置(インデックス)が与えられます。 まず、配列がいっぱいかどうかをチェックし、そうでない場合は、その場所からすべてのデータ要素を1ステップ下に移動します。 これにより、新しいデータ要素用のスペースが確保されます。
アルゴリズム
*A* は *N* 要素の配列であると仮定します。 格納できる要素の最大数は *MAX* で定義されます。
begin
IF N = MAX, return
ELSE
N = N + 1
SEEK Location index
For All Elements from A[index] to A[N]
Move to next adjacent location
A[index] = New_Element
end
Cでの実装
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {1, 2, 4, 5};
int N = 4; //number of elements in array
int i = 0; //loop variable
int index = 2; //index location to insert new value
int value = 3; //new data element to be inserted
//print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
//now shift rest of the elements downwards
for(i = N; i >= index; i--) {
array[i+1] = array[i];
}
//add new element at first position
array[index] = value;
//increase N to reflect number of elements
N++;
//print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
上記のプログラムをコンパイルして実行すると、次の結果が生成されます-
出力
Printing array before insertion −
array[0] = 1
array[1] = 2
array[2] = 4
array[3] = 5
Printing array after insertion −
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
配列の指定されたインデックスの後への挿入
このシナリオでは、新しいデータ要素(値)を挿入する必要がある配列の場所(インデックス)が与えられます。 シークプロセスのみが異なり、残りのアクティビティは前の例と同じです。
アルゴリズム
*A* は *N* 要素の配列であると仮定します。 格納できる要素の最大数は *MAX* で定義されます。
begin
IF N = MAX, return
ELSE
N = N + 1
SEEK Location index
For All Elements from A[index + 1] to A[N]
Move to next adjacent location
A[index + 1] = New_Element
end
Cでの実装
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {1, 2, 4, 5};
int N = 4; //number of elements in array
int i = 0; //loop variable
int index = 1; //index location after which value will be inserted
int value = 3; //new data element to be inserted
//print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
//now shift rest of the elements downwards
for(i = N; i >= index + 1; i--) {
array[i + 1] = array[i];
}
//add new element at first position
array[index + 1] = value;
//increase N to reflect number of elements
N++;
//print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
上記のプログラムをコンパイルして実行すると、次の結果が生成されます-
出力
Printing array before insertion −
array[0] = 1
array[1] = 2
array[2] = 4
array[3] = 5
Printing array after insertion −
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
配列の指定されたインデックスの前に挿入
このシナリオでは、新しいデータ要素(値)を挿入する前に、配列の位置(インデックス)が与えられます。 今回は、 index-1 、つまり特定のインデックスの1つ先の位置までシークします。残りのアクティビティは前の例と同じです。
アルゴリズム
*A* は *N* 要素の配列であると仮定します。 格納できる要素の最大数は *MAX* で定義されます。
begin
IF N = MAX, return
ELSE
N = N + 1
SEEK Location index
For All Elements from A[index - 1] to A[N]
Move to next adjacent location
A[index - 1] = New_Element
end
Cでの実装
#include <stdio.h>
#define MAX 5
void main() {
int array[MAX] = {1, 2, 4, 5};
int N = 4; //number of elements in array
int i = 0; //loop variable
int index = 3; //index location before which value will be inserted
int value = 3; //new data element to be inserted
//print array before insertion
printf("Printing array before insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d \n", i, array[i]);
}
//now shift rest of the elements downwards
for(i = N; i >= index + 1; i--) {
array[i + 1] = array[i];
}
//add new element at first position
array[index + 1] = value;
//increase N to reflect number of elements
N++;
//print to confirm
printf("Printing array after insertion −\n");
for(i = 0; i < N; i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
上記のプログラムをコンパイルして実行すると、次の結果が生成されます-
出力
Printing array before insertion −
array[0] = 1
array[1] = 2
array[2] = 4
array[3] = 5
Printing array after insertion −
array[0] = 1
array[1] = 2
array[2] = 4
array[3] = 5
array[4] = 3