首页 > 其他分享 >王道视频-数据结构-笔记4：串

王道视频-数据结构-笔记4：串

时间：2023-02-06 13:36:06浏览次数：76  
标签：结点 ch return chars 笔记 next 王道 StringNode 数据结构


文章目录

  • 0 笔记说明
  • 1 串的定义
  • 2 串的基本操作描述
  • 3 串的存储结构及基本操作实现
  • 3.1 串的顺序存储
  • 3.1.1 使用静态数组实现
  • 3.1.2 使用动态数组实现
  • 3.1.3 具体存储空间分配
  • 3.2 串的链式存储
  • 3.2.1 结点存储单个字符
  • 3.2.2 结点存储多个字符
  • 3.3 基本操作实现
  • 3.3.1 赋值
  • 3.3.1.1 顺序串
  • 3.3.1.2 链串
  • 3.3.2 复制
  • 3.3.2.1 顺序串
  • 3.3.2.2 链串
  • 3.3.3 判空
  • 3.3.3.1 顺序串
  • 3.3.3.2 链串
  • 3.3.4 求长
  • 3.3.4.1 顺序串
  • 3.3.4.2 链串
  • 3.3.5 清空
  • 3.3.5.1 顺序串
  • 3.3.5.2 链串
  • 3.3.6 销毁
  • 3.3.6.1 顺序串
  • 3.3.6.2 链串
  • 3.3.7 串联
  • 3.3.7.1 顺序串
  • 3.3.7.2 链串
  • 3.3.8 求子串
  • 3.3.8.1 顺序串
  • 3.3.8.2 链串
  • 3.3.9 定位
  • 3.3.9.1 顺序串
  • 3.3.9.2 链串
  • 3.3.10 比较
  • 3.3.10.1 顺序串
  • 3.3.10.2 链串
  • 4 KMP算法

0 笔记说明

博客内容是对自己笔记的书面整理，根据自身学习需要，我可能会增加必要内容。

1 串的定义

字符串(String)是由零个或多个字符组成的有限序列，简称为串。一般记为S=‘a1a2…an’(n≥0)，其中S是串名，引号括起来的字符序列是串的值，ai可以是字母、数字或其他字符，串中包含的字符的个数n称为串的长度。n=0时的串称为空串。例如S1=‘HelloWorld’，S2=‘Naruto’，S3=’’，S4=’ '。下面是关于串的几个概念：

（1）子串：串中任意个连续的字符组成的子序列。如’Hello’是串S1的子串。

（2）主串：包含子串的串。如S2是子串’ruto’的主串。

（3）字符在主串中的位置：字符在串中第一次出现的序号。如’r’在S2中的位置是3。注意位序从1开始而不是从0开始。

（4）子串在主串中的位置：子串的第一个字符在主串中的位置。如’World’在S1中的位置为6。

（5）空格串：S3是空串，S4是包含1个空格的空格串。

串是一种特殊的线性表，数据元素之间呈线性关系。串的数据对象限定为字符集，如中文字符、英文字符、数字字符、标点字符等。

2 串的基本操作描述

串的基本操作通常以子串为操作对象。假设有串T=’’，S=‘Naruto’，W=‘Sasuke’，串的基本操作如下：

1、StrAssign(&T,chars)：赋值操作。把串T赋值为chars。

2、StrCopy(&T,S)：复制操作。由串S复制得到串T。

3、StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。

4、Strlength(S)：求串长。返回串S的元素个数。

5、ClearString(&S)：清空操作。将S清为空串。

6、DestroyString(&S)：销毁串。将串S销毁并回收存储空间。

7、Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串。

8、SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。

9、Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0（因为若定位成功，则位置是从1开始的，返回0就说明定位失败了）。

