數(shù)據(jù)結(jié)構(gòu)ppt：第3章串與文本編輯.ppt

《數(shù)據(jù)結(jié)構(gòu)ppt：第3章串與文本編輯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)ppt：第3章串與文本編輯.ppt（71頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第3章 串與文本編輯,3.1 串的類型定義 3.2 串的存儲(chǔ)表示 3.3 串的模式匹配算法 3.4 文本編輯 3.5 小結(jié),0,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,1. 串的相關(guān)術(shù)語 串是由零個(gè)或多個(gè)字符組成的有限序列，記為：s= s1s2sn 。其中s是串名；雙引號(hào)內(nèi)的字符序列s1s2sn是串值；n(n=0)表示串的長(zhǎng)度。,1,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,例如：s1= “data structure” //串，長(zhǎng)度為14 串長(zhǎng)度為零的串稱為空串。 例如：s= “” //空串，長(zhǎng)度為0 組成串的字符均為空格的串稱為空格串或空白串。 例如：s= “ ” //空格串，長(zhǎng)度為4

2、,2,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串?？沾侨魏未淖哟?。 例如：s1 = “data structure” s2= “data” //s2是s1的子串 s3= “structure” //s3是s1的子串 s4= “datastructure” //s4不是s1的子串 包含子串的串稱為主串。上例中s1為主串。,3,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,子串的序號(hào)是該子串的第一個(gè)字符在主串中的序號(hào)。在上例子串s2在s1中的序號(hào)為1，s3在s1中的序號(hào)為6。S4不是s1的子串，也可以說，s4在s1中的序號(hào)為0。 當(dāng)且僅

3、當(dāng)串的長(zhǎng)度相等并且對(duì)應(yīng)位置上的字符都相同時(shí)，稱這兩個(gè)字符串是相等的。 例如：s1= “data structure” s2= “data structure” s3= “datastructure ” //s1與s2相等，s3與s1和s2均不相等,4,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,按照串中字符的次序，逐一比較兩個(gè)字符串中字符的大小，以確定兩個(gè)串的大小關(guān)系的操作，稱為串的比較。 例如：s5=data，s6= DATA，則有s5 s6的比較結(jié)果為1，s5 < s6的比較結(jié)果為0。,5,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,2. 串的ADT定義 在引入串的ADT定義前我們先來看一

4、個(gè)字符串應(yīng)用的例子。 【例3-1】有一個(gè)字符串“l(fā)ive on no evil”，檢查它是否為“回文”。當(dāng)一個(gè)字符串順讀和逆讀都一樣，就可以稱這個(gè)字符串是回文。,6,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,英文中的回文具有廣義和狹義之分，廣義的回文是指串中的空格字符不計(jì)入內(nèi)，比如串“ten animals I slam in a net”去掉空格字符后是一個(gè)回文。狹義的回文是指將空格字符計(jì)入在內(nèi)，比如題目中的“Live on no evil.”不過濾掉空格就是回文字符串。單個(gè)英文單詞的回文符合狹義回文。例如：eye、mum、refer、level等。,7,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,判

5、斷一個(gè)字符串s是否為回文（狹義的），需要進(jìn)行如下操作： （1）存儲(chǔ)串s，并以相反順序存儲(chǔ)為串t； （2）比較s與t； （3）得出字符串s是否為回文串的判斷； （4）輸出回文串s 例3-1是一個(gè)串的實(shí)際應(yīng)用問題，為解決問題所需要的有關(guān)串的操作，即串類型應(yīng)該提供的應(yīng)用接口都是以串為單位，而不是串中的單個(gè)字符為單位。下面給出串的ADT定義：,8,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,ADT String Data: D=ai ai ElemSet, i=1,2,...,n,n=0 Structure: S=| ai-1,ai D, i=2,3,,n oPerations: ConstructStri

