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

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

2、符，是一個(gè)空串；而s2中有兩個(gè)空格字符，它的長(zhǎng)度等于2，它是由空格字符組成的串，一般稱(chēng)此為空格串。 概念： 子串、主串：串中任意連續(xù)的字符組成的子序列被稱(chēng)為該串的子串。包含子串的串又被稱(chēng)為該子串的主串。 例如，有下列四個(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= “Program” c= “pro” d= “prog

3、ram ” 串的基本操作：（1） 創(chuàng)建串 StrAssign (s1,s2)（2）判斷串是否為空 StrEmpty(s) （3）計(jì)算串長(zhǎng)度StrLength(s) （4）串連接 StrConcat(s1,s2) （5）求子串 SubStr(s,i,len)（6）串的定位 StrIndex(s1,t) 4.1.2 串的存儲(chǔ)結(jié)構(gòu) 1. 順序存儲(chǔ)結(jié)構(gòu) 串的順序存儲(chǔ)結(jié)構(gòu)與線(xiàn)性表的順序存儲(chǔ)類(lèi)似，用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)串中的字符序列。在C語(yǔ)言中，有兩種實(shí)現(xiàn)方式： 第一種是事先定義字符串的最大長(zhǎng)度，字符串存儲(chǔ)在一個(gè)定長(zhǎng)的存儲(chǔ)區(qū)中。類(lèi)型定義如下所示： #define MAXSIZE 255 char s

4、MAXSIZE; 第二種是在程序執(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ǔ)資源的利用率。類(lèi)型定義如下所示：typedef struct char dataMAXSIZE;int curlen; SeqString;定義一個(gè)串變量：SeqString s;不同的定義形式，算法中的處理也略有不同。下面我們將給出在第一種順序存儲(chǔ)方式下串的幾個(gè)基本操作的算法。(1)串聯(lián)接：把兩個(gè)串s1和s2首尾連接成一個(gè)新串s ，即：sMAXSIZE-1) ret

5、urn 0 ; /* s長(zhǎng)度不夠*/j=0;while(s1j!=0) si=s1j;i+; j+; j=0;while(s2j!=0) si=s2j;i+; j+; si=0; return 1; (2)子串int StrSub (char *t, char *s, int i, int len)/* 用t返回串s中第個(gè)i字符開(kāi)始的長(zhǎng)度為len 的子串1i串長(zhǎng)*/ int slen; slen=StrLength(s); if ( islen | lenslen-i+1) printf(參數(shù)不對(duì)); return 0; for (j=0; jlen; j+) tj=si+j-1;tj=0;

6、return 1; (3) 串比較 int StrComp(char *s1, char *s2) int i=0; while (s1i=s2i & s1i!=0) i+; return (s1i-s2i);4.2 數(shù)組 4.2.1 數(shù)組的定義和基本運(yùn)算 數(shù)組的特點(diǎn)是每個(gè)數(shù)據(jù)元素可以又是一個(gè)線(xiàn)性表結(jié)構(gòu)。因此，數(shù)組結(jié)構(gòu)可以簡(jiǎn)單地定義為：若線(xiàn)性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡(jiǎn)單元素，則稱(chēng)為一維數(shù)組，即為向量；若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱(chēng)為二維數(shù)組；依次類(lèi)推，若二維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)，則稱(chēng)作三維數(shù)組。 結(jié)論：線(xiàn)性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例，而數(shù)組結(jié)構(gòu)又是線(xiàn)性表結(jié)構(gòu)的擴(kuò)展。舉

7、例：圖 4-3 其中，A是數(shù)組結(jié)構(gòu)的名稱(chēng)，整個(gè)數(shù)組元素可以看成是由m個(gè)行向量和n個(gè)列向量組成，其元素總數(shù)為mn。在C語(yǔ)言中，二維數(shù)組中的數(shù)據(jù)元素可以表示成a表達(dá)式1表達(dá)式2，表達(dá)式1和表達(dá)式2被稱(chēng)為下標(biāo)表達(dá)式，比如，aij。 數(shù)組結(jié)構(gòu)在創(chuàng)建時(shí)就確定了組成該結(jié)構(gòu)的行向量數(shù)目和列向量數(shù)目，因此，在數(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) 4.2.2 數(shù)組的存儲(chǔ)結(jié)構(gòu) 從理論上講，

