本章學習要點
◆熟悉串的相關概念以及串與線性表的關係
◆重點掌握串的定長儲存、堆分配儲存的表示方法與基本操作的實現
◆了解串的各種儲存結構，能根據需要合理選用串的儲存結構解決實際問題
「串」(string)，是字串的簡稱，它是一種特殊的線性表，其特殊性在於組成線性表的資料元素是單個字元。字串在計算機處理實際問題中使用非常廣泛，比如人名、地名、商品名、裝置名等均為字串。同樣在文字編輯、自然語言理解和翻譯、源程式的編輯和修改等方面，都離不開對字串的處理。
4.1串的基本概念
4.1.1串的概念
1．串的定義
串（string）是由n個字元組成的有限序列，記為：s=」a0a1a2…an-1」 (n≥0)。
其中，s是串的名字，字串行a0a1a2…an-1是串的值，ai(0≤i≤n-1)可以是字母、數字或其他字元元素；由於在c語言系統中陣列元素的下標是從0開始的，所以串中所含元素的序號等於該元素的下標值加1；串中所含字元的個數n稱為該串的長度，長度為0的字串稱為空串（null string）。
從串的定義可以看出，串實際上是資料元素為字元的特殊的線性表。
例如：（1）a=「x123長度為4的串)
（2）b=「12345654321長度為11的串)
（3）c=「bei jing長度為8的串)
（4）d長度為0的空串)
（5）e=「this is a string」 (長度為16的串)
（6）f=「 is a長度為6的串)
2．子串、主串和位置
串中任意連續的字元組成的子串行稱為該串的子串；相應地，包含子串的串稱為主串。串中的字元在串串行中的序號稱為該字元在該串中的位置；子串的第乙個字元在主串中的位置稱為子串在主串中的位置。顯然，串為其自身的子串，並規定空串為任何串的子串。
顯然，在不考慮空子串的情況下，乙個長度為n的字串具有n(n+1)/2個子串。
例如：在上例的(6)中串f就是(5)中串e的子串，且子串f在主串e中的位置是5。由於空格符也是乙個字元，所以在串g=「abc defghne」中包含有子串「c def」,而串 「cdef」不是串g的子串。
串g中第乙個字元『e』的位置是6，第二個字元『e』的位置是11。
3．串的比較
如果兩個串的長度相等且對應位置上的字元相同，則稱這兩個串相等。兩個串a、b的比較過程是：從前往後逐個比較對應位置上的字元的ascii碼值，直到不相等或有乙個字串結束為止，此時的情況有以下幾種：
（1）兩個串同時結束，表示a等於b；
（2）a中字元的ascii碼值大於b中相應位置上字元的ascii碼值或b串結束，表示a大於b；
（3）b中字元的ascii碼值大於a中相應位置上字元的ascii碼值或a串結束，表示a小於b。
例如：「abc」=「abc」,「abc」<「abcd」,「abxy」>「abcdefg」,「132」>「123456」
「abab」<「abab」,「3+2」>「2+3」。
4．空格串
由乙個或多個空格字元組成的串稱為空格串，空格串的長度為串中所含空格字元的個數。在串操作中不要將空格串和空串混淆。
4.1.2串的基本操作
儘管串的定義和線性表極為相似，但是串的基本操作和線性表有很大差別。**性表的基本操作中，大多以單個元素作為操作物件，比如對線性表的查詢、訪問、插入、刪除和排序等；而在串的基本操作中，通常以串整體或串的一部分（子串）作為操作物件，比如子串的查詢、擷取子串、刪除乙個子串、插入子串和子串替換等操作。
串的基本操作主要有：
（1）strassign(&t,chars)—由字串常量chars生成字串t的操作。
（2）strcopy(&t,s)—由串s複製生成串t的操作。
（3）strcompare(s,t)—若s=t返回0，s>t返回正數，s（4）strlength(s)—返回串s的長度。
（5）concat(&t,s1,s2)—將串s1和s2連線起來生成串t的操作。
（6）substring(&sub,s,pos,len)—以串s中pos位置開始的len個字元生成子串sub的操作。
（7）index(s,t,pos)—返回子串t在s中pos個字元以後出現的位置。
（8）replace(&s,t,v)—將串s中所有不重疊子串t替換為串v的操作。
（9）strinsert(&s,pos,t)—在串s中第pos個字元前插入串t的操作。
（10）strdelete(&s,pos,len)—刪除串s中第pos個字元開始的len個字元的操作。
4.2串的儲存表示與實現
既然串是線性表的特例，所以線性表的兩種儲存結構對於串也是適用的。在應用中具體選用何種儲存結構與串的操作有關，比如對串進行插入和刪除操作運算時選用鏈儲存結構較好，對串進行查詢和求子串運算時選用順序儲存結構較好。
本章主要介紹串的3種儲存表示方法：
（1）串的定長順序儲存表示法
（2）串的堆分配儲存表示法
（3）串的塊鏈式儲存表示法
4.2.1串的定長順序儲存表示
串的定長順序儲存表示是用一組位址連續的儲存單元來儲存串中的字串行。在串的定長順序儲存表示中，按照預定義的大小，為每個定長的串變數分配乙個固定長度的儲存區，所以可以用定長字元陣列來表示。
1．定長順序儲存結構
在c++執行環境中，定長順序結構定義為：
#include"iostream.h"
#include"stdio.h"
#define maxlen 255定義串的最大長度為255
typedef char sstring[maxlen+1定義定長順序儲存型別sstring
2．基本操作的c++程式實現
（1）求串長度操作int length_ss(sstring s)
操作返回串s中所含字元的個數，即串的長度；如果s為空串則返回0。
int length_ss(sstring s)
（2）串連線操作int concat_ss(sstring &t,sstring s1,sstring s2)
該操作將串s1、s2連線生成串t，如果在連線過程中產生了截斷（即s1的長度加上s2的長度大於maxlen）則返回0，否則返回1。
int concat_ss(sstring &t,sstring s1,sstring s2)
t[i]=0;
if((i==maxlen)&&s2[k判斷是否產生截斷*/
return(0);
else
return(1);
}（3）求子串操作int substring_ss(sstring &sub,sstring s,int pos,int len)
該操作擷取串s中從第pos個字元開始的連續的len個字元生成子串sub，如果位置pos和長度len合理則返回1，否則返回0.
int substring_ss(sstring &sub,sstring s,int pos,int len)
sub[i]='\0';
return 1;
}（4）初始化串操作int strassign_ss(sstring &t,char *s)
該操作用字元陣列s，初始化定長順序串t。如果不產生截斷（長度合理）返回1，否則返回0。
int strassign_ss(sstring &t,char *s)
（5）串複製操作void strcopy_ss(sstring &t,sstring s)
該操作將定長順序串s，複製到定長順序串t。
void strcopy_ss(sstring &t,sstring s)
（6）串比較操作int strcompare_ss(sstring s,sstring t)
該操作比較順序串s、t的大小，如果s>t則返回正數,如果s=t則返回0,否則返回負數。
int strcompare_ss(sstring s,sstring t)
（7）串的替換操作int replace_ss(sstring &s,int n,int m,sstring t)
該操作將串s中從第n個字元開始的連續的m個字元替換成串t中的字元，如果n和m的選取合理則返回1，否則返回0。
int replace_ss(sstring &s,int n,int m,sstring t)
{ sstring s1;
int len=length_ss(t);
int i=n-1,j=0,k=n+m-1; /*i為開始替換位置，j指向第乙個替換字元，k為剩餘字元的開始位置*/
if(n<1||m<0||n+m>length_ss(s)+1||length_ss(s)+len-m>maxlen) /*判斷位置是否合理*/
資料結構1800題 第4章串答案
第四章串 一 選擇題 注 子串的定義是 串中任意個連續的字元組成的子串行，並規定空串是任意串的子串，任意串是其自身的子串。若字串長度為n n 0 長為n的子串有1個，長為n 1的子串有2個，長為n 2的子串有3個，長為1的子串有n個。由於空串是任何串的子串，所以本題的答案為 8 8 1 2 1 37...
資料結構符串的基本操作
院系專業 姓名 林楨曦學號 106052010235 級班年 月 日 採用順序結構儲存串，編寫乙個函式substr str1,str2 用於判定str2是否是str1的子串。問題描述編寫乙個函式，實現在兩個已知字串中找出所有非空最長公共子串的長度和最長公共子串的個數。實現要求輸出非空最長公共子串的長...
資料結構C語言串的基本操作
串的基本操作 include include include define m 100 typedef structhstr void main printf 串中字元為 n for i 0 ilength i printf c l ch i printf n break case 2 break ...