关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集
原题题目
闲谈
做这个附加题很明显
也是为了再加深一点自己对图的理解
还是可以的
这道题很明显 因为之前就发现了
有的时候邻接矩阵的时空复杂度更高
而且占用的空间相对很小的浪费很对
所以这道题刚开始的时候就选择了邻接表
也是没花多久吧 中间还是调试了一下
之后就发现最后一个存档点过不了
之后才发现 MAX是1000 ：）
这里要注意一下 MAX尽量比1000大一点
因为你是从1开始存的 而他的1000空间包括了0
所以我强迫症就变成了1010了
题目大意
意思就是第一排的第一个 是总用户数N 第二个是最多你能转发关系层数
之后的N排就是表示
比如第一排 List[1] 后面的就是他关注的人
List[2] 是0 表示他谁都没有关注
以此类推
最后一排的第一个数字就是要有几个测试用户
后面的就是他的测试用户
测试用户的意思就是他作为博主转发 OK？
题目思路
Bloodstream - The Chainsmoker
核心思想还是BFS
没有什么很特别的地方
如果这道题觉得有点棘手 可以看一下我数据结构
这篇博客上面的那篇 六度空间
还是很详细的把BFS给介绍了一遍
六度空间关于BFS的介绍
然后就是处理数据 很正常的处理
下面直接给出代码吧 对于特别的地方我会给注释的
代码实现
#include <stdio.h>
#include <stdlib.h>
#define MAX 1010typedef int vertex;
typedef struct VNode
{
int v;struct VNode *Next;
} *Vertex;
int Nv,levelmax;//邻接表嘛
Vertex List[MAX];
int Visit[MAX];
void InitVisit();
void InitList();
void InsertVertex(vertex following,vertex user);
void BreadthFirstSearch(vertex v1);void InitVisit()
{
int i;for(i=1;i<=Nv;i++)Visit[i] = 0;return;
}void InitList()
{
int i;for(i=1;i<=Nv;i++)List[i] = NULL;return;
}void InsertVertex(vertex following,vertex user)
{
//这里Following的意思就是 用户关注的博主的意思Vertex NewNode;NewNode = (Vertex)malloc(sizeof(struct VNode));NewNode->v = user;NewNode->Next = List[following];List[following] = NewNode;return;
}//BFS模板
//实在不清楚的话
//可以去看我的六度空间博客
void BreadthFirstSearch(vertex v1)
{
int top = -1,rear = -1,level = 0,count = 0,last,tail;int Queue[MAX];vertex v2;Vertex position;Queue[++rear] = v1;Visit[v1] = 1;last = v1;while(top != rear){
v2 = Queue[++top];for(position = List[v2];position;position = position->Next){
if(!Visit[position->v]){
Queue[++rear] = position->v;Visit[position->v] = 1;count++;tail = position->v;}}if(v2 == last){
level++;last = tail;}if(levelmax == level)break;}printf("%d\n",count);return;
}//下面就是主函数实现了
//变量名字还是挺清晰的了
//大家可以仔细看一下 还是看得懂的
int main()
{
int i,j,follownumbers,testnumbers,testuser;vertex following；InitList();scanf("%d%d",&Nv,&levelmax);for(i=1;i<=Nv;i++){
scanf("%d",&follownumbers);for(j=1;j<=follownumbers;j++){
scanf("%d",&following);InsertVertex(following,i);}}scanf("%d",&testnumbers);for(i=1;i<=testnumbers;i++){
InitVisit();scanf("%d",&testuser);BreadthFirstSearch(testuser);}return 0;
}
兴趣果然是第一驱使力
希望自己再在里面找到自己感兴趣的部分
大家共勉！