Tim的资源站

一、串的定长顺序存储

类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列。所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区。例如：

#define MAXSIZE 256
char s[MAXSIZE];

则串的最大长度不能超过256。

如何标识实际长度呢？

1. 类似顺序表，用C++串描述如下：

typedef struct {
  char data[MAXSIZE];
  int Length;
} SeqString;

定义一个串变量：SeqString s;，这种存储方式可以直接得到串的长度：s.length，如下图所示。

串的顺序存储1:

2. 在串味存储一个不会再串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它用\0表示串的结束。这种存储方法不能直接得到串的长度，而是通过判断当前字符是否是\0来确定串是否结束，从而邱的串的长度。

   串的顺序存储2：

   

3. 设定长串存储空间：char s[MAXSIZE+1];，用s[0]存放串的实际长度，串值存放在s[1]~s[MAXSIZE]中，字符的序号和存储位置一致，应用更为方便。

二、顺序串的数据类型定义

（一）串的定义

class String {
  private:
    char *str;  // 存储字符串
    int size;   // 字符串长度

  public:
    String();   // 初始化为空串
    String(char *s);   // 构造函数用于C++串来初始化
    String(const String &obj);  // 构造函数用于C++对象来初始化
    ~String() {   // 析构函数
      delete str;
    }

    String substr(int pos, int length); // 从pos位置取子串
    void insert(const String &obj, int pos);  // 从串对象pos的位置插入子串obj
    void delete(int pos, int length);   // 在串对象pos起位置删除长度为length的子串
    int strsize() {
      return (strlen(str));
    }

    String operator = (String &obj);  // 串对象赋值
    String operator = (char *s);    // C++串赋值
    String operator + (String &obj);  // 串对象连接
    String operator + (char *s);  // 串对象与C++串连接
    friend String operator + (char *s, String &obj);  // C++串与连接串对象
    int StrIndex_BF(int k, String &p); // 简单模式匹配
    int StrIndex_KMP(int k, String &p); // KMP算法
    GetNext(char *t, int next[]);
}

（二）部分成员函数的实现

String::String() {
  size = 1;
  str = new char[size];

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }
  str[0] = '\0';
}

String::String(char *s) { // 用C++串初始化
  size = strlen(s) + 1;
  str = new char[size];

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }

  strcpy(str, s);
}

String::String(const String &obj) { // 用串对象obj初始化串对象
  size = obj.size;
  str = new char[size + 1];

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }

  strcpy(str, obj.str);
}

String String::operator +(String &obj) {  // 两个串对象的连接
  int len;
  String temp;
  delete [] temp.str;
  len = strlen(obj.str) + strlen(str) + 1;
  temp.str = new char[len];
  temp.size = len;

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }

  strcpy(temp.str, str);
  strcat(temp.str, obj.str);
  return temp;
}

String String::operator +(char *s) {  // 一个串对象和一个字符串的连接
  int len;
  String temp;
  delete [] temp.str;
  len = strlen(obj.str) + strlen(str) + 1;
  temp.str = new char[len];
  temp.size = len;

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }

  strcpy(temp.str, str);
  strcat(temp.str, s);
  return temp;
}

String String::operator +(char *s, String &obj) { // 一个字符串和一个串对象的连接
  int len;
  String temp;
  delete [] temp.str;
  len = strlen(s) + strlen(obj.str) + 1;
  temp.str = new char[len];
  temp.size = len;

  if (str == NULL) {
    cout << "申请空间失败" << endl;
    exit(1);
  }

  strcpy(temp.str, s);
  strcat(temp.str, obj.str);
  return temp;
}

String String::substr(int pos, int length) {
  int i;
  String temp;
  temp.str = new char[length + 1];

  for (i = 0; i < length; i++) {
    temp.str[i] = str[i + pos];
  }

  temp.str[i] = '\0';
  return (temp);
}

三、定长数据串的基本运算

（一）求串长

int strLength(char s[]) {
  int i = 0;
  while(s[i] != '\n') i++;
  return i;
}

（二）串连接

把两个串s₁和s₂首尾连接成一个新串s。

int StrConcat1(char s1[], char s2[], char s[]) {
  int i = 0, j, len1, len2;
  len1 = StrLength(s1);
  len2 = StrLength(s2);

  if (len1 + len2 > MAXSIZE - 1) return 0;  // s长度不够

  j = 0;
  while(s1[j] != '\0') {
    s[i] = s1[j];
    i++;
    j++;
  }

  j = 0;
  while(s2[j] != '\0') {
    s[i] = s2[j];
    i++;
    j++;
  }

  s[i] = '\0';
  return 1;
}

（三）求子串

// 用t返回串s中从第i个字符开始的长度为len的子串，1≤i≤串长
int StrSub(char *t, char *s, int i, int len) {
  int slen;
  slen = StrLength(s);

  if (i < 1 || i > slen || len < 0 || len > slen - i + 1) {
    cout << "参数不对" << endl;
    return 0;
  }

  for (j = 0; j < len; j++)
    t[j] = s[i + j - 1];

  t[j] = '\0';
  return 1;
}

（四）串比较

int StrComp(char *s1, char *s2) {
  int i = 0;
  while(s1[i] == s2[i] && s1[i] != '\0') i++;
  return (s1[i] == s2[i]);
}