指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:18701

签 名:

数学改变科学,科学改变世界

等  级
排  名 11
经  验 21312
参赛次数 49
文章发表 119
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:
先分析一下题意,有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用法总结(整理)


 

0.0分

3 人评分

  评论区