データ構造(C実装)------列

文字列(列と略称)は、線形テーブルのデータ要素のタイプが常に文字性であり、文字列のデータオブジェクトが文字セットに制約される特殊な線形テーブルと見なすことができる.
列は、0文字以上の有限シーケンスです.一般的には、s="s 1 s 2 s 3....sn"と記す、ここで、sは列名であり、二重引用符で囲まれた文字列を列の値と呼び、si(1<=i<=n)は列の要素と呼ぶ、アルファベット、数字または他の文字であってもよい、列を構成する基本単位であり、文字の個数nは列の長さと呼ぶ.
列のいくつかの用語:
　　　　１. 空白列:0文字からなる列を空白列と呼び、空白列には文字が含まれず、その長さは0です.
　　　　 2.サブストリング:ストリング内の任意の連続する文字からなるサブシーケンスを、ストリングのサブストリングと呼び、空のストリングは任意のストリングのサブストリングです.
　　　　 3.プライマリ・ストリング:サブストリングを含むストリングに対応するものをプライマリ・ストリングと呼びます.
　　　　 4.サブストリングの主ストリングの位置:通常、シーケンス内の文字のシーケンス番号をその文字の列の位置と呼び、サブストリングの主ストリング内の位置は、サブストリングの最初の文字の主ストリング内の位置で表される.　　　　　　
　　　　 5.2つの列が等しい:2つの列の長さが等しく、対応する位置の文字が等しい場合にのみ等しい.
列の表示:
　　1.列の順序は次のように格納されます.
シリアルのシーケンス格納構造はシーケンスシリアルと略称され、シーケンスシリアル中の文字シーケンスは連続した記憶ユニットのセットに順次格納され、主にシーケンスシリアルを実現する方法が3つあり、それぞれ以下の通りである.
(1)定長文字配列
シリアルの順序記憶構造では、定義済みのサイズに従って、定義されたシリアル変数ごとに固定サイズの記憶領域が割り当てられ、以下のように記述される.

//        
#define MAXSIZE 100
typedef char SString[MAXSIZE];

　　　　  
(2)文字列長のある配列

//        
#define MAXSIZE 100
typedef struct{
	char ch[MAXSIZE];
	int length;
}SqString;

　　　
(3)列のスタック割当て(すなわち動的配列)記憶記述

//         
typedef struct{
	char *ch; //     ，         ，  ，ch NULL
	int length; //   
}HString;

 
　　２.シリアルのチェーンストレージ表示:
リニア・テーブルのチェーン・ストレージ構造と同様に、チェーン・テーブル・メソッドを使用してシリアル値を格納する方法は、次の2つあります.
(1)列のチェーン構造タイプの説明:

//          
typedef struct node{
	char str;
	struct node *next;
}CNode,*LinkString;

　　　
(2)列のブロックチェーン格納タイプの説明:

//          
#define NODESIZE 3
typedef struct node{
	char ch[NODESIZE];
	struct node *next;
}SNode,*LinkStr;
LinkStr head;

　
　　3.列のインデックスストア表示:
列はインデックスで表すこともできますが、次の2つの方法があります.
(1)列の長さのインデックステーブル:

//       
#define MAXSIZE 100
typedef struct{
	char name[MAXSIZE];
	int length;
	char *startadr;
}LSNode;

(2)列の末尾ポインタ付きインデックステーブル:

//          
#define MAXSIZE 100
typedef struct{
	char name[MAXSIZE];
	int length;
	char *startadr;
	char *endadr;
}ENode;

　　　　
以上、三つのストレージ構造を紹介して列を表すが、それぞれのストレージ構造はいくつかの異なる方法で列を記述することができる.ここでは、列を記述するために最も一般的に使用される動的配列を実装し、このようにして口列の様々な動作を実現する.
基本操作:
ここでのすべての基本的な操作は,上述した動的配列,すなわちスタック構造で列を記述する前提の下で確立され,直接コードが与えられ,注釈が含まれている.

//         
typedef struct{
	char *ch; //     ，         ，  ，ch NULL
	int length; //   
}HString;


//          
void Str_Init(HString *S){
	S->ch = NULL;
	S->length = 0;
}



//     
void Str_Clear(HString *S){
	if(S->ch){
		free(S->ch);
		Str_Init(S);
	}
}


//         
int Str_IsEmpty(HString *S){
	return S->length == 0;
}


//      
int Str_GetLength(HString *S){
	return S->length;
}

