數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版4

1、第4章 串和數(shù)組本章主要介紹下列內(nèi)容： 串的定義、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算 數(shù)組的定義、基本運(yùn)算和存儲(chǔ)結(jié)構(gòu) 特殊矩陣的壓縮存儲(chǔ)退出14.1 串4.2 數(shù)組24.1 串 4.1.1 串的定義和基本運(yùn)算 串是字符串的簡(jiǎn)稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個(gè)有窮字符序列。3 串一般記作： s= “a1a2.an” (n0) 其中，s是串的名稱，用雙引號(hào)（“”）括起來(lái)的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長(zhǎng)度。當(dāng)n=0時(shí)，串中沒(méi)有任何字符，其串的長(zhǎng)度為0，通常被稱為空串。 s

2、1= “” s2= “ ” s1中沒(méi)有字符，是一個(gè)空串；而s2中有兩個(gè)空格字符，它的長(zhǎng)度等于2，它是由空格字符組成的串，一般稱此為空格串。 概念： 子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。4 例如，有下列四個(gè)串a(chǎn)，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出現(xiàn)的第一個(gè)字符的位置。 兩個(gè)串相等：兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)的字符也都相同。 例如，有下列四個(gè)串a(chǎn)，b，c，d： a= “program” b= “Progr

3、am” c= “pro” d= “program ”5 串的基本操作：（1） 創(chuàng)建串 StringAssign (s,string_constant)（2）判斷串是否為空 StringEmpty(s) （3）計(jì)算串長(zhǎng)度 Length(s) （4）串連接 Concat(s1,s2) （5）求子串 SubStr(s1,s2start,len)（6）串的定位 Index(s1,s2)6 例如1：將s2串插入到串s1的第i個(gè)字符后面。 SubStr(s3,s1,1,i); SubStr(s4,s1,i+1,Length(s1)-i); Concat(s3,s2); Concat(s3,s4); Str

4、ingAssign (s1,s3); 例如2：刪除串s中第i個(gè)字符開(kāi)始的連續(xù)j個(gè)字符。 SubStr(s1,s,1,i-1); SubStr(s2,s,i+j,Length(s)-i-j+1); Concat(s1,s2); StringAssign(s,s1); 7 4.1.2 串的存儲(chǔ)結(jié)構(gòu) 1. 順序存儲(chǔ)結(jié)構(gòu) 串的順序存儲(chǔ)結(jié)構(gòu)與線性表的順序存儲(chǔ)類似，用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)串中的字符序列。在C語(yǔ)言中，有兩種實(shí)現(xiàn)方式： 第一種是事先定義字符串的最大長(zhǎng)度，字符串存儲(chǔ)在一個(gè)定長(zhǎng)的存儲(chǔ)區(qū)中。類型定義如下所示： #define MAX_STRING 255 /0號(hào)單元存放串的長(zhǎng)度，字符從1號(hào)單元

5、開(kāi)始存放 type unsigned char StringMAX_STRING; 8 第二種是在程序執(zhí)行過(guò)程中，利用標(biāo)準(zhǔn)函數(shù)malloc和free動(dòng)態(tài)地分配或釋放存儲(chǔ)字符串的存儲(chǔ)單元，并以一個(gè)特殊的字符作為字符串的結(jié)束標(biāo)志，它的好處在于：可以根據(jù)具體情況，靈活地申請(qǐng)適當(dāng)數(shù)目的存儲(chǔ)空間，從而提高存儲(chǔ)資源的利用率。類型定義如下所示：typedef structchar *str; int length;STRING; 不同的定義形式，算法中的處理也略有不同。下面我們將給出在第二種順序存儲(chǔ)方式下串的幾個(gè)基本操作的算法。9（1） 串的賦值 int StringAssign(STRING*s,char

6、 *string_constant) if (s-str) free(s-str); /若s已經(jīng)存在，將它占據(jù)的空間釋放掉 for (len=0,ch=string_constant;ch;len+,ch+); /求string_constant串的長(zhǎng)度 if (!len) s-str=(char*)malloc(sizeof(char);s-str0=0; s-length=0; /空串10 else s-str=(char*)malloc(len+1)*sizeof(char); /分配空間 if (!s-str) return ERROR; s-str0.len=string_const

7、ant0.len; /對(duì)應(yīng)的字符賦值 s-length=len; /賦予字符串長(zhǎng)度 return OK;11（2）判斷串是否為空 int StringEmpty(STRING s) if (!s.length) return TRUE; else return FALSE;（3）求串的長(zhǎng)度 int Length(STRING s) return s.length;12（4）串連接 int Concat(STRING *s1,STRING s2) STRING s; StringAssign(&s,s1-str); /將s1原來(lái)的內(nèi)容保留在s中 len=Length(s1)+Length(s2)

8、; /計(jì)算s1和s2的長(zhǎng)度之和 free(s1-str); /釋放s1原來(lái)占據(jù)的空間 s1-str=(char*)malloc(len+1)*sizeof(char); /重新為s1分配空間13 if (!s1) return ERROR; else /連接兩個(gè)串的內(nèi)容 s1-str0.Length(s)-1=s.str0.Length(s)-1); s1-strLength(s).len+1=s2.str0.Length(s2); s1-length=len; free(s-str); /釋放為臨時(shí)串s分配的空間 return OK; 14（5）求子串 int SubStr(STRING *

9、s1,STRING s2,int start,int len) len2=Length(s2); /計(jì)算s2的長(zhǎng)度 if (startlen2|len2len2-start+1) /判斷start和len的合理性 s1-str=(char*)malloc(sizoef(char);s1-str0=0;s1-length=0;return ERROR; s1-str=(char*)malloc(len+1)*sizeof(char); if (!s1.str) return ERROR; s1-str0.len-1=s2.strstart-1.start+len -2; s1-strlen=0;

10、 s1-length=len; return OK;15（6）串的定位int Index(STRING s1,STRING s2) len1=Length(s1); len2=Length(s2); /計(jì)算s1和s2的長(zhǎng)度 i=0; j=0; /設(shè)置兩個(gè)掃描指針 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /對(duì)應(yīng)字符不相等時(shí)，重新比較 if (j=len2) return i-len2+1; else return 0;16 2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 由于串結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素為一個(gè)字符，所以最直接的鏈?zhǔn)酱鎯?chǔ)結(jié)

