1771: [编程入门]链表之节点删除（非链表的三种做法 map）

解题思路:
先分析一下题意，有a,b两个链表，要删除a链表内学号和b链表学号重复的节点，打印剩余节点数和其学号成绩。

因为只有学号和成绩，并且是一一对应的，所以我们可以用map来做，对map的查找和删除都很方便。

第一种方法（map）：

#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
    map<int,int>p;
    int n,m,a,b;
    cin>>n>>m;
    //输入a链表数据 
    for(int i=0; i<n; i++) {
        cin>>a>>b;
        p[a]=b;
    }
    //在b链表输入的过程中进行对a链表的查找和删除操作 
    for(int i=0; i<m; i++) {
        cin>>a>>b;
        p.erase(a);//使用关键字删除
         
        //使用迭代器删除
//      auto t=p.find(a);//先查找 
//      if(t!=p.end())p.erase(t);//存在则删除 
    }
    //打印 
    cout<<p.size()<<endl;
    for(auto i:p) {
        cout<<i.first<<" "<<i.second<<endl;
    }
 
    return 0;
}

如果自己实现Map的映射效果的话，就使用数组int p[10007]，其中下标代表学号，p[学号]上存放成绩，先将数组初始化成-1，表示学号没有使用，当进行查找时，不是-1就说明a链表内存在该学号，重新记为-1表示删除。

第二种方法（数组映射）：

#include <iostream>
#include <cstring>
 
using namespace std;
 
int n,m,a,b,z;//z表示a中需要删除的节点数 
int p[10007];
 
int main() {
    cin>>n>>m;
    memset(p, -1, sizeof(p));//初始化为-1（因为成绩不会有负数）
    //输入a链表数据 
    for(int i=0;i<n;i++){
        cin>>a>>b;
        p[a]=b;
    }
    //输入b链表数据 
    for(int i=0;i<m;i++){
        cin>>a>>b;
        //如果该学号上值不是-1，则记为-1表示删除 
        if(p[a]!=-1)p[a]=-1,z++;
    }
    //打印 
    cout<<n-z<<endl;
    for(int i=0;i<10007;i++){
        if(p[i]!=-1)cout<<i<<" "<<p[i]<<endl;
    }
     
 
    return 0;
}

当然，第二种方法是有缺陷的，这是假定了学号在10007以内，如果学号很大，就不能用数组表示了。

第三种方法，使用结构体，定义结构体数组，结构体内为学号和成绩，这样的缺点就是查找使用的时间较长。

第三种方法（结构体数组）：

#include <iostream>
 
using namespace std;
 
struct pp{
    int x,y;//学号，成绩（成绩为-1表示节点被删除） 
}p[107];
int n,m,a,b,z;//z表示被删除的节点数 
 
void find(int a){
    //查找，如果找到则记成绩为-1，表示删除 
    for(int i=0;i<n;i++){
        if(p[i].x==a)p[i].y=-1,z++;
    }
}
 
int main() {
    cin>>n>>m;
    //输入a链表数据 
    for(int i=0;i<n;i++){
        cin>>p[i].x>>p[i].y;
    }
    //输入b链表数据 
    for(int i=0;i<m;i++){
        cin>>a>>b;
        find(a);//查找的过程中已删除 
    }
     
    cout<<n-z<<endl;
    for(int i=0;i<n;i++){
        //成绩不是-1，则没有被删除 
        if(p[i].y!=-1)cout<<p[i].x<<" "<<p[i].y<<endl;
    }
     
 
    return 0;
}

这三种方法中使用map是最方便的，数组映射比较简洁，结构体数组比较全面。

补充一下map的用法吧。

1，map简介

map是STL的一个关联容器，它提供一对一的hash。

第一个可以称为关键字(key)，每个关键字只能在map中出现一次；

第二个可能称为该关键字的值(value)；

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的，后边我们会见识到有序的好处。比如一个班级中，每个学生的学号跟他的姓名就存在著一对一映射的关系。

2，查找元素,

当所查找的关键key出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置

iter = mapStudent.find("123");

if(iter != mapStudent.end())

       cout<<"Find, the value is"<

else

   cout<<"Do not Find"<<endl;

3，刪除与清空元素,

//迭代器刪除

iter = mapStudent.find("123");

mapStudent.erase(iter);

//用关键字刪除

int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0

//用迭代器范围刪除 : 把整个map清空

mapStudent.erase(mapStudent.begin(), mapStudent.end());

//等同于mapStudent.clear()

4，map的大小,

在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数，用法如下：

int nSize = mapStudent.size();

5，map的基本操作函数：

     C++ maps是一种关联式容器，包含“关键字/值”对

     begin()         返回指向map头部的迭代器

     clear(）        删除所有元素

     count()         返回指定元素出现的次数, (帮助评论区理解： 因为key值不会重复，所以只能是1 or 0)

     empty()         如果map为空则返回true

     end()           返回指向map末尾的迭代器

     equal_range()   返回特殊条目的迭代器对

     erase()         删除一个元素

     find()          查找一个元素

     get_allocator() 返回map的配置器

     insert()        插入元素

     key_comp()      返回比较元素key的函数

     lower_bound()   返回键值>=给定元素的第一个位置

     max_size()      返回可以容纳的最大元素个数

     rbegin()        返回一个指向map尾部的逆向迭代器

     rend()          返回一个指向map头部的逆向迭代器

     size()          返回map中元素的个数

     swap()           交换两个map

     upper_bound()    返回键值>给定元素的第一个位置

     value_comp()     返回比较元素value的函数

总结节选自 C++ map用法总结（整理）