10、StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。主要根据的是字符的ASCII码大小，举个栗子：① ‘abandon’<‘aboard’：从第一个字符开始往后依次对比，先出现更大字符的串就更大；② ‘abstract’<‘abstraction’：长串的前缀与短串相同时，长串更大；③ ‘abstract’<'abstract '：与②相同，长串的前缀与短串相同时，长串更大；④ ‘academic’>‘abuse’：与①相同，从第一个字符开始往后依次对比，先出现更大字符的串就更大；⑤ ‘academic’=‘academic’：只有两个串完全相同时，才相等。

3 串的存储结构及基本操作实现

3.1 串的顺序存储

3.1.1 使用静态数组实现

使用静态数组实现，定长顺序存储，C++代码如下：

#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
//下面两行需要放在main函数中，用来初始化顺序串（就就这么简单）
SString S;
S.length=0;

3.1.2 使用动态数组实现

使用动态数组实现，堆分配存储，C++代码如下：

#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char *ch; //ch指向串的基地址
    int length; //串的长度
}HString;
//下面三行需要放在main函数中，用来初始化顺序串
HString S;
S.ch=(char *)malloc(MAXLEN*sizeof(char));
S.length=0;

3.1.3 具体存储空间分配

关于变量length存储与否、存储在哪里，有四种方案（假定char ch[10]）：

（1）给ch[10]分配一段连续的存储空间后，额外开辟空间去存储length；

（2）ch[0]存储length，这样ch[10]只能存储9个字符。优点：字符的位序和数组下标相同；

（3）没有并且不存储length，以字符’\0’表示串的结尾；

（4）ch[0]不存储任何字符，额外开辟空间去存储length。

3.2 串的链式存储

3.2.1 结点存储单个字符

每个结点存储1个字符，C++代码如下：

typedef struct StringNode{
    char ch;
    struct StringNode *next;
}StringNode,*String;

3.2.2 结点存储多个字符

每个结点存储多个字符，C++代码如下：

typedef struct StringNode{
    char ch[4]; //每个结点存储多个字符，这里我设置存储4个
    struct StringNode *next;
}StringNode,*String;

在这种实现中，若最后一个结点中字符占不满所有区域时通常用#或者其他符号补上。

3.3 基本操作实现

首先说明：

（1）顺序串是用静态数组实现，ch[0]不存储任何字符，额外开辟空间去存储length，如下：

#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;

（2）链串每个结点存储4个字符，如下：

typedef struct StringNode{
    char ch[4]; //每个结点存储多个字符，这里我设置存储4个
    struct StringNode *next;
}StringNode,*String;

3.3.1 赋值

3.3.1.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
int main(){
    SString S;
    S.length=0; //S的初始化
    char a[]="naruto";
    StrAssign(S,a);
    for(int i=1;i<=S.length;i++)
        printf("%c",S.ch[i]);
    printf("\n");
    return 0;
}

输出：

naruto

3.3.1.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
void PrintString(String T){ //打印串T中的所有有效字符,碰到#则代表到了串的结尾
    StringNode *p=T->next; //p指向当前结点,刚开始指向头节点的下一个结点
    if(p==NULL)
        printf("这是一个空串！");
    else
        printf("非空串，输出如下：\n");
    while(p){
        for(int i=0;i<4;i++){
            if(p->ch[i]=='#')
                break;
            printf("%c",p->ch[i]);
        }
        p=p->next; //p指向下一个结点
    }
    printf("\n"); //换个行
}
int main(){
    String S;
    InitString(S);
    char a[]="haikyuu";
    StrAssign(S,a);
    PrintString(S);
    return 0;
}

输出：

非空串，输出如下：
haikyuu

3.3.2 复制

3.3.2.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
bool StrCopy(SString &T,SString S){ //由串S复制得到串T
    //既然S和T都是SString类型，长度肯定符合要求，所以不需要判断长度
    for(int i=1;i<=S.length;i++)
        T.ch[i]=S.ch[i];
    T.length=S.length;
    return true;
}
int main(){
    SString S,T;
    T.length=S.length=0; //初始化
    char a[]="naruto";
    StrAssign(S,a);
    StrCopy(T,S);
    for(int i=1;i<=T.length;i++)
        printf("%c",T.ch[i]);
    printf("\n");
    return 0;
}

