线性表的合并

3867阅读　2评论2011-08-13　sunjiangang-ok
分类：C/C++

    好久都没有用c语言写程序了，对于c语言都有些生疏了～在暑期最后这十几天内，把数据结构好好复习一下吧，今天静下心来，慢慢复习数据结构时候，发现自己长时间没有编写程序了，竟然编写一个简单的线性表的合并花费的2个多小时，唉，看来程序还是要坚持写的，不能放下～

题目要求：有两个线性表a和b，这两个线性表都是非递减有序排列，现在要把这两个线性表合并为一个非递减有序排列的c线性表。
算法思想：用i，j，k这3个指示器分别指向这3个线性表的下标，然后将a[i]和b[j]进行比较，如果a[i]
实现代码：
  1. #include <stdio.h>

  3. #define intlen(x) sizeof(x)/sizeof(int)      //用来计算x整型数组的长度

  5. int len_a, len_b, len_c;
  1. void merge(int a[], int b[], int c[])
  2. {
  3.     int i, j, k;
  4.     i = j = k = 0;
  5.     while(i < len_a && j < len_b) {
  6.         if(a[i] <= b[j]) {
  7.             c[k++] = a[i++];
  8.         } else {
  9.             c[k++] = b[j++];
  10.         }
  11.     }
  12.     while(i < len_a) {
  13.         c[k++] = a[i++];
  14.     }
  15.     while(j < len_b) {
  16.         c[k++] = b[j++];
  17.     }
  18. }

  20. int main()
  21. {
  22.     int a, b, i;
  23.     fprintf(stdout, "Input two array size:\n");
  24.     fscanf(stdin, "%d%d", &a, &b);
  25.     int arr_a[a], arr_b[b], arr_c[a+b];
  26.     fprintf(stdout, "Input array a:\n");
  27.     for(i = 0; i < a; i++) {
  28.         fscanf(stdin, "%d", arr_a+i);
  29.     }
  30.     fprintf(stdout, "Input array b:\n");
  31.     for(i = 0; i < b; i++) {
  32.         fscanf(stdin, "%d", arr_b+i);
  33.     }
  34.     len_a = intlen(arr_a);
  35.     len_b = intlen(arr_b);
  36.     len_c = intlen(arr_c);
  37.     merge(arr_a, arr_b, arr_c);
  38.     fprintf(stdout, "The merged result:\n");
  39.     for(i = 0; i < len_c; i++) {
  40.         fprintf(stdout, "%d\t", arr_c[i]);
  41.     }
  42.     fprintf(stdout, "\n");
  43.     return 0;
  44. }
测试结果：
  1. ^_^[sunny@sunny-laptop ~/DS]31$ ./a.out
  2. Input two array size:
  3. 3 4
  4. Input array a:
  5. 2
  6. 2
  7. 4
  8. Input array b:
  9. 1
  10. 3
  11. 5
  12. 6
  13. The merged result:
  14. 1    2    2    3    4    5    6    
  15. ^_^[sunny@sunny-laptop ~/DS]32$

上一篇：c语言宏定义总结
下一篇：linux内核list.h头文件分析（一）

文章评论