PTA-学校-数据结构（在指定位置插入元素、集合减法、顺序表（删除））

2-4 在指定位置插入元素

分数 6

作者 张志梅

单位 青岛大学

给出 n 个整数，在指定位置 pos（位置从1起始）前插入给定的值 val，请输出插入后的整数序列。

输入格式:

包含多组测试。第一行会有一个 T 表示组数 (1<=T<=20)，每组测试的第一行输入三个数 n , pos , val，第二行输入n个整数。其中，1<=n<=100，1<=pos<=n+1，1<=val<=100。

输出格式:

每组测试输出包含一行，行末不允许有多余的空格。

输入样例:

2
5 1 4
1 2 3 4 5
6 3 9
2 4 6 8 0 2

输出样例:

4 1 2 3 4 5
2 4 9 6 8 0 2

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#define MAXSIZE 100
typedef struct
{
    ElemType *data;
    int length;
    int size;
} SqList;
int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int n , pos , val;
        scanf("%d %d %d", &n, &pos, &val);
        SqList L;
        L.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
        L.length = n;
        L.size = MAXSIZE;
        int i;
        for (i = 0; i < n; i++)
        {
            scanf ("%d", L.data + i);
        }
        SqList L1;
        L1.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
        L1.length = n + 1;
        L1.size = MAXSIZE;
        for (i = 0; i < n + 1; i++)
        {
            if (i < pos - 1)
            {
                L1.data[i] = L.data[i];
            }
            else if (i == pos - 1)
            {
                L1.data[i] = val;
            }
            else
            {
                L1.data[i] = L.data[i - 1];
            }
        }
        for (i = 0; i < n + 1; i++)
        {
            printf("%d", L1.data[i]);
            if (i != n)
            {
                printf(" ");
            }
            else
            {
                printf("\n");
            }
        }
    }
    
}

注意

用了一个新的顺序表存加了数的新表

读取原始数组元素时，代码为：

scanf("%d", L.data[i]);  // 错误

问题：scanf 的第二个参数需要传入变量的地址（指针），而 L.data[i] 是数组元素的值，不是地址，会导致运行时崩溃（访问非法内存）。应该是：

for (i = 0; i < n; i++)
{
	scanf ("%d", L.data + i);
}

2-5 集合减法

分数 6

作者 朱允刚

单位 吉林大学

给定两个非空集合A和B，集合的元素为30000以内的正整数，编写程序求A-B。

输入格式:

输入为三行。第1行为两个整数n和m，分别为集合A和B包含的元素个数，1≤n, m ≤10000。第2行表示集合A，为n个空格间隔的正整数，每个正整数不超过30000。第3行表示集合B，为m个空格间隔的正整数，每个正整数不超过30000。

输出格式:

输出为一行整数，表示A-B，每个整数后一个空格，各元素按递增顺序输出。若A-B为空集，则输出0，0后无空格。

输入样例:

5 5
1 2 3 4 5
3 4 5 6 7 

输出样例:

1 2 

作者第一次的代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int ElemType;
#define MAXSIZE 10000
typedef struct {
    ElemType *data;
    int length;
} SqList;
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    SqList L1;
    L1.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L1.length = n;
    SqList L2;
    L2.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L2.length = m;
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &L1.data[i]);
    }
    for (i = 0; i < m; i++)
    {
        scanf("%d", &L2.data[i]);
    }
    SqList L3;
    L3.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L3.length = (n > m ? n : m);
    for (i = 0; i < L3.length; i++)
    {
        if (i < n && i < m)
        {
            L3.data[i] = abs(L1.data[i] - L2.data[i]);
        }
        else if (i < n)
        {
            L3.data[i] = -1;
        }
        else
        {
            L3.data[i] = -1;
        }
    }
    for (i = 0; i < L3.length; i++)
    {
        if (L3.data[i] != -1)
        {
            printf("%d ", L3.data[i]);
        }
        else
        {
            printf("0");
        }
    }
    free(L1.data);
    free(L2.data);
    free(L3.data);
    return 0;
}

只能说炸裂，本来信心满满，交上去结果不对。一问豆包，题读错了，难绷。代码也有问题

解析

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

typedef int ElemType;
#define MAXSIZE 10000

typedef struct {
    ElemType *data;
    int length;
} SqList;

// 比较函数用于快速排序
int cmp(const void *a, const void *b) {
    return (*(ElemType*)a - *(ElemType*)b);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 创建三个顺序表
    SqList L1, L2, L3;
    
    // 分配内存
    L1.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L2.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L3.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    
    L1.length = n;
    L2.length = m;
    L3.length = 0;
    
    // 读取集合A
    for (int i = 0; i < n; i++) {
        scanf("%d", &L1.data[i]);
    }
    
    // 读取集合B
    for (int i = 0; i < m; i++) {
        scanf("%d", &L2.data[i]);
    }
    
    // 对L2（集合B）进行排序（二分查找前提）
    qsort(L2.data, L2.length, sizeof(ElemType), cmp);
    
    // 遍历L1（集合A），在L2中二分查找
    for (int i = 0; i < L1.length; i++) {
        ElemType target = L1.data[i];
        int left = 0, right = L2.length - 1;
        int found = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (L2.data[mid] == target) {
                found = 1;
                break;
            } else if (L2.data[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 未在B中找到则加入结果集
        if (!found) {
            L3.data[L3.length++] = target;
        }
    }
    
    // 处理结果
    if (L3.length == 0) {
        printf("0");
    } else {
        // 对结果集排序（使用快速排序）
        qsort(L3.data, L3.length, sizeof(ElemType), cmp);
        
        // 输出结果（最后一个元素后无空格）
        for (int i = 0; i < L3.length; i++) {
            printf("%d ", L3.data[i]);
            if (i < L3.length - 1) {
                printf("");
            }
        }
    }
    
    // 释放内存
    free(L1.data);
    free(L2.data);
    free(L3.data);
    
    return 0;
}

还是用了别的东西，明天再研究一下

2-6 顺序表（删除）

分数 6

作者 邵煜

单位 宁波财经学院

已知一组数据，采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素

输入格式:

输入包含三行数据，第一行是表中元素个数，第二行是顺序表的各个元素，第三行是区间x和y。

输出格式:

删除元素值在[x,y]之间的所有元素后，输出新的顺序表。(最后无空格)

输入样例:

在这里给出一组输入。例如：

10
55 11 9 15 67 12 18 33 6 22
10 20

输出样例:

在这里给出相应的输出。例如：

55 9 67 33 6 22

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct {
    ElemType *data;
    int length;
}SqList;
int main()
{
    int n;
    scanf("%d",&n);
    SqList L;
    L.data=(ElemType *)malloc(n*sizeof(ElemType));
    L.length=n;
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&L.data[i]);
    } 
    int down,up;
    scanf("%d%d",&down,&up);
    SqList L1;
    L1.data=(ElemType *)malloc(n*sizeof(ElemType));
    L1.length=0;
    for(i=0;i<n;i++)
    {
        if(L.data[i] < down || L.data[i] > up)
        {
            L1.data[L1.length]=L.data[i];
            L1.length++;
        }
    }
    for (i=0;i<L1.length;i++)
    {
        printf("%d",L1.data[i]);
        if(i!=L1.length-1)
        {
            printf(" ");
        }
    }
    free(L.data);
    free(L1.data);
    return 0;
}