输出：

naruto

3.3.2.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
void PrintString(String T){ //打印串T中的所有有效字符,碰到#则代表到了串的结尾
    StringNode *p=T->next; //p指向当前结点,刚开始指向头节点的下一个结点
    if(p==NULL)
        printf("这是一个空串！");
    else
        printf("非空串，输出如下：\n");
    while(p){
        for(int i=0;i<4;i++){
            if(p->ch[i]=='#')
                break;
            printf("%c",p->ch[i]);
        }
        p=p->next; //p指向下一个结点
    }
    printf("\n"); //换个行
}
bool StrCopy(String &T,String S){ //由串S复制得到串T
    StringNode *p=S->next; //p指向扫描S时的当前结点，刚开始指向S的第一个结点
    if(p==NULL)
        return false; //若S为空串，则返回false
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*q; //rear指向链串T的最后一个结点，刚开始指向头结点,q指向新生成的结点
    int i;
    while(p!=NULL){
        q=(StringNode *)malloc(sizeof(StringNode));
        for(i=0;i<4;i++)
            q->ch[i]=p->ch[i];
        q->next=rear->next;
        rear->next=q;
        rear=q;
        p=p->next;
    }
    return true;
}
int main(){
    String S,T;
    InitString(S);
    InitString(T);
    char a[]="sakura";
    StrAssign(S,a);
    StrCopy(T,S);
    PrintString(T);
    return 0;
}

输出：

非空串，输出如下：
sakura

3.3.3 判空

3.3.3.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
bool StrEmpty(SString S){ //若S为空串，则返回true，否则返回false
    return S.length==0;
}
int main(){
    SString S;
    S.length=0;
    char a[]="naruto";
    printf("%d\n",StrEmpty(S));
    StrAssign(S,a);
    printf("%d\n",StrEmpty(S));
    return 0;
}

输出：

1
0

3.3.3.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
bool StrEmpty(String S){ //若S为空串，则返回true，否则返回false
    return S->next==NULL;
}
int main(){
    String T;
    InitString(T);
    if(StrEmpty(T))
        printf("刚开始T是空串\n");
    else
        printf("刚开始T不是空串\n");
    char a[]="haikyuu";
    StrAssign(T,a);
    if(StrEmpty(T))
        printf("现在T是空串\n");
    else
        printf("现在T不是空串\n");
    return 0;
}

输出：

刚开始T是空串
现在T不是空串

3.3.4 求长

3.3.4.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
int Strlength(SString S){ //返回串S的元素个数
    return S.length;
}
int main(){
    SString S;
    S.length=0;
    char a[]="naruto";
    printf("刚开始S的长度为：%d\n",Strlength(S));
    StrAssign(S,a);
    printf("现在S的长度为：%d\n",Strlength(S));
    printf("S为：");
    for(int i=1;i<=S.length;i++)
        printf("%c",S.ch[i]);
    printf("\n");
    return 0;
}

输出：

刚开始S的长度为：0
现在S的长度为：6
S为：naruto

3.3.4.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
int main(){
    String T;
    InitString(T);
    printf("刚开始T的长度为%d\n",strlength(T));
    char a[]="susuke";
    StrAssign(T,a);
    printf("现在T的长度为%d\n",strlength(T));
    return 0;
}

输出：

刚开始T的长度为0
现在T的长度为6

3.3.5 清空

3.3.5.1 顺序串

C++代码如下：

void ClearString(SString &S){ //将S清为空串
    S.length=0;
}

3.3.5.2 链串

对于链串，还是直接销毁比较好，看3.3.6.2 链串一节吧。

3.3.6 销毁

3.3.6.1 顺序串

