データ構造(C実装)------シーケンステーブル

線形テーブルは、n(n>=0)個の同じデータ型を有するデータ要素からなる有限シーケンスであり、通常は次のように記述されます.(a 1,a 2,.,ai-1,ai,ai+1,...,an)表の隣接する要素の間には、ai-1をaiの前駆者と呼び、aiをai-1の後継と呼び、2<=i<=nというシーケンシャル関係がある.表のデータ要素の個数nは、線形表の長さ、長さ0の線形表を空の表と呼ぶ.空でない線形表では、各データ要素には、a 1が最初の位置であるように決定された位置がある要素、anは最後の要素であり、aiはi番目の要素であり、iをデータ要素aiの線形テーブル上のビットシーケンスと呼ぶ.
シーケンステーブルとは、リニアテーブルのシーケンス記憶構造であり、リニアテーブルを連続した記憶ユニットのセットで順次記憶するデータ要素を指す.シーケンステーブルでは、論理関係が隣接する2つの要素も物理的に隣接しており、要素間の論理関係は下付き文字で反映されています.
配列は、順序テーブルを記述するために使用することができるが、順序テーブルの長さが絶えず変化することを考慮して、通常、1次元データと順序テーブルの長さを構造体にカプセル化して順序テーブルを記述する.次のようになります.

//      
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef struct{
	ElemType *elem;//      
	int length;	//    　
	int listsize; 	//         
}SqList;

        
線形テーブルに対して、初期化、挿入、削除、クリア、テーブル長の取得、印刷順序テーブルの破棄、位置決めなどの操作があり、以下のように分けられる.
       

//   
#define Status int 
#define OK 1
#define OVERFLOW 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

      
順序テーブルの様々な操作:

//    
Status InitList_Sq(SqList *L){
	L->elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

//          
Status ListInsert_Sq(SqList *L,int i,ElemType e){
	//    Ｌ   i           e
	ElemType *q,*p;
	if(i < 1 || i > L->length+1){
		printf("     
");
		return ERROR;
	}
	if(L->length >= L->listsize){
		ElemType *newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)
			exit(OVERFLOW);
		L->elem = newbase;
		L->listsize = L->listsize+LISTINCREMENT;
	}
	q = &(L->elem[i-1]);//      
	for (p = &(L->elem[L->length - 1]);p>=q;p--)
		*(p+1) = *p;
	
	*q = e;
	L->length++;
	printf("  %d         
",e);
	return OK;	
}

//       
Status ListPrint_Sq(SqList *L){
	ElemType *p,*q;
	if(L->length == 0){
		printf("     
");
		return ERROR;
	}
	p = L->elem;//         
	q = L->elem + L->length - 1;//         
	printf("      ：");
	while(p <= q ){
		printf("%d\t",*p);
		p++;
	}
	printf("
");
	return OK;
}

//         i   　
Status ListDelete_Sq(SqList *L,int i){
	ElemType *p,*q,e;
	if(i < 1 ||  i > L->length){
		printf("     
");
		return ERROR;
	}
	p = &(L->elem[i-1]);//          
	e = *p;//       
	q = L->elem + L->length -1;
	while(p < q){
		*p = *(p+1);
		p++;
	}
	L->length--;
	printf("  %d    
",e);
	return OK;
	
}

//        
int  ListLength_Sq(SqList *L){
	return L->length;
}

//       
Status ListEmpty_Sq(SqList *L){
	if(L->length == 0){
		printf("   
");
		return TRUE;
	}
	else{
		printf("   
");
		return FALSE;
		
	}
}
//     
Status ClearList_Sq(SqList *L){
	L->length = 0;
}

//     
Status DestroyList_Sq(SqList *L){
	free(L->elem);
	L->length = 0;
	return OK;
}

//         
Status GetListElem_Sq(SqList *L,int i){
	ElemType *p;
	if( i < 1 || i > L->length){
		printf("     
");
		return ERROR;
	}
	p = &(L->elem[i-1]);
	printf("    ，     i    %d",*p);
	return OK;
	
}
//          ，            
int LocateList_Sq(SqList *L,ElemType e){
	ElemType *p,*q;
	int l=0,flg=0;
	p = L->elem;
	q = L->elem + L->length -1;
	while(p  <= q){
		if( e == *p){
			flg = 1;
			break;
		}
		l++;
		p++;
	}
	if(flg == 0){
		printf("          
");
		return 0;
	}
	printf("    ，          %d   ",l);
	return l;
			
}

テストでは、主関数に構造体SqList Lを定義してから、InitList_のような関連関数をテストできます.Sq(&L);またはListPrint_Sq(&L);
順序表のまとめ:
             1. シーケンステーブル上で挿入演算を行う場合,テーブルの半分のデータ要素を移動する必要があり,その時間的複雑度はO(n)である.
             2. シーケンステーブル上で削除演算を行う場合,テーブルの約半分の要素を移動する必要があり,その時間的複雑さはO(n)である.
             3. 線形の順序記憶構造の特徴は、線形テーブルの論理関係で信頼されるデータ要素が物理的にも隣接していることである.すなわち、物理的に隣接して論理的に隣接していることを実現し、線形テーブルの各要素を連続した記憶ユニットで順次記憶することを要求する.この特徴は、順序テーブルに以下のようなメリットとデメリットをもたらす.
主なメリット:
1)要素間の論理関係を表すために余分な記憶領域を追加する必要はない.
2)線形テーブルのいずれかの要素に容易にランダムにアクセスできる.
主な欠点:
1)挿入と削除が不便です.シーケンステーブル内のデータ要素間の論理関係を維持するためには、演算の挿入と削除時に大量の要素を移動する必要があり、行き先の効率に影響します.
2)順序表の長さには常に一定の制限があり、予め使用する空間の大きさを推定する必要があり、推定が小さくなると、順序表のオーバーフローをもたらす.見積りが大きくなると、ストレージスペースの無駄になります.