4.1串

4.2數(shù)組

小結(jié)

習(xí)題

實訓(xùn)指導(dǎo)

第4章串與數(shù)組

問題引入

(1)日常工作和生活中，我們使用計算機首先涉及到的就是文字處理了，例如，我們需要進行文字編輯、信息檢索等。我們也使用過多種文字處理軟件，如Word、WPS等。那么，計算機是如何實現(xiàn)強大的文字處理功能呢？若需在自己編寫的軟件中加入文字處理功能，該如何實現(xiàn)呢？

(2)數(shù)組幾乎是各種高級語言都具備的數(shù)據(jù)類型，它在計算機中又是如何實現(xiàn)存儲及運算的呢？使用數(shù)組會給我們解決問題帶來什么樣的便利呢？

知識要點

(1)串的概念、基本運算及串的存儲結(jié)構(gòu)；

(2)串運算的實現(xiàn)；

(3)數(shù)組與特殊矩陣的存儲。

能力要求

充分利用串及數(shù)組的基本運算提高解決實際問題的針對性和有效性。

串(又稱字符串)是一種限定性的線性表，它限定數(shù)據(jù)元素僅由字符組成。計算機處理的對象有數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)，字符串是最基本的非數(shù)值數(shù)據(jù)。如在匯編和高級語言的編譯程序中，源程序和目標程序都是字符串數(shù)據(jù)；在事務(wù)處理程序中，如學(xué)生的姓名、家庭地址、愛好特長等，一般也是作為字符串處理的。隨著計算機的發(fā)展，串在文字編輯、信息檢索、符號處理等許多領(lǐng)域得到越來越廣泛的應(yīng)用。在這些應(yīng)用中，涉及到字符數(shù)據(jù)如何組織、如何存儲、進行什么樣的操作等等。

比如，在文本編輯中，主要工作是修改字符數(shù)據(jù)的形式和格式，也就是對字符串進行查找、插入、刪除和修改等操作。各種編輯軟件的功能強弱不同，但都包括字符串的上述基本操作，通過應(yīng)用這些基本操作，完成文本編輯工作。許多高級語言中也引入了串變量的概念。如同整型、實型變量一樣，串變量也可以參加各種運算，如兩個字符串的連接、求字符串的長度、求子串等。在這一章我們討論串的有關(guān)概念、存儲方法和串的基本運算及其實現(xiàn)。4.1串

4.1.1串的基本概念串(String)是由零個或多個字符組成的有限序列，一般記做S="a1a2…an"(n≥0)其中，S是串名；用雙引號括起來的字符序列為串值；引號是界限符；ai(1≤i≤n)是一個任意字符(字母、數(shù)字或其它字符)，它稱為串的元素，是構(gòu)成串的基本單位；串中所包含的字符個數(shù)n稱為串的長度，當n=0時，稱為空串，通常記為。將串值括起來的雙引號本身不屬于串，它的作用是避免串與常數(shù)或與標識符混淆。

例如，A=“123”是數(shù)字字符串，長度為3，它不同于整常數(shù)123；B=“xahz”是長度為4的字符串，而xahz通常表示一個標識符。

常將僅由一個或多個空格組成的串稱為空白串。注意空串和空白串的不同，例如""和""分別表示長度為1的空白串和長度為0的空串。串中任意連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串。通常稱字符在序列中的序號為該字符在串中的位置。子串在主串中的位置以子串的第一個字符首次在主串中出現(xiàn)的位置來表示。例如，設(shè)有兩個字符串A和B：

A="Thisisastring."

B="is"則它們的長度分別為17和2；B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號(或位置)為3。若兩個串的長度相等且對應(yīng)字符都相等，則稱兩個串是相等的。當兩個串不相等時，可按“字典順序”分大小。串也是線性表的一種，因此串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象限定為字符集。串的運算有很多，下面介紹部分基本運算。

(1)串賦值：已知串常量chars，生成一個值等于chars的串s。

(2)求串長：已知串s，返回串s的長度。

(3)串連接：已知串s1和s2，在s1的后面連接s2的串值。

(4)求子串：已知串s，返回從串s的第i個字符開始的長度為len的子串。

(5)串比較：已知串s1和s2，s1==s2，操作返回值為0；s1<s2，返回值<0；s1>s2，返回值>0。

(6)子串定位：已知串s和t，找子串t在主串s中首次出現(xiàn)的位置，即若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回?-1。

(7)串插入：已知串s和t，將串t插入到串s的第i個字符位置上。

(8)串刪除：已知串s，刪除串s中從第i個字符開始的長度為len的子串。

(9)串替換：已知串s、t和r，用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串。

(10)撤銷串：已知串s，撤銷串s。以上是串的一些基本操作。其中前5個操作是最為基本的，它們不能用其它的操作來合成，因此通常將這5個基本操作稱為最小操作集，反之，其它操作可在這個最小操作集上實現(xiàn)。4.1.2串的存儲結(jié)構(gòu)因為串是數(shù)據(jù)元素類型為字符型的線性表，所以線性表的存儲方式仍適用于串。也因為字符的特殊性和字符串經(jīng)常作為一個整體來處理的特點，所以串在存儲時還有一些與一般線性表不同之處。

1．串的順序存儲串的順序存儲結(jié)構(gòu)簡稱為順序串。與順序表類似，順序串是用一組地址連續(xù)的存儲單元來存儲串中的字符序列。因此可用高級語言的字符數(shù)組來實現(xiàn)，按其存儲分配的不同，可將順序串分為靜態(tài)存儲分配順序串和動態(tài)存儲分配的順序串兩類。

1)靜態(tài)存儲分配順序串所謂靜態(tài)存儲分配是指按預(yù)定義的大小，為每一個串變量分配一個固定長度的存儲區(qū)，即串值空間的大小在編譯時刻就已確定，是靜態(tài)的。所以串空間最大值為Maxsize時，最多只能放Maxsize-1個字符。其類型描述如下：

