数据结构_课程设计报告

1、数据结构课程设计报告学院：计算机科学与工程 专业：计算机科学与技术 班级：09级班 学号：姓名：指导老师：时间：2010年12月一、课程设计题目:1、哈夫曼编码的实现2、城市辖区地铁线路设计3、综合排序算法的比较二、小组成员：三、题目要求：哈夫曼编码的实现打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一 各字符出现的概率。针对上述统计结果，对各字符实现哈夫曼编码对任意文章，用哈夫曼编码对其进行编码对任意文章，对收到的电文进行解码某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费 用昂贵，因此需要合理安排地铁的建设路线。从包含各辖区的地图文件中读取辖区的名称和各辖区

2、的直接距离根据上述读入的信息，给出一种铺设地铁线路的解决方案。使乘客可以 沿地铁到达各个辖区，并使总的建设费用最小。输出应该建设的地铁路线及所需要建设的总里程信息。综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大 概的执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移 动的次数。对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速 排序简单选择排序，堆排序，归并排序，基数排序。待排 序的表长不少于100，要求采用随机数。至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的 比较次数和关键

3、字移动的次数改变数据量的大小，观察统计数据的变化情况。对试验统计数据进行分析。对各类排序算法进行综合评价。四、项目安排：1、小组内分工合作分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序 算法的比较。合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并 控制进度。五、完成自己的任务：任务：城市辖区地铁线路设计1.实现方案创建城市辖区图表信息将信息写入文件从文件读取信息 最优路径的选择 / 输出最优路 I径的相关信)在整个编程中，我是通过手动输入的方式把数据写到文件中，而不是直接从 文件中读取，这个不是题目要求的，但是我想当拿到数据之后都要对数据进行处 理，干脆直

4、接手动输入得出结果。在这个代码中，最重要的是铁路线路的最优设计。在这个代码的实现中，我 用了 Kruscal的想法，然后通过函数的嵌套实现最优路径的选取的。2.代码的实现#include#include#include#include #include #define MAXSIZE 100typedef struct link(int connect;int feeJ/费用struct link *next;edgenode;typedef struct node (char name10;/ 名称edgenode *link;city;typedef struct(city vexMAXS

5、IZE;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+)/建 立城市辖区信息表(printff请输入第d个城市辖区名称：,i)

6、;scanf(%s,);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-fee;p-connect=b;q-conn

7、ect=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(Hcls);/清 屏。int i;edgenode *p;for(i=1;icity_n+1;i+)(p=ga-vexi.link;/printf(%sn,);printf(n 与辖区 %s 相连的辖区有：n,);printf(n 名称费用n);if(p=NULL)printf(n);while(p!=NUL

8、L)(printf(%s %5dn,,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(,fp);fprintf(fp,n);fprintf(fp,%dn,p-connect);fprintf(fp,%d

9、n,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,,&p-connect,&p-fee)!=EOF)(p=(edgenode *)malloc(sizeof (edgenode );p-next=gb-vexi.link;gb-vexi.link=p;i+;fclose(fp

10、);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_b.link;while(t!=NULL)(if(t-connect=min_a)t-fee=0;/ t1-next=t;

11、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;/记下当前辖区，以便在此辖区的联系链中找到此链下的最小花费路径while(p!=NULL)if(p-feefee!=0)(min=p-fee;min_sign

12、=p-connect;min_record=j;p=p-next;if(min!=0)/把费用为0的滤去(因为在改变费用时把原来的费用给 置成了 0，以便判断哪些路径是比较过的)(printf(%s%s %dn,ga-vexmin_,ga-vexmin_,min);/输出建设路径total_fee=total_fee+min;ga=change(ga,min_record,min_sign); /改变两辖区间的费用，以便区分return ga;void find(city_graph *ga)/Kruscal 算法(int i;printf(nn以下是建

13、设路径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）城市辖区图表的信息尸4-r待的i车击e n褂,-HNN 1 2to 平“K pbJb so与斗舌ITT柞连K.I字莒尽有M日林辞一 FJ=.*1)112M亍FB1精1,或有=费41pc勺可害心-杜在口勺可咨略白=土1彳小用fSfCM SCIX与猿皿XXtl iT日勺耗皿