俩个有序顺序表的合并(好好学习)

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
简介: 今天上课的时候老师提到了这题,上课的时候脑子卡了,居然没做出来,在路上才想起来怎么操作对于这道题首先考虑的是LA LB为空的三种情况,
Elementype GetElem(list L, Position pos)
{
  if (pos<0 || pos>L->last)
  {
    return ERROR;
  }
  else
  {
    return L->Data[pos];
  }
}
//给出LA LB俩个递增顺序表,要求合并成为LC有序链表(LC为空)
struct LNode {
  Elementype Data[Maxszie];
  Position Last
};
//Last为最后一个下标值

今天上课的时候老师提到了这题,上课的时候脑子卡了,居然没做出来,在路上才想起来怎么操作


对于这道题首先考虑的是LA  LB为空的三种情况,



void merge(list a,list b,list c)

2.即LA为空,LB不为空的时候,将LA的Data全部拷贝进去,将LC->Last调为LB->Last


3.即LB为空,LA不为空的时候,将LB的Data全部拷贝进去,将LC->Last调为LC->Last


这三种是比较先考虑的,拷贝for循环就对了;(为空的判断的条件为Last=-1)


  if (a->Last == -1 && b->Last == -1)
  {
    return;
  }
  else if (a->Last != -1 && b->Last == -1)
  {
    for (int i = 0; i <= a->Last; i++)
    {
      c->Data[i] = a->Data[i];
    }
    c->Last = a->Last;
  }
  else if (b->Last != -1 && a->Last == -1)
  {
    for (int i = 0; i <= b->Last; i++)
    {
      c->Data[i] = b->Data[i];
    }
    c->Last = b->Last;
  }

接下来就是一些比较常规的情况了;我的想法是定义三个类似指针的玩意,来定位三个顺序表的下标。即pa =pb= pc=0;然后开始循环进行比较插入,判断pa pb对应位置的数据大小,那个小就把该下标下的data值赋给LC顺序表,循环下去直到pa 大于LA->Last,或者pb 大于LB->Last,最后只要还没有插入LC中的对应LA或LB的值全部插进LC


听到这里可能还有点懵,那么我们就用图来说明以下吧



刚开始的时候:

56df39e412ff4599afb10fbb00ec8dec.png

第一次以后,pa++,pc++

25d91491652349958ef8be4de1687810.png

第二次 pa++,pc++

acd4ad03725043a2a614bf0b89b23f4b.png

第三次:pb++,pc++

87e5a88dab094796b5964e6cbf998603.png 第四次:pa++,pc++

62811d1fc7f349a4985b29a30649e2cb.png

到这个时候我们发现pa已经大于LA-->Last   ,接下来就只需要把LB后面的全部放进去就可以了

45fa62b20ef5403fbd3584ca37f25831.png

这就是完成这道题的基本思路了,那么如何将PB中未插的数据如何全部插入呢,很简单。一个for循环,我们可以知道这个时候 pa大于 LA->last   但pb小于LB->Last;所以只要for循环到pb大于LB->Last就可以了!!!


这个时候的控制条件一定要十小心!!!


在代码的时候要判断到底是LA全部插了还是LB全部插了,可以通过

if (pa > a->Last )
这个是PA全部插入了


以下是代码实现:



  else 
  {
    c->Last = a->Last + b->Last + 1;
    int pa, pb, pc;
    pa = pb = pc = 0;
    for (; pa <= a->Last&&pb <=b->Last; pc++)
    //如果a的都插入或b全部插入了,就结束
    {
      if (a->Data[pa]< b->Data[pb])
      {
        c->Date[pc] = a->Data[pa];
        pa++;
      }
      else
      {
        c->Data[pc] = b->Data[pb];
        pb++;
      }
    }
    if (pa > a->Last )
    //如果是a表的全部插入了,那么就将b表全部插入
    {
      for (; pb <= b->Last; pb++,pc++)
      {
        c->Data[pc] = b->Data[pb];
      }
    }
    else//如果是b表的全部插入了,那么就将a表全部插入
    {
      for (; pa <= a->Last; pa++, pc++)
      {
        c->Data[pc] = a->Data[pa];
      }
    }
  }



相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
6月前
《剑指offer》——合并两个排序的链表
《剑指offer》——合并两个排序的链表
【剑指offer】-合并两个排序的链表-16/67
【剑指offer】-合并两个排序的链表-16/67
|
存储
OJ题库:俩个有序序列(数组)合并
OJ题库:俩个有序序列(数组)合并
39 0
【手撕力扣链表题】合并两个有序链表,删除排序链表中的重复元素(2/98)
【手撕力扣链表题】合并两个有序链表,删除排序链表中的重复元素(2/98)
120 0
|
存储 C++
剑指Offer - 面试题25:合并俩个排序的链表
剑指Offer - 面试题25:合并俩个排序的链表
57 0
剑指offer 24. 合并两个排序的链表
剑指offer 24. 合并两个排序的链表
90 0
【牛客】合并两个有序的数组
【牛客】合并两个有序的数组
115 0
【牛客】合并两个有序的数组
顺序表的十个基本操作(全)
一、初始化顺序表 二、插入 三、删除 3.1 按位删除 3.2 按数删除 四、查找 4.1 按位查找 4.2 按数查找 五、修改 5.1 按位修改 5.2 按数修改 六、逆置 七、排序 八、按序插入 九、按序合并 十、最小值
127 0
顺序表的十个基本操作(全)
|
算法 前端开发 索引
有序的数组,试试用指针法遍历
有序的数组,试试用指针法遍历
76 0