04-4.1.2 串的存储结构

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

顺序存储

// 静态数组实现
#define MAXLEN 255    // 预定义最大串长为255
typedef struct{
	char ch[MAXLEN];  // 每个分量存储一个字符
	int length;       // 串的实际长度
}SString;

// 动态数组实现
typedef struct{
	char *ch;    // 按串长分配存储区，ch指向串的基地址
	int length;  // 串的长度
}HString;

HString S;
S.ch = (char *) malloc (MAXLEN * sizeof(char));
S.length = 0;

考试过程中如果有提问优缺点，可以结合顺序表的知识思考优缺点[[2.2.1 顺序表的定义#顺序表的特点]]

串长的两种方案

1. char ch[10] 变量 length 在最后
2. char ch[0] 充当 length
   • 优点：字符的位序和数组下标相同
   • 缺点：字符串长度不能超过 255
3. 没有length 变量，以字符 '\0' 表示结尾（对应 ASCII 码的 0）
   • 缺点：每次都需要遍历，如果经常需要使用到这个参数，这个方案不适合
4. 教材采用的方案：ch[0] 废弃不用，但是仍然在结尾处 int length;

链式存储

typedef struct StringNode{
	char ch;                  // 每个结点存一个字符
	struct StringNode *next;
}StringNode, *String;

用这种存储方式，存储密度低，每个字符 1B，每个指针要用 4B 来存储，要解决这种问题，可以使每个结点存储多个字符

typedef struct StringNode{
	char ch[4];      // 每个节点存储4个字符，实际上还能更多
	struct StringNode *next;
}StringNode, *String;

基于顺序存储实现基本操作

SubString(&Sub, S, pos, len) 求子串

S.ch = "wangdao";
S.length = 7;

// 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
	// 子串范围越界
	if(pos+len-1 > S.length)
		return false;
	for(int i = pos; i < pos+len; i++)
		Sub.ch[i-pos+1] = S.ch[i];
	Sub.length = len;
	return true;
}

StrCompare(S, T) 比较两个串

// 比较
int StrCompare(SString S, SString T){
	for(int i = 1; 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;
}

Index(S, T) 定位

int Index(SString S, SString T){
	int i = 1, n = StrLength(S), m = StrLength(T);
	SString sub;          // 用于暂存子串
	while(i <= n-m+1){
		SubString(sub, S, i, m);
		if(StrCompare(sub, T) != 0)
			++i;
		else
			return i;     // 返回子串在主串中的位置
	}
	return 0;             // S中不存在与T相等的子串
}