数据结构之串的定长顺序存储

数据结构之串的定长顺序存储

1、串的定义：由零个或多个字符组成的有序序列:’abcdef‘

2、串的长度:串中字符的数目称为串的长度

3、空串：’’ ‘ ’空格串

4、子串：子串包含空串和串本身，如 ab 的子串：a、b、ab 和一个空子串共 4 个

5、子串在主串中的位置：比如：a,b,c,d 为以下的 4 个串a = ‘gao’; b = ‘bo’; c = ‘gaobo’; d = ‘gao bo’;首先他们的长度分别是3,2,5,6；同时 a,b 都是 c 和 d 的子串。a 在 c 和 d 中的位置都为 0.而 b在 c 中的位置是 3，在 d 中的位置是 4. 对于串’abcd’来说，他的子串有’a’, ’b’, ’c’, ’d’, ‘ab’, ‘bc’, ‘cd’, ‘abc’, ’bcd’,‘abcd’, ‘ ’总共 11 个

6、串相等：只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。比如：串’abcdef’和’abcdef’就是相等。但是上面的 4个串 a，b，c，d 彼此都不相等。

串的定长顺序存储
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。 既然是定长数组，就存在一个预定义的最大串长度。

串的定长顺序存储数据结构定义

#define SIZE 20
typedef struct Str
{
char elem[SIZE];
int length;//在串里面没有''一说当前有效数据个数
}Str;

串的基本操作

void StrAssign(Str *s,const char *chars);//利用字符串初始化串
void StrCpy(Str *s,Str *t);//将串 t 拷贝到 s
bool IsEmpty(Str *s);//判断串是否为空
int GetLength(Str *s);//求串的长度
void Clear(Str *s);//串清空
//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面
bool SubStr(Str *sub,Str *s,int pos,int len);
bool Insert(Str *s,int pos,Str *t);//在 pos 位置插入 t
//在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标
int BF(Str *s,Str *sub,int pos);
//用 v 替换从 pos 位置开始的第一个 t;
bool DeletePos(Str *s,int pos,int len);//从 pos 位置开始删除 len 个长度
bool Delete(Str *s,int pos,Str *t);//从 pos 位置开始删除子串 t;
bool Replace(Str *s,Str *t,Str *v,int pos);
bool ReplaceAll(Str *s,Str *t,Str *v);//将所有的 t 替换成 v
void Show(Str *s);
void Destroy(Str *s);

头文件str.h

#pragma once
#define SIZE 20
typedef struct Str
{char elem[SIZE];int length;//在串里面没有''一说当前有效数据个数
}Str;
void StrAssign(Str *s, const char *chars);//利用字符串初始化串
void StrCpy(Str *s, Str *t);//将串 t 拷贝到 s
bool IsEmpty(Str *s);//判断串是否为空
int GetLength(Str *s);//求串的长度
void Clear(Str *s);//串清空//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面
bool SubStr(Str *sub, Str *s, int pos, int len);
bool Insert(Str *s, int pos, Str *t);//在 pos 位置插入 t//在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标
int BF(Str *s, Str *sub, int pos);
//用 v 替换从 pos 位置开始的第一个 t;
bool DeletePos(Str *s, int pos, int len);//从 pos 位置开始删除 len 个长度
bool Delete(Str *s, int pos, Str *t);//从 pos 位置开始删除子串 t;
bool Replace(Str *s, Str *t, Str *v, int pos);
bool ReplaceAll(Str *s, Str *t, Str *v);//将所有的 t 替换成 v
void Show(Str *s);
void Destroy(Str *s);

源文件 str.cpp

#include"str.h"
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string>
void StrAssign(Str *s, const char *chars)//利用字符串初始化串
{assert(s != NULL&&chars != NULL);int length = strlen(chars);if (length > SIZE){return;}for (int i = 0; i < length; i++){s->elem[i] = chars[i];}s->length = length;
}
void StrCpy(Str *s, Str *t)//将串 t 拷贝到 s
{assert(s != NULL&&t != NULL);int len = t->length;if (len > SIZE){return;}for (int i = 0; i < len; i++){s->elem[i] = t->elem[i];}}
bool IsEmpty(Str *s)//判断串是否为空
{return s->length == 0;
}
int GetLength(Str *s)//求串的长度
{return s->length;
}
void Clear(Str *s)//串清空
{s->length = 0;
}//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面
bool SubStr(Str *sub, Str *s, int pos, int len)
{assert(sub != NULL&&s != NULL);if (pos<0 || pos>s->length || len > sub->length||pos+len>s->length){return false;}for (int i = 0; i < len; i++){sub->elem[i] = s->elem[i + pos];}sub->length = len;return true;
}
bool Insert(Str *s, int pos, Str *t)//在 pos 位置插入 t
{assert(s != NULL&&t != NULL);int tlen = t->length;int slen = s->length;if (pos<0  || pos + tlen>SIZE){return false;}//先将pos位置后面的数据向后挪tlen个for (int i = slen - 1; i >= pos; i--){s->elem[i + tlen] = s->elem[i];}//将t插入for (int i = 0; i < tlen; i++){s->elem[i + pos] = t->elem[i];}s->length = tlen + slen;return true;}//在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标
//从第pos位置开始 比较s与sub每一个字符 若相等则比较下一个若不相等则从第pos+1开始比较
int BF(Str *s, Str *sub, int pos)
{assert(s != NULL&&sub != NULL);if (pos<0 || pos>s->length){return -1;}int slen = s->length;int sub_len = sub->length;int i = pos;int j = 0;while (i <= slen || j <= sub_len){if (s->elem[i] == sub->elem[j]){i++;j++;}else{j = 0;i = i - j + 1;}}if (j >= sub_len){return i;}return -1;
}
//用 v 替换从 pos 位置开始的第一个 t;bool DeletePos(Str *s, int pos, int len)  //从 pos 位置开始删除 len 个长度
{assert(s != NULL);int slen = s->length;for (int i = pos; i < slen - len; i++)   // abcdef{s->elem[i] = s->elem[len + i];}s->length = slen - len;return true;
}bool Delete(Str *s, int pos, Str *t)  //从 pos 位置开始删除子串 t;
{assert(s != NULL && t != NULL);if (pos < 0 || pos > s->length){return false;}int index = BF(s, t, pos);if (index == -1){return false;}DeletePos(s, index, t->length);return true;
}bool Replace(Str *s, Str *t, Str *v, int pos)  //用 v 替换从 pos 位置开始的第一个 t;
{assert(s != NULL && t != NULL && v != NULL);int index = BF(s, t, pos);if (index == -1){return false;}DeletePos(s, index, t->length);return Insert(s, index, v);
}bool ReplaceAll(Str *s, Str *t, Str *v)  //将所有的 t 替换成 v
{assert(s != NULL && t != NULL && v != NULL);while (Replace(s, t, v, 0)) {};return true;
}void Show(Str *s)
{assert(s != NULL);int slen = s->length;for (int i = 0; i < slen; i++){printf("%c", s->elem[i]);}printf("n");
}