11、構(gòu)是每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域存放一個(gè)字符。舉例：s t r i n g S圖 4-117 優(yōu)點(diǎn)是操作方便；不足之處是存儲(chǔ)密度較低。所謂存儲(chǔ)密度為： 若要將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，就可以緩解這個(gè)問(wèn)題。舉例：S s t r i n g # # # # 圖 4-218 由于串中的字符個(gè)數(shù)不一定是每個(gè)結(jié)點(diǎn)存放字符個(gè)數(shù)的整倍數(shù)，所以，需要在最后一個(gè)結(jié)點(diǎn)的空缺位置上填充特殊的字符。 這種存儲(chǔ)形式優(yōu)點(diǎn)是存儲(chǔ)密度高于結(jié)點(diǎn)大小為1 的存儲(chǔ)形式；不足之處是做插入、刪除字符的操作時(shí)，可能會(huì)引起結(jié)點(diǎn)之間字符的移動(dòng)，算法實(shí)現(xiàn)起來(lái)比較復(fù)雜。194.2 數(shù)組 4.2.1 數(shù)組的定義和基本運(yùn)算 數(shù)組的特點(diǎn)是每個(gè)數(shù)據(jù)元素可以又是一個(gè)

12、線性表結(jié)構(gòu)。因此，數(shù)組結(jié)構(gòu)可以簡(jiǎn)單地定義為：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡(jiǎn)單元素，則稱為一維數(shù)組，即為向量；若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組；依次類推，若二維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組。 結(jié)論：線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。舉例：20圖 4-321 其中，A是數(shù)組結(jié)構(gòu)的名稱，整個(gè)數(shù)組元素可以看成是由m個(gè)行向量和n個(gè)列向量組成，其元素總數(shù)為mn。在C語(yǔ)言中，二維數(shù)組中的數(shù)據(jù)元素可以表示成a表達(dá)式1表達(dá)式2，表達(dá)式1和表達(dá)式2被稱為下標(biāo)表達(dá)式，比如，aij。 數(shù)組結(jié)構(gòu)在創(chuàng)建時(shí)就確定了組成該結(jié)構(gòu)的行向量數(shù)目和列向量數(shù)目，

13、因此，在數(shù)組結(jié)構(gòu)中不存在插入、刪除元素的操作。 二維數(shù)組結(jié)構(gòu)的基本操作： （1） 給定一組下標(biāo)，修改該位置元素的內(nèi)容 Assign(A,item,index1,index2) （2）給定一組下標(biāo)，返回該位置的元素內(nèi)容 Value(A,item,index1,index2)22 4.2.2 數(shù)組的存儲(chǔ)結(jié)構(gòu) 從理論上講，數(shù)組結(jié)構(gòu)也可以使用兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。然而，由于數(shù)組結(jié)構(gòu)沒(méi)有插入、刪除元素的操作，所以使用順序存儲(chǔ)結(jié)構(gòu)更為適宜。換句話說(shuō)，一般的數(shù)組結(jié)構(gòu)不使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 組成數(shù)組結(jié)構(gòu)的元素可以是多維的，但存儲(chǔ)數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲(chǔ)數(shù)組結(jié)構(gòu)之前，需要

14、解決將多維關(guān)系映射到一維關(guān)系的問(wèn)題。舉例：23圖 4-424 第0行 第1行 第m-1行圖 4-5 第0列 第1列 第m-1列圖 4-625LOC(i,j)=LOC(0,0)+(n*i+j)*L數(shù)組結(jié)構(gòu)的定義：#define MAX_ROW_INDEX 10#define MAX_COL_INDEX 10typedef struct EnterType itemMAX_ROW_INDEXMAX_COL_INDEX ; ARRAY;26基本操作算法舉例：（1）給數(shù)組元素賦值void Assign(ARRAY *A,EnterType item,int index1,int index2) if

