串的顺序存储
串(String)的顺序存储是指使用一段连续的存储单元来存储字符串中的字符。
计算串的长度
静态存储(定长顺序存储)
#define MAXLEN 255//预定义最大串为255typedef 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; // 如果越界,返回falsefor (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; // 移动到下一个位置elsereturn i; // 如果找到相等的子串,返回其在主串中的位置}return 0; // 如果循环结束还没有找到子串,返回0
}