数据结构（9）串的顺序存储结构

串的顺序存储结构

鸽了很久的数据结构篇，最近确实事情好多，为了申请外宿一直和导员斗智斗勇，今天来看一个串这一节，其实就串的基本代码部分不是特别重要，本着复习线性表的目的，我们再来看一遍。

创建串

代码语言：javascript复制

typedef struct{
    char ch[MaxSize];
    int length;
}SString;

初始化

代码语言：javascript复制

bool InitString(SString &S){
    S.length = 0;
}

判空

代码语言：javascript复制

bool StrEmpty(SString S){
    if(S.length==0)
        return true;
    return false;
}

复制：把串S复制得到串T

代码语言：javascript复制

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;
}

返回串长

代码语言：javascript复制

int StrLength(SString S){
    return S.length;
}

求子串

求子串,即用Sub返回S的第pos个字符起 长度为len的子串。这点倒是串新的东西:

• 首先边界情况：就是要求的子串长度大于原串长
• 其次就是从父串S的第pos个位置依次给子串赋值即可
• 子串的长度就是我们给定的len

代码语言：javascript复制

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。
• 如果循环完发现没有不相同的元素，就返回两者的长度差，长度长的>长度短的

代码语言：javascript复制

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，所以给注释掉了。

代码语言：javascript复制

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
}

插入删除输出

代码语言：javascript复制

//插入
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("%ct",S.ch[i]);
    }
    printf("n");
    return true;
}

主函数及运行

代码语言：javascript复制

#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("%dn",t);
    Delete(S2,1,&c);
    Delete(S2,2,&c);
    Print(S2);
    int j = Index(S1,S2);
    printf("%dn",j);
}

return

0 人点赞