軟件技術(shù)基礎(chǔ)11大為第

串及其運算串的存儲結(jié)構(gòu)串的模式匹配算法多維數(shù)組矩陣的壓縮存儲習題55.1.1

串的概念串(String)是由多個或零個字符組成的有限序列，記做S="c1c2c3…cn"(n≥0)。其中，S是串名；由雙引號括起來的字符序列稱為串值，但雙引號本身不屬于串；ci(1≤i≤n)是串中字符，i是字符在串中的位置序號；n是串的長度，表示串中字符的個數(shù)，不包含任何字符的串稱為空串，例如""是長度為0的空串。5.1

串及其運算串中任意個連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應地稱為主串。子串在主串中的序號定義為子串在主串中首次出現(xiàn)的位置序號。例如，設(shè)S1和S2分別為S1=“This

is

a

string”

S2=“is”則S2是S1的子串，S1是S2的主串。S2在S1中出現(xiàn)了兩次，首次出現(xiàn)在主串的第3個位置上，因此S2在S1中的序號是3。特別需要一提的是，空串是任意串的子串，任意串是其自身的子串。通常，串可以分為串變量和串常量。正如我們所知道的，在程序中常量只能被引用而不能改變其值，但變量的值可以被改變。在C++語言中，串變量可以用字符型數(shù)組來表示，串常量可以用雙引號括起來的字符序列直接表示或者用符號常量來表示，例如有如下定義：char

str[]="string"; const

char

str_const[]="string";str是串變量，而str_const是串符號常量。5.1.2

串的基本運算串的基本運算和線性表有很大的差別。線性表的插入、刪除等運算都是以“單個元素”作為操作對象；而對串的運算，通常是把串作為一個整體進行操作，如串的復制、串的比較、插入和刪除子串等。很多高級語言都提供了字符串操作的函數(shù)庫，下面結(jié)合串的基本運算給出C語言有關(guān)字符串操作函數(shù)的例子。我們先定義幾個相關(guān)的變量：char

s1[80]=“d:\\user\\wang\\”,

s2[40]=“file.txt”,

s3[80];//字符串中含有轉(zhuǎn)義字符‘\\‘int

result;說明：字符串從字符數(shù)組下標為0的元素開始存放。StrLen(S)——求串長度，返回字符串長度。例如：printf("%d",strlen(s1));

//輸出

13StrCpy(&T,

S)——復制串，將源串復制給目標串。例如：strcpy(s3,s1); //s3

的值為"d:\\user\\wang\\"StrCmp(S1,S2)——比較串，比較兩個串的大小，返回整型值。>

0 S1

>

S2S1

<

S2<

0 S1

<

S2StrCmp(S1,S2)返回值==0例如：result=strcmp(“good”,“Good”);//result>0result=strcmp(“15”,“15”);result=strcmp(“That”,“The”);//result=0//result<0StrCat(&T,S)——串聯(lián)接，將串S聯(lián)接到串T的末尾，返回指向串S的指針。例如：printf(“%s”,strcat(s1,s2));//輸出：d:\\user\\wang\\file.txtStrStr(S,Sub)——子串定位，查找串Sub在串S中第一次出現(xiàn)的位置，若查找到，則返回該位置信息，否則返回NULL。例如：printf("%d\n",strstr(s1,"user")-s1+1);

//輸出4(6)

StrChr(S,C)——字符定位，查找字符C在串S中第一次

出現(xiàn)的位置，若查找到，則返回該位置信息，否則返回NULL。例如：result=strchr(s2,‘t’)-s2+1;

//result的值是6上述操作是最基本的串運算，其余的串運算一般可以由這些基本運算組合而成?！纠?.1】取子串運算。取主串中start

起始的length

個字符作為子串。#include<string.h>#include<stdio.h>void

substr(char*,char*,int,int);//字符串中含有轉(zhuǎn)義字符'\\'//輸入起始位置和長度void

main(

){char

s1[

]="d:\\user\\wang\\",s2[80];int

start,length;printf("start,length=");scanf("%d,%d",&start,&length);substr(s2,s1,start,length);puts(s2);}void

