串的顺序存储
串（String）的顺序存储是指使用一段连续的存储单元来存储字符串中的字符。
计算串的长度
静态存储(定长顺序存储)
#define MAXLEN 255//预定义最大串为255
typedef struct {
char ch[MAXLEN];//每个分量存储一个字符
int length;//串的实际长度
}SString;动态存储(堆分配存储)
typedef struct {
char* ch;//按串长分配存储区，ch指向串的基地址
int length;//串的长度
}HString;
void main() {
HString S;
S.ch = (char*)malloc(MAXLEN * sizeof(char));
S.length = 0;
}注意调用完malloc函数后需要手动用free函数回收内存空间
代码示例
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100 // 定义串的最大长度
typedef struct {
char ch[MAXLEN]; // 按串长分配存储区
int length; // 串的长度
} HString;
// 函数：initString
// 功能：初始化一个HString串
// 参数：str - 指向HString结构的指针
void initString(HString *str) {
str->length = 0;
}
// 函数：assignString
// 功能：为HString串赋值
// 参数：str - 指向HString结构的指针
// chars - 要赋值的字符数组
void assignString(HString *str, char *chars) {
int i = 0;
while (chars[i] != '\0' && i < MAXLEN) {
str->ch[i] = chars[i];
i++;
}
str->length = i;
}
// 函数：concatString
// 功能：连接两个HString串
// 参数：str1 - 第一个HString串
// str2 - 第二个HString串
// 返回值：连接后的HString串
HString concatString(HString str1, HString str2) {
HString result;
initString(&result);
int i, j;
for (i = 0; i < str1.length; i++) {
result.ch[i] = str1.ch[i];
}
for (j = 0; j < str2.length && i + j < MAXLEN; j++) {
result.ch[i + j] = str2.ch[j];
}
result.length = i + j;
return result;
}
// 函数：printString
// 功能：打印一个HString串
// 参数：str - 要打印的HString串
void printString(HString str) {
for (int i = 0; i < str.length; i++) {
printf("%c", str.ch[i]);
}
printf("\n");
}
int main() {
HString S, T, R;
// 初始化串
initString(&S);
initString(&T);
// 赋值
assignString(&S, "Hello");
assignString(&T, " World");
// 打印原始串
printString(S);
printString(T);
// 连接两个串
R = concatString(S, T);
printString(R);
return 0;
}
串的链式存储
串的链式存储结构是指使用链表来存储字符串中的字符。
typedef struct {
char ch;//每个结点存1个字符
struct StringNode* next;
}StringNode, * String;但这样子的操作会造成内存存储密度过低
所以我们可以优化一下代码，在每个结点多存一些字符
typedef struct {
char ch[4];//每个结点存多个字符
struct StringNode* next;
}StringNode, * String;
代码示例
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
char data; // 存储字符数据
struct Node* next; // 指向下一个节点的指针
} Node;
typedef struct {
Node* head; // 指向链表头节点的指针
int length; // 串的长度
} LString;
// 函数：initLString
// 功能：初始化一个LString串
// 参数：str - 指向LString结构的指针
void initLString(LString *str) {
str->head = NULL;
str->length = 0;
}
// 函数：appendLString
// 功能：向LString串追加一个字符
// 参数：str - 指向LString结构的指针
// ch - 要追加的字符
void appendLString(LString *str, char ch) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = ch;
newNode->next = NULL;
if (str->head == NULL) {
// 如果链表为空，新节点作为头节点
str->head = newNode;
} else {
// 否则，找到链表的最后一个节点，并追加新节点
Node* current = str->head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
str->length++;
}
// 函数：printLString
// 功能：打印一个LString串
// 参数：str - 要打印的LString串
void printLString(LString str) {
Node* current = str.head;
while (current != NULL) {
printf("%c", current->data);
current = current->next;
}
printf("\n");
}
// 函数：freeLString
// 功能：释放LString串的内存
// 参数：str - 指向LString结构的指针
void freeLString(LString *str) {
Node* current = str->head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
str->head = NULL;
str->length = 0;
}
int main() {
LString S;
// 初始化串
initLString(&S);
// 追加字符
appendLString(&S, 'H');
appendLString(&S, 'e');
appendLString(&S, 'l');
appendLString(&S, 'l');
appendLString(&S, 'o');
// 打印串
printLString(S);
// 释放内存
freeLString(&S);
return 0;
}
基本操作的实现
求子串
SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串
// 函数SubString：从字符串S中提取从pos位置开始的长度为len的子串
bool SubString(SString *Sub, SString S, int pos, int len) {
if (pos + len - 1 > S.length || pos < 1) // 检查子串范围是否越界
return false; // 如果越界，返回false
for (int i = pos; i < pos + len; i++) // 循环，将子串复制到Sub中
//将源字符串S中从pos开始的第i个字符复制到目标子串Sub的相应位置
Sub->ch[i - pos + 1] = S.ch[i];
Sub->ch[len] = '\0'; // 在子串末尾添加空字符，标记字符串结束
Sub->length = len; // 设置子串的长度
return true; // 如果操作成功，返回true
}比较操作
StrCompare(S,T):比较操作。若S>T，则返回值>0:若S=T，则返回值<0;
//比较操作。若S>T，则返回值>0:若S=T，则返回值<0;
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):定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0
// 函数Index：在主串S中查找子串T的位置
// 返回值：如果找到子串，返回子串在主串中的位置（从1开始计数）
// 如果没有找到，返回0
int Index(SString S, SString T) {
int i = 1, n = StrLength(S), m = StrLength(T);
SString sub; // 定义一个SString变量，用于暂存从主串S中提取的子串
// 循环，直到i超过可能存在子串的最后一个位置
while (i <= n - m + 1) {
SubString(&sub, S, i, m); // 从S中提取从位置i开始的长度为m的子串
if (StrCompare(sub, T) != 0) // 如果提取的子串与T不相等
++i; // 移动到下一个位置
else
return i; // 如果找到相等的子串，返回其在主串中的位置
}
return 0; // 如果循环结束还没有找到子串，返回0
}
总结：
