数据结构报告

【实验一内容及要求】问题描述：编号是1,2,…,n（n>0）的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。扩展：设置一个比较人性化的操作环境。【实验二内容及要求】问题描述：利用栈的基本操作实现一个算术表达式的求值的程序。基本要求：（1） 定义栈的顺序存取结构。（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。（3） 定义一个函数用来计算表达式结果，并且可以显示表达式的后缀表示。（4） 设计一个测试主函数进行测试。扩展：能对“+”“—”“*”“/”“（）”等进行操作。进行操作的数可以是一个比较大的数。【实验三内容及要求】问题描述：采用顺序存储结构，完成串的联接和子串定位操作。基本要求：（1） 定义串的顺序存取结构。（2） 分别定义串的联接和子串定位的基本操作。（3） 设计一个测试主函数进行测试。扩展;能实验求子串，判断字符串大小，求字符串长度等功能。【实验四内容及要求】问题描述：采用二叉链表作为存储结构，完成图1的二叉树的建立和遍历操作。基本要求：（1） 基于先序遍历的构造算法。输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。（2） 利用中序顺序遍历所建的二叉树，将遍历结果打印输出。扩展：能实现二叉树判空，求深度，求二叉树结点数，清空二叉树等操作。能设置一个选择操作的界面，使操作环境更人性化。【实验五内容及要求】问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1） 能随机生成30个值为0到100的数。（2） 用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值扩展：能对进行操作的数是随机产生还是键盘输入进行选择，能选择每次是按那种方式排序。程序设计的基本思想，原理和算法描述：(包括程序的结构，数据结构，输入/输出设计，符号名说明等)【实验一(约瑟夫环)】通过查找一个数，从而得到查找下一个数的方法，通过循环链表可以实现上面的要求，即将第一个数放在表头，下一个数的查找方法放在表尾，从而实现循环查找。【实验二(表达式求值)】输入表达式时，会将原来的内容清空，并且必须按照中缀表示输入。如果你细看一下中缀表达式，你就会发现，除了括号，表达式的结构是“操作数”、“操作符”、“操作数”、……“操作符(=)”，为了统一这个规律，同时也为了使输入函数简单一点，规定括号必须这样输入“0(”、“)0”；这样一来，“0”就不能作为操作数出现在表达式中了。【实验三(串的基本操作)】串是数据类型为字符的特殊的线性表，在串的基本操作中，通常以“串的整体”作为操作对象。所以串的基本操作和线性表有很大差别。利用数组存储实现串的基本操作：即赋值、求长度、连接、求子串、子串定位、替换、退出等操作。请构造以下系统：它是一个命令解释程序，循环往复地处理用户输入地每一条命令，直到输入终止程序的命令为此。命令定义如下：赋值。格式为：A串标识用串标识所表示的串的值建立新串，并显示新串的值。求长度。格式为：L串标识回车求串的长度并显示。求子串。格式为：S串标识数1数2如果参数合法，则显示子串的串值。子串定位。格式为：I串标识1串标识2显示第二个串在第一个串中首次出现时的起始位置。替换。格式为：R串标识1串标识2串标识3将第一个串中所有出现的第二个串用第三个串替换，显示串标识1、串标识串标识3和替换后的串。退出。格式为：Q结束程序的运行。【实验四(树的基本操作)】(1)INITIATE(BT)初始化操作。置BT为空树。ROOT(BT)\ROOT(x)求根函数。求二叉树BT的根结点或求结点x所在二叉树的根结点。若BT是空树或x不在任何二叉树上，则函数值为“空”。PARENT(BT,x)求双亲函数。求二叉树BT中结点x的双亲结点。若结点x是二叉树BT的根结点或二叉树BT中无x结点，则函数值为“空”。LCHILD(BT,x)和RCHILD(BT,x)求孩子结点函数。分别求二叉树BT中结点x的左孩子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。LSIBLING(BT,x)和RSIBING(BT,x)求兄弟函数。分别求二叉树BT中结点x的左兄弟和右兄弟结点。若结点x是根结点或不在BT中或是其双亲的左/右子树根,则函树值为“空”。CRT_BT(x,LBT,RBT)建树操作。生成一棵以结点x为根，二叉树LBT和RBT分别为左，右子树的二叉树。INS_LCHILD(BT,y,x)和INS_RCHILD(BT,x)插入子树操作。将以结点x为根且右子树为空的二叉树分别置为二叉树BT中结点y的左子树和右子树。若结点y有左子树/右子树，则插入后是结点x的右子树。DEL_LCHILD(BT,x)和DEL-RCHILD(BT,x)删除子树操作。分别删除二叉树BT中以结点x为根的左子树或右子树。若x无左子树或右子树，则空操作。TRAVERSE(BT)遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。CLEAR(BT)清除结构操作。将二叉树BT置为空树。【实验五(排序)】将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。假设要排序的数组是A[1]……A[N]，首先任意选取一个数据(通常选用第一个数据)作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：、设置两个变量I、J,排序开始的时候I：=1,J：=N；以第一个数组元素作为关键数据，赋值给X,即X：=A[1]；、从J开始向前搜索，即由后开始向前搜索J：=J-1)，找到第一个小于X的值，两者交换；、从I开始向后搜索，即由前开始向后搜索(I：=1+1)，找到第一个大于X的值，两者交换；、重复第3、4步，直到I=J；源程序：【实验一(约瑟夫环)】#include"stdio.h"#include"stdlib.h"typedefstructlnode//定义结构体{intnum,code;//编号和密码structlnode*next;}lnode;voidmain(){inti,j,key,n;lnode*p,*s,*head;//结构体指针head=(lnode*)malloc(sizeof(lnode));//为头结点分配空间p=head;printf("pleaseinputthewholenumberofpeople:");scanf("%d",&n);for(i=1;i<=n;i++)//循环{printf("%d",i);//输出n个人的编号printf("Password:");scanf("%d",&key);//n个人的密码s=p;p=(lnode*)malloc(sizeof(lnode));//创建新的结点s->next=p;p->num=i;p->code=key;}p->next=head->next;p=head;head=head->next;//将p移到头结点free(p);printf("\nIputm:");scanf("%d",&key);do{j=1;//j记数p=head;while(j<key)//将j的值加到与m相等为止{s=p;p=p->next;j++;}i=p->num;//将p指向的编号赋给ikey=p->code;//将p指向的密码赋给keyprintf("Out:");printf("Number%d\n",i);s->next=p->next;head二p->next;//重新定义head,下次循环的开始结点free(p);n--;//每循环一次人是减1}while(n>0);}【实验二(表达式求值)】#include<stdio.h>#include<conio.h>#include<math.h>#include<stdlib.h>typedefstruct{charfun;intgrade;}Functor;//定义算符栈结构体FunctorFUNCTOR[20];floatNUM[20];//定义算符栈和对象栈charch[100];intsub=0;//存放输入流的字符串floatChar_To_Num(){//将表示数据的字符串转化成数据intflag=0,i=-1;floatvalue=0.0;while((ch[sub]>=48&&ch[sub]<=57)||ch[sub]=='.'){if(ch[sub]=='.')flag=1;else{if(flag==0)value=value*10+ch[sub]-48;else{value=value+(ch[sub]-48)*pow(10,i);i--;}}sub++;}returnvalue;}intIn_Grade(charc){//算符在栈内时的级别intg;switch(c){case'八':g=3;break;case'*':case'/':case'%':g=2;break;case'+':case'-':g=1;break;case'(':g=0;break;case')':g=-1;break;}returng;}intOut_Grade(){//算符在栈外时的级别intg;switch(ch[sub]){case'A':g=4;break;case'*':case'/':case'%':g=2;break;case'+':case'-':g=1;break;case'(':g=4;break;case')':g=-1;break;}returng;voidError(){printf("输入的表达式有误！\n");printf("\n按任意键退出");getch();exit(1);}voidCalculate(inti,intj){if(i>=2){//判断对象栈中元素个数switch(FUNCTOR[j-1].fun){case'A':NUM[i-2]=pow(NUM[i-2],NUM[i-l]);break;case'*':NUM[i-2]=NUM[i-2]*NUM[i-1];break;case'/':NUM[i-2]=NUM[i-2]/NUM[i-1];break;case'%':NUM[i-2]=int(NUM[i-2])%int(NUM[i-1]);break;case'+':NUM[i-2]=NUM[i-2]+NUM[i-1];break;case'-':NUM[i-2]=NUM[i-2]-NUM[i-1];break;}NUM[i-1]=0;FUNCTOR[j-1].fun=0;}elseError();//若对象栈若只剩一个数据，则输入的表达式有误}floatChar_Transform(){inti=0,j=0,grade,flag=0;while(ch[sub]!='='||j!=0){if(ch[sub]=='='){//输入的字符是否取完Calculate(i,j);i--;j--;}else{if(ch[sub]>=48&&ch[sub]<=57){//判断是否为运算对象NUM[i++]=Char_To_Num();if(flag){NUM[i-1]=-NUM[i-1];FUNCTOR[j-1].fun=0;j--;flag=0;}}else{if(ch[sub]=='%'||(ch[sub]>=40&&ch[sub]<=43)||ch[sub]=='-'||ch[sub]==s'||ch[sub]=='/'){//判断是否为算符if(FUNCTOR[j-1].fun=='-'&&FUNCTOR[j-2].fun=='('&&ch[sub]==')'){//判断是否为负数NUM[i-1]=-NUM[i-1];FUNCTOR[j-1].fun=0;FUNCTOR[j-2].fun=0;j=j-2;sub++;}else{if(FUNCTOR[j-1].fun=='('&&ch[sub]==')'){//括号内表达式计算完后则将左括号从栈中去除FUNCTOR[j-1].fun=0;j--;sub++;}else{grade=Out_Grade();//栈外算符的级别if(j==0||grade>FUNCTOR[j-1].grade){//第一个或级别比栈内算符高的进栈FUNCTOR[j].fun=ch[sub];FUNCTOR[j].grade=In_Grade(ch[sub]);if(j==0&&FUNCTOR[j].fun=='-')flag=1;j++;sub++;}

