算法习题---5.9数据库（Uva1592）

一：题目

对数据库中数据进行检测，是否出现数据冗余现象。即是否某一列出现两个及以上数据重复

如上图中，第二列中第2,3行数据重复，所以我们判断为数据冗余。因为他可以分解为下面两张表

（一）样例输入

How to compete in ACM ICPC,Peter,[email protected]

How to win ACM ICPC,Michael,[email protected]

Notes from ACM ICPC champion,Michael,[email protected]

,Peter,[email protected]

,Michael,[email protected]

（二）样例输出

NO

 3　　//这两行中出现数据冗余

 3　　//冗余出现在上面两行的这两列中

YES

二：代码实现

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <string>

#include <sstream>

#include <set>

#include <map>

#include <vector>

#include <algorithm>

using namespace std;

vector<string> split(string source, string pattern)

{

    vector<string> res;

    int spos = , epos, p_len = pattern.length() - ,s_len = source.length()-;

    source += pattern;

    char col = '';

    while (spos<s_len && (epos = source.find(pattern,spos))&&epos!=string::npos)

    {

        stringstream stream;

        stream << col++;　　//在末尾加上列号，可以防止出现因为不同列数据重复现象

        res.push_back((source.substr(spos, epos - spos)).append(stream.str()));

        spos = epos + ;

    }

    return res;

}

int main()

{

    FILE *fp = freopen("data5_9.in", "r", stdin);

    freopen("data5_9.out", "w", stdout);

    string line;

    int row, col;

    while ((cin >> row)&&row!=)

    {

        //获取行列数

        cin >> col;

        vector<string> str_vec;

        set<string> str_set;

        map<string, int> str_map;

        vector<int> res;    //保存两行，一列重复

        for (int r = ; r <= row; r++)

        {

            getchar();

            getline(cin, line);    //重点使用

            str_vec = split(line, ",");    //由于没有split字符串分割函数，使用find和substr进行分割

            vector<string>::iterator iter = str_vec.begin();    //进行迭代插入

            int c = ;

            for (; iter != str_vec.end(); iter++)

            {

                if (!str_set.count(*iter))

                {

                    str_set.insert(*iter);

                    str_map[*iter] = r *  + c++;

                }

                else    //出现同一列重复

                {

                    int r_r = (str_map[*iter] / 10)*10 + r;　　//23表示第2,3行重复

                    res.push_back(r_r*10+c++);    //将重复的行列添加到res映射中

                }

            }

        }

        if (res.empty())    //进行结果输出

            cout << "YES" << endl;

        else

        {

            cout << "NO" << endl;

            int r_r = res.front();

            cout << r_r /  << ' ' << r_r /  %  << endl;    //输出行

            for (vector<int>::iterator it = res.begin(); it != res.end(); it++)

                cout << *it %  << " ";    //输出列

            cout << endl;

        }

    }

    freopen("CON", "r", stdin);

    freopen("CON", "w", stdout);

    return ;

}