6、ng() //操作結(jié)果：創(chuàng)建一個(gè)空的串s DestructString() //操作條件：已有串s //操作結(jié)果：銷毀當(dāng)前串s StringLen() //操作條件：已有串s //操作結(jié)果：得到當(dāng)前串s的實(shí)際長(zhǎng)度,9,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,StringCpy(t) //操作條件：已有串s和參數(shù)串t //操作結(jié)果：將t復(fù)制到當(dāng)前串s中 OutputString() //操作條件：已有串s //操作結(jié)果：輸出當(dāng)前串s SubString(pos, len, ,11,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,3.2.1 串的順序存儲(chǔ) 將串所占用空間的大小稱為串容量，實(shí)際存在的元素個(gè)數(shù)稱

7、為串長(zhǎng)，如圖3-1所示。,12,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,為了表示串的結(jié)束，可在串內(nèi)容最后一個(gè)有效字符后，再多開辟一個(gè)存儲(chǔ)空間，存放結(jié)束標(biāo)志0 （C/C++語言中的字符串就采用這種方法），如圖3-2所示。,13,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,借助于順序存儲(chǔ)時(shí)數(shù)組的0號(hào)下標(biāo)存儲(chǔ)串長(zhǎng)，即有效地利用了空間，又使得串中字符的位序與其存放位置（下標(biāo)）一致，如圖3-3所示。,14,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,定義順序串： #define MAX 100 class SqString public: char *base;//存儲(chǔ)串的字符數(shù)組 //base0表示串的實(shí)際長(zhǎng)度,不

8、另設(shè)結(jié)束標(biāo)志 int maxlen;//表示串的最大長(zhǎng)度 public: SqString();//構(gòu)造函數(shù) SqString(char *s); //構(gòu)造函數(shù) SqString(SqString //析構(gòu)函數(shù),15,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,bool InsertString(int pos,SqString ,16,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,順序串的構(gòu)造與析構(gòu) 串的構(gòu)造有三種方法，分別是構(gòu)造空串、由基本類型的字符串構(gòu)造一個(gè)新串以及使用串對(duì)象來構(gòu)造串。下面給出三種方法構(gòu)造串的實(shí)現(xiàn)過程。 （1）構(gòu)造空的順序串。 【算法3-1-1】 SqString::SqString

9、() maxlen=MAX; base=new charmaxlen+1;//0下標(biāo)留作記錄長(zhǎng)度 base0=0; ,17,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,（2）由基本字符串構(gòu)造一個(gè)新串。 【算法3-1-2】 SqString::SqString(char *s)//由機(jī)內(nèi)標(biāo)準(zhǔn)串構(gòu)造 maxlen=MAX; base= new charmaxlen+1; base0=strlen(s); for(int i=0;si!=0;i++) basei+1=si; ,18,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,（3）使用串對(duì)象來構(gòu)造串。 【算法3-1-3】 SqString::SqString(

10、SqString ,19,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,（4）析構(gòu)函數(shù) 【算法3-1-4】 SqString::SqString() delete base; ,20,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,順序串插入操作 順序串插入操作的功能是將一個(gè)指定的串插入到當(dāng)前串中的指定位置之前，以s串和t串分別表示當(dāng)前串和待插入串，則插入前后s串與t串的狀態(tài)如圖3-4（a）和圖3-4（b）所示。,21,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,22,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,順序串插入操作實(shí)現(xiàn)算法為： 檢查插入位置的合法性，即當(dāng)插入位置posbase0，或base0+t.base0 m

