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

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

2、符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。 概念： 子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。 例如，有下列四個串a(chǎn)，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出現(xiàn)的第一個字符的位置。 兩個串相等：兩個串的長度相等，并且各個對應的字符也都相同。 例如，有下列四個串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）計算串長度StrLength(s) （4）串連接 StrConcat(s1,s2) （5）求子串 SubStr(s,i,len)（6）串的定位 StrIndex(s1,t) 4.1.2 串的存儲結(jié)構(gòu) 1. 順序存儲結(jié)構(gòu) 串的順序存儲結(jié)構(gòu)與線性表的順序存儲類似，用一組連續(xù)的存儲單元依次存儲串中的字符序列。在C語言中，有兩種實現(xiàn)方式： 第一種是事先定義字符串的最大長度，字符串存儲在一個定長的存儲區(qū)中。類型定義如下所示： #define MAXSIZE 255 char s

4、MAXSIZE; 第二種是在程序執(zhí)行過程中，利用標準函數(shù)malloc和free動態(tài)地分配或釋放存儲字符串的存儲單元，并以一個特殊的字符作為字符串的結(jié)束標志，它的好處在于：可以根據(jù)具體情況，靈活地申請適當數(shù)目的存儲空間，從而提高存儲資源的利用率。類型定義如下所示：typedef struct char dataMAXSIZE;int curlen; SeqString;定義一個串變量：SeqString s;不同的定義形式，算法中的處理也略有不同。下面我們將給出在第一種順序存儲方式下串的幾個基本操作的算法。(1)串聯(lián)接：把兩個串s1和s2首尾連接成一個新串s ，即：sMAXSIZE-1) ret

5、urn 0 ; /* s長度不夠*/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中第個i字符開始的長度為len 的子串1i串長*/ int slen; slen=StrLength(s); if ( islen | lenslen-i+1) printf(參數(shù)不對); 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ù)組的定義和基本運算 數(shù)組的特點是每個數(shù)據(jù)元素可以又是一個線性表結(jié)構(gòu)。因此，數(shù)組結(jié)構(gòu)可以簡單地定義為：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡單元素，則稱為一維數(shù)組，即為向量；若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組；依次類推，若二維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組。 結(jié)論：線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴展。舉

7、例：圖 4-3 其中，A是數(shù)組結(jié)構(gòu)的名稱，整個數(shù)組元素可以看成是由m個行向量和n個列向量組成，其元素總數(shù)為mn。在C語言中，二維數(shù)組中的數(shù)據(jù)元素可以表示成a表達式1表達式2，表達式1和表達式2被稱為下標表達式，比如，aij。 數(shù)組結(jié)構(gòu)在創(chuàng)建時就確定了組成該結(jié)構(gòu)的行向量數(shù)目和列向量數(shù)目，因此，在數(shù)組結(jié)構(gòu)中不存在插入、刪除元素的操作。 二維數(shù)組結(jié)構(gòu)的基本操作： （1） 給定一組下標，修改該位置元素的內(nèi)容 Assign(A,item,index1,index2) （2）給定一組下標，返回該位置的元素內(nèi)容 Value(A,item,index1,index2) 4.2.2 數(shù)組的存儲結(jié)構(gòu) 從理論上講，

8、數(shù)組結(jié)構(gòu)也可以使用兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。然而，由于數(shù)組結(jié)構(gòu)沒有插入、刪除元素的操作，所以使用順序存儲結(jié)構(gòu)更為適宜。換句話說，一般的數(shù)組結(jié)構(gòu)不使用鏈式存儲結(jié)構(gòu)。 組成數(shù)組結(jié)構(gòu)的元素可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關系映射到一維關系的問題。舉例：圖 4-4 第0行 第1行 第m-1行圖 4-5 第0列 第1列 第n-1列圖 4-6在C語言中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矩陣的壓縮存儲 矩陣是在很多科學與工程計算中遇到的數(shù)學模型。在數(shù)學上，矩陣是這樣定義的：它是一個由sn個元素排成的s行（橫向）n列（縱向）的表。下面就是一個矩陣： 1. 特殊矩陣 所謂特殊矩陣就是元素值的排列具有一定規(guī)律的矩陣。常見的這類矩陣有：對稱矩陣、下（上）三角矩陣、對角線矩陣等等。 對稱矩陣的特點是aij=aji， 2. 稀疏矩陣的壓縮存儲 若一個mn的矩陣含有t個非零元素，且t遠遠

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

12、atype v; /*非零元素值*/ SPNode; /*三元組類型*/typedef struct int mu,nu,tu; /*矩陣的行、列及非零元素的個數(shù)*/ SPNode dataSMAX; /*三元組表*/ SPMatrix; /*三元組表的存儲類型*/4.3 應用舉例例.1 若矩陣Amn 中存在某個元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。 基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個二維數(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+)/*檢測該行中的最小值是否是鞍點*/if (Aij=min ) k=j; p=0; while (pm & Apj=m) printf (%d,%d,%dn, i ,k,min); /* if */ /*for i*/ 例4.2 在串的堆分配存儲結(jié)構(gòu)上實現(xiàn)求子串函數(shù)SUBSTR(S，i，j) 。例4.3 已知一個二維數(shù)組A，行下標0i7，列下標0