數(shù)據(jù)結(jié)構案例教程語言版.文字版

1、教學目標與要求：本章主要介紹串的定義、串的結(jié)構及其基本運算的實現(xiàn)，數(shù)組、矩陣的概念、結(jié)構以及相應運算的算法，廣義表的概念和結(jié)構以及相應運算的算法。通過本章學：熟悉串的基本運算的定義，并能利用這些基本運算實現(xiàn)串的其他各種運算的方法。熟練掌握在串的定長順序的方法。結(jié)構上實現(xiàn)串的各種運算理解串的鏈式及索引的方法。掌握稀疏矩陣的定義、三元組表和鏈表結(jié)構。掌握稀疏矩陣的轉(zhuǎn)置運算，了解相應的算法描述。掌握廣義表的定義及其頭尾鏈式廣義表長度、深度的方法。結(jié)構，以及了解求教學重點與難點：本章重點是熟悉數(shù)組的方式、矩陣的壓縮方式，難點是稀疏矩陣的壓縮表示實現(xiàn)的算法。3.1“文學研究助手”案例3.1.1案例實現(xiàn)過

2、程【案例說明】文學研究需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”。假設英文小說存放在一個文本文件中，每個單詞不包含空格且不跨行，單詞由字符序列下功能。且區(qū)分大小寫。設計一個程序，實現(xiàn)以統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)。檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的位置以及次數(shù)。程序運行結(jié)果如圖 3.1 所示。圖 3.1 文學研究助手【案例目的】理解串的有關概念及基本運算，了解串與線性表的關系。使用 C 語言提供的串操作函數(shù)構造與串相關的算法解決簡單的應用問題?！炯夹g要點】算法的基本思路描述如下。建立文本文件。統(tǒng)計文本文件中給定

3、的單詞數(shù)。 設置變量num=0 用于統(tǒng)計單詞數(shù)，字符數(shù)組 w 用于存放文本中的單詞。 如果文件沒有結(jié)束，從文件中取字符，如果當前字符不是空格、回車換行或結(jié)束符，則該字符屬于一個單詞。直到出現(xiàn)單詞分隔符后，把取得的單詞與給定單詞進行比較，如果相同，num 加 1；否則，繼續(xù)查找下一個單詞。檢索給定單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應位置。 設置變量num=0，用于存放每一行的單詞數(shù)，字符數(shù)組 w 用于存放文本中的單詞，row 用于存放該單詞所在的行號，col 數(shù)組用于存放每一行中的若干單詞的位置。78 首先同步驟(2)先取單詞，然后把取得的單詞與給定單詞進行比較，如果相同，記錄下該

