两个十字链表相加

谁践踏了优雅 2022-08-25 05:28 126阅读 0赞

\#define OVERFLOW -1

//------------稀疏矩阵的十字链表存储表示--------------  
typedef struct OLNode\{  
int i,j; //该非零元的行和列下标  
int e;//非零元  
struct OLNode \* right, \* down; // right指向该非零元所在行的右边的非零元，down指向下面的非零元  
\}OLNode, \* OLink;  
typedef struct \{  
OLink \* rhead, \* chead; //rhead指向一个一维数组，里面存放每个行链表的头结点；chead指向一个一维数组，里面存放每个列链表的头结点  
int mu,nu,tu; //稀疏矩阵的行数，列数，非零元个数  
\}CrossList;

\#include "iostream"  
\#include "cstdio"  
\#include "cstdlib"

void CreateSMatrix\_OL( CrossList &M )  
\{  //创建稀疏矩阵M;用十字链表存储  
printf("----------请依次输入稀疏矩阵M的  行数、列数、非零元个数 （空格隔开）---------\\n");  
scanf("%d%d%d",&M.mu, &M.nu, &M.tu ); //输入M的行数、列数、非零元个数  
if( !(M.rhead = (OLink \*)malloc( (M.mu+1) \* sizeof(OLink) )))exit(OVERFLOW); //给rhead分配一个一维数组，失败则退出程序  
if( !(M.chead = (OLink \*)malloc( (M.nu+1) \* sizeof(OLink) )))exit(OVERFLOW); //给chead分配一个一维数组，失败则退出程序  
  
int x;  
for(x =1 ; x <= M.mu; x++) M.rhead\[x\] = NULL; //初始化rhead指向的一维数组个元素都为空，即每个行链表都为空  
for(x =1 ; x <= M.nu; x++) M.chead\[x\] = NULL;

int i,j,e;  
OLNode \* p,\* q;  
int cnt\_e;//用来统计非零元个数  
printf("--------下面输入%d行，每行三个数： 行标 列标  元素的值（空格隔开）--------\\n",M.mu);  
for(cnt\_e = 1; cnt\_e <= M.tu ; cnt\_e++)\{  
scanf("%d%d%d",&i,&j,&e);  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
p->i = i; p->j = j;  p->e = e;

if( M.chead\[j\] == NULL || M.chead\[j\]->i > i) \{ p->down = M.chead\[j\]; M.chead\[j\] = p;\}  
else\{ //寻找新非零元在列标中的插入位置  
for( q = M.chead\[j\] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环  
p->down = q->down; q->down = p; //完成列插入  
\}//else  
\}//for  
return;  
\}  
void PrintSMatrix\_OL( CrossList M )  
\{  
OLNode \* pr;  
int cnt\_r,cnt\_c;//控制行和列  
printf("---------------------------- 稀疏矩阵 ------------------------\\n");  
for( cnt\_r =1; cnt\_r <= M.mu; cnt\_r++ )\{  //控制行  
pr = M.rhead\[cnt\_r\]; //pr指向每一行的链表  
for( cnt\_c = 1; cnt\_c<= M.nu ;cnt\_c++)\{ //控制咧  
if( NULL == pr )  printf("= ",0); //该行是空行  
else \{//不是空行  
if(cnt\_c == pr->j ) \{ printf("= ",pr->e); pr = pr->right;\}  
else printf("= ",0);  
\}//else  
//pr = M.rhead\[cnt\_r\];  
\}//for  
printf("\\n");  
\}//for  
return;  
\}

void AddSMatrix\_OL(CrossList M1,CrossList M2,CrossList &M)  
\{  
//创建空稀疏矩阵M  
M.mu = M1.mu;  M.nu = M1.nu; M.tu = 0;  
if( !(M.rhead = (OLink \*)malloc( (M.mu+1) \* sizeof(OLink) )))exit(OVERFLOW); //给rhead分配一个一维数组，失败则退出程序  
if( !(M.chead = (OLink \*)malloc( (M.nu+1) \* sizeof(OLink) )))exit(OVERFLOW); //给chead分配一个一维数组，失败则退出程序  
int x;  
for( x =1 ; x <= M.mu; x++) M.rhead\[x\] = NULL; //初始化rhead指向的一维数组个元素都为空，即每个行链表都为空  
for( x =1 ; x <= M.nu; x++) M.chead\[x\] = NULL;

//相加  
int i,j,e,cnt\_r;  
OLNode \* p1,\*p2,\*p,\*q;  
for( cnt\_r=1; cnt\_r<=M.mu; cnt\_r++) // 按行的顺序相加  
\{  
p1=M1.rhead\[cnt\_r\];// p1指向矩阵M1的第i行的第1个结点  
p2=M2.rhead\[cnt\_r\];// p2指向矩阵N2的第i行的第1个结点  
while(p1&&p2)// p1和p2均不空  
\{  
if(p1->j < p2->j) // 矩阵M当前结点的列小于矩阵N当前结点的列  
\{  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
i = p1->i; j = p1->j; e = p1->e;  
p->i = i;p->j = j;p->e= e;// 给结点赋值  
  
//p结点插入M  
if( M.rhead\[i\] == NULL || M.rhead\[i\]->j > j) \{ p->right = M.rhead\[i\]; M.rhead\[i\] = p;\}  
else\{ //寻找新非零元在航标中的插入位置  
for( q = M.rhead\[i\] ; (q->right)&&(q->right->j < j); q = q->right ) ; //循环到合适位置，这是个空循环  
p->right = q->right; q->right = p; //完成行插入  
  
\}//else  
if( M.chead\[j\] == NULL || M.chead\[j\]->i > i) \{ p->down = M.chead\[j\]; M.chead\[j\] = p;\}  
else\{ //寻找新非零元在列标中的插入位置  
for( q = M.chead\[j\] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环  
p->down = q->down; q->down = p; //完成列插入  
\}//else

M.tu++;// 非零元素数加1  
p1 = p1->right;

\}  
else if(p1->j > p2->j )// 矩阵M当前结点的列大于矩阵N当前结点的列  
\{  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
i = p2->i; j = p2->j; e = p2->e;  
p->i = i;p->j = j;p->e= e;// 给结点赋值

M.tu++;// 非零元素数加1  
p2=p2->right; // p2指针向右移  
\}  
  
else if(p1->e + p2->e)  // 矩阵M、N当前结点的列相等且两元素之和不为0  
\{  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
i = p1->i; j = p1->j; e = p1->e +p2->e;  
p->i = i;p->j = j;p->e= e;// 给结点赋值

p1 = p1->right; // p1指针向右移  
p2 = p2->right; // p2指针向右移  
M.tu++; // 非零元素数加1  
\}  
else  \{// 矩阵M、N当前结点的列相等且两元素之和为0  
p1=p1->right; // p1指针向右移  
p2=p2->right; // p2指针向右移  
\}

\}//while  
  
while(p1) // 将矩阵M该行的剩余元素插入矩阵Q  
\{  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
  
i = p1->i; j = p1->j; e = p1->e ;  
p->i = i;p->j = j;p->e= e;// 给结点赋值

if( M.rhead\[i\] == NULL || M.rhead\[i\]->j > j) \{ p->right = M.rhead\[i\]; M.rhead\[i\] = p;\}  
else\{ //寻找新非零元在航标中的插入位置  
for( q = M.rhead\[i\] ; (q->right)&&(q->right->j < j); q = q->right ) ; //循环到合适位置，这是个空循环  
p->right = q->right; q->right = p; //完成行插入  
\}//else  
if( M.chead\[j\] == NULL || M.chead\[j\]->i > i) \{ p->down = M.chead\[j\]; M.chead\[j\] = p;\}  
else\{ //寻找新非零元在列标中的插入位置  
for( q = M.chead\[j\] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环  
p->down = q->down; q->down = p; //完成列插入  
\}//else  
p1 = p1->right; // p1指针向右移  
M.tu++; // 非零元素数加1  
\}  
while(p2) // 将矩阵N该行的剩余元素插入矩阵Q  
\{  
if( !(p = (OLNode \*)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元  
i = p2->i; j = p2->j;e = p2->e;  
p->i = i;p->j = j;p->e= e;// 给结点赋值

if( M.rhead\[i\] == NULL || M.rhead\[i\]->j > j) \{ p->right = M.rhead\[i\]; M.rhead\[i\] = p;\}  
else\{ //寻找新非零元在航标中的插入位置  
for( q = M.rhead\[i\] ; (q->right)&&(q->right->j < j); q = q->right ) ; //循环到合适位置，这是个空循环  
p->right = q->right; q->right = p; //完成行插入  
\}//else  
if( M.chead\[j\] == NULL || M.chead\[j\]->i > i) \{ p->down = M.chead\[j\]; M.chead\[j\] = p;\}  
else\{ //寻找新非零元在列标中的插入位置  
for( q = M.chead\[j\] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环  
p->down = q->down; q->down = p; //完成列插入  
\}//else  
p2=p2->right; // p1指针向右移  
M.tu++; // 非零元素数加1  
\} //while  
\}//for  
  
return;  
\}  
int main ()  
\{  
//freopen("Debug\\\\input.txt", "r", stdin);  
// freopen("Debug\\\\output.txt", "w", stdout);

CrossList M1,M2,M; //定义一个稀疏矩阵M  
CreateSMatrix\_OL(M1); //创建稀疏矩阵M;用十字链表存储  
PrintSMatrix\_OL(M1);

CreateSMatrix\_OL(M2); //创建稀疏矩阵M;用十字链表存储  
PrintSMatrix\_OL(M2);

AddSMatrix\_OL(M1,M2,M); // 稀疏矩阵M1,M2相加结果为M  
PrintSMatrix\_OL(M);  
  
system("pause");  
return 0;  
\}