数据结构 实验报告-4

第一题 六度空间：

一、实验内容：

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人”。

二、实验目的：

掌握图的广度优先搜索，熟悉图这种抽象数据结构；

三、程序清单：

▶

Code

#include<stdio.h>
#include<stdlib.h>

#define max 9999

int a[max][max], Nv, Ne;
int visited[max];

void creat()
{
    int i, j;
    int p, q;
    scanf("%d %d", &Nv, &Ne);
    for (i = 0; i <= Nv; i++)
    {
        for (j = 0; j <= Nv; j++)
        {
            a[i][j] = 0;
        }
    }
    for (i = 0; i < Ne; i++)
    {
        scanf("%d %d", &p, &q);
        a[p][q] = 1;
        a[q][p] = a[p][q];
    }
}

int BT(int i)
{
    int q[max] = { 0 };
    int rear = -1, front = -1;
    int j;
    int temp;
    int cnt;

    int level;
    int last;
    int tail;

    for (j = 0; j <= Nv; j++)
    {
        visited[j] = 0;
    }

    visited[i] = 1;
    cnt = 1;
    level = 0;
    last = i;
    q[++rear] = i;
    while (front < rear)
    {
        temp = q[++front];

        for (j = 1; j <= Nv; j++)
        {
            if (a[temp][j] && !visited[j])
            {
                visited[j] = 1;
                q[++rear] = j;
                cnt++;
                tail = j;
            }
        }
        if (temp == last)
        {
            level++;
            last = tail;
        }
        if (level == 6)
        {
            break;
        }
    }

    return cnt;
}

int main()
{
    int i, j;
    int count;
    double b;
    creat();
    for (i = 1; i <= Nv; i++)
    {
        count = BT(i);
        b = 100.0 * count / Nv;
        printf("%d: %.2f%%\n", i, b);
    }

    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第二题 家庭房产：

一、实验内容：

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

二、实验目的：

掌握并查集；

三、程序清单：

▶

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct people{
 int id,fid,mid,k,sum,area;
 int cid[20];
 bool vis=false;
};
struct home{
 int id,pnum,sum,area;
 bool vis=false;
};

bool cmp1(home a,home b){
 if(a.vis!=b.vis){
  if(a.vis==true){
   return true;
  }else return false;
 }
 if(a.area*b.pnum != b.area*a.pnum){
  return a.area*b.pnum > b.area*a.pnum;
 }else if(a.id!=b.id){
  return a.id<b.id;
 }
}

people pp[10005];
home hh[10005];
bool vis[10005];
int fa[10005];

int getfa(int x){
 while(x!=fa[x]){
  x=fa[x];
 }return x;
};

void uni(int a,int b){
 int faa = getfa(a);
 int fab = getfa(b);
 if(faa<fab){
  fa[fab]=faa;
 }else if(fab<faa){
  fa[faa]=fab;
 }
}

int main(){
 for(int i=0;i<10005;i++)fa[i]=i;
 int n;
 cin>>n;
 for(int i=0;i<n;i++){
  int id,fid,mid,k;
  cin>>id>>fid>>mid>>k;
  vis[id]=true;
  pp[i].vis=true;
  pp[i].id=id;
  pp[i].fid=fid;
  pp[i].mid=mid;
  pp[i].k=k;
  if(fid!=-1){
   uni(fid,id);
   vis[fid]=true;
  }
  if(mid!=-1){
   uni(mid,id);
   vis[mid]=true;
  }
  for(int j=0;j<k;j++){
   int cid;
   cin>>cid;
   pp[i].cid[j]=cid;
   vis[cid]=true;
   uni(cid,id);
  }
  int sum,area;
  cin>>sum>>area;
  pp[i].sum=sum;
  pp[i].area=area;
 }
 int cnt=0;
 for(int i=0;i<n;i++){
   int ffa=getfa(pp[i].id);
   if(hh[ffa].vis!=true)cnt++;
   hh[ffa].vis=true;
   hh[ffa].id=ffa;
   if(pp[i].vis==true){
    hh[ffa].sum+=pp[i].sum;
    hh[ffa].area+=pp[i].area;
   }

 }
 for(int i=0;i<10005;i++){
  if(vis[i]){
   hh[getfa(i)].pnum++;
  }
 }
 sort(hh+0,hh+10005,cmp1);
 cout<<cnt<<endl;
 for(int i=0;i<cnt;i++){
  printf("%04d %d %0.3f %0.3f\n",hh[i].id,hh[i].pnum,1.0*hh[i].sum/hh[i].pnum,1.0*hh[i].area/hh[i].pnum);
 }
 return 0;
}

五、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；