第2章第3节 串
最后更新于：2022-04-01 19:51:50
关于串的基本定义已经在[第2章栈和队列以及串](http://blog.csdn.net/u013595419/article/details/50516508#t6)中介绍过了，与栈和队列类似，同样存在顺序结构存储的串（这里简称顺序串）和链式结构存储的串（这里简称链串）。
## 一.顺序串
### 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;ilength;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]data[i]){
return -1;
}else if(S->data[i]>T->data[i]){
return 1;
}else{
i++;
}
}
if(ilength){
return 1;
}else if(ilength){
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;ilength+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;idata[T->length++]=S->data[i];
}
return T;
}
~~~
## 二.链串
### 2.1定义
采用链式存储的串称为链串。一般采用不带头结点的单链表实现。
链串的数据结构描述如下：
~~~
typedef struct SNode
{ ElemType data;
struct SNode *next;
}String;
~~~
因为采用链式存储时的串与[第1章的单链表](http://blog.csdn.net/u013595419/article/details/50481785)操作类似，这里便不再详细说明。
';