1 / 20 数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。实验教材：数据结构题集 及基本操作 , 如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。本程序采用的是链栈结构，具有初始化一个栈、PUSH 、POP 、显示所有栈里的元素四个功能。 循环队列掌握队列的特点 ( 先进先出 FIFO及基本操作 , 如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。、实验代码 栈程序代码：#include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType。typedef struct SNode SElemType data。struct SNode *next。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 20 页2 / 20 SNode,*LinkStack 。int CreatTwo(LinkStack &head,int n int i。SNode *p。head=(LinkStackmalloc(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 。 return 1。 int menu_select( int sn。for( 。 scanf(%d,&sn 。if(sn6 printf(nt输入错误，请重新输入 n 。else break。 return sn。 int Push(LinkStack &top,SElemType e SNode *q。q=(LinkStackmalloc(sizeof(SNode。if(!q printf(溢出!n 。return(ERROR。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 20 页3 / 20 q-data=e 。q-next=top-next。top-next=q 。return(OK 。 int Pop(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 。 void main( int e。LinkStack top。printf(1.初始化一个栈。 n2.PUSH。n3.POP。n4. 显示所有栈里的元素。 n5. 结束。 n 。while(1 switch(menu_select( case 1: if(CreatTwo(top,Stack_Sizeprintf(Success!n。break。 case 2: printf(Push:n。scanf(%d,&e 。if(Push(top,eprintf(Success!n。break。case 3: if(Pop(top,eprintf(Success!n。printf(%dn,e。break。case 4: LinkStack p 。printf(所有栈里的元素 :n 。p=top。while(p-next 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 20 页4 / 20 p=p-next 。printf(%7d,p-data。 printf(n。break。case 5: return 。 运行结果： 循环队列程序代码：#include #include #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef struct int *elem。/ 队列存储空间int front。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 20 页5 / 20 int rear。SqQueue 。/ 判断选择是否正确int menu_select( int sn。for( 。 scanf(%d,&sn 。if(sn6 printf(nt输入错误，请重新输入 n 。else break。 return sn。 / 参数( 传出SqQueue &Q, 循环队列 ( 空 int InitQueue(SqQueue &Q Q.elem=(int *malloc(MAXSIZE*sizeof(int。if(!Q.elemexit(OVERFLOW 。Q.front=Q.rear=-1。for(int i=0。i Q.elemi=-1。return OK 。 / 返回 Q的元素个数int QueueLength(SqQueue Q return (Q.rear-Q.front+MAXSIZE%MAXSIZE 。 / 显示队列的元素void Display(SqQueue Q for(int i=0。i。i+ if(Q.elemi!=-1printf(%d ,Q.elemi。printf(n。 / 入队精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 20 页6 / 20 int EnQueue(SqQueue &Q,int e Q.rear=(Q.rear+1%MAXSIZE。if(Q.rear=Q.frontreturn ERROR。Q.elemQ.rear=e。return OK 。 / 出队int DeQueue(SqQueue &Q,int &e if(Q.front=Q.rearreturn ERROR。e=Q.elemQ.front+1。Q.elemQ.front+1=-1。Q.front=(Q.front+1%MAXSIZE 。return OK 。 void main( SqQueue Q 。InitQueue(Q 。int elem,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( case 1: printf(请输入队列元素 ( 以 0 结束:n 。scanf(%d,&elem 。 while(elem!=0 EnQueue(Q,elem。scanf(%d,&elem 。 printf(队列为： n 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 20 页7 / 20 Display(Q 。fflush(stdin。break。 case 2: scanf(%d,&elem 。EnQueue(Q,elem 。printf(队列为： n 。Display(Q 。fflush(stdin。break。case 3: DeQueue(Q,elem 。printf(队列为： n 。Display(Q 。break。case 4: printf(n队列的所有元素 :n 。Display(Q 。break。case 5: printf(%dn,QueueLength(Q。break。case 6: return 。 运行结果：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 20 页8 / 20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 20 页9 / 20 实验二、数组、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。本程序数组的大小定义为3*3，可以通过修改“ #define M ”来变动。本程序具有矩阵相加、矩阵A转置、矩阵 B转置、矩阵相乘四个功能。、实验代码：#include #define M 3 void MatrixAdd(int m1MM,int m2MM,int resultMM/两个矩阵 m1和 m2相加, 结果放到 result int i,j。for (i=0。i for(j=0。j resultij=m1ij+m2ij。 void MatrixTrams(int m1MM,int resultMM/矩阵转置 int i,j。for (i=0。i for (j=0。j resultij=m1ji。 void MatrixMultiply(int m1MM,int m2MM,int resultMM int i,j。for (i=0。i for (j=0。j resultij=0。for (int k=0。k 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 20 页10 / 20 resultij+=m1ik*m2kj。 void Display(int resultMM/显示矩阵 int i,j。for (i=0。i for(j=0。j printf(%-5d,resultij。printf(n。 void main( int AMM,BMM。int i,j。printf(请输入第一个矩阵： n 。for(i=0。i for(j=0。j scanf(%d,&Aij。printf(请输入第二个矩阵： n 。for(i=0。i for(j=0。j scanf(%d,&Bij。int resultMM。/*printf(n 矩阵 A:n 。Display(A 。printf(n 矩阵 B:n 。Display(B 。*/ printf(请选择： n1. 矩阵相加： n2. 矩阵 A转置： n3.矩阵 B转置： n4. 矩阵相乘： n5. 退出。 nn 。while (1 int l。scanf(%d,&l。switch(l case 1: printf(矩阵相加的运算结果： n 。MatrixAdd(A,B,result。Display(result。printf(n。break。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 20 页11 / 20 case 2: printf(矩阵 A转置的运算结果： n 。MatrixTrams(A,result。Display(result。printf(n。break。case 3: printf(矩阵 B转置的运算结果： n 。MatrixTrams(B,result。Display(result。printf(n。break。case 4: printf(矩阵相乘的运算结果： n 。MatrixMultiply(A,B,result。Display(result。printf(n。break。case 5: printf(退出。 n 。return 。default: printf(输入错误！ 。printf(n。 实验结果：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 20 页12 / 20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 20 页13 / 20 实验三、查找、实验内容掌握各种查找 顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。本实验采用二分查找。二分查找又称折半查找，它是一种效率较高的查找方法。折半查找法的优点是比较次数少，查找速度快，平均性能好。其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。本程序具有找出数据位置和显示查找次数两个功能。、实验代码：#include #define MAX 100 void main( int rMAX,i,k,low,high,mid,m,n。printf(nn 建立递增有序的查找顺序表 。for(i=0。i scanf(%d,&ri。if(ri=-1 n=i 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 20 页14 / 20 break。 printf(n 请输入要查找的数据： n 。scanf(%d,&k 。low=0。high=n-1 。m=0 。while(low mid=(low+high/2 。m+ 。if(rmidk high=mid-1 。else if(rmid low=mid+1。else break。 if(lowhigh printf(没有找到 n 。printf(共进行 %d次比较。 n,m 。if(rmid mid+。printf(可将这个数插入到第 %d个数的后面。 n,mid 。 else printf(n 要找的数据 =%d在第%d个数的位置上。n,k,mid+1。 printf(nn 共进行了 %d次比较。 n,m 。 实验结果：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 20 页15 / 20 实验四、树、实验内容：进一步掌握树的结构及非线性特点，递归特点和动态性；进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。本程序将第一个元素作为树根，其余元素若小于树根则为左子树，若大于树根则为右子树。本程序具有求左子树、求右子树、求深度、先序遍历、中序遍历递归算法）、中序遍历 非递归算法）、后序遍历六个功能。、实验代码/ 描述：两个指针指向左右孩子，算法见教材#include #include #define MAX 50 typedef struct btnode 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 20 页16 / 20 int Data。struct btnode *Llink。struct btnode *Rlink。btnode,*btreetype。btreetype CreatTree(int n/传入数据数量，返回根结点指针 int i。btreetype root=NULL。for (i=0。i btreetype newNode,currentNode,parentNode。newNode=(btreetypemalloc(sizeof(btnode。scanf(%d,&newNode-Data 。newNode-Llink=NULL。newNode-Rlink=NULL 。currentNode=root。if(currentNode=NULLroot=newNode 。else while (currentNode!=NULL parentNode=currentNode 。if(newNode-DataData currentNode=currentNode-Llink。else currentNode=currentNode-Rlink。 if(newNode-DataData parentNode-Llink=newNode 。else parentNode-Rlink=newNode 。 return root。 void OutputTree(btreetype &root 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 20 页17 / 20 btreetype p。p=root-Llink。printf(建立的二叉树的左子树为：n 。while (p!=NULL printf(%-8d,p-Data。p=p-Llink 。 p=root-Rlink。printf(n建立的二叉树的右子树为：n 。while (p!=NULL printf(%-8d,p-Data。p=p-Rlink 。 int depth(btreetype root btreetype p。p=root 。int dep1 。int dep2 。if(root=NULLreturn 0。else dep1=depth(p-Llink。dep2=depth(p-Rlink。if(dep1dep2return(dep1+1。else return(dep2+1。 void PreOrder(btreetype &root/先序遍历 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 20 页18 / 20 printf(%-5d,p-Data。PreOrder(p-Llink。PreOrder(p-Rlink。 void InOrder(btreetype &root/中序遍历 InOrder(p-Llink。printf(%-5d,p-Data。InOrder(p-Rlink。 void InOrder_Norecuision(btreetype &root btreetype stackMAX。btreetype p。int top=0。p=root 。do while (p!=NULL top+。stacktop=p。p=p-Llink 。 if (top0 p=stacktop。top- 。printf(%-5d,p-Data。p=p-Rlink 。 while (p!=NULL|top!=0。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 20 页19 / 20 void PostOrder(btreetype &root btreetype p。p=root 。if (p!=NULL PostOrder(p-Llink。PostOrder(p-Rlink。printf(%-5d,p-Data。 void main( btreetype btree。int count。printf(请输入元素个数： n 。scanf(%d,&count。printf(请输入数据： n 。btree=CreatTree(count。OutputTree(btree。printf(n建立的二叉树的深度为 :%dn,depth(btree。printf(n先序遍历： n 。PreOrder(btree 。printf(n中序遍历 。InOrder(btree。printf(n中序遍历 。InOrder_Norecuision(btree。printf(n后序遍历： n 。PostOrder(btree。printf(n。 实验结果：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 20 页20 / 20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 20 页