4、單詞的位置，并且 num 加 1，否則，繼續(xù)查找下一個單詞。如果當前字符 ch=n，說明該行結(jié)束，輸出該行所需信息，同時 num 清零，進行下一行的統(tǒng)計，直到文件結(jié)束。【代碼及分析】79char filename20;creattext()/*建立文本文件*/ FILE *fp;char ch;prf(請輸入文件名：);gets(filename);/*輸入文本文件名*/ if(fp=fopen(filename,w)=NULL)prf(cannot open filen); return;prf(請輸入文件文件內(nèi)容,以#作為結(jié)束符:n); ch=getchar();/*將從鍵盤輸入的以#為結(jié)

5、束符的一串字符存放在文本文件中*/while(ch!=#) fp(ch,fp); ch=getchar(); fclose(fp);count(char *word) /*統(tǒng)計給定單詞在文件中出現(xiàn)的次數(shù)*/ FILE *fp;char ch,w20; j=0,num=0;if(fp=fopen(filename,r)=NULL) prf(cannot open filen); return 0;while(!feof(fp)/*如果文件沒有結(jié)束*/ ch=fgetc(fp);j=0;while(ch!= &ch!=n&!feof(fp)/*文件中的單詞*/ wj+=ch;ch=fgetc(fp

6、);wj=0;if(strcmp(w,word)=0)/*如果文件中的單詞與給定單詞相同,num 加 1*/ num+;return num;/*num 即為所求單詞數(shù)*/search(char *word)/*用于實現(xiàn)檢索并輸出單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應位置*/ FILE *fp;char ch,w20;3.1.2應用擴展1判斷字符串中心對稱對于給定的一個由 n 個字符組成的字符串 s，判斷其是否為中心對稱串。若中心對稱串為 s=c1c2,cici+1,cn，則 s 滿足如下條件。n 必須是偶數(shù)。假設 j=n/2，則必有 cj = cj+1, cj-1 = cj+2

7、,c1 = cn。要求如下。(1) 用單鏈表n 個字符，單鏈表的結(jié)點長度為 1。(2) 借助棧來判斷字符串是否中心對稱。2文本加密和一個文本串可用事先給定的字母表進行加密。試寫一算法將輸入的文本串進行加密并輸出；另寫一算法，將輸入的已加密的文本串進行并輸出。設字母表為：80a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s jj=0,num=0,row=1,col20,i=0,k;/*num 用于存放每一行單詞數(shù),row行號*/*col 數(shù)組用

8、于在每一行中該單詞出現(xiàn)的相應位置*/ if(fp=fopen(filename,r)=NULL)prf(cannot open filen); return;while(!feof(fp) ch=fgetc(fp); j=0;i+;while(ch!= &ch!=n&!feof(fp) wj+=ch;ch=fgetc(fp); i+; wj=0;if(strcmp(w,word)=0)colnum=i-j;num+; if(ch=n|feof(fp) /*每一行結(jié)束,統(tǒng)計結(jié)果*/if(num)prf(the number of %d row is %dn,row,num); prf(the c

9、ol is:);for(k=0;knum;k+)prf(%5d,colk); prf(n);row+;i=0;num=0;測試數(shù)據(jù)如下：3.1.3相關知識及注意事項1串的概念及其基本運算在計算機的各方面應用中，非數(shù)值處理問題的應用越來越多。如在匯編程序和編譯程序中，源程序和目標程序都是作為一種字符串數(shù)據(jù)進行處理的。在事務處理系統(tǒng)中，用戶的 和地址及貨物的名稱、規(guī)格等也是字符串數(shù)據(jù)。在不同類型的應用中，所處理的字符串具有不同的特點，要有效地實現(xiàn)字符串的處理，就必須根據(jù)具體情況使用合適的結(jié)構。字符串(簡稱為串)，可以將它看作是一種特殊的線性表，其特殊性在于線性表的數(shù)據(jù)元素的類型總是字符型，字符串的

10、數(shù)據(jù)對象約束為字符集。在一般線性表的基本運算中，大多以單個元素作為運算對象，而在串中，則是以串的整體或一部分作為運算對象。因此，一般線性表和串的運算有很大的不同。串是由零個或多個字符組成的有限序列。一般記作s=s1 s2 sn其中 s 是串名，引號括起來的字符序列s1s2sn是串的值，si(1in)稱為串的元素，可以是字母、數(shù)字或其他字符，是串的基本，字符個數(shù) n(n0)稱為串的長度。注意：串值必須用一對雙引號括起來，但雙引號本身不屬，它的作用只是為了避免與變量名或數(shù)的常量而已。串中常用的幾個術語如下?？沾?。由零個字符組成的串稱為空串，空串中不包含任何字符，其長度為 0。空格串。由一個或多個空

11、格組成的串稱為空格串，它的長度是串中所包含的空格的個數(shù)。(3)子串。(4)(5)子串。串中任意個連續(xù)的字符組成的子序列稱為該串的子串?？沾侨魏未闹鞔?。包含子串的串相應地稱為主串。子串在主串中的位置。通常稱字符在序列中的序號為該字符在串中的位置。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。(6) 兩串相等。當且僅當兩個串的長度相等，并且各個對應位置的字符都相等時才相等。例如，假設 a、b、c 和d 為如下的 4 個串。81a=BEI b=JINGEnter a String(len%d) : encrypt a encrypted string : tkzwsdfEnter

12、a encrypted string(len%d) : tkzwsdfa Original String : encrypt它們的長度分別為 3、4、7 和 8，并且 a 和 b 都是 c、d 的子串，a 在 c 和 d 中的位置都是 1，而b 在 c 中的位置是 4、在d 中的位置則是 5，串 a、b、c 和d 彼此都不相等。串的基本運算如下。求串長 Length_Str(S)。初始條件：串 S 存在。運算結(jié)果：返回串 S 中的元素個數(shù)，空串返回 0。串賦值 Assign_Str(S1,S2)。初始條件： S1 是一個串變量，S2 是一個串常量或者一個串變量。運算結(jié)果：將 S2 的串值賦給

13、S1，S1 原來的值被覆蓋掉。串連接 Concat_Str(S1,S2,S) 或 Concat_Str(S1,S2)。初始條件：串 S1、S2 存在。運算結(jié)果：兩個串的連接就是將一個串的串值緊接著放在另一個串的后面，連接成一個串。前者是產(chǎn)生新串 S，S1 和 S2 不改變;后者是在 S1 的后面連接 S2 的串值，S1 改變， S2 不改變。求子串 Sub_Str(S,i,len)。初始條件：串 S 存在，1iLength_Str(S)，0lenLength_Str(S)-i+1 。運算結(jié)果：返回從串 S 的第 i 個字符開始的長度為 len 的子串。串比較 Compare_Str(S1,S2

14、)。初始條件：串 S1、S2 存在。運算結(jié)果：若 S1=S2，返回 0；若 S1S2，返回值大于 0。子串定位 Index_Str(S,T)。初始條件：串 S 和 T 存在，T 為非空串。運算結(jié)果：若 TS，則返回子串 T 在主串 S 中首次出現(xiàn)的位置；否則，返回值 0。(7) 串Insert_Str(S,i,t)。初始條件：串 S 和 T 存在，1iLength_Str(S)+1。運算結(jié)果：將串 T到串 S 的第i 個字符位置上。串刪除 Delete_Str(S,i,len)。初始條件：串 S 存在，1iLength_Str(S)，0lenLength_Str(S)-i+1。運算結(jié)果：刪除串

15、 S 中從第 i 個字符開始的長度為 len 的子串。串替換 Replace_Str(S,T,R)。初始條件：串 S、T 和 R 存在，且 T 不為空。運算結(jié)果：用串 R 替換串 S 中出現(xiàn)的所有與串 T 相等的不的子串。2串的表示串作為線性表的一個特例，線性表的表示方式也適用。但是由于組成串的結(jié)點是單個字符，因此其表示有其特殊之處。82c=BEIJNG d=BEI JING1) 串的順序表示串的順序結(jié)構簡稱順序串，順序串中的字符序列被順序地存放在一組地址連續(xù)的單元中。在 C 語言中有以下幾種實現(xiàn)方式。(1) 定長字符數(shù)組。在串的順序結(jié)構中，按照預定義的大小，為每個定義的串變量分配一個固定長度

16、的區(qū)，則可用定長字符數(shù)組描述。(2) 帶串長的字符數(shù)組。(3) 動態(tài)數(shù)組。 以一組地址連續(xù)的分配而得的。單元存放串值字符序列，但空間是在程序執(zhí)行過程中動態(tài)不同的定義形式，算法中的處理也略有不同。2) 串的鏈式和線性表的鏈式表示結(jié)構相類似，也可采用鏈式結(jié)構串值。用鏈式結(jié)構串值時，每個結(jié)點包含字符域和指針域兩部分，字符域用于存放字符，指針域用于存放指向下一個結(jié)點的指針，因此，串可用單鏈表表示。串的鏈式結(jié)構的類型描述如下：用單鏈表存放串時，每個結(jié)點僅一個字符，如圖 3.2(a)所示。(a) 結(jié)點大小為 1 的鏈表(b) 結(jié)點大小為 3 的鏈表圖 3.2 串值的鏈式結(jié)構83typedef struct

17、 Nodechar str;struct Node *next;CNode,*LinkString;typedef structchar *ch;/*若是非空串,則按串長分配區(qū),否則 ch 為 NULL*/ length;/*串長度*/HString;#define MAXSTRLEN 255/*用戶可在 255 以內(nèi)定義最大串長*/ typedef structcharAXSTRLEN;/*數(shù)據(jù)區(qū)*/length;/*串長度*/SqString;#define MAXSTRLEN 255/*用戶可在 255 以內(nèi)定義最大串長*/typedef char SStringMAXSTRLEN;串的

18、鏈式密度可定義為結(jié)構的優(yōu)點是運算方便，缺點是密度低、空間利用率低。串的密度= 串值所占的存諸單元實際分配的 單元為了解決這個問題，提高空間的利用率，可以使每個結(jié)點存放多個字符，稱為塊鏈結(jié)構。當結(jié)點大小大于 1 時，因為串長不一定是結(jié)點大小的整數(shù)倍，所以鏈表的最后一個結(jié)點不一定全被串值占滿，此時通常補上非串值字符，如圖 3.2(b)所示，每個結(jié)點存放 3 個字符。串的塊鏈結(jié)構類型描述如下：3) 串的索引表示該方法是用串變量的名字作為關鍵字組織名字表(索引表)的，該表中的是串名和串值之間的對應關系。名字表中包含的項目可根據(jù)不同的需要來設置。如果串值是以鏈式結(jié)構存放的，則索引表中需要存放串名和串值鏈

19、表的起始地址；如果串值是以順序存儲方式存放的，則索引表中除了存放串值的起始地址外，還需要給出一個信息指示串值存放的末地址。其中，表示末地址信息的方法有以下兩種：一是給出串長，二是設置尾指針直接指向串值的末地址。下面給出這兩種索引表的類型定義，串值和索引表均是按順序方式存放的。(1) 帶長度的索引表。該索引表示的結(jié)構示意圖如圖 3.3 所示。圖 3.3 帶長度的索引表84#define MAXSIZE 255 typedef structchar nameMAXSIZE;/*存放串名*/length;/*存放串長*/char *startadr;/*存放串值的起始地址*/LSNode;#defi

20、ne NODESIZE 3/*可由用戶定義的塊大小*/ typedef struct nodechar chNODESIZE; struct node *next;SNode,*LinkStr;LinkStr head;(2) 帶末指針的索引表。該索引表示的結(jié)構示意圖如圖 3.4 所示。圖 3.4 帶尾指針的索引表3串基本運算的實現(xiàn)以串的順序結(jié)構為例，給出串的基本運算的實現(xiàn)算法。1) 空順序串的創(chuàng)建 Create_HStr(&S)2) 順序串的賦值 Assign_HStr(&S,&T)85void Assign_HStr(HString *S,HString *T)/*將順序串T 賦給順序串

21、S*/i;if(S-ch) free(S-ch);/*原來S 占據(jù)的空間*/ S-length=T-length;if(T-length)S-ch=(char *)malloc(T-length*sizeof(char); for(i=0;ilength;i+)S-chi=T-chi;else S-ch=NULL;void Create_HStr(HString *S) S-ch=NULL;S-length=0;typedef structchar *ch;/*若是非空串,則按串長分配區(qū),否則 ch 為 NULL*/ length;/*串長度*/HString;#define MAXSIZE

22、255 typedef structchar nameMAXSIZE;/*存放串名*/length;/*存放串長*/char *endadr;/*存放串值的末地址*/char *startadr;/*存放串值的起始地址*/ENode;3)順序串連接 Concat_HStr()4)順序串的長度 Length_HStr(&S)5)順序串的比較 Strcmp_HStr(&S,&T)6)順序串的Insert_HStr(&S,&T)void Insert_HStr(HString *S,HString *T)/*將串T到串S 的第i,j;個位置上,1S-length+1*/f(位置不合法!);if( S

23、-length+1) prS-length=S-length+T-length;for(i=S-length;i=;-i)/*為T 而騰出位置*/Si+T-length=Si;for(j=0;jlength;j+) S-chj+=T-chj;/*T*/7) 順序串的刪除 Delete_HStr(&S,len)86Strcmp_HStr(HString *S,HString *T)/*若 ST,則返回值0;若 S=T,則返回值=0;若 ST,則返回值0*/ i;for(i=0;ilength & ilength;i+) if(S-chi!=T-chi) break;return(S-chi-T-

24、chi);Length_HStr(HString *S)/*返回 S 的元素個數(shù),稱為串的長度*/ return S-length;void Concat_HStr(HString *S,HString *T)/*將串T 連接到串S 之后*/ HString temp;i,j;Assign_HStr(&temp,S);/*將 S 原來的內(nèi)容保存到 temp 中*/S-length=S-length+T-length; /*計算 S 和T 的長度作為S 的新長度*/ free(S-ch) ;/*原來S 占據(jù)的空間*/S-ch=(char *)malloc(S-length*sizeof(char

25、);/*重新為S 分配空間*/for(i=0;ichi=temp.chi;for(j=0;jlength;j+)/*將 T 的值賦值給 S*/S-chi+=T-chj; free(temp.ch);4簡單的模式匹配算法串的模式匹配即子串定位，是一種重要的串運算。設 S 和 T 是給定的兩個串，在主串S 中查找子串 T 的過程稱為模式匹配，如果在主串 S 中找到等于 T 的子串，則稱匹配成功，函數(shù)返回子串 T 在主串 S 中首次出現(xiàn)的模式串。位置，否則匹配失敗，返回 0。子串 T 也稱為簡單的模式匹配算法的基本 ：首先將 S1 與T1 進行比較，若不同，就將 S2 與 T1 進行比較，直到 S

26、的某一個字符 Si 和 T1 相同，再將它們之后的字符進行比較，若也相同，則如此繼續(xù)比較，當 S 的某一個字符 Si 與T 的字符 Tj 不相同時，則 S 返回到本趟開始字符的下一個字符，即 Si-j+2，T 返回到 T1，開始下一趟的比較。重復上述過程，若T 中的字符全部掃描一遍，則說明本趟匹配成功，本趟的起始位置是 i-j+1 或 i-T0；否則，匹配失敗。為了運算方便，設字符串的長度存放在 0 號單元，串值從 1 號單元存放，這樣字符序號與位置一致。算法源代碼如下：例如，設主串 S=ababcabcacbab，模式 T=abcac，則簡單的模式匹配過程如圖 3.5所示。87IndexBF

27、_Str(char *S,char *T)/*從串S 的第一個字符開始找首次與串T 相等的子串*/ i=1,j=1;while(i=S0 & jT0) return(i-T0); /*匹配成功,返回位置*/ else return 0;void Delete_HStr(HString *S,len)/*刪除串 S 中從第個字符開始的長度為 len 的子串 */ i;if(S-length|lenS-length-+1) prf(輸入不合法!);S-length=S-length-len;for(i=-1;ilength;i+) Si=Si+len;圖 3.5 簡單模式匹配的匹配過程3.2“稀疏

28、矩陣的轉(zhuǎn)置”案例3.2.1案例實現(xiàn)過程【案例說明】一個 mn 的矩陣 A，它的轉(zhuǎn)置矩陣 B 是一個 nm 的矩陣，且 aij=bji，0im，0jn。例如，在圖 3.6 中，矩陣 B 就是矩陣 A 的轉(zhuǎn)置矩陣。編寫一個程序，實現(xiàn)稀疏矩陣的轉(zhuǎn)置，要求稀疏矩陣采用三元組順序表來表示?！景咐康摹?1) 理解數(shù)組的順序結(jié)構及地址計算方式。88了解特殊矩陣和疏稀矩陣的概念，掌握特殊矩陣壓縮掌握稀疏矩陣的三元組表表示方法及有關算法。時的下標變換方法。(a) 稀疏矩陣A(b) 稀疏矩陣B圖 3.6 稀疏矩陣A 和B【技術要點】設有如下說明：TSMatrix a,b;其中，a 和b 分別表示矩陣 A 和 B

29、 的三元組順序表，如圖 3.7 所示。(a) a.data(b)b.data圖 3.7 稀疏矩陣 A 和 B 的三元組順序表在三元組表的形式下，求稀疏矩陣 A 的轉(zhuǎn)置矩陣 B，實際上就是由 a 求得b。由 a 的行數(shù)、列數(shù)、非零元素數(shù)可以直接得到 b 的列數(shù)、行數(shù)、非零元素數(shù)。由 a.data 得到 b.data，可采用兩種方法來實現(xiàn)。 按照矩陣A 的列序進行轉(zhuǎn)置。這種方法需要對 a.data 進行 n 趟掃描(n 為矩陣A 的列數(shù))才能完成。具體地說，對 a.data中的三元組依次掃描第 0 列、第 1 列、最后一列，并將掃描到的每個三元組的行、列交換后順序到 b.data 中即可。 按照

30、a.data 中三元組的次序進行轉(zhuǎn)置。要想掃描一趟 a.data 就能得到 b.data，必須每掃描到一個三元組就直接將它放到 b.data中相應的位置上。因此，需要知道 a.data 中的元素在 b.data 中的位置，這就要預先確89定矩陣 A 的每一列的第一個非零元素在 b.data 中相應的位置。為此，需要附設兩個數(shù)組num1.n和 cpot1.n，分別非零元素在 b.data 中的矩陣 A 中每一列的非零元素個數(shù)和矩陣 A 中每一列第 1 個位置。顯然，有如下的公式成立。例如，對圖 3.6 中的矩陣A，num 和 cpot 的值見表 3-1。表 3-1矩陣 A 的num 與 cpot

31、 值【代碼及分析】90#include #define MAXSIZE 50/*假設非零元個數(shù)的最大值為 50*/ #define MAXRC 10typedef structi,j; e;triple;/*非零元的結(jié)點類型*/typedef structtriple dataMAXSIZE+1; /*非零元三元組表,data0未用*/ mu,nu,tu;/*矩陣的行數(shù)、列數(shù)和非零元個數(shù)*/TSMatrix;/*轉(zhuǎn)置矩陣類型*/ TSMatrix tcreate(m,n,t)/*以三元組順序表的格式建立待轉(zhuǎn)置的稀疏矩陣 M*/TSMatrix M; k;M.mu=m;M.nu=n;M.tu=t

32、;prf(ninput %d data,M.tu); prf(ni j enn); for(k=1;k=M.tu;+k)scanf(%d%d%d,&M.datak.i,&M.datak.j,&M.datak.e); return(M);void prt(TSMatrix M)/*以二維數(shù)組的格式輸出轉(zhuǎn)置型矩陣 M*/ i,j,k=1;for(i=0;iM.mu;i+) prf(n); for(j=0;jM.tu) prf(%3d,0); while(k=M.tu)if(i=M.datak.i)&(j=M.datak.j)col01234numcol22101cpotcol13566cpot0=

33、1cpotcol=cpotcol-1+numcol-11coln該算法的時間主要耗費在 col 和p 的雙重循環(huán)語句上，所以時間復雜度為 O(nu*tu)。 該算法效率低的原因是需要反復掃描 a 的三元組表 a.data，尋找第 0 列、第 1 列、最末一列的三元組。若能直接確定 a.data 中每一個三元組在 b.data 中的位置，則對 a.data三元組表掃描一趟即可。這是可以做到的，因為 a 中第 0 列的第一個非零元素一定在b.data1中，如果還知道 a 中第 0 列的非零元素的個數(shù)，那么 a 中第 1 列的第一個非零元素在 b.data 中的位置便等于第 0 列的第一個非零元素在

34、 b.data 中的位置加上第 0 列的非零元素的個數(shù)，依次類推。因為 a.data 中三元組的存放順序是以行優(yōu)先的，對同一行來說，91prf(%3d,M.datak.e); k+ ;break ;elseprf(%3d,0); break;prf(n);TSMatrix transe(TSMatrix a)/*采用三元組表表示,求稀疏矩陣a 的轉(zhuǎn)置矩陣 b*/ TSMatrix b;col,p,q;b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;/*矩陣的行、列、非零元素個數(shù)*/ if(b.tu) /*有非零元素則轉(zhuǎn)換*/q=1;for(col=0;cola.nu;+col)/*

35、按a 的列序順序掃描*/ for(p=1;p=a.tu;+p)if(a.datap.j=col)b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.e=a.datap.e;+q;return(b);main()m,n,t; TSMatrix E,F;prf(ninput m,n,t:);scanf(%d%d%d,&m,&n,&t); E=tcreate(m,n,t);prt(E); F=transe(E); prt(F);必定先遇到列號小的元素，這樣只需掃描一趟 a.data 即可。改進算法源代碼：92#include #define MAXSIZE

36、 50/*假設非零元個數(shù)的最大值為 50*/ #define MAXRC 10typedef structi,j; e;triple;/*非零元的結(jié)點類型*/typedef structtriple dataMAXSIZE+1;/*非零元三元組表,data0未用*/ mu,nu,tu;/*矩陣的行數(shù)、列數(shù)和非零元個數(shù)*/TSMatrix;/*轉(zhuǎn)置矩陣類型*/ TSMatrix tcreate(m,n,t)/*以三元組順序表的格式建立待轉(zhuǎn)置的稀疏矩陣 M*/TSMatrix M; k;M.mu=m;M.nu=n;M.tu=t;prf(ninput %d data,M.tu); prf(ni j

37、enn); for(k=1;k=M.tu;+k)scanf(%d%d%d,&M.datak.i,&M.datak.j,&M.datak.e); return(M);void prt(TSMatrix M)/*以二維數(shù)組的格式輸出轉(zhuǎn)置型矩陣 M*/ i,j,k=1;for(i=0;iM.mu;i+) prf(n); for(j=0;jM.tu) prf(%3d,0); while(k=M.tu)if(i=M.datak.i)&(j=M.datak.j) prf(%3d,M.datak.e);k+ ;break ;elseprf(%3d,0); break;prf(n);TSMatrix fast

