資料結構~11.串

本文是上一篇文章的後續,詳情點選該連結~

串的基本定義

       串是由零個或者多個字元組成的有序序列。串中字元的個數稱為串的長度,含有零個元素的串叫空串。

//這就好比一個名為str的串
	char str[] = "today is greate day";
           

       串中任意連續的字元組成的子序列稱為該串的子串,包含子串的串稱為主串，某個字元在串中的序号稱為這個字元的位置。通常用子串第一個字元作為子串在主串中的位置。要注意,空格也是串字元集合中的一個元素，由一個或者多個空格組成的串稱為空格串(注意:空格串不是空串)

       串的邏輯和線性表類似,串限定了元素為字元的線性表。從操作集上講,串和線性表有很大的差別,線性表的操作主要針對表内的某一個元素,而串操作主要針對串内的一個子串

串的存儲結構

       一般不采用剛才的那種方式來定義并初始化一個串。原因是僅僅以'\0'作為串結束的标記在求串長的時候需要掃描整個串,時間複雜度為O(n)。不如額外來定義一個變量,專門來存儲串的長度,這樣一來求串長的時間複雜度為 O(1)

順序存儲表示結構體定義如下

#define MAXSIZE 100
typedef struct {
	char str[MAXSIZE + 1]; //MAX + 1 是為了多出一個 \0 作為結束标記
	int length;
}Str;
           

動态配置設定存儲表示

       在程式執行的過程根據需要動态配置設定

typedef struct {
	char *ch;			//指向動态配置設定存儲區首位址的字元指針
	int length;			//串的長度
}Str;
           

       這種存儲方式在使用時,需要用函數malloc()來配置設定一個長度為length,類型為char的存儲空間,配置設定的空間可以用函數free()釋放掉。用函數malloc()配置設定存儲的空間如果成功,則傳回一個指向起始位址的指針,作為串的基位址,這個位址由ch指針來指向。如果配置設定失敗,則傳回NULL。

       動态配置設定存儲比順序存儲更加靈活,是以在串處理應用程式中,更為常用。

串的基本操作

指派操作

       與普通變量指派操作不同,串的指派操作不能直接用=來表示,因為串是一個數組,必須對數組中的每個元素進行逐一指派。操作串的指派操作可以用strassign()實作。其功能是将一個常量字元串指派給str。成功傳回1,失敗傳回0

int strassign(Str &str,char *ch) {
	int len = 0,i;
	char* c = ch;	//将ch賦給c，這樣操作c時候,就不會破壞原來的ch
	//求串c的長度
	while (*c) {
		len++;
		c++;
	}
	if (len == 0) {	//如果ch為空串,則傳回空串
		str.ch = NULL;
		str.length = 0;
		return 1;
	}
	else {
		//動态配置設定空間,取 len + 1 是為了多出一個空間存放 '\0'
		str.ch = (char*)malloc(sizeof(char) * (len + 1));
		if (str.ch == NULL) {
			return 0;
		}
		else {
			//把ch重新指派給c，這樣c又恢複到初始值
			c = ch;
			for (i = 0; i <= len; ++i,++c) {
				str.ch[i] = *c;
				str.length = len;
				return 1;
			}
		}
	}
}
           

擷取串的長度操作

int strlength(Str str) {
	return str.length;
}
           

串的比較操作

       串的比較操作是串排序應用中的核心操作。通常是用ASCLL碼進行比較

//串的比較操作
int strcompare(Str s1,Str s2) {
	int i;
	//任何一個串被周遊完畢就跳出循環
	for (i = 0; i < s1.length && i < s2.length; ++i) {
		//當兩個串遇到不相同的字元的時候,就進行ASCLL比較
		if (s1.ch[i] != s2.ch[i]) {
			return s1.ch[i] - s2.ch[i];
		}
	}
	//假如兩個串完全相同,就進行長度比較
	return s1.length - s2.length;
}
           

串的連結操作

       将兩個串首尾相接,合并成一個字元串的操作稱為串連接配接操作

//串的連結操作
int concat(Str& str, Str str1, Str str2) {
	int i = 0, j = 0;
	//這裡 + 1是為了給 '\0' 留個位置
	str.ch = (char*)malloc(sizeof(char) * (str1.length + str2.length + 1));

	if (str.ch == NULL) {
		return 0;
	}

	while (i < str1.length) {
		str.ch[i] = str1.ch[i];
		++i;
	}
	//這裡使用 <= 是為了連同 str2.ch最後 '\0' 一起複制
	while (j <= str2.length) {
		//從i的坐标開始指派
		str.ch[i + j] - str2.ch[j];
		++j;
	}
	str.length = str1.length + str2.length;
	return 1;
}
           

求子串操作

       求從給定串中某一位置結束的串的操作稱為求字串操作(規定開始位置總在結束位置的前邊)。

//str串中從post開始到len，由substr傳回
int substring(Str&substr,Str str,int pos,int len) {
	int i = 0, j = 0;
	if (pos < 0 || pos >= str.length || len < 0 || len > str.length - pos) {
		return 0;
	}
	if (substr.ch) {
		free(substr.ch);
		substr.ch = NULL;
	}
	if (len == 0) {
		substr.ch = NULL;
		substr.length = 0;
		return 1;
	}
	else {
		substr.ch = (char*)malloc(sizeof(char) * (len + 1));
		i = pos;
		j = 0;
		while (i < pos + len) {
			substr.ch[j] = str.ch[i];
			++i;
			++j;
		}
		substr.ch[j] = '\0';
		substr.length = len;
		return 1;
	}
}
           

串清空操作

int clearstring(Str &str) {
	if (str.ch) {
		free(str.ch);
		str.ch = NULL;
	}
	str.length = 0;
	return 1;
}