Question

数据结构：顺序表的合并（C语言）

大神你好。求帮写个代码被，有重谢。
用C语言编写程序：设有顺序表 LA＝（3,5,8,11）和
LB=（2,6,8,9,11,15,20）；
① 若LA和LB分别表示两个集合A和B，求新集合
C＝A U B（ “并”操作，相同元素不保留）
预测输出：LC=（3,5,8,11,2,6,9,15,20）
② 将LA归并到LB表中且仍保持有序（保留相同元素）
预测输出：LB=（2,3,5,6,8,8,9,11,11,15,20）
③将LA和LB归并新表LC中且变为逆序（保留相同元素）
预测输出：LB=（20,15,11,11,9,8,8,6,5,3,2 ）

Answer 1

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量
#define LISTINCREMENT 2 // 线性表存储空间的分配增量

struct SqList
{
    int *elem; // 存储空间基址
    int length; // 当前长度
  int listsize; // 当前分配的存储容量(以sizeof(int)为单位)
};

void InitList(SqList &L)
{ // 操作结果：构造一个空的顺序线性表
  L.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));
  if (!L.elem)
      exit(0); // 存储分配失败
  L.length = 0; // 空表长度为0
  L.listsize = LIST_INIT_SIZE; // 初始存储容量
}

int ListInsert(SqList &L, int i, int e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
  int *newbase, *q, *p;
  if (i<1 || i>L.length + 1) // i值不合法
    return 0;
  if (L.length >= L.listsize) // 当前存储空间已满,增加分配
  {
    if (!(newbase = (int *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(int))))
        exit(0); // 存储分配失败
    L.elem = newbase; // 新基址
    L.listsize += LISTINCREMENT; // 增加存储容量
  }
  q = L.elem + i - 1; // q为插入位置
  for (p = L.elem + L.length - 1; p >= q; --p) // 插入位置及之后的元素右移
  *(p + 1) = *p;
  *q = e; // 插入e
  ++L.length; // 表长增1
  return 1;
}

void Print(SqList &L)
{
  int i;
  for (i = 0; i<L.length; i++)
    printf("%d ", *(L.elem + i));
  printf("\n");
}

// ————————————————————————————————————
// 函数①
void MergeList1(SqList La, SqList Lb, SqList &Lc)
{
  int *pa, *pa_last, *pb, *pb_last, *pc;
  pa = La.elem;
  pb = Lb.elem;
  Lc.listsize = Lc.length = La.length + Lb.length;//不用InitList()创建空表Lc
  pc = Lc.elem = (int *)malloc(Lc.listsize*sizeof(int));
  if (!Lc.elem) // 存储分配失败
    exit(0);
  pa_last = La.elem + La.length - 1;
  pb_last = Lb.elem + Lb.length - 1;
  while (pa <= pa_last&&pb <= pb_last) // 表La和表Lb均非空
  { // 归并
    if (*pa < *pb)
      *pc++ = *pa++;
    else if (*pa > *pb)
      *pc++ = *pb++;
    else{
      *pc++ = *pa++;
      pb++;
      Lc.length--;
    }
  }
  while (pa <= pa_last) // 表La非空且表Lb空
  *pc++ = *pa++; // 插入La的剩余元素
  while (pb <= pb_last) // 表Lb非空且表La空
    *pc++ = *pb++; // 插入Lb的剩余元素
}

// ————————————————————————————————————
// 函数②
void MergeList2(SqList La, SqList &Lb, SqList &Lc)
{
  int *pa, *pa_last, *pb, *pb_last, *pc;
  pa = La.elem;
  pb = Lb.elem;
  Lc.listsize = Lc.length = La.length + Lb.length;//不用InitList()创建空表Lc
  pc = Lc.elem = (int *)malloc(Lc.listsize*sizeof(int));
  if (!Lc.elem) // 存储分配失败
    exit(0);
  pa_last = La.elem + La.length - 1;
  pb_last = Lb.elem + Lb.length - 1;
  while (pa <= pa_last&&pb <= pb_last) // 表La和表Lb均非空
  { // 归并
    if (*pa <= *pb)
        *pc++ = *pa++;
    else
      *pc++ = *pb++;
  }
  while (pa <= pa_last) // 表La非空且表Lb空
    *pc++ = *pa++; // 插入La的剩余元素
  while (pb <= pb_last) // 表Lb非空且表La空
    *pc++ = *pb++; // 插入Lb的剩余元素
  Lb.length = Lc.length;
  Lb = Lc;
}

// ————————————————————————————————————
// 函数③
void Inverse(SqList &L){
  int i, t;
  for (i = 0; i < L.length / 2; i++)
  {
      t = *(L.elem + i);
    *(L.elem + i) = *(L.elem + L.length - i - 1);
    *(L.elem + L.length - i - 1) = t;
  }
}

void main(){
  SqList LA, LB, LC;
  int a[4] = { 3, 5, 8, 11 }, b[7] = { 2, 6, 8, 9, 11, 15, 20 };
  int i;
        
  InitList(LA);
  InitList(LB);
  InitList(LC);
  for (i = 0; i < 4; i++)
    ListInsert(LA, i + 1, a[i]);
  for (i = 0; i < 7; i++)
    ListInsert(LB, i + 1, b[i]);
  printf("LA=");
  Print(LA);
  printf("LB=");
  Print(LB);
  printf("\n");
        
  MergeList1(LA, LB, LC);
  printf("①LC=");
  Print(LC);
  printf("\n");
        
  MergeList2(LA, LB, LC);
  printf("②LB=");
  Print(LB);
  printf("\n");
        
  printf("③LC=");
  Inverse(LC);
  Print(LC);
}