还剩17页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
计算机软件技术基础上机编程上机题一线性表
1.建立单向链表;表长任意;
2.可交互输出单链表中的内容;
3.编写算法计算出自己所建单链表的长度并输出;
4.输出自己所建立单链表中的第K个结点,并将剩余结点输出;
5.将单链表倒排并输出结果#includestdio.h#includemalloc.htypedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;linklist*Creatlist//建立链表//{intx;linklist*h*s;h=NULL;printf\npleaseinputthedateendwith0:\n;printf\nInputdata:;scanf%dx;whilex!=0{s=mallocsizeoflinklist;s-data=x;s-next=h;h=s;printf\nInputdata:;scanf%dx;}returnh;}voidPutlistlinklist*h//输出单链表中的内容//{linklist*s;s=h;whiles!=NULL{printf%4ds-data;s=s-next;}}intLonglinklist*h//计算链表的长度//{inti=0;linklist*s;s=h;whiles!=NULL{i++;s=s-next;}returni;}voidDeletelinklist*hintk//删除链表中第k个结点//{inti=0;linklist*p1*p2;p1=h;ifk==1{h=h-next;freep1;}else{whileik-1p1!=NULL{i++;p2=p1;p1=p1-next;}p2-next=p1-next;freep1;}}linklist*Nixulinklist*h//逆序输出链表//{linklist*r*q*p;r=h;p=r-next;q=p-next;ifh==NULLprintfthelinklistisempty\n;//空表//whileq!=NULLh!=NULL{p-next=r;r=p;p=q;q=q-next;}h-next=NULL;p-next=r;returnp;//返回根结点//}main{intkx;linklist*h;do//输出菜单//{printf\nqingshurumingling:\n;printf
1.jianlilianbiao;\n;printf
2.shuchulianbiaozhongdeneirong;\n;printf
3.shuchulianbiaodechangdu;\n;printf
4.shanchudiKgejiedian;\n;printf
5.jianglianbiaodaoxubingshuchu;\n;printf
6.tuichuchengxu;\n;printfqingshuru1--6deshuzi:\n;scanf%dx;ifx1||x6printferror!\n;elseswitchx{case1:h=Creatlist;break;case2:Putlisth;break;case3:printflianbiaodechangdushi%dLongh;break;case4:printfInputthenodeyouwanttodelete:\n;scanf%dk;Deletehk;Putlisth;break;case5:h=Nixuh;Putlisth;break;case6:exit0;break;//退出程序//}}while1;}退出程序;上机题二二叉树
1.动态交互建立二叉树,结点个数任意;
2.分别用DLRLDRLRD三种方式对二叉树进行遍历并输出结果;
3.计算二叉树中结点个数并输出;
4.计算二叉树深度并输出源程序#includestdio.h#includemalloc.hstructTreeNode{intdata;structTreeNode*Lchild;structTreeNode*Rchild;};structTreeNode*create//用于建立二叉树的子函数//{structTreeNode*T;inta;scanf%da;ifa==0returnNULL;else//动态建立二叉树//{T=structTreeNode*mallocsizeofstructTreeNode;T-data=a;//建立根结点//T-Lchild=create;//递归建立左子树//T-Rchild=create;//递归建立右子树//}returnT;}voidPrestructTreeNode*T//用于进行先序遍历的子函数//{ifT!=NULL{printf%5dT-data;//访问根结点//PreT-Lchild;//递归访问左子树//PreT-Rchild;//递归访问右子树//}}voidMidstructTreeNode*T//用于进行中序遍历的子函数//{ifT!=NULL{MidT-Lchild;//递归访问左子树//printf%5dT-data;//访问根结点//MidT-Rchild;//递归访问右子树//}}voidPoststructTreeNode*T//用于进行后序遍历的子函数//{ifT!=NULL{PostT-Lchild;//递归访问左子树//PostT-Rchild;//递归访问右子树//printf%5dT-data;}}voidvisitstructTreeNode*T//用于访问二叉树的子函数//{printftheresultofDLR:;PreT;printf\n;printftheresultofLDR:;MidT;printf\n;printftheresultofLRD:;PostT;printf\n;}intleafstructTreeNode*T//用于计算叶子结点的子函数//{intab;ifT==NULLreturn0;elseifT-Lchild==NULLT-Rchild==NULL//判断该结点是叶子结点//return1;else{a=leafT-Lchild;//递归计算左子树上叶子数//b=leafT-Rchild;//递归计算右子树上叶子数//returna+b+1;}}intmaxintxinty//用于取两数的较大值的子函数//{ifxyreturnx;elsereturny;}intdeepstructTreeNode*T//用于计算二叉树深度的子函数//{intk=0;ifT==NULLreturn0;elseifT-Lchild==NULLT-Rchild==NULL//该结点有孩子,深度增加1//return1;elsereturn1+maxdeepT-LchilddeepT-Rchild;//递归求取树的深度//}main{intmnp;structTreeNode*T;printfcreateatree\n;T=create;//建立二叉树//printf
1.visitthetree\n;//打印菜单//printf
2.putoutthetotalnumberofnode\n;printf
3.putoutthedepthofthetree\n;printf
4.exit\n;while1{printf\npleaseinput1-4:;//完成菜单的相应功能//scanf%dm;ifm==1visitT;ifm==2{n=leafT;printfthetotalnumberofleavesinthetreeis%d\nn;}ifm==3ifm==3{p=deepT;printfthedepthofthetreeis%d\np;}ifm==4break;}}调试结果createatree
1025040689600056850069000250001.visitthetree
2.putoutthetotalnumberofnode
3.putoutthedepthofthetree
4.exitpleaseinput1-4:thetotalnumberofleavesinthetreeis10pleaseinput1-4:pleaseinput1-4:pleaseinput1-4:pleaseinput1-4:pleaseinput1-4:1theresultofDLR:12546896568569theresultofLDR:15496868556692theresultofLRD:96885695664521pleaseinput1-4:2thetotalnumberofleavesinthetreeis10pleaseinput1-4:3thedepthofthetreeis7pleaseinput1-4:4Pressanykeytocontinue上机题三图 在交互方式下完成下列任务
1、根据教材上算法,完成图的深度和广度优先遍历,要求任意给定起始点,输出结果;
2、根据教材上算法,完成图的单源最短路径的算法,要求任意给定源点,输出结果程序#includestdio.h#includemalloc.h#defineM1000#defineVNum6structGLink{intNo;intRight;structGLink*Relat;};intG[VNum][VNum]=1//对图进行初始化//{13111M41MM0155010M13M015MMM13M017MMMM260MMMM3M0};structGLink*GL[VNum];intVisited[VNum];voidCreateGLinkintG[VNum][VNum]//建立邻接表//{intij;structGLink*p*q;fori=0;iVNum;i++{GL[i]=q=NULL;forj=0;jVNum;j++{ifi!=jifG[i][j]0G[i][j]M//该两点存在有向路径//{p=structGLink*mallocsizeofstructGLink;p-No=j;//将该点加入邻接表//p-Right=G[i][j];ifGL[i]==NULLGL[i]=p;elseq-Relat=p;q=p;}}}}voidDFSintA[VNum][VNum]intV//用于进行深度优先遍历的子函数,V是起点//{inti;printf[%d]V;Visited[V]=1;//将其标记为已访问//fori=0;iVNum;i++ifA[V][i]0A[V][i]MVisited[i]!=1//该结点未被访问过//DFSAi;//访问该点//fori=0;iVNum;i++ifVisited[i]!=1DFSAi;//仍有未必访问过的点,访问该点//}voidBFSintA[VNum][VNum]intV//用于广度优先遍历的子函数//{intCQ[VNum];inta=0bc;intik=1;fori=0;iVNum;i++CQ[i]=M;Visited[V]=1;//标志为访问过//CQ
[0]=V;printf[%d]V;//将该结点放入队列//whilek6ak//仍有结点未被访问并且队列中仍有结点的后继结点未被访问//{b=CQ[a];forc=0;cVNum;c++//依次将队列中以结点为首的邻接表中的结点插入队列//ifVisited[c]==0A[b][c]MA[b][c]!=0{printf[%d]c;CQ[++k]=c;//未被访问过,将其插入到队列中//Visited[c]=1;//标志为访问过//}a++;}fori=0;iVNum;i++ifVisited[i]==0BFSAi;}voidShortintA[VNum][VNum]intV//用于计算最短路径的子函数,V是起点//{intDist[VNum]Path[VNum];intS=0;intik;intwmu;fori=0;iVNum;i++{Dist[i]=A[V][i];//默认这两点之间即为最短路径//ifDist[i]MPath[i]=V;//存储该路径//}S=S|1V;fork=0;kVNum;k++{wm=M;u=V;fori=0;iVNum;i++ifS1i==0Dist[i]wm//该两点间存在路径//{u=i;wm=Dist[i];}S=S|1u;fori=0;iVNum;i++ifS1i==0Dist[u]+A[u][i]Dist[i]{Dist[i]=Dist[u]+A[u][i];//找到新的最短路径//Path[i]=u;//更新路径长度//}}fori=0;iVNum;i++//输出该源结点到其他各点的最短路径//ifS1i!=0{k=i;whilek!=V{printf%d-k;k=Path[k];}printf%dV;printf=%d\nDist[i];}elseprintfNoPath:%di;}main{intijab;CreateGLinkG;printf
1.searchthegraphdeepfirst\n;//打印菜单//printf
2.searchthegraphbroadfirst\n;printf
3.findtheshortestpath\n;printf
4.exit\n;while1//完成菜单功能//{printf\npleaseinputanumfrom1to4:;scanf%da;ifa==1{fori=0;iVNum;i++Visited[i]=0;printfpleaseinputthefirstnode:;scanf%dj;printf\nTheResultofDFSis:;DFSGj;printf\n;}ifa==2{fori=0;iVNum;i++Visited[i]=0;printfpleaseinputthefirstnode:;scanf%dj;printf\nTheResultofBFSis:;BFSGj;printf\n;}ifa==3{printfpleaseinputthesourcenode:;scanf%db;printf\nTheResultofShortestpathis:\n;ShortGb;}ifa==4break;}}结果调试截图上机题四检索和排序在交互方式下完成下列任务
1、任意给定无序序列,用对半检索法,交互检索任意给定的关键字KEY;
2、任意给定无序序列,用快速排序法对进行排序,并统计交换次数;
3、任意给定无序序列,用冒泡排序法对进行排序,并统计交换次数和排序的趟数;程序#includestdio.h#defineM100structRedType{intkey;intother;};inta;intSearchstructRedTypeST[]intnintkey//用于进行对半查找的子函数//{intlowhighmid;low=0;high=n-1;whilelow=high//未检索完毕//{mid=low+high/2;//指向中间值//ifST[mid].key==keyreturnmid+1;//检索成功//elseifkeyST[mid].keyhigh=mid-1;//待查找值小于中间值,到前一半查找//elselow=mid+1;//待查找值大于中间值,到后一半查找//}return0;} intQuickSortstructRedTypeL[]intlowinthigh//用于快速排序的子函数//{intijt=0;structRedTypetemp;iflow=high//待排序队列空,结束//return0;i=low;j=high;temp=L[i];whileij{whileL[j].key=temp.keyji//从后向前找出第一个小于关键值的数据//j--;ifij{L[i]=L[j];t++;}//交换,同时交换次数加1//whileL[i].key=temp.keyji//从前向后找出第一个大于关键值的数据//i++;ifij{L[j]=L[i];t++;}//交换,同时交换次数加1//}L[i]=temp;printf\n\nTheQukSortLoop[%d]is:i;forj=0;ja;j++printf%dL[j].key;returnt+QuickSortLlowi-1+QuickSortLi+1high;//对前后块分别进行快速排序//}voidbubsortstructRedTypeL[]intn//用于冒泡排序的子函数//{intij=0mfag=1t=0;structRedTypex;whilejnfag0{fag=0;//标志有无交换//fori=0;in-1;i++ifL[i+1].keyL[i].key//满足交换条件//{fag++;//标记发生交换//x=L[i];//将相邻数据交换//L[i]=L[i+1];L[i+1]=x;t++;//交换次数加1//}iffag//输出交换过程//{j++;//排序次数加1//form=0;mn;m++printf%5dL[m].key;printf\n\n;}}printfthesortedarrayis:;//输出排序完之后的数据//form=0;mn;m++printf%5dL[m].key;printf\n;printf\nthetimesofsortis:%dj;//给出排序次数//printf\nthetotaltimesofexchangeis:%d\nt;//给出交换次数//}main{intbmnij;structRedTypeS[M]T[M];printfinputthelengthofthedata:;//预先给定数据的个数//scanf%da;printfpleaseinputthedata\n;fori=0;ia;i++scanf%dS[i].key;printf\n
1.quicksort\n;//打印菜单//printf
2.bubsort\n;printf
3.searchthedatayouwanttosee\n;printf
4.exit\n;while1//完成菜单功能//{printf\npleaseinputanumberfrom1to4:;scanf%db;ifb==1{fori=0;ia;i++T[i].key=S[i].key;j=QuickSortT0a-1;printf\nthetotaltimesofexchangeis:%d\nj;}ifb==2{fori=0;ia;i++T[i].key=S[i].key;bubsortTa;}ifb==3{printfpleaseinputthethekeyvalue:;//输入欲查找的关键值//scanf%dm;n=SearchTam;ifn==0printfcantfindthekeyvalue\n;elseprintfthelocationofthekeyvalueis:%d\nn;}ifb==4break;}}结果调试截图心得体会 在这学期的计算机软件技术的实验中,我学会了很多一开始拿到实验题目时感觉有点无从下手,后来静下心来慢慢分析这些题目,发现要用到的知识都是平时学的东西,只是程序比较复杂,要分成几个部分于是我在编一个程序前把程序的流程在纸上整理好,突然间也发现了流程图在这时候的重要性,因为以前编的程序大多相对简单,思路可以在脑海里记着,现在发现流程图可以把程序里面的主程序和子程序分清楚,把各个程序段的嵌套调用关系理清,这是编程序一个很好的方法同时还认识到学好C语言和学好数据结构有联系,但是却是不同的两个概念,数据结构是一个新的内容,而C语言知识提供一个平台去描述这个内容的在认识到这些后,我关掉了其他的网页,认真的投入实验中,编程,调试,修改,运行,不停的循环,枯燥但也不乏趣味,错的多也不用怕,那样你可以见到很多没见过的错误,争取以后避免编程,调试,修改,调试再修改,过程也许有些枯燥,但你得承认,当你运行出结果时,真的很有成就感以后会更加努力的!。