結(jié)構(gòu)4-1

順序串。

#defineMaxsize256 //該值依賴于應(yīng)用，由用戶定義

typedefstruct

{charch[Maxsize]; //字符依次存儲在ch[0]..ch[Maxsize-1]中

intlen;

}sstring; //sstring是順序串類型，串的最大長度不能超過255在實際應(yīng)用中，可聲明一個sstring類型的變量s以實現(xiàn)對串的操作運算。在直接使用定長的字符數(shù)組存放串內(nèi)容時，一般可使用一個不會出現(xiàn)在串中的特殊字符放在串值的末尾來表示串的結(jié)束。例如，C語言中以字符'\0'表示串值的終結(jié)。

C語言中串的靜態(tài)存儲結(jié)構(gòu)如圖4-1所示。圖4-1C語言中串的靜態(tài)存儲結(jié)構(gòu)

2)動態(tài)存儲分配的順序串(堆串)動態(tài)存儲分配的順序串仍以一組地址連續(xù)的存儲單元存放串中的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得的。系統(tǒng)將一個地址連續(xù)、容量很大的存儲空間作為字符串的可用空間，每當建立一個新串時，系統(tǒng)就從這個空間中分配一個大小和字符串長度相同的空間存儲新串的串值。假設(shè)以一維數(shù)組heap[Maxsize]表示可供字符串進行動態(tài)分配的存儲空間，并設(shè)一整型變量free指向heap中未分配區(qū)域的開始地址。在程序執(zhí)行過程中，當生成一個新串時，就從free指示的位置起為新串分配一個所需大小的存儲空間，同時記錄該串的相關(guān)信息。這種存儲結(jié)構(gòu)稱為堆結(jié)構(gòu)。動態(tài)分配存儲空間的順序串也叫堆串。堆串可定義如下：

結(jié)構(gòu)4-2

堆串。

typedefstruct

{intlength;

intstart;

}heapstring;在C語言中，已經(jīng)有一個稱為“堆”的自由存儲空間，故可利用malloc()和free()等動態(tài)存儲管理函數(shù)，根據(jù)實際需要動態(tài)分配和釋放字符數(shù)組空間，如圖4-2所示。圖4-2順序串的動態(tài)存儲結(jié)構(gòu)其類型可描述如下：

結(jié)構(gòu)4-3C語言中的堆串。

typedefstruct

{char*ch; //指示串的起始地址，可按實際的串長分配存儲區(qū)

intlen;

}hstring;

hstrings; //定義一個串變量在程序中，可根據(jù)實際需求為這種類型的串變量動態(tài)分配存儲空間，非常有效、方便，只是在程序執(zhí)行過程中要不斷地生成新串和銷毀舊串。

2．串的鏈式存儲順序串上的插入和刪除操作不方便，需要移動大量的字符。因此，我們可用單鏈表方式來存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串，如圖4-3所示。圖4-3結(jié)點大小為1的鏈串s鏈串的類型可描述如下：

結(jié)構(gòu)4-4鏈串。

typedefstructnode

{charch;

structnode*next; //next為指向結(jié)點的指針

}lstring;一個鏈串可由指向頭結(jié)點的指針s唯一確定。鏈串結(jié)構(gòu)便于進行插入和刪除運算，但存儲空間利用率太低。為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小，顯然，當結(jié)點大小大于1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符來填充最后一個結(jié)點，以表示串的終結(jié)。對于結(jié)點大小不為1的鏈串，其類型定義只需對上述的結(jié)點類型做簡單的修改即可，如圖4-4所示。圖4-4結(jié)點大小為4的鏈串

結(jié)構(gòu)4-5鏈串。

#definenodesize80

typedefstructnode

{chardata[nodesize];

structnode*next;

}lstring;雖然提高結(jié)點的大小使得存儲密度增大，但是做插入、刪除運算時，需要考慮結(jié)點的分拆與合并，可能會引起大量字符的移動，給運算帶來不便。圖4-5所示為在圖4-4所示鏈串的第三個字符之后插入“xyz”后的鏈串。圖4-5鏈串的插入4.1.3串運算的實現(xiàn)選擇不同的存儲結(jié)構(gòu)，則有不同的運算算法。這一節(jié)我們將討論在不同的存儲結(jié)構(gòu)下串的部分基本運算。采用靜態(tài)存儲順序串，則串變量的長度是固定的，即是一個定長字符數(shù)組。這時，串的長度可在定義的長度范圍內(nèi)變化，超過預(yù)定義長度的串值則被舍去。所以，在改變串長的操作中，如串的連接、插入和替換等運算中就要考慮超出預(yù)定義長度的串值將被截去的情況。采用動態(tài)存儲順序串，串變量的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得的，可根據(jù)實際需求為串變量動態(tài)分配存儲空間，非常有效、方便，但需不斷地生成新串、撤消舊串。采用鏈串存儲方式，便于進行插入和刪除運算，但存儲空間利用率相對較低。若提高結(jié)點的存儲密度，又會給操作帶來不便，所以較少使用。下面，我們采用靜態(tài)存儲順序串，實現(xiàn)求子串運算、定位運算；采用動態(tài)存儲順序串，實現(xiàn)串插入、串連接運算；采用鏈串存儲方式實現(xiàn)串定位運算。

算法4-1

