软件基础实验报告

#计算机软件技术基础

实验报告姓名：XXX班级：XX0X01学号：30X05050XX实验一线性表.■1、建立单向链表，表长任意；2、可交互输出单链表中的内容；3、编写算法计算出自己所建单链表的长度并输出；4、删除自己所建单链表中的第K个结点，并将剩余结点输出;5、将单链表倒排，输出结果。源程序如下：#include<stdio.h>#include<malloc.h>typedefintdatatype;typedefstructnode〃链表结构体〃{datatypedata;structnode*next;}linklist;linklist*creatlist()〃建立链表//{intx;linklist*head,*s;head=NULL;printf("\n输入链表数据:")；scanf("%d",&x);while(x!=O){s=malloc(sizeof(linklist));〃为链表开辟一系列的空间//s->data=x;s->next=head;head=s;printf("\n输入链表数据:");scanf("%d",&x);}returnhead;}voidlistContent(linklist*h){linklist*s;s=h;while(s!=NULL){printf("%4d",s->data);s=s->next;}}intlistLong(linklist*h){inti=0;linklist*s;s=h;while(s!=NULL){i++;s=s->next;}return(i);}voidDeleteNode(linklist*h,intk){inti=0;linklist*p,*q;p=h;if(k==1)〃输出链表内容//〃计算链表长度////删除第K个节点//h=h->next;free(p);}else{while(i<k-1&&p!=NULL){i++；q=p;p=p->next;}q->next=p->next;free(p);}〃逆序排列链表//〃逆序排列链表//linklist*DaoXu(linklist*h){linklist*r,*q,*p;r=h;p=r->next;q=p->next;if(h==NULL)printf("链表为空\n");while(q!=NULL&&h!=NULL){p->next=r;r=p;p=q;q=q_>next;}h->next=NULL;p->next=r;return(p);}main(){intk,x;linklist*h;do{printf("\n功能:\n");printf("1.建立链表\n");printf("2.输出链表内容;\n");

printf("3.获得链表长度\n");printf("4删除第K个节点\n");printf("5.将链表倒序输出\n");printf("6.退出\n");prints请输入功能号:\n");scanf("%d",&x);if(x<1||x>6)printf("错误！\n");elseswitch(x){case1:h=creatlist();break;case2:listLong(h);break;case3:printf("链表的长度是：%d",listLong(h));break;case4:printf('请输入要删除的节点:\n");scanf("%d",&k);DeleteNode(h,k);listContent(h);break;case5:h=DaoXu(h);listContent(h);break;case6:exit(0);break;}}while(1);}运行结果：D;\安D;\安潢的取啊匚十十\斷連咒件天、內IZ-TD：\妄装的探忡^匚+4\新建交阵夹\口£阳悭验一心输人谴表数扌居;毋输入链表数据;昶输入错表数据冷弓输入错表数据："输入错表数据汨容=內扁序号表表表M倒能mmmi功・-、立出出入內长甘序内L;表表锂锂镇義.:^立出出hnvI-123456.实验总结：1.在编写倒排链表的程序时，对于循环的计数的控制没有搞好，以致无法得到想要的链表；2.要给一个指针创立空间之后才能调用它，否则会出错。解决办法：1.通过单步调试程序，调整循环次数，来使循环中的个参数达到自己想要的通过查阅资料，完成对链表程序的实现。在写每一个子函数时，常常会遗漏小的判断条件，比如遗漏了判断是否为空等；还有就是在对指针操作时，有时多加了*，或者分号写成逗号；在调试程序的过程中有很多小的错误或者判断条件错误等。实验二件错误等。实验二在交互方式完成下列任务:1、动态交互建立二叉树，结点个数任意；2、分别用DLR、LDR、LRD三种方式对二叉树进行便利并输出结果；3、计算二叉树中的结点个数并输出；4、计算二叉树的深度并输出；源程序如下：include"stdio.h"include"malloc.h"structBTNode{intdata;structBTNode*Lchild,*Rchild;};structBTNode*build(structBTNode*p);structBTNode*creatrent(structBTNode*p);voidDLR(structBTNode*T);structBTNode*creatrent(structBTNode*p){intx;printf("输入根：rent=");scanf("%d",&x);if(x==1000){p=NULL;}else{p->data=x;p->Lchild=(structBTNode*)malloc(sizeof(structBTNode));p->Rchild=(structBTNode*)malloc(sizeof(structBTNode));if(p==NULL)returnp;p->Lchild=build(p->Lchild);p->Rchild=build(p->Rchild);returnp;}}structBTNode*build(structBTNode*p){intx;printf("输入数据(输入值为时，表示该结点为空)：value=");scanf("%d",&x);