substr(char*sub,

char*s,int

pos,int

len){if(pos<1||pos>strlen(s)||len<0)

printf(“parameter

error!\n”);else{//復制子串字符//添加子串的串結(jié)束符strncpy(sub,s+pos-1,len);strcpy(sub+len,“\0”);}}上述程序是C語言的完整程序。不同的語言對串運算會有差異，因此應以該語言的參考手冊為準。5.2.1

串的順序存儲串的順序存儲結(jié)構(gòu)簡稱為順序串。與順序表類似，順序串是用字符向量來存儲，并且在串的末尾用一個特定的字符作為串結(jié)束符，例如C語言中以轉(zhuǎn)義字符‘\0’作為串結(jié)束符。為了具有一般性，我們?nèi)匀话汛念愋投x為一個結(jié)構(gòu)類型，其中用一個一維字符型數(shù)組存放串值，并用一個整型量表示串的長度。串的類型定義如下：#define

maxsize

256typedef

struct{ char

ch[maxsize];int

length;}SeqString;5.2

串的存儲結(jié)構(gòu)【例5.2】編寫一個算法void

strdelete(SeqString*S,intpos,int

len)，若滿足1≤pos≤S->length-len+1，則從串S中刪除第

pos個字符開始長度為len的子串；否則不刪除。void

strdelete(SeqString*S,int

pos,intlen){char

temp[maxsize];if(pos>=1&&pos<=S->length-len+1){strncpy(temp,S->ch,pos-1);strcpy(temp+pos-1,S->ch+pos+len-1);strcpy(S->str,temp);S->length=S->length-len;}}5.2.2

串的鏈式存儲和順序表類似，在順序串上不方便進行插入、刪除操作，需要移動大量的元素。采用鏈表存儲串值可以提高插入、刪除的效率，串的鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串中的每個結(jié)點可以存放一個字符，若結(jié)點的指針域占4個字節(jié)，那么鏈串的存儲密度只有20%。如果每個結(jié)點存放多個字符，例如4個字符，則存儲密度可以達到50%，從而有效地提高了存儲空間的利用率。通常將每個結(jié)點存放字符的個數(shù)定義為結(jié)點大小，圖5.1(a)和(b)中的每個結(jié)點大小分別是1和4。一個結(jié)點可存放多個字符，而串長度不一定是結(jié)點大小的倍數(shù)，因此鏈表中最后一個結(jié)點的數(shù)據(jù)域有可能沒有被串值占滿，可以用特殊的字符(例如'\0')來填充。圖5.1

鏈串的示意圖鏈串結(jié)點的類型定義如下：結(jié)點大小為1。typedef

struct

node{ char

data;struct

node*next;}LinkString;結(jié)點大小為4。typedef

struct

node{ char

data[4];struct

node*next;}LinkString;子串定位又稱為串的模式匹配(PatternMatching)，是串運算中最重要的操作之一。所謂模式匹配，就是在文本中查找是否存在給定的單詞及出現(xiàn)的位置，例如實現(xiàn)文本編輯程序中的查找功能。C語言函數(shù)庫中的子串定位函數(shù)strstr可以實現(xiàn)串的模式匹配操作，串的模式匹配算法分樸素的模式匹配和改進的模式匹配兩種。5.3

串的模式匹配算法5.3.1

順序串上的模式匹配樸素的模式匹配算法又稱為窮舉的模式匹配算法，假設(shè)S為目標串(主串)，T為模式串(子串)，S="s1,s2,…,sn"

T="t1,t2,…,tm"

其中0＜m≤n在實際應用中，模式串長度m通常遠遠小于目標串長度n，即m<<n。下面給出不依賴其他串操作運算的模式匹配算法。算法

5.1

順序串的模式匹配。int

Index(seqstring*S,

seqstring*T,int

pos)//順序串的樸素模式匹配，串的位序從1

開始{

i=pos;

j=1;

//

目標串從第pos個字符開始與模式串的第一個字符開始進行比較while(i<=S->length&&j<=T->length)if(S->ch[i-1]==T->ch[j-1])//串從向量的0

元素開始存放{ i++;

j++;}//繼續(xù)比較后面的字符

else{

i=i-j+2;j=1;

}

//本趟不匹配，設(shè)置下一趟匹配的起始位序if(j>T->length)

return(i-T->length);

//匹配成功else return(0);//匹配不成功}分別利用計數(shù)指針i和j指示目標串S和模式串T中當前比較

的字符位序。算法的基本思想是：從目標串S的第pos個字符開

始與模式串T的第一個字符進行比較，若相等，則繼續(xù)比較后

面的字符；否則，從目標串的下一個字符開始與模式串的第一

個字符進行下一趟比較。重復此過程，直至模式串中的每個字

符依次與目標串中的一個連續(xù)的字符序列相等，則匹配成功，

函數(shù)值為與模式串中第一個字符相等的字符在目標串中的位序；如果各趟比較均不相等，則匹配不成功，函數(shù)值為0。從圖5.2

可以看出模式串T="abc"與目標串S="abbabca"的匹配過程

(pos=1)。圖5.2

樸素的模式匹配過程現(xiàn)在分析算法的時間復雜度。在最壞情況下，假設(shè)每一趟都比較了m次才能夠確定對應的字符是否均相等，共匹配了n-

m+1趟，比較字符的總次數(shù)為m(n-m+1)，由于n>>m，因此時間復雜度是O(m*n)。樸素的模式匹配算法雖簡單，但效率較低，這是因為在一趟匹配中目標串內(nèi)可能存在多個和模式串“部分匹配”的子串，而引起計數(shù)指針i的多次回溯。一種改進的模式匹配算法的時間復雜度為O(m+n)。其改進在于：每當一趟過程中出現(xiàn)字符比較不等時，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動”盡可能遠的距離，再繼續(xù)進行比較。具體算法讀者可參閱有關(guān)資料。5.3.2

鏈串上的模式匹配我們以結(jié)點大小為1的單鏈表存儲串，實現(xiàn)樸素的模式匹配算法。在算法中使用指針shift指向每一趟在目標串中比較的起始位置，若一趟比較中出現(xiàn)不相等的字符，指針shift右移指向下一個結(jié)點，繼續(xù)下一趟的比較。若匹配成功，則返回shift所指向的結(jié)點地址；若匹配不成功，則返回空地址值。具體算法如下：算法

5.2

鏈串的模式匹配。LinkString*Index(LinkString*S,LinkString*T,LinkString*pos)//從pos所指示的位置開始查找模式串T在目標串S中首次出現(xiàn)的位置{LinkString*shift,*sp,*tp;shift=pos;sp=shift;

tp=T;while(sp!=NULL&&tp!=NULL){if(sp->data==tp->data){//繼續(xù)比較后續(xù)結(jié)點中的字符

sp=sp->next;tp=tp->next;}else{//本趟匹配不成功，設(shè)置下一趟匹配的起始位置

shift=shift->next;sp=shift;

tp=T;}}if(tp==NULL)return

shift;//匹配成功

else

NULL;//匹配不成功}5.4

多維數(shù)組數(shù)組是一種常用的結(jié)構(gòu)類型。數(shù)組中的各元素具有相同的類型，數(shù)組元素具有值和確定元素位置的下標。通常可以把一維數(shù)組稱為向量，多維數(shù)組是向量的擴充。例如二維數(shù)組a

mn

a

2n

a1n

Amn

=

a

21

a11

a12a

22

a

m1

a

m2

可以看成由m個行向量組成，每個行向量中含有n

個元素；也可以看做具有n

個列向量，每個列向量中含有m

個元素。即Amn

=

{{a11

,

a12

,,

a1n

},{a

21

,

a

22

,,

a

2n

},,{a

m1

,

a

m2

,,

a

mn

}}或Amn

={{a11

,

a

21

,,

a

m1},{a12

,

a

22

,,

a

m2

},,{a1n

,

a

2n

,,

a

mn

}}一維數(shù)組中的每個元素ai

屬于一個向量，二維數(shù)組中的每個元素aij

屬于兩個向量。一維數(shù)組是線性結(jié)構(gòu)，而二維數(shù)組不應看做線性結(jié)構(gòu)，因為二維數(shù)組元素可能有多個直接前趨和多個直接后繼。三維數(shù)組以及多維數(shù)組的概念與二維數(shù)組類似。在計算機中一般采用順序存儲結(jié)構(gòu)來存放數(shù)組。而內(nèi)存結(jié)構(gòu)是一維的，因此存放二維數(shù)組或多維數(shù)組時，就必須按照某種順序?qū)?shù)組中的元素形成一個線性序列，然后將這個線性序列存放在內(nèi)存中。下面討論二維數(shù)組的存儲方式。(1)行優(yōu)先順序存儲：將數(shù)組元素按行向量的順序存儲，即第i+1

