データ構造——線形テーブル(逐次記憶)
リニア・テーブルのシーケンス・ストレージ
シーケンス格納された線形テーブルをシーケンステーブルと呼ぶ
ちくじきおく
特長
ビルド
モード
1アドレス連続、2ランダムアクセス、3シーケンス格納
1ヘッダアドレス、2ストレージ容量、3テーブル長
1静的、2動的
物理順序記憶方式
配列の下付き
ちくじひょう
メモリアドレス
0
a1
LOC(A)
1
a2
LOC(A)+sizeof(Elemtype)
…
…
…
i-1
ai
LOC(A)+(i-1)*sizeof(Elemtype)
…
…
…
n-1
an
LOC(A)+(n-1)*sizeof(Elemtype)
…
…
…
MaxSize-1
…
LOC(A)+(MaxSize-1)*sizeof(Elemtype)
メリットとデメリット
メリット
欠点
ストレージ密度が高く、要素の論理関係に余分なスペースを開く必要はありません.
挿入と削除操作には大量の要素を移動する必要があり,平均時間複雑度O(n)
ランダムアクセス、テーブル内の任意の要素への高速アクセス
ストレージに対する要求が高く、ストレージフラグメントが発生します.
(ランダムアクセスという概念は重要であり、ストレージではないことに注意してください)
順序記憶1、線形テーブルは論理構造であり、記憶ユニットのアドレスが連続している.シーケンステーブルとチェーンテーブルは格納構造である.2、線形表の順序表示
3、順序表の操作挿入操作順序表のi番目の要素の位置に新しい要素eを挿入する
削除操作順序テーブルのi番目の要素を削除し、削除要素の値をeに割り当て、返します.
値別検索順序テーブルLで最初の要素eの要素を検索し、そのビットシーケンスを返します.
練習問題1、順序表から最小値を持つ要素を削除し(一意と仮定)、関数から削除された要素の値を返します.空の位置に最後の要素が埋め込まれ、順序表が空の場合はエラーメッセージが表示され、実行を終了します.
2、効率的なアルゴリズムを設計して、順序表Lの中のすべての要素を逆置して、アルゴリズムの空間複雑度がO(1)であることを要求する.
3、長さnのシーケンステーブルLについて、線形テーブルのすべての値xの要素を削除する時間複雑度O(n)、空間複雑度O(1)のアルゴリズムを作成する.
このコードが与える消去方法は確かに思いもよらなかったが、暗記すればいい.
4、秩序テーブルからその値を所与の値sとtの間に削除する(s注意が必要で、この問題は秩序テーブルである
5、順序表からその値を所定値sとtの間に削除する(要求s
6、順序テーブルから値が重複するすべての要素を削除し、テーブル内のすべての要素が異なるようにします.
7、2つの順序テーブルを新しい順序テーブルに結合し、関数から結果順序テーブルを返す.典型的な方法は、しっかりと身につける.
8、一次元配列A[m+n]に2つの線状表(a 1,a 2,a 3...am)と(b 1,b 2,b 3...bn)を順次格納することが知られている.配列内の2つの順序テーブルの位置を交換し、(b 1,b 2,b 3...bn)を前に置く関数を作成してみます.これは王道が与えたコードで、確かに非常に効率的です.
私が自分でやれば、きっと新しい配列を開くに違いない.
9、線形テーブル(a 1,a 2,a 3...an)の要素は、逐次秩序化され、コンピュータ内に格納される.テーブル内の数値xの要素を最小時間で検索し、見つけたら後続の要素の位置と交換し、見つからない場合はテーブルに挿入し、テーブル内の要素を秩序正しく増加させるアルゴリズムを設計する必要があります.
10、【2010統一試験本題】n(n>1)個の整数を一次元配列Rに格納する.時間と空間の両方で可能な限り効率的なアルゴリズムを設計し、Rに格納されたシーケンスを左シフトp(0は(X 0,X 1,...,Xn−1)から(Xp,Xp+1,...,Xn−1,X 0,X 1,...,Xp−1)に変換する. 要求:1)アルゴリズムの基本設計思想を与える2)設計思想に基づいて,CあるいはC++あるいはJava言語記述アルゴリズムを採用し,肝心な点は注釈を与える3)アルゴリズムの時間複雑度と空間複雑度を説明する
11、【2011統一試験本題】長さL(L>=1)の昇順シーケンスSは、L/2番目の位置にある数をSの中位数と呼び、2つのシーケンスの中位数は、それらのすべての要素を含む昇順シーケンスの中位数である.既存の2つの昇順シーケンスAとBは,時間と空間の両方で可能な限り効率的なアルゴリズムを設計し,ABの中位数を探し出すことを試みた.要求:1)アルゴリズムの基本設計思想を与える2)設計思想に基づいて,CあるいはC++あるいはJava言語記述アルゴリズムを採用し,肝心な点は注釈を与える3)アルゴリズムの時間複雑度と空間複雑度を説明する
シーケンス格納された線形テーブルをシーケンステーブルと呼ぶ
ちくじきおく
特長
ビルド
モード
1アドレス連続、2ランダムアクセス、3シーケンス格納
1ヘッダアドレス、2ストレージ容量、3テーブル長
1静的、2動的
物理順序記憶方式
配列の下付き
ちくじひょう
メモリアドレス
0
a1
LOC(A)
1
a2
LOC(A)+sizeof(Elemtype)
…
…
…
i-1
ai
LOC(A)+(i-1)*sizeof(Elemtype)
…
…
…
n-1
an
LOC(A)+(n-1)*sizeof(Elemtype)
…
…
…
MaxSize-1
…
LOC(A)+(MaxSize-1)*sizeof(Elemtype)
メリットとデメリット
メリット
欠点
ストレージ密度が高く、要素の論理関係に余分なスペースを開く必要はありません.
挿入と削除操作には大量の要素を移動する必要があり,平均時間複雑度O(n)
ランダムアクセス、テーブル内の任意の要素への高速アクセス
ストレージに対する要求が高く、ストレージフラグメントが発生します.
(ランダムアクセスという概念は重要であり、ストレージではないことに注意してください)
順序記憶1、線形テーブルは論理構造であり、記憶ユニットのアドレスが連続している.シーケンステーブルとチェーンテーブルは格納構造である.2、線形表の順序表示
//
#define MaxSize 50 //
typedef struct{// ： 1 ， 0
ElemType data[MaxSize];
int length;
}SqList;
//
#define InitSize 100 //
typedef struct{
ElemType *data;
int MaxSize,length;
}SeqList;
SeqList L;// L
L.data=new ElemType[InitSize];
// ， ， ，
3、順序表の操作挿入操作順序表のi番目の要素の位置に新しい要素eを挿入する
bool ListInsert(SqList &L,int i,Elemtype e){
if(i<1||i>L.length+1)// i
return false;// 1， length，length+1
if(L.length>=MaxSize)// ，
return false;
for(int j=L.length;j>=i;j--)// ， length ， 0
L.data[j]=L.data[j-1];
L.data[i-1]=e;// ， i-1， 0
L.length++;
return true;
}
削除操作順序テーブルのi番目の要素を削除し、削除要素の値をeに割り当て、返します.
bool ListDelete(SqList &l,int i,Elemtype &e){
if(i<1||i>L.length)
return false;
e=L.data[i-1];
for(int j=i;j<L.lenth;j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}
値別検索順序テーブルLで最初の要素eの要素を検索し、そのビットシーケンスを返します.
int LocateElem(Sqlist L,ElemType e){
int i;
for(i=0;i<L.length;i++){
if(L.Data[i]==e){
return i+1;
}
}
}
練習問題1、順序表から最小値を持つ要素を削除し(一意と仮定)、関数から削除された要素の値を返します.空の位置に最後の要素が埋め込まれ、順序表が空の場合はエラーメッセージが表示され、実行を終了します.
bool Del_Min(SqList &L,ElemType &value){
// L ， value
// ， true； false
if(L.length==0)return false;
value=L.data[0];// value
int pos=0;
for(int i=0;i<L.length;i++){
if(L.data[i]<value){
value=L.data[i];
pos=i;
}
}
L.data[pos]=L.data[L.length-1];//
L.length--;
return true;
}
2、効率的なアルゴリズムを設計して、順序表Lの中のすべての要素を逆置して、アルゴリズムの空間複雑度がO(1)であることを要求する.
void Reverse(SqList &L){
if(L.length==0)return false;
if(L.length==1)return true;
ElemType temp;
for(int i=0;i<L.length/2;i++){
temp=L.data[i];
L.data[i]=L.data[L.length-1-i];
L.data[L.length-1-i]=temp;
}
return true;
}
3、長さnのシーケンステーブルLについて、線形テーブルのすべての値xの要素を削除する時間複雑度O(n)、空間複雑度O(1)のアルゴリズムを作成する.
void Del_x(SqList &L,ElemType x){
int k=0,i=0;
for(;i<L.length;i++){
if(L.data[i]!=x){
L.data[k]=L.data[i];
k++;// k x
}
}
L.length=k;
}
:
[a] [b] [x] [c] [d] [x] [e]
k=0 i=0
[a] [b] [x] [c] [d] [x] [e]
k=1 i=1
[a] [b] [x] [c] [d] [x] [e]
k=2 i=2
[a] [b] [x] [c] [d] [x] [e]
k=2 i=3
[a] [b] [c] [c] [d] [x] [e]
k=3 i=4
[a] [b] [c] [d] [d] [x] [e]
k=4 i=5
[a] [b] [c] [d] [d] [x] [e]
k=4 i=6
[a] [b] [c] [d] [e] [x] [e]
k=5 for
L.length = 5
[a] [b] [c] [d] [e]
このコードが与える消去方法は確かに思いもよらなかったが、暗記すればいい.
4、秩序テーブルからその値を所与の値sとtの間に削除する(s注意が必要で、この問題は秩序テーブルである
bool Del_s_t(SqList &L,ElemType s,Elemtype t){
int i,j;
if(s>=t||L.length==0)// s t ，
return false;
for(i=0;i<L.length&&L.data[i]<s;i++);// s
if(i>=L.length)// s，
return false;
for(j=i;j<L.length&&L.data[j]<=t;j++);// t
for(;j<L.length;i++,j++)
L.data[i]=L.data[j];
L.length=i;
return true;
}
[a] [b] [s] [c] [d] [t] [e]
i for ，i=2
j for ，j=6
for
i=2 j=6
[a] [b] [e] [c] [d] [t] [e]
i=3 j=7
L.length=3
[a] [b] [e]
5、順序表からその値を所定値sとtの間に削除する(要求s
bool Del_s_t(SqList &L,Elemtype s,Elemtype t){
int i,k=0;
if(L.length==0||s>=t)
return false;
for(i=0;i<L.length;i++){
if(L.data[i]>=s&&L.data[i]<=t){
k++;
}else{
L.data[i-k]=L.data[i];
}
}
L.length-=k;
return true;
}
[a] [b] [s] [c] [d] [t] [e]
i=0 k=0
[a] [b] [s] [c] [d] [t] [e]
i=1 k=0
[a] [b] [s] [c] [d] [t] [e]
i=2 k=0
[a] [b] [s] [c] [d] [t] [e]
k=1 i=3
[a] [b] [c] [c] [d] [t] [e]
k=1 i=4
[a] [b] [c] [d] [d] [t] [e]
k=1 i=5
[a] [b] [c] [d] [d] [t] [e]
k=2 i=6
[a] [b] [c] [d] [e] [t] [e]
k=2 i=7
L.length=L.length-k
6、順序テーブルから値が重複するすべての要素を削除し、テーブル内のすべての要素が異なるようにします.
bool Del_Same(SqList &L){
if(L.length==0)
return false;
int i,j;//i j
for(i=0,j=1;j<L.length;j++){
if(L.data[i]!=L.data[j]){
L.data[++i]=L.data[j];
}
}
L.length=i+1;
return true;
}
[a] [b] [b] [c] [d] [e] [e]
i=0 j=1
[a] [b] [b] [c] [d] [e] [e]
i=1 j=2
[a] [b] [b] [c] [d] [e] [e]
i=1 j=3
[a] [b] [c] [c] [d] [e] [e]
i=2 j=4
[a] [b] [c] [d] [d] [e] [e]
i=3 j=5
[a] [b] [c] [d] [e] [e] [e]
i=4 j=6
[a] [b] [c] [d] [e] [e] [e]
i=4 j=7
L.length=i+1
7、2つの順序テーブルを新しい順序テーブルに結合し、関数から結果順序テーブルを返す.典型的な方法は、しっかりと身につける.
bool Merge(SqList A,SqList B,SqList &C){
if(A.length+B.length>C.MaxSize)
return false;
int i=0,j=0,k=0;
while(i<A.length&&j<B.length){
if(A.data[i]<=B.data[j]){
C.data[k++]=A.data[i++];
}else{
C.data[k++]=B.data[j++];
}
}
while(i<A.length)
C.data[k++]=A.data[i++];
while(j<B.length)
C.data[k++]=B.data[j++];
C.length=k;
return true;
}
while(i8、一次元配列A[m+n]に2つの線状表(a 1,a 2,a 3...am)と(b 1,b 2,b 3...bn)を順次格納することが知られている.配列内の2つの順序テーブルの位置を交換し、(b 1,b 2,b 3...bn)を前に置く関数を作成してみます.これは王道が与えたコードで、確かに非常に効率的です.
typedef int DataType;//
void Reverse(DataType A[],int left,int right,int arraySize){
if(left>=right||right>=arraySize)
return;// left right ，
int mid=(left+right)/2;
for(int i=0;i<mid-left;i++){//
DataType temp=A[left+i];
A[left+i]=A[right-i];
A[right-i]=temp;
}
}
void Exchange(DataType A[],int m,int n,int arraySize){
Reverse(A,0,m+n-1,arraySize);
Reverse(A,0,n-1,arraySize);
Reverse(A,n,m+n-1,arraySize);
}
私が自分でやれば、きっと新しい配列を開くに違いない.
9、線形テーブル(a 1,a 2,a 3...an)の要素は、逐次秩序化され、コンピュータ内に格納される.テーブル内の数値xの要素を最小時間で検索し、見つけたら後続の要素の位置と交換し、見つからない場合はテーブルに挿入し、テーブル内の要素を秩序正しく増加させるアルゴリズムを設計する必要があります.
//
void SearchExchangeInsert(ElemType A[],ElemType x){
int low=0,high=n-1,mid,i,temp;// ，n
while(low<=high){
mid=(low+high)/2;
if(A[mid]==x) break;// x
else if(A[mid]<x) low=mid+1;// x ，
else high=mid-1;// x ，
}// if
if(A[mid]==x&&mid!=n-1){// x，
temp=A[mid];A[mid]=A[mid+1];A[mid+1]=temp;
}
if(low>high){// ， x， x
for(i=n-1;i>high;i--)//high x
A[i+1]=A[i];//
A[i+1]=x;// ，x==high
}
}
10、【2010統一試験本題】n(n>1)個の整数を一次元配列Rに格納する.時間と空間の両方で可能な限り効率的なアルゴリズムを設計し、Rに格納されたシーケンスを左シフトp(0は(X 0,X 1,...,Xn−1)から(Xp,Xp+1,...,Xn−1,X 0,X 1,...,Xp−1)に変換する. 要求:1)アルゴリズムの基本設計思想を与える2)設計思想に基づいて,CあるいはC++あるいはJava言語記述アルゴリズムを採用し,肝心な点は注釈を与える3)アルゴリズムの時間複雑度と空間複雑度を説明する
ab-->ba
ab->a-1b->a-1b-1->(a-1b-1)-1->ba
void Reverse(int R[],int from,int to){
int i,temp;
for(i=0;i<(to-from+1);i++){
temp=R[from+i];
R[from+i]=R[to-i];
R[to-i]=temp;
}
}
void Converse(int R[],int p,int n){
Reverse(R,0,p-1);
Reverse(R,p,n-1);
Reverse(R,0,n-1);
}
O(n)， O(1)
11、【2011統一試験本題】長さL(L>=1)の昇順シーケンスSは、L/2番目の位置にある数をSの中位数と呼び、2つのシーケンスの中位数は、それらのすべての要素を含む昇順シーケンスの中位数である.既存の2つの昇順シーケンスAとBは,時間と空間の両方で可能な限り効率的なアルゴリズムを設計し,ABの中位数を探し出すことを試みた.要求:1)アルゴリズムの基本設計思想を与える2)設計思想に基づいて,CあるいはC++あるいはJava言語記述アルゴリズムを採用し,肝心な点は注釈を与える3)アルゴリズムの時間複雑度と空間複雑度を説明する
int M_Search(int A[],int B[],int n){
int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
// A B 、
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]==B[m2])
return A[m1];
if(A[m1]<B[m2]){
if((s1+d1)%2==0){
s1=m1;
d2=m2;
}else{
s1=m1+1;
d2=m2;
}
}else{
if((s2+d2)%2==0){
d1=m1;
s2=m2;
}else{
d1=m1;
s2=m2+1;
}
}
}
return A[s1]<B[s2]?A[s1]:B[s2];//
}