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

性感上帝

/*接上一篇文章*/

演员信息记录：

演员信息记录存储的是他的基本信息以及他所参演电影的信息，在这里我们也没有适用任何形式的结构体或类，因为这样做同样会将所有演员的信息记录大小限定为一个值。所以我们将与该演员相关的信息全部存储在一块连续的内存空间里，这块内存的大小取决于演员的名字长度以及他所参演电影的个数。下面是关于此种方式的详细描述：

演员的名字如常规的C字符串那样，是按照一个个字符的形式被存储进去的。如果演员名字长度为偶数，那么在它之后会被强行插入额外的一个字符：’\0’。原因在于演员名字后面跟着信息很容易被系统看作一个短整型的数据，事实上所有硬件都将被操作的地址看作指向短整型数据的指针。

演员参演电影个数被存储在两字节大小的内存中（原因在于有些演员参演的电影数目远远多于255，所以一个字节很有可能不够用）。如果此时用于存储演员名字的字节数（总是偶数）与存储电影数目的字节数（总是2）之和不能被4整出，那么在这之后需要被额外的加上两个’\0’，这样整体就可以看做多个地址了。

紧接着的就是movieFile数据的偏移量数组，每个偏移量都代表了一个演员参演的电影信息。

下面是Cher记录的示例：

电影信息记录：

电影信息记录较之前者可能更复杂些，它的信息将会按如下规则被压缩：

电影的名字后面会加跟一个’\0’字符，以使它转换成一个常规的C语言风格的字符串。

电影发行的年份被存储在单字节中，由于好莱坞的历史还不超过2的8次方，所以，该字节实际存储的是它离1900年的偏移量。如果名字信息与年份信息的字节总数是奇数，那么它们与实际数据之间会增加一个’\0’字符。

接下来会有一个两字节大小的短整型用于存储该部电影中演员的个数，如果有必要的话，之后需要附加两个存储着0的字节。

最后就是偏移量数组，每个偏移量都对应着一个演员的actorFile数据。显而易见的是，这个数组的大小和步骤三那个短整型所存储的数值大小肯定是一样的。

需要注意的是：有些电影名字相同但它们实际上是不一样的电影（例如：Manchurian Candidate这部电影，首次发行是在1962年，但在2004时又被翻拍了，因此它们理应是不同的电影）。如果你已经看过文件夹中imdb-utils.h那个文件的话，你应该会看到film结构体内部实现了<和==的运算符重载。这样的话两部电影就可以通过运算符进行对比，从而进行分类。当然在本次课题中，你也只能通过film提供的运算符重载方法进行同名电影的分类。同样，你需要知道的是movieData数据集也遵守<运算符规则。

你不需要过多的关注如何实现搜索算法，最好事先独立完成imdb类的代码工作。我在这儿也提供了一个已经写好的测试程序：imdb-test.cc。运行该程序，它会自行测试你实现的imdb类是否足够稳定。我同时还提供了基于solaris和linux的两个不同版本的可执行测试案例，你可以将它们与你自己编写的测试案例进行对比。

实现任务1：

下面我列出了在实现imdb时需要的所有文件信息：

imdb-utils.h 该文件包含了film结构体的定义以及一个用于查找数据文件的内联方法。你最好不要对该文件进行大的改动。

imdb.h 这里面包含了imdb的一些基本接口信息，同样最好不要进行更改。当然你对私有字段有自己独到的看法，你也可以自行更改。

imdb.cc 这里面有构造函数、析构函数以及其它一些方法的实现细节。你的主要工作就是在这里实现getCredits与getCast方法。

imdb-test.cc 这是额外提供的单元测试代码，你可以用它测试你写的imdb类是否符合要求。

makefile 这个我就不解释，不懂的自行google。

今天这篇属于长文了，快接近5000字了，接下来就先简短的讲下做法：

bool imdb::getCredits(const string& player, vector<film>& films) const { return false;}

bool imdb::getCast(const film& movie, vector<string>& players) const { return false; }

在imdb.cc中实现两个方法，getCredits是传入一名演员的名字，然后将所有该演员主演的电影信息存到films中，getCast就是传入电影名，得到所有参演演员信息。

分析getCredits的实现（getCast与之类似）：

利用已有的条件，构造函数会将actorFile初始化好，因此由*(int *)actorFile可以得到演员信息的记录总数目，然后对这么多的数据进行遍历，例如遍历到第n项时（假设for循环从1开始）：

1、*(int *)(actorFile + n*4)这个可以得到偏移量的值

2、*(int *)(actorFile + (n+1)*4) - *(int *)(actorFile + n*4)这个得到的是第n项所代表的演员存储的记录数据大小

3、一个个字符读取直到读到’\0’，然后将读到的字符串与演员名字进行核对，不对就继续遍历，跳回1

4、如果结果是这名演员的信息，这里面得看演员的名字是不是奇数了，是奇数，直接往后读两字节，是偶数，就跳过一字节，然后读取两字节，这两字节就是前面介绍的偏移量数组，这些偏移量是相对于movieFile而言的（一定要记住），接下来就好办了，直接拿着偏移量就去取数据，这个复杂度为O（1），前面所说的快速取到数据也就是指的这个。

5、取数据，偏移量+movieFile地址就是数据的地址，根据上文所介绍的movie记录的数据格式，顺序依次为：

电影名字年份偏移值参演演员数目参演演员记录偏移量（相对于actorFile），我们在这需要的就是前两个值，取出来包装如film，然后再存入films即可，大功告成。

getCast基本也是一样的流程，具体的实现可能会遇到各种各样的bug，但相信自己，慢慢改。

关于六度分隔理论项目的第一部分难题就完成了，代码就不像之前那样事先贴出来，计划在发布完第二篇关于搜索的长文后再放源码。

特别的：请尽量在linux系列的操作系统中完成本次项目，不然就只能看着呵呵了。装个虚拟机啥的也不难吧。

本次课程需要文件已上传至百度网盘，自行下载：

http://pan.baidu.com/share/link?shareid=989138234&uk=3844400595

说明：

刚刚又校对了下整个稿子，前面有一段关于添加’\0’这个细节，不知道大家懂不懂，这是关于内存对齐那方面的知识，不知道有没有必要在后续的短文中提一下，有需求的话就留言。

大家尽量在中秋节前完成任务，不然搜索我觉得你会跟不上的，多google或直接留言给我（任何关于这个项目的问题）

每次都要进行的版权声明：本文取材至CS107，大家多去听听那位教授的课，很不错的。然后教材《计算机程序的构造与解释》和课外读物《七周七语言》，极力推荐看看。

THX ☺

//我的联系方式如下

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

微信公共号IT百问

关注方式：

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

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