Skip to content

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;
}