2022年结构分析方案.docx

精选学习资料 - - - - - - - - - 数据结构试验试验内容和目的：把握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问 题中的应用,以及培育书写规范文档的技巧；学习基本的查找和排序技 术；让我们在实际上机中具有编制相当规模的程序的才能；养成一种良好 的程序设计风格；试验教材：数据结构题集 <C 语言版）清华高校出版社 2007年试验工程：试验一、栈和循环队列 、试验内容： 栈 把握栈的特点 先进后出 FILO>及基本操作 , 如入栈、出栈等,栈 的次序储备结构和链式储备结构,以便在实际问题背景下敏捷应 用；本程序采纳的是链栈结构,具有初始化一个栈、PUSH、POP、显示全部栈里的元素四个功能； 循环队列 把握队列的特点 先进先出 FIFO>及基本操作 , 如入队、出队等,学 会循环队列的实现,以便在实际问题背景下敏捷运用；本程序具有 初始化一个队列、入队、出队、显示队列的全部元素、队列长度五 个功能；、试验代码 栈 程序代码：#include <stdio.h> #include <malloc.h> #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType；typedef struct SNode SElemType data；struct SNode *next；1 / 20 名师归纳总结 - - - - - - -第 1 页,共 20 页精选学习资料 - - - - - - - - - SNode,*LinkStack ；int CreatTwoLinkStack &head,int n> int i；SNode *p；head=LinkStack>mallocsizeofSNode>>；head->next=NULL；printf"请输入数据 数字>:n"> ；fori=n；i>0 ；-i> p=SNode *>mallocsizeofSNode>>scanf"%d",&p->data>；p->next=head->next ；head->next=p ； return 1；int menu_select> int sn；for ；> scanf"%d",&sn> ；ifsn<1|sn>6> else printf"nt输入错误,请重新输入 n"> ；break ； return sn； int PushLinkStack &top,SElemType e> SNode *q；q=LinkStack>mallocsizeofSNode>>；if.q> printf" 溢出 .n"> ；returnERROR>； 2 / 20 名师归纳总结 - - - - - - -第 2 页,共 20 页精选学习资料 - - - - - - - - - q->data=e ；q->next=top->next；top->next=q ；returnOK> ； int PopLinkStack &top,SElemType &e> SNode *q；if.top->next> printf"error.n">；returnERROR>； e=top->next->dataq=top->next ；top->next=q->next；freeq> ； returnOK> ；void main> int e；LinkStack top；printf"1. 初始化一个栈； n2.PUSH；n3.POP；n4. 显示全部栈 里的元素； n5. 终止； n"> ；while1> switchmenu_select>> case 1: ifCreatTwotop,Stack_Size>>printf"Success.n">；break ； case 2: printf"Push:n">；scanf"%d",&e> ；ifPushtop,e>>printf"Success.n">；break ；case 3: ifPoptop,e>>printf"Success.n">；printf"%dn",e>；break ；case 4: LinkStack p ；printf" 全部栈里的元素 :n"> ；p=top；whilep->next> 3 / 20 名师归纳总结 - - - - - - -第 3 页,共 20 页精选学习资料 - - - - - - - - - p=p->next ；printf"%7d",p->data>； printf"n">；break ；case 5: return ； 运行结果： 循环队列程序代码：#include<stdlib.h> #include<stdio.h> #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef struct int *elem；/ 队列储备空间 int front；4 / 20 名师归纳总结 - - - - - - -第 4 页,共 20 页精选学习资料 - - - - - - - - - int rear SqQueue；/ 判定挑选是否正确 int menu_select> int sn；for ；> scanf"%d",&sn> ；ifsn<1|sn>6> printf"nt输入错误,请重新输入 n"> ；else break ； return sn； / 参数 传出>SqQueue &Q,循环队列 空> int InitQueueSqQueue &Q> Q.elem=int *>mallocMAXSIZE*sizeofint>>；if.Q.elem>exitOVERFLOW> ；Q.front=Q.rear=-1；forint i=0；i<MAXSIZE；i+> Q.elemi=-1；return OK ； / 返回 Q的元素个数 int QueueLengthSqQueue Q> return Q.rear-Q.front+MAXSIZE>%MAXSIZE ； / 显示队列的元素 void DisplaySqQueue Q> forint i=0；i<=QueueLengthQ>；i+> ；ifQ.elemi.=-1>printf"%d ",Q.elemi>printf"n">； / 入队5 / 20 名师归纳总结 - - - - - - -第 5 页,共 20 页精选学习资料 - - - - - - - - - int EnQueueSqQueue &Q,int e> Q.rear=Q.rear+1>%MAXSIZE；ifQ.rear=Q.front>return ERROR；Q.elemQ.rear=e；return OK ； / 出队 int DeQueueSqQueue &Q,int &e> ifQ.front=Q.rear>return ERROR；e=Q.elemQ.front+1；Q.elemQ.front+1=-1；Q.front=Q.front+1>%MAXSIZE ；return OK ； void main> SqQueue Q；InitQueueQ> ；int elem,e printf" 请输入队列元素 以 0 终止 >:n"> ；scanf"%d",&elem> ；whileelem.=0> EnQueueQ,elem>； printf"scanf"%d",&elem> ；队列为： n"> ；DisplayQ> ；printf"1. 初始化一个队列； n2. 入队； n3. 出队； n4. 显示队 列的全部元素； n5. 队列长度 :n6. 终止； n"> ；while1> switchmenu_select>> case 1: printf"请输入队列元素 以 0 终止>:n"> ；scanf"%d",&elem> ； whileelem.=0> EnQueueQ,elem>；scanf"%d",&elem> ； printf" 队列为： n"> ；6 / 20 名师归纳总结 - - - - - - -第 6 页,共 20 页精选学习资料 - - - - - - - - - DisplayQ> ；fflushstdin>；break ； case 2: scanf"%d",&elem> ；EnQueueQ,elem>；printf" 队列为： n"> ；DisplayQ> ；fflushstdin>break ；case 3: DeQueueQ,elem>；printf" 队列为： n"> ；DisplayQ> ；break ；case 4: printf"n 队列的全部元素 :n"> ；DisplayQ> ；break ；case 5: printf"%dn",QueueLengthQ>>；break ；case 6: return ； 运行结果：7 / 20 名师归纳总结 - - - - - - -第 7 页,共 20 页精选学习资料 - - - - - - - - - 8 / 20 名师归纳总结 - - - - - - -第 8 页,共 20 页精选学习资料 - - - - - - - - - 试验二、数组、试验内容：数组一般不做插入或删除操作,也就是说,一旦建立了数组,就结构中的数据元素个数和元素之间的关系就不再发生变动；本程序数组的大小定义为3*3,可以通过修改“#define M ” 来变动；本程序具有矩阵相加、矩阵 能；、试验代码：#include <stdio.h> #define M 3 A转置、矩阵 B转置、矩阵相乘四个功void MatrixAddint m1MM,int m2MM,int resultMM>/ 两 个矩阵 m1和 m2相加 , 结果放到 result int i,j for i=0；i<M；i+> forj=0；j<M；j+> ；resultij=m1ij+m2ij void MatrixTramsint m1MM,int resultMM>/ 矩阵转置 int i,j；for i=0；i<M；i+> for j=0；j<M；j+> resultij=m1ji void MatrixMultiplyint m1MM,int m2MM,int resultMM> int i,j for i=0；i<M；i+> for j=0；j<M；j+> resultij=0；for int k=0；k<M；k+> 9 / 20 名师归纳总结 - - - - - - -第 9 页,共 20 页精选学习资料 - - - - - - - - - resultij+=m1ik*m2kj； void Displayint resultMM>/ 显示矩阵 int i,j；i<M；i+> for i=0 forj=0；j<M；j+> ；printf"%-5d",resultij>printf"n">； void main> int AMM,BMM；int i,j；printf"请输入第一个矩阵： n"> ；fori=0；i<M；i+> forj=0；j<M；j+> scanf"%d",&Aij>；printf"请输入其次个矩阵： n"> ；fori=0；i<M；i+> forj=0；j<M；j+> scanf"%d",&Bij>int resultMM；/*printf"n 矩阵 A:n"> ；DisplayA> ；printf"n 矩阵 B:n"> ；DisplayB> ；*/ printf" 请挑选： n1. 矩阵相加： n2. 矩阵 A 转置： n3. 矩阵 B 转置： n4. 矩阵相乘： n5. 退出； nn"> ；while 1> int l；scanf"%d",&l>switchl> case 1: printf" 矩阵相加的运算结果： n"> ；MatrixAddA,B,result>；Displayresult>；printf"n">；break ；10 / 20 名师归纳总结 - - - - - - -第 10 页,共 20 页精选学习资料 - - - - - - - - - case 2: printf"矩阵 A 转置的运算结果： n"> ；MatrixTramsA,result>；Displayresult>；printf"n">；break ；case 3: printf" 矩阵 B 转置的运算结果： n"> ；MatrixTramsB,result>；Displayresult>；printf"n">；break ；case 4: printf" 矩阵相乘的运算结果： n"> ；MatrixMultiplyA,B,result>；Displayresult>；printf"n">；break ；case 5: printf" 退出； n"> ；return ；default: printf" 输入错误！ ">；printf"n">； 试验结果：11 / 20 名师归纳总结 - - - - - - -第 11 页,共 20 页精选学习资料 - - - - - - - - - 12 / 20 名师归纳总结 - - - - - - -第 12 页,共 20 页精选学习资料 - - - - - - - - - 试验三、查找 、试验内容 把握各种查找 <次序、二分法、查找树、哈希）方法及适用场 合,并能在解决实际问题时敏捷应用；本试验采纳二分查找；二分查找又称折半查找,它是一种效率较高的查找方法；折半查找法的优点是比较次数少,查找速度快,平均性能好；其缺点是要求待查表为有序表,且插入删除困难；因此,折半查找方法适用于不常常变动而查找频繁的有序列表；本程序具有找出数据位置和显示查找次数两个功能；、试验代码：#include <stdio.h> #define MAX 100 void main> int rMAX,i,k,low,high,mid,m,n；<以-1 终止）：printf"nn 建立递增有序的查找次序表n"> ；fori=0；i<MAX；i+> scanf"%d",&ri>；ifri=-1> n=i ；13 / 20 名师归纳总结 - - - - - - -第 13 页,共 20 页精选学习资料 - - - - - - - - - break ； printf"n 请输入要查找的数据： n"> ；scanf"%d",&k> ；low=0；high=n-1 ；m=0；whilelow<=high> mid=low+high>/2 ；m+；ifrmid>k> high=mid-1 ；else ifrmid<k> low=mid+1；else break ；iflow>high> printf" 没有找到 n"> ；printf" 共进行 %d次比较； n",m> ；ifrmid<k> mid+；可将这个数插入到第 %d个数的后面； n",mid> ；printf" else printf"n 要找的数据 =%d在第 %d个数的位置上；共进行了 %d次比较； n",m> ；n",k,mid+1>； printf"nn 试验结果：14 / 20 名师归纳总结 - - - - - - -第 14 页,共 20 页精选学习资料 - - - - - - - - - 试验四、树 、试验内容：进一步把握树的结构及非线性特点,递归特点和动态性；进 一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用 广义表进行输入输出；本程序将第一个元素作为树根,其余元素 如小于树根就为左子树,如大于树根就为右子树；本程序具有求 左子树、求右子树、求深度、先序遍历、中序遍历 <递归算法）、中序遍历 <非递归算法）、后序遍历六个功能；、试验代码/ 描述：两个指针指向左右孩子,算法见教材 #include <stdio.h> #include <stdlib.h> #define MAX 50 typedef struct btnode 15 / 20 名师归纳总结 - - - - - - -第 15 页,共 20 页精选学习资料 - - - - - - - - - int Data；struct btnode *Llink；struct btnode *Rlink；btnode,*btreetype；btreetype CreatTreeint n>/ int i；传入数据数量,返回根结点指针btreetype root=NULL；for i=0；i<n ；i+> btreetype newNode,currentNode,parentNode；newNode=btreetype>mallocsizeofbtnode>> scanf"%d",&newNode->Data> ；newNode->Llink=NULL；newNode->Rlink=NULL；currentNode=root；ifcurrentNode=NULL>root=newNode ；else while currentNode.=NULL> parentNode=currentNode ；ifnewNode->Data<currentNode->Data> currentNode=currentNode->Llink；else currentNode=currentNode->Rlink；ifnewNode->Data<parentNode->Data> parentNode->Llink=newNode ；else parentNode->Rlink=newNode ； return root； void OutputTreebtreetype &root> 16 / 20 名师归纳总结 - - - - - - -第 16 页,共 20 页精选学习资料 - - - - - - - - - btreetype p；p=root->Llink；printf" 建立的二叉树的左子树为：n"> ；while p.=NULL> printf"%-8d",p->Data>；p=p->Llink ； p=root->Rlink；n"> ；printf"n建立的二叉树的右子树为：while p.=NULL> printf"%-8d",p->Data>；p=p->Rlink ； int depthbtreetype root> btreetype p；p=root ；int dep1 ；int dep2 ；ifroot=NULL>return 0；else dep1=depthp->Llink>；dep2=depthp->Rlink>；ifdep1>dep2>returndep1+1>；else returndep2+1>； void PreOrderbtreetype &root>/ 先序遍历 <递归）btreetype p；p=root ；if p.=NULL> 17 / 20 名师归纳总结 - - - - - - -第 17 页,共 20 页精选学习资料 - - - - - - - - - printf"%-5d",p->Data>；PreOrderp->Llink>；PreOrderp->Rlink>； void InOrderbtreetype &root>/ 中序遍历 <递归） btreetype p；p=root ；if p.=NULL> InOrderp->Llink>；printf"%-5d",p->Data>InOrderp->Rlink>；void InOrder_Norecuisionbtreetype &root> btreetype stackMAX；btreetype p；int top=0；p=root ；do while p.=NULL> top+；stacktop=p；p=p->Llink ； if top>0> p=stacktop；top- ；printf"%-5d",p->Data>p=p->Rlink ； while p.=NULL|top.=0>； 18 / 20 名师归纳总结 - - - - - - -第 18 页,共 20 页精选学习资料 - - - - - - - - - void PostOrderbtreetype &root> btreetype p；p=root ；if p.=NULL> PostOrderp->Llink>；PostOrderp->Rlink>；printf"%-5d",p->Data>void main> btreetype btree；int count；printf"请输入元素个数： n"> ；scanf"%d",&count>；printf"请输入数据： n"> ；btree=CreatTreecount>；OutputTreebtree>；printf"n建立的二叉树的深度为 :%dn",depthbtree>>printf"n先序遍历： n"> ；PreOrderbtree> ；printf"n 中序遍历 <递归算法）： n"> ；InOrderbtree>；printf"n 中序遍历 <非递归算法）： n"> ；InOrder_Norecuisionbtree>；printf"n 后序遍历： n"> ；PostOrderbtree>；printf"n">； 试验结果：19 / 20 名师归纳总结 - - - - - - -第 19 页,共 20 页精选学习资料 - - - - - - - - - 20 / 20 名师归纳总结 - - - - - - -第 20 页,共 20 页