由于我这里讨论的顺序串是用静态数组实现的，静态数组在main程序结束后就会自动回收内存，不需要手动销毁，如果使用的是动态数组的话使用free释放内存，不过我就不详细介绍这种情况了。

3.3.6.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
void DestroyString(String &S){ //将串S销毁并回收存储空间
    StringNode *q,*p;
    for(p=S->next;p!=NULL;p=q){
        q=p->next;
        free(p);
    }
    S->next=NULL; //令头结点的next指针指向NULL
}
int main(){
    String T;
    InitString(T);
    char a[]="haikyuu";
    StrAssign(T,a);
    printf("刚开始T的长度为%d\n",strlength(T));
    DestroyString(T);
    printf("现在T的长度为%d\n",strlength(T));
    return 0;
}

输出：

刚开始T的长度为7
现在T的长度为0

3.3.7 串联

3.3.7.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
bool Concat(SString &T,SString S1,SString S2){ //用T返回由S1和S2联接而成的新串
    if(S1.length+S2.length>=MAXLEN)
        return false; //总长度超出最大串长，返回false
    for(int i=1;i<=S1.length+S2.length;i++){
        if(i<=S1.length)
            T.ch[i]=S1.ch[i];
        else
            T.ch[i]=S2.ch[i-S1.length];
    }
    T.length=S1.length+S2.length;
    return true;
}
int main(){
    SString S,S1,S2;
    S.length=S1.length=S2.length=0; //初始化
    char a[]="naruto lo";
    char b[]="ves hinata";
    StrAssign(S1,a);
    StrAssign(S2,b);
    Concat(S,S1,S2);
    printf("S为：");
    for(int i=1;i<=S.length;i++)
        printf("%c",S.ch[i]);
    printf("\n");
    return 0;
}

输出：

S为：naruto loves hinata

3.3.7.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
void PrintString(String T){ //打印串T中的所有有效字符,碰到#则代表到了串的结尾
    StringNode *p=T->next; //p指向当前结点,刚开始指向头节点的下一个结点
    if(p==NULL)
        printf("这是一个空串！");
    else
        printf("非空串，输出如下：\n");
    while(p){
        for(int i=0;i<4;i++){
            if(p->ch[i]=='#')
                break;
            printf("%c",p->ch[i]);
        }
        p=p->next; //p指向下一个结点
    }
    printf("\n"); //换个行
}
bool Concat(String &T,String S1,String S2){ //用T返回由S1和S2联接而成的新串
    if(strlength(S1)==0&&strlength(S2)==0)
        return false; //S1、S2均是空串，则返回false
    if(strlength(S1)==0){
        T=S2;
        return true;
    }
    T=S1;
    if(strlength(S2)==0)
        return true;
    StringNode *p,*q;
    for(p=S1->next;p->next!=NULL;p=p->next); //寻找S1的最后一个结点
    StringNode *rear=p; //rear指向链串T的最后一个结点
    int i=0,j;
    while((rear->ch[i]!='#')&&i<4)
        i++;
    if(i==4){ //S1的最后一个结点存的4个字符都是有效的
        rear->next=S2->next; //直接让S1的最后一个结点的next指针指向S2的第一个结点即可
        return true;
    }
    for(q=S2->next;q!=NULL;q=q->next){ //S1的最后一个结点存的4个字符不都是有效的，需要特殊处理
        for(j=0;j<4&&q->ch[j]!='#';j++){
            rear->ch[i++]=q->ch[j];
            if(i==4){
                p=(StringNode *)malloc(sizeof(StringNode));
                i=0;
                p->next=rear->next;
                rear->next=p;
                rear=p;
            }
        }
    }
    while(i<4)
        rear->ch[i++]='#'; //最后一个结点有空缺，使用#填充
    rear->next=NULL;
    return true;
}
int main(){
    String T,S1,S2;
    InitString(T);InitString(S1);InitString(S2);
    char a[]="NAR";
    char b[]="UTO";
    StrAssign(S1,a);
    StrAssign(S2,b);
    Concat(T,S1,S2);
    PrintString(T);
    printf("T的长度为%d\n",strlength(T));
    return 0;
}

