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相等的子串
}

相关推荐

  1. 04-4.1.2 存储结构

    2024-06-09 22:28:02       11 阅读
  2. 数据结构概念大合集05

    2024-06-09 22:28:02       13 阅读
  3. 数据结构存储方式

    2024-06-09 22:28:02       32 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-09 22:28:02       8 阅读
  2. 【Python教程】压缩PDF文件大小

    2024-06-09 22:28:02       9 阅读
  3. 通过文章id递归查询所有评论(xml)

    2024-06-09 22:28:02       10 阅读

热门阅读

  1. 【react】useEffect 快速上手

    2024-06-09 22:28:02       8 阅读
  2. android-线程池3

    2024-06-09 22:28:02       6 阅读
  3. process to develop linux 5.4

    2024-06-09 22:28:02       7 阅读
  4. 软设之排序算法对比

    2024-06-09 22:28:02       5 阅读
  5. ghidra

    2024-06-09 22:28:02       6 阅读
  6. P11 品牌管理

    2024-06-09 22:28:02       8 阅读
  7. 爬山算法的详细介绍

    2024-06-09 22:28:02       7 阅读
  8. Flutter 常见报错记录

    2024-06-09 22:28:02       7 阅读
  9. 解决更新Android Studio后下载Gradle超时

    2024-06-09 22:28:02       8 阅读