求子串(采用靜態(tài)存儲順序串)。采用靜態(tài)存儲順序串，在已知串s中求從pos開始的長度為len的字串，用指針類型sub返回。算法描述如下：intstrsub(sstring*sub,sstrings,intpos,intlen){inti;if(pos<0||pos>s.len||len<1||len>s.len-pos){sub->len=0;return(0);} //子串起始位置及長度是否合適else{for(i=0;i<len;i++)sub->ch[i]=s.ch[i+pos];sub->ch[len]=’\0’; //子串結(jié)束sub->len=len;return(1);}}

算法4-2

定位。串的定位運算也稱為串的模式匹配，是一種重要的串運算。設(shè)s和t是給定的兩個串，在主串s中找到等于子串t的過程稱為模式匹配，如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲位置(或序號)，否則匹配失敗，返回-1。t也稱為模式。算法思想如下：首先將s0與t0進行比較，若不同，就將s1與t0進行比較，…，直到s的某一個字符si和t0相同，再將它們之后的字符進行比較，若也相同，則如此繼續(xù)往下比較，當s的某一個字符si與t的字符tj不同時，則s返回到本趟開始字符的下一個字符，即si-j+1，t返回到t0，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若t中的字符全部比較完，則說明本趟匹配成功，本趟的起始位置是i-j，否則，匹配失敗。設(shè)主串s="ababcabcacbab"，模式t="abcac"，匹配過程如圖4-6所示。采用靜態(tài)存儲順序串，算法描述如下：intstrindex(sstrings,intpos,sstringt){inti,j;if(t.len==0)return(0);i=pos;j=0;while(i<s.len&&j<t.len) //都沒遇到結(jié)束符

if(s.ch[i]==t.ch[j]){i++;j++;}

//繼續(xù)

else{i=i-j+1;j=0;} //回溯

if(j>=t.len)return(i-j);

//匹配成功，返回存儲位置

elsereturn(-1);}圖4-6簡單模式匹配的匹配過程

算法4-3

插入。采用動態(tài)存儲串，在已知串s的第pos個字符之前插入串t。算法描述如下：

intstrinsert(hstring*s,intpos,hstringt)

{char*temp;

inti;

if(pos<0||pos>s->len)return(0); //pos不合理

if(t.len)

//非空

{temp=(char*)malloc((s->len+t.len)*sizeof(char)); //臨時變量，用來暫存插入后的結(jié)果if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=0;i<t.len;i++)temp[i+pos]=t.ch[i];for(i=pos;i<=s->len;i++)temp[i+t.len]=s->ch[i];s->len+=t.len;s->ch=temp; //獲得相加結(jié)果

return(1);}}

算法4-4

連接。采用動態(tài)存儲串，將串t連接在串s的后面。算法描述如下：strcat(hstring*s,hstringt){char*temp;inti;temp=(char*)malloc((s->len+t.len)*sizeof(char));if(temp==NULL)return(0);for(i=0;i<=s->len;i++)temp[i]=s->ch[i]; //復(fù)制s串

for(i=s->len;i<=s->len+t.len;i++) //復(fù)制t串

temp[i]=t.ch[i-s->len];s->len+=t.len;s->ch=temp;return(1);}

算法4-5

串定位。采用鏈串存儲，求串t在串s中的位置，返回指向t串起始位置的指針。

lstring*lindex(lstring*s,lstring*t)

{lstring*loc,*p,*q;

loc=s;

p=loc;q=t;

while(p&&q) //當t、s串均未結(jié)束時

{if(p->data==q->data) //字符匹配時，指針后移

{p=p->next;

q=q->next;

}else //字符不匹配時，回溯{loc=loc->next;p=loc;q=t;}}if(q==NULL)return(loc); //匹配完成，返回

elsereturn(NULL);}4.2數(shù)組

數(shù)組可以視為一種擴展的特殊線性數(shù)據(jù)結(jié)構(gòu)，其特殊性是反映在數(shù)據(jù)元素的構(gòu)成上。在線性表中，每個數(shù)據(jù)元素都是不可再分的原子類型，而數(shù)組中的數(shù)據(jù)元素可以推廣到是一種具有特定結(jié)構(gòu)的數(shù)據(jù)。數(shù)組結(jié)構(gòu)有著廣泛的應(yīng)用。例如，一批同類型的數(shù)據(jù)序列可以看成一個一維數(shù)組結(jié)構(gòu)；一個矩陣就是一個二維數(shù)組結(jié)構(gòu)等。本節(jié)討論數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、特殊矩陣以及矩陣的壓縮存儲等。4.2.1數(shù)組的定義和運算數(shù)組是我們很熟悉的一種數(shù)據(jù)類型，很多高級語言都支持這種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看做一般線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看做一個線性表，二維數(shù)組可以看做“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看做“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。例如，對線性表A=(A0，A1，A2，…，An-1)，如果其中的任意元素Aj(0≤j≤n-1)是簡單類型，則A是一個一維數(shù)組，如果Aj本身也是一個線性表，即Aj=(a1j，a2j，…am-1，j)，則A是一個二維數(shù)組，如圖4-7所示。同理，三維數(shù)組可以看成是這樣的一個線性表，其中每個數(shù)據(jù)元素均是一個二維數(shù)組。依此類推，可以得到多維數(shù)組。圖4-7由線性表推廣得到的二維數(shù)組從數(shù)組的特殊結(jié)構(gòu)可以看出，數(shù)組中的每一個元素由一個值和一組下標來描述。“值”代表數(shù)組中元素的數(shù)據(jù)信息，一組下標用來描述該元素在數(shù)組中的相對位置信息。數(shù)組的維數(shù)不同，描述其對應(yīng)位置的下標的個數(shù)也不同。例如，在二維數(shù)組中，元素aij由兩個下標值i、j來描述，其中i表示該元素所在的行號，j表示該元素所在的列號。同樣，我們可以將這個特性推廣到多維數(shù)組：對于n維數(shù)組而言，其元素由n個下標值來描述其在n維數(shù)組中的相對位置。根據(jù)數(shù)組的結(jié)構(gòu)特性可以看出，數(shù)組實際上是一組有固定個數(shù)的元素的集合。也就是說，一旦定義了數(shù)組的維數(shù)和每一維的上下限，數(shù)組中元素個數(shù)就固定了。例如二維數(shù)組A3×4，它有3行、4列，即由12個元素組成。由于這個性質(zhì)，使得對數(shù)組的操作不像對線性表的操作那樣可以在表中任意一個合法的位置插入或刪除一個元素。通常在各種高級語言中，數(shù)組一旦被定義，每一維的大小及上下界就都不能改變。對于數(shù)組的操作一般有以下兩種：

(1)取值操作：給定一組下標，讀取對應(yīng)的數(shù)據(jù)元素值；

(2)賦值操作：給定一組下標，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素值。我們著重研究二維數(shù)組，因為它的應(yīng)用最為廣泛。4.2.2數(shù)組的順序存儲和實現(xiàn)對于數(shù)組A，一旦給定其維數(shù)n及各維長度bi(1≤i≤n)，則該數(shù)組中元素的個數(shù)是固定的，不能對數(shù)組做插入和刪除操作。由于不涉及移動數(shù)據(jù)元素操作，因此對于數(shù)組而言，采用順序存儲方式比較合適。我們知道，計算機內(nèi)存器的結(jié)構(gòu)是一維的，因此對于一維數(shù)組，只需按下標順序分配內(nèi)存即可。而對多維數(shù)組，就必須按照某種次序，將數(shù)據(jù)元素排成一個線性序列，然后將這個線性序列存放在存儲器中。數(shù)組的順序存儲結(jié)構(gòu)有兩種：一是以行為主序(或先行后列)的順序存放，如BASIC、Pascal、COBOL、C等程序設(shè)計語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行；另一種是以列為主序(先列后行)的順序存放，如FORTRAN語言中，用的是以列為主序的分配順序，即一列一列地分配。以行為主序的分配規(guī)律是：最右邊的下標先變化，即最右下標從小到大，循環(huán)一遍后，右邊第二個下標再變，…，從右向左，最后是最左下標。以列為主序分配的規(guī)律恰好相反：最左邊的下標先變化，即最左下標從小到大，循環(huán)一遍后，左邊第二個下標再變，…，從左向右，最后是最右下標。例如，二維數(shù)組Am×n以行為主序的存儲序列為

a00，a01，…，a0，n-1

，a10，a11，…，a1，n-1，…，am-1，0，am-1，1，…，am-1，n-1而以列為主序的存儲序列為a00，a10，…，am-1，0，a01，a11，…，am-1，1，…，a0，n-1，a1，n-1，…，am-1，n-1例如一個2?×?3的二維數(shù)組，邏輯結(jié)構(gòu)可以用圖4-8(a)表示。以行為主序的內(nèi)存映像如圖4-8(b)所示，分配順序為：a00，a01，a02，a10，a11，a12；以列為主序的分配順序為：a00，a10，a01，a11，a02，a12，它的內(nèi)存映像如圖4-8(c)所示。圖4-82?×?3數(shù)組存儲假設(shè)有一個3?×?4?×?2的三維數(shù)組A，共有24個元素，其邏輯結(jié)構(gòu)如圖4-9所示。

圖4-9三維數(shù)組的邏輯結(jié)構(gòu)三維數(shù)組元素的標號由三個數(shù)字表示。如果對A3×4×2采用以行為主序的方式存放，則順序為a000，a001，a010，a011，…，a220，a221，a230，a231采用以列為主序的方式存放，則順序為a000，a100，a200，a010，…，a221，a031，a131，a231以上的存放規(guī)則可推廣到多維數(shù)組的情況?？傊?，知道了多維數(shù)組的維數(shù)以及每維的上下界，就可以方便地將多維數(shù)組按順序存儲結(jié)構(gòu)存放在計算機中了。同時，根據(jù)數(shù)組的下標，可以計算出其在存儲器中的位置。因此，數(shù)組的順序存儲是一種隨機存取的結(jié)構(gòu)。下面，以“以行為主序”的分配為例，討論數(shù)組中數(shù)據(jù)元素存儲位置的計算。設(shè)有二維數(shù)組Am×n，下標從0開始，假設(shè)每個數(shù)組元素占size個存儲單元，首元素a00的存儲地址為LOC[0，0]。對任意元素aij來說，因為aij排在第i行，第j列，前面的i行有n?×?i個元素，第i行第j列個元素前面還有j個元素，所以可得aij的地址計算公式如下：LOC[i，j]=LOC[0，0]+(i×n+j)×?size同理，對三維數(shù)組Ar×m×n，可以看成是r個m?×?n的二維數(shù)組，若首元素的存儲地址為LOC[0，0，0]，則元素ai11的存儲地址為LOC[i，1，1]=LOC[0，0，0]+(i?×?m?×?n)?×?size，這是因為在該元素之前有i個m?×?n的二維數(shù)組。由ai11的地址和二維數(shù)組的地址計算公式，不難得到三維數(shù)組任意元素aijk的地址計算公式：LOC[i,j,k]＝LOC[0,0,0]+(i×m×n+j×n?+?k)?×size其中，0≤i≤r-1，0≤j≤m-1，0≤k≤n-1。數(shù)組是各種高級語言中均已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。在高級語言的應(yīng)用層上，一般不會涉及到數(shù)據(jù)元素存儲地址的計算，這一計算內(nèi)存地址的任務(wù)是由高級語言的編譯系統(tǒng)完成的。當我們使用數(shù)組進行程序設(shè)計時，只需給出數(shù)組的下標范圍，編譯系統(tǒng)將根據(jù)用戶提供的必要參數(shù)進行地址分配，存取數(shù)據(jù)元素時，也只要給出下標，而不必考慮其內(nèi)存情況。實例4-1若矩陣Am×n中存在某個元素aij且滿足aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素是否是它所在列中的最大值，是，則將其打印出來，接著處理下一行。矩陣A用一個二維數(shù)組表示。算法如下：voidsaddle(intA[][],intm,intn) //m，n是矩陣A的行和列{inti,j,min;for(i=0;i<m;i++)

//按行處理

{min=A[i][0]?for(j=1;j<n;j++)if(A[i][j]<min)min=A[i][j];

//找第i行最小值

for(j=0;j<n;j++) //檢測該行中的每一個最小值是否是鞍點

if(A[i][j]==min){k=j;p=0;while(p<m&&A[p][j]<=min)p++;if(p>=m)printf("%d,%d,%d\n",i,k,min);}}}4.2.3特殊矩陣的壓縮存儲矩陣是科學(xué)計算、工程數(shù)學(xué)中大量研究的對象。對于一個矩陣結(jié)構(gòu)用一個二維數(shù)組來表示顯然是非常恰當?shù)?。但在有些情況下，例如有些高階矩陣中，階次很高，數(shù)據(jù)量很大，而非零元素非常少(遠小于m?×?n)，若仍采用二維數(shù)組存放，就會有很多存儲單元都存放的是0，這不僅造成存儲空間的浪費，而且給運算帶來了很大的不便，這時，就很希望能夠只存儲部分有效元素。另外，還有一些矩陣的數(shù)據(jù)元素分布有一定規(guī)律，如三角矩陣、對稱矩陣、帶狀矩陣等，那么就可以利用這些規(guī)律，只存儲部分元素，從而提高存儲空間的利用率。這些問題都需要對矩陣進行壓縮存儲。一般的壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲空間，對零元素不分配空間。我們在這一節(jié)討論幾種特殊矩陣及對它們進行壓縮存儲的方式。