else{Calculate(i,j);i--;j--;}}}}elseError();//表达式中有非算术字符，则表达式有误}}}returnNUM[i-1];}voidmain(){floatresult;printf(''****************************************printf(''****************************************printf（"请输入要求解的表达式，并以等号“=”结束:\n"）;printf(''****************************************printf(''****************************************gets(ch);result=Char_Transform();printf("%s%.2f\n",ch,result);printf("\n按任意键退出");getch();}【实验三(串的基本操作)】#include<malloc.h>#include<string.h>#include<stdlib.h>#include"stdio.h"#include"conio.h"#defineMAXSTRLEN256typedefunsignedcharSHtring[MAXSTRLEN+1];/*求子串*/intSubstring(SHtringSub,SHtringS,intpos,intlen)/*在主串S中求出第pos个字符后的一个长度为len的字串，用sub返回*/{inti,j,k,m,n;m=strlen(S);if(pos<1||pos>m||len<0||len>m-pos+1)/*判断输入的要求的字串的位置是否正确*/return0;j=0;for(i=0;i<=len-1;i++){Sub[j]=S[pos+i];j++;}return1;}Concat(SHtringT,SHtringSl,SHtringS2) /*把串SI与S2连接在一起，用串T返回*/{inti,j,m,n;m=strlen(S1);n=strlen(S2);if(m+n<=MAXSTRLEN)/*判断是否T能装的下这两个串连接后的结果*/{j=1;for(i=l;iv=m;i++)/*先把si连接进去*/{T[j]=S1[i];j++;}for(i=1;i<=n;i++)/*把s2连接在S1的后面*/{T[j]=S2[i];j++;}T[0]=j;}else{j=i;for(i=1;i<=n;i++)/*当T的长度不够时，s2被截掉一些*/{T[j]=Si[i];j++;}for(i=i;i<=MAXSTRLEN-n;i++){T[j]=S2[i];j++;}T[0]=j;printf("lianjiehoudezichuanshi:\n");/*显示连接后的结果*/printf("%s\n",S1);getchar();}}intIndex(SHtringS,SHtringT,intpos)/*字串定位操作，返回T在主串S中第POS个字符后的位置*/{inti,j,k,m,q,n;SHtringSub;q=0;if(pos>0) /*判断所指定的位置是否正确*/{n=strlen(S);m=strlen(T);i=pos;}while(i<=n-m+1){Substring(Sub,S,i,m);/*通过对主串中指定位置后的字符进行求子串，判断字串与所给的字串是否相等*/for(k=1;k<=m;k++){if(Sub[k]!=T[k])/*不行同时继续进行求子串*/k=m+1;}if(k==m)/*相等时返回自串在主串中的位置*/{q=i;break;}printf("%s\n",Sub);getchar();++i;}returnq;strcompare(SHtringS,SHtringT)/*字符串比较，判断两个字符串是否相等,大于还是小于*/{inti,m,n,k;m=strlen(S);n=strlen(T);for(i=0;i<m&&i<n;++i)if(S[i]!=T[i])k=S[i]-T[i];elsek=m-n;if(k>0)printf("S>T\n");if(k<0)printf("S<T\n");if(k=0)printf("S=T");getchar();}/*求字符串的长度*/strlength(SHtringS1,SHtringS2){inti,j;i=strlen(S1);j=strlen(S2);printf("zifuchuanyichangdu=%d\nzifuchuanerchangdu=%d",i,j);getchar();}/*实现以上功能的主函数*/main(){inti,j,k,z;SHtringS1,S2,T,Y;j=0;k=0;z=0;printf("shurudiyigezifuchuan\n");scanf("%s",S1);

