基于C语言实现一个社交系统.zip

# 基于C语言实现一个社交系统 # 设计过程 ## 设计构想 Project 的基本要求是实现一个社交系统，使其能够进行基本的消息发布，信息共享，好友关注等功能。针对后台的操作，希望设计针对用户名的开放链表法的哈希索引，消息则使用链表实现，关注关系以有向图的十字链表存储。至于前台的设计，希望以一个界面类，实现全部的前台指令操作。在设计的时候，应当以功能为导向，为界面类提供应有的接口，以保证代码的正常运作。 文件存储的设想： - 尽可能减少内存的使用量，使用文件操作 - 修改用户信息不需要修改索引值，以达到代码量的减少 - 多索引，保证条件搜索的速度 - 可变信息与长度不可变的信息分开存储，以实现叠加式地文件内容增长，而非重写 数据结构的设想： - 尽可能实现不修改索引的情况下实现数据文件的修改 - 尽可能选用合适的数据结构，不同情况下使用的数据结构考虑实现为模板方式 对于程序的设想就是这样，在写程序的时候也一直尽量以之作为纲领。 ## 文件存储 因为要保证用户的信息在程序结束后不消失，所以需要将其保存在文件中。我将用户的所有内容分为三类：长度不变的个人信息（如电话，等等），用户发布的信息，以及关注信息。所有的文件都是以二进制存储。用户的所有关于个人的信息都存储在 info 中，用户发布的，消息在 meg 中，而关注在 like 中。他们的组织形式如 Figure 1 所示。  还有关于索引的存储，由于程序要求实现关于个人信息的各个条目的搜索，所以关于每一种信息的索引都单独存放。index 中存放的是用户名哈希索引，index_name 存放的是用户姓名索引，index_bir 是生日索引，index_tele 是电话索引，index_add 是地址索引。 ## 前台设计 程序的前台功能都是在 Interface 类中实现的，Interface 同时也是连结前台后台的主要类。同时为了测试模式，Interface 也提供了测试接口。详细接口如图 Figure 2，具体见。  ## 数据结构 ### 前台-字典树 本来是打算实现前缀搜索的功能的，后因时间紧迫，无奈放弃。不过在字典序输出关注列表时可以用到字典树，因此就保留了此数据结构。 在整个程序中，只有在前台显示列表的时候使用到了该数据结构，所以用处不是很大，就作为一个尝试吧。 ### 后台-哈希表（模板实现） 在程序的后台操作中，出于各种考虑，最终选择了链表寻址式哈希表作为索引的数据结构。主要的信息都是以字符串的方式存储，因此哈希的函数是针对字符串设计的，采用了 BKDRHash 方法，哈希表共有 H 项，H 为宏定义，大小可改动，解决冲突的方法是拓展链表法。考虑到系统要求的查找操作不只针对用户名，因此哈希表以模板类的方式实现，接口如 Figure 3 所示，详细接口见。  数据结构在第一次启动时，会建立哈希表项的空内容，之后会在索引文件中插入新的内容，在加入元素的时候会将其保存至硬盘中，以保证内存与硬盘内容的统一。在程序运行的过程中，数据结构始终不会被读入内存，索引项的寻址等操作大部分都是建立在文件操作的基础上。由于在实现的设想中，修改都是在数据文件中进行，而哈希索引只是存放指向数据文件的指针，因此是不会被修改，因此没有实现关于索引修改的接口，而对于信息修改导致的修改，采取的是先删除再插入的方法。  索引的格式如下所示，key 值是索引值，而 pointer 则指向索引值所在文件的位置，是一个文件指针。只要知道索引的键值，可以将其在文件中的位置找到，如果保证索引与数据的同步性，就可以大大提高遍历的效率，这也是本次 project 最有难度的地方吧。 | Key1 | Pointer1 | | ---- | -------- | | Key2 | Pointer2 | | … | … | 至于存储格式的设置，首先索引是有其键值以及指向 info 中对应信息所在位置的指针，而存储还需要保存一个指向下一个哈希索引节点的指针。即如下所示，Saveform 是由索引和指针构成，指针指向链表的下一个节点，依靠此建立了哈希链表。 | RecordNode1 | PointerToNext1 | | ----------- | -------------- | | RecordNode2 | PointerToNext2 | | … | … | 在每次插入新索引时，原本链表的最后一个节点会将 PointerToNext 指向新建立的索引结点，从而形成新的索引。这样就完完全全在文件中构建起了一个链表拓展法的哈希索引，提高了搜索的效率。 ### 后台-有向图十字链表 程序要求可以查看用户的关注以及关注用户的用户，因此选用有向图作为存储关注关系的数据结构，而十字链表是比较好的存储方式，因为其可以以链表的方式同时查看用户的关注以及关注用户的用户。该有向图也是常驻硬盘的。接口如图 Figure 5 所示，详细见。  所有关于关注关系的操作全部建立在 OLGraph 的基础上进行。至于关注关系的结构，由用户结点和关注弧构成。对于关注的文件存储，比较难的地方在于结点与弧都是增长的，因此保存起来不方便。最开始的想法是结点与弧保存在两个文件中，后来为了整齐考虑，最后把两个保存在一个文件 like 中。由于每个用户只需要知道与自己相关的关注关系，因此用户的信息里有一个指向 like 中该用户的用户结点，这样不需担心结点与弧会找不到位置，就可以实现混合存储了。 虽说理论上可以实现结点与弧混合存储，但是具体实现还是比较麻烦。首先，结点的存储格式如下，第一个元素是唯一的用户名，接下来就是十字链表的两根链表的头项，分别是关注该用户名的与该用户名关注的。 | Username | Firstin | Firstout | | -------- | ------- | -------- | | … | … | … | 至于弧的存储方式，如下所示，四个元素都是 long 变量，前面两个是二元关系的两个变量，代表 tailvex->headvex，而两个变量是指向有向图结点的指针。接下来的两个变量是指向关系链表中的下一个元素的指针，即指向下一个弧的指针。 | Tailvex | Headvex | Headlink | Taillink | | ------- | ------- | -------- | -------- | | … | … | … | … | 而由于两者都存储在一个文件中，所以是混合存储，用户数据中有一个指向其结点的指针，这样就可以由用户找到对应的结点，从而找到对应的关注关系。所以整个有向图的存储如下所示。 | Username | Firstin | Firstout | | | -------- | ------- | -------- | -------- | | Tailvex | Headvex | Headlink | Taillink | | Tailvex | Headvex | Headlink | Taillink | | Tailvex | Headvex | Headlink | Taillink | | Tailvex | Headvex | Headlink | Taillink | | Username | Firstin | Firstout | | | … | … | … | … | ### 后