1．三角矩陣三角矩陣可以分為三類：下三角矩陣、上三角矩陣、對稱矩陣。對于一個n階矩陣A來說，若當i<j時，有aij=0或aij=c(c為常數(shù))，則稱此矩陣為下三角矩陣；若當i>j時，有aij=0或aij=c(c為常數(shù))，則稱此矩陣為上三角矩陣；若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對稱矩陣。例如，圖4-10所示就是一個n?×?n的下三角矩陣，我們以此為例來討論三角矩陣的壓縮存儲。圖4-10n?×?n的下三角矩陣A對于下三角矩陣，只需存儲下三角的非零元素，對于零元素則不存儲。若以“行序為主序”進行存儲，則得到的序列是a00，a10，a11，a20，…，an-1，0，an-1，1，…，an-1，n-1由于下三角矩陣的元素個數(shù)為n(n+1)/2，即第0行：1個第1行：2個第2行：3個

………第n-1行：n個共有1+2+3+…+n=n(n+1)/2個元素。

所以可將三角矩陣壓縮到一個大小為n(n+1)/2的一維數(shù)組C中，如圖4-11所示。圖4-11三角矩陣的壓縮存儲假設(shè)每個數(shù)據(jù)元素占size個存儲單元，下三角矩陣中任意元素aij在一維數(shù)組C中的存儲位置可通過下式計算：Loc[i，j]=Loc[0，0]+(i(i+1)/2+j)×size(i≥j)也就是說，如果C中數(shù)據(jù)元素C[k]的下標為k，則k與下三角矩陣中數(shù)據(jù)元素aij的下標i、j之間的關(guān)系為k=i(i+1)/2+j若上三角部分為一常數(shù)c，則數(shù)組的大小可設(shè)為C[n(n+1)/2+1]，其中C[n(n+1)/2]存放常數(shù)c。例如，對一個5?×?5的下三角矩陣A，可以用一維數(shù)組C[15]對其進行壓縮存儲，如圖4-12所示。圖4-125?×?5的下三角矩陣的壓縮存儲同理，對上三角矩陣，只需存儲上三角的非零元素，對于零元素則不存儲，同樣可以將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組中。若以“行序為主序”進行存儲，得到的序列是a00，a01，a02，…，a0，n-1，a1，n-1，…，an-1，n-1其中，元素aij(i≤j)在數(shù)組C中的存儲位置為k=i(2n-i+1)/2+j-i(i≤j)