行的元素存放在第i

行的元素之后。元素存儲的線性序列為a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn(2)列優(yōu)先順序存儲：將數(shù)組元素按列向量的順序存儲，即第j+1

列的元素存放在第j

列的元素之后。元素存儲的線性序列為a11,a21,…,am1,a12,a22,…am2,…,a1n,a2n,…,amn在多數(shù)計算機語言中，二維數(shù)組都是按行優(yōu)先順序存儲的，少數(shù)語言采用按列優(yōu)先順序存儲。按照二維數(shù)組的上述兩種存儲的線性序列，在已知數(shù)組存儲的起始地址，下標的上、下界，以及每個數(shù)組元素所占用的存儲單元個數(shù)，就可以計算出元素aij

的存儲地址，從而對數(shù)組元素隨機存取。例如，二維數(shù)組A[c1..d1,c2..d2]按行優(yōu)先的順序存儲在內(nèi)存中，假設(shè)每個元素占d

個存儲單元，計算元素aij

的地址公式為Loc(aij)=Loc(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d

(5-1)其中Loc(ac1c2)是數(shù)組的起始地址，元素aij

前面的i-c1

行中共有

(i-c1)×(d2-c2+1)個元素，第i行上元素aij前面又有j-c2

個元素。類似的，我們可以得出二維數(shù)組A[c1..d1,c2..d2]按列優(yōu)先的順序存儲在內(nèi)存中，元素aij

的地址計算公式為Loc(aij)=Loc(ac1c2)+[(j-c2)×(d1-c1+1)+i-c1]×d

(5-2)【例

5.3】

假設(shè)二維數(shù)組按行優(yōu)先的順序存儲，分別計算數(shù)組

A[1..m,1..n]

和

A[0..m-

1,0..n-

1]

中元素

a

ij

的地址。行下標的下界是1，上界是m；列下標的下界是1，上界是n。元素aij的地址是Loc(aij)=Loc(a11)+[(i-1)×n+j-1]×d行下標的下界是0，上界是m-1；列下標的下界是0，上界是n-1。元素aij的地址是：Loc(aij)=Loc(a00)+(i×n+j)×d矩陣廣泛用于科學計算與工程應用中，在用高級語言編寫

程序時，常常采用二維數(shù)組存儲矩陣。采用這種存儲方法時，

不僅使矩陣運算簡單，而且存儲密度高。但是，如果階數(shù)很高

的矩陣中非零元素的分布具有一定的規(guī)律或者矩陣中有大量的

零元素，則為了節(jié)省存儲空間，可以對這類矩陣進行壓縮存儲。所謂壓縮存儲，就是為多個值相同的元素只分配一個存儲空間，零元素不分配存儲空間。5.5

矩陣的壓縮存儲5.5.1

特殊矩陣特殊矩陣是指n階方陣中非零元素或零元素的分布具有一定的規(guī)律。下面我們討論幾種特殊矩陣的壓縮存儲。1．三角矩陣在n階方陣中，以主對角線劃分，如果矩陣的下三角(不包括主對角線)中的元素均為值相同的常數(shù)，則稱為上三角矩陣，反之稱為下三角矩陣。在多數(shù)情況下，三角矩陣的常數(shù)為零。兩種三角矩陣如圖5.3所示。圖5.3

三角矩陣

2n(n

+1)2可以用向量A[0..n(n+1)/2]壓縮存儲三角矩陣，其中

A[0]~A[n(n+1)/2-1]存儲矩陣的下(上)三角中的元素，向量的最后一個分量A[n(n+1)/2]存儲三角矩陣中的常數(shù)。下三角矩陣按行優(yōu)先的順序存儲，A[k]與aij

的對應關(guān)系是：i(i

-1)

+

j

-1k

=(5-3)當i≥j當i＜j

2n(n

+1)2上三角矩陣按列優(yōu)先的順序存儲，A[k]與aij

的對應關(guān)系是：

j(j

-1)

+i

-1k

=(5-4)當i≤j當i＞j2．對稱矩陣若n階方陣A中的元素關(guān)于主對角線對稱，即滿足下述性質(zhì)：aij=aji1≤i，j≤n則稱

A

為對稱矩陣。如果采用一維數(shù)組存儲矩陣中的上三角或下三角元素，使對稱的兩個元素共享同一個存儲空間，則可以節(jié)省近一半的存儲空間。存儲

n

階對稱方陣時，一維數(shù)組的長度為

n(n+1)/2。圖

5.4(a)給出了一個

4

階對稱方陣，圖

5.5

是其存儲形式。圖5.4

一個4階對稱方陣圖5.5

一個4階對稱方陣的壓縮存儲3．對角矩陣所謂對角矩陣，是指方陣中的所有非零元素集中在以主對角線為中心的帶狀區(qū)域內(nèi)，帶狀區(qū)域之外的元素值均為零。帶寬為3的對角矩陣又稱為三對角矩陣，如圖5.6所示。圖5.6

三對角矩陣顯然，當|i-j|>1

時，元素aij

為0。一般地，對于k

對角矩陣(k

為奇數(shù))，當|i-j|>(k-1)/2

時，元素aij

為0。n階三對角矩陣有3n-2個非零元素，采用向量A[0..3n-3]按行優(yōu)先的順序壓縮存儲三對角矩陣。每個非零元素與向量下標的對應關(guān)系是：A[2(i-1)+j-1]=aij

1≤i≤n，i-1≤j≤i+1

(5-5)上述各種特殊矩陣的非零元素的分布都具有一定的規(guī)律，采用向量壓縮存儲時，通過元素與向量的對應關(guān)系，仍然可以對矩陣中的元素進行隨機存取。5.5.2

稀疏矩陣設(shè)矩陣Amn

中有t

個非零元素，若t

遠遠小于矩陣元素的總數(shù)(即t<<m×n，1m

·

n≤0.05)，并且非零元素在矩陣中的分布沒有規(guī)律，則稱A

為稀疏矩陣。由于稀疏矩陣中的非零元素的分布沒有規(guī)律，因此在存儲非零元素的同時，還必須存儲非零元素的位置信息。通常采用兩種方法對稀疏矩陣進行壓縮存儲：順序存儲結(jié)構(gòu)的三元組表和鏈式存儲結(jié)構(gòu)的十字鏈表。下面只討論用三元組表實現(xiàn)對稀疏矩陣的壓縮存儲。將稀疏矩陣中的非零元素的行號、列號和元素值作為一個三元組(i，j，aij)，所有非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，則得到一個其結(jié)點均是三元組的線性表。我們將該線性表的順序存儲結(jié)構(gòu)稱為三元組表。在下面的討論中，三元組均以按行優(yōu)先的順序進行排列。在三元組表中除了要表示非零元素之外，還需表示矩陣的行數(shù)、列數(shù)及非零元素的總數(shù)。三元組表的結(jié)構(gòu)類型定義描述為//最大非零元素個數(shù)#define

MaxSize

1000typedef

int

datatype;typedefstruct{ inti,j;datatypev;}

Node;typedefstruct{ int

m,n,t;Node

data[MaxSize];}

spmatrix;//非零元素的行、列號//非零元素的元素值//三元組結(jié)構(gòu)類型//行數(shù),列數(shù),非零元素個數(shù)//存放三元組表的向量//稀疏矩陣的三元組表結(jié)構(gòu)類型設(shè)a為spmattrix型指針變量，圖5.7(a)所示的稀疏矩陣A的三元組表如圖5.7(b)所示。下面以矩陣的轉(zhuǎn)置為例，說明采用三元組表的形式存儲稀疏矩陣時，如何實現(xiàn)矩陣的運算。一個m×n的矩陣A，它的轉(zhuǎn)置矩陣B是一個n×m的矩陣，且A[i][j]=B[j][i]，0≤i≤m-1，0≤j≤n，即A的行是B的列，A的列

是B的行。例如，圖5.7(a)中的A和圖5.8(a)中的B互為轉(zhuǎn)置矩陣。圖5.7稀疏矩陣A和它的三元素表*a圖5.8

稀疏矩陣B和它的三元素表

*b為了敘述方便，下面將三元組表*a中的成員a->data簡稱為三元組表，因為相對于其它成員而言，它是主要的。將A轉(zhuǎn)置為B，就是將A的三元組表a->data置換為B的三元組表b->data，如果只是互換a->data中i和j的內(nèi)容，那么所得到的b->data是按列存放的矩陣B的三元組表，還必須重新排列b->data中各結(jié)點的順序。由于A的列是B的行，故按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->data必定是按行優(yōu)先的順序存放。算法的基本思想是：對a->data按列掃描n趟，在第col趟掃描中，找出所有列號等于col的那些三元組，將它們的行號、列號和元素值分別放入b->data的列號、行號和元素值中，即可得到B的按行優(yōu)先的壓縮存儲表示。以圖5.7和圖5.8為例，設(shè)col=0，則掃描a->data找到列號為0的三元組依次是(0，0，3)和(2，0，

2)，存入b->data后為(0，0，3)和(0，2，2)，恰好為B中第0行的兩個非零元素，只要依次取col=0，1，2，3，即可得到a->data的轉(zhuǎn)置矩陣b->data。下面給出具體的算法：算法

5.3

矩陣的轉(zhuǎn)置(用三元組表存儲矩陣)。void

TransMat(spmatrix

*a,spmayrix

*b)//

返回稀疏矩陣A

的轉(zhuǎn)置，ano

和bno

分別指示a→data

和b→data中結(jié)點序號//col

指示*a

的列號(即*b

的行號){ int

ano,bno,col;b->m=a->n; b->n=a->m;//A

和B

的行列數(shù)交換b->t=a->t;//非零元素個數(shù)if(b->t>0)

//

有非零元素，則轉(zhuǎn)置{

bno=0；for(col=0;col<a->n;col++)//按*a

的列序轉(zhuǎn)置，對a->data掃描n

趟for(ano=0;ano<a->t;

ano++)if(a->data[ano].j==col){//掃描一趟三元組表//

列號為col，則進行置換b->data[bno].i=a->data[ano].j;//a

的列號變?yōu)閎

的行號//a

的行號變?yōu)閎

的列號b->data[bno].j=a->data[ano].i;b->data[bno].v=a->data[ano].v;bno++;//b->data

結(jié)點序號加1}}}

