搜索
数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。实验教材：数据结构题集（C语言版）清华大学出版社2007年实验项目：实验一、栈和循环队列㈠、实验内容：1栈掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。2循环队列掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。㈡、实验代码1栈程序代码：#includestdio.h#includemalloc.h#defineStack_Size6#defineERROR0#defineOK1typedefintSElemType;typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*LinkStack;intCreatTwo(LinkStack&head,intn){inti;SNode*p;head=(LinkStack)malloc(sizeof(SNode));head-next=NULL;printf(请输入数据(数字):\n);for(i=n;i0;--i){p=(SNode*)malloc(sizeof(SNode));scanf(%d,&p-data);p-next=head-next;head-next=p;}return1;}intmenu_select(){intsn;for(;;){scanf(%d,&sn);if(sn1||sn6)printf(\n\t输入错误，请重新输入\n);elsebreak;}returnsn;}intPush(LinkStack&top,SElemTypee){SNode*q;q=(LinkStack)malloc(sizeof(SNode));if(!q){printf(溢出!\n);return(ERROR);}q-data=e;q-next=top-next;top-next=q;return(OK);}intPop(LinkStack&top,SElemType&e){SNode*q;if(!top-next){printf(error!\n);return(ERROR);}e=top-next-data;q=top-next;top-next=q-next;free(q);return(OK);}voidmain(){inte;LinkStacktop;printf(1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n);while(1){switch(menu_select()){case1:if(CreatTwo(top,Stack_Size))printf(Success!\n);break;case2:printf(Push:\n);scanf(%d,&e);if(Push(top,e))printf(Success!\n);break;case3:if(Pop(top,e))printf(Success!\n);printf(%d\n,e);break;case4:LinkStackp;printf(所有栈里的元素:\n);p=top;while(p-next){p=p-next;printf(%7d,p-data);}printf(\n);break;case5:return;}}}运行结果：2循环队列程序代码：#includestdlib.h#includestdio.h#defineOVERFLOW-1#defineOK1#defineERROR0#defineMAXSIZE100typedefstruct{int*elem;//队列存储空间intfront;intrear;}SqQueue;//判断选择是否正确intmenu_select(){intsn;for(;;){scanf(%d,&sn);if(sn1||sn6)printf(\n\t输入错误，请重新输入\n);elsebreak;}returnsn;}//参数(传出)SqQueue&Q,循环队列(空)intInitQueue(SqQueue&Q){Q.elem=(int*)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(inti=0;iMAXSIZE;i++)Q.elem[i]=-1;returnOK;}//返回Q的元素个数intQueueLength(SqQueueQ){return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//显示队列的元素voidDisplay(SqQueueQ){for(inti=0;i=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf(%d,Q.elem[i]);printf(\n);}//入队intEnQueue(SqQueue&Q,inte){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)returnERROR;Q.elem[Q.rear]=e;returnOK;}//出队intDeQueue(SqQueue&Q,int&e){if(Q.front==Q.rear)returnERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;returnOK;}voidmain(){SqQueueQ;InitQueue(Q);intelem,e;printf(请输入队列元素(以0结束):\n);scanf(%d,&elem);while(elem!=0){EnQueue(Q,elem);scanf(%d,&elem);}printf(队列为：\n);Display(Q);printf(1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n);while(1){switch(menu_select()){case1:printf(请输入队列元素(以0结束):\n);scanf(%d,&elem);while(elem!=0){EnQueue(Q,elem);scanf(%d,&elem);}printf(队列为：\n);Display(Q);fflush(stdin);break;case2:scanf(%d,&elem);EnQueue(Q,elem);printf(队列为：\n);Display(Q);fflush(stdin);break;case3:DeQueue(Q,elem);printf(队列为：\n);Display(Q);break;case4:printf(\n队列的所有元素:\n);Display(Q);break;case5:printf(%d\n,QueueLength(Q));break;case6:return;}}}运行结果：实验二、数组㈠、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。本程序数组的大小定义为3*3，可以通过修改“#defineM”来变动。本程序具有矩阵相加、矩阵A转置、矩阵B转置、矩阵相乘四个功能。㈡、实验代码：#includestdio.h#defineM3voidMatrixAdd(intm1[M][M],intm2[M][M],intresult[M][M])//两个矩阵m1和m2相加,结果放到result{inti,j;for(i=0;iM;i++){for(j=0;jM;j++)result[i][j]=m1[i][j]+m2[i][j];}}voidMatrixTrams(intm1[M][M],intresult[M][M])//矩阵转置{inti,j;for(i=0;iM;i++){for(j=0;jM;j++)result[i][j]=m1[j][i];}}voidMatrixMultiply(intm1[M][M],intm2[M][M],intresult[M][M]){inti,j;for(i=0;iM;i++){for(j=0;jM;j++){result[i][j]=0;for(intk=0;kM;k++)result[i][j]+=m1[i][k]*m2[k][j];}}}voidDisplay(intresult[M][M])//显示矩阵{inti,j;for(i=0;iM;i++){for(j=0;jM;j++)printf(%-5d,result[i][j]);printf(\n);}}voidmain(){intA[M][M],B[M][M];inti,j;printf(请输入第一个矩阵：\n);for(i=0;iM;i++)for(j=0;jM;j++)scanf(%d,&A[i][j]);printf(请输入第二个矩阵：\n);for(i=0;iM;i++)for(j=0;jM;j++)scanf(%d,&B[i][j]);intresult[M][M];/*printf(\n矩阵A:\n);Display(A);printf(\n矩阵B:\n);Display(B);*/printf(请选择：\n1.矩阵相加：\n2.矩阵A转置：\n3.矩阵B转置：\n4.矩阵相乘：\n5.退出。\n\n);while(1){intl;scanf(%d,&l);switch(l){case1:printf(矩阵相加的运算结果：\n);MatrixAdd(A,B,result);Display(result);printf(\n);break;case2:printf(矩阵A转置的运算结果：\n);MatrixTrams(A,result);Display(result);printf(\n);break;case3:printf(矩阵B转置的运算结果：\n);MatrixTrams(B,result);Display(result);printf(\n);break;case4:printf(矩阵相乘的运算结果：\n);MatrixMultiply(A,B,result);Display(result);printf(\n);break;case5:printf(退出。\n);return;default:printf(输入错误！);printf(\n);}}}实验结果：实验三、查找㈠、实验内容掌握各种查找（顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。本实验采用二分查找。二分查找又称折半查找，它是一种效率较高的查找方法。折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。本程序具有找出数据位置和显示查找次数两个功能。㈡、实验代码：#includestdio.h#defineMAX100voidmain(){intr[MAX],i,k,low,high,mid,m,n;printf(\n\n建立递增有序的查找顺序表（以-1结束）：\n);for(i=0;iMAX;i++){scanf(%d,&r[i]);