?
我第一下拿到這個(gè)題目，第一反應(yīng)就是先定義好數(shù)據(jù)結(jié)構(gòu)，然后構(gòu)建好十字鏈表基礎(chǔ)操作的函數(shù)，也就是“創(chuàng)插遍歷”這些操作。下面是我的定義和函數(shù)操作。
typedef int ElemType;
typedef struct OLNode{
?? ?int i,j;//行號(hào)和列號(hào)
?? ?ElemType elem;
?? ?struct OLNode *right;//右邊元素?
?? ?struct OLNode *down;//下邊元素?
}OLNode,*OLink;typedef struct CrossList{
?? ?OLink* rHead;
?? ?OLink* cHead;
?? ?int mu,nu,tu;//行數(shù)、列數(shù)、非零元個(gè)數(shù)?
}CrossList;
CrossList* CreateOLSMatrix(int r,int c,int t){//創(chuàng)建目標(biāo)十字鏈表的表頭?
?? ?CrossList* p=(CrossList*)malloc(sizeof(CrossList));
?? ?if(p==NULL){
?? ??? ?printf("Out of space!");
?? ?}
?? ?p->mu=r;
?? ?p->nu=c;
?? ?p->tu=t;
?? ?p->rHead=(OLink*)malloc((r+1)*sizeof(OLink));
?? ?p->cHead=(OLink*)malloc((c+1)*sizeof(OLink));
?? ?if(p->rHead==NULL||p->cHead==NULL) printf("Out of space!\n");
?? ?for(int i=0;i<r+1;i++){
?? ??? ?p->rHead[i]=NULL;
?? ?}//強(qiáng)迫癥，初始化操作?
?? ?for(int i=0;i<c+1;i++){
?? ??? ?p->cHead[i]=NULL;
?? ?}//強(qiáng)迫癥，初始化操作?
?? ?return p;
}void InsertMatrix(CrossList* p,int i,int j,int elem){//插入數(shù)據(jù)
?? ?OLink p1=(OLink)malloc(sizeof(OLNode));
?? ?if(p1==NULL) printf("Out of space!\n");
?? ?p1->i=i;p1->j=j;p1->elem=elem;
?? ?//創(chuàng)建并填充結(jié)點(diǎn)
?? ?
?? ?if(p->rHead[i]==NULL||p->rHead[i]->j>j){
?? ??? ?p1->right=p->rHead[i];
?? ??? ?p->rHead[i]=p1;?
?? ?}else{
?? ??? ??? ?OLink q=p->rHead[i];
?? ??? ??? ?while(1){
?? ??? ??? ??? ?if(q->right==NULL||q->right->j>j) break;
?? ??? ??? ??? ?q=q->right;
?? ??? ??? ?}//找到插入位置
?? ??? ??? ?p1->right=q->right;
?? ??? ??? ?q->right=p1;
?? ??? ?}//完成行插入
?? ??? ?
?? ?if(p->cHead[j]==NULL||p->cHead[j]->i>i){
?? ??? ?p1->down=p->cHead[j];
?? ??? ?p->cHead[j]=p1;
?? ?}else{
?? ??? ??? ?OLink q=p->cHead[j];
?? ??? ??? ?while(1){
?? ??? ??? ??? ?if(q->down==NULL||q->down->i>i) break;
?? ??? ??? ??? ?q=q->down;
?? ??? ??? ?}//找到插入位置
?? ??? ??? ?p1->down=q->down;
?? ??? ??? ?q->down=p1;?
?? ??? ?}//完成列插入?
}int BuildMatrix(CrossList* p){//完善表
?? ?for(int k=1;k<=p->tu;k++){
?? ??? ?int i,j,elem;
?? ??? ?scanf("%d%d%d",&i,&j,&elem);
?? ??? ?InsertMatrix(p,i,j,elem);
?? ?}
}int OutputMatrix(CrossList* p){//輸出表
?? ?for(int i=1;i<=p->mu;i++){
?? ??? ?OLink q=p->rHead[i];
?? ??? ?for(int j=1;j<=p->nu;j++){
?? ??? ??? ?if(q!=NULL&&j==q->j){
?? ??? ??? ??? ?printf("%d %d %d\n",q->i,q->j,q->elem);
?? ??? ??? ??? ?q=q->right;
?? ??? ??? ?}
?? ??? ?}
?? ?}//按照先行后列的順序輸出?
}
其中插入數(shù)據(jù)這個(gè)函數(shù)有點(diǎn)難。
我們?cè)诓迦朐貢r(shí)，既要完成行插入，又要完成列插入。雖然這兩個(gè)步驟基本類似，但我還是建議大家不要看行插入步驟，獨(dú)立敲一遍列插入步驟。記住，不要著急，不要浮躁，靜下心來(lái)，不要害怕說(shuō)你同學(xué)就因此速度比你快，然后他就能做更多的練習(xí)，最后績(jī)點(diǎn)比你高，拿了獎(jiǎng)學(xué)金最后跟你炫耀，打擊挖苦你，嘲諷你。大學(xué)里面最可惡的不是不學(xué)習(xí)的人，而是那些”欻欻欻寫完作業(yè)，然后把你搞得浮躁，搞崩你的心態(tài)，最后嘲諷你不如他，還拿到了獎(jiǎng)學(xué)金”的人。（就和考理綜的時(shí)候，第一考場(chǎng)總有人來(lái)回翻卷子，就是為了搞崩你的心態(tài)）。不要慌，穩(wěn)下來(lái)，因?yàn)槟阋换牛麄兊哪康木瓦_(dá)到了。再回到這道題，如果你復(fù)制粘貼過(guò)來(lái)，很多東西你會(huì)忘記調(diào)整為列，而且Debug的時(shí)候，大家的第一反應(yīng)都是先關(guān)注行，所以忽視了列，如果列插入上出了問(wèn)題，是很難很難找出來(lái)錯(cuò)誤的，不信大家看我下面的例子：
if(p->cHead[j]==NULL||p->cHead[j]->i>i){
?? ??? ?p1->down=p->rHead[j];//1
?? ??? ?p->rHead[j]=p1;//2
?? ?}else{
?? ??? ??? ?OLink q=p->rHead[j];//3
?? ??? ??? ?while(1){
?? ??? ??? ??? ?if(q->down==NULL||q->down->i>i) break;
?? ??? ??? ??? ?q=q->down;
?? ??? ??? ?}//找到插入位置
?? ??? ??? ?p1->down=q->down;
?? ??? ??? ?q->down=p1;?
?? ??? ?}//完成列插入?
?上面3處就是我復(fù)制過(guò)來(lái)以后，忘記調(diào)整過(guò)來(lái)的地方，如果只輸出i=2這一行的第2個(gè)元素，結(jié)果是下面這樣，根本就不正確。
3 3 3
1 0 2
2 1 2
2 2 3--------------------------------
Process exited after 16.53 seconds with return value 3221225477
請(qǐng)按任意鍵繼續(xù). . .
正確的代碼應(yīng)該把這3處給改掉，像下面這樣：
if(p->cHead[j]==NULL||p->cHead[j]->i>i){
?? ??? ?p1->down=p->cHead[j];//1
?? ??? ?p->cHead[j]=p1;//2
?? ?}else{
?? ??? ??? ?OLink q=p->cHead[j];//3
?? ??? ??? ?while(1){
?? ??? ??? ??? ?if(q->down==NULL||q->down->i>i) break;
?? ??? ??? ??? ?q=q->down;
?? ??? ??? ?}//找到插入位置
?? ??? ??? ?p1->down=q->down;
?? ??? ??? ?q->down=p1;?
?? ??? ?}//完成列插入?
?最后，也就是咱們程序的核心：“矩陣相加”了：
int AddMatrix(CrossList* p1,CrossList* p2,CrossList* p3){//矩陣相加得到新矩陣p3?
?? ?for(int i=1;i<=p1->mu;i++){
?? ??? ?//先行后列，一點(diǎn)一點(diǎn)地來(lái)做?
?? ??? ?OLink temp1=p1->rHead[i];
?? ??? ?OLink temp2=p2->rHead[i];
?? ??? ?for(int j=1;j<=p1->nu;j++){
?? ??? ??? ?int flag1=temp1!=NULL&&j==temp1->j;
?? ??? ??? ?int flag2=temp2!=NULL&&j==temp2->j;
?? ??? ??? ?//為什么我要用flag呢？因?yàn)槎挤旁趇f后面的話，if會(huì)變的很長(zhǎng)很長(zhǎng)，超級(jí)麻煩?
?? ??? ??? ?if(flag1==1&&flag2!=1){//如果這個(gè)位置上,p1有數(shù)據(jù)，p2沒(méi)數(shù)據(jù)?
?? ??? ??? ??? ?InsertMatrix(p3,temp1->i,temp1->j,temp1->elem);
?? ??? ??? ??? ?temp1=temp1->right;
?? ??? ??? ?}
?? ??? ??? ?if(flag1!=1&&flag2==1){//如果這個(gè)位置上,p1沒(méi)數(shù)據(jù)，p2有數(shù)據(jù)?
?? ??? ??? ??? ?InsertMatrix(p3,temp2->i,temp2->j,temp2->elem);
?? ??? ??? ??? ?temp2=temp2->right;
?? ??? ??? ?}
?? ??? ??? ?if(flag1==1&&flag2==1){//如果這個(gè)位置上,p1有數(shù)據(jù)，p2也有數(shù)據(jù)?
?? ??? ??? ??? ?int total=temp1->elem+temp2->elem;
?? ??? ??? ??? ?if(total==0){
?? ??? ??? ??? ??? ?p3->tu=p3->tu-2;
?? ??? ??? ??? ??? ?//如果p1的數(shù)據(jù)與p2的數(shù)據(jù)相加為0，那就不用插入
?? ??? ??? ??? ??? ?//別忘了p3中非零元素要減2
?? ??? ??? ??? ?}else if(total!=0){
?? ??? ??? ??? ??? ?InsertMatrix(p3,temp1->i,temp1->j,total);
?? ??? ??? ??? ??? ?p3->tu--;
?? ??? ??? ??? ?}//如果相加和不為0，那么把和total插入。
?? ??? ??? ??? ? //別忘了p3中非零元素要自減?
?? ??? ??? ??? ?temp1=temp1->right;
?? ??? ??? ??? ?temp2=temp2->right;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
最后總結(jié)一下，有一些特別容易錯(cuò)的地方，而且不容易Debug出來(lái)：
1.插入元素時(shí)，既要完成行插入，又要完成列插入。雖然這兩個(gè)步驟基本類似，但還是建議大家不要看行插入步驟，獨(dú)立敲一遍列插入步驟。
2.注意三元組表的行數(shù)是從1開(kāi)始，列數(shù)也是從1開(kāi)始，所以在設(shè)置for循環(huán)時(shí)，要注意應(yīng)該設(shè)置成：
for(int i=1;i<=...;i++)?
不應(yīng)該設(shè)置成：
for(int i=0;i<...;i++)?
這也就是為什么，在對(duì)CrossList型變量的rHead動(dòng)態(tài)分配空間時(shí)，要多分配1個(gè)的原因，就是因?yàn)橄聵?biāo)為0的位置不可以使用。
p->rHead=(OLink*)malloc((r+1)*sizeof(OLink));
3.在進(jìn)行矩陣相加時(shí)，特殊情況優(yōu)先考慮，即優(yōu)先考慮“矩陣p1和p2在i行j列上都有元素”的情況，這個(gè)時(shí)候就要根據(jù)相加和來(lái)判斷了。如果相加和為0，該怎么處理；如果相加和不為0，又該怎么處理，不管你怎么做，都要記住一點(diǎn)："temp1=temp1->right;temp2=temp2->right;"
4.不要忘記考慮相加和為0的情況，這種情況不能插到新表里面去。（詳見(jiàn)我的上一篇文章）(8條消息) 西工大NOJ數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)——2.2稀疏矩陣加法，實(shí)現(xiàn)C=A+B_沒(méi)耳朵的Rabbit的博客-CSDN博客
5.最后，提供一個(gè)測(cè)試用例，興許對(duì)你有幫助（直接復(fù)制粘貼到exe黑框里面就行）?
3 3 9 9
1 1 1
1 2 2
1 3 3
2 1 4
2 2 5
2 3 6
3 1 7
3 2 8
3 3 9
1 1 9
1 2 8
1 3 7
2 1 6
2 2 5
2 3 4
3 1 3
3 2 2
3 3 11 1 10
1 2 10
1 3 10
2 1 10
2 2 10
2 3 10
3 1 10
3 2 10
3 3 10--------------------------------
Process exited after 13.05 seconds with return value 0
請(qǐng)按任意鍵繼續(xù). . .
?最后，還是完整的代碼：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
typedef int ElemType;
typedef struct OLNode{
int i,j;//行號(hào)和列號(hào)
ElemType elem;
struct OLNode *right;//右邊元素
struct OLNode *down;//下邊元素
}OLNode,*OLink;
typedef struct CrossList{
OLink* rHead;
OLink* cHead;
int mu,nu,tu;//行數(shù)、列數(shù)、非零元個(gè)數(shù)
}CrossList;
CrossList* CreateOLSMatrix(int r,int c,int t){//創(chuàng)建目標(biāo)十字鏈表的表頭
CrossList* p=(CrossList*)malloc(sizeof(CrossList));
if(p==NULL){
printf("Out of space!");
}
p->mu=r;
p->nu=c;
p->tu=t;
p->rHead=(OLink*)malloc((r+1)*sizeof(OLink));
p->cHead=(OLink*)malloc((c+1)*sizeof(OLink));
if(p->rHead==NULL||p->cHead==NULL) printf("Out of space!\n");
for(int i=0;i<r+1;i++){
p->rHead[i]=NULL;
}//強(qiáng)迫癥，初始化操作
for(int i=0;i<c+1;i++){
p->cHead[i]=NULL;
}//強(qiáng)迫癥，初始化操作
return p;
}
void InsertMatrix(CrossList* p,int i,int j,int elem){//插入數(shù)據(jù)
OLink p1=(OLink)malloc(sizeof(OLNode));
if(p1==NULL) printf("Out of space!\n");
p1->i=i;p1->j=j;p1->elem=elem;
//創(chuàng)建并填充結(jié)點(diǎn)
if(p->rHead[i]==NULL||p->rHead[i]->j>j){
p1->right=p->rHead[i];
p->rHead[i]=p1;
}else{
OLink q=p->rHead[i];
while(1){
if(q->right==NULL||q->right->j>j) break;
q=q->right;
}//找到插入位置
p1->right=q->right;
q->right=p1;
}//完成行插入
if(p->cHead[j]==NULL||p->cHead[j]->i>i){
p1->down=p->cHead[j];
p->cHead[j]=p1;
}else{
OLink q=p->cHead[j];
while(1){
if(q->down==NULL||q->down->i>i) break;
q=q->down;
}//找到插入位置
p1->down=q->down;
q->down=p1;
}//完成列插入
}
int BuildMatrix(CrossList* p){//完善表
for(int k=1;k<=p->tu;k++){
int i,j,elem;
scanf("%d%d%d",&i,&j,&elem);
InsertMatrix(p,i,j,elem);
}
}
int OutputMatrix(CrossList* p){//輸出表
for(int i=1;i<=p->mu;i++){
OLink q=p->rHead[i];
for(int j=1;j<=p->nu;j++){
if(q!=NULL&&j==q->j){
printf("%d %d %d\n",q->i,q->j,q->elem);
q=q->right;
}
}
}//按照先行后列的順序輸出
}
int AddMatrix(CrossList* p1,CrossList* p2,CrossList* p3){//矩陣相加得到新矩陣p3
for(int i=1;i<=p1->mu;i++){
//先行后列，一點(diǎn)一點(diǎn)地來(lái)做
OLink temp1=p1->rHead[i];
OLink temp2=p2->rHead[i];
for(int j=1;j<=p1->nu;j++){
int flag1=temp1!=NULL&&j==temp1->j;
int flag2=temp2!=NULL&&j==temp2->j;
//為什么我要用flag呢？因?yàn)槎挤旁趇f后面的話，if會(huì)變的很長(zhǎng)很長(zhǎng)，超級(jí)麻煩
if(flag1==1&&flag2!=1){//如果這個(gè)位置上,p1有數(shù)據(jù)，p2沒(méi)數(shù)據(jù)
InsertMatrix(p3,temp1->i,temp1->j,temp1->elem);
temp1=temp1->right;
}
if(flag1!=1&&flag2==1){//如果這個(gè)位置上,p1沒(méi)數(shù)據(jù)，p2有數(shù)據(jù)
InsertMatrix(p3,temp2->i,temp2->j,temp2->elem);
temp2=temp2->right;
}
if(flag1==1&&flag2==1){//如果這個(gè)位置上,p1有數(shù)據(jù)，p2也有數(shù)據(jù)
int total=temp1->elem+temp2->elem;
if(total==0){
p3->tu=p3->tu-2;
//如果p1的數(shù)據(jù)與p2的數(shù)據(jù)相加為0，那就不用插入
//別忘了p3中非零元素要減2
}else if(total!=0){
InsertMatrix(p3,temp1->i,temp1->j,total);
p3->tu--;
}//如果相加和不為0，那么把和total插入。
//別忘了p3中非零元素要自減
temp1=temp1->right;
temp2=temp2->right;
}
}
}
}
int main(){
//int r,c,t1;
//scanf("%d%d%d",&r,&c,&t1);
int r,c,t1,t2;
scanf("%d%d%d%d",&r,&c,&t1,&t2);
//輸入行數(shù)、列數(shù)、兩個(gè)矩陣的非零元個(gè)數(shù)
CrossList* p1=CreateOLSMatrix(r,c,t1);
CrossList* p2=CreateOLSMatrix(r,c,t2);
CrossList* p3=CreateOLSMatrix(r,c,t1+t2);
//創(chuàng)建三個(gè)十字鏈表的表頭
//其中p3表示最終相加得到的十字鏈表
//p1+p2時(shí)，可能會(huì)有元素合并，或者合并之后結(jié)果為0之類的情況出現(xiàn)，導(dǎo)致p3中非零元素小于t1+t2
//但是方便起見(jiàn)，還是記非零元素個(gè)數(shù)為t1+t2
//要是真有元素合并，以及合并之后結(jié)果為0，那“非零元素-1”這一步到時(shí)候再做也不遲
BuildMatrix(p1);
BuildMatrix(p2);
AddMatrix(p1,p2,p3);
OutputMatrix(p3);
return 0;
}如果對(duì)你有幫助的話，就請(qǐng)麻煩點(diǎn)個(gè)贊叭
真心希望點(diǎn)贊加關(guān)注哦
你們的鼓勵(lì)是我創(chuàng)作路上的不竭動(dòng)力文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-425455.html
謝謝大家！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-425455.html
到了這里，關(guān)于西工大NOJ數(shù)據(jù)結(jié)構(gòu)理論——013.以十字鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)矩陣相加（嚴(yán)5.27）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
