




版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO/IEC 23090-7:2022/AMD1:2024 EN Information technology - Coded representation of immersive media - Part 7: Immersive media metadata - Amendment 1: Common metadata for imme
- 【正版授權(quán)】 ISO 7718-2:2025 EN Aircraft - Passenger doors interface requirements for connection of passenger boarding bridge or passenger transfer vehicle - Part 2: Upper deck doors
- 【正版授權(quán)】 ISO 16900-11:2025 EN Respiratory protective devices - Methods of test and test equipment - Part 11: Determination of field of vision
- 【正版授權(quán)】 IEC 81355-1:2024 EN/FR Industrial systems,installations and equipment and industrial products - Classification and designation of information - Part 1: Basic rules and clas
- 2025年集成電路代工廠商業(yè)秘密保護(hù)合同
- 2025年動(dòng)力調(diào)諧陀螺平臺(tái)項(xiàng)目建議書(shū)
- 提升學(xué)校藝術(shù)教育影響力的策略計(jì)劃
- 醫(yī)院宣傳工作總結(jié)與改進(jìn)方法計(jì)劃
- 班級(jí)傳統(tǒng)文化傳承活動(dòng)的計(jì)劃
- 營(yíng)養(yǎng)科膳食服務(wù)效果評(píng)估與改進(jìn)計(jì)劃
- 部編版一年級(jí)語(yǔ)文下冊(cè)語(yǔ)文園地五《單元拓展-字族文》教學(xué)設(shè)計(jì)
- 靜脈輸液法操作并發(fā)癥的預(yù)防及處理
- 牙外傷的遠(yuǎn)期并發(fā)癥監(jiān)測(cè)
- 2024年中國(guó)成人心肌炎臨床診斷與治療指南解讀課件
- 全國(guó)川教版信息技術(shù)八年級(jí)下冊(cè)第一單元第2節(jié)《制作創(chuàng)意掛件》信息技術(shù)教學(xué)設(shè)計(jì)
- DL-T-1846-2018變電站機(jī)器人巡檢系統(tǒng)驗(yàn)收規(guī)范
- 重大事故隱患判定標(biāo)準(zhǔn)與相關(guān)事故案例培訓(xùn)課件(建筑)
- 《我的寒假生活》
- 陜2018TJ 040建筑節(jié)能與結(jié)構(gòu)一體化 復(fù)合免拆保溫模板構(gòu)造圖集
- DZ/T 0430-2023 固體礦產(chǎn)資源儲(chǔ)量核實(shí)報(bào)告編寫(xiě)規(guī)范(正式版)
- (高清版)WST 442-2024 臨床實(shí)驗(yàn)室生物安全指南
評(píng)論
0/150
提交評(píng)論