請大家試著自己推導(dǎo)這一結(jié)果。對于對稱矩陣，則可以只存儲上三角部分，也可只存儲下三角部分，將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組中。若只存儲下三角部分，那么元素aij在數(shù)組C中的存儲位置為(i≥j)(i≤j)

2．稀疏矩陣設(shè)m?×?n矩陣中有t個非零元素，且t<<m?×?n，這樣的矩陣稱為稀疏矩陣。很多科學(xué)管理及工程計算中，常會遇到階數(shù)很高的大型稀疏矩陣。如果按常規(guī)分配方法順序分配計算機內(nèi)存，那將是相當浪費內(nèi)存的，并且也給計算帶來不便。如圖4-13所示的矩陣M中，非零元素個數(shù)為8個，矩陣元素為42個，顯然是一個稀疏矩陣。圖4-13稀疏矩陣M

1)稀疏矩陣的三元組表存儲對于稀疏矩陣，我們設(shè)想另外一種存儲方法，即僅僅存放非零元素。但這類矩陣中零元素的分布通常沒有規(guī)律，為了能找到相應(yīng)的元素，所以僅存儲非零元素的值是不夠的，還要記下它所在的行和列。于是采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個三元組(row，col，value)，然后再按某種規(guī)律存儲這些三元組，這就是稀疏矩陣的三元組表示法。每個非零元素在一維數(shù)組中的表示形式如圖4-14所示。

