目录
一.初始化
顺序表中串的存储
串的链式存储
二.赋值操作：将str赋值给S
链式表
顺序表
三.复制操作：将chars复制到str中
链式表
顺序表
四.判空操作
链式表
顺序表
五.清空操作
六.串联结
链式表
顺序表
七.求子串
链式表
顺序表
八. 比较串的大小
链式表
顺序表
九.定位操作
链式表
顺序表
一.初始化
顺序表中串的存储
#define MaxLen 255
typedef struct{
char ch[MaxLen];//静态数组,系统自动回收
int length;
}SString;
typedef struct{
char *ch;
int length;
}HString;
HString S;
S.ch=(char*)malloc(MaxLen*sizeof(char));//在堆区分配存储空间,所以需要free手动回收
S.length=0;串的链式存储
typedef struct StringNode{
char ch;//一个字符占一个字节
struct StringNode *next;//占4个字节/8个字节
}StringNode,*String;
//以上定义的结构体类型存储密度低,可以采用以下方案定义结构体
typedef struct StringNode{
char *ch;//或一个结点存放更多字符
struct StringNode *next;
}StringNode,*String;二.赋值操作：将str赋值给S
链式表
void StrAssign(const StringNode* str, char** S) {
int len = 0;
const StringNode* currentNode = str;
// 计算字符串长度
while (currentNode != NULL && currentNode->ch != '\0') {
len++;
currentNode = currentNode->next;
}
*S = (char*)malloc((len + 1) * sizeof(char)); // 分配空间，要考虑'\0'所以长度加1
int i = 0;
//将 currentNode 指向 str，我们可以从链表的头部开始逐个访问节点，并依次处理每个节点的字符
currentNode = str;
// 复制字符到新的字符串里
while (currentNode != NULL && currentNode->ch != '\0') {
(*S)[i] = currentNode->ch;
i++;
currentNode = currentNode->next;
}
(*S)[i] = '\0'; // 在新的字符串末尾添加'\0'表示结束
}
顺序表
void StrAssign(SString S, SString& sub) {
int length = 0;
while (S.ch[length] != '\0') {
sub.ch[length] = S.ch[length];
length++;
}
sub.ch[length] = '\0';
}
三.复制操作：将chars复制到str中
链式表
void StrCopy(StringNode* str, const char* chars) {
int len = strlen(chars);
int i;
for (i = 0; i < len; i++) {
str->ch = chars[i];
if (i < len - 1) {
str->next = (StringNode*)malloc(sizeof(StringNode));
// 若字符串还没有复制完毕则手动扩展空间
str->next->ch = '\0'; // 将下一个节点的 ch 字段设置为空字符
str = str->next;
}
}
str->next = NULL;
}
顺序表
和赋值操作相同
void StrCopy(SString S, SString& sub) {
int length = 0;
while (S.ch[length] != '\0') {
sub.ch[length] = S.ch[length];
length++;
}
sub.ch[length] = '\0';
}
四.判空操作
链式表
bool StrEmpty(String str)
{
if(str->ch[0]=='\0')
return true;
else
return false;
}顺序表
bool StrEmpty(SString S) {
if (S.ch[0] == '\0')
return true;
else
return false;
}五.清空操作
void StrClear(StringNode* str)
{
while(str!=NULL){
free(str);
str=str->next;
}
}六.串联结
链式表
void Concat(StringNode* str, char* s1, char* s2) {
int len1 = strlen(s1);
int len2 = strlen(s2);
// 创建一个新的结点用于存储连接后的字符串
StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
newNode->ch = (char*)malloc((len1 + len2 + 1) * sizeof(char)); // 加1是为了存放字符串结束符 '\0'
newNode->next = NULL;
// 连接字符串并保存到新结点的ch字段
strcpy(newNode->ch, s1);
strcat(newNode->ch, s2);
// 找到链表末尾并将新结点连接到其后
while (str->next != NULL) {
str = str->next;
}
str->next = newNode;
}顺序表
void Concat(SString& sub, SString S, SString T) {
int i = 0;
// 复制字符串 S 到 sub
while (S.ch[i] != '\0') {
sub.ch[i] = S.ch[i];
i++;
}
// 复制字符串 T 到 sub
int j = 0;
while (T.ch[j] != '\0') {
sub.ch[i] = T.ch[j];
i++;
j++;
}
sub.ch[i] = '\0'; // 添加字符串结束符
}
七.求子串
链式表
void Insert(StringNode** str, char ch) {
StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
newNode->ch = ch;
newNode->next = NULL;
if (*str == NULL) {
*str = newNode;
return;
}
StringNode* currentNode = *str;
while (currentNode != NULL) {
currentNode = currentNode->next;
}
currentNode->next = newNode;
}
StringNode* SubString(StringNode* str, int pos, int len) {
StringNode* subStr = NULL;
StringNode* currentNode = str;
int currentPos = 0;
while (currentNode != NULL && currentPos < pos + len) {
if (currentPos >= pos) {
Insert(&subStr, currentNode->ch);
}
currentNode = currentNode->next;
currentPos++;
}
return subStr;
}
顺序表
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;
}
八. 比较串的大小
链式表
int getListLength(StringNode* head) {
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
int compareLinkedListLength(StringNode* list1, StringNode* list2) {
int length1 = getListLength(list1);
int length2 = getListLength(list2);
if (length1 > length2) {
return 1;
} else if (length1 < length2) {
return -1;
} else {
return 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;
}九.定位操作
链式表
ListNode* locateNode(StringNode* head, int position) {
if (position <= 0 || head == nullptr) {
return nullptr;
}
ListNode* current = head;
int count = 1;
while (current != nullptr && count < position) {
current = current->next;
count++;
}
return current;
}顺序表
若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0
#define MaxLen 255
typedef struct {
char ch[MaxLen]; // 静态数组,系统自动回收
int length;
} SString;
void SubString(SString& sub, SString S, int start, int length) {
int i;
for (i = 0; i < length; ++i) {
sub.ch[i] = S.ch[start + i];
}
sub.ch[length] = '\0'; // 添加字符串结束符
sub.length = length;
}
int StrCompare(SString S, SString T) {
int i = 0;
while (S.ch[i] != '\0' && T.ch[i] != '\0') {
if (S.ch[i] != T.ch[i]) {
return S.ch[i] - T.ch[i];
}
i++;
}
return S.length - T.length;
}
int Index(SString S, SString T) {
int i = 1, n = S.length, m = T.length; // n, m 分别为字符串 S 和 T 的长度
SString sub;
while (i <= n - m + 1) {//确保了字符串 T 在字符串 S 中进行匹配时不会越界
//假设 n = 10，m = 3，那么 n - m + 1 = 8
//在循环中，当 i = 9 或 i = 10 时，剩余的字符串 S 的长度已经小于 T 的长度，无法再进行匹配
SubString(sub, S, i, m);
if (StrCompare(sub, T) != 0)
++i;
else
return i;
}
return 0;
}以上代码如有错误，请大佬们赐教！！💖💖感谢到大佬们指出错误
