关于串的基本定义已经在[第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;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章的单链表](http://blog.csdn.net/u013595419/article/details/50481785)操作类似，这里便不再详细说明。