《2022年结构分析方案》由会员分享,可在线阅读,更多相关《2022年结构分析方案(20页珍藏版)》请在金锄头文库上搜索。
1、1 / 20 数据结构实验实验内容和目的:掌握几种基本的数据结构:集合、线性结构、树形结构等在求解实际问题中的应用,以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。实验教材:数据结构题集 及基本操作 , 如入栈、出栈等,栈的顺序存储结构和链式存储结构,以便在实际问题背景下灵活应用。本程序采用的是链栈结构,具有初始化一个栈、PUSH 、POP 、显示所有栈里的元素四个功能。 循环队列掌握队列的特点 ( 先进先出 FIFO及基本操作 , 如入队、出队等,学会循环队列的实现,以便在实际问题背景下灵活运用。本程序具有初始
2、化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。、实验代码 栈程序代码:#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,i
3、nt 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 Pus
4、h(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(ERR
5、OR。 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(Su
6、ccess!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 OVERF
7、LOW -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。 / 参数( 传出SqQ
8、ueue &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!
9、=-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
10、.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(me
11、nu_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。br
12、eak。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 实验二、数组
13、、实验内容:数组一般不做插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动。本程序数组的大小定义为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
14、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。
15、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转置: n
16、3.矩阵 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
17、 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 精选学
18、习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 20 页13 / 20 实验三、查找、实验内容掌握各种查找 顺序、二分法、查找树、哈希)方法及适用场合,并能在解决实际问题时灵活应用。本实验采用二分查找。二分查找又称折半查找,它是一种效率较高的查找方法。折半查找法的优点是比较次数少,查找速度快,平均性能好。其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。本程序具有找出数据位置和显示查找次数两个功能。、实验代码:#include #define MAX 100 void main( int r
19、MAX,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 brea
20、k。 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 实验四、树、实验内容:进一步掌握树的结构及非线性特点,递归特点和动态性;进一步巩固对指针的使用和二叉树的三种遍历方
21、法、建立方法及用广义表进行输入输出。本程序将第一个元素作为树根,其余元素若小于树根则为左子树,若大于树根则为右子树。本程序具有求左子树、求右子树、求深度、先序遍历、中序遍历递归算法)、中序遍历 非递归算法)、后序遍历六个功能。、实验代码/ 描述:两个指针指向左右孩子,算法见教材#include #include #define MAX 50 typedef struct btnode 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 20 页16 / 20 int Data。struct btnode *Llink。struct btn
22、ode *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 。
23、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 精选学习资料 - - - - - - - - - 名师归纳总结 - - -
24、 - - - -第 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=
25、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-Dat
26、a。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
27、 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 页