数据结构篇其六-串

数据结构—串

前置说明

由于学习Java面向对象语言走火入魔，试图在C语言中模拟实现面向对象设计。里面加入了大量的函数指针配合结构体来模拟类中的成员方法
故此篇，亦可称:

面向对象的C语言程序设计
用C语言实现串这种数据结构，并将它应用到解决实际问题。
C语言特性的，麻烦的，不如自动回收的要手动管理内存，容易出Bug的。（bushi。

编程语言：C语言
IDE:VS Code
函数实现灵感：出于Java中的String类提供的方法，在C语言实现一下。

串介绍

由于版本更替，计算机对字符处理越来越多，引入了字符串的概念。
串：由零或多个字符组成的有限序列，又称字符串
一般记为s=“a1a2……an”,s为串的名称，用双引号引起来，部分语言由单引号，三引号的写法。
串的长度串的可见字符数目个数就是串的长度，就是上面的a1,a2……，an。
空串空串的长度为0，空串用"“表示。
主串与字串最初的串为主串，在主串中取一部分连续的字符序列得到一个新串，该串称为字符串的子串。比如"String"其字串可以是"S”,“Str”,""等。
串的比较两个串的比较是比较相应位置的字符，在ASCII码集中每个字符都与整数建立了一一映射。

如比较silly，stupid.第一个字符相等，那么比较第二个字符i,t。我们只需要记得ASCII码集中小写字母的编码是递增关系，而26字母表，i在t前面，故认为“i<t”，比较结束，我们认为silly比stupid小。比较逻辑是这样的。
若两个串长度不一，其中一个串比较完了，那么认为长串更大。
两个串相等的充分必要条件：两个串长度相等且对应字符一一相等。

使用说明

1.若在栈上创建String类型 变量，如String s,需要进行String s={.Init=StrInit},结构体的局部初始化
如下图

#include"String.h"
//很可惜不能实现像Java中的this关键字来隐式传递参数。
int main(){
    //Object-oriented Programming in C

    String s={.Init=StrInit};
    s.Init(&s);
    s.append(&s,"hello");
    s.toString(&s);
    printf("\n");
    s.append(&s,",world!");
    s.toString(&s);
    
    return 0;
}

2.若在栈上创建一个String* 的指针变量，需要调用newString函数，String* str=newString();newString会在堆上创建一个这样的String变量并返回其地址。

int main(){
    //Object-oriented Programming in C
    String* str=newString();
    str->append(str,"hello, ");
    char* arr="1,2,3,4,5";
    str->valueOfCharArrays(str,arr);
    str->toString(str);
    
    return 0;
}

3.由于结构体内置freememory函数指针，通过指针来调用函数可以回收自身内存，调用后相当于销毁了自身。若采用指针，请注意将该指针置空。
4.这里麻烦点在于不好好管理内存容易泄露。

结构体说明(串的顺序结构)

以下是动态字符串定义，全称Dynamic String,简称string。
注意前面字段定义，很显然这是顺序结构的定义。
串的顺序结构是用一组地址连续的存储单元存储串中的字符序列，为了摆脱原有字符串的固定性，我们选择堆区的内存以便我们实现动态扩容。
我们把\0踢出在外，但注意\0还是存在，只不过由我们内部函数封装好，始终给\0预留空间，不对外显示，使用不受\0限制。

typedef struct string{
    //顺序表！】
    //字段/属性/成员
    char* a;//字符指针
    int length;//记录当前字符串的长度，也是有效长度。
    int capacity;//只记录实际有效的字符容量，不包括'\0'，'\0'始终额外留一个字节空间。

    //--------------------------------------------------------------
    //成员函数，用函数指针模拟一下

    //get函数
    int (*getLength)(struct string* self);//获取当前字符串的长度，相当于C库中string函数。
    //操作字符串函数
    void (*toString)(struct string* self);//打印字符串
    void (*append)(struct string* self,const char* str);//连接字符串
    bool (*empty)(struct string* self);//判断字符串是否为空串。
    struct string* (*substring)(struct string* self,int startIndex,int endIndex);//原字符串中创建一个对应区间[startIndex,endIndex)的子字符串。

    //整型，浮点型，字符数组，单个字符的转化为字符串
    void (*valueOfInt)(struct string* self,int val);
    void (*valueOfLong) (struct string* self,long val);
    void (*valueOfFloat) (struct string* self,float val);
    void (*valueOfDouble) (struct string* self,double val);
    void (*valueOfCharArrays)(struct string* self,char val[]);

    //动态字符串之间的操作
    void (*copyOf)(struct string* self,struct string* other);//动态字符串之间的拷贝。
    int (*compareTo)(struct string* self,struct string* other);//比较两个字符串大小
    bool (*equal)(struct string* self,struct string* other);//比较字符串是否相等。
    int (*indexOf)(struct string* S,struct string* T,int pos);//BF算法求子串在主串指定pos之后的下标。

    //管理内存 
     void (*Init)(struct string* str); //字符串普通变量构造函数
     void (*reset)(struct string* self);//重置字符串，如同一开始初始化一样。效果和newString之后相同。
     void (*freememory)(struct string* self);//销毁自身，释放所有动态内存。使用此方法后记得将原有指针置空处理。
}String;

函数说明

gitte

测试不够严谨，难免出错。请自行学习，并在评论区指正错误，谢读。