程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 數據結構（C實現）------- 串

數據結構（C實現）------- 串

編輯：關於C語言

數據結構（C實現）------- 串

字符串（簡稱串）,可以將其看作是種特殊的線性表，其特殊性在於線性表的數據元素的類型總是字符性，字符串的數據對象紅豆為字符集。

　串是由０個或多個字符組成的有限序列。一般記作：s = "s1 s2 s3 .... sn",，其中，s是串名，用雙引號括起來的字符序列稱為串的值，si（1<=i <= n）稱為串的元素，可以是字母，數字或其他字符，是構成串的基本單位，字符的個數n稱為串的長度.

串中的幾個術語：

　　　　１. 空串：　由０個字符組成的串稱為空串，空串不包含任何字符，其長度為０。

　　　　 2. 子串：　串中任意個連續的字符組成的子序列稱為該串的子串，空串是任何串的子串。

　　　　 3. 主串：　包含子串的串相應的稱為主串。

　　　　 4. 子串在主串的位置：通常稱字符在序列中的序號為該字符在串的位置，子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。　　　　　　

　　　　 5. 兩串相等：當且僅當兩個串的長度相等，並且各個對應位置的字符都相等時才相等。

串的表示：

　　1. 串的順序存儲表示：

　　　串的順序存儲結構簡稱為順序串，順序串中的字符序列被順序地存放在一組連續的存儲單元中，主要有三種實現順序串的方式，分別如下：

　　　(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;

　　２.串的鏈式存儲表示：

　　　　和線性表的鏈式存儲結構相類似，也可以采用鏈表方法存儲串值，有以下兩個方法：

　　　　(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.串的索引存儲表示：

　　　　串也可以用索引的方式來表示，有以下兩種方法：

　　　　(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("子串的位置或長度不合法！\n");
		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("位置不合法!\n");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("順序串為空！\n");
		return -1;
	}
	if(Str_IsEmpty(Sub)){
		printf("給定子串為空，空串為任何串的子串！\n");
		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("位置不合法!\n");
		exit(-1);
	}
	if(Str_IsEmpty(T)){
		printf("子串為空!\n");
		exit(0);
	}
	Str_Init(&temp);
	temp.length = S->length + T->length;
	printf("%d\n",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("子串的位置或長度不合法！\n");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("順序串為空!\n");
		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("順序串為空!\n");
		exit(0);
	}
	else
		printf("%s\n",S->ch);		
}