软件基础实验报告

1、作者:日期：计算机软件技术基础实验报告姓名:XXX班级：XX0X01学号：30X05050XX实验线性表1、建立单向链表，表长任意；2、可交互输出单链表中的内容；3、编写算法计算出自己所建单链表的长度并输出；4、删除自己所建单链表中的第K个结点，并将剩余结点输出;5、将单链表倒排，输出结果。源程序如下：#include#includeVmalloc.htypedefintdatatype；typedefstructnode/链表结构体datatypedata;struetnode*next;link1ist；linklist*creat1ist()建立链表/intx;1inklist*head

2、,*s；head=NULL;printf(n输入链表数据：);scanf(%d，&x);whi1e(x!=0)s=ma1loc(sizeof(1inklist);为链表开辟一系列的空间/s-data=x;snext=head;head=s;printf(n输入链表数据：”)；scanf(n%d，&x);returnhead；voidlistContent(link1ist*h)/输出链表内容/link1ist*s；s=h;while(s!=NULL)printf(%4d,s-data);s=s-next;int1istLong(linklist*h)/计算链表长度/inti=0；linklis

3、t*s;s=h;while(s!=NULL)i+；s=s-next；return(i);voidDeleteNode(link1ist*h,intk)/删除第K个节点/inti=0;linklist*p,*q;P=h;if(k=1)h=hnext；free(p);elsewhile(inext；qnext=p-next;free(p);linklist*DaoXu(linklist*h)逆序排列链表/linklist*r,*q,*p;r=h;p=rnext;q=p-next；if(h=NULL)printf(链表为空n);while(q!=NULL&h!=NULL)p-next=r;r=p;p

4、=q；q=q-next;h-next=NULL;p-next=r；return(p);main()intk,x;linklist大h；doprintf(n功能:n);printf(”l.建立链表n)；printf(2.输出链表内容；n);printf(3.获得链表长度n);printf(4.删除第K个节点n)；printf(”5将链表倒序输出n);printf(6.退出n);printf(请输入功能号:n)；scanf(%d,&x);if(x6)printf(”错误!n)；elseswitch(x)case1：h=creatlist();break;case2:listLong(h);brea

5、k;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(O);break;1while(1)；运行结果:输入链表数据詔3输入链表数据詔41while(1)；运行结果:输入链表数据詔3输入链表数据詔4输入错表数据赳弓输入错表数据汚石输入错表数据汚石的出出入k功234-Jrrl4内离茶表表表M倒内长鬥序输入错表数据咱6

6、k-5.M表表表6k-5.M表表表K-z倒能链链mi功:V一出出入矍输内：表表锂锂S義.-立出出hnvX-122456.实验总结：1在编写倒排链表的程序时，对于循环的计数的控制没有搞好，以致无法得到想要的链表；2.要给一个指针创立空间之后才能调用它，否则会出错。解决办法：1通过单步调试程序，调整循环次数,来使循环中的个参数达到自己想要的通过查阅资料，完成对链表程序的实现。在写每一个子函数时，常常会遗漏小的判断条件，比如遗漏了判断是否为空等;还有就是在对指针操作时，有时多加了*,或者分号写成逗号；在调试程序的过程中有很多小的错误或者判断条件错误等。实验二在交互方式完成下列任务：1、动态交互建立二

7、叉树，结点个数任意；2、分别用DLR、LDR、LRD三种方式对二叉树进行便利并输出结果；3、计算二叉树中的结点个数并输出；4、计算二叉树的深度并输出；源程序如下：includestdio.hinc1udemal1oc.hstructBTNodeintdata;structBTNode*Lchi1d,*Rchi1d;structBTNode*build(structBTNode*p);structBTNode*creatrent(structBTNode*p);voidDLR(structBTNode*T);structBTNode*creatrent(structBTNode*p)。intx;

8、。printf(输入根:rent=);。scanf(%d,&x);。if(x=1000)p=NULL；eIsep-data=x；pLchiId=(structBTNode*)malloc(sizeof(structBTNode)；p-RchiId=(structBTNode*)malloc(sizeof(structBTNode);if(p=NULL)returnp;pLchild=build(pLchild);p-Rchild=build(pRchild)；returnp;structBTNode*bui1d(struct盯Node*p)intx;printf(输入数据(输入值为时，表示该结

9、点为空):value=)；scanf(%d,&x)；if(x=1000)p=NULL;elsepdata=x;p-Lchild=(structBTNode*)malloc(sizeof(structBTNode)；pRchild=(structBTNode*)malloc(sizeof(structBTNode)；if(p=NULL)returnp;pLchild=build(p-Lchild);p-Rchild=build(p-Rchild);returnp;voidDLR(structBTNode*T)f(T=NULL)return；printf(%d,T-data);DLR(TLchil

10、d)；DLR(TRchild);voidLDR(structBTNode*T)if(T=NULL)return;LDR(T-Lchi1d);。printf(%d,T-data)；LDR(TRchi1d)；voidLRD(struetBTNode*T)if(T=NULL)return；。LRD(TLchi1d);bLRD(T-Rchild);bprintf(”%d,T-data)；voidmain()bstructBTNode*rent=NULL;intflag；bwhile(1)bbprintf(选择输入的操作：nl:创建2：先序n3：中序n3:后序n)；bscanf(%d,&flag);bs

11、witch(flag)bcase1:brent=(structBTNode*)malloc(sizeof(structBTNode);rent=creatrent(rent);bbreak;case2:DLR(rent);printf(n);break;case3：LDR(rent);printf(n)；break;bbbcase4:LRD(rent);printf(、n);break;运彳丁结果:rent=6据倾入值为01080-話触入道为0：1000-亍居输入值为:rent=6据倾入值为01080-話触入道为0：1000-亍居输入值为0Y1000-亍居输入值为0Y1000-泳输入值为0Y1

12、000-?居输入值0Y1000,)入数亍居哦入蕃为0Y1000,认数据哦入蕃为0:1000,LA数扌居贏入置0Y10B0,为01000,表更该结点为31：value=1表更该结点为空：value=1000表巫该结点为空八ualue=2表巫该结点为空八ualue=5表巫该结点为空八ualue=1000表巫该结点为空八ualue=1000表巫该结点为空八ualue=1000恚巫该结点为空儿ualue=8表丞该结点为空儿ualue=1000表示该结点为空儿ualue=1000QQ作操的中后1劉先中后：tHU-312L2m*实验总结:通过查资料完成程序,还是在调试程序的过程中出现恩多的错误，除了一些基

13、本的错误，也出现了判断错误，比如在进行先序，中序，后序遍历的时候都没加if(k!=NULL)这个条件，导致在执行程序的时候，只进行先序遍历，然后出错退出。实验三出错退出。实验三在交互方式下完成下列任务：1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果；2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果;源程序如下：#inc1ude#include#defineQ1000#defineVNum6structGLinkintNo；intRight;structGLink*Relat；;0,23,16,Q,45,bQ,0,15,50,10,Q,20

14、,Q,0,15,Q,Q,Q,20,Q,0,35,Q,bQ,Q,Q,30,0,Q,Q,5,4,Q,Q,0intGVNumVNum=/对图进行初始化/Q,;structGLink大GLVNum;intVisitedVNum;voidCreateGLink(intGVNumVNum)立邻接表voidCreateGLink(intGVNumVNum)立邻接表/inti,j；structGLink*p,*q;for(i=0;iVVNum；i+)GLi=q=NULL;for(j=0;jVVNum；j+)if(i!=j)if(Gij0)&(GijNo=j;/该两(structGLink);/将该p-Righ

15、t=Gij；if(GLi=NULL)GLi=p;elseqRelat=p;q=p;voidDFS(intAVNumVNum,intV)/用于进行深度优先遍历的子函数,V是起点/inti;printf(%d,V)；VisitedV=1；/将其标记为已访问/for(i=0;iVNum;i+)if0)&(AViVK)&(Visitedi!=1)/该结点未被访问过/DFS(A,i);/访问该点/for(i=0；iVNum;i+)if(Visitedi!=1)DFS(A,i);/仍有未必访问过的点，访问该点/用于广度/标/将该结点voidBFS(intAVNumVNum/用于广度/标/将该结点intCQ

16、VNum;inta=0,b,c;inti,k=1；for(i=0;iVNum；i+)CQi=K;VisitedV=1；志为访问过/CQ0=V;printf(”%d,V);放入队列/while(kV6&ak)/仍有结点未被访问并且队列中仍有结点的后继结点未被访问/b=CQa；for(c=0；cVVNum;c+)/依次将队列中以结点为首的邻接表中的结点插入队列/if(Visitedc=0&AbcK&Abc!=0)printf(%d,c);CQ+k=c;/未被访问过，将其插入到队列中/Visitedc=1;/标志为访问过/a+;for(i=0;iVVNum;i+)if(Visitedi=0)BFS(

17、A,i);voidShort(intAVNumVvoidShort(intAVNumVNum,intV)起点/用于计算最短路径的子函数V是intDistVNum,PathVNum；intS=0；inti,k；intwm,u；for(i=0；iVNum;i+)Disti=AVi；/默认这两点之间即为最短路径/if(DistiK)Pathi=V;/存储该路径/S=S|(1VVV);for(k=0；kVNum；k+)wm=K;u=V;for(i=0；iVVNum;i+)if(S&(1Vi)=0)&(Distiwm)/该两点间存在路径/u=i;wm=Disti;S=S|(1u);for(i=0;iVV

18、Num;i+)if(S&(1Vi)=0)&(Distu+Aui)VDisti)。Disti=Distu+Aui;/找到新的最短路径/Pathi=u;/更新路径长度/。for(i=0;iVVNum;i+)/输出该源结点到其他各点的最短路径/if(S&(1i)!=0)k=i；while(k!=V)printf(%d-k);k=Pathk;printf(%d,V);Printf(=%dn,Disti)；elseprintf(NoPath:%d,i);main()inti,j,a,b;CreateGLink(G);Printf(1.深度优先遍历n);打印菜单/Printf(2.广度优先遍历n);pri

19、ntf(3.寻找单源最短路径n);printf(4.退出n);/while(1)/完成菜单功能/printf（n功能项选择从1到4:“）;scanf(%d,&a);if(a=1)for(i=0;iVNum;i+)Visitedi=0;printf(请输入第一个节点：);scanf(%d,&j);printf(n深度遍历DFS是:)；DFS(G,j);printf(n)；if(a=2)for(i=0;iVNum；i+)Visitedi=0;printf(请输入第一个节点:);bscanf(%d,&j)；bPrintf(n广度遍历结果BFS是:)；bBFS(G,j)；printf(n);bif(a

20、=3)printf(请输入源点：);scanf(%d,&b);printf(n单源最短路径是:n)；Short(G,b);if(a=4)break；运行结果:tstEc+cn-H-kjhC语言uglgh7.exesearchthegraphdeepfirstseapchthegpaplibroadfivst8_findtiiesFurtestpath4_exitTOC o 1-5 h zpleaseinputanunfvum1to4：1Ktleaseinputthefivstnode：1IlieBesultofDFSis：til2101【41131【51pleaseinputanunfrom1

21、to4；2|tleaseinputtliefirstnode-1TFeResultofBFSis=til1213【切0【51pleaseinputanunfrom1to4；3jjeleaseinputtiiesourcenode；1lieResultofShortestpathla:0-2-1=351=0-1=15-2-1=30intji;voidduiban(inta1O,intn,intkey)intlow,high,mid,flag;1ow=0;high=n-1;flag=0;while(1owamid)1ow=mid+1;elsehigh=mid-1;if(flag=1)prin廿(是

22、第d个元素,mid+1);elseprintf(E)；voidmaopao(inta10,intn)inti,j,temp,flag；intjiao,tang;jiao=tang=0;for(i=0；in-1;i+)flag=1;for(j=0;jn-i-1；j+)“if(aj+1=high)return(0)；i=low;j=high;temp=ai;while(i!=j)while(aj=temp)&(ji)j；if(ji)ai+=aj;ji+;while(aii)i+;if(ji)aj-=ai;ji+;ai=temp;kuaishu(a,low,l)；kuaishu(a,i+l,high

23、);main()inti,a10,n,q,p,t；doprintf(n1用对半检索法,交互检索任意给定的关键字KEY);printf(n2.用快速排序法对其进行排序，并统计交换次数);printf(n3.用冒泡排序法对其进行排序，并统计交换次数和排序的趟数”);printf(npleasewritetheorder：);scanf(%d,&i);while(i4)printf(nTheorderyouprintiswrong!,pleaseprintagain!);scanf(%d,&i)；switch(i)case1:printf(pleaseinput:n);for(n=0;n10；n+)scanf(%dn，&an);doprintf(pleaseinput:n)；。scanf(%d,&q);duiban(a,10,q);0printf(:n);scanf(%d，&p);000while(p=1);break;case2:ji=0;0printf(pleaseinputdata：n)；for(n=0；n8;n+)scanf(%d,&an);kuaishu(a,0,9)；printf(n快速排序的交换次数是%d,ji)；printf(n结果是)；00for(n=0；n10;n+)printf(%d,an)；break；case3：0print