20144月金山WPS实习生C++笔试题
今天无聊就写了出来，仅供参考，大题都是不一样的，准备参加笔试的同学别以为是一样的哈
发现自己手写效果真的挺差的，而且不能调试BUG真心挺多的，本来还以为我自己做的挺不错的，但是真正写出来，我去啊，发现BUG一堆堆的啊！
//金山WPS C++面试题
/*完成下列函数的功能，可以自己重新设计类，也可以改名etc
1.可以插入学生
2.可以删除学生
3.可以找出成绩最高的N位学生
struct Student{
int id;
string name;
double score;
}
class StudentMrg{
public:
Student[100];
bool InsertStudent(Student *s);//插入学生
bool DeleterStudent(const string &name);
student FindByName(const string *name);//
vector<student> GetNTop(Student *s,int n);//最高分的n个
StudentMrg();
~StudentMrg();
}
*/
/*
我是用单链表做的，因为更容易增删
*/
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
struct student{//直接做成嵌套类，更安全,但是测试不方便，还是弄到外面吧
string name;
double score;
struct student *next;//我去啊，我笔试好像写出了struct *student next了，郁闷
};
class StudentMrg{
//public://要放到前面，前置声明
private:
student *front;//头指针
student *rear;//尾指针,指向最后一个元素的下一个节点
int size;//学生人数
public:
StudentMrg();
~StudentMrg();
bool Insert(student *s);
bool Delete(const string &name);
bool FindByName(const string &name);//发现这里最好返回一个副本,//发现直接返回引用也不错
//发现返回一个结构好郁闷的样子，因为最后那个构造怎么写？
//结构体是可以返回，但是如果找不到的时候该返回什么？
//返回一个bool值吧
vector<student> GetNTop(int n)const;
void showStudentMrg()
{
student *p=front;
cout<<"size="<<size<<endl;
while(p!=rear)//不能写成while(p),因为rear是指向最后一个的下一个,p!=null就行，
{
cout<<"name:"<<p->name<<" ,score:"<<p->score<<endl;
p=p->next;
}
cout<<"over"<<endl;
};//这个是我方便测试
};
//实现
StudentMrg::StudentMrg()//建立新链表
{
front=rear=nullptr;
size=0;
};
StudentMrg::~StudentMrg()//要逐一节点删除
{
student *p=front;
while(p)//当p！=nullptr时才执行删除，这样保证了空链表不会删除失败
{
front=p->next;
delete p;
p=front;
}
};
//插入我的思想是新建节点插入，并根据成绩高低进行排序插入,这样方便查找最高分的人
bool StudentMrg::Insert(student *s)
{
bool flag=false;//判断是否成功插入了
if(!front)//当是第一次插入新数据时,//即当front=nullptr时
{
student *newS=new student;
front=newS;
newS->name=s->name;
newS->score=s->score;
//rear=newS->next;//最好把newS->next指向尾指针
rear=front->next;
size++;//学生数-1；
flag=true;
return flag;
}
else//不是第一次插入时
{
//啊，忘记判断在头部插入的时候了啊，我去啊
//当要在头部插入数据时
if(s->score>=front->score)
{
student *insertS=new student;//因为析构函数用了delete，节点值都要new
insertS->name=s->name;
insertS->score=s->score;
insertS->next=front;//使新节点成为新头部
front=insertS;
size++;
flag=true;
return flag;
}
//当不是头部插入时
//*******//为何新建了这两个变量，在监视里面找不到呢？？
student *find=front;//用于查找插入的位置
student *temp=find;//用于记录find的上一个值
/*testing 明明有，为何监视找不到？？？？
cout<<"front:"<<front<<endl;
cout<<"find:"<<find<<endl;
cout<<"temp:"<<temp<<endl;
*/
/*
按分数从低到高插入
*/
while(find!=rear)//当find所指向的下一个指针不是尾指针时//find->next!=rear//error
{ //应当是find不是rear是，否则的话，例如，插入70到20,100的时候
//find指向100时，还没进来判断就结束了while
//cout<<"find->next:"<<find->next<<endl;
//判断要注意了，当上一个<=s->score的时候，就应该插入了
//这里默认是在链表中间插入
if((temp->score>s->score)&&((find->score==s->score)||(find->score<s->score)))
{
student *insert=new student;
insert->name=s->name;//值复制过来
insert->score=s->score;
//链表插入，先断开后面的，再连接前面的
insert->next=find;
temp->next=insert;
size++;
flag=true;
return true;
}
//倘若不是
temp=find;//先保存上一个值
find=find->next;//顺移,指向下一个
}
//在最后面插入时
if(find==rear)//这时，find指向rear的前一个节点
{
student *endInsert=new student;
endInsert->name=s->name ;
endInsert->score=s->score;
temp->next=endInsert;//改变尾指针
rear=endInsert->next;
size++;
flag=true;
return flag;
}
}
return flag;
//发现写在卷子上就会忽略很多细节的东西，真郁闷。
};
bool StudentMrg::Delete(const string &name)
{
student *find=front;//用于存储找到的那个节点
student *temp=find;//用于记录find的上一个节点
bool flag=false;
if(front->name==name)//如果是头指针
{
front=front->next;//头指针后移
delete temp;
size--;
flag=true;
return flag;
}
while(find!=rear)//当find->不为null时，即不==rear,即是在中间删除时
{ //直接领find不为rear即可，这样即便删除最后一个，此时，find==rear
//因为temp保存了上一个值，temp->next=find->next 依然会令上一个指向rear指针
if(find->name==name)//如果找到，这里假设不存在同名
{
temp->next=find->next;//直接更改指针
delete find;
size--;
flag=true;
return flag;
}
temp=find;
find=find->next;
}
//如果是rear的前一个节点,发现删除的时候，前一句可以正确地删除rear的前一个节点
//但是Insert就不行了，因为有个if判断语句
/*if(find->next)
{
}*/
cout<<"no such student who's name is "<<name<<endl;
return flag;
};
bool StudentMrg::FindByName(const string &name)
{
student *find=front;
while(find!=rear)//
{
if(find->name==name)
{
/*
student target;
target.name=find->score;
target.score=find->score;
return target;//find;//student{nname,score,nullptr};
//这个结构体是临时的，返回会不会出问题呢？
*/
cout<<"Had found!"<<" name:"<<find->name<<" score:"<<find->score<<endl;
return true;
}
find=find->next;
}
cout<<"no such man,can't find!"<<endl;
//return *rear;
return false;
}
//说真的，感觉最后这个最容易啊
vector<student> StudentMrg::GetNTop(int n)const//GetNTop(const StudentMrg *s,int n)
{
bool flag=false;
if(n>size)
cout<<"OO,no so many people!Are you king me ??"<<endl;
else
{
flag=true;
student *p=front;
vector<student> arr;
//vector<student>::iterator it=arr.begin();//用迭代器,发现不太会用0.0
while(n--)
{
//cout<<"in"<<endl;
student s={p->name,p->score,nullptr};
arr.push_back(s);
p=p->next;//居然写出了P++,真是人才啊..
}
/*/test
vector<student>::iterator it;
for(it=arr.begin();it!=arr.end();++it)
cout<<it->name<<" "<<it->score<<endl;
cout<<"OKK"<<endl;
*/
if(flag)
return vector<student>(arr);
else
return vector<student>(0);
}
}
/*
void output(const student *s){
cout<<s->name<<" "<<s->score<<endl;
};
*/
void JSstudent()//testing
{
{
StudentMrg s;
//student *s1={"one",50,nullptr};
//s.Insert(s1);
student s1[5]={{"one",30,nullptr},
{"two",10},
{"three",70},
{"four",65},
{"five",100}};
for(int i=0;i<5;i++)
s.Insert(&s1[i]);
//s.showStudentMrg();//插入测试成功
//s.Delete("five");
//student find(s.FindByName("five5"));
//if(find.name!="")
//cout<<"name:"<<find.name<<" score:"<<find.score<<endl;
//s.showStudentMrg();
//s.FindByName("one1");
vector<student> ar=s.GetNTop(6);//大于5时会有BUG
//ostream_iterator<string,char> out(cout," ");
//for_each(ar.begin(),ar.end(),output);
vector<student>::iterator it;
if(ar.size()>0)//加了这个判断之后就不会有BUG了
{
cout<<"The top "<<ar.size()<<" is :"<<endl;
for(it=ar.begin();it!=ar.end();++it)
cout<<it->name<<" "<<it->score<<endl;
cout<<endl;
}
cout<<"JS over"<<endl;
cin.get();
}
}