printf("shurudiergezifu\n");scanf("%s",S2);j=Index(S1,S2,1);printf("\n%d",j);strcat(S1,S2);getchar();}实验四（树的基本操作）】#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BiTNode;typedefBiTNode*BiTree;intCreateBiTree(BiTree*T){charc;scanf("%c",&c);if(c=='')/*判断最初输入的是否是空格键，如果是则建立一棵空树*/*T=0;else{/*//生成一个新/*//生成左/*/生成右*T=/*//生成一个新/*//生成左/*/生成右(*T)->data=c;CreateBiTree(&(*T)->lchild);子树*/CreateBiTree(&(*T)->rchild);子树*/}}/*前序遍历*/voidPreorder(BiTNode*T){if(T){printf("%c",T->data);/*先遍历根结点*/Preorder(T->lchild); /*遍历左子树*/Preorder(T->rchild); /*遍历右子树*/}}/*中序遍历*/voidInorder(BiTNode*T){if(T){Inorder(T->lchild);/*先遍历左树*/printf(" %c",T->data);/*遍历根结点*/Inorder(T->rchild);/*最后遍历右子树*/}}voidmain(){BiTreeT=NULL;charj;intflag=1;/*/ 程序解说 */printf("qingshuruxianxubianlideerchashu\n");if(!CreateBiTree(&T))/*/初始化树*/gotoback;back:while(flag)/*用switch语句实现遍历操作的自由选择*/{printf("\npleaseshuru1,2,3:\n");printf("1.xianxu,2.zhongxu,3.tuichu\n");getchar();scanf("%c",&j);switch(j){case'1':if(T){printf("xianxubianlijieguo\n:");Preorder(T);printf("\n");}elseprintf("NULL!\n");break;case'2':if(T){printf("zhongxubianli\n:");Inorder(T);printf("\n");}elseprintf("NULL!\n");break;default:flag=0;printf("Over!pressanykeytoquit\n");/*程序运行结束提示语}}}【实验五(排序)】#include<stdio.h>#include<time.h>#defineMAXSIZE2000typedefstruct{intkey[MAXSIZE];intlength;}list;longintcompCount;longintshiftCount;voidmenu(int*m)/*retunm*/{inti;charmenu[6][15]={"1CREATE","2IMPORT","3SORT","4SHOWRESULT","5SAVERESULT","6EXIT"};clrscr();printf("SORTCOMPARESYSTEM\n");for(i=0;i<6;i++)printf("%s\n",menu[i]);printf("\nPleaseSelect(1-6):\n");scanf("%d",m);}voidmenusort(int*m)/*retunm*/{inti;charmenusort[5][15]={"1SHELLSORT","2QUICKSORT","3HEAPSORT","4MERGESORT","5ALLSORT"};clrscr();printf("SORT\n");for(i=0;i<5;i++)printf("%s\n",menusort[i]);printf("\nPleaseSelect(1-5):\n");scanf("%d",m);}voidmenushow(int*m)/*retunm*/{inti;charmenushow[4][20]={"1SHELLSORTRESULT","2QUICKSORTRESULT","3HEAPSORTRESULT","4MERGESORTRESULT"};clrscr();printf("SHOWSORTRESULT\n");for(i=0;i<4;i++)printf("%s\n",menushow[i]);printf("\nPleaseSelect(1-4):\n");scanf("%d",m);}voidmenusave(int*m){inti;charmenusave[4][20]={"1SHELLSORTRESULT","2QUICKSORTRESULT","3HEAPSORTRESULT","4MERGESORTRESULT"};clrscr();printf("SAVE:\n");for(i=0;i<4;i++)printf("%s\n",menusave[i]);printf("\nPleaseSelect(1-4):\n");scanf("%d",m);}voidcreate(list*L){inti;printf("HOWMANYDATA?\n");scanf("%d",&((*L).length));for(i=1;i<=(*L).length;i++){printf("\nPLEASEINPUTTHE%dthDATA:\n",i);scanf("%d",&(*L).key[i]);}printf("\nCREATECOMPLETE!\n");}intlistopen(list*L,char*filename){intk=1;FILE*data;data=NULL;data=fopen(filename,"rb");while(!feof(data)){fscanf(data,"%d",&(*L).key[k]);k++;}(*L).length=k-1;}voidimport(list*L)/*fixL*/charfilename[255];inti;printf("\nPLEASEINPUTTHEFILEPATHANDNAME:\n");scanf("%s",filename);clrscr();listopen(L,filename);for(i=1;i<(*L).length;i++)printf("%d",(*L).key[i]);printf("\nPRESSANYKEYRETURNTOMAINMENU...\n");getch();}voidsave(listL){FILE*data;charfilename[255];intr;printf("\nPLEASEINPUTTHEFILEPATHANDNAME:\n");scanf("%s",filename);data=fopen(filename,"wb");for(r=1;r<=L.length;r++)fprintf(data,"%d\n",L.key[r]);fclose(data);printf("SAVEOK!\nPRESSANYKEYTORETURNTHEMAINMENU...");getch();}listshellsort(listL)/*retunL_SHELL*/{inti,j,gap,x,n;compCount=shiftCount=0;n=L.length;gap=n/2;while(gap>0){compCount++;for(i=gap+1;i<=n;i++){compCount++;j=i-gap;while(j>0){compCount++;if(L.key[j]>L.key[j+gap]){compCount++;x=L.key[j];shiftCount++;L.key[j]=L.key[j+gap];shiftCount++;L.key[j+gap]=x;shiftCount++;j=j-gap;}elsej=0;}}gap=gap/2;}returnL;}voidshell(listL,list*LS,float*timeshell)/*returnLS,timeshell.MUSTaddan"getch"!!*/{clock_tstart,end;start=clock();(*LS)=shellsort(L);end=clock();*timeshell=(end-start)/CLK_TCK;printf("\nSHELLSORTCOSTTIME:%fSECONDS.",*timeshell);printf("Compare%dtimes.Shfit%dtimes.\n",compCount,shiftCount);}intPartition(list*pL,intlow,inthigh){intpivotkey;pL->key[0]=pL->key[low];shiftCount++;pivotkey=pL->key[low];shiftCount++;while(low<high){compCount++;while(low<high&&pivotkey<=(pL->key[high])){compCount++;compCount++;--high;}pL->key[low]=pL->key[high];shiftCount++;while(low<high&&(pL->key[low])<=pivotkey){compCount++;compCount++;++low;}pL->key[high]=pL->key[low];shiftCount++;}pL->key[low]=pL->key[0];shiftCount++;returnlow;}/*Partition*/voidQSort(list*pL,intlow,inthigh){intpivotloc;if(low<high){compCount++;pivotloc=Partition(pL,low,high);QSort(pL,low,pivotloc-1);QSort(pL,pivotloc+1,high);}}/*QSort*/listQuickSort(listpL){compCount=shiftCount=0;QSort(&pL,1,pL.length);returnpL;}/*QuickSort*/voidquick(listL,list*LQ,float*timequick)/*MUSTaddan"getch"!!*/{clock_tstart,end;start=clock();(*LQ)=QuickSort(L);end=clock();*timequick=(end-start)/CLK_TCK;printf("\nQUICKSORTCOSTTIME:%fSECONDS.",*timequick);printf("Compare%dtimes.Shfit%dtimes.\n",compCount,shiftCount);}voidsift(listL,intl,intm){inti,j,x;i=l;j=2*i;x=L.key[i];while(j<=m){compCount++;if(j<m&&L.key[j]<L.key[j+1]){j++;compCount++;compCount++;}if(x<L.key[j]){compCount++;L.key[i]=L.key[j];shiftCount++;i=j;shiftCount++;j=2*i;}elsej=m+1;}L.key[i]=x;shiftCount++;}listheapsort(listL){inti,w;compCount=shiftCount=0;for(i=L.length/2;i>=1;i--){sift(L,i,L.length);compCount++;}for(i=L.length;i>=2;i--){compCount++;w=L.key[i];shiftCount++;L.key[i]=L.key[1];shiftCount++;L.key[1]=w;shiftCount++;sift(L,i-1,1);}returnL;}voidheap(listL,list*LH,float*timeheap){clock_tstart,end;start=clock();(*LH)=heapsort(L);end=clock();*timeheap=(end-start)/CLK_TCK;printf("\nHEAPSORTCOSTTIME:%fSECONDS.",*timeheap);printf("Compare%dtimes.Shfit%dtimes.\n",compCount,shiftCount);}voidMerge(intsource[],intresult[],intsize,intn){intlb1,lb2,ub1,ub2,p,i,j;lb1=0;p=0;while((lb1+size)<n){compCount++;lb2=lb1+size;ub1=lb2-1;if((lb2+size-1)>n){ub2=n-1;compCount++;shiftCount++;}else{ub2=lb2+size-1;compCount++;shiftCount++;}i=lb1;j=lb2;while((i<=ub1)&&(j<=ub2)){compCount++;compCount++;if(source[i]<=source[j]){result[p++]=source[i++];shiftCount++;compCount++;}else{result[p++]=source[j++];shiftCount++;compCount++;}}while(i<=ub1){result[p++]=source[i++];shiftCount++;compCount++;}while(j<=ub2){result[p++]=source[j++];shiftCount++;compCount++;}lb1=ub2+1;}i=lb1;while(p<n){compCount++;result[p++]=source[i++];shiftCount++;}}voidMergesort(list*L){intn=(*L).length;ints=1;int*temp=(int*)malloc(n*sizeof(int));compCount=shiftCount=0;if(temp==NULL){printf("outofmemory");return;}while(s<n){compCount++;Merge((*L).key,temp,s,n);s*=2;Merge(temp,(*L).key,s,n);}compCount++;}voiddomerge(listL,list*LM,float*timemerge)/*MUSTaddan"getch"!!*/{clock_tstart,end;start=clock();Mergesort(&L);end=clock();(*LM)=L;*timemerge=(end-start)/CLK_TCK;printf("\nMERGESORTCOSTTIME:%fSECONDS.",*timemerge);printf("Compare%dtimes.Shfit%dtimes.\n",compCount,shiftCount);}main(){listL,LS,LQ,LH,LM;intLOCK3=0,LOCK4=0,LOCK5=0,RUN=1,LOCK41=0,LOCK42=0,LOCK43=0,LOCK44=0;intcomd,r;floattimeshell,timequick,timeheap,timemerge;while(RUN==1){start:menu(&comd);switch(comd){case1:create(&L);LOCK3=1;break;case2:import(&L);LOCK3=1;gotostart;

