1.已知一個稀疏矩陣如下圖所示:
0 4 0 0 0 0 0
0 0 0 -3 0 0 1
8 0 0 0 0 0 0
0 0 0 5 0 0 0
0 -7 0 0 0 2 0
0 0 0 6 0 0 0
圖3-1 具有6行×7列的一個稀疏矩陣
⑴寫出它的三元組線性表；
解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6))
⑵給出它的順序存儲表示；
解：
下標(biāo) 1 2 3 4 5 6 7 8 ... MaxTerms row(行號) 1 2 2 3 4 5 5 6 col(列號) 2 4 7 1 4 2 6 4 val(元素值) 4 -3 1 8 5 -7 2 6
⑶給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示；
解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
⑷給出對它進行快速轉(zhuǎn)置時,num向量中各分量的值；
⑸給出對它進行快速轉(zhuǎn)置前和轉(zhuǎn)置后,pot向量中各分量的值。
解：
Col 1 2 3 4 5 6 7 Num[col] 1 2 0 3 0 1 1 pot[col](前) 1 2 4 4 7 7 8 pot[col](后) 2 4 4 7 7 8 9
2.采用順序存儲方式實現(xiàn)稀疏矩陣M1和M2相加的運算，運算結(jié)果由變量M返回。
解：
void Add(SMatrix& M1,SMatrix& M2,SMatrix& M)
//采用順序存儲方式實現(xiàn)稀疏矩陣M1和M2相加的運算，運算結(jié)果由變量M返回
{
InitMatrix(M);
//若兩個矩陣尺寸不同，則給出錯誤信息并停止運行
if ((M1.m!=M2.m)||(M1.n!=M2.n)){
cerr<<"tow matrix measurenents are different!"<<end1;
exit(1);
}
M.m=M1.m;M.n=M1.n;
//若兩個矩陣均為零矩陣，則無須計算
if(M1.t==0)&&(M2.t==0))
return;
int i=1,j=1; //用i，j 分別指示M1.smt M2.sm數(shù)組中待比較元素的下標(biāo),初值均
//為1
int k=1; //用k指示M.sm數(shù)組中待寫入元素的下標(biāo)，初值為1
while((i<=M1.t)&&(j<=M2.t))
{//把行號較小元素寫入到結(jié)果矩陣中,若行號相同進行列號的比較,使列號
//較小的元素寫入到結(jié)果矩陣中,若行、列號均相等，則當(dāng)相應(yīng)元素的
//和不為0時才把這個和寫入到結(jié)果矩陣中
if(M1.sm[i].row<M2.sm[j].row){
M.sm[k]=M1.sm[i];
i++;k++;
}
else
if(M1.sm[i].row>M2.sm[j].row){
M.sm[k]=M2.sm[j];
j++;k++;
}
else{
if(M1.sm[i].col<M2.sm[j].col){
M.sm[k]=M1.sm[i];
i++;k++;
}
else if(M1.sm[i].col>M2.sm[i].col{
M.sm[k]=M2.sm[j];
j++;k++;
}
else{//此時相應(yīng)元素的行列號必然相等
if(M.sm[i].val+M2.sm[j].val!=0){
M.sm[k].row=M1.sm[i].row;
M.sm[k].col=M1.sm[i].col;
M.sm[k].val=M1.sm[i].val+M2.sm[j].val;
k++;
}
i++;j++;
}
}
}
while(i<=M1.t)
{ //把M1中的剩余元素寫入到結(jié)果矩陣M中
M.sm[k]=M1.sm[i];
i++;k++;
}
while(j<=M2.t)
{ // 把M2中的剩余元素寫入到結(jié)果矩陣M中
M.sm[k]=M2.sm[j];
j++;k++;
}
M.t=k-1;//把寫入到結(jié)果矩陣M中元素的個數(shù)賦給M中保存元素個數(shù)的
//變量域
return;
}
3.畫出下列每個廣義表的帶表頭附加結(jié)點的鏈接存儲結(jié)構(gòu)圖并分別計算出它們的長度和深度。
⑴ A=(())
⑵ B=(a,b,c)
⑶ C=(a,(b,(c)))
⑷ D=((a,b),(c,d))
⑸ E=(a,(b,(c,d)),(e))
⑹ F=((a,(b,(),c),((d)),e)))
解：每小題的長度和深度如下表示。
題號 1 2 3 4 5 6 長度 1 3 2 2 3 1 深度 2 1 3 2 3 4
4.編寫一個建立廣義表鏈接存儲結(jié)構(gòu)的算法，假定廣義表由字符串值提供。
解：
void Create(GLNode*&GL,char*a)
//根據(jù)在字符串a(chǎn)中保存的廣義表生成其對應(yīng)的存儲結(jié)構(gòu)
{
static int i=0;//定義靜態(tài)變量i指示a中待處理的字符串位置，每處理一
//個字符后i值增1
if(a[i]=='\0')
return; //當(dāng)字符串處理結(jié)束后返回
if(a[i]=='#'){
GL=NULL;
i++;
}
else if(a[i]=='('){
GL=new GLNode;
GL->tag=True;
i++;
Create(GL->sublist,a);
}
if(GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
else{
GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
if(GL==NULL) //此時的a[i]必然為')'字符
i++;
else if(a[i]==','){
i++;
Create(GL->next,a);
}
else if((a[i]==')')||(a[i]==',')){
i++;
GL->next=NULL;
}
}
5.編寫一個廣義表中查找元素字等于給定值的算法，若查找成功則返回數(shù)值1，
否則返回數(shù)值0。
解：
int Find(GLNode*GL,char ch)
//從廣義表GL中查找單元素字符等于ch的算法，若查找成功，則返回數(shù)值1，
//否則返回數(shù)值0
{
while(GL!=NULL){
if(GL->tag==0){//處理單元素結(jié)點
if(GL->data==ch)
return 1;//查找成功返回1
else
GL=GL->next; //否則繼續(xù)向后查找
}
else{//處理子表結(jié)點
int x=Find(GL->sublist,ch);//向子表中繼續(xù)查找
if(x)//若在子表中查找成功則返回1，否則繼續(xù)向后查找
return 1;
else
GL=GL->next;
}
}
return 0； //當(dāng)查找到表為空時返回0
}
