關于串的基本定義已經在[第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)操作類似，這里便不再詳細說明。