第2章第3节串-数据结构与算法

关于串的基本定义已经在第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 "#"!):
");
    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!
");
        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章的单链表操作类似，这里便不再详细说明。

第2章第3节 串