小世界效应：从凯文·贝肯到六度分隔理论（1）

性感上帝

/*以前写的文章和大家分享下*/

斯坦福的老师很喜欢用一些生活的小案例来引入课题，小的Project也不例外。

凯文·贝肯是好莱坞的大牌明星，这次Project也得从他说起。虽然贝肯在娱乐圈可谓呼风唤雨，人气也是相当的高，但他与奥斯卡的缘分却令人唏嘘。他的演艺生涯，不乏经典大片：Flatliners，The Air Up There，Footloose等等，但遗憾的是，一直未能捧获奥斯卡小金人。

时间回到1993年，当时还在读大学的Mike Ginelli、Craig Fass和Brain Turtle发明了一款有关凯文·贝肯的游戏，游戏的很简单，它能将任意的一位演艺界的明星用不超过6部电影与凯文·贝肯搭上关系，这也算是“六度分隔理论”的一个雏形。这款小游戏迅速在大众之中流行开来还得归功于Jon Stewart，他在电视秀中让大家第一次接触到了这样一款“神奇”的游戏。这样的游戏也引发了人们对于关系的进一步思考，世界在这套理论体系之下是如此的小。

你可以在开始项目前先感受一下在线版本: http://oracleofbacon.org/

具体玩法：

你说出两个明星的名字，你的朋友需要用少于6部电影将两位明星联系起来。

例如：你说A和B

你朋友得出以下的回答：

A和C同时出演了XXX那部电影

C和D同时出演了XXXX那部电影

D和B同时出演了X那部电影

于是A和B仅仅用了三部电影就联系起来了。

如果看到这儿还没有明白，请还是先去体验下在线版本。

概览：

目前，我能告诉大家的是，我们整个项目可以具体分为两块：

你需要实现imdb这样一个类，这个类的主要作用是能让你快速查找到某一部电影里面参演的所有演员信息以及某一位演员参演的所有影片信息。目前看来，我们好像可以直接使用stl模板中的map来实现，具体可以实例化两个map：一个用于某演员映射到所有电影，另一个用于某电影映射到所有演员。但细想下来，光从几兆的文本文件中读取这些信息就得花费很多时间，更要命的是，类型的识别也需要花费几分钟的时间，反正没人会愿意坐在电脑面前干等着，难道不是吗？所以这时候就需要大家开动脑袋瓜子，用我们的扎实的内存管理与数据结构的知识去处理这样子的数据，让我们的程序能够尽可能快的读取演员以及电影的信息。大家可以稍加思考，这个是本次项目的一个重点问题，不过大家放心，我会在后面实现 (*^__^*)

Imdb：全称Internet Movie Database

在完成第一步后，我们同时需要实现一个广度优先的搜索算法，通过算法可以找到两位演员的最短关系路径，当然这也得依靠上一步你设计的优秀数据结构啦。当然，我们事先也可以估摸一下，如果算法跑了一会儿，然后发现关系路径的长度已经大于6了，那么可以认定这两位是不可能联系在一块的啦。这部门的内容可能需要你对CS106B这套课程掌握的比较好，当然也没关系，这部分也能让不熟悉前面知识的同学重新温习下STL，这里面也会集中体现出C++作为“高层次”语言在模板以及面向对象上的优势，同时C作为“低级”语言，在内存管理以及面向过程上的优点也将发挥的淋漓尽致。敬请期待吧。

任务1：实现imdb类

首先，整个项目的落脚点是imdb类细致处理、实现。下面是已经实现了接口：

struct film{

    string title;

    int year;

};

class imdb{

    public:

                imdb(const string& directory);

                bool getCredits(const string& player,vector<film>& films) const;

                bool getCast(const film& movie,vector<string>& players) const;

                ~imdb();

    private:

                const void *actorFile;

                const void *movieFile;

};

由于我在初始化actorFile与movieFile时需要预先处理大量的原始数据，期间使用了一些比较不常见的UNIX方法，所以整个类的构造函数与析构函数已经为你实现了，你不需要操心这部分的工作。值得高兴的是，构造函数和析构函数的复杂度都为O(1)，这也正是我们想要的，: ）

我们现在需要关注的工作是实现getCredits与getCast这两个方法，它们的只要功能是从数据中分类出演员与电影的信息用于填充films和players这两个vector数据。如果能够按照预期的那样实现，那么这两个方法将会带来飞速的查询速度。

整个项目的前提是数据不需要大家操心，但为了能更好的实现上面的两个方法，接下来的部分会给大家详细介绍这些数据是如何存储的，以便于大家能自如的操作它们。

//由于发帖字数限制，请继续看第二篇

//下面是我的联系方式

＝＝＝只做最真实的自己＝＝＝

微信公共号IT百问

关注方式：

1、打开微信搜索微信号ID：itbaiwen

2、或者扫描下方的二维码