//

TransMat該算法的時間主要耗費在col和ano的二重循環(huán)上，算法的時間復雜度為O(n×t)。而通常用二維數(shù)組表示矩陣時，其轉(zhuǎn)置算法的時間復雜度是O(m×n)。如果非零元素個數(shù)大于矩陣的行數(shù)，則從轉(zhuǎn)置算法的時間復雜度來說，采用三元組表存儲就不合適了。一、名詞解釋串，順序串，鏈串，特殊矩陣，稀疏矩陣，對稱方陣，上(下)三角矩陣二、填空題含零個字符的串稱為

串，用

表示。其他

串稱為

串。任何串中所含

的個數(shù)稱為該串的長度。當且僅當兩個串的

相等并且各個對應位置上的字符都

時，這兩個串相等。一個串中任意個連續(xù)字符組成的序列稱為該串的

串，該串稱為它所有子串的

串。習題5通常將鏈串中每個存儲結(jié)點所存儲的字符個數(shù)稱為。當結(jié)點大小大于1時，鏈串的最后一個結(jié)點的各個數(shù)據(jù)域不一定總能全被字符占滿，此時，應在這些未用的數(shù)據(jù)域里補上

。一般地，一個n維數(shù)組可視為其數(shù)據(jù)元素為

維數(shù)組的線性表。數(shù)組通常只有

