数据结构实践周部分题目答案

苏州科技学院《数据结构程序设计》报告学号1132107107姓名郁家琪班级1121日期2012年7月5号实践报告1学号___1132107107__姓名_ 郁家琪__班级____1121_________一、实验目的：熟悉数据结构，培养良好的程序设计能力二、实验内容：（粘贴你所选择的题目）管道铺设施工的最佳方案选择需要在某个城市的n各居民区之间都可以架设管道，则在这n各居民区之间只需架设n-1条管道即可。

假设任意两个居民区之间均可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案能使总投资尽可能少，这个问题即为求网络的“最小生成树”。

要求：在所有可能架设的管道中选取n-1条，即能连通n各居民区又能使总投资最小。

连通网络可采用邻接矩阵存储，以顶点对（i，j）的形式输出最小生成树的边。

测试数据如教材p2图1.2（a）所示。

（难度系数为4）三、设计说明：写出数据结构的定义①图文件的结构②图在内存中的存储结构邻接矩阵、邻接表、三元组③最小生成树的存储结构④图形的显示结构四、功能说明：说明本程序中的每一个函数及其功能。

①准备代价文件自动随机生成、用户可以自定义②读图文件，得到图的存储结构③计算最小生成树何种算法效率更好？Prim、Kruskal④显示最小生成树文本方式：各边、总权值图形函数：屏幕初始化、端点位置的初始化、绘边函数、代价显示函数、绘无边图函数......五、调试分析内容包括：（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析（2）算法的时空分析和改进设想（3）经验与体会等通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。

设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。

在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如独立思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。

总之，此次课程设计让我受益匪浅。

六、测试结果包括输入和输出(粘贴输入输出界面，即用户屏幕)七、带注释的源程序#include<stdio.h>#define INFINIFY 9999 void main(){int date[20][20];int areanum;int edgenum;int price;printf("请输入单位长度的价格:\n");scanf("%d",&price);printf("请输入: 顶点数,边数:\n");scanf("%d,%d",&areanum,&edgenum);//初始化矩阵各元素值int i,j;for(i=0;i<areanum;i++)for(j=0;j<areanum;j++)date[i][j]=INFINIFY;//读入边int from,to,m;printf("输入边,格式为i,j,k,表示i 到j 的权值是m:\n");for(i=0;i<edgenum;i++){scanf("%d,%d,%d",&from,&to,&m);date[from][to]=m;date[to][from]=m;}//输出邻接矩阵printf("输出邻接矩阵为:\n");for(i=0;i<areanum;i++){for(j=0;j<areanum;j++){printf("%d\t",date[i][j]);}printf("\n");}//prim();//辅助数组short_way,near_area//short_way[i]表示居民区i到目前生成树中所有点集u中某个居民区（点）的路程最小值//near_area[i]表示u中能使其最小的居民区（点）int short_way[20];int near_area[20];int min;int k,s;//0已经放入u中//初始化short_way 和near_areafor(i=1;i<areanum;i++){short_way[i]=date[0][i];near_area[i]=0;}short_way[i]=0;near_area[i]=0;s=0;printf("从居民区0 出发，\n");for(i=1;i<areanum;i++)//有n-1条边要加入生成树，所以只要循环n-1次即可{min=INFINIFY;//求生成树外顶点到生成树内顶点具有最小权值的边j=1;k=1;while(j<areanum)//确定当前具有最小权值的边及位置{if(short_way[j]!=0 && short_way[j]<min){min=short_way[j];k=j;} j++;}printf("从居民区%d到居民区%d,居民区路程(边的权值)为%d\n",near_area[k],k,min);short_way[k]=0;s+=min;for(j=0;j<areanum;j++){if(date[k][j]<short_way[j]){short_way[j]=date[k][j];near_area[j]=k;}}}printf("%d个居民区之间铺设煤气管道最小生成树的总长度s 为:%d\n",areanum,s);printf("所以%d个居民区之间铺设煤气管道所需最小代价price 为:%d\n",areanum,s*price);}实践报告2学号__1132107107_____姓名__郁家琪_____班级____1121_________一、目的：熟悉数据结构，培养良好的程序设计能力二、实验内容：（粘贴你所选择的题目）实现单链表基础上的选择排序。

（难度系数为2）三、设计说明：写出数据结构的定义1.选择排序结构2.单链表结构四、功能说明：说明本程序中的每一个函数及其功能。

1.选择排序可以使数组中的数按顺序排列2.单链表结构更方便排序的运行快速，便捷3.输入输出，储存功能五、调试分析内容包括：（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析（2）算法的时空分析和改进设想（3）经验与体会等通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。

设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。

在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如独立思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。

总之，此次课程设计让我受益匪浅。

六．测试结果包括输入和输出(粘贴输入输出界面，即用户屏幕)七．带注释的源程序#include "stdio.h"#include<stdlib.h>typedef struct node{int data;struct node *next;}*Linklist,Node;Linklist creat(int n){Linklist head,r,p;int x,i;head=(Node*)malloc(sizeof(Node));r=head;printf("输入数字:\n");for(i=n;i>0;i--){scanf("%d",&x);p=(Node*)malloc(sizeof(Node));p->data=x;r->next=p;r=p;}r->next=NULL;return head;}void output(Linklist head)//将你输入的一组数重新输出，方便下面的结果的比较{Linklist p;p=head->next;do{printf("%8d",p->data);p=p->next;}while(p);printf("\n");}void paixu(Linklist head){Linklist p,q,small;int temp;for(p=head->next;p->next!=NULL;p=p->next){small=p;for(q=p->next;q;q=q->next)if(q->data<small->data)small=q;if(small!=p){temp=p->data;p->data=small->data;small->data=temp;}}printf("输出排序后的数字:\n");output(head);} //用选择排序法把小的数逐一排序，通过n-1次的得到结果void main(){Linklist head;int n;printf("输入数字的个数n:\n");scanf("%d",&n);head=creat(n);printf("输出数字:\n");output(head);paixu(head);}实践报告3学号__1132107107_____姓名__郁家琪__ _ __班级____1121_________一、目的：熟悉数据结构，培养良好的程序设计能力二、实验内容：（粘贴你所选择的题目）快速排序。

任务：用程序实现线性表基础上的冒泡和快速排序，并输出排序结果，数据可通过随机函数随机生成。