8、數(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)更為適宜。換句話(huà)說(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)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問(wèn)題。舉例：圖 4-4 第0行 第1行 第m-1行圖 4-5 第0列 第1列 第n-1列圖 4-6在C語(yǔ)言中LOC(i,j)=LOC(0,0)+(n*i+j)*L數(shù)組結(jié)構(gòu)的定義：#define MAX_ROW_INDEX 10#define MAX_COL_INDEX 10typedef

9、 struct EnterType itemMAX_ROW_INDEXMAX_COL_INDEX ; ARRAY;基本操作算法舉例：（1）給數(shù)組元素賦值void Assign(ARRAY *A,EnterType item,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) exit(ERROR); else A-itemindex1index2=item;（2）返回給定位置的元素內(nèi)容 int Value(ARRAY A,EntryType *item,int index1,int index2) if

10、(index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) return FALSE; else *item= A.itemindex1index2; return OK; 3矩陣的壓縮存儲(chǔ) 矩陣是在很多科學(xué)與工程計(jì)算中遇到的數(shù)學(xué)模型。在數(shù)學(xué)上，矩陣是這樣定義的：它是一個(gè)由sn個(gè)元素排成的s行（橫向）n列（縱向）的表。下面就是一個(gè)矩陣： 1. 特殊矩陣 所謂特殊矩陣就是元素值的排列具有一定規(guī)律的矩陣。常見(jiàn)的這類(lèi)矩陣有：對(duì)稱(chēng)矩陣、下（上）三角矩陣、對(duì)角線(xiàn)矩陣等等。 對(duì)稱(chēng)矩陣的特點(diǎn)是aij=aji， 2. 稀疏矩陣的壓縮存儲(chǔ) 若一個(gè)mn的矩陣含有t個(gè)非零元素，且t遠(yuǎn)遠(yuǎn)

11、小于m*n，則我們將這個(gè)矩陣稱(chēng)為稀疏矩陣。舉例：圖 4-14 稀疏矩陣的壓縮存儲(chǔ)方法三元組表示法。 矩陣中的每個(gè)元素都是由行序號(hào)和列序號(hào)唯一確定的。因此，我們需要用三項(xiàng)內(nèi)容表示稀疏矩陣中的每個(gè)非零元素，即形式為：(i,j,value) 其中，i表示行序號(hào)，j表示列序號(hào)，value表示非零元素的值，通常將它稱(chēng)為三元。我們將稀疏矩陣中的所有非零元素用這種三元的形式表示，并將它們按以行為主的順序存放在一個(gè)一維數(shù)組中，就形成了我們所說(shuō)的三元組表示法。舉例：圖 4-15define SMAX 1024 /*一個(gè)足夠大的數(shù)*/typedef struct int i,j; /*非零元素的行、列*/ dat

12、atype v; /*非零元素值*/ SPNode; /*三元組類(lèi)型*/typedef struct int mu,nu,tu; /*矩陣的行、列及非零元素的個(gè)數(shù)*/ SPNode dataSMAX; /*三元組表*/ SPMatrix; /*三元組表的存儲(chǔ)類(lèi)型*/4.3 應(yīng)用舉例例.1 若矩陣Amn 中存在某個(gè)元素aij滿(mǎn)足：aij是第i行中最小值且是第j列中的最大值，則稱(chēng)該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫(xiě)一個(gè)算法，找出A中的所有鞍點(diǎn)。 基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個(gè)二維數(shù)組表示 算法如下：void

13、 saddle (int A ,int m, int n) /*m,n是矩陣A的行和列*/ int i,j,min,k,p; for (i=0;im;i+) /*按行處理*/ min=Ai0 for (j=1; jn; j+) if (Aijmin ) min=Aij;/*找第i行最小值*/ for (j=0; jn; j+)/*檢測(cè)該行中的最小值是否是鞍點(diǎn)*/if (Aij=min ) k=j; p=0; while (pm & Apj=m) printf (%d,%d,%dn, i ,k,min); /* if */ /*for i*/ 例4.2 在串的堆分配存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串函數(shù)SUBSTR(S，i，j) 。例4.3 已知一個(gè)二維數(shù)組A，行下標(biāo)0i7，列下標(biāo)0