2023年软件基础实验报告

计算机软件技术基础实验报告姓名:ＸXX班级：XＸ０X01学号:３0X０505０ＸX实验一线性表：１、建立单向链表,表长任意；2、可交互输出单链表中的内容；3、编写算法计算出自己所建单链表的长度并输出；4、删除自己所建单链表中的第K个结点，并将剩余结点输出;5、将单链表倒排，输出结果。源程序如下:#inｃｌudｅ<stdｉo.ｈ>#includｅ<malloc．ｈ>ｔypｅdｅｆintdataｔypｅ;typeｄｅｆｓtｒｕctnode/／链表结构体//｛dａtaｔypedａta;ｓｔrucｔnoｄe*ｎexｔ;}linｋｌist;liｎklist*crｅatｌist()/／建立链表//{ｉntx；ｌinkｌｉｓt*head,*s;head=NULL;priｎｔf（"\n输入链表数据："）;scａnｆ（"%d＂，&x);wｈile(x！＝0){ｓ=mａlloc(ｓizeｏf(ｌiｎｋlｉｓｔ）);//为链表开辟一系列的空间//s->datａ＝x；s-＞next=ｈead；head=s;priｎｔf("＼n输入链表数据:＂);scanf(＂%d",＆ｘ);}rｅturnheａd；}ｖoｉdｌｉstＣontｅnt（linｋlist*h)/／输出链表内容//{linｋlist*s;s=h;whｉｌe(s!=NULL){printｆ(＂%４d＂,ｓ-＞data);s＝ｓ->next;}}intlistLong(liｎｋｌｉsｔ＊h）//计算链表长度//{iｎｔi=０;liｎｋｌist＊s;s=h;whｉle(s!=NULL){i＋+；s=s->nｅｘt；｝returｎ(i);}ｖoｉdDｅlｅtｅNode(linklｉst*ｈ，iｎｔｋ)//删除第K个节点/／{intｉ=0；liｎkliｓt*p，＊q；p=h;ｉf(k==1){h=h-＞ｎeｘｔ;ｆree(p)；}ｅlｓe{wｈilｅ（i<k-1＆&p!=NULL){i＋+;ｑ=p;p=p－>nｅxt；}q->next＝ｐ－＞ｎｅxｔ;ｆrｅｅ（p);｝｝linklisｔ＊DaoXu（ｌinklｉｓｔ*h）／/逆序排列链表／/{ｌinklist*r,＊q,*p;r＝h;p=ｒ-＞ｎext;q＝p->next;iｆ（h==NＵＬＬ)pｒｉｎtｆ("链表为空\n");while（ｑ!=NＵＬL&&h!=NUＬＬ）{p->ｎext=ｒ;r=p；p=ｑ;ｑ=q->neｘｔ；}h->neｘｔ=NULＬ;ｐ->next=ｒ;ｒeturn(p);｝maiｎ()｛ｉntk,x;ｌｉnklｉst*ｈ；dｏ{prinｔf("\ｎ功能:\ｎ");printf("1．建立链表\ｎ＂)；printf（"2.输出链表内容;\ｎ＂);prinｔｆ("3.获得链表长度\ｎ＂);pｒiｎtf("4.删除第K个节点\n");printf("5.将链表倒序输出\n")；printf（"6.退出\n＂);ｐrｉntｆ("请输入功能号:\n"）;sｃanf("％d",&x);ｉf(x＜１||x>6）priｎtf("错误!＼ｎ＂）;elｓｅswitch（x)｛case1:h=creatlｉst(）;ｂｒeak；case2：lisｔLｏng（h);ｂrｅak;caｓｅ３：prinｔf(＂链表的长度是：%ｄ",liｓtLｏｎg(h))；breａk;case４：printf(＂请输入要删除的节点:＼n＂);ﻩscanｆ("%d"，&k);ﻩDｅｌeｔeNoｄe（ｈ,k);lisｔContent（h);break；caｓe5:h＝DaoXｕ(h);listCｏntent(h）;break;cａse6：exit(0);bｒeak；}}ｗhile(１);}运营结果：实验总结:1.在编写倒排链表的程序时，对于循环的计数的控制没有搞好，以致无法得到想要的链表；２.要给一个指针创建空间之后才干调用它，否则会犯错。解决办法:1.通过单步调试程序，调整循环次数，来使循环中的个参数达成自己想要的通过查阅资料,完毕对链表程序的实现。在写每一个子函数时，经常会漏掉小的判断条件,比如漏掉了判断是否为空等;尚有就是在对指针操作时，有时多加了*，或者分号写成逗号；在调试程序的过程中有很多小的错误或者判断条件错误等。实验二在交互方式完毕下列任务：1、动态交互建立二叉树,结点个数任意;2、分别用ＤLR、LDR、LRD三种方式对二叉树进行便利并输出结果；3、计算二叉树中的结点个数并输出;4、计算二叉树的深度并输出；源程序如下:#inｃｌude＂stdio.h"#inclｕde"maｌloc.ｈ＂ｓtructＢTNｏｄe{inｔdatａ; ｓtｒuctBＴNode*Ｌｃhild,*Rcｈild;};sｔｒuｃtBTＮodｅ＊buiｌｄ(strucｔBＴNode*ｐ)；stｒｕcｔBＴＮode*creatrenｔ(ｓｔｒuctＢTNode*p);voidDLR（struｃtＢTＮode＊T);stｒｕctBTNｏde＊creatreｎt（ｓtｒｕｃtＢTNode*p){ﻩintｘ； ﻩprintf("输入根：rent=")；ﻩ ﻩscａnf("%d",&x); ﻩif(x＝＝1000){ｐ=NULL;} else ﻩ{ﻩﻩp->data=x;ﻩﻩ p-＞Lchiｌd=（ｓtｒｕctBTNode*)ｍaｌloc(sｉzeof(strｕctBＴNode)); p->Ｒchild＝（ｓtructBTＮode*)malloｃ（sizeoｆ(struｃtＢTＮoｄe)); ﻩ iｆ(p＝=NUＬL)reｔurnp;ﻩp->Ｌchild=ｂｕild(p－>Lcｈild); p->Ｒcｈild=build(ｐ->Rchiｌd）; ﻩreｔurｎp; }}structBＴNode*ｂｕｉld(sｔｒuctBTNode＊p）{ intx;ﻩprinｔf("输入数据(输入值为时,表达该结点为空):value="); ｓcanf(＂％ｄ",&ｘ); ﻩif（x==1000){p=NUＬL;} else ﻩ{ p-＞data=x;ﻩﻩﻩp->Lchｉlｄ=(struｃtＢTＮodｅ*)ｍaｌlｏｃ（siｚeof（stｒuctＢTＮode));ﻩｐ->Ｒｃhild=(structＢＴＮode＊）ｍallｏc(sizｅoｆ(stｒuctＢTNode）);ﻩ ｝if（p==NＵLL）reｔurｎp；ﻩp-＞Lchiｌd=ｂuiｌd(ｐ->Ｌｃｈiｌd); ｐ-＞Ｒchiｌd＝bｕild（p->Rcｈild); ﻩｒeturｎp; ﻩ｝vｏｉdDLR（stｒuctBTNode*T){ ｉf(T==NUＬL）retｕrｎ；ﻩｐrｉntf("％d",T->ｄaｔa);ﻩＤLＲ（Ｔ->Lchild);DLR(Ｔ->Ｒchiｌd);}voiｄLＤＲ（structBＴNode*Ｔ)｛ iｆ(T=＝ＮULL)rｅｔurn；ﻩ LDＲ（T-＞Ｌcｈild);ﻩprintｆ（"%d",T－>ｄata）;ＬＤR(T->Rcｈild);}voidLRD(structBTNode*T）{ ｉf（T=＝NULＬ)rｅｔurn; LRＤ（Ｔ->Lchｉlｄ);ﻩLＲＤ（T->Rchild); ｐrintf("%d＂，T-＞daｔａ);}ｖoidｍａiｎ(){ﻩstrｕcｔBTNｏdｅ*reｎt=NＵLＬ； intflag;ﻩwｈilｅ(1) { ﻩｐｒinｔf("选择输入的操作:\ｎ1：创建\2:先序\n３:中序\n3:后序＼n"）;ﻩｓcanf(＂％ｄ",＆ｆｌａg);ﻩswitch(flag) ﻩ｛ﻩcasｅ1: rent=(sｔrucｔBTNode*)maｌloc(sizeｏf(ｓtructBTNodｅ));renｔ=creａtrent(renｔ);ﻩｂreak；ﻩcａsｅ２：DLR(reｎt)；prｉnｔf("\n"）;break; ｃaｓe3:ＬDR(rent);printｆ("＼ｎ＂);bｒeaｋ;ﻩ ﻩﻩcasｅ４:LＲＤ(ｒenｔ)；printｆ("\n＂);bｒeak；ﻩﻩ}ﻩ}}运营结果：实验总结:通过查资料完毕程序，还是在调试程序的过程中出现恩多的错误，除了一些基本的错误，也出现了判断错误,比如在进行先序，中序，后序遍历的时候都没加if(ｋ!=NULL)这个条件，导致在执行程序的时候，只进行先序遍历，然后犯错退出。实验三在交互方式下完毕下列任务:１、根据教材上算法,完毕图的深度和广度优先遍历,规定任意给定起始点，输出结果;2、根据教材上算法，完毕图的单源最短途径的算法，规定任意给定源点，输出结果;源程序如下：#incluｄe<stdio.h>#incｌude<ｍalloｃ.ｈ>＃defｉnｅQ10０0#definｅＶNｕm6stｒｕcｔGＬink{iｎtＮo；ｉntRighｔ;sｔructGＬink*Relat;｝；intG[VNum][VＮum]=//对图进行初始化//{０,23，1６,Q,45,Q, Q,0,15,50,1０,Q， ２0,Ｑ,0,1５，Ｑ，Q, Q，2０,Q,0，３5,Q，ﻩQ,Q，Q,3０,0,Q,Q,5，4,Q,Q，0｝;structＧLink*ＧL[ＶNum];ｉntViｓiteｄ[VNｕm];vｏiｄCｒeatｅGLinｋ（iｎtG［VNｕm］[VNum])／／建立邻接表/／{iｎtｉ,j;ｓｔructGLiｎk＊ｐ,*q;for(ｉ＝0;i<ＶＮum;i＋+){ＧＬ[i]=ｑ=NULL;for(j=０；ｊ<ＶNｕm;j++){ｉｆ(i!=j) iｆ((G[i][j］>０)＆&(Ｇ[i][ｊ]<K）)//该两点存在有向途径// {ｐ=（ｓｔｒucｔGLｉnk*)mａlloｃ(siｚeｏf(struｃtGLｉｎｋ））;ﻩp－>Ｎo＝j;／/将该点加入邻接表/／ﻩp－>Ｒiｇhｔ=G［i］[j]; ｉf(GL[i]==NULＬ) GL[i]=ｐ; eｌseﻩ q->Relaｔ=p;ﻩｑ=p; ｝}}}voiｄＤＦＳ（intＡ［VＮum][VNum]，inｔV)//用于进行深度优先遍历的子函数,V是起点／/{iｎti;priｎtf(＂[%d]"，V）;Vｉsiteｄ［V]=1;//将其标记为已访问//for(ｉ＝０；i<VNum；i+＋)if((A[V][i]＞０)&&(Ａ[V][i］<K)&&(Visｉtｅｄ[i]！=１))//该结点未被访问过／/ＤFS(A,i);/／访问该点/／for(i=０;i<ＶNum；ｉ＋+)ｉｆ(Vｉsiｔｅｄ[i]!＝1)DFS(Ａ,i);／/仍有未必访问过的点，访问该点//}vｏiｄBFS(intA[VNum][ＶNum],intV)／／用于广度优先遍历的子函数／／{intCQ[ＶNum］；inta=0,b,c;inti,k＝１;fｏr(ｉ=0;i<VNum;i++)CQ[i]＝K；Vｉsiｔｅｄ[V]=１;//标志为访问过//CQ[０]＝V;prinｔf（"[%d］＂,Ｖ);//将该结点放入队列/／whiｌｅ（k<6&&a＜ｋ)//仍有结点未被访问并且队列中仍有结点的后继结点未被访问/／{ｂ=CQ[ａ];for(c＝0；c<VＮum;c++)/／依次将队列中以结点为首的邻接表中的结点插入队列//iｆ(Ｖisiteｄ[c］=＝0&&A[ｂ][c]<Ｋ&&A[b][ｃ］!=0)｛prinｔf("[%d］"，ｃ);CQ[++k］=c；//未被访问过，将其插入到队列中//Visitｅd［c]＝1；//标志为访问过//}a＋+;}fｏｒ（i=0；i<ＶＮuｍ；i+＋)if(Visitｅd[i]==0)BFS（A,i);}voidShorｔ（ｉntA[VNum][VＮuｍ],ｉｎｔV)//用于计算最短途径的子函数,V是起点//{iｎtDist[VNｕm],Paｔh[VＮum];intS=０;iｎti,k;intｗm,ｕ；foｒ(ｉ=０；ｉ<VＮum;i+＋)｛Disｔ[i］=A[Ｖ][i］；//默认这两点之间即为最短途径//if(Dist[i］<K)Ｐaｔh[ｉ]=V;／/存储该途径//}S=S|（1＜<V);for(k=0;ｋ<VＮｕｍ;k＋+){wｍ=K;ｕ=V;for(i=０;i<VNｕm；i+＋)if（（(S&(1<＜i）)==0)&&(Ｄist[ｉ］<wm)）／/该两点间存在途径/／｛ｕ＝i;ﻩwm=Dist[i]；}S=Ｓ|(1<<u）;for(i＝0;i<ＶNｕm;i++)ﻩif(（(S&(1<＜i）)==0)&＆(（Dｉsｔ[u]＋Ａ［ｕ][ｉ])＜Ｄisｔ［i])) {Diｓt［i］=Ｄiｓt［u］+A[u］[ｉ];//找到新的最短途径// Paｔh[i]=u;／／更新途径长度//ﻩ｝｝fｏｒ(i=0;i＜VＮum；i+＋)//输出该源结点到其他各点的最短途径/／if((S&（1<<ｉ）)!=0）{ｋ＝i;wｈiｌe(k!=Ｖ)｛printf(＂%d<-",k)； k＝Path[ｋ];}ｐriｎｔf("%d"，V）;prinｔf("=％ｄ\n",Diｓt［i］）；}ｅlseｐriｎtf(＂NoPath:％d"，ｉ);}maｉn(）{ｉnｔi,j,ａ,b;CreａteGLｉｎk（Ｇ);ｐrｉｎｔf(＂1.深度优先遍历＼ｎ");//打印菜单//printf("2.广度优先遍历＼ｎ");ｐriｎtｆ（"3.寻找单源最短途径\n");prinｔf（＂4.退出\n＂);ｗhiｌe(1）/／完毕菜单功能/／{ｐrｉntf（"\n功能项选择从1到4:＂);scanｆ（"%d＂,&ａ);if(a==1){for（i＝0;ｉ＜ＶNum;i++)Viｓited［i]=0; priｎｔｆ("请输入第一个节点:＂); ﻩscａnf（＂％d",&ｊ)； priｎtf（"\ｎ深度遍历DFＳ是：");DFＳ(G,ｊ）；ｐｒｉnｔf（＂\n");｝iｆ（a＝=2){for(i=０;i<VＮuｍ;ｉ+＋)Ｖisｉted[i］=0;pｒiｎｔf（＂请输入第一个节点:")；ﻩ scａnｆ("%d",＆j);ﻩﻩprintf（＂\n广度遍历结果ＢＦS是:＂);ﻩﻩBFS(Ｇ,j);ｐrｉｎtf("\n"）； ｝iｆ（a==3){printf("请输入源点:");sｃａｎf("％d"，&ｂ）;pｒintf("＼n单源最短途径是:\n＂);Shｏｒt(G,b);}iｆ(a=＝４)ｂreaｋ;｝｝运营结果:实验总结:１运营时,2表达深度优先遍历,３表达广度优先遍历。碰到问题：1.建立图时,指针太过复杂，很容易搞混;2.广度优先遍历中，编写时,打印输出进入死循环；解决办法:1．通过单步调试找出赋值错误和参数调用的错误;2．将函数中的q移位移到循环外面。实验四检索和排序在交互方式下完毕下类任务:任意给定无序系列,用快速排序法对其进行排序,并记录互换次数。任意给定的无序序列,用对半检索法交互检索任意给定的关键字KＥY任意给定无序系列，用冒泡排序法对其进行排序，并记录互换次数和排序的趟数源程序如下:#inclｕｄe<ｓtdio.ｈ>intｊi;vｏidｄuibaｎ(inta[1０],intn,ｉnｔkey){ｉntlow,higｈ，mid,flag；low=0;high=n-1;flaｇ＝0;while(ｌow<＝ｈigｈ）｛mｉd＝(low+hiｇh)/2；iｆ(ａ[mid]＝=key){fｌag=1;breaｋ;}elｓeif(ｋeｙ>a[miｄ])lｏw=mｉｄ+1;elｓehigh=ｍｉｄ-1;}if(flag==1)pｒｉnｔｆ(＂是第%d个元素",miｄ+1);elｓeprintf("Ｅ＂)；}ｖｏｉdmａｏｐao（inｔａ[10],ｉｎtn)｛inti,j,temp,flag；iｎtjiaｏ,tanｇ;ｊiａｏ＝tａng=0;ｆｏr(ｉ=０;i<ｎ-１；i+＋){flag=1；ｆor（j=0；ｊ<ｎ-i-１;ｊ++)ﻩ iｆ（ａ[j+1]<ａ［j］）{ｔｅmｐ=a[j];a[j]=a[j+１]；a[j+１]=temp;jiao++；ｆlａg=0;}ﻩｔaｎg++; if(flａg=＝１)brｅａk;}pｒintf（"\ｎ互换次数和排序趟数分别是%d和%d＂,jiao,tang);}vｏidkuaｉshｕ（inｔａ[10],intｌow,inthｉｇｈ)｛ｉnti,j;inttｅｍp;ｉf(low＞=hiｇh）ｒetｕrｎ（0）;i=low;j=high;ｔｅmp=a[i];ｗhile(i！=j）{whｉle(（a［j]>=ｔｅmp)&&(j>i))j--;iｆ（j＞i）{ａ[ｉ++]＝a[j];jｉ++;}while((a[i]＜＝temp)&&(j>i）)i+＋;if(j>ｉ）｛a[j-－]＝a[i];ｊｉ++;}}a[i]＝tｅmp；kuaiｓｈu(a，ｌow,i－1）;ｋuaishｕ(a,i+1,high）;｝main（）{iｎti,a[10],n,q，p,ｔ;do{priｎtf("\ｎ１．用对半检索法，交互检索任意给定的关键