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))
⑵給出它的順序存儲表示；
解：
下標 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
⑶給出它的轉置矩陣的三元組線性表和順序存儲表示；
解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
⑷給出對它進行快速轉置時,num向量中各分量的值；
⑸給出對它進行快速轉置前和轉置后,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相加的運算，運算結果由變量M返回。
解：
void Add(SMatrix& M1,SMatrix& M2,SMatrix& M)
//采用順序存儲方式實現(xiàn)稀疏矩陣M1和M2相加的運算，運算結果由變量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ù)組中待比較元素的下標,初值均
//為1
int k=1; //用k指示M.sm數(shù)組中待寫入元素的下標，初值為1
while((i<=M1.t)&&(j<=M2.t))
{//把行號較小元素寫入到結果矩陣中,若行號相同進行列號的比較,使列號
//較小的元素寫入到結果矩陣中,若行、列號均相等，則當相應元素的
//和不為0時才把這個和寫入到結果矩陣中
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{//此時相應元素的行列號必然相等
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中的剩余元素寫入到結果矩陣M中
M.sm[k]=M1.sm[i];
i++;k++;
}
while(j<=M2.t)
{ // 把M2中的剩余元素寫入到結果矩陣M中
M.sm[k]=M2.sm[j];
j++;k++;
}
M.t=k-1;//把寫入到結果矩陣M中元素的個數(shù)賦給M中保存元素個數(shù)的
//變量域
return;
}
3.畫出下列每個廣義表的帶表頭附加結點的鏈接存儲結構圖并分別計算出它們的長度和深度。
⑴ 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.編寫一個建立廣義表鏈接存儲結構的算法，假定廣義表由字符串值提供。
解：
void Create(GLNode*&GL,char*a)
//根據(jù)在字符串a中保存的廣義表生成其對應的存儲結構
{
static int i=0;//定義靜態(tài)變量i指示a中待處理的字符串位置，每處理一
//個字符后i值增1
if(a[i]=='\0')
return; //當字符串處理結束后返回
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){//處理單元素結點
if(GL->data==ch)
return 1;//查找成功返回1
else
GL=GL->next; //否則繼續(xù)向后查找
}
else{//處理子表結點
int x=Find(GL->sublist,ch);//向子表中繼續(xù)查找
if(x)//若在子表中查找成功則返回1，否則繼續(xù)向后查找
return 1;
else
GL=GL->next;
}
}
return 0； //當查找到表為空時返回0
}