38、trans(TSMatrix a)/*采用三元組順序表表示，將稀疏矩陣 A 快速轉(zhuǎn)置為矩陣 B*/ TSMatrix b;col,p,q,t;該算法僅比前一個算法多了兩個輔助數(shù)組，從時間上看，算法中有 4 個并列的單重循環(huán)，循環(huán)次數(shù)分別為 nu 和 tu，因而總的時間復雜度為 O(nu+tu)。3.2.2應用擴展設稀疏矩陣 A 和 B 具有相同大小，即 mn。編寫一個程序，計算 CA+B。要求采用三元組表示。程序應完成如下功能。(1)(2)(3)程序中能輸入 A、B 兩個三元組的數(shù)據(jù)。把矩陣相加結(jié)果送到 C 中。輸出 C 中的結(jié)果。算法如下。依次掃描 A 和 B 的行號和列號，若 A 的當前項

39、的行號等于 B 的當前項的行號，則比較其列號，將較小列的項存入 C 中，如果列號也相等，則將對應的元素值相加后存入 C 中；93numMAX; cpotMAX;b.mu=a.nu;b.nu=a.mu;b.tu=a.tu; if(b.tu)for(col=0;cola.nu;+col) numcol=0; for(t=1;t=a.tu;+t) +numa.da.j;/*求a 中每一列含有的非零元個數(shù)*/cpot1=1;/*求第 col 列中第一個非零元在 b.data 中的序號*/for(col=1;cola.nu;+col) cpotcol=cpotcol-1+numcol-1; for(p=

40、1;p=a.tu;+p)/*掃描三元組表*/col=a.datap.j;/*當前三元組的列號*/ q=cpotcol;/*當前三元組在 B.data 中的位置*/ b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.e=a.datap.e;+cpotcol;return(b);main()m,n,t; TSMatrix E,G;prf(ninput m,n,t:);scanf(%d%d%d,&m,&n,&t); E=tcreate(m,n,t);prt(E); G=fasttrans(E); prt(G);若 A 的當前項的行號小于 B 的當前項的行