11、axlen（沒有足夠空間插入t）時(shí)，提示錯(cuò)誤信息，終止程序； 從pos指向的位置開始，一直到最后的字符，每個(gè)字符都要向后移動(dòng)，移動(dòng)的長(zhǎng)度為t串的長(zhǎng)度； 插入t串，修改s的串長(zhǎng)，操作成功，結(jié)束。,23,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,【算法3-2】 bool SqString::InsertString(int pos,SqString //元素后移,24,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,for(i=1;i<=t.base0;i++) basepos-1+i=t.basei; //插入元素 base0+=t.base0; return true; ,25,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串

12、的存儲(chǔ)表示,順序串刪除操作 順序串刪除操作的功能是刪除s串中從第pos個(gè)位置開始的長(zhǎng)度為len的子串。如圖3-5所示。,26,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,27,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,順序串刪除操作實(shí)現(xiàn)算法為： 檢查參數(shù)的合法性，有兩種不合法的操作條件：一是pos的值不在串s的長(zhǎng)度范圍內(nèi)，即posbase0；二是從串s第pos個(gè)位置開始不存在長(zhǎng)度為len的子串，即pos+len-1base0； 將待刪除的子串復(fù)制給t； 在s中刪除指定的子串，修改s的串長(zhǎng)，操作成功，結(jié)束。,28,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,【算法3-3】 bool SqString::DelS

13、ubString(int pos,int len,SqString,29,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,for(i=pos+len;i<=base0;i++)//元素前移 basei-len=basei; base0-=len; return true; ,30,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,輸出順序串操作 順序串輸出操作的功能是將串中的字符全部輸出。順序串輸出操作實(shí)現(xiàn)算法為： 檢查串時(shí)否為空串，若為空，輸出空串信息； 若串非空，則利用循環(huán)輸出串的內(nèi)容； 操作成功，結(jié)束。,31,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,【算法3-4】 void SqString::OutputSt

14、ring() if(base0==0) //判斷串是否為空串 cout<<空串<

15、次將t串中每一個(gè)字符復(fù)制到s； 更新當(dāng)前串長(zhǎng)，操作成功，返回。,34,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,【算法3-5】 void SqString::ConnectString(SqString ,35,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,6. 求子串（非空子串） 求子串的定義為將串s中的第pos個(gè)字符開始長(zhǎng)度為len的子串，復(fù)制到串t中。如圖3-7所示。,36,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,順序串中求子串的實(shí)現(xiàn)算法為： 檢查參數(shù)的合法性，當(dāng)posbase0，或lenbase0時(shí)，操作失敗； 將當(dāng)前串從pos指向位置開始的長(zhǎng)度為len的子串復(fù)制到串t中； 操作成功，結(jié)束。,37,

16、數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,【算法3-6】 bool SqString::SubString(int pos,int len,SqString ,38,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,3.2.2 串的鏈?zhǔn)酱鎯?chǔ) 串的順序存儲(chǔ)方式節(jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對(duì)串執(zhí)行插入、刪除子串等操作，就需要頻繁移動(dòng)串中的字符，因此，我們引入串的另一種存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)，又稱動(dòng)態(tài)存儲(chǔ)。這樣就可以避免頻繁的插入、刪除操作帶來的效率低下等問題。,39,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下，存儲(chǔ)空間被分成一系列大小相同的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含兩個(gè)域：字符域data和指針域next。其中，

17、字符域用來存放字符，指針域則用來存放指向下一個(gè)結(jié)點(diǎn)的指針。 一個(gè)串可用一個(gè)單鏈表來存儲(chǔ)。鏈表中的結(jié)點(diǎn)數(shù)目等于串的長(zhǎng)度。例如，一個(gè)字符串s=“ABCDEFGHI”，那么它的單鏈表存儲(chǔ)方式如圖3-8所示。,40,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,41,數(shù)據(jù)結(jié)構(gòu)與算法,為了提高串的鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)密度，節(jié)省空間，可以將鏈串的結(jié)點(diǎn)大小設(shè)置為4。那么串s=“ABCDEFGHI”在結(jié)點(diǎn)大小為4的鏈串存儲(chǔ)結(jié)構(gòu)如圖3-9所示。,3.2 串的存儲(chǔ)表示,鏈串的存儲(chǔ)結(jié)構(gòu)可定義如下： #define N 4 struct LStringNode char dataN; struct LStringNode *nex

18、t; ; class LinkString LStringNode *head; int length;,42,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,public: LinkString(); LinkString(char *t); LinkString(LinkString ,43,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,鏈串的插入操作與單鏈表的插入過程相似，但又有明顯的區(qū)別，單鏈表中每一個(gè)結(jié)點(diǎn)都是一個(gè)單獨(dú)的元素，而塊鏈?zhǔn)降拇忻恳粔K有若干個(gè)獨(dú)立的元素，如圖3-10（a）所示，當(dāng)插入位置不是剛好位于每一塊的起始處時(shí)，插入子串的處理相對(duì)要復(fù)雜。為盡量減少插入時(shí)字符的移動(dòng)，可采用犧牲一定存儲(chǔ)空間

19、的辦法，將插入點(diǎn)所在塊的串拆分成兩個(gè)塊，無效字符的位置用“#”填充，如圖3-10（b）所示，這樣，待插入的串就可以直接進(jìn)行鏈接。,44,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,45,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲(chǔ)表示,鏈串插入操作實(shí)現(xiàn)算法為： 判斷插入位置是否有效，無效立即結(jié)束；否則繼續(xù)； 找到插入位置，以指針p指向pos所在塊或其前一塊；若pos對(duì)塊長(zhǎng)取余不為0，p指向pos所在塊，生成新結(jié)點(diǎn)，對(duì)該塊進(jìn)行拆分；否則，p指向pos所在塊的前一塊； 將t串鏈接到s串中； 操作成功，結(jié)束。 【算法3-7】,46,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,設(shè)s和t是給定的兩個(gè)串，其長(zhǎng)度分別為n和m，

20、且有nm，在串s中找到等于子串t的過程稱為模式匹配，其中，串s稱為主串，t稱為模式。如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲(chǔ)位置(或序號(hào))，否則匹配失敗，返回0。,47,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,Brute-Force算法簡(jiǎn)稱為BF算法，亦稱簡(jiǎn)單匹配算法，設(shè)主串s=s1sn，模式串t=t1tm，其基本思想是： 1. 從主串s的第一個(gè)字符s1開始和模式串t=t1tm中的第一個(gè)字符t1比較； 2. 若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，s2和t2； 3. 若不相等，從主串s的第二個(gè)字符s2開始重新與模式串t的第一個(gè)字符t1進(jìn)行比較。 4. 重復(fù)上述過程，

21、如果在主串s中找到一個(gè)與串t相同的子串，則匹配成功，返回模式串t在主串s主的序號(hào)；如果比較完主串s的所有字符序列，沒有和模式串t相等的子串，則匹配失敗返回0。,48,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,設(shè)主串s=“ababcabcacba”模式串t=“abcac”。s的長(zhǎng)度為n(n=12)，t的長(zhǎng)度為m（m=5）。指針i、j分別為主串s、模式串t當(dāng)前比較字符的下標(biāo)。模式匹配的過程如圖3-11所示。,49,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,50,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,51,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,上述匹配過程中，可以得出以下結(jié)果： （1）若在前

22、k-1(k1)次比較過程中未匹配成功，則第k次比較是從s串的第k個(gè)字符sk開始和t中的第一個(gè)字符t1比較； （2）設(shè)某次匹配有sitj，其中1in，1jm，ij，則應(yīng)有si-1=tj-1，... si-j+1=t1。再由（1）可知，下一次匹配串t右移一個(gè)位置，使得與字符t1對(duì)應(yīng)的s的開始位置是i-j+2，即主串的字符si-j+2與模式串的第一個(gè)字符t1進(jìn)行比較。如圖3-12所示。,52,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,53,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,【算法3-8】 int SqString::Indexof(SqString ,54,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹

23、配算法,else i=i-j+2; j=1; if(jt.base0) return i-t.base0;//掃描完畢，匹配成功 else return 0;//匹配失敗 ,55,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,56,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,限于篇幅，不再分析圖3-13所示的串在后續(xù)階段的匹配過程，可按KMP算法的思想繼續(xù)推導(dǎo)。 【算法3-9】,57,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,3.4.1 問題描述與算法分析 文本編輯是指利用計(jì)算機(jī)進(jìn)行編輯工作，修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。 在進(jìn)行文本編輯時(shí)，我們把整個(gè)文本看成是一個(gè)字符串，

24、稱為文本串，為了便于處理，進(jìn)一步地將文本串拆分成若干子串，即頁是文本串的子串，行又是頁的子串。,58,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,例如有下列一段英文： Night-Song in the Jungle Now Rann the Kite brings home the night That Mang the Bat sets free The herds are shut in barn and hut For loosed till dawn are we 把這首小詩看成是一個(gè)文本串，輸入到內(nèi)存后如圖3-14所示。,59,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,60,數(shù)據(jù)結(jié)構(gòu)與算法,3.4

25、 文本編輯,其相應(yīng)的行表如表3-1所示，每一個(gè)行表項(xiàng)包含行號(hào)、該行的起始地址、長(zhǎng)度。,61,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,為實(shí)現(xiàn)文本編輯問題的求解，我們定義一個(gè)文本編輯類Editer如下（其中串的存儲(chǔ)類型采用3.2.1節(jié)的順序串SqString）： #define MAX 50 typedef struct Text_Row_Table //行表元素結(jié)構(gòu)定義 int iRow; SqString *iStartAddress; int iLength; Text_Row_Table; class Editer //文本編輯類的定義 Text_Row_Table RTableMAX;//行表

26、 int Row_Count;//行數(shù),62,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,public: Editer()Row_Count=0; void InputText();//“輸入文本”處理函數(shù) void SearchText();//“查找文本”處理函數(shù) //其他功能，略 ;,63,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,3.4.2 算法實(shí)現(xiàn) 1. 輸入文本 由于各行的文本子串以行表項(xiàng)為標(biāo)識(shí)，因此輸入階段的處理，主要完成的就是每輸入一行文本子串就為其建立一個(gè)行表項(xiàng)，記錄行號(hào)、起始地址與行內(nèi)串長(zhǎng)度。如算法3-10所示。,64,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,【算法3-10】 void Edite

27、r::InputText() char in_strMAX; while(cin.getline(in_str,MAX,n) ,65,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,2. 查找文本 【算法3-11】 void Editer::SearchText() coutstr; SqString s(str); for(int i=0,j;iIndexof_KMP(s)),66,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯, cout=Row_Count) cout<<未找到！<

28、ace std; void main() Editer t1; t1.InputText(); t1.SearchText(); ,68,數(shù)據(jù)結(jié)構(gòu)與算法,,運(yùn)行結(jié)果： Night-Song in the Jungle Now Rann the Kite brings home the night That Mang the Bat sets free 請(qǐng)輸入要查找的文本串 Kite brings 找到了，行號(hào)2 位置14,69,數(shù)據(jù)結(jié)構(gòu)與算法,3.5 小結(jié),串是一種數(shù)據(jù)類型受到限制的特殊線性表，規(guī)定表中的每一個(gè)元素類型只能為字符型。串雖然是線性表，但又有它特殊的地方，即表中元素為單個(gè)字符，但串結(jié)構(gòu)通常不是單個(gè)處理某一個(gè)字符元素，通常是整串進(jìn)行討論。 串的存儲(chǔ)方式與線性表類似，也具有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式。串的插入、刪除等操作較線性表上的操作要復(fù)雜一些。在順序串中給出了串的構(gòu)造、插入、刪除、串的輸出和串的連接等算法。在鏈?zhǔn)酱薪o出了串的插入、刪除等算法。,70,數(shù)據(jù)結(jié)構(gòu)與算法,