输出

非空串，输出如下：
NARUTO
T的长度为6

3.3.8 求子串

3.3.8.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
bool SubString(SString &Sub,SString S,int pos,int len){ //用Sub返回串S的第pos个字符起长度为len的子串
    if(pos<=0 ||pos>S.length||len<=0||pos+len>S.length+1)
        return false;
    for(int i=pos,j=1;i<pos+len;i++)
        Sub.ch[j++]=S.ch[i];
    Sub.length=len;
    return true;
}
int main(){
    SString S,Sub;
    S.length=Sub.length=0; //初始化
    char a[]="naruto";
    StrAssign(S,a);
    SubString(Sub,S,3,4); //用Sub返回串S的第3个字符起长度为len的子串
    printf("Sub为：");
    for(int i=1;i<=Sub.length;i++)
        printf("%c",Sub.ch[i]);
    printf("\n");
    return 0;
}

输出：

Sub为：ruto

3.3.8.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
void PrintString(String T){ //打印串T中的所有有效字符,碰到#则代表到了串的结尾
    StringNode *p=T->next; //p指向当前结点,刚开始指向头结点的下一个结点
    if(p==NULL)
        printf("这是一个空串！");
    else
        printf("非空串，输出如下：\n");
    while(p){
        for(int i=0;i<4;i++){
            if(p->ch[i]=='#')
                break;
            printf("%c",p->ch[i]);
        }
        p=p->next; //p指向下一个结点
    }
    printf("\n"); //换个行
}
bool SubString(String &Sub,String S,int pos,int len){ //用Sub返回串S的第pos个字符起长度为len的子串
    if(pos+len>strlength(S)+1||pos<1||len<1||pos>strlength(S)) //不需要判断S是否为空串，因为已隐含在判断条件中
        return false;
    Sub->next=NULL; //不管Sub原先是不是空串，都从零开始构建，使头结点的next指向NULL
    int i=1,j=(pos-1)/4+1,count=0; //i和j在多处使用,有多个功能;这里的j是计算第pos个字符在第j个结点上;count是计数变量
    StringNode *p,*q,*rear=Sub; //q指向新结点，p指向链串S的某个结点,rear指向Sub的最后一个结点，刚开始指向Sub的头结点
    for(p=S->next;i<j;i++,p=p->next); //找到链串S的第j个结点
    i=(pos-1)%4; //从第j个结点的索引值为i处开始提取字符，i的范围为[0,3]
    j=0; //现在j充当另一个角色：结点索引下标
    while(count<len){
        if(j%4==0){ //需要新建结点并连在Sub上
            q=(StringNode *)malloc(sizeof(StringNode));
            q->next=rear->next;
            rear->next=q;
            rear=q;
            j=0;
       }
        while(j<4&&i<4&&count<len){
            rear->ch[j++]=p->ch[i++];
            count++;
        }
        if(i==4){
            p=p->next; //p需要指向下一个结点
            i=0;
        }
    }
    while(j<4)
        rear->ch[j++]='#'; //如果最后一个结点还有位置空着就用#填充
    return true;
}
int main(){
    String S,Sub;
    InitString(S);InitString(Sub);
    char a[]="hinata";
    StrAssign(S,a);
    SubString(Sub,S,3,4);
    PrintString(Sub);
    printf("Sub的长度为%d\n",strlength(Sub));
    return 0;
}

输出：

非空串，输出如下：
nata
Sub的长度为4

3.3.9 定位

