4.1串

4.2數(shù)組

小結(jié)

習(xí)題

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

第4章串與數(shù)組

問題引入

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

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

知識(shí)要點(diǎn)

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

(2)串運(yùn)算的實(shí)現(xiàn)；

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

能力要求

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

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

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

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

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

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

A="Thisisastring."

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

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

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

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

(4)求子串：已知串s，返回從串s的第i個(gè)字符開始的長(zhǎng)度為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個(gè)字符位置上。

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

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

(10)撤銷串：已知串s，撤銷串s。以上是串的一些基本操作。其中前5個(gè)操作是最為基本的，它們不能用其它的操作來合成，因此通常將這5個(gè)基本操作稱為最小操作集，反之，其它操作可在這個(gè)最小操作集上實(shí)現(xiàn)。4.1.2串的存儲(chǔ)結(jié)構(gòu)因?yàn)榇菙?shù)據(jù)元素類型為字符型的線性表，所以線性表的存儲(chǔ)方式仍適用于串。也因?yàn)樽址奶厥庑院妥址?jīng)常作為一個(gè)整體來處理的特點(diǎn)，所以串在存儲(chǔ)時(shí)還有一些與一般線性表不同之處。

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

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

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

順序串。

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

typedefstruct

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

intlen;

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

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

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

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

堆串。

typedefstruct

{intlength;

intstart;

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

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

typedefstruct

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

intlen;

}hstring;

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

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

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

typedefstructnode

{charch;

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

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

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

#definenodesize80

typedefstructnode

{chardata[nodesize];

structnode*next;

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

算法4-1

求子串(采用靜態(tài)存儲(chǔ)順序串)。采用靜態(tài)存儲(chǔ)順序串，在已知串s中求從pos開始的長(zhǎng)度為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);} //子串起始位置及長(zhǎng)度是否合適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

定位。串的定位運(yùn)算也稱為串的模式匹配，是一種重要的串運(yùn)算。設(shè)s和t是給定的兩個(gè)串，在主串s中找到等于子串t的過程稱為模式匹配，如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲(chǔ)位置(或序號(hào))，否則匹配失敗，返回-1。t也稱為模式。算法思想如下：首先將s0與t0進(jìn)行比較，若不同，就將s1與t0進(jìn)行比較，…，直到s的某一個(gè)字符si和t0相同，再將它們之后的字符進(jìn)行比較，若也相同，則如此繼續(xù)往下比較，當(dāng)s的某一個(gè)字符si與t的字符tj不同時(shí)，則s返回到本趟開始字符的下一個(gè)字符，即si-j+1，t返回到t0，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若t中的字符全部比較完，則說明本趟匹配成功，本趟的起始位置是i-j，否則，匹配失敗。設(shè)主串s="ababcabcacbab"，模式t="abcac"，匹配過程如圖4-6所示。采用靜態(tài)存儲(chǔ)順序串，算法描述如下：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);

//匹配成功，返回存儲(chǔ)位置

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

算法4-3

插入。采用動(dòng)態(tài)存儲(chǔ)串，在已知串s的第pos個(gè)字符之前插入串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)); //臨時(shí)變量，用來暫存插入后的結(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

連接。采用動(dòng)態(tài)存儲(chǔ)串，將串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

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

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

