數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案4_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案4_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案4_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案4_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案4_第5頁(yè)
已閱讀5頁(yè),還剩5頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第4章數(shù)組、字符串與廣義表

1.具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為數(shù)組?

數(shù)組可以看成是形如(index,value)的數(shù)據(jù)集合,其中,index

是元素的索引,表示數(shù)據(jù)的邏輯位置,任意兩個(gè)數(shù)據(jù)的index都不相

同;value表示數(shù)據(jù)元素的值。

2.設(shè)有二維數(shù)組a[5][6],每個(gè)元素占相鄰的8個(gè)字節(jié),存儲(chǔ)器按

字節(jié)編址,已知a的起始地址是1000,試計(jì)算:

(1)數(shù)組a的最后一個(gè)元素起始地址;

1000+(30-1)*8=1232。

(2)按行序優(yōu)先時(shí),元素a[3][5]的起始地址;

1000+(3*6+5)*8=1184

(3)按行列序優(yōu)先時(shí),元素a[4][3]的起始地址。

1000+(3*5+4)*8=1152

3.請(qǐng)簡(jiǎn)述數(shù)組和矩陣的關(guān)系。

矩陣是指縱橫排列的二維數(shù)據(jù)表格。在高級(jí)語(yǔ)言編程中,通常用

二維數(shù)組來(lái)描述一個(gè)矩陣,從而可以對(duì)矩陣中的元素進(jìn)行隨機(jī)存取。

但矩陣的索引通常從1而不是像數(shù)組那樣從0開(kāi)始,并且使用A(i,

j)而不是A[i,j]的形式來(lái)引用矩陣中的元素。

4.矩陣有哪些基本運(yùn)算?

矩陣的操作包括轉(zhuǎn)置'加法'減法和乘法等。

5.稀疏矩陣的特點(diǎn)是什么?為什么要對(duì)稀疏矩陣采用壓縮存儲(chǔ)

技術(shù)?

稀疏矩陣的特點(diǎn)是矩陣中非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣零元素個(gè)

數(shù)。

采用壓縮存儲(chǔ)技術(shù)主要是為了節(jié)省空間。

6.設(shè)A和B是稀疏矩陣,都以三元組作為存儲(chǔ)結(jié)構(gòu),請(qǐng)寫(xiě)出矩

陣相加的算法C=A+Bo

〃稀疏矩陣的三元組表示

#include<iostream>

usingnamespacestd;

#defineM50

#defineN50

#defineMaxSize20

typedefintElemType;

typedefstruct

(

intr;

intc;

ElemTyped;

}TupNode;

typedefstruct

introws;

intcols;

intnums;

TupNodedata[MaxSize];

}TSMatrix;

intA[M][N],B[M][N];

//建立三元組

voidCreateMat(intA[M][N],TSMatrix&t,introw,intcol)

(

inti,j;

t.rows=row;t.cols=col;t.nums=0;

for(i=0;i<M;i++)

(

for(j=0;j<N;j++)

(

if(A[i][j]!=O)

(

t.data[t.nums].r=i;t.data[t.nums].c=j;

t.data[t.nums].d=A[i][j];t.nums++;

)

)

〃矩陣相加

intMatAdd(TSMatrix&a,TSMatrix&b,TSMatrix&c)

(

inti=O,j=O,k=O;

ElemTypev;

if(a.rows!=b.rows||a.cols!=b.cols)return0;

c.rows=a.rows;c.cols=a.cols;

while(i<a.nums&&j<b.nums)

(

if(a.data[i].r==b.data[j].r)

|

if(a.data[i].c<b.data[j].c)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

elseif(a.data[i].c>b.data[j].c)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

)

else

(

v=a.data[i].d+b.data[j].d;

if(v!=O)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=v;

k++;

)

i++;j++;

)

)

elseif(a.data[i].r<b.data[j].r)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

else

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

}

)

if(i==a.nums)

while(j<b.nums)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

}

if(j==b.nums)

while(i<a.nums)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

c.nums=k;

return1;

)

//輸出三元組

voidDispMat(TSMatrixt)

(

inti;

if(t.nums<=0)

(

cout<<"此矩陣所有元素都為"<<endl;

return;

)

cout?t.rows?,\t'?t.cols?'\t'?t.nums?endl;

cout?"----------------"?endl;

for(i=0;i<t,nums;i++)

cout?t.data[i].r?'\t'?t.data[i].c?'\t'?t.data[i].d?endl?endl;

)

〃主函數(shù)

intmain()

introw,col,i,j;

TSMatrixa,b,c;

cout<<"請(qǐng)輸入矩陣的行'列數(shù):\n";

cin?row?col;

cout<<"請(qǐng)輸入矩陣A的元素:\n";

for(i=0;i<row;i++)

for(j=0;j<col;j++)

cin?A[i][j];

cout<<"請(qǐng)輸入矩陣B的元素:\n";

for(i=0;i<row;i++)

for(j=0;j<col;j++)

cin?B[i][j];

CreateMat(A,a,row,col);

CreateMat(B,b,row,col);

cout<<"矩陣A的三元組表示為:\n";

DispMat(a);

cout?"矩陣B的三元組表示為:\n";

DispMat(b);

if(MatAdd(a,b,c))

cout?"矩陣A、B相加后得到的三元組表示為:\n";

DispMat(c);

)

return0;

)

7.簡(jiǎn)述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。

字符串簡(jiǎn)稱串,它是一種以字符為元素的特殊線性表。字符串可

以看成是以字符為元素的一維數(shù)組。具體實(shí)現(xiàn)時(shí),在C/C++中的字符

串使用為字符型數(shù)組來(lái)表示。為了便于確定字符串的結(jié)尾,在字符型

數(shù)組中使用\0(就是0)作為字符串的截止符。

8.列舉一些需要進(jìn)行字符串模式匹配的應(yīng)用場(chǎng)景。

例如,在文本編輯中經(jīng)常要查找某一特定單詞或者一段話在整篇

文章中出現(xiàn)的位置,按照姓名查找某個(gè)學(xué)生'員工、居民。有效的模

式匹配能極大地提高文本編輯程序的能力。

9.列舉幾個(gè)字符串的其他操作。

求字符串中某個(gè)子串出現(xiàn)的次數(shù),刪除滿足條件的子串,字符串

字符移位等。

10.什么是廣義表?廣義表與線性表的區(qū)別是什么?

廣義表又稱列表,是由n(n>0)個(gè)元素組成的有窮序列:GL=(e,,

e2,……品),但與線性表不同的是,廣義表中的元素允許以不同的形

式出現(xiàn):它可以是一個(gè)原子(邏輯上不能再分解的元素),也可以是

另一個(gè)廣義表。

11.一^個(gè)廣義表是(a,(a,b,c),d,e,(m,n),(w,(i,j),x)),請(qǐng)問(wèn)該廣義

表的長(zhǎng)度、深度分別是多少?請(qǐng)畫(huà)出該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意

圖。

該廣義表的深度是3,長(zhǎng)度是6。

該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意圖如下:

head

~?tup

headuhead,1

.headv

|i|5|11IMN11LoJ^J

mvr^iLiMJGW

12.請(qǐng)列舉出一些可以歸納成數(shù)組、矩

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論