PTA-学校-数据结构（两个有序序列的中位数、数组循环左移）

2-1 两个有序序列的中位数

分数 6

作者 DS课程组

单位 浙江大学

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4

输入样例2:

6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1

解析

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

#define MAXSIZE 100000
typedef int ElemType;
typedef ElemType * list;
typedef struct
{
    ElemType * data;
    int lengh;
    int size;
}SqList;
int main()
{
    SqList L1, L2;
    L1.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L2.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    int n;
    scanf("%d", &n);
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d",&L1.data[i]);
    }
    L1.lengh = n;
    L1.size = MAXSIZE;
    for (i = 0; i < n; i++)
    {
        scanf("%d",&L2.data[i]);
    }
    L2.lengh = n;
    L2.size = MAXSIZE;
    SqList L3;
    L3.data = (ElemType *)malloc(2 * MAXSIZE * sizeof(ElemType));
    L3.lengh = 0;
    L3.size = 2 * MAXSIZE;
    int j = 0, k = 0;
    while (j < L1.lengh && k < L2.lengh)
    {
        if (L1.data[j] < L2.data[k])
        {
            L3.data[L3.lengh]=L1.data[j];
            L3.lengh++;
            j++;
        }
        else
        {
            L3.data[L3.lengh]=L2.data[k];
            L3.lengh++;
            k++;
        }
    }
    if (j < L1.lengh)
    {
        while (j < L1.lengh)
        {
            L3.data[L3.lengh]=L1.data[j];
            L3.lengh++;
            j++;
        }
    }
    if (k < L2.lengh)
    {
        while (k < L2.lengh)
        {
            L3.data[L3.lengh]=L2.data[k];
            L3.lengh++;
            k++;
        }
    }
    int mid = L3.lengh / 2;
    int ans = (L3.data[mid] + L3.data[mid - 1]) / 2;
    printf("%d", ans);
    free(L1.data);
    free(L2.data);
    free(L3.data);
    return 0;
}

注意

在 SqList 结构体中，elem 是一个 指向 ElemType 类型的指针，但它的作用是 指向一块连续的内存空间（动态数组），用于存储顺序表中的数据元素。

具体解释：

1. elem 的本质：elem 被定义为 ElemType * elem;，这是一个指针变量，本身不是数组。但在代码中，通过 malloc 为它分配了一块连续的内存：

   L.elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));

   这行代码会在堆区申请一个能存储 MAXSIZE 个 ElemType 元素的连续空间，elem 指针指向这块空间的首地址。

2. 用法上等同于数组：虽然 elem 是指针，但由于它指向的是连续内存，因此可以像数组一样通过下标访问元素。例如代码中的：

   // 输入元素到顺序表
   for(int i = 0; i < n; i++)
       cin >> L.elem[i];
   
   // 插入元素时移动数据（类似数组操作）
   for(int i = L.length - 1; i >= a - 1; i--)
       L.elem[i + 1] = L.elem[i];

   这里的 L.elem[i] 与数组的访问方式完全一致，本质上是通过指针偏移（elem + i）访问第 i 个元素。

3. 与静态数组的区别：静态数组（如 int arr[100];）的大小在编译时固定，而 elem 指向的是 动态数组（大小由 malloc 的参数决定，这里是 MAXSIZE）。如果需要，还可以通过 realloc 调整其大小（不过本题中 MAXSIZE 固定，未体现此特性）。

总结：

elem 本身是指针，但它指向一块连续的动态分配内存，在功能和用法上完全等同于一个数组，用于存储顺序表中的数据元素。这种设计是顺序表的典型实现方式 —— 通过指针管理动态数组，兼顾灵活性（可动态调整大小）和数组的随机访问特性。

2-2 数组循环左移

分数 6

作者 DS课程组

单位 浙江大学

本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯a**n−1）变换为（a**m⋯a**n−1a0a1⋯a**m−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式:

输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。

输出格式:

在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

8 3
1 2 3 4 5 6 7 8

输出样例：

4 5 6 7 8 1 2 3

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#define MAXSIZE 100
typedef struct {
    ElemType *data;
    int length;
    int size;
}SqList;

void Reverse(SqList *L , int left, int right)
{
    while (left < right)
    {
        ElemType temp = L->data[left];
        L->data[left] = L->data[right];
        L->data[right] = temp;
        left++;
        right--;
    }
}
int main()
{
    SqList L;
    L.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    int n;
    int x;
    scanf("%d %d" , &n , &x);
    L.length = n;
    L.size = MAXSIZE;
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &L.data[i]);
    }
    x = x % n;
    Reverse(&L , 0 , x - 1);
    Reverse(&L , x , n - 1);
    Reverse(&L , 0 , n - 1);
    for (i = 0; i < n; i++)
    {
        printf("%d", L.data[i]);
        if (i != n - 1)
        {
            printf(" ");
        }
    }
    free(L.data);
    return 0;
}

注意

1. 要实现数组的循环左移，且不使用额外数组并尽量减少移动次数，可以采用三次反转的方法。具体步骤如下：

   1. 计算有效移动次数：m = m % n（避免m大于n的情况）。
   2. 反转前m个元素。
   3. 反转剩余n-m个元素。
   4. 反转整个数组。

   这种方法的时间复杂度为O(n)，且只需常数级额外空间。

   代码说明：

   1. 反转函数 reverse：通过双指针交换元素，实现数组指定区间的原地反转。

   2. 主函数逻辑

      ：

      • 读取数组大小 n 和移动位数 m。

      • 计算有效移动次数 m = m % n（处理 m ≥ n 的情况）。

      • 若

        m ≠ 0

        ，执行三次反转操作：

        • 反转前 m 个元素。
        • 反转剩余 n-m 个元素。
        • 反转整个数组。

   3. 输出格式：循环输出数组元素，元素间用空格分隔，结尾无多余空格。

   示例验证：

   输入：

   8 3
   1 2 3 4 5 6 7 8

   处理过程：

   1. 反转前3个：[1,2,3] → [3,2,1] → 数组变为 [3,2,1,4,5,6,7,8]。
   2. 反转后5个：[4,5,6,7,8] → [8,7,6,5,4] → 数组变为 [3,2,1,8,7,6,5,4]。
   3. 反转整个数组：[4,5,6,7,8,1,2,3] → 得到结果。