{lstring*loc,*p,*q;

loc=s;

p=loc;q=t;

while(p&&q) //當(dāng)t、s串均未結(jié)束時(shí)

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

{p=p->next;

q=q->next;

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

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

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

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

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

a00，a01，…，a0，n-1

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

圖4-9三維數(shù)組的邏輯結(jié)構(gòu)三維數(shù)組元素的標(biāo)號(hào)由三個(gè)數(shù)字表示。如果對(duì)A3×4×2采用以行為主序的方式存放，則順序?yàn)閍000，a001，a010，a011，…，a220，a221，a230，a231采用以列為主序的方式存放，則順序?yàn)閍000，a100，a200，a010，…，a221，a031，a131，a231以上的存放規(guī)則可推廣到多維數(shù)組的情況?？傊?，知道了多維數(shù)組的維數(shù)以及每維的上下界，就可以方便地將多維數(shù)組按順序存儲(chǔ)結(jié)構(gòu)存放在計(jì)算機(jī)中了。同時(shí)，根據(jù)數(shù)組的下標(biāo)，可以計(jì)算出其在存儲(chǔ)器中的位置。因此，數(shù)組的順序存儲(chǔ)是一種隨機(jī)存取的結(jié)構(gòu)。下面，以“以行為主序”的分配為例，討論數(shù)組中數(shù)據(jù)元素存儲(chǔ)位置的計(jì)算。設(shè)有二維數(shù)組Am×n，下標(biāo)從0開始，假設(shè)每個(gè)數(shù)組元素占size個(gè)存儲(chǔ)單元，首元素a00的存儲(chǔ)地址為L(zhǎng)OC[0，0]。對(duì)任意元素aij來說，因?yàn)閍ij排在第i行，第j列，前面的i行有n?×?i個(gè)元素，第i行第j列個(gè)元素前面還有j個(gè)元素，所以可得aij的地址計(jì)算公式如下：LOC[i，j]=LOC[0，0]+(i×n+j)×?size同理，對(duì)三維數(shù)組Ar×m×n，可以看成是r個(gè)m?×?n的二維數(shù)組，若首元素的存儲(chǔ)地址為L(zhǎng)OC[0，0，0]，則元素ai11的存儲(chǔ)地址為L(zhǎng)OC[i，1，1]=LOC[0，0，0]+(i?×?m?×?n)?×?size，這是因?yàn)樵谠撛刂坝衖個(gè)m?×?n的二維數(shù)組。由ai11的地址和二維數(shù)組的地址計(jì)算公式，不難得到三維數(shù)組任意元素aijk的地址計(jì)算公式：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ù)組是各種高級(jí)語言中均已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。在高級(jí)語言的應(yīng)用層上，一般不會(huì)涉及到數(shù)據(jù)元素存儲(chǔ)地址的計(jì)算，這一計(jì)算內(nèi)存地址的任務(wù)是由高級(jí)語言的編譯系統(tǒng)完成的。當(dāng)我們使用數(shù)組進(jìn)行程序設(shè)計(jì)時(shí)，只需給出數(shù)組的下標(biāo)范圍，編譯系統(tǒng)將根據(jù)用戶提供的必要參數(shù)進(jìn)行地址分配，存取數(shù)據(jù)元素時(shí)，也只要給出下標(biāo)，而不必考慮其內(nèi)存情況。實(shí)例4-1若矩陣Am×n中存在某個(gè)元素aij且滿足aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫一個(gè)算法，找出A中的所有鞍點(diǎn)?；舅枷耄涸诰仃嘇中求出每一行的最小值元素，然后判斷該元素是否是它所在列中的最大值，是，則將其打印出來，接著處理下一行。矩陣A用一個(gè)二維數(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++) //檢測(cè)該行中的每一個(gè)最小值是否是鞍點(diǎn)

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特殊矩陣的壓縮存儲(chǔ)矩陣是科學(xué)計(jì)算、工程數(shù)學(xué)中大量研究的對(duì)象。對(duì)于一個(gè)矩陣結(jié)構(gòu)用一個(gè)二維數(shù)組來表示顯然是非常恰當(dāng)?shù)?。但在有些情況下，例如有些高階矩陣中，階次很高，數(shù)據(jù)量很大，而非零元素非常少(遠(yuǎn)小于m?×?n)，若仍采用二維數(shù)組存放，就會(huì)有很多存儲(chǔ)單元都存放的是0，這不僅造成存儲(chǔ)空間的浪費(fèi)，而且給運(yùn)算帶來了很大的不便，這時(shí)，就很希望能夠只存儲(chǔ)部分有效元素。另外，還有一些矩陣的數(shù)據(jù)元素分布有一定規(guī)律，如三角矩陣、對(duì)稱矩陣、帶狀矩陣等，那么就可以利用這些規(guī)律，只存儲(chǔ)部分元素，從而提高存儲(chǔ)空間的利用率。這些問題都需要對(duì)矩陣進(jìn)行壓縮存儲(chǔ)。一般的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間。我們?cè)谶@一節(jié)討論幾種特殊矩陣及對(duì)它們進(jìn)行壓縮存儲(chǔ)的方式。

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

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

所以可將三角矩陣壓縮到一個(gè)大小為n(n+1)/2的一維數(shù)組C中，如圖4-11所示。圖4-11三角矩陣的壓縮存儲(chǔ)假設(shè)每個(gè)數(shù)據(jù)元素占size個(gè)存儲(chǔ)單元，下三角矩陣中任意元素aij在一維數(shù)組C中的存儲(chǔ)位置可通過下式計(jì)算：Loc[i，j]=Loc[0，0]+(i(i+1)/2+j)×size(i≥j)也就是說，如果C中數(shù)據(jù)元素C[k]的下標(biāo)為k，則k與下三角矩陣中數(shù)據(jù)元素aij的下標(biāo)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。例如，對(duì)一個(gè)5?×?5的下三角矩陣A，可以用一維數(shù)組C[15]對(duì)其進(jìn)行壓縮存儲(chǔ)，如圖4-12所示。圖4-125?×?5的下三角矩陣的壓縮存儲(chǔ)同理，對(duì)上三角矩陣，只需存儲(chǔ)上三角的非零元素，對(duì)于零元素則不存儲(chǔ)，同樣可以將其壓縮存儲(chǔ)到一個(gè)大小為n(n+1)/2的一維數(shù)組中。若以“行序?yàn)橹餍颉边M(jìn)行存儲(chǔ)，得到的序列是a00，a01，a02，…，a0，n-1，a1，n-1，…，an-1，n-1其中，元素aij(i≤j)在數(shù)組C中的存儲(chǔ)位置為k=i(2n-i+1)/2+j-i(i≤j)

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

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

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

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

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

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

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

