??[數(shù)據(jù)結(jié)構(gòu)]串的基本定義及操作??

?

??一.串的定義及實(shí)現(xiàn)

概念熟記:

串是由0個(gè)或多個(gè)字符組成的有限的序列，記作$S{=}^{\prime }{a}_1{a}_2...a_n^{\prime }$，其中，當(dāng)$n=0$時(shí)表示空串

串中任意多個(gè)連續(xù)的字符組成的子序列稱為子串，包含子串的串稱為主串

若兩個(gè)串的長(zhǎng)度相等且每一個(gè)元素都相同，則這兩個(gè)串相等

? 比較線性表和串：

1. 在邏輯結(jié)構(gòu)上：串和線性表即為相似，區(qū)別僅為串的數(shù)據(jù)對(duì)象為字符集（如：數(shù)字，英文，中文，符號(hào)等）
2. 在操作上：串和線性表的操作大有不同，主要體現(xiàn)在操作對(duì)象上：
   $①$ 線性表的操作對(duì)象一般為單個(gè)元素
   $②$ 串的操作對(duì)象一般為子串

?? 怎么理解操作對(duì)象為子串？
因?yàn)橥枰鄠€(gè)字符才能表達(dá)出完整的實(shí)際意義，比如：${}^{\prime }wor{d}^{\prime }$ ，若把他們拆解為 { ′ w ′ , ′ o ′ , ′ r ′ , ′ d ′ } \{'w','o','r','d'\} {′w′,′o′,′r′,′d′}，并不能很好地體現(xiàn)它的實(shí)際含義，中文也類似，一個(gè)漢字也難以體現(xiàn)，所以將他們看做是一個(gè)整體來處理，與單個(gè)元素不同

??二.串的實(shí)現(xiàn)

??1.串的存儲(chǔ)方式

??1.順序存儲(chǔ)

順序存儲(chǔ)，即用一片連續(xù)的內(nèi)存空間存儲(chǔ)字符串序列

//靜態(tài)存儲(chǔ)
#define Maxsize 50

typedef struct {
	char ch[Maxsize]; //字符串?dāng)?shù)組
	int len;
}SString;

??注意：當(dāng)串的長(zhǎng)度超過最大長(zhǎng)度時(shí)，串會(huì)被截?cái)啵簿褪侵蟮淖址麑⒉粫?huì)保留

串的表示方式：

1. ??字符從數(shù)組下標(biāo)為0的位置開始存放，長(zhǎng)度單獨(dú)開辟一個(gè)變量空間存儲(chǔ):

優(yōu)點(diǎn)：長(zhǎng)度變量 $length$ 為 $int$ 型變量，可以存放的數(shù)據(jù)范圍大；
缺點(diǎn)：字符的位置與下標(biāo)不對(duì)齊

2. ??數(shù)組的首位置用len填充
   
   
   

優(yōu)點(diǎn)：字符位置與數(shù)組下標(biāo)對(duì)齊
缺點(diǎn)：此時(shí)的長(zhǎng)度變量 $length$ 只能為 $char$ 類型，若長(zhǎng)度 $>255$，則會(huì)溢出，無法記錄

3. ??在字符串?dāng)?shù)組的后面添加一個(gè)結(jié)束標(biāo)志’\0’

優(yōu)點(diǎn)：不用單獨(dú)存放長(zhǎng)度變量，到結(jié)束標(biāo)志符’\0’時(shí)自動(dòng)結(jié)束
缺點(diǎn)：若要頻繁使用長(zhǎng)度時(shí)，每一次都需要遍歷得到長(zhǎng)度，效率低

4. ?首元素不存放，從下標(biāo)為1開始，且單獨(dú)開辟空間存放長(zhǎng)度變量

優(yōu)點(diǎn)：既可以滿足數(shù)組下標(biāo)與字符位置對(duì)齊，又可以保證變量足夠表示長(zhǎng)度

??2.堆存儲(chǔ)

堆分配存儲(chǔ)依然需要開辟一片連續(xù)的存儲(chǔ)單元去存放字符串?dāng)?shù)組，但不同的是，他們的 存儲(chǔ)空間是在使用過程中動(dòng)態(tài)分配獲得的

#include<iostream>
using namespace std;

typedef struct {
	char *ch; //字符串?dāng)?shù)組
	int len;
}HString;

??3.塊鏈存儲(chǔ)

類似地，串也可以用鏈?zhǔn)酱鎯?chǔ)，由于串的特殊性，每個(gè)元素只有一個(gè)字符，因此，我們可以構(gòu)造每個(gè)結(jié)點(diǎn)，既可以存放一個(gè)字符，也可以存放多個(gè)字符，則將每個(gè)結(jié)點(diǎn)稱為塊，整個(gè)鏈表稱為塊鏈結(jié)構(gòu)

由于指針占4B，每一個(gè)字符占1B，因此，我們可以存放四個(gè)結(jié)點(diǎn)，盡可能降低存儲(chǔ)密度