3.3.9.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
bool SubString(SString &Sub,SString S,int pos,int len){ //用Sub返回串S的第pos个字符起长度为len的子串
    if(pos<=0 ||pos>S.length||len<=0||pos+len>S.length+1)
        return false;
    for(int i=pos,j=1;i<pos+len;i++)
        Sub.ch[j++]=S.ch[i];
    Sub.length=len;
    return true;
}
int Index(SString S,SString T){ //若S中不存在与T值相同的子串，则返回0，否则返回T在S中第一次出现的位置
    if(S.length<T.length||S.length==0||T.length==0)
        return 0; //若串T比S长，则T不可能是S的子串；或者其一是空串，则匹配失败
    SString Sub;
    Sub.length=0; //初始化Sub
    int flag=0,i,j; //flag标志是0则代表失败，1代表成功
    for(i=1;i<=S.length-T.length+1;i++){
        SubString(Sub,S,i,T.length); //求S中长度与T相同的子串，然后比较
        for(j=1;j<=T.length;j++)
            if(Sub.ch[j]!=T.ch[j])
                break;
        if(j==T.length+1){ //此时代表匹配成功
            flag=1;break;
        }
    }
    if(flag) //如果匹配成功则返回索引i
        return i;
    return 0; //匹配失败返回0
}
int main(){
    SString S,T;
    S.length=T.length=0; //初始化
    char a[]="naruto";
    char b[]="ut";
    StrAssign(S,a);
    StrAssign(T,b);
    printf("%d\n",Index(S,T));
    return 0;
}

输出：

4

3.3.9.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
bool SubString(String &Sub,String S,int pos,int len){ //用Sub返回串S的第pos个字符起长度为len的子串
    if(pos+len>strlength(S)+1||pos<1||len<1||pos>strlength(S)) //不需要判断S是否为空串，因为已隐含在判断条件中
        return false;
    Sub->next=NULL; //不管Sub原先是不是空串，都从零开始构建，使头结点的next指向NULL
    int i=1,j=(pos-1)/4+1,count=0; //i和j在多处使用,有多个功能;这里的j是计算第pos个字符在第j个结点上;count是计数变量
    StringNode *p,*q,*rear=Sub; //q指向新结点，p指向链串S的某个结点,rear指向Sub的最后一个结点，刚开始指向Sub的头结点
    for(p=S->next;i<j;i++,p=p->next); //找到链串S的第j个结点
    i=(pos-1)%4; //从第j个结点的索引值为i处开始提取字符，i的范围为[0,3]
    j=0; //现在j充当另一个角色：结点索引下标
    while(count<len){
        if(j%4==0){ //需要新建结点并连在Sub上
            q=(StringNode *)malloc(sizeof(StringNode));
            q->next=rear->next;
            rear->next=q;
            rear=q;
            j=0;
       }
        while(j<4&&i<4&&count<len){
            rear->ch[j++]=p->ch[i++];
            count++;
        }
        if(i==4){
            p=p->next; //p需要指向下一个结点
            i=0;
        }
    }
    while(j<4)
        rear->ch[j++]='#'; //如果最后一个结点还有位置空着就用#填充
    return true;
}
int Index(String S,String T){ //若S中不存在与T值相同的子串，则返回0，否则返回T在S中第一次出现的位置
    if(strlength(S)<strlength(T)||strlength(S)==0||strlength(T)==0)
        return 0; //若串T比S长，则T不可能是S的子串；或者其一是空串，则匹配失败
    String Sub;
    InitString(Sub);
    int flag,i,j;
    for(i=1;i<=strlength(S)-strlength(T)+1;i++){
        SubString(Sub,S,i,strlength(T)); //求S中长度与T相同的子串Sub，然后比较Sub与T
        StringNode *p,*q;
        for(flag=0,p=T->next,q=Sub->next;p&&flag==0;p=p->next,q=q->next) //每次比较都初始化flag为0
            for(j=0;j<4;j++)
                if(p->ch[j]!=q->ch[j]){
                    flag=1;break; //当前子串不匹配，需要比较下一个子串，令flag为1
                }
        if(p==NULL&&j==4) //此时代表匹配成功
            return i;
    }
    return 0; //匹配失败返回0
}
int main(){
    char a[]="naruto";char b[]="ut";
    String S,Sub;
    InitString(S);InitString(Sub);
    StrAssign(S,a);StrAssign(Sub,b);
    printf("%d\n",Index(S,Sub));
    return 0;
}