圖4-14三元組的結(jié)構(gòu)將三元組按行優(yōu)先的順序，同一行中列號從小到大的規(guī)律排列成一個線性表，稱為三元組表，采用順序存儲方法存儲該表。如圖4-13所示稀疏矩陣對應(yīng)的三元組表如圖4-15所示。圖4-15稀疏矩陣的三元組表表示顯然，要唯一地表示一個稀疏矩陣，在存儲三元組表的同時還需要存儲該矩陣的總行數(shù)、總列數(shù)。為了運算方便，矩陣的非零元素的個數(shù)也同時存儲。三元組表的類型說明如下：

結(jié)構(gòu)4-6矩陣的三元組。defineMaxsize1024 //一個足夠大的數(shù)typedefstruct{introw,col; //非零元素的行、列

datatypev; //非零元素值}triple; //三元組類型typedefstruct{intmu,nu,tu; //矩陣的行、列及非零元素的個數(shù)

tripledata[Maxsize?+?1]; //三元組表，data[0]未用}tsmatrix; //三元組表的存儲類型

2)用三元組表實現(xiàn)稀疏矩陣的轉(zhuǎn)置矩陣的三元組存儲方法確實節(jié)約了存儲空間，但矩陣的運算從算法上可能變得復(fù)雜些。下面以稀疏矩陣的轉(zhuǎn)置運算為例介紹其實現(xiàn)方法。所謂的矩陣轉(zhuǎn)置，是指把位于(row，col)位置上的元素轉(zhuǎn)換到(col，row)位置上，也就是說，把元素的行列互換。如圖4-13所示的6×7矩陣M，它的轉(zhuǎn)置矩陣就是7×6的矩陣N，如圖4-16所示。圖4-16矩陣M的轉(zhuǎn)置矩陣N顯然，稀疏矩陣的轉(zhuǎn)置矩陣仍為稀疏矩陣，所以可以采用三元組表實現(xiàn)矩陣的轉(zhuǎn)置。聲明兩個三元組變量：

tsmatrixA,B;

A表示一個m×n的稀疏矩陣，其轉(zhuǎn)置B則是一個n×m的稀疏矩陣，由A求B需要以下條件：

(1)?A的行、列轉(zhuǎn)化成B的列、行；

(2)將A.data中每一三元組的行列交換后存放到B.data中；并且保證B.data中的數(shù)據(jù)也是以“行序為主序”進行存放(B.data中的行號即為A.data中的列號)。要保證B.data中的數(shù)據(jù)也是以“行序為主序”進行存放，可以有兩種方法，下面分別介紹。

算法4-6轉(zhuǎn)置方法一。這種方法的思路是按照A.data中的列序進行轉(zhuǎn)置，并依次送入B.data中，即在A.data中依次找第一列的、第二列的，直到最后一列，并將找到的每個三元組的行、列交換后順序存儲到B.data中即可，如圖4-17所示。圖4-17矩陣的轉(zhuǎn)置附設(shè)一個位置計數(shù)器j，用于指向當前轉(zhuǎn)置后元素應(yīng)放入三元組表B.data中的位置。處理完一個元素后，j加1，j的初值為1。具體轉(zhuǎn)置算法如下：voidtranstsmatrix1(tsmatrixA，tsmatrix*B)//為了能使調(diào)用函數(shù)得到轉(zhuǎn)置結(jié)果，我們將B設(shè)為指針類型{inti,j,k;B->mu=A.nu;B->nu=A.mu;B->tu=A.tu;

//稀疏矩陣的行、列、元素個數(shù)

if(B->tu>0)

//有非零元素則轉(zhuǎn)換

{j=1;

?for(k=1;k<=A.nu;k++)

//按A的列序轉(zhuǎn)換

for(i=1;i<=A.tu;i++)

//掃描整個三元組表

if(A.data[i].col==k)

{B->data[j].row=A.data[i].col;?B->data[j].col=A.data[i].row;?B->data[j].v=A.data[i].v;

j++;

}

}}分析該算法，其時間主要耗費在col和p的二重循環(huán)上，所以其時間復(fù)雜性為O(n?×?t)，(設(shè)m、n是原矩陣的行、列，t是稀疏矩陣的非零元素個數(shù))，和通常存儲方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲空間，但算法的時間性能更差一些。

算法4-7轉(zhuǎn)置方法二。方法一效率低的原因是算法要從A的三元組表中尋找第一列、第二列、…，要反復(fù)搜索A表。若能直接確定A中每一三元組在B中的位置，則對A的三元組表掃描一次即可。這是可以做到的，因為A中第一列的第一個非零元素一定存儲在B.data[1]，如果還知道第一列的非零元素的個數(shù)，那么第二列的第一個非零元素在B.data中的位置便等于第一列的第一個非零元素在B.data中的位置加上第一列的非零元素的個數(shù)，依次類推。因為A中三元組的存放順序是先行后列，對同一行來說，必定先遇到列號小的元素，這樣只需掃描一遍A.data即可。根據(jù)這個想法，需引入兩個輔助數(shù)組來實現(xiàn)：num[n+1]和pos[n+1]。num[col]表示矩陣A中第col列的非零元素的個數(shù)(為了方便均從1單元用起)，pos[col]初始值表示矩陣A中的第col列的第一個非零元素在B.data中的位置。于是pos的初始值為

pos[1]=1；

pos[col]=pos[col-1]+num[col-1]；2≤col≤n例如對于圖4-17中矩陣A的num和pos的值如圖4-18所示。圖4-18矩陣A的num與pos值依次掃描A.data，當掃描到一個col列元素時，直接將其存放在B.data的pos[col]位置上，pos[col]加1。pos[col]中始終是下一個col列元素在B.data中的位置。按以上思路改進轉(zhuǎn)置算法如下：

voidtranstsmatrix2(tsmatrixA，tsmatrix*B)