41、號，則將 A 的項存入 C 中；若 A 的當前項的行號大于 B 的當前項的行號，則將 B 的項存入 C 中。3.2.3相關知識及注意事項11)數(shù)組數(shù)組的概念數(shù)組是一種常用的數(shù)據(jù)結(jié)構，幾乎所有的高級語言都提供數(shù)組類型。高級語言中的數(shù)組在計算機內(nèi)存中是用一批連續(xù)的單元來表示的，稱為數(shù)組的順序結(jié)構，實際使用中還可以根據(jù)需要選擇數(shù)組的其他方式以及基本運算的實現(xiàn)。方式。在此著重二維數(shù)組特別是稀疏矩陣的數(shù)組作為一種數(shù)據(jù)結(jié)構其特點是結(jié)構中的元素本身可以是具有某種結(jié)構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維

42、數(shù)組”的一維數(shù)組，依次類推。圖示是一個 m 行 n 列的二維數(shù)組。圖 3.8 m 行 n 列的二維數(shù)組通常在各種高級語言中，數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種運算。(1)(2)2)運算：給定一組下標，對應的數(shù)據(jù)元素。修改運算：給定一組下標，修改與其相對應的數(shù)據(jù)元素。數(shù)組的順序表示和刪除運算，也就是說，數(shù)組一旦建立，結(jié)構中的元素個數(shù)由于對數(shù)組一般不作和元素間的關系就不再發(fā)生變化。因此，一般采用順序的方法來表示數(shù)組。由于單元是一維的結(jié)構，而數(shù)組是一個的結(jié)構，則用一組地址連續(xù)的存儲單元存放數(shù)組的數(shù)據(jù)元素，就有個次序約定問題。通常，有兩種順序方式：一種是以行序為主序