//      
void Str_Assign(HString *S,char *chars){
	int i = 0,j;
	char *c = chars;
	//      S
    Str_Clear(S);
	//        
	while(*c){
		i++;
		c++;
	}
	//          0，     
	if(i > 0){
		S->ch = (char*)malloc(3*sizeof(char));
		for(j = 0;j < i;j++){
			S->ch[j] = chars[j];
		}
		S->length = i;
	}
}
//      , Ｔ   Ｓ
void Str_Copy(HString *S,HString *T){
	int i;
	//      S
    Str_Clear(S);
    S->length = T->length;
   
    if(S->length){
		S->ch = (char *)malloc(sizeof(char)*S->length);
		for(i = 0;i < S->length;i++)
			S->ch[i] = T->ch[i];
	}
}




//      , T   S  
void Str_Concat(HString *S,HString *T){
	//    S  
	HString temp;
	int i,j;
	Str_Init(&temp);
	Str_Assign(&temp,S->ch);
	
	//  S
	Str_Clear(S);
	//   S    
	S->length = temp.length + T->length;
	S->ch = (char*)malloc(sizeof(char) * S->length);
	//   temp T     S
	for(i = 0;i < temp.length;i++)
		S->ch[i] = temp.ch[i];
	for(j = 0; j < T->length;j++)
		S->ch[i++] = T->ch[j];

	// temp   
	free(temp.ch);
}

//      ,  Ｓ>T,    ０  ，  ，     ０  
int Str_Compare(HString *S,HString *T){
	int i;
	for(i = 0; i < S->length && i < T->length;i++)
		if(S->ch[i] != T->ch[i])
			return S->ch[i] - T->ch[i];
	return S->length - T->length;
}


//     Ｓub  
void Str_GetSub(HString *S,int pos,int len,HString *Sub){
	int i;
	//           
	if(pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1){
		printf("           ！
");
		exit(-1);
	}
	else{
		Str_Clear(Sub);
		if(len){
			Sub->ch = (char *)malloc(len * sizeof(char));
			for(i = 0;i < len;i++)
				Sub->ch[i] = S->ch[pos + i -1];
			Sub->length = len;
		}
	}
}

//                         
int Str_GetSubIndex(HString *S,HString *Sub,int pos){
	int i,j;
	//         
	if(pos < 1 || pos > S->length){
		printf("     !
");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("     ！
");
		return -1;
	}
	if(Str_IsEmpty(Sub)){
		printf("      ，         ！
");
		return 0;
	}
	
	for(i = pos - 1; i < S->length - Sub->length + 1;i++){
		for(j = 0; j < Sub->length;j++)
			if(S->ch[i+j] != Sub->ch[j])
				break;
		//       ， j= sub->length
		if(j == Sub->length)
			return i + 1;			
	}
	//     ，   -1;
	return -1;	
}




//        
void Str_Insert(HString *S,int pos,HString *T){
	int i;
	HString temp;
	if(pos < 1 || pos > S->length){
		printf("     !
");
		exit(-1);
	}
	if(Str_IsEmpty(T)){
		printf("    !
");
		exit(0);
	}
	Str_Init(&temp);
	temp.length = S->length + T->length;
	printf("%d
",temp.length);
	temp.ch = (char *)malloc(sizeof(char)*temp.length);
	for(i  = 0 ;i < pos ;i++)
		temp.ch[i] = S->ch[i];
	for(; i < pos + T->length;i++)
		temp.ch[i] = T->ch[i - pos];
	for(;i < temp.length;i++)
		temp.ch[i] = S->ch[i - T->length];
	//  Ｓ　  ，   temp   S
	Str_Clear(S);
	S->ch = temp.ch;
	S->length = temp.length;
	
}


//        
void Str_DeleteSub(HString *S,int pos,int len){
	int i;
	HString temp;
	//           
	if(pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1){
		printf("           ！
");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("     !
");
		exit(0);
	}
	Str_Init(&temp);
	temp.length = S->length - len;
	temp.ch = (char *)malloc(sizeof(char)*temp.length);
	for(i = 0 ;i < pos - 1; i++)
		temp.ch[i] = S->ch[i];
	for(;i < temp.length;i++)
		temp.ch[i] = S->ch[i+len];
	//  Ｓ  ，   temp   S
	Str_Clear(S);
	S->ch = temp.ch;
	S->length = temp.length;
	
}
//     
void Str_Print(HString *S){
	int i = 0;
	if(Str_IsEmpty(S)){
		printf("     !
");
		exit(0);
	}
	else
		printf("%s
",S->ch);		
}