两个十字链表相加

2024-06-03 19:32
文章标签 链表 相加 两个 十字

本文主要是介绍两个十字链表相加，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#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.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
 }//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;// 给结点赋值

                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
                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;// 给结点赋值

                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指针向右移
                 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;
}

这篇关于两个十字链表相加的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1027908。

相关文章

锐捷和腾达哪个好? 两个品牌路由器对比分析

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时，Tenda和锐捷都是备受关注的品牌，各自有独特的产品特点和市场定位，选择哪个品牌的路由器更合适，实际上取决于你的具体需求和使用场景，我们从... 在选购路由器时，锐捷和腾达都是市场上备受关注的品牌，但它们的定位和特点却有所不同。锐捷更偏向企业级和专
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位：为1时表示在内存期间被访问过，为0时表示未被访问；修改位：为1时表示该页面自从被装入内存后被修改过，为0时表示未修改过。 置换页面时，最先置换访问位和修改位为00的，其次是01(没被访问但被修改过)的，之后是10(被访问了但没被修改过)，最后是11。 2.内聚的类型 功能内聚：完成一个单一功能，各个部分协同工作，缺一不可。 顺序内聚：
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
javaScript日期相加减例子

javaScript日期相加减例子

当前时间加上2天 var d = new Date(“2015-7-31”); d.setDate(d.getDate()+2); var addTwo=d.getFullYear()+”年”+(d.getMonth()+1)+”月”+d.getDate()+”日”; “控制台输出===============”+”当前日期加2天：”+addTwo; 使用这种方法，月份也会给你计算.
阅读更多...
2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

根据通知，2024年AMC10美国数学竞赛的报名还有两周，正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间，认真备考，最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢？做真题，吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题，可以帮助孩子找到真实竞赛的感觉，而且更加贴近比赛的内容，可以通过真题查漏补缺，更有针对性的补齐知识的短板。
阅读更多...
【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

总结，删除链表节点问题使用到列表，哈希表，递归比较容易超时，我觉得使用计数排序比较稳，处理起来也不是很难。 1. 力扣3217：从链表中移除在数组中的节点 1.1 题目： 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。 示例 1： 输入： nums = [1,2,3], head = [1,2,3,
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2