43、的方式，又稱行優(yōu)先；一種是以列序為主序的方式，又稱列優(yōu)先。例如，一個 23 二維數(shù)組，邏輯結(jié)構可以用圖 3.9(a)表示。行優(yōu)先表示如圖 3.9(b)所示，順序為：a00，a01，a02，a10 ，a11，a12。列優(yōu)先順序為：a00，a10，a01，a11，a02，a12，它的表示如圖 3.9(c)所示。對于數(shù)組，一旦規(guī)定了它的維數(shù)和各維的長度，便可為它分配空間。反之，只要結(jié)構為例加以說明。給出一組下標便可求得相應數(shù)組元素的位置。下面僅以行優(yōu)先94(a)邏輯表示(b) 以行序為主序(c) 以列序為主序圖 3.9 二維數(shù)組的邏輯與表示例如，二維數(shù)組 Amn 以行序為主序在內(nèi)存中，設數(shù)組的基址為

44、 LOC(a00)，每個數(shù)組元素占據(jù) d 個單元，那么 aij 的地址函數(shù)為LOC(aij)=LOC(a00)+(i*n+j)*d元素 aij 的地址應是數(shù)組的址加上排在元素 aij 前面的元素所占用的單元數(shù)。因為數(shù)組元素 aij 的前面有 i-1 行，每一行的元素個數(shù)為 n，在第 i 行中它的前面還有 j-1 個數(shù)組元素，故元素 aij 的前面一共有(i-1)*n + j-1 個元素。在不同的程序設計語言中，數(shù)組每一維的下界定義不盡相同，若數(shù)組每一維的下界定義為 1，則LOC(aij) = LOC(a11) +(i-1)*n + j -1) * d推廣到一般的二維數(shù)組 Ac1.d1c2.d2

