1. 首页
  2. IT资讯

数据结构:递增排列的数组 union all 算法 2.1

递增排列的数组 union all
假设有2个线性表,递增排列的数组,如
char a[20]=”abbcopqtuwz”;
char b[20]=”bcfgjmtv”;
我们需要实现一个union all,将两个字符串中的字符合并到

一个新的线性表c中,其中也是按照递增排列的。
那么按照我们要求输出应该为
abbbccfgjmopqttuvwz

那么算法如下:

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include <string.h>
  3. int main(void)
  4. {
  5.         char a[20]=“abbcopqtuwz”;
  6.         char b[20]=“bcfgjmtv”;
  7.         char c[30];
  8.         memset(c,0,30);
  9.         int n=0;
  10.         int m=0;
  11.         int h=0;
  12.         int a_len=strlen(a);
  13.         int b_len=strlen(b);
  14.         while(n<a_len && m<b_len)
  15.         {
  16.                 if(a[n]< b[m])
  17.                 {
  18.                         c[h]=a[n];
  19.                         n++;
  20.                 }
  21.                 else if(a[n]==b[m])
  22.                 {
  23.                         c[h]=a[n];
  24.                         n++;
  25.                 }
  26.                 else
  27.                 {
  28.                         c[h]=b[m];
  29.                         m++;
  30.                 }
  31.                 h++;
  32.         }
  33.         if(a[n] != 0)
  34.         {
  35.                 while(n<a_len)
  36.                 {
  37.                         c[h]=a[n];
  38.                         n++;
  39.                         h++;
  40.                 }
  41.         }
  42.         if(b[m] != 0 )
  43.         {
  44.                 while(m<b_len)
  45.                 {
  46.                         c[h]=b[m];
  47.                         m++;
  48.                         h++;
  49.                 }
  50.         }
  51.   
  52.         printf(“%sn”,c);
  53. }

运行程序输出为:abbbccfgjmopqttuvwz

可以看到和预期一模一样。
分析这个算法的渐进时间复杂度,实际上我们发现他只是一个单循环,很明显我们原操作只是c[h]=a[n];这样的复制
所以时间复杂度为:
T(n)=O(n)
但是这样的算法明显依赖于两个数组排序好了的情况

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2124893/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183855.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code