我们很早之前应该就接触了字符串的概念

在数据结构里,字符串要单独用一种存储结构来存储

也就是串存储结构,这里的串也就是字符串


严格上说串也是一种线性存储结构

也具有一对一的逻辑关系

一些特殊的串:

空串:存储 0 个字符的串,例如 S = “”(双引号紧挨着);

空格串:只包含空格字符的串,例如 S = ” “(双引号包含 5 个空格);

子串和主串:假设有两个串 a 和 b,如果 a 中可以找到几个连续字符组成的串与 b 完全相同,则称 a 是 b 的主串,b 是 a 的子串。

例如,若 a = “shujujiegou”,b = “shuju”,由于 a 中也包含 “shuju”,因此串 a 和串 b 是主串和子串的关系;只有串 b 整体出现在串 a 中,才能说 b 是 a 的子串,比如 “shujiejugou” 和 “shuju” 就不是主串和子串的关系。子串在主串中的位置,指的是子串首个字符在主串中的位置。


串的定长顺序存储结构

最简单的理解就是char[]数组里面存放字符串

例如char[6] = {‘a’,’b’,’c’,’d’,’e’};就是一个串的定长顺序存储结构

底层实现就是数组,一般我们认知里的数组都是有固定长度的

定长在这里的意思便是固定长度的数组

但是实际上我们可以使用动态分配的方法去存放字符串

如果用教材的方式实现的话,我们需要加上一个int来定义这个固定长度

也就是顺序串

一般定义如下

typedef struct
{
    char data[Maxsize];
    int length;
}Sqstring;

基本运算如下

#include<iostream>
using namespace std;
#define Maxsize 100

class Sqstring{
    public:
        Sqstring();
        void Strassign(char str[]);
        void OutString();
        void OutLength();
        void InsertStr(Sqstring s,int i,Sqstring &final);
        void DeleteStr(int i,int j,Sqstring &final);
        void ChangeStr(Sqstring s,int i,int j,Sqstring &final);
        void GetStr(int i,int j,Sqstring &final);
        void Contact(Sqstring s1,Sqstring s2);
        
        char data[Maxsize];
        //存放串字符 
        int length;
        //存放串长度 
};

Sqstring::Sqstring(){
    length = 0;
}

void Sqstring::Strassign(char str[]){
    int i=0;
    for(i=0;str[i]!='\0';i++){
        data[i] = str[i];
    }//当传入的字符串检测到空的时候停止 
    
    length = i;//设定一下串的长度 
}//生成串

void Sqstring::OutString(){
    int i;
    if(length > 0){
        for(i=0;i<length;i++){
            cout<<data[i]<<" ";
        }
    }
    cout<<endl;
}//输出串 

void Sqstring::OutLength(){
    cout<<length<<endl;
}//输出长度 

void Sqstring::InsertStr(Sqstring s,int i,Sqstring &final){
    int j;
    final.length = 0;
    if(i<=0 || i>length){
        return;
    }else{
        for(j=0;j<i-1;j++){
            final.data[j] = data[j];
        }//把原来串第i个位置前的字符赋值给最后输出的字符串 
        for(j=0;j<s.length;j++){
            final.data[j+i-1] = s.data[j];
        }//把要插入的串添加到最后输出的字符串
        for(j=i-1;j<length;j++){
            final.data[s.length+j] = data[j];
        }//把原来串的剩余部分添加进最后输出的字符串 
        final.length = s.length +length;//新串的长度 
    }
}//插入字串生成新的串

void Sqstring::DeleteStr(int i,int j,Sqstring &final){
    int k;
    final.length = 0;
    if(i<=0 || i>length || i+j>length+1){
        return;
    }else{
        for(k=0;k<i-1;k++){
            final.data[k]=data[k];
        }//把指定位置前的原串元素给新串
        for(k=i+j-1;k<length;k++){
            final.data[k-j]=data[k];
        }//把扣去指定位置指定长度元素剩下的元素给新串
        final.length = length - j;
        //新串的长度等于原长度减去指定长度 
    }
}//删除指定位置指定长度的串后生成新串 
 
void Sqstring::ChangeStr(Sqstring s, int i, int j, Sqstring &final){
    int k;
    final.length = 0;
    if(i<=0 || i>length || i+j >length +1){
        return;
    }else{
        for(k=0;k<i-1;k++){
            final.data[k] = data[k];
        }//指定位置前元素转移
        for(k=0;k<s.length;k++){
            final.data[i+k-1] = s.data[k]; 
        }//把s的元素转移过去
        for(k=i+j-1;k<length;k++){
            final.data[s.length+k-j] = data[k];
        }//把剩余的元素转移过去
        final.length = s.length + length - j; 
    }
}//替换字符串中的一部分生成新串

 void Sqstring::GetStr(int i,int j,Sqstring &final){
 	int k;
 	final.length = 0;
 	if(i<=0 || i>length ||i+j>length +1){
     	return;	
    }else{
        for(k=0;k<=j-1;k++){
            final.data[k] = data[k+i];
        }
        final.length = j;
    }
}//提取指定位置指定长度的字符串 