15、(index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) exit(ERROR); else A-itemindex1index2=item;27（2）返回給定位置的元素內(nèi)容 int Value(ARRAY A,EntryType *item,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) return FALSE; else *item= A.itemindex1index2; return OK; 28 3矩陣的壓縮存儲(chǔ) 矩陣是在很多科學(xué)與工程計(jì)算中遇到的數(shù)學(xué)模型。

16、在數(shù)學(xué)上，矩陣是這樣定義的：它是一個(gè)由sn個(gè)元素排成的s行（橫向）n列（縱向）的表。下面就是一個(gè)矩陣：29圖4-7 sn的矩陣它是一個(gè)sn的矩陣。30 1. 特殊矩陣 所謂特殊矩陣就是元素值的排列具有一定規(guī)律的矩陣。常見(jiàn)的這類矩陣有：對(duì)稱矩陣、下（上）三角矩陣、對(duì)角線矩陣等等。 對(duì)稱矩陣的特點(diǎn)是aij=aji，比如，下面就是一個(gè)對(duì)稱矩陣：31圖 4-832 下（上）三角矩陣的特點(diǎn)是以主對(duì)角線為界的上（下）半部分是一個(gè)固定的值，下（上）半部分的元素值沒(méi)有任何規(guī)律。比如，下面是一個(gè)下三角矩陣：圖 4-933 對(duì)角矩陣的特點(diǎn)是所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。比如，下面就是一個(gè)3階

17、對(duì)角矩陣：圖 4-1034 對(duì)于這些特殊矩陣，應(yīng)該充分利用元素值的分布規(guī)律，將其進(jìn)行壓縮存儲(chǔ)。選擇壓縮存儲(chǔ)的方法應(yīng)遵循兩條原則：一是盡可能地壓縮數(shù)據(jù)量，二是壓縮后仍然可以比較容易地進(jìn)行各項(xiàng)基本操作。 三種特殊矩陣的壓縮方法：。 （1）對(duì)稱矩陣 對(duì)稱矩陣的特點(diǎn)是aij=aji。一個(gè)nn的方陣，共有n2個(gè)元素，而實(shí)際上在對(duì)稱矩陣中有n(n-1)/2個(gè)元素可以通過(guò)其他元素獲得。35 壓縮的方法是首先將二維關(guān)系映射成一維關(guān)系，并只存儲(chǔ)其中必要的n(n+1)/2個(gè)（主對(duì)角線和下三角）元素內(nèi)容，這些元素的存儲(chǔ)順序以行為主序。舉例： 假設(shè)定義一個(gè)數(shù)組型變量：int A10;圖 4-1136 k是對(duì)稱矩陣位于

18、（i，j）位置的元素在一維數(shù)組中的存放位置。37操作算法的實(shí)現(xiàn)：int Value(int A,EntryType *item,int i,int j) if (iMAX_ROW_INDEX| jMAX_COL_INDEX) return FALSE; else if (i=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; *item=Ak; return TRUE; 38 （2）下（上）三角矩陣 下三角矩陣的壓縮存儲(chǔ)與上面講述的對(duì)稱矩陣的壓縮存儲(chǔ)一樣，只是將上三角部分的常量值存儲(chǔ)在0單元，下三角和主對(duì)角上的元素從1號(hào)單元開(kāi)始存放。 舉例：圖 4-12 對(duì)于任

19、意的（i，j），在一維數(shù)組中的存放位置可利用下列公式求得：39操作算法的實(shí)現(xiàn)：int Value(int A,EntryType *item,int i,int j) if (iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; else if (i=j) k=i*(i-1)/2+j; else k=0; *item=Ak; return TRUE; 40 （3）對(duì)角矩陣 我們以三階對(duì)角矩陣為例討論一下它的壓縮存儲(chǔ)方法。對(duì)于對(duì)角矩陣，壓縮存儲(chǔ)的主要思路是只存儲(chǔ)非零元素。這些非零元素按以行為主序的順序，從下標(biāo)為1 的位置開(kāi)始依次存放在一維數(shù)組中，而0位置存放數(shù)

20、值0。圖 4-1341 下面我們討論一下對(duì)于任意給定的（i，j），求得在一維數(shù)組中存儲(chǔ)位置k的方法。42操作算法的實(shí)現(xiàn)：int Value(int A ,EntryType *item,int i,int j) if (iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; else if (j=(i-1)&j=(i+1) k=3*(i-1)+j-i+1; else k=0; *item=Ak; return TRUE; 43 2. 稀疏矩陣的壓縮存儲(chǔ) 若一個(gè)mn的矩陣含有t個(gè)非零元素，且t遠(yuǎn)遠(yuǎn)小于m*n，則我們將這個(gè)矩陣稱為稀疏矩陣。舉例：圖 4-1444 稀疏矩陣的壓縮存儲(chǔ)方法三元組表示法。 矩陣中的每個(gè)元素都是由行序號(hào)和列序號(hào)唯一確定的。因此，我們需要用三項(xiàng)內(nèi)容表示稀疏矩陣中的每個(gè)非零元素，即形式為：(i,j,valu