if(x==1000){p=NULL;}else{p->data=x;p->Lchild=(structBTNode*)malloc(sizeof(structBTNode));p->Rchild=(structBTNode*)malloc(sizeof(structBTNode));}if(p==NULL)returnp;p->Lchild=build(p->Lchild);p->Rchild=build(p->Rchild);returnp;}voidDLR(structBTNode*T){if(T==NULL)return;printf("%d",T->data);DLR(T->Lchild);DLR(T->Rchild);}voidLDR(structBTNode*T){if(T==NULL)return;LDR(T->Lchild);printf("%d",T->data);LDR(T->Rchild);}voidLRD(structBTNode*T){if(T==NULL)return;LRD(T->Lchild);LRD(T->Rchild);printf("%d",T->data);}voidmain(){structBTNode*rent=NULL;intflag;while(1){printf("选择输入的操作：\nl:创建\2:先序\n3：中序\n3:后序\n");scanf("%d",&flag);switch(flag){case1:

rent=(structBTNode*)malloc(sizeof(structBTNode));rent=creatrent(rent);break;case2:DLR(rent);printf("\n");break;case3:LDR(rent);printf("\n");break;case4:LRD(rent);printf("\n");break;}}}运行结果：:rent=b据倾入值为0^1000-:rent=b据倾入值为0^1000-話《触入道为0：1000-亍居£输入值为0Y1000-亍居£输入值为0Y1000-亍居£输入值为0Y1000-亍居£输入值为0Y1000-泳输入值为0Y1000-认数据哦入蕃为0:1000,LA教据丈输入値为0Y10B0,为0^1000,表更该结点为空＞：value=1表更该结点为空＞：value=1000表巫该结点为空八ualue=2表巫该结点为空八ualue=5表巫该结点为空八ualue=1000表巫该结点为空八ualue=1000表巫该结点为空八ualue=1000恚巫该结点为空儿ualue=8表丞该结点为空儿ualue=1000表示该结点为空儿ualue=1000QQQQ作

操£的中后1劉先中后

・・：tHU-312L2m*实验总结：通过查资料完成程序，还是在调试程序的过程中出现恩多的错误，除了一些基本的错误，也出现了判断错误,比如在进行先序，中序，后序遍历的时候都没加讦（k!二NULL）这个条件，导致在执行程序的时候，只进行先序遍历，然后出错退出。在交互方式下完成下列任务：1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果；2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果;源程序如下:#include<stdio.h>#include<malloc.h>#defineQ1000#defineVNum6structGLink{intNo;intRight;structGLink*Relat;};intG[VNum][VNum]=//对图进行初始化//0,23,16,Q,45,Q,Q,0,15,50,10,Q,20,Q,0,15,Q,Q,Q,20,Q,0,35,Q,Q,Q,Q,30,0,Q,Q,5,4,Q,Q,0{};structGLink*GL[VNum];intVisited[VNum];voidCreateGLink(intG[VNum][VNum])//建立邻接表//{inti,j;

structGLink*p,*q;

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

