程序设计实训报告

PAGE55数据结构课程实训报告设计题目：（1）建立通讯录（2）电网建设造价系统专业计算机科学与技术班级09计算机科学与技术（1）班学生学号指导教师起止时间南昌工程学院2010年12月目录绪言11.1课程设计的目的21.2课程设计的基本要求2课程设计内容32.1建立通讯录32.2电网建设造价系统10实训总结15附：程序源代码一、课程设计的目的数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程实训可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程实训主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1、独立思考，独立完成：课程实训中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。3、按照课程设计的具体要求写课程实训报告，要求题目按照如下几个内容认真完成；其中包括：a）需求分析：在该部分中叙述，每个模块的功能要求b）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。三、课程设计内容1、建通讯录【问题描述】设实现通讯录查找系统。【基本要求】(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码为关键字建立表；(3)显示、插入、删除、查找并显示给定电话号码的记录；(4)要求人机界面友好，使用图形化界面；【实现提示】主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。算法描述：首先用结构体的类型定义姓名、电话号码、住址。然后建立线性链表存储通讯录，每次增加记录时，从键盘上输入新纪录的基本信息插入表中，要修改记录时按输入的电话号码为关键字查找记录，若有则修改，若无则不能修改；查找记录时从键盘输入关键字，即记录的电话号码，从表中查找是否有记录的号码等于查找关键字，若有则查找成功，否则查找不成功；删除时，先在通讯录中查找记录，若查找成功则删除，否则无法删除。算法实现：#include<stdlib.h>#include<windows.h>#include<iostream.h>#include<string.h>#include<stdio.h>#include<malloc.h>typedefstructpnode/*个人记录结点类型*/{charname[8];/*姓名*/chartel[16];/*电话号码*/charaddress[30];/*住址*/}personnode;personnode*person;charfilename[20];/*存储通讯录名称的数组*/FILE*fp;voidcreate()/*增加记录*/{personnode*person;person=(personnode*)malloc(sizeof(personnode));printf("\n请输入通讯录名:");scanf("%s",filename);if((fp=fopen(filename,"w"))==NULL){ printf("\n没有输入通讯录名，不能建立通讯录！"); exit(0);}fprintf(fp,"%-10s%-20s%-50s\n","姓名","电话号码","住址");printf("\n请输入姓名、电话号码及住址（以空格隔开，以#结束）\n");scanf("%s",person->name);while(strcmp(person->name,"#")){ scanf("%s%s",person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); scanf("%s",person->name);}fclose(fp);}voidlist()/*显示通讯录的信息*/{if((fp=fopen(filename,"r"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n************************************************\n"); printf("%24s\n","通讯录"); while(!feof(fp)) {fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address);printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); } fclose(fp); printf("**************************************************\n\n");}voidappend()/*增加记录*/{ personnode*person; person=(personnode*)malloc(sizeof(personnode));if((fp=fopen(filename,"a"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n请输入要添加的姓名、电话号码及住址\n"); scanf("%s%s%s",person->name,person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); fclose(fp);}voidfind()/*查找记录*/{ intk=0; chartelkey[16]; printf("\n请输入要查找记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"rb"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { fscanf(fp,"%s%s%s",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { printf("\n\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); k=1; } }if(!k)printf("\n\n对不起，通讯录中没有此人的记录!\n");fclose(fp);}voidalter()/*修改记录*/{ longoffset; intk=0; chartelkey[16]; printf("\n请输入要修改记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n请输入新姓名、电话号码及住址:"); scanf("%s%s%s",person->name,person->tel,person->address); fseek(fp,offset,SEEK_SET); printf("%ld",ftell(fp)); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); } else printf("\n对不起，通讯录中没有此人的记录！\n"); fclose(fp);}voidcancel()/*删除记录*/{longoffset; intk=0; charm; chartelkey[16]; printf("\n请输入要删除记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n确实要删除？y/n"); scanf("%c",&m); if(m='y') { fseek(fp,offset,SEEK_SET); fprintf(fp,"%-14s%-24s%-48s\n","","",""); } } else printf("\n对不起，通讯录中没有此人的记录！\n"); fclose(fp);}voidmain(){ intm,n=1; system("CLS"); create(); while(n) { printf("\n"); printf("\t\t1append\n"); printf("\t\t2find\n"); printf("\t\t3alter\n"); printf("\t\t4cancel\n"); printf("\t\t5list\n"); printf("\t\t6quit\n"); printf("\n"); printf("\t请选择（1~~6）\n"); scanf("%d",&m); switch(m) { case1:append();break; case2:find();break; case3:alter();break; case4:cancel();break; case5:list();break; case6:exit(0); } }}心得体会：许多运算中都用到查找，针对不同的数据对象可以选用不同的查找方法，例如现在的通讯录记录数据时，整个通讯录的状态可能经常变化，因此，首先就要确定通讯录的存储结构必须采用链式的，否则在频繁的插入和删除操作中其效率会较低，在确定好存储结构后，才决定选用何种查找方法。有时在程序设计中，不一定非要全部采用自己编写的源代码，如果有标准的库函数，同样可以使用标准的库函数，这样既可以节约时间，也便于统一规范。如果要想较好的利用某种编程语言自带的库函数，则必须充分地理解该编程语言库函数的功能、特点，否则就无法引用。应注意的问题：在C++中“delete”为关键字，因此在编程时应将函数“delete（）”的名称进行修改，在此改为“cancel（）”否则在编译时会出现错误。在C++中清屏函数不能用“clrscr()”可改为system("CLS")可起到同样的效果，头文件为"#include<windows.h>"在写插入、删除、修改、添加、显示等函数时不需要每个函数都定义“personnode*person”只需在程序前面定义一下就好了，否则编译时将出现警告!运行结果如下图所示：2、电网建设造价模拟系统【问题描述】假设一个城市有n个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。【基本要求】（1）用连通图来表示n个城市之间以及n个城市之间可能设置的电网线路。（2）用菜单选择方式完成下列功能：创建电网顶点；添加电网的边；构造最小生成树；显示最小生成树；退出程序。算法描述:设无向连通网G=（V,E），其中V为网图中所有顶点的集合（即问题描述中的城市集合），E为网图中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T={}。Prim算法的思想是，从所有u属于U，v属于V-U的边中，选取具有最小权值的边（u,v),将顶点v加入集合U中，将边（u,v)加入集合T中，如此不断反复，直到U=V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。算法实现：#include<stdio.h>#include<windows.h>#include<stdlib.h>#definemaxlen10#definelarge999#definenull0typedefstruct{ inta[maxlen],b[maxlen],w[maxlen];/*第k条边的起点，终点，权值*/ charvexs[maxlen];/*顶点信息集合*/ intvexnum,arcnum;/*顶点数和边数*/ intarcs[maxlen][maxlen];/*邻接矩阵*/}graph;graphg;/*g为图类型变量*/voidprint_graph(graphg)/*输出邻接矩阵*/{ inti,j; printf("邻接矩阵:\n"); printf("vertex\t");/*vertex为顶点标识*/ for(i=0;i<g.vexnum;i++) printf("%4c",g.vexs[i]);/*输出邻接矩阵中的所有顶点*/ printf("\n"); for(i=0;i<g.vexnum;i++)/*输出邻接矩阵中的所有值*/ { printf("%4c\t",g.vexs[i]); for(j=0;j<g.vexnum;j++) printf("%4d",g.arcs[i][j]); printf("\n"); }}graphcre_grah(graphg)/*创建图结构*/{ inti,j,k,c=999;/*设c值999为无穷大*/ for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) g.arcs[i][j]=c;/*初始化邻接矩阵中的所有元素值为无穷大*/ for(k=0;k<g.arcnum;k++) { g.arcs[g.a[k]-1][g.b[k]-1]=g.w[k];/*对邻接矩阵赋值*/ g.arcs[g.b[k]-1][g.a[k]-1]=g.w[k]; } returng;/*返回创建的图*/}voidprim(graphg)/*用prim算法求最小生成树*/{ inti,j,k,min; intlowcost[maxlen];/*保存权值的数组*/ intcloset[maxlen];/*保存最小生成树结点的数组*/ printf("最小生成树的边为:\n"); for(i=1;i<g.vexnum;i++)/*将邻接矩阵中第1行的所有权值存入lowcost数组*/ { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[1]=0;/*选择顶点1作为出发点*/ j=1; for(i=1;i<g.vexnum;i++)/*找权值最小的边*/ { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; } printf("(%c,%c),",g.vexs[closet[k]],g.vexs[k]);/*输出权值最小的边*/ closet[k]=0;/*设置为已访问标志*/ for(j=1;j<g.vexnum;j++)/*考虑经过已选出的最短边，修改其他边的权值*/ if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; closet[j]=k; } }}voidmain(){ inti,j,k; system("CLS"); printf("请输入城市的个数，城市间道路的条数:"); scanf("%d,%d",&i,&j); g.vexnum=i; g.arcnum=j; for(i=0;i<g.vexnum;i++)/*输入所有顶点信息*/ { getchar(); printf("\n第%d个顶点的信息:",i+1); g.vexs[i]=getchar(); } for(k=1;k<=g.arcnum;k++) { printf("\t请输入第%d条边的起点:",k); scanf("%d",&g.a[k-1]); printf("\n请输入第%d条边的终点:",k); scanf("%d",&g.b[k-1]); printf("\n请输入第%d条边的权值:",k); scanf("%d",&g.w[k-1]); } cre_grah(g); prim(g);}心得体会:图是基本数据结构类型中最为复杂的一类，也是最有应用价值的一类数据结构，许多应用问题可以通过它来解决。如现在的工程造价问题就是一类重要的应用问题。在利用图解决各类问题时，首先要确定选用何种存储结构最为合适。选用何种存储结构必须依据具体的实际情况而定，因为不同的存储结构都具有其适用的情形。利用图的相关算法解决实际问题时，一定要对算法思想有深刻的理解。应注意的问题：在C++中清屏函数不能用“clrscr()”可改为system("CLS")可起到同样的效果，头文件为"#include<windows.h>"。在运行程序时输入城市的个数，城市间道路的条数应输入正确，否则将得不到正确的结果。应将函数“voidprint_grah(graphg)”放在函数“graphcre_grah(graphg)”之前，否则就会出错！运行结果如下图所示：实训总结：刚开始学数据结构时感觉不是很好学，但是现在学完了整本书，再回头看看书又觉得也不是那么难学！可能是刚开始学吧，对编程还不是很了解，所以为了完成这次实训着实花了我不少时间，而且程序也不是设计的很好。在这次实训中遇到了不少问题，比如：在C++中清屏函数不能用“clrscr()”可改为system("CLS")可起到同样的效果，头文件为"#include<windows.h>"、在C++中“delete”为关键字，因此在编程时应将函数“delete（）”的名称进行修改，在此改为“cancel（）”否则在编译时会出现错误等，一开始还不知道是怎么回事，后来经过查阅资料才渐渐明白。通过这次实训我觉得数据结构这门课程比较重要，也学到了不少东西。让我渐渐开始对数据结构感兴趣，对编程感兴趣。通过这次实训，我觉得要学好编程应该多看看别人的程序，应该通过图书馆、上网多查阅资料，这样日积月累，才能真正提高自己的编程能力。像这次实训，要不是有网，好多错误真的是改不出来。总而言之，这次实训对我帮助挺大的！ 数据结构 课程实训报告设计题目：（1）建立通讯录（2）电网建设造价系统专业计算机科学与技术班级09计算机科学与技术（1）班学生余飞学号2009101101指导教师康平起止时间2010.12.27——2011.1.7南昌工程学院2010年12月一．建立通讯录a）需求分析：(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码为关键字建立表；(3)显示、插入、删除、查找并显示给定电话号码的记录；(4)要求人机界面友好，使用图形化界面；b）概要设计主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。c）详细设计#include<stdlib.h>#include<windows.h>#include<iostream.h>#include<string.h>#include<stdio.h>#include<malloc.h>typedefstructpnode{charname[8];chartel[16];charaddress[30];}personnode;personnode*person;charfilename[20];/*存储通讯录名称的数组*/FILE*fp;voidcreate()/*增加记录*/{personnode*person;person=(personnode*)malloc(sizeof(personnode));printf("\n请输入通讯录名:");scanf("%s",filename);if((fp=fopen(filename,"w"))==NULL){ printf("\n没有输入通讯录名，不能建立通讯录！"); exit(0);}fprintf(fp,"%-10s%-20s%-50s\n","姓名","电话号码","住址");printf("\n请输入姓名、电话号码及住址（以空格隔开，以#结束）\n");scanf("%s",person->name);while(strcmp(person->name,"#")){ scanf("%s%s",person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); scanf("%s",person->name);}fclose(fp);}voidlist()/*显示通讯录的信息*/{if((fp=fopen(filename,"r"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n**********************\n"); printf("%24s\n","通讯录"); while(!feof(fp)) {fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address);printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); } fclose(fp); printf("**************************************************\n\n");}voidappend()/*增加记录*/{ personnode*person; person=(personnode*)malloc(sizeof(personnode));if((fp=fopen(filename,"a"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n请输入要添加的姓名、电话号码及住址\n"); scanf("%s%s%s",person->name,person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); fclose(fp);}voidfind()/*查找记录*/{ intk=0; chartelkey[16]; printf("\n请输入要查找记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"rb"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { fscanf(fp,"%s%s%s",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { printf("\n\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); k=1; } }if(!k)printf("\n\n对不起，通讯录中没有此人的记录!\n");fclose(fp);}voidalter()/*修改记录*/{ longoffset; intk=0; chartelkey[16]; printf("\n请输入要修改记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n请输入新姓名、电话号码及住址:"); scanf("%s%s%s",person->name,person->tel,person->address); fseek(fp,offset,SEEK_SET); printf("%ld",ftell(fp)); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); } else printf("\n对不起，通讯录中没有此人的记录！\n"); fclose(fp);}voidcancel()/*删除记录*/{longoffset; intk=0; charm; chartelkey[16]; printf("\n请输入要删除记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n确实要删除？y/n"); scanf("%c",&m); if(m='y') { fseek(fp,offset,SEEK_SET); fprintf(fp,"%-14s%-24s%-48s\n","","",""); } } else printf("\n对不起，通讯录中没有此人的记录！\n"); fclose(fp);}voidmain(){ intm,n=1; system("CLS"); create(); while(n) { printf("\n"); printf("\t\t1append\n"); printf("\t\t2find\n"); printf("\t\t3alter\n"); printf("\t\t4cancel\n"); printf("\t\t5list\n"); printf("\t\t6quit\n"); printf("\n"); printf("\t请选择（1~~6）\n"); scanf("%d",&m); switch(m) { case1:append();break; case2:find();break; case3:alter();break; case4:cancel();break; case5:list();break; case6:exit(0); } }}d）调试分析二、电网建设造价模拟系统a）需求分析：（1）用连通图来表示n个城市之间以及n个城市之间可能设置的电网线路。（2）用菜单选择方式完成下列功能：创建电网顶点；添加电网的边；构造最小生成树；显示最小生成树；退出程序。b）概要设计设无向连通网G=（V,E），其中V为网图中所有顶点的集合（即问题描述中的城市集合），E为网图中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T={}。Prim算法的思想是，从所有u属于U，v属于V-U的边中，选取具有最小权值的边（u,v),将顶点v加入集合U中，将边（u,v)加入集合T中，如此不断反复，直到U=V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。c）详细设计#include<stdio.h>#include<windows.h>#include<stdlib.h>#definemaxlen10#definelarge999#definenull0typedefstruct{ inta[maxlen],b[maxlen],w[maxlen];/*第k条边的起点，终点，权值*/ charvexs[maxlen];/*顶点信息集合*/ intvexnum,arcnum;/*顶点数和边数*/ intarcs[maxlen][maxlen];/*邻接矩阵*/}graph;graphg;/*g为图类型变量*/voidprint_graph(graphg)/*输出邻接矩阵*/{ inti,j; printf("邻接矩阵:\n"); printf("vertex\t");/*vertex为顶点标识*/ for(i=0;i<g.vexnum;i++) printf("%4c",g.vexs[i]);/*输出邻接矩阵中的所有顶点*/ printf("\n"); for(i=0;i<g.vexnum;i++)/*输出邻接矩阵中的所有值*/ { printf("%4c\t",g.vexs[i]); for(j=0;j<g.vexnum;j++) printf("%4d",g.arcs[i][j]); printf("\n"); }}graphcre_grah(graphg)/*创建图结构*/{ inti,j,k,c=999;/*设c值999为无穷大*/ for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) g.arcs[i][j]=c;/*初始化邻接矩阵中的所有元素值为无穷大*/ for(k=0;k<g.arcnum;k++) { g.arcs[g.a[k]-1][g.b[k]-1]=g.w[k];/*对邻接矩阵赋值*/ g.arcs[g.b[k]-1][g.a[k]-1]=g.w[k]; } returng;/*返回创建的图*/}voidprim(graphg)/*用prim算法求最小生成树*/{ inti,j,k,min; intlowcost[maxlen];/*保存权值的数组*/ intcloset[maxlen];/*保存最小生成树结点的数组*/ printf("最小生成树的边为:\n"); for(i=1;i<g.vexnum;i++)/*将邻接矩阵中第1行的所有权值存入lowcost数组*/ { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[1]=0;/*选择顶点1作为出发点*/ j=1; for(i=1;i<g.vexnum;i++)/*找权值最小的边*/ { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; } printf("(%c,%c),",g.vexs[closet[k]],g.vexs[k]);/*输出权值最小的边*/ closet[k]=0;/*设置为已访问标志*/ for(j=1;j<g.vexnum;j++)/*考虑经过已选出的最短边，修改其他边的权值*/ if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; closet[j]=k; } }}voidmain(){ inti,j,k; system("CLS"); printf("请输入城市的个数，城市间道路的条数:"); scanf("%d,%d",&i,&j); g.vexnum=i; g.arcnum=j; for(i=0;i<g.vexnum;i++)/*输入所有顶点信息*/ { getchar(); printf("\n第%d个顶点的信息:",i+1); g.vexs[i]=getchar(); } for(k=1;k<=g.arcnum;k++) { printf("\t请输入第%d条边的起点:",k); scanf("%d",&g.a[k-1]); printf("\n请输入第%d条边的终点:",k); scanf("%d",&g.b[k-1]); printf("\n请输入第%d条边的权值:",k); scanf("%d",&g.w[k-1]); } cre_grah(g); prim(g);}d）调试分析三．课程实训总结：1.调试程序前先进行人工检查。在写好一个程序以后，不要匆匆忙忙上机，而应对纸面上的程序进行人工检查。这一步是十分重要的，它能发现程序设计人员由于疏忽而造成的多数错误。而这一步骤往往容易被人忽视。有人总希望把一切推给计算机系统去做，但这样就会多占用机器时间，作为一个程序人员应当养成严谨的科学作风，每一步都要严格把关，不把问题留给后面的程序。2.调试程序的时候不可避免的会出现错误，有的时候就那么几个，但有时会有很多，如果系统提示的出错信息多，应当从上到下一一改正。有时显示出一大片出错信息往往使人感到问题严重，无从下手。其实可能只有一二个错误。例如，对使用的变量未定义，编译时就会对所有含该变量的语句发出出错信息；有的是少了“}”或多了“}”有的是书写语句时忘记写“；”或是全角的“；”了，只要加上一个变量定义，或填加“}；”就所有错误都消除了。3.在编译时给出语法错误的信息，可以根据提示的信息具体找出程序中出错之处并改正之。应当注意的是有时提示的出错并不是真正出错的行，如果在提示出错的行上找不到错误的话应当到上一行再找。有时提示出错的类型并非绝对准确，由于出错的情况繁多各种错误互有关联，因止要善于分析，找出真正的错误，而不要只从字面意义上找出错信息，钻牛角尖。4.有时在程序设计中，不一定非要全部采用自己编写的源代码，如果有标准的库函数，同样可以使用标准的库函数，这样既可以节约时间，也便于统一规范。5.所编的程序应当采用结构化程序方法编程，以增加可读性并且可以尽可能多加注释，以帮助理解每段程序的作用。6.通过实训，我们更加认识到：数据结构这门课程的学习不应当只局限在课本里，我们应当多去机房里编辑程序，然后不断调试，这样才能在实践中掌握理论知识，做到学以致用。数据结构课程实训报告设计题目：（1）电网建设造价系统（2）建通讯录专业计算机科学与技术系班级计算机科学与技术（1）班学生朱曦学号2009101142指导教师康平起止时间2010.12.27-2011.01.07南昌工程学院2010年12月一、课程设计的目的数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程实训可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程实训主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1、独立思考，独立完成：课程实训中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。3、按照课程设计的具体要求写课程实训报告，要求题目按照如下几个内容认真完成；其中包括：a）需求分析：在该部分中叙述，每个模块的功能要求b）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。课程实训总结：（保存在word文档中）总结可以包括：课程实训过程的收获、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程实训过程中对《数据结构》课程的认识等内容；4、每组实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分；（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“200413498高魁”。该文件夹下至少包括：“源代码”、“课程实训报告”、“可执行文件”。由学习委员收集刻盘按规定时间统一上交）。5、课程实训报告不要附原代码，可以对重点函数及结构进行说明。报告格式参照附件。6、报告提交时间：第19周星期五检查，迟交无成绩。形式：课程设计报告(要求打印）和电子文档(统一刻盘）。电网建设造价模拟系统算法描述:设无向连通网G=（V,E），其中V为网图中所有顶点的集合（即问题描述中的城市集合），E为网图中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T={}。Prim算法的思想是，从所有u属于U，v属于V-U的边中，选取具有最小权值的边（u,v),将顶点v加入集合U中，将边（u,v)加入集合T中，如此不断反复，直到U=V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。算法实现：#include<stdio.h>#include<windows.h>#include<stdlib.h>#definemaxlen10#definelarge999#definenull0typedefstruct{ inta[maxlen],b[maxlen],w[maxlen];/*第k条边的起点，终点，权值*/ charvexs[maxlen];/*顶点信息集合*/ intvexnum,arcnum;/*顶点数和边数*/ intarcs[maxlen][maxlen];/*邻接矩阵*/}graph;graphg;/*g为图类型变量*/voidprint_graph(graphg)/*输出邻接矩阵*/{ inti,j; printf("邻接矩阵:\n"); printf("vertex\t");/*vertex为顶点标识*/ for(i=0;i<g.vexnum;i++) printf("%4c",g.vexs[i]);/*输出邻接矩阵中的所有顶点*/ printf("\n"); for(i=0;i<g.vexnum;i++)/*输出邻接矩阵中的所有值*/ { printf("%4c\t",g.vexs[i]); for(j=0;j<g.vexnum;j++) printf("%4d",g.arcs[i][j]); printf("\n"); }}graphcre_grah(graphg)/*创建图结构*/{ inti,j,k,c=999;/*设c值999为无穷大*/ for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) g.arcs[i][j]=c;/*初始化邻接矩阵中的所有元素值为无穷大*/ for(k=0;k<g.arcnum;k++) { g.arcs[g.a[k]-1][g.b[k]-1]=g.w[k];/*对邻接矩阵赋值*/ g.arcs[g.b[k]-1][g.a[k]-1]=g.w[k]; } returng;/*返回创建的图*/}voidprim(graphg)/*用prim算法求最小生成树*/{ inti,j,k,min; intlowcost[maxlen];/*保存权值的数组*/ intcloset[maxlen];/*保存最小生成树结点的数组*/ printf("最小生成树的边为:\n"); for(i=1;i<g.vexnum;i++)/*将邻接矩阵中第1行的所有权值存入lowcost数组*/ { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[1]=0;/*选择顶点1作为出发点*/ j=1; for(i=1;i<g.vexnum;i++)/*找权值最小的边*/ { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; } printf("(%c,%c),",g.vexs[closet[k]],g.vexs[k]);/*输出权值最小的边*/ closet[k]=0;/*设置为已访问标志*/ for(j=1;j<g.vexnum;j++)/*考虑经过已选出的最短边，修改其他边的权值*/ if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; closet[j]=k; } }}voidmain(){ inti,j,k; system("CLS"); printf("请输入城市的个数，城市间道路的条数:"); scanf("%d,%d",&i,&j); g.vexnum=i; g.arcnum=j; for(i=0;i<g.vexnum;i++)/*输入所有顶点信息*/ { getchar(); printf("\n第%d个顶点的信息:",i+1); g.vexs[i]=getchar(); } for(k=1;k<=g.arcnum;k++) { printf("\t请输入第%d条边的起点:",k); scanf("%d",&g.a[k-1]); printf("\n请输入第%d条边的终点:",k); scanf("%d",&g.b[k-1]); printf("\n请输入第%d条边的权值:",k); scanf("%d",&g.w[k-1]); } cre_grah(g); prim(g);}心得体会:图是基本数据结构类型中最为复杂的一类，也是最有应用价值的一类数据结构，许多应用问题可以通过它来解决。如现在的工程造价问题就是一类重要的应用问题。在利用图解决各类问题时，首先要确定选用何种存储结构最为合适。选用何种存储结构必须依据具体的实际情况而定，因为不同的存储结构都具有其适用的情形。利用图的相关算法解决实际问题时，一定要对算法思想有深刻的理解。应注意的问题：在C++中清屏函数不能用“clrscr()”可改为system("CLS")可起到同样的效果，头文件为"#include<windows.h>"。在运行程序时输入城市的个数，城市间道路的条数应输入正确，否则将得不到正确的结果。应将函数“voidprint_grah(graphg)”放在函数“graphcre_grah(graphg)”之前，否则就会出错！运行结果如下图所示：建立通讯录算法描述：首先在计算机存储器上建立一个表，即所需的通讯录，通讯录中记录的基本信息由姓名、电话号码、住址组成。每次增加记录时，从键盘上输入新纪录的基本信息，然后写入表；而修改记录，则打开表，在表中查找相应的记录，如有则修改，否则不能修改；查找记录时从键盘输入关键字，即记录的电话号码，然后打开表，从表中查找是否有记录的号码等于查找关键字，若有则查找成功，否则查找不成功；删除时，先在通讯录中查找记录，若查找成功则删除，否则无法删除。算法实现：#include<stdlib.h>#include<windows.h>#include<iostream.h>#include<string.h>#include<stdio.h>#include<malloc.h>typedefstructpnode/*个人记录结点类型*/{charname[8];/*姓名*/chartel[16];/*电话号码*/charaddress[30];/*住址*/}personnode;personnode*person;charfilename[20];/*存储通讯录名称的数组*/FILE*fp;voidcreate()/*增加记录*/{personnode*person;person=(personnode*)malloc(sizeof(personnode));printf("\n请输入通讯录名:");scanf("%s",filename);if((fp=fopen(filename,"w"))==NULL){ printf("\n没有输入通讯录名，不能建立通讯录！"); exit(0);}fprintf(fp,"%-10s%-20s%-50s\n","姓名","电话号码","住址");printf("\n请输入姓名、电话号码及住址（以空格隔开，以#结束）\n");scanf("%s",person->name);while(strcmp(person->name,"#")){ scanf("%s%s",person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); scanf("%s",person->name);}fclose(fp);}voidlist()/*显示通讯录的信息*/{if((fp=fopen(filename,"r"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n************************************************\n"); printf("%24s\n","通讯录"); while(!feof(fp)) {fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address);printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); } fclose(fp); printf("**************************************************\n\n");}voidappend()/*增加记录*/{ personnode*person; person=(personnode*)malloc(sizeof(personnode));if((fp=fopen(filename,"a"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} printf("\n请输入要添加的姓名、电话号码及住址\n"); scanf("%s%s%s",person->name,person->tel,person->address); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); fclose(fp);}voidfind()/*查找记录*/{ intk=0; chartelkey[16]; printf("\n请输入要查找记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"rb"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { fscanf(fp,"%s%s%s",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { printf("\n\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); k=1; } }if(!k)printf("\n\n对不起，通讯录中没有此人的记录!\n");fclose(fp);}voidalter()/*修改记录*/{ longoffset; intk=0; chartelkey[16]; printf("\n请输入要修改记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n请输入新姓名、电话号码及住址:"); scanf("%s%s%s",person->name,person->tel,person->address); fseek(fp,offset,SEEK_SET); printf("%ld",ftell(fp)); fprintf(fp,"%-10s%-20s%-50s\n",person->name,person->tel,person->address); } else printf("\n对不起，通讯录中没有此人的记录！\n"); fclose(fp);}voidcancel()/*删除记录*/{longoffset; intk=0; charm; chartelkey[16]; printf("\n请输入要删除记录的电话号码:"); scanf("%s",telkey);if((fp=fopen(filename,"r+"))==NULL){ printf("\n不能打开通讯录！"); exit(0);} while(!feof(fp)) { offset=ftell(fp); fscanf(fp,"%s%s%s\n",person->name,person->tel,person->address); if(!strcmp(telkey,person->tel)) { k=1; break; } } if(k) { printf("\n已查到，记录为:"); printf("%-10s%-20s%-50s\n",person->name,person->tel,person->address); printf("\n确实要删除？y/n"); scanf("%c",&m); if(m='y') { fseek(fp,offset,SEEK_SET); fprintf(fp,"%-14s%-24s%-48s\n","","",""); } } else printf("\n对不