【C++】设计并实现一种简单的社交网络模型图
本帖最后由 c豆本豆豆奶 于 2019-8-27 11:22 编辑haha,这也算是上学期的期末课程设计，放上来给大家看一下，写了两三天左右，话不多说，上我们的设计要求
数据结构课程设计题目 从以下题目中任选一题：
（1）大数据分析问题（难度系数1.2） 某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天最热top100 词汇的可行办法。
（2）随时找到数据流中的中位数（难度系数1.3） 随时找到数据流中的中位数：有一个源源不断地吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。 要求： 1）如果MedianHolder已经保存了吐出的N个数，那么任意时刻将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。 2）取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)。
（3）神秘国度的爱情故事（难度系数1.5） 题目要求：某个太空神秘国度中有很多美丽的小村，从太空中可以想见，小村间有路相连，更精确一点说，任意两村之间有且仅有一条路径。小村A 中有位年轻人爱上了自己村里的美丽姑娘。每天早晨，姑娘都会去小村B 里的面包房工作，傍晚 6 点回到家。年轻人终于决定要向姑娘表白，他打算在小村C 等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村 C 是否在小村B 到小村 A 之间的路径上。你可以帮他解决这个问题吗？ 输入要求：输入由若干组测试数据组成。每组数据的第1 行包含一正整数 N ( l 《N 《 50000 ) , 代表神秘国度中小村的个数，每个小村即从0到N - l 编号。接下来有 N -1 行输入，每行包含一条双向道路的两个端点小村的编号，中间用空格分开。之后一行包含一正整数M ( l 《 M 《500000 ) ，代表着该组测试问题的个数。接下来M 行，每行给出 A 、B 、 C 三个小村的编号，中间用空格分开。当N 为 O 时，表示全部测试结束，不要对该数据做任何处理。 输出要求：对每一组测试给定的A 、 B 、C，在一行里输出答案，即：如果C 在 A 和B 之间的路径上，输出 Yes ，否则输出No.
（4）Huffman编码与解码（难度系数1.3） 对一篇英文文章，统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。 [基本要求] （1） 输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。 （2） 在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即01的信息用比特位表示，不能用字符’0’和’1’表示。 （3） 提供读编码文件生成原文件的功能。
（5）社交网络图实现（难度系数1.4） [问题描述] 设计并实现一种简单的社交网络模型图。 [基本要求] （1） 每个人的信息是一个结点，人与人的联系构成边。个人信息里要有地理坐标信息，以便后续应用中能方便找靠近的人。 （2） 根据输入的任意两个人信息，给出他们之间的联系路径，最少经过多少人构成联系。 （3） 根据位置信息的动态变化，找寻附近能够联络的人，即能够通过1次中间人能联络的人等。 （4） 可根据自己的创意添加更多的功能。
我这个懒人当然要莽了，选的第五个设计，看网上的一些代码都非常不靠谱，完全运行不了的~或者跟要求不符合啊，分享一下我的效果，用的邻接表啊，本来想用矩阵的，弄了好久没弄出来，有比较有思路的也可以交流交流，好久之前还写了用python爬小说网站，整理成书的，因为实在是受不了网站上的色情广告了hhhh，下次看一下能不能找出来分享给大家源码。
好像没办法贴全，完整代码行数比较多，把我的排版都弄乱了，就先放前面一点吧，完整的放在附件里面了
#include<iostream>
#include<fstream>
#include<queue>
#include<cstring>
using namespace std;
#define inf 10000
const int MAX = 100;
struct link
{
int data;
string name;
link *lnext;
};
struct Node
{
int v;
string nn;
link *lnext;
};
struct Graph
{
Node node; //所有的结点
int ncount;
};
int visited; //查询是否走过的数组
int pa;
int tono(Graph G,string n){
for(int i=1;i<=G.ncount;++i){
if(G.node.nn==n)
return i;
}
}
string toname(Graph G,int q){
for(int i=1;i<=G.ncount;++i){
if(G.node.v==q)
return G.node.nn;
}
}
Graph CreateGraph()
{
int a,b,c,d;
cout<<"输入总人数，总边数";
cin>>a>>b;
//表的初始化 ,人数是节点
Graph G;
G.ncount = a;
int i ;
string na;
for(i = 1; i <= a; i ++)
{ cout<<"输入姓名："<<endl;
cin>>na;
G.node.nn = na;
G.node.v = i;
G.node.lnext = NULL;
}
int n1 = 0,n2 = 0;
link *s;
string n5,n6;
for(int i=0;i<b;++i)
{ cout<<"输入联通一条边的两人";
cin>>n5>>n6;
c = tono(G,n5);
d = tono(G,n6);
s = new link;
s->data = d;
s->name = n6;
s->lnext=G.node.lnext;
G.node.lnext=s; //从尾部插入
//delete(s);
s=new link;
s->data = c;
s->name = n5;
s->lnext=G.node.lnext;
G.node.lnext=s; //无向图
//delete(s);
}
return G;
}
页:
[1]