串的顺序存储

一、串的定长顺序存储

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

#define MAXSIZE 256
char s[MAXSIZE];

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

如何标识实际长度呢?

  1. 类似顺序表,用C++串描述如下:
typedef struct {
  char data[MAXSIZE];
  int Length;
} SeqString;

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

串的顺序存储1:

串的顺序存储

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

    串的顺序存储2:

    串的顺序存储2

  2. 设定长串存储空间: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;
}

(二)串连接

把两个串s1和s2首尾连接成一个新串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]);
}
用户头像
登录后发表评论