Pythonのシーケンステーブルとは
1、 シーケンステーブルの紹介
シーケンステーブルは最も単純な線形構造です。論理的に隣接するデータは、互いに隣接するコンピューターに保存されます。最初の要素をすばやく見つけることができます。中央にスペースを入れないため、挿入または削除するときに多くの移動が必要になります。素子。シーケンステーブルは、連続ストレージスペースMaxsizeを割り当て、elemを使用してベースアドレスを記録し、lengthを使用して実際の要素数、つまりシーケンステーブルの長さを記録できます。
上の図1は、シーケンステーブルの基本的な形式を示しています。データ要素自体は継続的に保存され、各要素が占めるストレージユニットのサイズは固定されて同じです。要素の添え字はその論理アドレスであり、要素ストレージの物理アドレス（実際のメモリアドレス）です。これは、ストレージ領域の開始アドレスLoc（e0）に、論理アドレス（i番目の要素）とストレージユニットサイズ（c）の積を加えたもの、つまりLoc（element i）= Loc（e0）+ c *で計算できます。私
したがって、指定された要素にアクセスするときに最初からトラバースする必要はなく、対応するアドレスは計算によって取得でき、時間の複雑さはO（1）です。
要素のサイズが均一でない場合は、図2の外部要素を使用して実際のデータ要素を個別に格納する必要があり、シーケンステーブルの各ユニット位置には、対応する要素のアドレス情報（つまりリンク）が格納されます。各リンクは同じ量のストレージを必要とするため、上記の式を使用して、要素リンクの保存場所を計算し、実際に保存されているデータ要素をリンクに沿って見つけることができます。図2のcは、データ要素のサイズではなく、リンクアドレスを格納するために必要なストレージの量であり、通常は非常に小さいことに注意してください。
図2に示すシーケンステーブルは、実際のデータへのインデックスとも呼ばれ、最も単純なインデックス構造です。
2、 シーケンステーブルの構造
シーケンステーブルの完全な情報は2つの部分で構成され、1つはテーブル内の要素のコレクションであり、もう1つは正しい操作のために記録する必要のある情報、つまりテーブルの全体的な状況に関する情報です。この部分の情報には、主に要素の格納領域の容量が含まれます。そして、現在のテーブルの要素の数。
3、 シーケンステーブルの2つの基本的な実装方法
1 統合構造として、テーブル情報を格納するためのユニットと要素の格納領域が連続して格納領域に配置され、データの2つの部分が完全なシーケンシャルテーブルオブジェクトを形成します。統合された構造は、強力な整合性と簡単な管理を備えています。ただし、データ要素の格納領域はテーブルオブジェクトの一部であるため、シーケンステーブルの作成後に要素の格納領域は固定されます。
2 分離された構造の場合、テーブル全体に関連する情報（つまり、容量と要素の数）のみがテーブルオブジェクトに格納され、実際のデータ要素は、リンクを介して基本テーブルオブジェクトに関連付けられた別の独立した要素ストレージ領域に格納されます。
4、 エレメント保管エリアの交換
一体構造シーケンステーブル情報領域とデータ領域は連続して格納されているため、データ領域を入れ替える場合は、全体、つまりシーケンステーブルオブジェクト全体（シーケンステーブルの構造情報が格納されている領域を参照）を変更することしかできません。データ領域を分離された構造に置き換える場合は、テーブル情報領域のデータ領域のリンクアドレスを更新するだけで、シーケンステーブルオブジェクトは変更されません。
5、 要素の保管領域の拡張
別の構造のシーケンステーブルを使用すると、データ領域をより大きなストレージスペースに置き換えると、テーブルオブジェクトを変更せずにデータストレージ領域を拡張でき、このテーブルが使用されるすべての場所を変更する必要がありません。プログラムの動作環境（コンピュータシステム）に空きストレージがある限り、このテーブル構造は、いっぱいであるために操作が失敗することはありません。このテクノロジーによって実装されたシーケンステーブルは、使用中に容量を動的に変更できるため、動的シーケンステーブルと呼ばれます。
拡張のための2つの戦略
拡張ごとに固定数のストレージロケーションが追加されます。たとえば、拡張ごとに10個の要素ロケーションが追加されます。この戦略は、線形成長と呼ばれます。
特徴：スペースを節約しますが、頻繁な拡張操作と多くの操作。
拡張ごとに容量が2倍になります。たとえば、拡張ごとにストレージスペースが2倍になります。
機能：拡張操作の実行回数を減らしますが、スペースリソースを浪費する可能性があります。スペースを時間と交換するための推奨される方法。
6、 シーケンステーブルの追加、削除、変更、およびクエリ操作のPythonコード実装
# シーケンステーブルclassSequenceを作成します_Table():
# 初期化
def __init__(self):
self.date =[None]*100
self.length =0
# いっぱいかどうかを確認します
def isFull(self):if self.length 100:print("シーケンステーブルがいっぱいで、要素を追加できません")return1else:return0
# 下の表のインデックスで検索
def selectByIndex(self,index):if index =0 and index<=self.length-1:return self.date[index]else:print("入力した添え字が正しくありません。再入力してください\n")return0
# 要素で添え字を検索
def selectByNum(self,num):
isContain =0for i inrange(0,self.length):if self.date[i]== num:
isContain =1print("あなたが探している要素のインデックスは%d\n"%i)if isContain ==0:print("必要なデータが見つかりませんでした")
# データを追加する
def addNum(self,num):if self.isFull()==0:
self.date[self.length]= num
self.length +=1
# 注文表を印刷する
def printAllNum(self):for i inrange(self.length):print("a[%s]=%s"%(i,self.date[i]),end=" ")print("\n")
# を押してデータを挿入します
def insertNumByIndex(self,num,index):if index<0 or index self.length:return0
self.length +=1for i inrange(self.length-1,index,-1):
temp = self.date[i]
self.date[i]= self.date[i-1]
self.date[i-1]= temp
self.date[index]= num
return1 #を押してデータを削除します
def delectNumByIndex(self,index):if self.length <=0:print("シーケンステーブルにデータがないため、削除する必要はありません")for i inrange(index,self.length-1):
temp = self.date[i]
self.date[i]= self.date[i +1]
self.date[i +1]= temp
self.date[self.length-1]=0
self.length -= 1def main(): #シーケンステーブルオブジェクトを作成します
seq_t =Sequence_Table()
# 3つの要素を挿入します
seq_t.addNum(1)
seq_t.addNum(2)
seq_t.addNum(3)
# 印刷検証
seq_t.printAllNum()
# インデックスで検索
num = seq_t.selectByIndex(2)print("あなたが探しているデータは%d\n"% num)
# インデックスに従ってデータを挿入します
seq_t.insertNumByIndex(4,1)
seq_t.printAllNum()
# 番号に従って添え字を確認してください
seq_t.selectByNum(4)
# データを削除する
seq_t.delectNumByIndex(1)
seq_t.printAllNum()if __name__ =="__main__":main()
実行結果は次のとおりです。
a[0]=1 a[1]=2 a[2]=3
あなたが探しているデータは3です
a[0]=1 a[1]=4 a[2]=2 a[3]=3
あなたが探している要素のインデックスは1です
a[0]=1 a[1]=2 a[2]=3
7、 シーケンステーブルの追加、削除、変更、およびチェック操作のC言語コードの実装
# include<stdio.h
//1.シーケンステーブルのストレージ構造を定義します
typedef struct
{ //配列を使用して要素を線形テーブルに格納する
int data[100];//シーケンステーブルの要素数
int length;}Sequence_table,*p_Sequence_table;//2.シーケンステーブルvoidinitSequenceTableの初期化(p_Sequence_table T){//渡されたテーブルが空かどうかを判断し、空の場合は終了します。(T == NULL){return;}//デフォルトの長さを0に設定します
T- length =0;}//3.シーケンステーブルの長さを見つけます
int lengthOfSequenceTable(p_Sequence_table T){if(T==NULL){return0;}return T- length;}//4.シーケンステーブルがいっぱいかどうかを確認します
int isFull(p_Sequence_table T){if(T- length =100){printf("シーケンステーブルがいっぱいで、これ以上要素を追加できません");return1;}return0;}//5.シリアル番号で検索
int selectSequenceTableByIndex(p_Sequence_table T,int index){if(index =0&&index<=T- length-1){return T- data[index];}printf("入力したシリアル番号が間違っています。再入力してください\n");return0;}//6.voidselectSequenceTableByNumの存在をコンテンツで検索します(p_Sequence_table T,int num){
int isContain =0;for(int i=0; i<T- length; i++){if(T- data[i]== num){
isContain =1;printf("あなたが探している要素の添え字は:%d\n",i);}}if(isContain ==0){printf("探していたデータが見つかりませんでした\n");}}//7.要素を追加します（チームの最後に追加します）voidaddNumber(p_Sequence_table T,int num){//シーケンステーブルがいっぱいでない場合(isFull(T)==0){
T- data[T- length]= num;
T- length++;}}//8.シーケンステーブルのトラバースvoidprintAllNumOfSequenceTable(p_Sequence_table T){for(int i =0; i<T- length; i++){printf("T[%d]=%d ",i,T- data[i]);}printf("\n");}//9.挿入操作
int insertNumByIndex(p_Sequence_table T, int num,int index){if(index<0||index T- length){return0;}
T- length++;for(int i = T- length-1; i index; i--){
int temp = T- data[i];
T- data[i]= T- data[i-1];
T- data[i-1]= temp;}
T- data[index]= num;return1;}//10.要素voiddelectNumを削除します(p_Sequence_table T,int index){if(T- length <=0){printf("シーケンステーブルにデータがないため、削除する必要はありません");}for(int i = index;i<T- length-1; i++){
int temp = T- data[i];
T- data[i]= T- data[i+1];
T- data[i+1]= temp;}
T- data[T- length-1]=0;
T- length--;}
int main(int argc,const char * argv[]){//シーケンステーブル構造を作成する
Sequence_table seq_t;//initSequenceTableを初期化します(&seq_t);//データの追加addNumber(&seq_t,1);addNumber(&seq_t,2);addNumber(&seq_t,3);//印刷検証printAllNumOfSequenceTable(&seq_t);//インデックスに従って内容を確認してください
int num =selectSequenceTableByIndex(&seq_t,2);printf("チェックするデータは:%d\n",num);//insertNumByIndexを挿入します(&seq_t,4,1);printAllNumOfSequenceTable(&seq_t);//selectSequenceTableByNumの内容に従って添え字を確認してください(&seq_t,4);//添え字delectNumに従ってデータを削除します(&seq_t,1);printAllNumOfSequenceTable(&seq_t);return0;}
実行結果は次のとおりです。
T[0]=1 T[1]=2 T[2]=3
チェックするデータは次のとおりです。3
T[0]=1 T[1]=4 T[2]=2 T[3]=3
探している要素の添え字は次のとおりです：1
T[0]=1 T[1]=2 T[2]=3
ナレッジポイントの拡張：
Pythonの2種類のリストとタプルは、シーケンシャルリストの実装テクノロジを採用しています。シーケンシャルリストには、前述のシーケンシャルリストのすべてのプロパティがあります。
タプルは不変のタイプ、つまり不変のシーケンスリストであるため、内部状態を変更する操作をサポートしていません。その他の点では、リストの性質に似ています。
リストの基本的な実現技術
Python標準タイプリストは、要素数が可変の線形リストです。要素を追加および削除したり、さまざまな操作で既存の要素の順序を維持したり（つまり、順序を保持したり）、次の動作特性もあります。
添字（場所）に基づく効率的な要素アクセスと更新。時間の複雑さはO（1）である必要があります。
この機能を満たすには、シーケンシャルテーブルテクノロジーを使用する必要があり、テーブル内の要素は連続ストレージ領域に保存されます。
要素を任意に追加することができ、要素を追加する過程で、テーブルオブジェクトの識別子（関数IDによって取得される値）は変更されません。
この機能を満たすには、要素のストレージ領域を置き換えることができる必要があります。また、ストレージ領域を置き換えたときにリストオブジェクトの識別IDが変更されないようにするには、個別の実装テクノロジのみを使用できます。
Pythonの公式実装では、listは個別のテクノロジを使用して実装された動的シーケンスリストです。これが、指定された位置に要素を挿入するよりも、list.append（x）（またはlist.insert（len（list）、x）、最後に挿入）を使用する方が効率的である理由です。
Pythonの公式実装では、リスト実装は次の戦略を採用しています。空のテーブル（または小さなテーブル）を作成するとき、システムは8つの要素を保持できるストレージ領域を割り当てます。挿入操作（挿入または追加）を実行するとき。 、要素の保存領域がいっぱいの場合は、4倍の保存領域を変更します。ただし、この時点でテーブルがすでに非常に大きい場合（現在のしきい値は50000）、戦略を変更し、2倍にする方法を使用してください。この変更戦略の導入は、空きストレージの場所が多すぎないようにすることです。
上記は、Pythonのシーケンステーブルとは何かの詳細な内容です。Pythonのシーケンステーブルの詳細については、ZaLou.Cnの他の関連記事に注意してください。
Recommended Posts