{GL[i]=q=NULL;for(j=0;j<VNum;j++){if(i!=j)if((G[i][j]>0)&&(G[i][j]<K))//该两点存在有向路径//{p=(structGLink*)malloc(sizeof(structGLink));p->No=j;//将该点加入邻接表//p->Right=G[i][j];if(GL[i]==NULL)GL[i]=p;elseq->Relat=p;q=p;}}}voidDFS(intA[VNum][VNum],intV)//用于进行深度优先遍历的子函数，V是起点//{inti;printf("[%d]",V);Visited[V]=1;for(i=0;i<VNum;i++)if((A[V][i]>0)&&(A[V][i]<K)&&(Visited[i]!=1))DFS(A,i);for(i=0;i<VNum;i++)if(Visited[i]!=1)DFS(A,i);}voidBFS(intA[VNum][VNum],intV){intCQ[VNum];inta=0,b,c;inti,k=1;for(i=0;i<VNum;i++)CQ[i]=K;Visited[V]=1;CQ[0]=V;printf("[%d]",V);//将其标记为已访问////该结点未被访问过////访问该点////仍有未必访问过的点，访问该点////用于广度优先遍历的子函数////标志为访问过////将该结点放入队列//while(k<6&&a<k)//仍有结点未被访问并且队列中仍有结点的后继结点未被访问//{b=CQ[a];for(c=0;c<VNum;c++)//依次将队列中以结点为首的邻接表中的结点插入队列//if(Visited[c]==0&&A[b][c]<K&&A[b][c]!=0)//未被访问过，将其插入到队列中//////未被访问过，将其插入到队列中////标志为访问过//CQ[++k]=c;Visited[c]=1;}a++;}for(i=0;i<VNum;i++)if(Visited[i]==0)BFS(A,i);//用于计算最短路径的子函数，V//用于计算最短路径的子函数，V是起点////默认这两点之间即为最短路径////存储该路径//voidShort(intA[VNum][VNum],intV){intDist[VNum],Path[VNum];intS=0;inti,k;intwm,u;for(i=0;i<VNum;i++){Dist[i]=A[V][i];if(Dist[i]<K)Path[i]=V;}S=S|(1<<V);for(k=0;k<VNum;k++){wm=K;u=V;//该两点间存在路径//该两点间存在路径//if(((S&(1<<i))==0)&&(Dist[i]<wm)){u=i;wm=Dist[i];}S=S|(1<<u);

for(i=0;i<VNum;i++)if(((S&(1<<i))==0)&&((Dist[u]+A[u][i])<Dist[i])){Dist[i]=Dist[u]+A[u][i];//找到新的最短路径//Path[i]=u;//更新路径长度//}}for(i=0;i<VNum;i++)//输出该源结点到其他各点的最短路径//if((S&(1<<i))!=0){k=i;while(k!=V){printf("%d<-",k);k=Path[k];}printf("%d",V);printf("=%d\n",Dist[i]);}elseprintf("NoPath:%d",i);}main(){inti,j,a,b;CreateGLink(G);printf("1.深度优先遍历\n");〃打印菜单//printf("2广度优先遍历\n");printf("3•寻找单源最短路径\n");printf("4.退出\n");while(1)//完成菜单功能//{printf("\n功能项选择从1到4:");scanf("%d",&a);if(a==1){for(i=0;i<VNum;i++)Visited[i]=0;printf("请输入第一个节点:");scanf("%d",&j);printf("\n深度遍历DFS是:");DFS(G,j);printf("\n");}if(a==2){for(i=0;i<VNum;i++)Visited[i]=0;printf("请输入第一个节点:");scanf("%d",&j);printf("\n广度遍历结果BFS是:");BFS(G,j);printf("\n");}if(a==3){printf("请输入源点：");scanf("%d",&b);printf("\n单源最短路径是:\n");Short(G,b);}if(a==4)break;

运行结果：B"E:\c++\c4-4-\kjh；匚语言事习DebugXkjh?.exe"i.searchtFegraplideepfirst2_seapchthecfpaplibroadfivst_findtiiesFuptestpath4_exitTOC\o"1-5"\h\zpleaseinputanumfrom1to4：1pleaseinputthefivstnodei1lieBesultofDFSis：tl][23[01[41133pleaseInputanunfram1to4；2leaseinputtLefirstniide：：21TFeResultofBFSis=til[21[3]【幻[0]【51pleaseinputanunfran1to4；3pleaseinputthesourcenode；1TFeResultofShortestpathis:0<-2<-1=35=0<-1=15<-2<-1=3K<-1=10NoFat11；5pleaseinputanunfv'jn1to4；4^ressanykesptocontinue实验总结：1运行时，2表示深度优先遍历，3表示广度优先遍历。碰到问题:1.建立图时，指针太过复杂，很容易搞混;2.广度优先遍历中，编写时，打印输出进入死循环;解决办法：1.通过单步调试找出赋值错误和参数调用的错误;2.将函数中的q2.将函数中的q移位验I循环四面。检索和排序在交互方式下完成下类任务：1、任意给定无序系列，用快速排序法对其进行排序，并统

计交换次数。2、任意给定的无序序列，用对半检索法交互检索任意给定的关键字KEY3、任意给定无序系列，用冒泡排序法对其进行排序，并统计交换次数和排序的趟数源程序如下：#include<stdio.h>intji;voidduiban(inta[10],intn,intkey){intlow,high,mid,flag;low=0;high=n-1;flag=0;while(low<=high){mid=(low+high)/2;if(a[mid]==key){flag=1;break;}elseif(key>a[mid])low=mid+1;elsehigh=mid-1;}if(flag==1)printf("是第％d个元素",mid+1);elseprintf("E");}voidmaopao(inta[10],intn){inti,j,temp,flag;intjiao,tang;jiao=tang=0;for(i=0;i<n-1;i++){flag=1;for(j=0;j<n-i-1;j++)if(a[j+1]<a[j]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;jiao++;flag=0;}tang++;if(flag==1)break;}printf("\n交换次数和排序趟数分别是%d和%d",jiao,tang);}voidkuaishu(inta[10],intlow,inthigh){inti,j;inttemp;if(low>=high)return(0);i=low;j=high;temp=a[i];while(i!=j){while((a[j]>=temp)&&(j>i))j--;if(j>i){a[i++]=a[j];ji++;}while((a[i]<=temp)&&(j>i))i++;if(j>i){a[j--]=a[i];ji++;}}

a[i]=temp;kuaishu(a,low,i-l);kuaishu(a,i+l,high);}main(){inti,a[10],n,q,p,t;do{printf(〃\用对半检索法，交互检索任意给定的关键字KEY");printf(〃\ni!快速排序法对其进行排序，并统计交换次数");printf(〃\用冒泡排序法对其进行排序，并统计交换次数和排序的趟数");printf("\npleasewritetheorder:");scanf("%d"，&i);while(i〈l||i〉4){printf("\nTheorderyouprintiswrong!,pleaseprintagain!");scanf("%d"，&i);}switch(i){case1:printf("pleaseinput:\n");for(n=0;n〈10;n++)scanf("%d"，&a[n]);do{printf("pleaseinpi\tn");scanf("%d"，&q);duiban(a,10,q);printf(〃:\n〃)；scanf("%d"，&p);}while(p==1);break;case2:ji=0;printf("pleaseinput:d\rt"i);for(n=0;n〈8;n++)scanf("%d"，&a[n]);kuaishu(a,0,9);printf("快速排序的交