首页 > 代码库 > 洛谷P1738 洛谷的文件夹

洛谷P1738 洛谷的文件夹

原题目:点我

题目是一个略水的题,我机制地用面向对象做了。。。所以代码量急剧加大,100行233

模拟即可,字符串处理麻烦点。如果没有找到子文件夹就新建文件夹,如果有就进入该文件夹。

提示:高能,指针+动态内存,用数组太low(在noip中用数组才是王道!)

#include <iostream>#include <vector>#include <string>using namespace std;int foldercnt=-1;//根目录已经算了一个了,所以要把自己去除掉bool isleaf(string s)//判断这个字符串有没有斜杠{    for(string::iterator it=s.begin();it!=s.end();++it)        if(*it==‘/‘)return false;    return true;}string getname(string s)//得到这个字符串的第一个斜杠和第二个斜杠之间的字串{    string ans;    int cnt=0;    for(string::iterator it=s.begin();it!=s.end();++it)    {        if(*it==‘/‘)cnt++;        if(cnt==1&&*it!=‘/‘)ans.push_back(*it);        if(cnt==2)break;    }    return ans;}string getmy(string s)//得到这个字符串开始到第一个斜杠之间的字串{    string ans;    bool have=0;    for(string::iterator it=s.begin();it!=s.end();++it)    {        if(*it==‘/‘)have=1;        if(!have)ans.push_back(*it);    }    return ans;}string getrest(string s)//得到第一个斜杠之后的字串{    string ans;    bool have=0;    for(string::iterator it=s.begin();it!=s.end();++it)    {        if(have)ans.push_back(*it);        if(*it==‘/‘)have=1;    }    return ans;}struct folder//文件夹结构体{    /***constructor***/    folder(string name)//构造函数    {        this->name=name;        this->son.clear();        foldercnt++;//文件数量++    }    ~folder()//析构函数    {        for(vector<folder*>::iterator it=this->son.begin();it!=this->son.end();++it)//析构自己所有的子文件夹            if(*it!=NULL)            {                delete *it;                *it=NULL;            }    }    void make(string x)//制作函数    {        if(isleaf(x))return;//如果到这里是叶子了,返回        if(getmy(x)!=this->name)return;//这句话帮了我大忙        string nm=getname(x);//得到儿子的名称        for(vector<folder*>::iterator it=this->son.begin();it!=this->son.end();++it)//找一找有没有        {            if((*it)->name==nm)//如果有            {                (*it)->make(getrest(x));//切割字符串,进入子文件夹                return;//直接返回            }        }        folder* fp=new folder(nm);//没有的情况,新建文件夹        this->son.push_back(fp);//把文件夹放到儿子表列        fp->make(getrest(x));//make文件夹        return;    }    string name;//自己的名称    vector<folder*>son;//儿子表列};int main(){    folder *root=new folder("");//根节点名字为空    int n;//数量    string tmp;//输入    cin >> n;//输入    for(int i=1;i<=n;i++)//循环输入    {        cin >> tmp;        root->make(tmp);//制作文件夹        cout << foldercnt << endl; //输出总数    }    delete root;//删除根文件夹,释放内存(你想想你平时删除文件夹了文件夹里面的东西全没了嘛)    root=NULL;//野指针    return 0;}

 

洛谷P1738 洛谷的文件夹