开发者社区> 技术小阿哥> 正文

线性表-归并算法

简介:
+关注继续查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*例如:有两个线性表LA=(1,5,7,15)
                    LB=(3,6,8,9,13,15,17)
则:                LC=(1,3,6,8,9,13,15,15,17)
上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则首先设LC为空表,然后将LA或LBs中的元素逐个插入到LC当中。
为使LC中元素按值非递减排列,可设两个指针i,j分别向LA和LB中的某个元素,若设i当所指的元素为a,j所指的元素为b则当前应插LC元素c为
 
    |->  b a>b
  c=|->  a a=b
    |->  a a<b
    显然,设指针i的j的初使值为1,在所指元素插入LC之后,指针在表LA或LB中将顺序后移。
*/
template<class T>
class merge<T>::
void MergetList(T La,T Lb, T Lc)
{
/*已知线性表La和Lb中的数据元素按值非递减排列*/
/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/
    InitList(Lc);
    i=j=1;k=0;
    La_len=ListLength(La);
    Lb_len=ListLength(Lb);
    while((i<La_len)&&(j<=Lb_len))
    {
        GetElem(La,i,ai);
        GetElem(Lb,j,bj);
        if(ai<bj)
        {
            ListInsert(Lc,++k,ai);
            ++i;
        }
        else if (ai==bj)
        {
            ListInsert(Lc,++k,ai);++i;++j;
        }
        else
        {
            ListInsert(Lc,++k,bj);++i;++j;
        }
    }
    while(i<=La_len)
    {
        /*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
        GetElem(La,i++,ai);
        ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len)
    {
        /*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
        GetElem(La,j++,bj);
        ListInsert(Lc,++k,bj);
    }
}/***********************************************************************-*/
/* MergeList                                                             */
/************************************************************************/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
18108 0
PostgreSQL 9.6 并行计算 优化器算法浅析
背景 之前写过几篇 PostgreSQL 并行计算的文章,文中并没有仔细描述PostgreSQL是如何决策并行计算,以及并行度的。 开源数据库PostgreSQL攻克并行计算难题https://yq.aliyun.com/articles/44655 PostgreSQL 并行计算 在
8361 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
17699 0
排序算法(四):归并排序
归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。 以下所讲归并都是指二路归并: 之前的冒泡、选择和插入排序都是维持一个待排序集合和一个已排序集合,在每次的迭代过程中从待排序集合中移动一个元素到已排序集合中,通过不断的迭代来完成排序,所以需要进行的迭代次数一般都是 级别。
825 0
13692
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载