45、，則 aij 的地址函數(shù)為LOC(aij)=LOC(a c1 c2)+(i- c1) *(d2 - c2 + 1)+(j- c2) )*d 2特殊矩陣的壓縮矩陣在科學與工程計算中有廣泛的應用。在用高級語言編程時，通常用二維數(shù)組來表示矩陣，這樣利用上述地址計算公式可以快速矩陣中的每個元素。然而，在實際應用中會遇到一些特殊矩陣，所謂特殊矩陣是指矩陣中值相同的元素或者零元素的分布有一定規(guī)律。例如，對稱矩陣、三角矩陣和三對角矩陣都是特殊矩陣。1) 對稱矩陣在一個 n 階方陣 A 中，若元素滿足下述性質(zhì)aij=aji0i，jn-1稱 A 為對稱矩陣。例如，圖 3.10 所示是一個 5 階對稱矩陣。圖 3

46、.10 5 階對稱方陣95在對稱矩陣中，元素關于主對角線對稱相等，故只要矩陣上三角或下三角中的元素即可。每一對相等的對稱元素共個空間，這樣能節(jié)約近一半的空間。不失一般性，可以行序為主序主對角線(包括對角線)以下的元素。例如，在 n 階對稱矩陣 A 的下三角矩陣中，第 i 行(0in)恰有 i+1 個元素，元素總數(shù)為 n*(n+1)/2。假設以一維數(shù)組 san*(n+1)/2作為n 階對稱矩陣 A 的圖如圖 3.11 所示。結(jié)構，示意圖 3.11 對稱矩陣的壓縮為了便于關系。對稱矩陣 A 中的元素，必須在 sak和矩陣元素 aij 之間找到一個對應的在下三角矩陣中，ij 且 0i,jn，元素 a

