数据结构---串（赋值，求子串，比较，定位）
目录
一.初始化
顺序表中串的存储
串的链式存储
二.赋值操作：将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'所以长度加1int 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;elsereturn false;}顺序表
bool StrEmpty(SString S) {if (S.ch[0] == '\0')return true;elsereturn 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 到 subwhile (S.ch[i] != '\0') {sub.ch[i] = S.ch[i];i++;}// 复制字符串 T 到 subint 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;elsereturn i;}return 0;
}以上代码如有错误，请大佬们赐教！！💖💖感谢到大佬们指出错误