关于串的基本定义已经在第2章栈和队列以及串中介绍过了,与栈和队列类似,同样存在顺序结构存储的串(这里简称顺序串)和链式结构存储的串(这里简称链串)。
一.顺序串
1.1定义
串的顺序实现是指分配一块连续的存储单元用于串中的元素,并附设表示串长度的标志。
串的顺序结构存储可以描述为:
typedef char ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}String;
1.2基本操作
1.2.1创建串
输入字符元素,以“#”号作为结束标志。
void StrCreat(String* S){
char x;
S->length=0;
printf("Input String_S(End of '#'!):\n");
scanf("%c",&x);
while(x!='#'){
S->data[S->length++]=x;
scanf("%c",&x);
}
}
1.2.2求串长度
因为串的定义中有length变量,只需返回结果便可。
int StrLength(String* S){
return S->length;
}
1.2.3拷贝字符串
将字符串S拷贝到字符串T中,对字符串依次访问,同时赋值于字符串T即可完成拷贝。
void StrCopy(String* S, String* T){
for(int i=0;i<S->length;i++){
T->data[i]=S->data[i];
}
T->length=S->length;
}
1.2.4比较字符串大小
字符串大小比较实际是比较ASCII码大小,从左向右依次比较,如果此时哪个字符串的ASCII码值比较大,则返回结果;如果两个字符串长度不相等,但前面若干个字符均相等,则长度大的字符串比较大。
int StrCompare(String* S,String* T){
int i=0;
while(i!=S->length&&i!=T->length){
if(S->data[i]<T->data[i]){
return -1;
}else if(S->data[i]>T->data[i]){
return 1;
}else{
i++;
}
}
if(i<S->length){
return 1;
}else if(i<T->length){
return -1;
}else{
return 0;
}
}
1.2.5连接字符串
将字符串T连接在字符串S后,注意此时S的长度以便,注意修改length变量。
void StrConcat(String* S, String* T){
int i=S->length;
for(i=i+1;i<S->length+T->length;i++){
S->data[i]=T->data[i-S->length];
}
S->length=i;
}
1.2.6以串S中pos位置开始的len个字符生成子串Sub
因为采用的是顺序存储结构,可以使用函数随机访问,直接找到pos位置,然后将其后len个字符串均赋值给新的子串T便可。
String* SubString(String*S,int pos,int len){
String *T;
T=(String*)malloc(sizeof(String));
T->length=0;
if(pos>S->length||(pos+len)>S->length){
printf("Illege Position!\n");
exit(0);
}
for(int i=pos;i<pos+len;i++){
T->data[T->length++]=S->data[i];
}
return T;
}
二.链串
2.1定义
采用链式存储的串称为链串。一般采用不带头结点的单链表实现。
链串的数据结构描述如下:
typedef struct SNode
{ ElemType data;
struct SNode *next;
}String;
因为采用链式存储时的串与第1章的单链表操作类似,这里便不再详细说明。