#include<iostream>
using namespace std;

typedef struct {
	char ch[4]; //字符串?dāng)?shù)組,每個(gè)結(jié)點(diǎn)存多個(gè)字符
	struct StringNode *next;
}StringNode,*String;

??2.串的基本操作

??1.串的初始化

將字符串?dāng)?shù)組的長(zhǎng)度設(shè)為0，實(shí)現(xiàn)邏輯上的空串

void InitString(SString& S) {
	S.len = 0; //邏輯上的初始化
}

??2.求子串

bool SubString(SString& Sub, SString S, int pos, int len) { //Sub為子串，S為主串
	if (pos + len - 1 > S.len) //如果求的子串長(zhǎng)度比總長(zhǎng)度要大，則返回
		return false;
	for (int i = pos; i <= pos + len - 1; i++) {
		Sub.ch[i - pos + 1] = S.ch[i]; //第一個(gè)元素不存
	}
	Sub.len = len;
	return true;
}

??3.比較串

int StrCompare(SString S, SString T) {
	for (int i = 1; i <= S.len && i <= T.len; i++) { //同時(shí)在兩個(gè)串長(zhǎng)以內(nèi)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i]; //返回該元素的ASCII差值
	}
	return S.len - T.len; //如果掃描過的字符全部相同，則長(zhǎng)的更大
}

??4.定位串

int Index(SString S, SString T) { //定位子串T在主串S中的位置
	int i = 1, n = S.len, m = T.len;
	SString sub; //記錄子串
	while (i <= n - m + 1) {
		SubString(sub, S, i, m); //求子串
		if (StrCompare(sub, T) != 0)  //每一次都比較子串和T，如果子串不等于T，繼續(xù)遍歷下一個(gè)子串
			++i;
		else
			return i;
	}
	return 0;
}

??5.串的賦值

將 $chars$ 的值賦值給$S$中的字符串?dāng)?shù)組

注意：由于字符串是以’\0’結(jié)束的，所以可以以此作為判斷條件

void StrAssign(SString& S, char chars[]) {
	int len = strlen(chars);
	for (int i = 1; i <= len; i++) {
		if (chars[i-1] != '\0')
		{
			S.ch[i] = chars[i-1];
			S.len++;
		}
	}
}

完整代碼實(shí)現(xiàn)：

#include<iostream>
#define Maxsize 50
#include<cstring>
using namespace std;

typedef struct {
	char ch[Maxsize]; //字符串?dāng)?shù)組
	int len;
}SString;

// 1.初始化
void InitString(SString& S) {
	S.len = 0; //邏輯上的初始化
}

//2.求子串
bool SubString(SString& Sub, SString S, int pos, int len) { //Sub為子串，S為主串
	if (pos + len - 1 > S.len) //如果求的子串長(zhǎng)度比總長(zhǎng)度要大，則返回
		return false;
	for (int i = pos; i <= pos + len - 1; i++) {
		Sub.ch[i - pos + 1] = S.ch[i]; //第一個(gè)元素不存
	}
	Sub.len = len;
	return true;
}

//3.比較串
int StrCompare(SString S, SString T) {
	for (int i = 1; i <= S.len && i <= T.len; i++) { //同時(shí)在兩個(gè)串長(zhǎng)以內(nèi)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i]; //返回該元素的ASCII差值
	}
	return S.len - T.len; //如果掃描過的字符全部相同，則長(zhǎng)的更大
}


//4.定位
int Index(SString S, SString T) { //定位子串T在主串S中的位置
	int i = 1, n = S.len, m = T.len;
	SString sub; //記錄子串
	while (i <= n - m + 1) {
		SubString(sub, S, i, m); //求子串
		if (StrCompare(sub, T) != 0)  //每一次都比較子串和T，如果子串不等于T，繼續(xù)遍歷下一個(gè)子串
			++i;
		else
			return i;
	}
	return 0;
}

//5.賦值
void StrAssign(SString& S, char chars[]) {
	int len = strlen(chars);
	for (int i = 1; i <= len; i++) {
		if (chars[i-1] != '\0')
		{
			S.ch[i] = chars[i-1];
			S.len++;
		}
	}
}

//6.輸出
void Print(SString S) {
	for (int i = 1; i <= S.len; i++) {
		cout << S.ch[i];
	}cout << endl;
}


int main() {
	SString S, T;
	InitString(S);
	InitString(T);

	char s[] = "yanruixiaobao";
	char t[] = "ruixiao";

	StrAssign(S, s);
	StrAssign(T, t);

	//打印
	cout << "串S和T為：" << endl;
	Print(S);
	Print(T);

	cout << "子串T在S中的位置為:" << Index(S, T) << endl;

	system("pause");
	return 0;
}

輸出結(jié)果：

?

?

文章來源地址http://www.zghlxwxcb.cn/news/detail-741650.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】串的基本定義及操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！