线性表基本操作
题目1
线性表是最常见和常用的ADT。假设线性表的元素为整数，请基于顺序存储结构实现线性表ADT。
基本功能包括：
（1）建立线性表；
输入有两行，第一行是一个整数n，线性表的长度； 第二行是n和数据元素
（2）插入：
输入两个整数，即元素插入的位置和元素值
（3）删除：
输入一个整数，即要删除的元素
（4）搜索：
输入一个整数，即搜索元素的值
（5）输出：
输出线性表的各个元素，空格分开。
（6）集合的并运算：
输入创建第二个集合（线性表），完成并运算
（7）集合的交运算：
输入创建第二个集合（线性表），完成交运算
（8）合并两个有序线性表：
两个有序线性表，合并后仍然有序
测试数据：
5 //线性表A的长度
1 3 5 7 9 //线性表A的数据
2 10 //表示在第2个位置插入10
10 //表示删除值=10的数据元素
9 //查找元素9
22 / /查找元素22
6 //线性表B的长度
1 2 3 4 5 6
例如:
输入：
5
1 3 5 7 9
2 10
10
9
22
6
1 2 3 4 5 6
输出：
A is created as: 1 3 5 7 9
After inserted A is 1 10 3 5 7 9
After deleted A is 1 3 5 7 9
9 is located at index of 5
22 is not found
B is created as: 1 2 3 4 5 6
A cross B is 1 3 5
A union B is 1 3 5 7 9 2 4 6
A union B in sequence is 1 2 3 4 5 6 7 9
这个题不知道是不是题目不全，第一眼看到的时候一脸懵逼，最后发现，其实就是按照题目给出的样例模拟就行：（1）输入n后，再输入n个数，建立A线性表；（2）输入两个数i和j，表示在A表的第i个位置插入数字j；（3）输入一个数num，在A中删除num；（4）输入两个数，分别寻找其位置；（5）输入m后，再输入m个数，建立A线性表；（6）输出（A并B）的结果；（7）输出（A或B）的结果；（8）从小到大的输出（A或B）的结果。
#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 105
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
const double e=2.71828182845;
const double pi = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int a[n+5];
rep(i,1,n)
{
cin>>a[i];
}
cout<<"A is created as:";
rep(i,1,n)
{
cout<<" "<<a[i];
}
cout<<'\n';
int index,num;
cin>>index>>num;
per(i,index+1,n+1)
{
a[i]=a[i-1];
}
a[index]=num;
cout<<"After inserted A is";
rep(i,1,n+1)
{
cout<<" "<<a[i];
}
cout<<'\n';
int num1;
cin>>num1;
int flag=0;
rep(i,1,n+1)
{
if(num1==a[i])
{
flag=i;
break;
}
}
rep(i,flag,n+1)
{
a[i]=a[i+1];
}
cout<<"After deleted A is";
rep(i,1,n)
{
cout<<" "<<a[i];
}
cout<<'\n';
int num2;
cin>>num2;
cout<<num2<<" ";
flag=0;
rep(i,1,n)
{
if(num2==a[i])
{
flag=i;
break;
}
}
if(flag!=0)
cout<<"is located at index of "<<flag<<'\n';
else
cout<<"is not found"<<'\n';
int num3;
cin>>num3;
flag=0;
cout<<num3<<" ";
rep(i,1,n)
{
if(num3==a[i])
{
flag=i;
break;
}
}
if(flag!=0)
cout<<"is located at index of "<<flag<<'\n';
else
cout<<"is not found"<<'\n';
int m;
cin>>m;
int b[m+5];
rep(i,1,m)
{
cin>>b[i];
}
cout<<"B is created as:";
rep(i,1,m)
{
cout<<" "<<b[i];
}
cout<<'\n';
cout<<"A cross B is";
rep(i,1,n)
{
rep(j,1,m)
{
if(a[i]==b[j])
{
cout<<" "<<a[i];
break;
}
}
}
cout<<'\n';
cout<<"A union B is";
int c[n+m+5];
int k=1;
rep(i,1,n)
{
cout<<" "<<a[i];
c[k]=a[i];
k++;
}
rep(i,1,m)
{
int u=0;
rep(j,1,n)
{
if(b[i]==a[j])
{
u=1;
break;
}
}
if(u==0)
{
c[k]=b[i];
k++;
cout<<" "<<b[i];
}
}
k--;
cout<<'\n';
cout<<"A union B in sequence is";
sort(c+1,c+1+k);
rep(i,1,k)
{
cout<<" "<<c[i];
}
cout<<'\n';
return 0;
}
题目2
线性表是最常见和常用的ADT。假设线性表的元素为整数，请基于单链式存储结构实现线性表ADT。
基本功能包括：
（1）建立线性表；
输入有两行：第一行一个整数，是输入元素的结束标志，例如0，则在输入结束时输入0，就表示输入结束了。
第二行是线性表的各个元素，最后一个是结束标志。
（2）插入：
输入两个整数，即元素插入的位置和元素值
（3）删除：
输入一个整数，即要删除的元素值
（4）搜索：
输入一个整数，即要搜索元素的值
（5）输出：
输出线性表的各个元素，空格分开。
（6）集合的并运算：
输入创建第二个集合（线性表），完成并运算
（7）集合的交运算：
输入创建第二个集合（线性表），完成交运算
（8）合并两个有序线性表：
两个有序线性表，合并后仍然有序
测试数据：
测试样例：
0 //线性表输入结束标志
1 3 5 7 9 0 //线性表A的各个元素，最后是结束标志
2 10 //表示在第2个位置插入10
10 //表示删除值=10的数据元素
9 //查找元素9
22 // 查找元素22
0 //线性表输入结束标志
1 2 3 4 5 6 0 //线性表B的各个元素，最后是结束标志
例如:
输入：
0
1 3 5 7 9 0
2 10
10
9
22
0
1 2 3 4 5 6 0
输出：
A is created as: 1 3 5 7 9
After inserted A is 1 10 3 5 7 9
After deleted A is 1 3 5 7 9
9 is located at index of 5
22 is not found
B is created as: 1 2 3 4 5 6
A cross B is 1 3 5
A union B is 1 3 5 7 9 2 4 6
A union B in sequence is 1 2 3 4 5 6 7 9
这个和上一个题差不多，只是把创建线性表时的输入变了一下，相应的变一下即可。
#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 105
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
const double e=2.71828182845;
const double pi = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=1,m1;
cin>>m1;
int a[100005];
while(1)
{
int k1;
cin>>k1;
if(k1!=m1)
a[n]=k1;
else
break;
n++;
}
n--;
cout<<"A is created as:";
rep(i,1,n)
{
cout<<" "<<a[i];
}
cout<<'\n';
int index,num;
cin>>index>>num;
per(i,index+1,n+1)
{
a[i]=a[i-1];
}
a[index]=num;
cout<<"After inserted A is";
rep(i,1,n+1)
{
cout<<" "<<a[i];
}
cout<<'\n';
int num1;
cin>>num1;
int flag=0;
rep(i,1,n+1)
{
if(num1==a[i])
{
flag=i;
break;
}
}
rep(i,flag,n+1)
{
a[i]=a[i+1];
}
cout<<"After deleted A is";
rep(i,1,n)
{
cout<<" "<<a[i];
}
cout<<'\n';
int num2;
cin>>num2;
cout<<num2<<" ";
flag=0;
rep(i,1,n)
{
if(num2==a[i])
{
flag=i;
break;
}
}
if(flag!=0)
cout<<"is located at index of "<<flag<<'\n';
else
cout<<"is not found"<<'\n';
int num3;
cin>>num3;
flag=0;
cout<<num3<<" ";
rep(i,1,n)
{
if(num3==a[i])
{
flag=i;
break;
}
}
if(flag!=0)
cout<<"is located at index of "<<flag<<'\n';
else
cout<<"is not found"<<'\n';
int m=1,n1;
cin>>n1;
int b[m+5];
while(1)
{
int k1;
cin>>k1;
if(k1!=n1)
b[m]=k1;
else
break;
m++;
}
m--;
cout<<"B is created as:";
rep(i,1,m)
{
cout<<" "<<b[i];
}
cout<<'\n';
cout<<"A cross B is";
rep(i,1,n)
{
rep(j,1,m)
{
if(a[i]==b[j])
{
cout<<" "<<a[i];
break;
}
}
}
cout<<'\n';
cout<<"A union B is";
int c[n+m+5];
int k=1;
rep(i,1,n)
{
cout<<" "<<a[i];
c[k]=a[i];
k++;
}
rep(i,1,m)
{
int u=0;
rep(j,1,n)
{
if(b[i]==a[j])
{
u=1;
break;
}
}
if(u==0)
{
c[k]=b[i];
k++;
cout<<" "<<b[i];
}
}
k--;
cout<<'\n';
cout<<"A union B in sequence is";
sort(c+1,c+1+k);
rep(i,1,k)
{
cout<<" "<<c[i];
}
cout<<'\n';
return 0;
}
题目3
实习目的：熟练掌握链表的建立及基本操作
问题描述：
1）实现链表的排序(升序)
2）实现两个有序链表的合并：A=A∪B，要求合并后仍然有序。
提交前请将所有的提示信息去掉，只保留最后的输出结果。例如运行时：从键盘直接输入：
2 1 2
3 1 2 3
输出结果为：
1
2
3
分别表示第一个链表元素个数为2，元素分别为 1,2 ；第二个链表元素个数为3，元素分别为1,2,3。
例如:
输入：
2 2 1
3 1 2 3
输出：
1
2
3
这个题用链表写会非常麻烦，用数组，合并后去重会更简单些。
#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 105
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
const double e=2.71828182845;
const double pi = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int a[n+1];
rep(i,1,n)
{
cin>>a[i];
}
int m;
cin>>m;
int b[m+1];
rep(i,1,m)
{
cin>>b[i];
}
int c[n+m+5],k=1;
mm(c);
rep(i,1,n)
{
c[k]=a[i];
//cout<<k<<" "<<c[k]<<'\n';
k++;
}
rep(i,1,m)
{
c[k]=b[i];
//cout<<k<<" "<<c[k]<<'\n';
k++;
}
k--;
sort(c+1,c+1+k);
cout<<c[1]<<'\n';
rep(i,2,k)
{
if(c[i]!=c[i-1])
cout<<c[i]<<'\n';
}
return 0;
}
