数据结构——光纤网络设计

设计进度安排

1、分析居民区光纤网络的数据属性，并依据光纤铺设的功能要求，确定算法设计方案；

2、完成网络光纤铺设的数据结构设计工作，包括图文件的结构与存储结构、最小生成树的存储结构、图形的显示结构等；

3、完成功能设计工作，包括随机生成代价文件、读图文件、计算最小生成树、显示最小生成树等；

4、使用C或C++程序设计语言编写实现算法程序；

5、完成大作业报告。

设计内容

　　认真参阅课程相关参考资料、数据，了解铺设网络光纤的原理要求，设计一个实现居民小区之间网络光纤铺设的最佳方案选择的算法，具体内容如下：

　　需要在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。

需求分析

1.光纤网络设计
在某个城市n个居民小区之间铺设网络光纤，设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小。

2.功能要求
输入居民区的个数，光纤的条数，光纤的单价，以及各个居民区之间的距离，运用克鲁斯卡尔算法，输出系统最优的铺设方案。

代码具体

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

        cout<<"居民小区光纤路线铺设最优方案设计 "<<endl;

        int neighborhoodNum, opticalNum; // 居民区个数, 光纤线路条数

        int neighborhood1, neighborhood2; //两个居民区

        double price; //光纤线路单位长度价格

        double distance, shortest_distance=0; //最短总路线长度

        int neighborhoodArrary[100][100]; //邻接矩阵

        int i, j;     


       cout<<"请输入居民区个数: ";

        cin>>neighborhoodNum;

        cout<<"请输入光纤线路条数: ";

        cin>>opticalNum;

        cout<<"请输入光纤线路单位长度价格 : ";

        cin>>price;

        cout<<endl;   


        for(i=0; i<neighborhoodNum; i++)

                 for(j=0; j<neighborhoodNum; j++)

                 {

                         neighborhoodArrary[i][j]=9999;

                 }


        cout<<"请输入各光纤线路的两居民区及距离："<<endl;

        j=1; //j 表示第 n 条线路

        for(i=0; i<opticalNum; i++)

        {

                 cout<<"请输入第 "<<j<<" 条光纤线路的两居民区及距离: "; //存储两居民区及距离

                 cin>>neighborhood1>>neighborhood2>>distance;

              neighborhoodArrary[neighborhood1][neighborhood2]=distance;

              neighborhoodArrary[neighborhood2][neighborhood1]=distance;

                 j++;

        }

       

        int short_way[100];

        int near_neighborhood[100];

        int min_way;

        int temp_neighborhood;

       
        for(i=1; i<neighborhoodNum; i++)

        {

                 short_way[i]=neighborhoodArrary[0][i];

               near_neighborhood[i]=0;

        }
      

        short_way[i]=0;

        near_neighborhood[i]=0;

        cout<<"居民小区光纤路线铺设最优方案设计如下: \n";

        for(i=1; i<neighborhoodNum; i++)

        {

                 min_way=9999; j=1; temp_neighborhood=1;              

                 while(j<neighborhoodNum)

                         {
                                  if(short_way[j]!=0 && short_way[j]<min_way)
                                          {  
                                                 min_way=short_way[j];
                                             temp_neighborhood=j;
                                          }
                                  j++;
                         }
                        
                 cout<<" 居民区 "<<near_neighborhood[temp_neighborhood]<<"----("<<min_way<<"米) ----居民区"<<temp_neighborhood<<endl;
       
                 short_way[temp_neighborhood]=0;

                 shortest_distance+=min_way;
       
                 for(j=0; j<neighborhoodNum; j++)

                if(neighborhoodArrary[temp_neighborhood][j]<short_way[j])

                 {
                         short_way[j]=neighborhoodArrary[temp_neighborhood][j];
                         near_neighborhood[j]=temp_neighborhood;
                 }
        }

      

        cout<<"最短总长度为: "<<shortest_distance<<"米"<<endl;

        cout<<"最低总造价为: "<<shortest_distance*price<<"元"<<endl<<endl;

      
        char choice;
       

        cout<<"清空数据, 重新输入? T or F : "; cin>>choice;
        if(choice=='T' )
        {
                 system("cls") ; //清空屏幕, 重新开始
        }

        if(choice=='F' )
        {
                 cout<<"成功退出!";
                 exit(0) ; //退出程序 }
        }

}

代码运行结果：

总结：
运用最小生成树，点表示居民区，路径表示光纤线路，运用克鲁斯卡尔算法，使既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小。考虑iostream库输入输出流便捷，采用C++代码。思考设计过程中遇到算法选择的困难，最后考虑时间复杂度和空间复杂度选择克鲁斯卡尔算法。