case3:if(LOCK3==0)gotostart;menusort(&comd);LOCK4=1;LOCK5=1;switch(comd){case1:LOCK41=1;shell(L,&LS,×hell);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case2:LOCK42=1;quick(L,&LQ,&timequick);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case3:LOCK43=1;heap(L,&LH,&timeheap);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case4:LOCK44=1;domerge(L,&LM,&timemerge);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case5:LOCK41=1;LOCK42=1;LOCK43=1;LOCK44=1;shell(L,&LS,×hell);quick(L,&LQ,&timequick);heap(L,&LH,&timeheap);domerge(L,&LM,&timemerge);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case6:gotostart;}case4:if(LOCK4==0)gotostart;menushow(&comd);switch(comd){case1:if(LOCK41==0)gotostart;for(r=1;r<=LS.length;r++)printf("%d",LS.key[r]);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case2:if(LOCK42==0)gotostart;for(r=1;r<=LQ.length;r++)printf("%d",LQ.key[r]);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case3:if(LOCK43==0)gotostart;for(r=1;r<=LH.length;r++)printf("%d",LH.key[r]);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case4:if(LOCK44==0)gotostart;for(r=1;r<=LM.length;r++)printf("%d",LM.key[r]);printf("\nPRESSANYKEYTORETURNMAINMENU...\n");getch();gotostart;case6:gotostart;}case5:if(LOCK5==0)gotostart;menusave(&comd);switch(comd){case1:if(LOCK41==0)gotostart;save(LS);break;case2:if(LOCK42==0)gotostart;save(LQ);break;case3:if(LOCK43==0)gotostart;save(LH);break;case4:if(LOCK44==0)gotostart;save(LM);break;case6:break;}break;case6:exit（0）;}}}七、运行结果：【实验一（约瑟夫环）】pleaseinputthewholenumberofpeple:71Password:32Password:13Password:74Password:25Password:46Password:87Password:4Iputm:20Out:Number6Out:Number1Out:Number4Out:Number7Out:Number2Out:Number3Out:Number5Pressanykeytocontinue【实验二（表达式求值）】inputaexpressionandendupwitha'='12+3-9*2+18/3=therensultis3【实验三（串的基本操作）】shurudiyigezifuchuan123456shuruyigezifu234zifuchuanyichangdu=6zifuchuanyichangdu=3lianjiehoudezifuchuanwei:123456234实验四（树的基本操作）】BiTraversepre:abdecfBiTraverseIn:dbeacfBiTraversepost:debfca【实验五（排序）】suijichanshengshu?YorNNqingshuruwugeshu:2356859575qingxuanze:1.charu2kuaisu3maopao1charu:2356758595kuaisu:2356758595maopao:2356758595七、调试和运行程序过程中产生的问题及采取的措施：【实验一】这个程序比较简单，了解循环链表的结构以及其功能，我们就可以完成，但也要在编程的时候注意点，本人就因为掉了课括号使得我检查了半天，搞的我头晕晕的。【实验二】本实验是利用栈实现表达式的求值，在设计算法的过程中我遇到了许多的问题，首先是如何解决算数运算中优先级的设置，其次是如何构造合理的栈的结构用来辅助我进行求解表达式的值，有了这些还不行，我还得自习分析一个表达式的求解过程，合理地安排每个中间计算结果的存储。带着这些问题，我把书上的栈的内容认真地看来好几遍，终于有了一个大概框架，根据书上的提示以及书上列出的优先表，我把这个表格变成七行七列的数组，行号是新输入的运算符，列号是原来输入的运算符中最后一个，这样根据对应的行号与列好就能在数组中找到一个符号，这个符号就是比较之后的运算优先级，然后根据优先级判断是进行求值还是继续把这个运算符入栈，如果是大于号或者等于号就从数字栈中弹出数进行运算，并把计算结果入栈，如此反复进行判断，运算结束。但是按照这个思路我写出了程序，运行的时候结果总是不对，而且还不知道怎样结束计算，后来想出了一个办法，就是在字符栈中首先入栈一个符号，如果出栈的是这个符号则代表运算结束。这样终于把问题给解决了，心里特别舒服。这个程序的运行结果只有在输入的数据在100以内时才能得出正确的结果，而且不能求出负数，也就是说如果结果是小于零的数就会出现乱码，但是相对同学的程序有很大的进步，因为很多同学的程序只能求10以内的数的运算。程序能够进行一些错误的判断，像除法出错和栈空时的操作判错，但是不能判断很长表达式的出错报告，不管结果如何，都会有答案，显然答案有时是不对的。【实验三（串的基本操作）】其实程序的一部分程序已经在数据结构书上已给出，只需要将书上的类C语言改成C语言就可以了。改的过程中需要注意书上的是类C语言的程序，是