數(shù)據(jù)結(jié)構(gòu)--第四章--課件教學(xué)資料

1、 4.1 串的抽象數(shù)據(jù)類(lèi)型的定義串的抽象數(shù)據(jù)類(lèi)型的定義 串：是由零個(gè)或多個(gè)字符組成的有限序列。串：是由零個(gè)或多個(gè)字符組成的有限序列。 s=a1a2 an 空串：零個(gè)字符的串。空串：零個(gè)字符的串。 長(zhǎng)度：串中字符的數(shù)目。長(zhǎng)度：串中字符的數(shù)目。 子串：串中任意個(gè)連續(xù)的字符組成的子序列。子串：串中任意個(gè)連續(xù)的字符組成的子序列。 主串：包含子串的串。主串：包含子串的串。 位置：通常稱(chēng)字符在序列中的序號(hào)為位置：通常稱(chēng)字符在序列中的序號(hào)為 該字符在串中的位置。該字符在串中的位置。 4.1 串的抽象數(shù)據(jù)類(lèi)型的定義如下串的抽象數(shù)據(jù)類(lèi)型的定義如下： ADT String 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： D ai |aiCh

2、aracterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 串是有限長(zhǎng)的字符序串是有限長(zhǎng)的字符序 列，由一對(duì)單引號(hào)相列，由一對(duì)單引號(hào)相 括，如括，如: a string 基本操作基本操作： StrAssign ( SubString( sub, commander , 1, 9) SubString( sub, commander , 9, 1) 求得 sub = r 求得 sub = commander SubString(sub, commander , 4, 7) sub = ? SubString(sub, beijing

3、, 7, 2) = ? sub = ? SubString( student , 5, 0) = 起始位置和子串長(zhǎng)度之間存在約束關(guān)系起始位置和子串長(zhǎng)度之間存在約束關(guān)系 長(zhǎng)度為長(zhǎng)度為 0 的子串為的子串為“合法合法”串串 Index (S, T, pos) 初始初始條件：條件：串S和T存在，T是非空串， 1posStrLength(S)。 操作結(jié)果：操作結(jié)果： 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos 個(gè)字符之后第一次出現(xiàn)的位置;否則 函數(shù)值為0。 假設(shè) S = abcaabcaaabc , T = bca Index(S, T, 1) = 2; Index(

4、S, T, 3) = 6; Index(S, T, 8) = 0; “子串在主串中的位置子串在主串中的位置”意指子串 中的第一個(gè)字符在主串中的位序位序。 Replace ( / 0號(hào)單元存放串的長(zhǎng)度 一、串的定長(zhǎng)順序存儲(chǔ)表示一、串的定長(zhǎng)順序存儲(chǔ)表示 按這種串的表示方法實(shí)現(xiàn)的串的 運(yùn)算時(shí)，其基本操作為 “字符序列字符序列 的復(fù)制的復(fù)制” 串串的實(shí)際長(zhǎng)度可在這個(gè)預(yù)定義長(zhǎng) 度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義 長(zhǎng)度的串值則被舍去，稱(chēng)之為“截截 斷斷” 特點(diǎn)特點(diǎn): Status Concat(SString S1, SString S2, SString / Concat 例如：例如：串的聯(lián)接算法中需分三種

5、情況處理： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截?cái)?else if (S10 MAXSTRSIZE) / 截?cái)?else / 截?cái)?僅取S1) T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut

6、= FALSE; typedef struct char *ch; / 若是非空串，則按串長(zhǎng)分配 /存儲(chǔ)區(qū)，否則 ch 為NULL int length; / 串長(zhǎng)度 HString; 二、串的堆分配存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示 通常，C語(yǔ)言中提供的串類(lèi)型就是以 這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù) malloc( ) 和 free( ) 進(jìn)行串值空間的動(dòng)態(tài)管 理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)， 稱(chēng)串值共享的存儲(chǔ)空間為“堆堆”。 C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符， 串長(zhǎng)是一個(gè)隱含值。 這類(lèi)串操作實(shí)現(xiàn)的算法為: 先為新生成的串分配一個(gè)存儲(chǔ)空間，然后 進(jìn)行串值的復(fù)制。 三、串的塊鏈存儲(chǔ)表示三、串

