codeup7.3 偷懒导致的水题

问题 B: C语言-链表排序

时间限制:1 Sec内存限制:128 MB
提交:146解决:114
[​​​提交​​​][​​状态​​​][​​讨论版​​][命题人:外部导入]

题目描述

已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

输入

第一行，a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成

输出

按照学号升序排列的数据

样例输入

2 3 5 100 6 89 3 82 4 95 2 10

样例输出

2 10 3 82 4 95 5 100 6 89

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;

struct Node
{
  int sno;
  int score;
}node[N];

bool cmp(Node n1,Node n2){
  return n1.sno<n2.sno;
}

int main(){
  int m,n;
  while(cin>>m>>n){
    for(int i=0;i<m+n;i++){
      cin>>node[i].sno>>node[i].score;
    }
    sort(node,node+m+n,cmp);
    for(int i=0;i<m+n;i++){
      cout<<node[i].sno<<" "<<node[i].score<<endl;
    }
  }
  return 0;
}

问题 C: 最快合并链表(线性表)

时间限制:1 Sec内存限制:128 MB
提交:110解决:91
[​​​提交​​​][​​状态​​​][​​讨论版​​][命题人:外部导入]

题目描述

知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

输入

m=5

3 6 1 3 5

n=4.

7 10 8 4

输出

3 6 1 3 5 7 10 8 4

样例输入

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

样例输出

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

#include<iostream>
using namespace std;
int a[100000];
int main(){
  int m;
  while(cin>>m){
    int index=0;
    while(m--){
      cin>>a[index++];
    }
    cin>>m;
    while(m--){
      cin>>a[index++];
    }
    for(int i=0;i<index;i++){
      cout<<a[i]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

问题 D: 链表查找(线性表)

时间限制:1 Sec内存限制:128 MB
提交:117解决:84
[​​​提交​​​][​​状态​​​][​​讨论版​​][命题人:外部导入]

题目描述

线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：

（1） 用最少时间在表中查找数值为x的元素。

（2） 若找到将其与后继元素位置相交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。

输入

输入：x=3

输入长度：9

输入数据：2 3 5 7 12 15 17 23 45

输出

相同元素为：3

交换后的链表为：2 5 3 7 12 15 17 23 45

样例输入

4 9 2 3 5 7 12 15 17 23 45

样例输出

no 2 3 4 5 7 12 15 17 23 45

#include<iostream>
#include <vector>
using namespace std;

int main(){
  vector<int> vi;
  int x,n,m;
  while(cin>>x){
    vi.clear();
    cin>>n;
    while(n--){
      cin>>m;
      vi.push_back(m);
    }
    int i;
    for(i=0;i<vi.size();i++){
      if(vi[i]==x){
        cout<<x<<endl;
        swap(vi[i],vi[i+1]);
        break;
      }else{
        if(x<vi[i]){
          cout<<"no\n";
          vi.insert(vi.begin()+i,x);
          break;
        }
      }
    }
    for(int i=0;i<vi.size();i++){
      cout<<vi[i]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

问题 E: 算法2-24 单链表反转

时间限制:10 Sec内存限制:128 MB
提交:161解决:91
[​​​提交​​​][​​状态​​​][​​讨论版​​][命题人:外部导入]

题目描述

根据一个整数序列构造一个单链表，然后将其反转。

例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2

输入

输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开

输出

针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开

如果链表为空，则只输出一行，list is empty

样例输入

5 1 2 3 4 5 0

样例输出

1 2 3 4 5 5 4 3 2 1 list is empty

#include<iostream>
using namespace std;
int main(){
  int n;
  int a[100000];
  while(cin>>n){
    if(n==0){
      cout<<"list is empty\n";
    }else{
      for(int i=0;i<n;i++){
        cin>>a[i];
        cout<<a[i]<<" ";
      }
      cout<<endl;
      for(int i=n-1;i>=0;i--){
        cout<<a[i]<<" ";
      }
      cout<<endl;
    }
  }
  return 0;
}

问题 F: 算法2-25 有序单链表删除重复元素

时间限制:30 Sec内存限制:128 MB
提交:145解决:83
[​​​提交​​​][​​状态​​​][​​讨论版​​][命题人:外部导入]

题目描述

根据一个递增的整数序列构造有序单链表，删除其中的重复元素

输入

输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开

输出

针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开

如果链表为空，则只输出一行，list is empty

样例输入

5 1 2 3 4 5 5 1 1 2 2 3 0

样例输出

1 2 3 4 5 1 2 3 4 5 1 1 2 2 3 1 2 3 list is empty

#include<iostream>
#include<set>
using namespace std;
int main(){
  set<int> se;
  int n;
  int a[100000];
  while(cin>>n){
    se.clear();
    if(n==0){
      cout<<"list is empty\n";
      continue;
    }
    for(int i=0;i<n;i++){
      cin>>a[i];
      se.insert(a[i]);
      cout<<a[i]<<" ";
    }
    cout<<endl;
    for(set<int>::iterator it=se.begin();it!=se.end();it++){
      cout<<*it<<" ";
    }
    cout<<endl;
  }
  return 0;
}