【C++】设计并实现一种简单的社交网络模型图

c豆本豆豆奶

                                               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，下次看一下能不能找出来分享给大家源码。



好像没办法贴全，完整代码行数比较多，把我的排版都弄乱了，就先放前面一点吧，完整的放在附件里面了

[C++] 纯文本查看 复制代码

#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[MAX+1]; //所有的结点  
  int ncount; 
};  
  
int visited[MAX+1]; //查询是否走过的数组 
int pa[MAX+1];  
  
 
int tono(Graph G,string n){
	for(int i=1;i<=G.ncount;++i){
		if(G.node[i].nn==n)
			return i;
	}
}

string toname(Graph G,int q){
		for(int i=1;i<=G.ncount;++i){
		if(G.node[i].v==q)
			return G.node[i].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[i].nn = na;
        G.node[i].v = i;  
        G.node[i].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[c].lnext;  
        G.node[c].lnext=s; //从尾部插入  
        //delete(s);  
  
        s=new link;  
        s->data = c;  
        s->name = n5;
        s->lnext=G.node[d].lnext;  
        G.node[d].lnext=s; //无向图  
        //delete(s);  
    }  
    return G;  
}