输出：

4

3.3.10 比较

3.3.10.1 顺序串

C++代码如下：

#include<string.h>
#include<stdio.h>
#define MAXLEN 255 //规定最大串长为255
typedef struct{
    char ch[MAXLEN]; //存储的是字符
    int length; //串的实际长度
}SString;
bool StrAssign(SString &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)>=MAXLEN) //因为ch[0]不存储任何字符，所以最多能存储MAXLEN-1个字符
        return false; //chars字符长度超出最大串长，返回false
    for(int i=1;i<=strlen(chars);i++) //从ch[1]开始存储字符
        T.ch[i]=chars[i-1];
    T.length=strlen(chars);
    return true;
}
int StrCompare(SString S,SString T){ //S>T则返回值>0;S=T则返回值=0;S<T则返回值<0
    //从第一个字符开始往后依次对比，先出现更大字符的串就更大
    //长串的前缀与短串相同时，长串更大
    //只有两个串完全相同时，才相等。
    int len=S.length-T.length,i;
    if(S.length==0||T.length==0)
        return len;
    if(len>0){
        for(i=1;i<=T.length;i++){
            if(S.ch[i]>T.ch[i])
                return 1;
            else if(S.ch[i]<T.ch[i])
                return -1;
        }
        if(i==T.length+1) //能执行到这条语句代表S与T的前T.length个字符相同，而S更长，所以返回值大于0
            return 1;
    }
    else if(len<0){
        for(i=1;i<=S.length;i++){
            if(S.ch[i]>T.ch[i])
                return 1;
            else if(S.ch[i]<T.ch[i])
                return -1;
        }
        if(i==S.length+1) //能执行到这条语句代表S与T的前S.length个字符相同，而T更长，所以返回值小于0
            return -1;
    }
    for(i=1;i<=T.length;i++){ //能执行到这条语句代表S与T长度相同，只需比较各个位置的字符大小即可
        if(S.ch[i]>T.ch[i])
            return 1;
        else if(S.ch[i]<T.ch[i])
            return -1;
        }
    return 0; //能执行到这条语句代表S与T长度相同,且各个位置的字符均相同，所以返回0，表示S=T
}
int main(){
    SString S,T;
    S.length=T.length=0; //初始化
    char a[]=""; //数组a存储的是一个字符串
    char b[]=""; //数组b存储的是另一个字符串
    StrAssign(S,a);
    StrAssign(T,b);
    if(StrCompare(S,T)==0)
        printf("S=T");
    else if(StrCompare(S,T)>0)
        printf("S>T");
    else
        printf("S<T");
    printf("\n");
    return 0;
}

输入输出示例：

数组a

数组b

输出

abandon

aboard

S<T

abstract

abstraction

S<T

academic

abuse

S>T

abandon

abandon

S=T

‘’，即空字符串

‘’，即空字符串

S=T

‘’，即空字符串

aboard

S<T

abandon

‘’，即空字符串

S>T

3.3.10.2 链串

