1、数据结构课程设计报告城市地铁设计数据结构课程设计报告学院：计算机科学与工程专业：计算机科学与技术班级：09级班学号：姓名：指导老师: 时间: 2010年12月一、课程设计题目： 1、哈夫曼编码的实现 2、城市辖区地铁线路设计 3、综合排序算法的比较二、小组成员：三、题目要求：1哈夫曼编码的实现（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。（2）针对上述统计结果，对各字符实现哈夫曼编码（3）对任意文章，用哈夫曼编码对其进行编码（4）对任意文章，对收到的电文进行解码2某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地
2、铁的建设路线。（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（3）输出应该建设的地铁路线及所需要建设的总里程信息。3综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。（1）对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序简单选择排序，堆排序，归并排序，基数排序。（2）待排 序的表长不少于100，要求采用
3、随机数。（3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数（4）改变数据量的大小，观察统计数据的变化情况。（5）对试验统计数据进行分析。对各类排序算法进行综合评价。四、项目安排：1、小组内分工合作分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。五、完成自己的任务：任务：城市辖区地铁线路设计1.实现方案 在整个编程中，我是通过手动输入的方式把数据写到文件中，而不是直接从文件中读取，这个不是题目要求的，但是我想当拿到数据之后都要对数据进行处理，干脆直接
4、手动输入得出结果。 在这个代码中，最重要的是铁路线路的最优设计。在这个代码的实现中，我用了Kruscal的想法，然后通过函数的嵌套实现最优路径的选取的。2.代码的实现#include#include#include#include #include #define MAXSIZE 100typedef struct link int connect; int fee;/费用 struct link *next;edgenode;typedef struct node char name10;/名称 edgenode *link;city;typedef struct city vexMAXSI
5、ZE; int city_n,city_e;city_graph; city_graph ga;int total_fee=0;/记录总费用void creat(city_graph *ga)/创建辖区总信息 int i=0 ,a,b; edgenode *q; edgenode *p; printf(请输入城市辖区个数: );/城市中辖区的个数 scanf(%d,&ga-city_n); printf(请输入城市辖区间路径的总个数: );/辖区间的路径 scanf(%d,&ga-city_e); for(i=1;icity_n+1;i+)/建立城市辖区信息表 printf(请输入第%d个城市
6、辖区名称: ,i); scanf(%s,ga-vexi.name); ga-vexi.link=NULL; for(i=0;icity_e;i+)/辖区联系表(头插法) printf(请输入第%d组两个相邻辖区的编号,i+1);/还没有处理数据，比如输入的是超出规定范围的数据 p=(edgenode *)malloc(sizeof (edgenode ); q=(edgenode *)malloc(sizeof (edgenode ); scanf(%d%d,&a,&b); printf(请输入两辖区间的费用： );/两辖区间路程的费用 scanf(%d,&p-fee); q-fee=p-fe
7、e; p-connect=b; q-connect=a; p-next=ga-vexa.link;/建立两辖区间的联系 ga-vexa.link=p; q-next=ga-vexb.link; ga-vexb.link=q; void view(city_graph *ga)/输出 system(cls);/清屏。 int i; edgenode *p; for(i=1;icity_n+1;i+) p=ga-vexi.link; /printf(%sn,ga-vexi.name); printf(n与辖区 %s 相连的辖区有：n,ga-vexi.name); printf(n名称费用n); i
8、f(p=NULL) printf(-n); while(p!=NULL) printf(%s %5dn,ga-vexp-connect.name,p-fee); p=p-next; printf(nn); void insert(city_graph *ga)/导入文件中 FILE *fp; edgenode *p; int i=0; if(fp=fopen(e:辖区.txt,w+)=NULL) printf(打开文件失败!n); exit(0); for(i=1;icity_n+1;i+) p=ga-vexi.link; fputs(ga-vexi.name,fp); fprintf(fp,
9、n); fprintf(fp,%dn,p-connect); fprintf(fp,%dn,p-fee); fclose(fp);/*city_graph * load(city_graph *gb)/从文件中导出/待解决 FILE *fp; int i=1; edgenode *p; if(fp=fopen(e:辖区.txt,r+)=NULL) printf(打开文件失败!n); exit(0); while(fscanf(fp,%s%d%d,gb-vexi.name,&p-connect,&p-fee)!=EOF) p=(edgenode *)malloc(sizeof (edgenode
10、 ); p-next=gb-vexi.link; gb-vexi.link=p; i+; fclose(fp); return gb;*/city_graph * change(city_graph *ga,int min_a,int min_b)/改变俩辖区间的费用 edgenode *p,*q,*t,*t1; p=ga-vexmin_a.link; q=ga-vexmin_a.link; t1=ga-vexmin_b.link; while(p!=NULL) if(p-connect=min_b) p-fee=0; /q-next=p; q=p; p=p-next; t=ga-vexmin
11、_b.link; while(t!=NULL) if(t-connect=min_a) t-fee=0; / t1-next=t; t1=t; t=t-next; return ga;city_graph * find_next(city_graph *ga,int i)/ edgenode *p,*q; int j,min,min_sign,min_record; q=ga-vexi.link; min=q-fee; min_sign=q-connect; min_record=i; for(j=1;jcity_n+1;j+)/找费用最少的两个辖区 p=ga-vexj.link;/记下当前辖
12、区，以便在此辖区的联系链中找到此链下的最小花费路径 while(p!=NULL) if(p-feefee!=0) min=p-fee; min_sign=p-connect; min_record=j; p=p-next; if(min!=0)/把费用为0的滤去（因为在改变费用时把原来的费用给置成了0，以便判断哪些路径是比较过的） printf(%s - %s %dn,ga-vexmin_record.name,ga-vexmin_sign.name,min);/输出建设路径 total_fee=total_fee+min; ga=change(ga,min_record,min_sign);
13、 /改变两辖区间的费用，以便区分 return ga;void find(city_graph *ga)/Kruscal算法 int i; printf(nn以下是建设路径nn); printf(辖区名-辖区名-费用nn); for(i=1;icity_n+1;i+) ga=find_next(ga,i);/调用函数找全部路径中最小费用的辖区 printf(n总费用 = %dnn,total_fee);void main() /city_graph *gb; creat(&ga); view(&ga); insert(&ga);/读入文件 /gb=(city_graph *)malloc(sizeof(city_graph); /gb=load(gb);/导出到文件中 find(&ga);/未使用到从文件导出的图，而是使用了导入文件的图，因为导出文件有问题。3.运行结果：（1）城市辖区图表的信息 （2）最优建设路径的相关信息 （3）结果分析 与理论上的分析结果是一样的。可能是我选取的数据不够广泛，导致通过程序得出的结果都没发生什么不一样的变化。（4）存在的问题： 当输入非数字的字符时，没有对此情况进行解决；其次是在路径的查找中得到了相应的结果，但是却不是完美的，改变费用为零后，在查找路径之后的输出中仍然有费用为零的输出，但这个问题已经解决，只需要控制输出就可以了。
