字符串（String）
计算机上的非数值处理的对象基本上是字符串数据。字符串(String)是由零个或you'x多个字符组成的有限序列，一般记为：
s = "a1a2...an" (n>=0)
其中s是串的名，引号内是字符串的值；
ai可以是字母、数字或其他字符；
串中字符数目n称为串的长度，0个字符的串称为空串，它的长度为0；
串中任意个连续的字符组成的子序列称为该串的子串；
包含子串的串相应的称为主串；
字符在序列中的序号称为该字符在串中的位置；
子串在主串中的位置则以子串的第一个字符在主串中的位置来表示；
称两个串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，例如在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，例如在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。
字符串有3种机内表示方法：
方法一：定长顺序存储表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之。
#define MAXSTRLEN 255 //最大串长不超过255
typedef unsigned char String[MAXSTRLEN + 1] //0号单元存放字符串的长度
串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。
对串长有两种表示方法：一是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度；二是在串值后面加一个不计入串长的结束标记字符，如在C语言中以“\0”表示串值的终结。此时的串长为隐含值。
定长顺序存储表示的缺点在于，出现字符串长度超过上界MAXSTRLEN时，一般用截尾法处理，但是这种情况不仅在求联接字符串时可能发生，在串的其他操作中，如插入、置换也可能发生。克服这个弊病惟有不限定串长的最大长度，即动态分配串值的存储空间。
方法二：堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。
本章封装的字符串对象即用堆分配存储方法存储
定义如下：
typedef struct MyString{
char *str;
int length;
}MyString;
这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的。
方法三：串的块链存储表示
和线性表的链式存储结构相类似，也可以采用链表方式存储串值。由于串结构的特殊性——结构中的每个数据元素是一个字符，则用链表存储字符串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。
由于在一般情况下，对串进行操作时，只需要从头向尾顺序扫描即可，则对串值不必建立双向链表。
为了便于串的操作，当以链表存储串值时，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。
在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或很多，这要求我们考虑串值的存储密度。存储密度可定义为：
存储密度 = 串值所占的存储位 / 实际分配的存储位
显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。如果在串处理过程中需要进行内、外存交换的话，则会因为内外存交换操作过多而影响处理的总效率。
应该看到，串的字符集的大小也是一个重要因素，一般的，字符集小，则字符的机内编码就短，这也影响串值的存储方式的选区。
串值的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。
本章封装的字符串数组对象即用块链存储方法存储
定义如下：
typedef struct MyStringArray_P
{
MyString *mystring;
struct MyStringArray_P *next;
}MyStringArray_P;
typedef struct MyStringArray{
MyStringArray_P *This;
MyStringArray_P *front;
MyStringArray_P *tear;
void (*clear)(struct MyStringArray *This);
int (*isEmpty)(struct MyStringArray *This);
int (*length)(struct MyStringArray *This);
int (*index)(struct MyStringArray *This, MyString *e);
int (*get)(struct MyStringArray *This, int index, MyString **e);
int (*getFront)(struct MyStringArray *This, MyString **e);
int (*getTear)(struct MyStringArray *This, MyString **e);
int (*modify)(struct MyStringArray *This, int index, MyString *e);
int (*insert)(struct MyStringArray *This, int index, MyString *e);
int (*delete)(struct MyStringArray *This, int index, MyString **e);
int (*tearPush)(struct MyStringArray *This, MyString *e);
int (*tearPop)(struct MyStringArray *This, MyString **e);
int (*frontPush)(struct MyStringArray *This, MyString *e);
int (*frontPop)(struct MyStringArray *This, MyString **e);
int (*traverse)(struct MyStringArray *This,int (*visit)(MyString **e));
}MyStringArray;
目前实现了的字符串操作函数有：
MyString *myStringAssign(char *str);
int myStringLength(MyString *S);
int isMyStringEmpty(MyString *S);
int clearMyString(MyString *S);
void destroyMyString(MyString *S);
int compareMyString(MyString *S1,MyString *S2);
MyString *copyMyString(MyString *S);
MyString *concatMyString(MyString *S1,MyString *S2);
int myStringIndexChar(MyString *S,char indexElem,int pos);
int insertMyString(MyString *S1,MyString *S2,int pos);
MyString *substrMyString(MyString *S,int start,int end);
MyStringArray *splitMyString(MyString *S,char splitElem);
MyString.c文件
#include <stdio.h>
#include <malloc.h>
#include "MyString.h"
MyString *myStringAssign(char *str){
int i,str_length = 0;
MyString *S = (MyString *)malloc(sizeof(MyString));
if(!S) return NULL;
while(*(str+str_length) != '\0'){
str_length++;
}
str_length++;
S->str = (char *)malloc(str_length*sizeof(char));
if(!S->str){
free(S);
return NULL;
}
S->length = str_length - 1;
for(i=0;i<str_length;i++){
*(S->str + i) = *(str + i);
}
return S;
}
int myStringLength(MyString *S){
return S->length;
}
int isMyStringEmpty(MyString *S){
if(S->length){
return 0;
}else{
return 1;
}
}
int clearMyString(MyString *S){
if(S->str){
free(S->str);
S->str = NULL;
}
S->length = 0;
}
void destroyMyString(MyString *S){
free(S->str);
S->str = NULL;
free(S);
S = NULL;
}
int compareMyString(MyString *S1,MyString *S2){
int i;
int result = 0;
for(i=0;i<S1->length && i<S2->length;i++){
if(*(S1->str+i) != *(S2->str+i)){
result = *(S1->str+i) - *(S2->str+i);
break;
}
}
if(result == 0){
result = S1->length - S2->length;
}
return result;
}
MyString *copyMyString(MyString *S){
int i;
if(!S->str) return NULL;
MyString *temp = (MyString *)malloc(sizeof(MyString));
if(!temp) return NULL;
temp->str = (char *)malloc((S->length+1)*sizeof(char));
if(!temp->str){
free(temp);
return NULL;
}
temp->length = S->length;
for(i=0;i<S->length+1;i++){
*(temp->str + i) = *(S->str + i);
}
return temp;
}
MyString *concatMyString(MyString *S1,MyString *S2){
int i;
if(!S1->str || !S2->str) return NULL;
MyString *temp = (MyString *)malloc(sizeof(MyString));
if(!temp) return NULL;
temp->str = (char *)malloc((S1->length + S2->length + 1)*sizeof(char));
if(!temp->str){
free(temp);
return NULL;
}
for(i=0;i<S1->length;i++){
*(temp->str + i) = *(S1->str + i);
}
for(i=0;i<S2->length+1;i++){
*(temp->str + S1->length + i) = *(S2->str + i);
}
temp->length = S1->length + S2->length;
return temp;
}
int myStringIndexChar(MyString *S,char indexElem,int pos){
int index = -1;
int i;
if(!S) return -1;
for(i=pos;i<S->length;i++){
if(*(S->str + i) == indexElem){
index = i;
break;
}
}
return index;
}
int insertMyString(MyString *S1,MyString *S2,int pos){
int i;
if(!S2->str) return -1;
if(pos < 0 || pos > S1->length) return -1;
S1->str = (char *)realloc(S1->str,(S1->length + S2->length + 1)*sizeof(char));
if(!S1->str) return -1;
for(i=S1->length;i>=pos;i--){
*(S1->str + S2->length + i) = *(S1->str + i);
}
for(i=0;i<S2->length;i++){
*(S1->str + pos + i) = *(S2->str + i);
}
S1->length += S2->length;
return 0;
}
MyString *substrMyString(MyString *S,int start,int end){
int i,length;
if(start < 0 || start >= S->length || end <= 0 || end > S->length || end <= start) return NULL;
MyString *temp = (MyString *)malloc(sizeof(MyString));
if(!temp) return NULL;
length = end - start;
temp->str = (char *)malloc((length+1)*sizeof(char));
if(!temp->str){
free(temp);
return NULL;
}
for(i=0;i<length;i++){
*(temp->str + i) = *(S->str + start + i);
}
*(temp->str + length) = '\0';
temp->length = length;
return temp;
}
MyStringArray *splitMyString(MyString *S,char splitElem){
int start = 0,end = 0,index = 0;
MyStringArray *strarray = NULL;
MyString *strtemp = NULL;
index = myStringIndexChar(S,splitElem,0);
if(index == -1) return NULL;
strarray = InitMyStringArray();
end = index;
if(end != start){
strtemp = substrMyString(S,start,end);
strarray->tearPush(strarray,strtemp);
destroyMyString(strtemp);
if(end == S->length){
return strarray;
}
}
index++;
start = index;
while(index > 0){
index = myStringIndexChar(S,splitElem,index);
if(index != -1){
end = index;
strtemp = substrMyString(S,start,end);
strarray->tearPush(strarray,strtemp);
destroyMyString(strtemp);
if(end == S->length){
break;
}
index++;
start = index;
}
}
if(end != S->length){
end = S->length;
strtemp = substrMyString(S,start,end);
strarray->tearPush(strarray,strtemp);
destroyMyString(strtemp);
}
return strarray;
}
MyString.h文件
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _MYSTRING_H
#define _MYSTRING_H
/* Exported types ------------------------------------------------------------*/
typedef struct MyString{
char *str;
int length;
}MyString;
typedef struct MyStringArray_P
{
MyString *mystring;
struct MyStringArray_P *next;
}MyStringArray_P;
typedef struct MyStringArray{
MyStringArray_P *This;
MyStringArray_P *front;
MyStringArray_P *tear;
void (*clear)(struct MyStringArray *This);
int (*isEmpty)(struct MyStringArray *This);
int (*length)(struct MyStringArray *This);
int (*index)(struct MyStringArray *This, MyString *e);
int (*get)(struct MyStringArray *This, int index, MyString **e);
int (*getFront)(struct MyStringArray *This, MyString **e);
int (*getTear)(struct MyStringArray *This, MyString **e);
int (*modify)(struct MyStringArray *This, int index, MyString *e);
int (*insert)(struct MyStringArray *This, int index, MyString *e);
int (*delete)(struct MyStringArray *This, int index, MyString **e);
int (*tearPush)(struct MyStringArray *This, MyString *e);
int (*tearPop)(struct MyStringArray *This, MyString **e);
int (*frontPush)(struct MyStringArray *This, MyString *e);
int (*frontPop)(struct MyStringArray *This, MyString **e);
int (*traverse)(struct MyStringArray *This,int (*visit)(MyString **e));
}MyStringArray;
/* Includes ------------------------------------------------------------------*/
#include "MyStringArray.h"
MyString *myStringAssign(char *str);
int myStringLength(MyString *S);
int isMyStringEmpty(MyString *S);
int clearMyString(MyString *S);
void destroyMyString(MyString *S);
int compareMyString(MyString *S1,MyString *S2);
MyString *copyMyString(MyString *S);
MyString *concatMyString(MyString *S1,MyString *S2);
int myStringIndexChar(MyString *S,char indexElem,int pos);
int insertMyString(MyString *S1,MyString *S2,int pos);
MyString *substrMyString(MyString *S,int start,int end);
MyStringArray *splitMyString(MyString *S,char splitElem);
#endif
MyStringArray.c文件
#include <stdio.h>
#include <malloc.h>
#include "MyStringArray.h"
static void clear(MyStringArray *This);
static int isEmpty(MyStringArray *This);
static int length(MyStringArray *This);
static int index(MyStringArray *This, MyString *e);
static int get(MyStringArray *This, int index, MyString **e);
static int getFront(MyStringArray *This, MyString **e);
static int getTear(MyStringArray *This, MyString **e);
static int modify(MyStringArray *This, int index, MyString *e);
static int insert(MyStringArray *This, int index, MyString *e);
static int delete(MyStringArray *This, int index, MyString **e);
static int tearPush(MyStringArray *This, MyString *e);
static int tearPop(MyStringArray *This, MyString **e);
static int frontPush(MyStringArray *This, MyString *e);
static int frontPop(MyStringArray *This, MyString **e);
static int traverse(MyStringArray *This,int (*visit)(MyString **e));
MyStringArray *InitMyStringArray(){
MyStringArray *strArray = (MyStringArray *)malloc(sizeof(MyStringArray));
MyStringArray_P *p = (MyStringArray_P *)malloc(sizeof(MyStringArray_P));
strArray->This = p;
p->next = NULL;
strArray->front = p;
strArray->tear = strArray->front;
strArray->clear = clear;
strArray->isEmpty = isEmpty;
strArray->length = length;
strArray->index = index;
strArray->get = get;
strArray->getFront = getFront;
strArray->getTear = getTear;
strArray->modify = modify;
strArray->insert = insert;
strArray->delete = delete;
strArray->tearPush = tearPush;
strArray->tearPop = tearPop;
strArray->frontPush = frontPush;
strArray->frontPop = frontPop;
strArray->traverse = traverse;
return strArray;
}
void DestroyMyStringArray(MyStringArray *strArray){
strArray->clear(strArray);
free(strArray->This);
strArray->This = NULL;
free(strArray);
strArray = NULL;
}
static void clear(MyStringArray *This){
MyStringArray_P *p = This->This->next;
MyStringArray_P *temp = NULL;
while(p){
temp = p;
p = p->next;
free(temp->mystring->str);
temp->mystring->str = NULL;
free(temp);
temp = NULL;
}
p = This->This;
p->next = NULL;
This->front = p;
This->tear = This->front;
}
static int isEmpty(MyStringArray *This){
MyStringArray_P *p = This->This;
if(p->next){
return 0;
}else{
return 1;
}
}
static int length(MyStringArray *This){
int j = 0;
MyStringArray_P *p = This->This->next;
while(p){
j++;
p = p->next;
}
return j;
}
static int index(MyStringArray *This, MyString *e){
MyStringArray_P *p = This->This->next;
int pos = -1;
int j = 0;
if(!e) return -1;
while(p){
if(compareMyString(p->mystring,e) == 0){
pos = j;
}
p = p->next;
j++;
}
return pos;
}
static int get(MyStringArray *This, int index, MyString **e){
MyStringArray_P *p = This->This->next;
int j = 0;
while(p && j < index){
p = p->next;
j++;
}
if(!p || j > index) return -1;
*e = copyMyString(p->mystring);
return 0;
}
static int getFront(MyStringArray *This, MyString **e){
MyStringArray_P *p = This->front->next;
*e = copyMyString(p->mystring);
return 0;
}
static int getTear(MyStringArray *This, MyString **e){
MyStringArray_P *p = This->tear;
*e = copyMyString(p->mystring);
return 0;
}
static int modify(MyStringArray *This, int index, MyString *e){
MyStringArray_P *p = This->This->next;
if(!e) return -1;
int j = 0;
while(p && j < index){
p = p->next;
j++;
}
if(!p || j > index) return -1;
free(p->mystring);
p->mystring = copyMyString(e);
if(p->mystring){
return 0;
}else{
return -1;
}
}
static int insert(MyStringArray *This, int index, MyString *e){
MyStringArray_P *p = This->This;
int j = 0;
if(!e) return -1;
MyStringArray_P *temp = (MyStringArray_P *)malloc(sizeof(MyStringArray_P));
if(!temp) return -1;
while(p && j < index){
p = p->next;
j++;
}
if(!p || j > index) return -1;
temp->next = p->next;
p->next = temp;
temp->mystring = copyMyString(e);
if(!temp->mystring){
free(temp);
return -1;
}else{
return 0;
}
}
static int delete(MyStringArray *This, int index, MyString **e){
MyStringArray_P *p = This->This;
MyStringArray_P *temp = NULL;
int j = 0;
while(p->next && j < index){
p = p->next;
j++;
}
if(!p->next || j > index) return -1;
temp = p->next;
p->next = temp->next;
*e = copyMyString(temp->mystring);
free(temp);
return 0;
}
static int tearPush(MyStringArray *This, MyString *e){
MyStringArray_P *p = This->This;
if(!e) return -1;
MyStringArray_P *temp = (MyStringArray_P *)malloc(sizeof(MyStringArray_P));
if(!temp) return -1;
temp->mystring = copyMyString(e);
if(temp->mystring){
if(This->front == This->tear){
p->next = temp;
}else{
This->tear->next = temp;
}
temp->next = NULL;
This->tear = temp;
return 0;
}else{
free(temp);
return -1;
}
}
static int tearPop(MyStringArray *This, MyString **e){
MyStringArray_P *p = This->This;
MyStringArray_P *temp = NULL;
while(p->next->next){
p = p->next;
}
temp = p->next;
This->tear = p;
if(!temp) return -1;
*e = copyMyString(temp->mystring);
free(temp);
p->next = NULL;
return 0;
}
static int frontPush(MyStringArray *This, MyString *e){
MyStringArray_P *p = This->This;
if(!e) return -1;
MyStringArray_P *temp = (MyStringArray_P *)malloc(sizeof(MyStringArray_P));
if(!temp) return -1;
temp->mystring = copyMyString(e);
if(temp->mystring){
temp->next = p->next;
p->next = temp;
if(This->front == This->tear){
This->tear = temp;
}
return 0;
}else{
free(temp);
return -1;
}
}
static int frontPop(MyStringArray *This, MyString **e){
if(This->front == This->tear){
e = NULL;
return -1;
}
MyStringArray_P *p = This->front->next;
*e = copyMyString(p->mystring);
This->front->next = p->next;
if(This->tear == p) This->tear = This->front;
free(p);
return 0;
}
static int traverse(MyStringArray *This,int (*visit)(MyString **e)){
if(This->front == This->tear){
return -1;
}
MyStringArray_P *temp = This->front->next;
while(temp){
if(visit(&(temp->mystring)) != 0) break;
temp = temp->next;
}
return 0;
}
MyStringArray.h文件
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _MYSTRINGARRAY_H
#define _MYSTRINGARRAY_H
/* Includes ------------------------------------------------------------------*/
#include "MyString.h"
/* Exported types ------------------------------------------------------------*/
/* Exported macro ------------------------------------------------------------*/
MyStringArray *InitMyStringArray();
void DestroyMyStringArray(MyStringArray *strArray);
#endif
testMyStringArray.c文件
#include <stdio.h>
#include <malloc.h>
#include "MyStringArray.h"
char name[][14] = {"without ","new ","experiences, ","something ","inside ","of ","us ","sleeps."};
int printMyString(MyString **str){
printf("%s",(*str)->str);
return 0;
}
int main(void){
int i;
MyStringArray *strarray = InitMyStringArray();
MyString *string = NULL;
printf("MyStringArray is empty:%d\n",strarray->isEmpty(strarray));
for(i=0;i<8;i++){
string = myStringAssign(name[i]);
strarray->frontPush(strarray,string);
destroyMyString(string);
}
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
printf("MyStringArray is empty:%d\n",strarray->isEmpty(strarray));
printf("MyStringArray length:%d\n",strarray->length(strarray));
strarray->clear(strarray);
printf("MyStringArray is empty:%d\n",strarray->isEmpty(strarray));
printf("MyStringArray length:%d\n",strarray->length(strarray));
for(i=0;i<8;i++){
string = myStringAssign(name[i]);
strarray->tearPush(strarray,string);
destroyMyString(string);
}
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
strarray->get(strarray,3,&string);
printf("the MyString of index 3 is: ");
printMyString(&string);
printf("\n");
destroyMyString(string);
strarray->getTear(strarray,&string);
printf("the tear MyString is: ");
printMyString(&string);
printf(" ,index is: %d\n",strarray->index(strarray,string));
destroyMyString(string);
strarray->getFront(strarray,&string);
printf("the front MyString is: ");
printMyString(&string);
printf("\n");
destroyMyString(string);
string = myStringAssign("me ");
strarray->modify(strarray,6,string);
destroyMyString(string);
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
string = myStringAssign("you and ");
strarray->insert(strarray,6,string);
destroyMyString(string);
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
strarray->delete(strarray,6,&string);
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
printMyString(&string);
printf(" deleted!\n");
destroyMyString(string);
strarray->tearPop(strarray,&string);
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
printMyString(&string);
printf(" tear poped!\n");
destroyMyString(string);
strarray->frontPop(strarray,&string);
printf("MyStringArray: ");
strarray->traverse(strarray,printMyString);
printf("\n");
printMyString(&string);
printf(" front poped!\n");
destroyMyString(string);
DestroyMyStringArray(strarray);
return 0;
}
编译testMyStringArray.c文件：
gcc MyString.c MyString.h MyStringArray.c MyStringArray.h testMyStringArray.c -o testMyStringArray
执行testMyStringArray：
MyStringArray is empty:1
MyStringArray: sleeps.us of inside something experiences, new without
MyStringArray is empty:0
MyStringArray length:8
MyStringArray is empty:1
MyStringArray length:0
MyStringArray: without new experiences, something inside of us sleeps.
the MyString of index 3 is: something
the tear MyString is: sleeps. ,index is: 7
the front MyString is: without
MyStringArray: without new experiences, something inside of me sleeps.
MyStringArray: without new experiences, something inside of you and me sleeps.
MyStringArray: without new experiences, something inside of me sleeps.
you and deleted!
MyStringArray: without new experiences, something inside of me
sleeps. tear poped!
MyStringArray: new experiences, something inside of me
without front poped!
编译testMyString.c文件：
gcc MyString.c MyString.h MyStringArray.c MyStringArray.h testMyString.c -o testMyString
执行testMyString：
str_a :hello , length :6
is MyString empty: 0
str_a equals str_c
is MyString empty: 1
str_a is not equal str_c
str_b :Mr Bluyee, length :9
str_c :hello Mr Bluyee, length :15
the char 'B' index: 9
str_a :hello Mr Bluyee, length :15
str_c :hello, length :5
without new experiences, something inside of us sleeps.