C++代码如下：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct StringNode{
    char ch[4]; //每个结点存储4个字符
    struct StringNode *next;
}StringNode,*String;
void InitString(String &T){ //对链串初始化，使用的是带头结点的链串
    T=(StringNode *)malloc(sizeof(StringNode));
    T->next=NULL;
}
bool StrAssign(String &T,char *chars){ //赋值操作,把串T赋值为字符串chars
    if(strlen(chars)==0)
        return false; //字符串是空时返回false，表示赋值失败
    T->next=NULL; //不管T原先是不是空串，都从零开始构建，使头结点的next指向NULL
    StringNode *rear=T,*p; //rear指向链串T的最后一个结点，刚开始指向头结点,p指向新生成的结点
    int i=0,j,k=(strlen(chars))%4; //k为chars的长度对4取余
    while(i<int(strlen(chars)/4)*4){
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4)
            p->ch[j++]=chars[i++];
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    if(k!=0){ //若k非零则代表还有未存储的字符，其个数=k
        p=(StringNode *)malloc(sizeof(StringNode));
        j=0;
        while(j<4){
            if(j<k)
                p->ch[j++]=chars[i++];
            else
                p->ch[j++]='#'; //不够就用#代替
        }
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
    return true;
}
int strlength(String S){ //返回串S的元素个数
    int len=0,i;
    for(StringNode *p=S->next;p!=NULL;p=p->next)
        for(i=0;i<4&&p->ch[i]!='#';i++,len++);
    return len;
}
int StrCompare(String S,String T){ //S>T则返回值>0;S=T则返回值=0;S<T则返回值<0
    //从第一个字符开始往后依次对比，先出现更大字符的串就更大
    //长串的前缀与短串相同时，长串更大
    //只有两个串完全相同时，才相等。
    int len=strlength(S)-strlength(T),i;
    if(strlength(S)==0||strlength(T)==0)
        return len; //都为空串则相同返回0，此时正好len=0
    StringNode *q,*p; //q指向S的结点，p指向T的结点
    if(len>0){ //S较长
        for(q=S->next,p=T->next;p;p=p->next,q=q->next)
            for(i=0;i<4&&p->ch[i]!='#';i++){
                if(q->ch[i]>p->ch[i])
                    return 1;
                else if(q->ch[i]<p->ch[i])
                    return -1;
            }
        if(p==NULL) //能执行到这条语句代表S与T的前strlength(T)个字符相同，而S更长，所以返回值大于0
            return 1;
    }
    else if(len<0){ //T较长
        for(q=S->next,p=T->next;q;p=p->next,q=q->next)
            for(i=0;i<4&&q->ch[i]!='#';i++){
                if(q->ch[i]>p->ch[i])
                    return 1;
                else if(q->ch[i]<p->ch[i])
                    return -1;
            }
        if(q==NULL) //能执行到这条语句代表S与T的前strlength(S)个字符相同，而T更长，所以返回值小于0
            return -1;
    }
    for(q=S->next,p=T->next;p;p=p->next,q=q->next) //能执行到这条语句代表S与T长度相同，只需比较各个位置的字符大小即可
        for(i=0;i<4&&p->ch[i]!='#';i++){
            if(q->ch[i]>p->ch[i])
                return 1;
            else if(q->ch[i]<p->ch[i])
                return -1;
            }
    return 0; //能执行到这条语句代表S与T长度相同,且各个位置的字符均相同，所以返回0，表示S=T
}
int main(){
    String S,T;
    InitString(S);InitString(T);
    char a[]=""; //数组a存储的是一个字符串
    char b[]=""; //数组b存储的是另一个字符串
    StrAssign(S,a);
    StrAssign(T,b);
    if(StrCompare(S,T)==0)
        printf("S=T");
    else if(StrCompare(S,T)>0)
        printf("S>T");
    else
        printf("S<T");
    printf("\n");
    return 0;
}

输入输出示例：

数组a

数组b

输出

abandon

aboard

S<T

abstract

abstraction

S<T

academic

abuse

S>T

abandon

abandon

S=T

‘’，即空字符串

‘’，即空字符串

S=T

‘’，即空字符串

aboard

S<T

abandon

‘’，即空字符串

S>T

4 KMP算法

KMP算法比较复杂，也非常重要，因此我需要花时间去理解与思考，我会单独写一篇关于KMP算法的博客，待更新。

END

标签：结点,ch,return,chars,笔记,next,王道,StringNode,数据结构
From： https://blog.51cto.com/u_14975310/6038976

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99