实践性考核实验

1过程性考核实验2实验一、单链表的插入和删除实验二、括号匹配检查实验三、图的深度优先遍历实验四、排序算法的比较实验五、查找算法的比较3实验一、单链表的插入和删除4实验二、括号匹配检查5实验三、图的广度优先遍历实验名称：图的广度优先遍历实验目的：熟悉图的邻接表存储方式，掌握图的结构体定义，掌握图的深度优先遍历算法。熟悉队列的基本操作实验内容：1，定义队列及其基本操作函数2，定义图的邻接表存储结构体3，定义图的输入函数4，定义图的遍历函数5，设计main函数，输入图的顶点个数，是否有向图，由用户输入图的邻接矩阵和遍历起点序号，输出遍历顶点序号6运行结果：7运行结果：V1V2V4V7V3V6V58运行结果：9图的邻接矩阵结构体定义typedefstringVertexType;typedefintEdgeType;structMGraph{VertexTypeV[MaxNum+1];EdgeTypeE[MaxNum+1][MaxNum+1];intVisited[MaxNum+1];intn,e;};10循环队列结构体定义typedefintDataType;#defineMAXQSIZE100typedefstruct{DataTypedata[MAXQSIZE];intfront,rear;}SqQueue;11队列的基本操作定义voidInitQueue(SqQueue&Q){Q.front=Q.rear=0;}intQueueEmpty(SqQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intQueueFull(SqQueue&Q){if(Q.front==(Q.rear+1)%MAXQSIZE)return1;elsereturn0;}12队列的基本操作定义voidEnQueue(SqQueue&Q,DataTypee){if((Q.rear+1)%MAXQSIZE==Q.front)return;Q.data[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}voidDeQueue(SqQueue&Q,DataType&e){if(Q.front==Q.rear)return;e=Q.data[Q.front];Q.front=(Q.front+1)%MAXQSIZE;}13深度优先遍历函数定义voidBFSTraverse(structMGraph&G,intStarti){for(i=1;i=G.n;i++)G.Visited[i]=0;InitQueue(Q);cout广度优先遍历序列如下:endl;if(G.Visited[Starti]==0){G.Visited[Starti]=1;cout访问G.V[Starti]endlEnQueue(Q,Starti);while(!QueueEmpty(Q)){……}}}14深度优先遍历函数定义……while(!QueueEmpty(Q)){DeQueue(Q,uw=FirstAdjVex(G,u);while(w!=0){if(G.Visited[w]==0)//尚未访问{G.Visited[w]=1;cout访问G.V[w]endl;EnQueue(Q,w);}w=NextAdjVex(G,u,w);}}15深度优先遍历函数定义intFirstAdjVex(structMGraphG,intu){inti;for(i=1;i=G.n;i++)if(G.E[u][i]==1)returni;return0;}intNextAdjVex(structMGraphG,intu,intw){inti;for(i=w+1;i=G.n;i++)if(G.E[u][i]==1)returni;return0;}16Main函数定义voidmain(){structMGraphG1;inti,j,k;cout请输入顶点个数:;cinG1.n;cout请输入边数：;cinG1.e;for(i=1;i=G1.n;i++){cout请输入第i顶点名称：;cinG1.V[i];}17Main函数定义……//初始化邻接矩阵for(i=1;i=G1.n;i++)for(j=1;j=G1.n;j++)G1.E[i][j]=0;//输入边的起点序号和终点序号for(k=1;k=G1.e;k++){cout请输入第k边的起点序号：;cini;cout请输入第k边的终点序号：;cinj;G1.E[i][j]=1;G1.E[j][i]=G1.E[i][j];}……18Main函数定义……cout图对应的邻接矩阵如下：endl;for(i=1;i=G1.n;i++){for(j=1;j=G1.n;j++)coutG1.E[i][j];coutendl;}cout开始遍历过程.........endl;intstarti;cout请输入遍历起点序号:(0表示结束);cinstarti;BFSTraverse(G1,starti);}19实验三、图的深度优先遍历实验名称：图的遍历实验目的：熟悉图的邻接表存储方式，掌握图的结构体定义，掌握图的深度优先遍历算法。实验内容：1，定义图的邻接表存储结构体2，定义图的输入函数3，定义图的遍历函数4，设计main函数，输入图的顶点个数，是否有向图，由用户输入图的邻接表和遍历起点序号，输出遍历顶点序号20实验四、排序算法的比较实验名称：排序算法的比较实验目的：熟悉记录集合结构定义，掌握冒泡排序算法、直接选择排序算法、快速排序算法，比较三种排序算法效率。实验内容：1，定义待排序数据集合结构体2，定义冒泡排序函数3，定义直接选择排序算法函数4，定义快速排序算法函数5，设计main函数，输入待排序数据，用户选择排序方法，输出排序结构及排序过程中的比较次数21程序运行结果22冒泡排序算法设计longbublesort(record*a,intn){intj,i,flag;longcount=0;for(i=1;i=n;i++){flag=1;for(j=1;j=n-i;j++){if(a[j+1].keya[j].key){flag=0;a[0]=a[j];a[j]=a[j+1];a[j+1]=a[0];}count++;}if(flag==1)break;}returncount;}23直接选择排序算法设计longselectsort(record*r,intn){inti,j,k;longcount=0;for(i=1;i=n-1;i++){k=i;for(j=i+1;j=n;j++){if(r[j].keyr[k].key)k=j;count++;}if(k!=i){r[0]=r[i];r[i]=r[k];r[k]=r[0];}}returncount;}24快速排序算法设计longquicksort(record*r,intlow,inthigh){longcount=0;inti=low;intj=high;r[0]=r[i];if(i=j)returncount;while(ij){while(ij&&r[j].key=r[0].key){j--;count++;}if(ij){r[i]=r[j];i++;}while(ij&&r[i].key=r[0].key){i++;count++;}if(ij){r[j]=r[i];j--;}}r[i]=r[0];………25快速排序算法设计longquicksort(record*r,intlow,inthigh){longcount=0;inti=low;intj=high;r[0]=r[i];if(i=j)returncount;while(ij){………}r[i]=r[0];count=count+quicksort(r,low,i-1);count=count+quicksort(r,i+1,high);returncount;}26Main函数设计voidmain(){recordr1[maxsize+1];intchoose;cout请输入maxsize个数据，建立待排序表endl;inti;for(i=1;i=maxsize;i++)cinr1[i].key;longcount=0;。。。。}27Main函数设计do{coutendl待排序数据是：;for(i=1;i=maxsize;i++)coutr1[i].key;coutendl;cout请选择排序方法:“1-冒泡,2-直接选择,3-快速,0-退出“endl;cinchoose;count=0;……}28Main函数设计do{……count=0;if(choose==1){count=bublesort(r2,maxsize);show(r2,maxsize,count);}elseif(choose==2){count=selectsort(r2,maxsize);show(r2,maxsize,count);}………}29Main函数设计do{……elseif(choose==3){count=quicksort(r2,1,maxsize);show(r2,maxsize,count);}elseif(choose==0)break;elsecout选择错误！请重新选择！endl;}while(choose!=0);30实验五、查找算法的比较实验名称：查找算法比较实验目的：熟悉查找的基本操作，掌握查找表的结构体定义，掌握顺序查找、折半查找算法实验内容：1，定义查找表结构体2，定义顺序查找函数3，定义折半查找函数4，设计main函数，实现由用户输入待查找数据，由用户选择查找方式，输出查找结果，及查找次数31程序运行结果32//结构体定义#definemaxsize10typedefintdatatype;typedefstructrecord{datatypekey;charotherinfo;}record;33//顺序查找intseqsearch(record*r,intn,datatypekey,int&count){inti=n;r[0].key=key;while(r[i].key!=key){i--;count++;}count++;returni;}34//二分查找intbinsearch(record*r,intn,datatypekey,int&count){intmid,low=1,high=n;while(low=high){mid=(low+high)/2;count++;if(r[mid].key==key)returnmid;elseif(r[mid].keykey)high=mid-1;elselow=mid+1;}return0;}35//main函数的设计recordr1[maxsize+1];intchoose;datatypekey;cout请输入maxsize个数据，建立查找表endl;inti;for(i=1;i=maxsize;i++)cinr1[i].key;36//main函数的设计intcount=0;do{count=0;coutendl待查找序数据是：;for(i=1;i=maxsize;i++)coutr1[i].key;coutendl;cout请选择排序方法:1-顺序查找,2-折半查找,0-退出endl;cinchoose;cout请输入查找数据;cinkey;。。。。。37//main函数的设计intcount=0;do{。。。。。cout请输入查找数据;cinkey;int