{inti,j,k,col;

intnum[n+1],pos[n+1];

B->mu=A.nu;B->nu=A.mu;B->tu=A.tu;

//稀疏矩陣的行、列、元素個數(shù)

if(B->tu)

//有非零元素則轉(zhuǎn)換{for(col=1;col<=A.nu;col++)num[col]=0;for(k=1;k<=A.tu;k++) //求矩陣A中每一列非零元素的個數(shù)

num[A.data[k].col]++;pos[1]=1; //矩陣A中每一列第一個非零元素在B.data中的位置for(col=2;col<=A.nu;col++)pos[col]=pos[col-1]+num[col-1];

for(i=1;i<=A.tu;i++)

//掃描三元組表

{col=A.data[i].col;

//當前三元組的列號

j=pos[col];

//當前三元組在B.data中的位置

B->data[j].col=A.data[i].row;B->data[j].row=A.data[i].col;B->data[j].v=A.data[i].v;

pos[col]++;

}}}分析這個算法的時間復(fù)雜度：這個算法中有四個循環(huán)，分別執(zhí)行n、t、n-1、t次，在每個循環(huán)中，每次迭代的時間是一常量，因此總的計算量是O(n+t)。當然它所需要的存儲空間比前一個算法多了兩個輔助數(shù)組。小結(jié)

本章主要介紹了串和數(shù)組的概念及其基本運算和存儲結(jié)構(gòu)，回顧這些內(nèi)容，應(yīng)重點理解和掌握以下內(nèi)容：

(1)串(字符串)是數(shù)據(jù)類型受限的線性結(jié)構(gòu)，其數(shù)據(jù)元素只能是字符類型的。串可以作為一個整體參與各種操作。高級語言中均已可以使用不同的表達方式表示一個串結(jié)構(gòu)。

(2)關(guān)于串的運算有多種，其中串賦值、求串長、串連接、求子串、串比較等是最基本的運算。高級語言中也提供了多種串的運算函數(shù)，可在實際中靈活應(yīng)用。

(3)數(shù)組是各種高級語言中均包含的數(shù)據(jù)類型，我們在學(xué)習(xí)線性表、棧、隊列、串等結(jié)構(gòu)時就借助數(shù)組來實現(xiàn)它們的順序存儲結(jié)構(gòu)。正因為此，數(shù)組在很多高級語言中一旦定義，其結(jié)構(gòu)是不可改變的，所以，數(shù)組所涉及到的運算主要是存和取。

(4)二維以上的數(shù)組可看做是一維數(shù)組的推廣。一維和二維數(shù)組的應(yīng)用最為廣泛。二維數(shù)組可按行或按列存儲，每個數(shù)組元素的存儲位置可通過數(shù)組起始地址、每個元素所占空間以及元素在數(shù)組中的位置求得。矩陣與二維數(shù)組的結(jié)構(gòu)一致，所以常常用二維數(shù)組來解決有關(guān)矩陣的問題。對特殊矩陣，如對稱矩陣、三角矩陣、稀疏矩陣等可采用壓縮實現(xiàn)有效存儲和運算。

習(xí)題

一、填空題

1．串(字符串)也是一種受限的線性表，其特點是它的數(shù)據(jù)元素只能是

，它可以作為一個

參與所需要的運算。

2．空白串是由

組成的串，空串是

的串，因此空白串和空串不同。

3.字符串中任意多個

字符所組成的子序列被稱為是這個串的“子串”，這個字符串本身則為“主串”。

4.設(shè)有串s="Iamastudent"，則該串的長度是

。

5.數(shù)組是指n(n>1)個具有

的數(shù)據(jù)元素的有序集合。

6.數(shù)組在很多高級語言中一旦定義，其結(jié)構(gòu)就是不可改變的，所以，數(shù)組所涉及到的運算主要

。

7.對稱矩陣的特點是

，下三角矩陣的特點是

，上三角矩陣的特點是

，稀疏矩陣的特點是

。

8.設(shè)有一個5階上三角矩陣A，將其元素按行優(yōu)先順序存放在一維數(shù)組B中，若每個元素占用2個存儲單元，B[0]的地址是100，那么A[3][4]的地址是

。二、選擇題

1．設(shè)有兩個串s1和s2，求s2在s1中首次出現(xiàn)的位置的操作稱為()。A.連接 B.模式匹配C.求子串 D.求串長

2．串“”的長度是()。

A.?0 B.?1 C.?2 D.?3

3.設(shè)有一個8階的對稱矩陣A，采用以行優(yōu)先的方式壓縮存儲。a11為第一個元素，存儲地址為1，每個元素占一個地址空間，那么元素a85的地址是()。

A.?33 B.?130 C.?13 D.?23

4.一個m×m的對稱矩陣，如果以行優(yōu)先的方式壓縮存儲，那么所需的存儲容量應(yīng)為()。

A.?m×(m-1)/2 B.?m×m/2

C.?m×(m+1)/2

D.?(m+1)×(m+1)/2

5.二維數(shù)組M中的每個元素占3個存儲單元，行下標i的范圍是1..8，列下標的范圍是1..10，M的首地址是M，那么該數(shù)組以行優(yōu)先存儲時，元素M[8][5]的起始地址應(yīng)該是()。

A.?M+141B.?M+180C.?M+222D.?M+225三、問答題

1．簡述下列每對術(shù)語的區(qū)別：空串和空白串；串常量和串變量；主串和子串；靜態(tài)分配的順序串和動態(tài)分配的順序串。

2.設(shè)s="Iamastudent",t="good",q="programer"。給出下列操作的結(jié)果：

StrLength(s)；SubString(sub1,s,1,7)；StrIndex(s,'a',4)；

StrReplace(s,'student',q)；Strcat(StrCat(sub1,t))。

3.設(shè)有7行8列的二維數(shù)組A，每個數(shù)據(jù)元素占4個存儲單元，已知A[0，0]的地址為1000，計算：