2)用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置矩陣的三元組存儲(chǔ)方法確實(shí)節(jié)約了存儲(chǔ)空間，但矩陣的運(yùn)算從算法上可能變得復(fù)雜些。下面以稀疏矩陣的轉(zhuǎn)置運(yùn)算為例介紹其實(shí)現(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)置矩陣仍為稀疏矩陣，所以可以采用三元組表實(shí)現(xiàn)矩陣的轉(zhuǎn)置。聲明兩個(gè)三元組變量：

tsmatrixA,B;

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

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

(2)將A.data中每一三元組的行列交換后存放到B.data中；并且保證B.data中的數(shù)據(jù)也是以“行序?yàn)橹餍颉边M(jìn)行存放(B.data中的行號(hào)即為A.data中的列號(hào))。要保證B.data中的數(shù)據(jù)也是以“行序?yàn)橹餍颉边M(jìn)行存放，可以有兩種方法，下面分別介紹。

算法4-6轉(zhuǎn)置方法一。這種方法的思路是按照A.data中的列序進(jìn)行轉(zhuǎn)置，并依次送入B.data中，即在A.data中依次找第一列的、第二列的，直到最后一列，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中即可，如圖4-17所示。圖4-17矩陣的轉(zhuǎn)置附設(shè)一個(gè)位置計(jì)數(shù)器j，用于指向當(dāng)前轉(zhuǎn)置后元素應(yīng)放入三元組表B.data中的位置。處理完一個(gè)元素后，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;

//稀疏矩陣的行、列、元素個(gè)數(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++)

//掃描整個(gè)三元組表

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++;

}

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

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

pos[1]=1；

pos[col]=pos[col-1]+num[col-1]；2≤col≤n例如對(duì)于圖4-17中矩陣A的num和pos的值如圖4-18所示。圖4-18矩陣A的num與pos值依次掃描A.data，當(dāng)掃描到一個(gè)col列元素時(shí)，直接將其存放在B.data的pos[col]位置上，pos[col]加1。pos[col]中始終是下一個(gè)col列元素在B.data中的位置。按以上思路改進(jìn)轉(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;

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

if(B->tu)

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

num[A.data[k].col]++;pos[1]=1; //矩陣A中每一列第一個(gè)非零元素在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;

//當(dāng)前三元組的列號(hào)

j=pos[col];

//當(dāng)前三元組在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]++;

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

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

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

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

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

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

習(xí)題

一、填空題

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

，它可以作為一個(gè)

參與所需要的運(yùn)算。

2．空白串是由

組成的串，空串是

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

3.字符串中任意多個(gè)

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

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

。

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

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

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

。

7.對(duì)稱矩陣的特點(diǎn)是

，下三角矩陣的特點(diǎn)是

，上三角矩陣的特點(diǎn)是

，稀疏矩陣的特點(diǎn)是

。

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

。二、選擇題

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

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

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

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

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

4.一個(gè)m×m的對(duì)稱矩陣，如果以行優(yōu)先的方式壓縮存儲(chǔ)，那么所需的存儲(chǔ)容量應(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中的每個(gè)元素占3個(gè)存儲(chǔ)單元，行下標(biāo)i的范圍是1..8，列下標(biāo)的范圍是1..10，M的首地址是M，那么該數(shù)組以行優(yōu)先存儲(chǔ)時(shí)，元素M[8][5]的起始地址應(yīng)該是()。

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

1．簡(jiǎn)述下列每對(duì)術(shù)語的區(qū)別：空串和空白串；串常量和串變量；主串和子串；靜態(tài)分配的順序串和動(dòng)態(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，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，已知A[0，0]的地址為1000，計(jì)算：

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

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

(3)按行存儲(chǔ)時(shí)元素a46的地址；

(4)按列存儲(chǔ)時(shí)元素a46的地址。

4.對(duì)上三角矩陣，將其壓縮存儲(chǔ)到一個(gè)一維數(shù)組C中。若以“行序?yàn)橹餍颉边M(jìn)行存儲(chǔ)，試求元素aij(i≤j)在數(shù)組C中的存儲(chǔ)位置。

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

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

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

3．以hstring為存儲(chǔ)表示，寫一個(gè)求子串的算法。

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

abcdefghijklmnopqrstuvwxyz

ngzqtcobmuhelkpdawxfyivrsj

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

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

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

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

【實(shí)訓(xùn)目的】

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

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

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

【實(shí)現(xiàn)提示】一個(gè)簡(jiǎn)單的文本編輯操作演示程序包括字符串的部分基本運(yùn)算：賦值、比較、連接、插入、刪除和清除運(yùn)算。字符串采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)(即堆分配)存儲(chǔ)。【實(shí)現(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",