47、ij 前面有 i 行，共有 i*(i+1)/2 個元素，而 aij又是它所在行中的第 j+1 個，所以在上面的壓縮因此，sak和矩陣元素 aij 之間的關系為k=i*(i+1)/2+j表示中，aij 是第 i*(i+1)/2+(j+1)個元素。0kn*(n+1)/2若 ij，則 aij 是上三角中的元素，因為 aij=aji ，這樣，上三角中的元素 aij 時，訪問和它對應的下三角中的 aji 即可。因此，將上式中的行列下標交換就是上三角中的元素在sa 中的對應關系k=j*(j+1)/2+i0kn*(n+1)/2綜上所述，對于對稱矩陣中的任意元素 aij，若令 i=max(i,j)，j=min

48、(i,j)，則將上面兩個式子綜合起來得到k=i*(i+1)/2+j2) 三角矩陣三角矩陣通常指的是下三角矩陣和上三角矩陣。若 n 階方陣上三角(不包括對角線)中的元素均為常數(shù) c，則稱該矩陣為下三角矩陣。同理，若 n 階方陣下三角(不包括對角線)中的元素均為常數(shù) c，則稱該矩陣為上三角矩陣，如圖 3.12 所示。(a) 下三角矩陣(b) 上三角矩陣圖 3.12 三角矩陣上三角矩陣或下三角矩陣的壓縮，除了其上(下)三角中(包括對角線)的元外，還需要一個空間來常數(shù) c。96與對稱矩陣類似，若以行序為主序，下三角矩陣元素 aij 和 sak之間的關系為k=i*(i+1)/2+j0kn*(n+1)/2

49、 ，ij， 0i,jn-1若以列序為主序，上三角矩陣元素 ai j 和 sak之間的關系為k=j*(j+1)/2+i3) 對角矩陣0k1 時，元素 aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。例如，用一維數(shù)組 sa3*n-2來存放三對角矩陣 A的所有數(shù)據(jù)元素，若以行序為主序，sak 和矩陣元素 aij 之間的關系為k=(3*i-1)+(j-i+2)-1=2*i+j0i,jn-1若以列序為主序，sak 和矩陣元素 aij 之間的關系為k=(3*j-1)+(i-j+2)-1=2*j+i3稀疏矩陣的三元組0i,jn-1設 mn