(1)數(shù)組A共占用多少存儲單元；

(2)數(shù)組A的最后一個元素的地址；

(3)按行存儲時元素a46的地址；

(4)按列存儲時元素a46的地址。

4.對上三角矩陣，將其壓縮存儲到一個一維數(shù)組C中。若以“行序為主序”進行存儲，試求元素aij(i≤j)在數(shù)組C中的存儲位置。

5.試給出圖4-19所示矩陣的三元組，并根據(jù)所得三元組分別按照兩種轉(zhuǎn)置求其轉(zhuǎn)置矩陣的三元組。圖4-19第5題圖四、應(yīng)用題

1．編寫一個程序?qū)崿F(xiàn)順序棧上的各種基本操作，在主函數(shù)中通過菜單選擇完成。

2．利用C的庫函數(shù)strlen,strcpy和strcat寫一算法voidStrInsert(char*S,char*T,inti),將串T插入到串S的第i個位置上。若i大于S的長度，則插入不執(zhí)行。

3．以hstring為存儲表示，寫一個求子串的算法。

4.一個文本串可用事先給定的字母映射表進行加密。例如，設(shè)字母映射表為

abcdefghijklmnopqrstuvwxyz

ngzqtcobmuhelkpdawxfyivrsj

則字符串"encrypt"被加密為"tkzwsdf"。試寫一算法將輸入的文本串進行加密后輸出；另寫一算法將輸入的已加密的文本串進行解密后輸出。

5.當稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)時，試寫出矩陣相加的算法，其結(jié)果存放在三元組表C中。

6.用數(shù)組結(jié)構(gòu)存儲一元多項式，編寫算法求解兩個一元多項式相加結(jié)果。實訓(xùn)指導(dǎo)

一、串的應(yīng)用——簡單文本編輯

【實訓(xùn)目的】

(1)熟練掌握串的結(jié)構(gòu)以及這種數(shù)據(jù)結(jié)構(gòu)的特點；

(2)能夠在三種存儲結(jié)構(gòu)上實現(xiàn)串的基本運算。

【實訓(xùn)內(nèi)容】通過菜單完成文本編輯的基本功能。文本編輯程序用于源程序的輸入和修改，公文書信、報刊和書籍的編輯排版等。常用的文本編輯程序有Word、WPS等。文本編輯的實質(zhì)是修改字符數(shù)據(jù)的形式和格式。雖然各個文本編輯程序的功能強弱不同，但基本操作是一樣的，都包括串的查找、插入和刪除等操作。

【實現(xiàn)提示】一個簡單的文本編輯操作演示程序包括字符串的部分基本運算：賦值、比較、連接、插入、刪除和清除運算。字符串采用動態(tài)存儲結(jié)構(gòu)(即堆分配)存儲。【實現(xiàn)過程】#defineNULL0typedefstruct{char*ch;intlen;}hstring;intstrassign(hstring*s,char*chars){inti=0,slen;while(chars[i]!='\0')i++;slen=i;if(slen){s->ch=(char*)malloc(slen*sizeof(char));if(s->ch==NULL)return(0);for(i=0;i<=slen;i++)s->ch[i]=chars[i];}elses->ch=NULL;s->len=slen;return(1);}intstrcompare(hstrings,hstringt){inti;for(i=0;i<s.len&&i<t.len;i++)if(s.ch[i]==t.ch[i]);elseif(s.ch[i]>t.ch[i])return(1);elsereturn(-1);return(0);}strcat(hstring*s,hstringt) //參見算法4-4strinsert(hstring*s,intpos,hstringt) //參見算法4-3strdelete(hstring*s,intpos,intlen){inti;char*temp;if(pos<0||pos>s->len-len)return(0);if(len){temp=(char*)malloc((s->len-len)*sizeof(char));if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];

for(i=pos;i<=s->len-len;i++)temp[i]=s->ch[i+len];

s->len-=len;s->ch=temp;

return(1);}}intclearstring(hstring*s){if(s->ch){s->ch=NULL;s->len=0;}return(0);}main(){intinp,flag=1;char*s,*t;hstrings1,s2,*res;

intpos,len,ret;printf("1:strassing\n");

printf("2:strcompare\n");printf("3:strcat\n");printf("4:strinsert\n");

printf("5:strdelete\n");printf("6:clearstring\n");printf("7:exit");printf("pleaseinput1--7\n\n");while(flag)

{scanf("%d",&inp);switch(inp){case1:{scanf("%s",s);ret=strassign(&s1,s);if(ret!=0)printf("thestringis:%s\n",s1.ch);elseprintf("error\n");break;}case2:{printf("s=");scanf("%s",s);strassign(&s1,s);

printf("t=");scanf("%s",t);strassign(&s2,t);ret=strcompare(s1,s2);switch(ret){ case0:printf("twostringsareequle\n");break; case1:printf("thefirststring>thesecondstring\n");break; case-1:printf("thefirststring<thesecondstring\n");break;} break;}case3:{printf("s=");scanf("%s",s);strassign(&s1,s);printf("t=");scanf("%s",t);strassign(&s2,t);strcat(&s1,s2);printf("s1cats2is:%s\n",s1);break;}

case4:{printf("s=");scanf("%s",s);strassign(&s1,s);printf("t=");scanf("%s,",t);strassign(&s2,t);printf("pos=");scanf("%d",&pos);strinsert(&s1,pos,s2);

printf("result:%s\n",s1);

break;}case5:{

printf("s=");scanf("%s,",s);strassign(&s1,s);printf("pos=");scanf("%d",&pos);printf("len=");scanf("%d",&len);

strdelete(&s1,pos,len);printf("result:%s\n",s1);

break;}case6:{printf("s=");scanf("%s",