数据结构（9）串的顺序存储结构
串的顺序存储结构
鸽了很久的数据结构篇，最近确实事情好多，为了申请外宿一直和导员斗智斗勇，今天来看一个串这一节，其实就串的基本代码部分不是特别重要，本着复习线性表的目的，我们再来看一遍。
创建串
typedef struct{
char ch[MaxSize];
int length;
}SString;初始化
bool InitString(SString &S){
S.length = 0;
}判空
bool StrEmpty(SString S){
if(S.length==0)
return true;
return false;
}复制：把串S复制得到串T
bool StrCopy(SString &T,SString S){
for(int i=1;i<=S.length;i++){
T.length = S.length;
T.ch[i] = S.ch[i];
}
return true;
}返回串长
int StrLength(SString S){
return S.length;
}求子串
求子串,即用Sub返回S的第pos个字符起 长度为len的子串。这点倒是串新的东西:
- 首先边界情况：就是要求的子串长度大于原串长
- 其次就是从父串S的第pos个位置依次给子串赋值即可
- 子串的长度就是我们给定的len
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;
}
}比较：若S>T,返回>0的值，反之，返回小于0的值,相等就返回0
这里的比大小是根据字母的顺序比的：例：abcab
具体步骤：
- 设置i从1循环到S和T的较短长度值
- 如果发现不相同的元素，就返回两者之差：差为 正数即S>T,负数即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;
}定位：返回主串S中存在与T相同的子串，返回它在主串中第一次出现的位置，没有就返回0
定位这里分别使用了上面的两个函数，思路就是从第一个子串开始，找到这个串的所有子串，再和T进行匹配。
在匹配过程中，我们使用上面的比较函数，若子串和T不相等，就i++一直循环，直至相等，return i。
在最后的位置有一个return 0，这是视频上写的，但我在实现的时候发现加上return 0 最后不管找没找到都会返回0，所以给注释掉了。
int StrLength(SString S);
bool SubString(SString &Sub,SString S,int pos,int len);
int StrCompare(SString S,SString T);
int Index(SString S,SString T){
int i=1;
int n = StrLength(S);
int m = StrLength(T);
SString Sub;//暂存子串
while(i<n-m+1){//能遍历的次数，一个子串一个子串过
SubString(Sub,S,i,m);
if(StrCompare(Sub,T)!=0)
i++;
else
return i;
}
//return 0;//找了一遍也没找到，就返回0
}插入删除输出
//插入
bool Insert(SString &S,int i,char c){
if(i<1 || i>S.length+1 || S.length>=MaxSize)
return false;
for(int j=S.length;j>=i;j--){
S.ch[j] = S.ch[j-1];
}
S.ch[i] = c;
S.length ++;
return true;
}
//删除
bool Delete(SString &S,int i,char *c){
if(i<1 || i>S.length || S.length==0)
return false;
for(int j=i;j<=S.length;j++){
S.ch[j-1] = S.ch[j];
}
*c = S.ch[i];
S.length--;
return false;
}
//输出
bool Print(SString S){
if(S.length==0)
return false;
for(int i=1;i<=S.length;i++){
printf("%c\t",S.ch[i]);
}
printf("\n");
return true;
}
主函数及运行
#include <stdio.h>
#include "l.h"
#include <stdlib.h>
int main (){
SString S1;
SString S2;
SString Sub;
char c;
InitString(S1);
InitString(S2);
InitString(Sub);
char a[7]={'a','b','c','d','e','f','g'};
for(int i=1;i<=7;i++){
Insert(S1,i,a[i-1]);
}
Print(S1);
StrCopy(S2,S1);//S2复制S1
SubString(Sub,S1,3,4);
int t = StrCompare(S2,Sub);//输出-2，因为a比c小
printf("%d\n",t);
Delete(S2,1,&c);
Delete(S2,2,&c);
Print(S2);
int j = Index(S1,S2);
printf("%d\n",j);
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