和

兩種基本運算。通常采用

存儲結(jié)構(gòu)來存放數(shù)組。對二維數(shù)組可有兩種存儲方法：一種是以

為主序的存儲方式，另一種是以

為主序的存儲方式。C語言數(shù)組用的是以

序為主序的存儲方法。數(shù)組M中每個元素的長度是3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址EA開始連續(xù)存放在存儲器中。若按行方式存放，則元素M[8][5]的起始地址為

；若按列優(yōu)先方式存放，則元素M[8][5]的地址為

。二維數(shù)組M的成員是6個字符(每個字符占一個存儲單元)組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要

個字節(jié)；M的第8列和第5行共占

個字節(jié)；若M按行方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先方式存儲時的

元素的起始地址一致。需要壓縮存儲的矩陣可分為

矩陣和

矩陣兩種。對稱方陣中有近半的元素重復，若為每一對元素只分配一個存儲空間，則可將n2個元素壓縮存儲到

個元素的存儲空間中。假設(shè)以一維數(shù)組M(1..n(n+1)/2)作為n階對稱矩陣A的

存儲結(jié)構(gòu)，以行序為主序存儲其下三角(包括對角線)中的元素，數(shù)組M和矩陣A間對應的關(guān)系為

。11．上三角矩陣中，主對角線上的第t行(1≤t≤n)有

