详解版
第1关：删除顺序表中指定值的所有元素
- 任务要求
- 参考答案
- 评论2
- 关卡排行榜
- 任务描述
-
编程要求
- 输入
- 输出
- 测试说明
- 来源
任务描述
本关任务：利用顺序表表示一个包括n个整数的序列，请实现一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法可以删除表中所有值为item的元素。
编程要求
输入
多组数据，每组数据有三行，第一行为顺序表的长度n，第二行为顺序表的n个元素（元素之间用空格分隔），第三行为待删除的元素的值item。当n=0时输入结束。
输出
对于每组数据分别输出一行，依次输出删除值为item的元素后顺序表中的剩余元素，元素之间用空格分隔。
测试说明
平台会对你编写的代码进行测试：
测试输入： 5 44 11 22 33 22 11 6 22 33 11 33 33 55 33 0
预期输出： 44 22 33 22 22 11 55
#include<iostream>
//" iostream：用于处理标准输入输出流，例如cin和cout。
#define MAXSIZE 100
using namespace std;
typedef struct{
int *elem; //存储空间的基地址
int length; //当前长度
}SqList;
void InitList_Sq(SqList &L,int n){
//构造顺序表
L.elem=new int[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
L.length=n; //空表长度为0
}
void DeleteItem(SqList &A,int item){
/**************begin************/
//删除顺序表A中所有值为item的元素
//思路1，找到并记录所有值为item的元素的位置，再输出，比较麻烦
//思路2，找到不为item的值，找到一个存一个，较为简单
//一般来说，用的变量少会简单点，多找规律
int num = 0;
for(int i=0;i<=A.length-1;i++){
if(A.elem[i]!=item){
A.elem[num] = A.elem[i];
num++;
}
}
A.length = num;
/**************end************/
}
void PrintA(SqList A)
{//输出数组元素
for(int i=0;i<A.length-1;i++)
cout<<A.elem[i]<<" ";
cout<<A.elem[A.length-1]<<endl;
}
int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
SqList A;
InitList_Sq(A,n);
for(int i=0;i<n;i++)
cin>>A.elem[i];
int item;
cin>>item;
DeleteItem(A,item);
PrintA(A);
}
return 0;
}第2关：求解两个升序序列的中位数
任务描述
本关任务：一个长度为L(L≥1)的升序序列S，处在第L/2（若为小数则去掉小数后加1）个位置的数称为S的中位数。例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试实现一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
编程要求
输入
多组数据，每组数据有三行，第一行为序列的长度n，第二行为序列A的n个元素，第三行为序列B的n个元素（元素之间用空格分隔）。当n=0时输入结束。
输出
对于每组数据分别输出两个序列的中位数，占一行。
注意 2n 要写成 2*n,小编在这里卡了半个小时，怀疑人生QAQ，还有文章来源：https://www.toymoban.com/news/detail-851307.html
#include <iostream>
using namespace std;
void Input(int a[],int n)
{//读入序列
for(int i=0;i<n;i++)
cin>>a[i];
}
int Search_Mid(int A[],int B[],int n)
{//求解两个升序序列的中位数
/**************begin************/
//分析题目，处在第L/2（若为小数则去掉小数后加1）个位置的数称为S的中位数。
// 式子可以为 (m + n + 1) / 2;但本题为两个等长序列，不用考虑
//思路：拼接并输出一个新的有序序列
int i;
int j;
int c[2*n];
for(i=0;i<n;i++){
c[i] = A[i];
}
for(i=0;i<n;i++){
c[n+i] = B[i];
}
for(i=0;i<2*n-1;i++){
for(int j = i+1;j<=2*n-1;j++){
if(c[i] > c[j]){
int temp = c[i];
c[i] = c[j];
c[j] = temp;
}
}
}
return c[n-1];
/**************end************/
}
int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
int A[n],B[n];
Input(A,n);
Input(B,n);
cout<<Search_Mid(A,B,n)<<endl;
}
return 0;
}也可以参考别人提供的答案，要解析的话扣1（已改）文章来源地址https://www.toymoban.com/news/detail-851307.html
#include<iostream>
using namespace std;
void Input(int t[],int n){
for(int i=0;i<n;i++)
cin>>t[i];
}
void Find(int A[], int B[], int n) { // 定义一个名为Find的函数，接收两个int类型的数组A和B以及一个int类型的n。
int h1=0, e1=n-1, h2=0, e2=n-1; // 初始化四个变量，h1和h2表示数组A的起始和结束位置，e1和e2表示数组B的起始和结束位置。
while(h1<e1&&h2<e2) { // 当两个数组都还有元素未被比较时，循环继续。
int a=(h1+e1)/2; // 找到数组A的中点。
int b=(h2+e2)/2; // 找到数组B的中点。
if(A[a]==B[b]) { // 如果两个中点元素相等。
cout<<A[a]<<endl; // 输出这个元素。
return; // 结束函数。
}
else if(A[a]<B[b]) { // 如果A的中点元素小于B的中点元素。
if((e1-h1)%2==0) h1=a; // 如果A的右半部分已经处理完（即e1-h1是偶数），则新的h1为当前的中点。
else h1=a+1; // 如果A的右半部分还没处理完（即e1-h1是奇数），则新的h1为当前中点+1。
e2=b; // 将e2更新为当前的中点。
}
else if(A[a]>B[b]) { // 如果A的中点元素大于B的中点元素。
if((e2-h2)%2==0) h2=b; // 如果B的右半部分已经处理完（即e2-h2是偶数），则新的h2为当前的中点。
else h2=b+1; // 如果B的右半部分还没处理完（即e2-h2是奇数），则新的h2为当前中点+1。
e1=a; // 将e1更新为当前的中点。
}
}
if(A[e1]<B[e2]) cout<<A[e1]<<endl; // 如果A的最后一个元素小于B的最后一个元素，输出A的最后一个元素。
else cout<<B[e2]<<endl; // 否则，输出B的最后一个元素。
}
int main(){
int n;
while(cin>>n&&n!=0){
int A[1000];
int B[1000];
Input(A,n);
Input(B,n);
Find(A,B,n);
}
return 0;
}到了这里，关于编程题实训-顺序表应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