50、 矩陣中有 t 個非零元素且 tn) s=m;else s=n;/*確定行列、表頭結(jié)點的個數(shù)*/ p=(OLink)malloc(sizeof(OLNode);p-row=m;p-col=n;hm=p;cp0=p;/*cp1.s為一組指示行表頭結(jié)點的指針*/ for(i=1;irow=0;p-col=0;cpi=p;p-right=p;p-down=p; cpi-1-uval.next=p;cps-uval.next=hm; for(i=1;irow=r;p-col=c;p-uval.val=v; q=cpr;/*尋找行表中 位置*/while(q-right !=cpr)&(q-right-

51、colright; p-right=q-right;q-right=p; /*/q=cpc;/*尋找列表中位置*/while(q-down!=cpc)&(q-down-rowdown; p-down=q-down;q-down=p;/*完成*/struct Lnode *down,*right; unionstruct Lnode *next; ElemType val;uval;OLNode,*OLink;其中，LS 是廣義表的名稱，n 是它的長度。每個 ai(1in)是 LS 的成員，它可以是單個元素，也可以是一個廣義表，分別稱為廣義表 LS 的原子和子表。當廣義表 LS 非空時，稱第一個

52、元素 a1 為 LS 的表頭(Head)，稱其余元素組成的表(a2，ai，an)為 LS 的表尾(Tail)。任何一個非空廣義表其表頭可能是原子，也可能是廣義表，而其表尾必定為廣義表。顯然，廣義表的定義是遞歸的。為了書寫清楚起見，通常用大寫字母表示廣義表，用小寫字母表示單個數(shù)據(jù)元素，廣義表用括號括起來，括號內(nèi)的數(shù)據(jù)元素用逗號分隔開。例如，分析下列廣義表的長度、表頭和表尾。A=()B=(e)C=(a,(b,c,d) D=(A,B,C)E=(a,E)F=()其中，表 A 是一個空表，長度為 0；表 B 只有一個原子 e，B 的長度為 1，B 的表頭為 e，表尾為空表()；表 C 的長度為 2，兩個

53、元素分別為原子 a 和子表(b,c,d)，表頭為 a，表尾為(b,c,d) ；表 D 的長度為 3 ， 3 個元素都是子表，將子表的值代入后，則有 D=(),(e),(a,(b,c,d)，其表頭為 A，表尾為(B,C)；表 E 是一個遞歸的表，它的長度為 2，相當于一個無限的列表，其表頭表尾分別為 a 和(E)；表 F 的長度為 1，只有一個元素，為空表()，其表頭和為()。注意：列表()和()不同。前者為空表，長度 n=0；后者長度 n=1，可分解得到其表頭、表尾均為空表()。從上述廣義表的定義可以得到廣義表的下列重要性質(zhì)。廣義表是一種多層次的數(shù)據(jù)結(jié)構。廣義表的元素可以是單元素，也可以是子表

54、，而子表的元素還可以是子表。廣義表可以是遞歸的表。廣義表的定義并沒有限制元素的遞歸，即廣義表也可以是其自身的子表。例如，表 E 就是一個遞歸的表。廣義表可以為其他表所共享。例如，表 A、表 B、表 C 是表 D 的共享子表。在 D中可以不必列出子表的值，而用子表的名稱來。5廣義表的結(jié)構由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構，因此難以用順序結(jié)構來表示。而鏈式儲結(jié)構來結(jié)構分配較為靈活，易于解決廣義表的共享與遞歸問題，所以通常都采用鏈式存廣義表。在這種表示方式下，每個數(shù)據(jù)元素可用一個結(jié)點表示。若廣義表不空，則可分解成表頭和表尾；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。頭尾表示法就是根據(jù)這

55、一性質(zhì)設計而成的一種方法。101因為廣義表中的數(shù)據(jù)元素既可能是列表也可能是單元素，所以相應地在頭尾表示法中結(jié)點的結(jié)構形式有兩種：一種是表結(jié)點，用以表示列表；另一種是元素結(jié)點，用以表示單元素。在表結(jié)點中應該包括一個指向表頭的指針和指向表尾的指針；而在元素結(jié)點中應該包括所表示單元素的元素值。為了區(qū)分這兩類結(jié)點，在結(jié)點中還要設置一個標志域，如果標志為 1，則表示該結(jié)點為表結(jié)點；如果標志為 0，則表示該結(jié)點為元素結(jié)點。頭尾表示法的結(jié)點類型描述如下：頭尾表示法結(jié)點的結(jié)構如下：表結(jié)點元素結(jié)點例如，若采用頭尾表示法的方式，廣義表 D 的結(jié)構如圖 3.17 所示。圖 3.17 廣義表的結(jié)構采用頭尾表示法容易分

56、清廣義表中單元素或子表所在的層次。例如，在廣義表 D 中，單元素 a 和 e 在同一層次上，而單元素 b、c、d 在同一層次上且比 a 和 e 低一層，子表 B和 C 在同一層次上。另外，最的表結(jié)點的個數(shù)即為廣義表的長度。例如，在廣義表 D的最有 3 個表結(jié)點，其長度為 3。6求廣義表的深度廣義表的深度定義為廣義表中所有元素均為原子時括弧的最多重數(shù)，是廣義表的一種量度。設非空廣義表為LS=(a1,a2,an)其中 ai 為原子或子表，則求 LS 的深度可分解為 n 個子問題，每個子問題為求 ai 的深102tag=0cate.atomtag=1cate.ptr hpcate.ptr. tpty

57、pedef enumATOM,LIST ElemTag;/*ATOM=0 表示原子,LIST=1 表示子表*/ typedefElemType;typedef struct GLnodeElemTag tag;/*公共部分,用于區(qū)分原子結(jié)點和表結(jié)點*/ union/*原子結(jié)點和表結(jié)點的聯(lián)合部分*/ElemType atom;/*atom 是原子結(jié)點的值域*/ structstruct GLnode *hp,*tp;ptr;/*ptr 是表結(jié)點的指針域,ptr.hp 和 ptr.tp 分別指向表頭和表尾*/cate;GLNode,*GList;/*廣義表類型*/度，若 ai 是原子，則其深度為零

58、；若 ai 是廣義表，則和上述一樣處理。而 LS 的深度為所有 ai 的深度中的最大值加 1?？毡硪彩菑V義表，由定義可知空表的深度為 1。由此可見，求廣義表的深度的遞歸算法有兩個終結(jié)狀態(tài)：空表和原子。只要求得 ai 的深度，廣義表的深度就容易求得。顯然，它應比所有子表深度的最大值多 1。算法如下。若 LS 為空表時，返回 1；若 LS 指向原子時，返回 0。當 LS 指向非空表時，p=LS，操作如下。首先求得表頭 p-ptr.hp 的深度depth。若 depth 大于 max，則 max=depth。指針p 指向當前列表表尾。算法源代碼如下：本 章 小 結(jié)本章簡要介紹了串的有關概念、的相關知

59、識。通過“文學研究助手”案例，介紹了結(jié)構以及串的基本運算在順序結(jié)構上的實現(xiàn)算法；通過“稀疏矩陣的轉(zhuǎn)置”案例，介紹了矩陣的壓縮方法，對于稀疏矩陣，通常采用三元組表或鏈表存放元素，介紹了廣義表的概念、基本運算和結(jié)構。習題3一、選擇題1下面關的敘述中，哪一個是不正確的？()A) 串是字符的有限序列B) 空串是由空格的串C) 模式匹配是串的一種重要運算103GListDepth(GList L)/*采用頭尾鏈表結(jié)構,求廣義表L 的深度*/ GList p;depth,max;if(!L)return 1;/*空表深度為 1*/ if(L-tag=ATOM) return 0; /*原子深度為 0*/

60、for(max=0,p=L;p;p=p-cate.ptr.tp)/*求以 p-cate.ptr.hp 為頭指針的子表深度*/depth=GListDepth(p-cate.ptr.hp); if(depthmax) max=depth;return max+1;/*非空表的深度是各元素的深度的最大值加 1*/D) 串既可以采用順序，也可以采用鏈式2有兩個串 p 和q，其中 q 是p 的子串，求 q 在p 中首次出現(xiàn)的位置的算法稱為()。A) 求子串B) 連接C) 模式匹配)。C) 36D) 求串長3若串 s=software，其子串的個數(shù)是(A) 84串的長度是指(B) 37)。D) 9串中所