7、的塊鏈存儲(chǔ)表示 也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù) 元素是一個(gè)字符，因此用鏈表存儲(chǔ)時(shí)，元素是一個(gè)字符，因此用鏈表存儲(chǔ)時(shí)， 通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符， 而是一個(gè)子串。而是一個(gè)子串。 存儲(chǔ)密度存儲(chǔ)密度 = 數(shù)據(jù)元素所占存儲(chǔ)位 實(shí)際分配的存儲(chǔ)位 #define CHUNKSIZE 80 / 可由用戶(hù)定義的塊大小 typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head

8、, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LString; 例如: 在編輯系統(tǒng)中，整個(gè)文本編輯區(qū) 可以看成是一個(gè)串，每一行是一個(gè)子串， 構(gòu)成一個(gè)結(jié)點(diǎn)。即: 同一行的串用定長(zhǎng)結(jié)構(gòu) (80個(gè)字符), 行和行之間用指針相聯(lián)接。 實(shí)際應(yīng)用時(shí)，可以根據(jù)問(wèn)題所需來(lái) 設(shè)置結(jié)點(diǎn)的大小。 本章作業(yè)本章作業(yè) 1. 1.兩個(gè)串相等的充分必要條件是兩個(gè)串相等的充分必要條件是 什么？什么？ 2. 2.空串與空格串是相同的嗎？為空串與空格串是相同的嗎？為 什么？什么？ 習(xí)題一習(xí)題一 1. for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for

9、 (k=1; k=n; +k) cij+=aik*bkj; O（n3） 2. for (i=1; i=n; i=2*i) +x; O（log2n） 3. s=0; for (i=0; i=n; i+) for (j=0; j=n; j+) for (k=0; knext= p-next ; （2）p-next=s; （3）t=p-data; （4）p-data= s-data ; （5）s-data= t ; 9.在一個(gè)單鏈表中刪除在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作： q=p-next; p-data=p-next-data; p-next= p-nex

10、t-next ; free(q); 習(xí)題一習(xí)題一 10.從順序表中刪除所有值為從順序表中刪除所有值為x的元素。的元素。 void delall(Sqlist while(iL.len for(j=i+1; jnext; While ( p-cost next; If ( p-cost=h Else t=(LNode*) malloc (sizeof (LNode); t-cost=h; t-num=m; q-next=t; t-next=p; 習(xí)題一習(xí)題一 12若一個(gè)棧的輸入序列是若一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素，輸出序列的第一個(gè)元素 是是n，則第，則第i個(gè)輸出元素是（

11、個(gè)輸出元素是（ D ）。）。 A 不確定不確定 B n-i C n-i-1 D n-i+1 13設(shè)棧設(shè)棧S和隊(duì)列和隊(duì)列Q的初始狀態(tài)為空，元素的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6 依次通過(guò)棧依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若，若6個(gè)元素出隊(duì)的順序個(gè)元素出隊(duì)的順序 是是e2、e4、e3、e6、e5、e1，則棧，則棧S的容量至少應(yīng)該是（的容量至少應(yīng)該是（ C ）。）。 A 6 B 4 C 3 D 2 14一個(gè)棧的入棧序列是一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是，則棧的不可能的輸出序列是 （ C ）。）。 A 54321 B

12、 45321 C 43512 D 12345 15在操作序列在操作序列push(1)、push(2)、pop、push(5)、push(7)、 pop、push(6)之后，棧頂元素和棧底元素分別是什么？之后，棧頂元素和棧底元素分別是什么？ （push(k)表示整數(shù)表示整數(shù)k入棧，入棧，pop表示棧頂元素出棧。）表示棧頂元素出棧。） 【解答解答】棧頂元素為棧頂元素為6，棧底元素為，棧底元素為1。 習(xí)題一習(xí)題一 16棧和隊(duì)列是兩種特殊的線(xiàn)性表，棧的操作特性是（棧和隊(duì)列是兩種特殊的線(xiàn)性表，棧的操作特性是（ ），隊(duì)），隊(duì) 列的操作特性是（列的操作特性是（ ），棧和隊(duì)列的主要區(qū)別在于（），棧和隊(duì)列的主要區(qū)別在于（ ）。）。 【解答解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置 不同不同 17循環(huán)隊(duì)列的引入是為了克服（循環(huán)隊(duì)列的引入是為了克服（ ）。）。 【解答解答】假溢出假溢出 18數(shù)組數(shù)組Qn用來(lái)表示一個(gè)循環(huán)隊(duì)列，用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一為隊(duì)頭