個元素，按行優(yōu)先順序在一維數(shù)組M中存放上三角矩陣中的元素aij時，aij之前的前i-1行共有

個元素，在第i行上，aij是該行的第

個元素，M[k]和aij的對應關(guān)系是

。當i>j時，aij=c(c表示常量)，c存放在M[

]中。三、選擇題1．在串的基本運算中，能夠改變串值的運算有(

)。A.

EQAL(S,T)

B.

LENGTH(S)C.CONCAT(S,T)D.REPLACE(S,T,R)E.INDEX(S,T)2．在串的基本運算中，不能夠改變串值的運算有(

)。B.

INSERT(S1,i,S2)D.

SUBSTR(S,i,j)A.

ASSIGN(S,T)C.

DELETE(S,i,j)E.

REPLACE(S,T,R)對于以行序為主序的存儲結(jié)構(gòu)來說，在數(shù)組A[c1..d1，c2..d2]中，c1和d1分別為數(shù)組A的第一個下標的下界和上界，c2和d2分別為第二個下標的下界和上界，每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由(

)式確定。Loc(i,j)=

Loc(c1,

c2)+[(i-c1)*(d2-c2)

+

(j-c2)]*kLoc(i,j)=Loc(c1,

c2)+[(i-c1)*(d2-c2+1)

+

(j-c2)]*kLoc(i,j)=Loc(c1,

c2)+[(j-c2)*(d1-c1+1)

+

(i-c1)]*kLoc(i,j)=

Loc(c1,

c2)+[(j-c2)*(d1-c1)

+

(i-c1)]*k對于C語言的二維數(shù)組DataTypeA[m][n],每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組中任意元素a[i,j]的存儲位置可由(

)式確定。Loc(i,j)=Loc(0,0)+[

i*(n+1)

+j]*kLoc(i,j)=Loc(0,0)+[

j*(m+1)

+i]*kLoc(i,j)=Loc(0,0)+(i*n

+j)*kLoc(i,j)=Loc(0,0)+(

j*m

+i)*k5．稀疏矩陣的壓縮存儲方法是只存儲(

)。A.

非零元素

B.

三元組(i,j,

aij)C.

aij

D. i,

j6．基于三元組表的稀