11203: 【原1203】link
题目
题目描述
author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1203
Description
将两个线性表合并成为一个线性表。
Input Format
输入文件包括四行。
第一行包括一个字符串，有三种情况：int、char、double，代表线性表的类型。
第二行包括两个正整数n,m. (1<=n,m<=10000)
第三行包括n个用空格分开的数据，内容可能是整形，浮点或者字符，由第一行的内容决定，代表第一个线性表的元素。
第四行包括m个用空格分开的数据，内容可能是整形，浮点或者字符，由第一行的内容决定，代表第二个线性表的元素。
Output Format
输出文件包括一行内容，其中每个数据用空格隔开，代表合并后线性表的元素。
Sample Input
int
3 3
1 4 6
29 75 1
Sample Output
1 4 6 29 75 1
Limits
1.保证每个数据分别不超过int,char,double的范围。
2.请用一个过程或重载“+”将两个线性表合成为一个新的线性表，否则代码分给0分。（使用重载运算符的有额外加分）
BugenZhao's solution
//
// Created by BugenZhao on 2019/3/16.
//
// 简单线性表实现
#include <iostream>
#include <string>
using namespace std;
template<typename Item>
class Table {
int size;
int i;
Item *items;
public:
explicit Table(int size) {
this->size = size;
i = 0;
items = new Item[size]{};
}
void add(const Item &item) {
items[i++] = item;
}
virtual ~Table() {
delete[] items;
}
friend ostream &operator<<(ostream &os, const Table &table) {
for (int i = 0; i < table.size; i++) {
os << table.items[i] << ' ';
}
return os;
}
friend Table operator+(const Table &lhs, const Table &rhs) {
Table ret(lhs.size + rhs.size);
for (int i = 0; i < lhs.size; i++) {
ret.add(lhs.items[i]);
}
for (int i = 0; i < rhs.size; i++) {
ret.add(rhs.items[i]);
}
return ret;
}
};
int main() {
string typeName;
int n, m;
cin >> typeName >> n >> m;
if (typeName == "int") {
Table<int> tableA(n), tableB(m);
int tmp;
for (int i = 0; i < n; ++i) {
cin >> tmp;
tableA.add(tmp);
}
for (int i = 0; i < m; ++i) {
cin >> tmp;
tableB.add(tmp);
}
cout << (tableA + tableB) << endl;
} else if (typeName == "char") {
Table<char> tableA(n), tableB(m);
char tmp;
for (int i = 0; i < n; ++i) {
cin >> tmp;
tableA.add(tmp);
}
for (int i = 0; i < m; ++i) {
cin >> tmp;
tableB.add(tmp);
}
cout << (tableA + tableB) << endl;
} else if (typeName == "double") {
Table<double> tableA(n), tableB(m);
double tmp;
for (int i = 0; i < n; ++i) {
cin >> tmp;
tableA.add(tmp);
}
for (int i = 0; i < m; ++i) {
cin >> tmp;
tableB.add(tmp);
}
cout << (tableA + tableB) << endl;
}
return 0;
}
ligongzzz's solution
#include "iostream"
#include "cstring"
using namespace std;
template <class T>
class myLink {
public:
T data;
myLink *next = nullptr;
};
template <class T>
class mySheet {
public:
myLink<T> *head;
myLink<T> *rear;
mySheet() {
head = new myLink<T>;
rear = head;
}
mySheet(T data) {
head = new myLink<T>;
head->next = new myLink<T>;
head->next->data = data;
rear = head->next;
}
~mySheet() {
for (auto p = head; p;) {
auto temp = p->next;
if (p == rear) {
delete p;
break;
}
delete p;
p = temp;
}
}
//复制构造函数
mySheet(const mySheet<T> &b) {
head = new myLink<T>;
for (auto p1 = head, p2 = b.head; p2->next != nullptr;) {
p1->next = new myLink<T>;
p1->next->data = p2->next->data;
p1 = p1->next;
p2 = p2->next;
rear = p1;
}
}
//重载等号
mySheet<T>& operator=(const mySheet<T> &b) {
head = new myLink<T>;
for (auto p1 = head, p2 = b.head; p2->next != nullptr;) {
p1->next = new myLink<T>;
p1->next->data = p2->next->data;
p1 = p1->next;
p2 = p2->next;
rear = p1;
}
return *this;
}
void append(T b) {
rear->next = new myLink<T>;
rear = rear->next;
rear->data = b;
}
//重载加号
mySheet<T> operator+(const mySheet<T> &b) const {
mySheet<T> temp = *this;
mySheet<T> tempAdd = b;
temp.rear->next = tempAdd.head->next;
return temp;
}
//打印
void print() {
for (auto p = head;; ) {
if (p->next == nullptr) break;
if (p != head) cout << " ";
cout << p->next->data;
p = p->next;
}
}
};
int main() {
char type[10];
int num1, num2;
cin >> type;
cin >> num1 >> num2;
if (strcmp(type, "int") == 0) {
mySheet<int> a, b;
for (int i = 0; i < num1; i++) {
int temp;
cin >> temp;
a.append(temp);
}
for (int i = 0; i < num2; i++) {
int temp;
cin >> temp;
b.append(temp);
}
mySheet<int> c;
c = a + b;
c.print();
}
if (strcmp(type, "char") == 0) {
mySheet<char> a, b;
for (int i = 0; i < num1; i++) {
char temp;
cin>>temp;
a.append(temp);
}
for (int i = 0; i < num2; i++) {
char temp;
cin >> temp;
b.append(temp);
}
mySheet<char> c;
c = a + b;
c.print();
}
if (strcmp(type, "double") == 0) {
mySheet<double> a, b;
for (int i = 0; i < num1; i++) {
double temp;
cin >> temp;
a.append(temp);
}
for (int i = 0; i < num2; i++) {
double temp;
cin >> temp;
b.append(temp);
}
mySheet<double> c;
c = a + b;
c.print();
}
return 0;
}
Neight99's solution
#include <cstring>
#include <iostream>
using namespace std;
template <class T>
class seqList {
private:
T *data;
int Length;
int maxSize;
void doubleSpace();
public:
seqList(int initSize = 10);
seqList(const seqList<T> &);
~seqList();
int length() const;
void add(const T &x);
void traverse() const;
seqList<T> operator+(seqList<T> &);
seqList<T> &operator=(const seqList<T> &);
T &operator[](int);
};
template <class T>
void seqList<T>::doubleSpace() {
T *tmp = data;
maxSize *= 2;
data = new T[maxSize];
for (int i = 0; i < Length; ++i) {
data[i] = tmp[i];
}
delete[] tmp;
}
template <class T>
seqList<T>::seqList(int initSize) {
data = new T[initSize];
Length = 0;
maxSize = initSize;
}
template <class T>
seqList<T>::~seqList() {
delete[] data;
}
template <class T>
int seqList<T>::length() const {
return Length;
}
template <class T>
void seqList<T>::add(const T &x) {
if (Length == maxSize) {
doubleSpace();
}
data[Length] = x;
Length++;
}
template <class T>
void seqList<T>::traverse() const {
for (int i = 0; i < Length - 1; i++) {
cout << data[i] << ' ';
}
cout << data[Length - 1];
}
template <class T>
seqList<T> seqList<T>::operator+(seqList<T> &right) {
seqList<T> tmp(this->length() + right.length());
for (int i = 0; i < this->length(); i++) {
tmp.add(data[i]);
}
for (int i = 0; i < right.length(); i++) {
tmp.add(right[i]);
}
return tmp;
}
template <class T>
T &seqList<T>::operator[](int x) {
return data[x];
}
template <class T>
seqList<T>::seqList(const seqList<T> &right) {
Length = right.Length;
maxSize = right.maxSize;
data = new T[maxSize];
for (int i = 0; i < maxSize; i++) {
data[i] = right.data[i];
}
}
template <class T>
seqList<T> &seqList<T>::operator=(const seqList<T> &right) {
if (&right != this) {
delete[] data;
Length = right.Length;
maxSize = right.maxSize;
data = new T[maxSize];
for (int i = 0; i < Length; i++) {
data[i] = right.data[i];
}
}
return *this;
}
int main() {
char type[50];
int l1, l2;
cin >> type >> l1 >> l2;
if (strcmp(type, "int") == 0) {
seqList<int> vec1, vec2, vec3;
int tmp;
for (int i = 0; i < l1; ++i) {
cin >> tmp;
vec1.add(tmp);
}
for (int i = 0; i < l2; ++i) {
cin >> tmp;
vec2.add(tmp);
}
vec3 = vec1 + vec2;
vec3.traverse();
}
if (strcmp(type, "double") == 0) {
seqList<double> vec1, vec2, vec3;
double tmp;
for (int i = 0; i < l1; ++i) {
cin >> tmp;
vec1.add(tmp);
}
for (int i = 0; i < l2; ++i) {
cin >> tmp;
vec2.add(tmp);
}
vec3 = vec1 + vec2;
vec3.traverse();
}
if (strcmp(type, "char") == 0) {
seqList<char> vec1, vec2, vec3;
char tmp;
for (int i = 0; i < l1; ++i) {
cin >> tmp;
vec1.add(tmp);
}
for (int i = 0; i < l2; ++i) {
cin >> tmp;
vec2.add(tmp);
}
vec3 = vec1 + vec2;
vec3.traverse();
}
return 0;
}
q4x3's solution
/**
* 链表合并
**/
#include <iostream>
using namespace std;
template <typename T>
struct node {
node *next;
T data;
};
template <class T>
class list {
private:
node<T> *head, *rear;
void init() {
head = rear = new node<T>;
}
public:
list() {init();}
list(const list &obj) {
node<T> *p = obj.head->next;
while(p != NULL) {
node<T> *q = new node<T>;
q->data = p->data;
rear->next = q;
rear = q;
p = p->next;
}
}
~list() {
node<T> *p = head->next;
while(p != NULL) {
node<T> *q = p;
p = p->next;
delete q;
}
delete head;
}
void input(int n) {
T tmp;
for(int i = 0;i < n;++ i) {
cin >> tmp;
node<T> *p;
p = new node<T>;
p->data = tmp;
rear->next = p;
rear = p;
}
rear->next = NULL;
return;
}
void output() {
node<T> *p = head->next;
while(p != NULL) {
cout << p->data << " ";
node<T> *q = p;
p = p->next;
}
return;
}
void copy(const list &obj) {
node<T> *p = obj.head->next;
while(p != NULL) {
node<T> *q = new node<T>;
q->data = p->data;
rear->next = q;
rear = q;
p = p->next;
}
rear->next = NULL;
}
list<T> operator+ (const list<T> &obj) {
list<T> L;
node<T> *p1 = head->next;
while(p1 != NULL) {
node<T> *q1 = new node<T>;
q1->data = p1->data;
L.rear->next = q1;
L.rear = q1;
p1 = p1->next;
}
node<T> *p2 = obj.head->next;
while(p2 != NULL) {
node<T> *q2 = new node<T>;
q2->data = p2->data;
L.rear->next = q2;
L.rear = q2;
p2 = p2->next;
}
L.rear->next = NULL;
return L;
}
};
int main() {
char s[10];
cin >> s;
int n, m;
if(s[0] == 'i') {
list<int> L1, L2, L;
cin >> n >> m;
L1.input(n); L2.input(m);
L.copy(L1 + L2);
L.output();
}
if(s[0] == 'c') {
list<char> L1, L2, L;
cin >> n >> m;
L1.input(n); L2.input(m);
L.copy(L1 + L2);
L.output();
}
if(s[0] == 'd') {
list<double> L1, L2, L;
cin >> n >> m;
L1.input(n); L2.input(m);
L.copy(L1 + L2);
L.output();
}
cout << endl;
return 0;
}
satgo1546's solution
#include <cstdio>
using namespace std;
int a[20006];
char b[20006];
double c[20006];
char t[42];
int n;
// 使用重载运算符的有额外加分（迫真）
class L {
public:
bool operator+(char t) {
if (t == 'i') {
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
} else if (t == 'c') {
for (int i = 0; i < n; i++) {
getchar();
b[i] = getchar();
putchar(b[i]);
putchar(i == n - 1 ? '\n' : ' ');
}
} else {
for (int i = 0; i < n; i++) {
scanf("%lf", &c[i]);
printf("%g%c", c[i], i == n - 1 ? '\n' : ' ');
}
}
return true;
}
};
int main(int argc, char *argv[]) {
scanf(" %s %d%d", &t, &argc, &n);
n += argc;
L l;
argc = l + t[0];
return argc - 1;
}
skyzh's solution
#include <iostream>
#include <cstring>
using namespace std;
template <typename T>
struct List {
T data[20000];
int cap;
};
template <typename T>
List<T> operator+ (const List<T> & a, const List<T> & b) {
List<T> c;
int i;
for (i = 0; i < a.cap; i++) {
c.data[i] = a.data[i];
}
for (int j = 0; j < b.cap; i++, j++) {
c.data[i] = b.data[j];
}
c.cap = a.cap + b.cap;
return c;
}
template <typename T>
void run() {
int a, b;
cin >> a >> b;
cin.get();
List<T> La, Lb;
La.cap = a;
Lb.cap = b;
for (int i = 0; i < a; i++) cin >> La.data[i];
for (int i = 0; i < b; i++) cin >> Lb.data[i];
List<T> Lc = La + Lb;
for (int i = 0; i < a + b; i++) cout << Lc.data[i] << " ";
cout << endl;
}
int main() {
char t[100];
cin >> t;
if (strcmp(t, "int") == 0) run<int>();
if (strcmp(t, "char") == 0) run<char>();
if (strcmp(t, "double") == 0) run<double>();
return 0;
}
victrid's solution
#include <iostream>
using namespace std;
template <typename T>
struct uzel {
uzel<T>* next;
uzel<T>* last;
T value;
uzel(T& nos) {
last = nullptr;
next = nullptr;
value = nos;
}
uzel() {
last = nullptr;
next = nullptr;
}
};
template <typename T>
class linlist {
template <typename Ty>
friend linlist<Ty> operator+(linlist<Ty>& lin1, linlist<Ty>& lin2);
template <typename Ty>
friend ostream& operator<<(ostream& os, const linlist<Ty>& l);
private:
uzel<T>* start;
uzel<T>* end;
public:
linlist<T>* operator+=(T var) {
uzel<T>* temp = new uzel<T>(var);
end->last->next = temp;
end->last = temp;
temp->next = end;
return this;
}
linlist() {
start = new uzel<T>;
end = new uzel<T>;
start->next = end;
end->last = start;
}
linlist(linlist<T>& l) {
start = new uzel<T>;
end = new uzel<T>;
start->next = end;
end->last = start;
for (uzel<T>* ptr = l.start->next; ptr != l.end; ptr = ptr->next) {
*this += ptr->value;
}
}
};
template <typename T>
ostream& operator<<(ostream& os, const linlist<T>& l) {
uzel<T>* ptr = l.start->next;
while (ptr != l.end) {
if (ptr != l.start->next)
os << ' ';
os << ptr->value;
ptr = ptr->next;
}
return os;
}
template <typename T>
linlist<T> operator+(linlist<T>& lin1, linlist<T>& lin2) {
linlist<T> ans(lin1);
for (uzel<T>* ptr = lin2.start->next; ptr != lin2.end; ptr = ptr->next)
ans += ptr->value;
return ans;
}
template <typename T>
void process() {
int n, m;
cin >> n >> m;
T proc;
linlist<T> lin1, lin2;
for (int i = 0; i < n; i++) {
cin >> proc;
lin1 += proc;
}
for (int i = 0; i < m; i++) {
cin >> proc;
lin2 += proc;
}
cout << (lin1 + lin2);
}
int main() {
char type[7];
cin >> type;
switch (type[0]) {
case 'd':
process<double>();
break;
case 'c':
process<char>();
break;
case 'i':
process<int>();
}
return 0;
}
yyong119's solution
#include <iostream>
using namespace std;
const int MAX_N = 10005;
int n, m;
class op {
public:
int a[MAX_N << 1];
double b[MAX_N << 1];
char c[MAX_N << 5];
};
op operator+(op p, op q) {
op tmp;
for (int i = 1; i <= n; ++i) {
tmp.a[i] = p.a[i];
tmp.b[i] = p.b[i];
tmp.c[i] = p.c[i];
}
for (int i = 1; i <= m; ++i) {
tmp.a[i + n] = q.a[i];
tmp.b[i + n] = q.b[i];
tmp.c[i + n] = q.c[i];
}
return tmp;
}
int main() {
ios::sync_with_stdio(false);
char tmp[10];
cin >> tmp;
cin >> n >> m;
op p, q, r;
switch (tmp[0]) {
case 'i':
for (int i = 1; i <= n; ++i) cin >> p.a[i];
for (int i = 1; i <= m; ++i) cin >> q.a[i];
r = p + q;
for (int i = 1; i <= n + m; ++i) cout << r.a[i] << " ";
break;
case 'd':
for (int i = 1; i <= n; ++i) cin >> p.b[i];
for (int i = 1; i <= m; ++i) cin >> q.b[i];
r = p + q;
for (int i = 1; i <= n + m; ++i) cout << r.b[i] << " ";
break;
case 'c':
for (int i = 1; i <= n; ++i) cin >> p.c[i];
for (int i = 1; i <= m; ++i) cin >> q.c[i];
r = p + q;
for (int i = 1; i <= n + m; ++i) cout << r.c[i] << " ";
break;
}
return 0;
}
Zsi-r's solution
//NO.14的<>
//operato+不返回引用&
#include <iostream>
#include <cstring>
using namespace std;
template <class elemType> class mylist;
template <class elemType> mylist<elemType> operator+(const mylist<elemType> &l1,const mylist<elemType> &l2);
template<class elemType>
class mylist
{
friend mylist<elemType> operator+<>(const mylist &l1,const mylist &l2);
public:
elemType *data;
int size;
mylist(int initSize=1)
{
size=initSize;
data = new elemType[size];
}
mylist(const mylist<elemType> &x);//拷贝构造函数
mylist &operator=(const mylist &x);//赋值重载
~mylist(){delete []data;size=0;}
};
template<class elemType>//赋值重载
mylist<elemType> &mylist<elemType>::operator=(const mylist<elemType> &x)
{
if (this == &x) return *this;
size=x.size;
delete []data;
data= new elemType[size];
for(int i=0;i<size;i++)data[i]=x.data[i];
return *this;
}
template<class elemType>//拷贝构造函数
mylist<elemType>::mylist(const mylist<elemType> &x)
{
size=x.size;
elemType *data = new elemType[size];
for(int i=0;i<size;i++)data[i]=x.data[i];
}
template<class elemType>
mylist<elemType> operator+(const mylist<elemType> &l1,const mylist<elemType> &l2)
{
int i,j;
mylist<elemType> l3(l1.size+l2.size);
l3.size=l1.size+l2.size;
for (i=0;i<l1.size;i++)l3.data[i]=l1.data[i];
for (j=0;j<l2.size;j++)l3.data[i+j]=l2.data[j];
return l3;
}
int main()
{
char type[10];
int len1,len2;
cin >> type;
cin >> len1 >> len2;
if (!strcmp(type,"int"))
{
mylist<int> list1(len1),list2(len2),list3(len1+len2);
for (int i=0;i<len1;i++)cin>>list1.data[i];list1.size=len1;
for (int i=0;i<len2;i++)cin>>list2.data[i];list2.size=len2;
list3 = list1+list2;
for (int i=0;i<list3.size;i++)
cout << list3.data[i]<<' ';
}
else if (!strcmp(type,"double"))
{
mylist<double> list1(len1),list2(len2),list3(len1+len2);
for (int i=0;i<len1;i++)cin>>list1.data[i];list1.size=len1;
for (int i=0;i<len2;i++)cin>>list2.data[i];list2.size=len2;
list3 = list1+list2;
for (int i=0;i<list3.size;i++)
cout << list3.data[i]<<' ';
}
else if (!strcmp(type,"char"))
{
mylist<char> list1(len1),list2(len2),list3(len1+len2);
for (int i=0;i<len1;i++)cin>>list1.data[i];list1.size=len1;
for (int i=0;i<len2;i++)cin>>list2.data[i];list2.size=len2;
list3 = list1+list2;
for (int i=0;i<list3.size;i++)
cout << list3.data[i]<<' ';
}
return 0;
}