注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

始めの一歩

不是世界变得无聊了,而是你变成了无聊的人……

 
 
 

日志

 
 

【数据结构】线性表 源码 1 -- 合并两个有序「顺序表」(静态数组)  

2012-07-14 18:02:41|  分类: Fateの数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

来源:数据结构(C 语言版)严蔚敏、吴伟民 清华大学出版社 -- P20、例 2-2

 

要求:Input:顺序表 LA 和 LB,其中的数据元素按值非递减排序

   Output:将 LA 和 LB 归并成新顺序表 LC,且 LC 中数据元素仍按值非递减排序

 

PS:是“顺序表”,不是“线性表”。“顺序表”是“线性表”的“顺序存储结构”

PS2:使用“静态数组”,即:使用最简单的 array[ ] 实现

 

源码:(初出茅庐,难免有写的不好的地方,仅作备份之用,欢迎指点,喷子退散……)

/*-----------------------------------------------------------------------------------------------------------
                                    合并两个有序顺序表(静态数组)

Input:顺序表 LA 和 LB,其中的数据元素按值非递减排序
Output:将 LA 和 LB 归并成新顺序表 LC,且 LC 中数据元素仍按值非递减排序
------------------------------------------------------------------------------------------------------------*/

#include <stdio.h>

void Init_List(int LA[ ], int LB[ ], int LC[ ]);      // 初始化顺序表
void Scanf_List(int L[ ], int length, int *n);     // 从键盘输入数据
void Printf_List(int L[ ], int length);                // 显示顺序表中的数据

int LA[10], LB[10], LC[20];          // 数据定义,LA 与 LB 数据合并,输出到 LC

void main (void)
{
    int i, j, k;
    int LA_length, LB_length;      // LA,LB 中 有效数据 的 长度

    Init_List(LA, LB, LC);               // 初始化顺序表

    printf("输入顺序表 LA:");
    Scanf_List(LA, 10, &LA_length);        // 输入数据

    printf("输入顺序表 LB:");
    Scanf_List(LB, 10, &LB_length);

//  Printf_List(LA, 10);                  // 显示数据,测试输入是否正确
//  Printf_List(LB, 10);

/*----------------------------------------------------------------------------------------------------
算法本体:同时扫描 LA 与 LB,比较 LA[i] 与 LB[j] 的大小
                   如果 LA[i] <= LB[j],将 LA[i] 插到 LC 尾部,同时指针向后移动
                   如果 LA[i]  >  LB[j],将 LB[j] 插到 LC 尾部,同时指针向后移动
                   最后处理一下尾部特殊情况

注:i, j, k 的作用其实就相当于指针
-----------------------------------------------------------------------------------------------------*/

    for (i = 0, j = 0, k = 0; i < LA_length && j < LB_length; ) {
        if (LA[i] < LB[j]) {
            LC[k] = LA[i];
            i++;
            k++;
        }
        if (LA[i] == LB[j]) {
            LC[k] = LA[i];
            i++;
            j++;
            k++;
        }
        if (LA[i] > LB[j]) {
            LC[k] = LB[j];
            j++;
            k++;
        }
    }

    if (i > j) {
        for ( ; j < 10; j++) {
            LC[k] = LB[j];
            k++;
        }
    }
    else if (i < j) {
        for ( ; i < 10; i++) {
            LC[k] = LA[i];
            k++;
        }
    }

    printf("\n合并后的顺序表 LC:");
    Printf_List(LC, 20);        // 显示最终顺序表 LC 中的数据

    printf("\n");
}

/*--------------------------------------------
         初始化顺序表,数据清零
---------------------------------------------*/

void Init_List(int LA[ ], int LB[ ], int LC[ ])
{
    int i;
    for (i = 0; i < 10; i++) {
        LA[i] = 0;
        LB[i] = 0;
    }
    for (i = 0; i < 20; i++) LC[i] = 0;
}

/*---------------------------------------------------------
从键盘输入数据,length 为 数据个数上限
                                   n     为 有效数据个数
----------------------------------------------------------*/

void Scanf_List(int L[ ], int length, int *n)
{
    int i = 0;
    (*n) = 0;
    while (i < length && scanf("%d", &L[i]) == 1) {
        if (L[i] == 0) break;
        i++;
        (*n)++;
    }
}

/*---------------------------------------------
             显示顺序表中的数据
----------------------------------------------*/

void Printf_List(int L[ ], int length)
{
    int i;
    for (i = 0; i < length; i++) {
        printf("%d ", L[i]);
    }
    printf("\n");
}

 

输出结果:

【数据结构】线性表 源码 1 -- 合并两个有序「顺序表」(静态数组) - 灼眼のFate - 運命の始まり

【数据结构】线性表 源码 1 -- 合并两个有序「顺序表」(静态数组) - 灼眼のFate - 運命の始まり

【数据结构】线性表 源码 1 -- 合并两个有序「顺序表」(静态数组) - 灼眼のFate - 運命の始まり

【数据结构】线性表 源码 1 -- 合并两个有序「顺序表」(静态数组) - 灼眼のFate - 運命の始まり

  评论这张
 
阅读(1073)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018