void Sqstring::Contact(Sqstring s1,Sqstring s2){
    int i;
    length = s1.length+s2.length;
    for(i=0;i<s1.length;i++){
        data[i] = s1.data[i];
    }
    for(i=0;i<s2.length;i++){
        data[s1.length+i] = s2.data[i];
    }
}//连接两个字符串生成新串 

int main(){
    char str[15]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','\0'};
    char str1[4]={'x','y','z','\0'};
    
    Sqstring s;
    Sqstring s1;
    Sqstring s2;
    Sqstring s3;
    Sqstring s4;
    
    s.Strassign(str);
    s1.Strassign(str1);
    s.OutString();
    s.OutLength();
    s1.OutString();
    s.InsertStr(s1,9,s2);
    s2.OutString();
    s.DeleteStr(2,5,s2);
    s2.OutString();
    s.ChangeStr(s1,2,5,s2);
    s2.OutString();
    s.GetStr(2,10,s3);
    s3.OutString();
    s4.Contact(s1,s2);
    s4.OutString();
    
    return 0; 
}

串的堆分配存储结构

前面也说到了,堆分配的实现就是采用动态数组去存储字符串

通常编程语言会将程序占有的内存空间分成多个不同的区域

程序包含的数据会被分门别类并存储到对应的区域

所以在这里稍微补充一下知识(参考来源)

  • 1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
  • 2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由系统回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。
  • 3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域(读写), 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域(ZI)。 – 程序结束后由系统释放
  • 4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放 (只读)
  • 5、程序代码区—存放函数体的二进制代码。 (只读)

C/C++不提供垃圾回收机制,因此需要对堆中的数据进行及时销毁,防止内存泄漏,使用free和delete销毁new和malloc申请的堆内存,而栈内存是动态释放。

这个我需要研究研究

之后再补充


串的块链存储结构

事实上就是链串

相比书上的做法我还是引入了头指针head

如果不用head按照书上的方法一样也可以实现

#include<iostream>
using namespace std;
#define Maxsize 100

struct SNode{
    char data;
    SNode *next;
};

class LinkString{
    public: 
        LinkString();
        void StrAssign(char str[]);
        void OutString();
        void OutLength();
        void DeleteStr();
        void InsertStr(LinkString s,int i,LinkString &final);
        void DeleteLocateStr(int i,int j,LinkString &final);
        void ChangeLocateStr(int i,int j,LinkString s,LinkString &final);
        void GetStr(int i,int j,LinkString &final);
        void Contact(LinkString s1,LinkString s2);
        
        SNode *head;
        int length;
};

LinkString::LinkString(){
    head = NULL;
    length = 0;
}

void LinkString::StrAssign(char str[]){
    SNode *p,*q;
    head = new SNode;
    q = head; 
     
    for(int i=0;str[i] != '\0';i++){
        p = new SNode;
        p->data = str[i];
        q->next = p;
        q = p;
        length++;
    }
    q->next = NULL;
}//读取字符到串中 

void LinkString::OutString(){
    SNode *p;
    p = head->next;
    while(p != NULL){
        cout<<p->data<<" ";
        p = p->next; 
    }
    cout<<endl;
}//输出串 

void LinkString::OutLength(){
    cout<<length<<endl;
}//输出串的长度 

void LinkString::DeleteStr(){
    SNode *p;
    p = head->next;
    while(p != NULL){
        delete p;
        p = p->next;
    }
}//删除串 

void LinkString::InsertStr(LinkString s,int i,LinkString &final){
    int k;
    SNode *p,*q;
    p = head->next; 
    final.head = new SNode;
    final.head->next = p;
    for(k=0;k<i;k++){
        p = p->next;
    }
    q = new SNode;
    q = p->next;
    p->next = s.head->next;
    for(k=0;k<s.length;k++){
        p = p->next;
    }
    p->next = q;
    final.length = length + s.length;
}//插入串生成新串

void LinkString::DeleteLocateStr(int i,int j,LinkString &final){
    int k;
    SNode *p,*q;
    p = head->next;
    final.head->next = p;
    for(k=0;k<i;k++){
        p = p->next;
    }
    q = p;
    for(k=0;k<i+j;k++){
        q = q->next;
    }
    p->next = q;
    final.length = length - j;
}//删除指定位置指定长度的字符串


int main(){
    char str[15]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','\0'};
    char str1[4]={'x','y','z','\0'};
    
    LinkString s;
    LinkString s1;
    LinkString s2;
    LinkString s3;
    LinkString s4;
    
    s.StrAssign(str);
    s1.StrAssign(str1);
    s.OutString();
    s.OutLength();
    s.InsertStr(s1,9,s2);
    s2.OutString();
    s.DeleteLocateStr(2,5,s2);
    s2.OutString();
    
    return 0;	
}

 

发表评论

您的电子邮箱地址不会被公开。