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 顺序表的定义#顺序表的特点]]
串长的两种方案
char ch[10]变量length在最后char ch[0]充当length- 优点：字符的位序和数组下标相同
- 缺点：字符串长度不能超过 255
- 没有
length变量，以字符'\0'表示结尾（对应 ASCII 码的 0）- 缺点：每次都需要遍历，如果经常需要使用到这个参数，这个方案不适合
- 教材采用的方案：
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;elsereturn i; // 返回子串在主串中的位置}return 0; // S中不存在与T相等的子串
}