2022年数据结构实训报告知识 .pdf
江西信息应用职业技术学院计算机技术系上机实训报告江西信息应用职业技术学院计算机技术系上机实训报告课程：数据结构任课教师：夏侯赟实 训 场 所 及 日期：综 303 机房；2008-10-23 姓名：学号：专业及班级：实训：栈 与 队 列 的基本操作实训序号：3 成员人数：1 一、实训目的及要求1.掌握栈与队列的基本操作，并能对其进行简单应用。2.掌握栈与队列输入与输出，栈与队列的基本操作。二、实训设备状况正常。三、实训内容名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告1、利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。2、对于输入的任意括号串进行匹配进行配对检测；若配对，则返回”right”;若不配对则返回”error”。3、在链队列上的入队和出队操作。四、实训步骤1、步骤 1 进入编程环境，建立一新文件步骤 2 存储定义步骤 3 建立建立链栈的几个基本操作步骤 4 实现十进制转换成二进制步骤 5 编译运行程序，观察运行情况和输出结果2、步骤 4 实现括号匹配配对检测运算3、步骤 3 建立有两个元素的链队列。步骤 4 实现链队列上的入队和出队五、调试过程及实训结果名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告六、总结1、掌握栈与队列的基本操作：入栈、出栈，入队、出队。2、掌握对栈的操作都是在栈顶进行。3、掌握入队操作在队尾，出队操作在队尾。4、在链队列上的入队和出队操作是在单链表上插入和删除操作的特殊情况，只是需要修改队尾或队首指针。5、栈与队列在实际应用中非常广泛。七、附录（源程序清单等）exp1.c：/进制的转换/算法描述:初始化栈只要 x 不为 0 重复做下列动作将 x2 入栈x=x/2 只要栈不为空重复做下列动作:栈顶出栈,输出栈顶元素/*进制转换*/main()名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告 int k,i,j,a8,x;i=0;printf(please input the number:);scanf(%d,&x);while(x!=0)k=x%2;ai+=k;x=x/2;for(j=i-1;j=0;j-)printf(%d,aj);printf(n);exp2.c：/括号匹配/算法描述:从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。/*括号匹配检测*/#include#include#define NULL 0 typedef struct node char data;struct node*next;stacknode,*LinkStack;initstack(LinkStack s)s=NULL;char gettop(LinkStack s)return(s-data);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告 push(LinkStack s,char e)LinkStack p;p=(LinkStack)malloc(sizeof(stacknode);p-data=e;p-next=s;s=p;pop(LinkStack s,char*e)LinkStack p;*e=s-data;p=s;s=s-next;free(p);main()LinkStack s,p;char ch;int bool;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告s=NULL;p=(LinkStack)malloc(sizeof(stacknode);/构造空栈p-data=#;/表示括号串的开始p-next=s;s=p;ch=getchar();bool=1;while(ch!=n&bool)if(ch=()p=(LinkStack)malloc(sizeof(stacknode);/如遇左括号，则左括号进栈p-data=(;p-next=s;s=p;if(ch=)if(s-data)=#)/取栈顶元素与#比较，bool=0;/无左括号配对，令bool=0 else s=s-next;/有左括号配对，名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告则消解左括号ch=getchar();if(s-data)!=#)/取栈顶元素与#比较，bool=0;/左括号数多于右括号，令 bool=0 if(bool)printf(rightn);/如果 bool=1，则打印正确else printf(errorn);/如果 bool=0，则打印错误 同学们根据上述程序，进栈、出栈、取栈顶元素改成函数调用名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告exp3.c：/链队输入、输出/链队列中结点类型定义如下：typedef struct node int data;struct node*link;JD;下面给出有关链队列入队和出队的算法。在把元素 x 加入链队列的算法中，函数返回值为 r，算法如下：JD*enlqueue(JD*r,int x)JD*p;p=(JD*)malloc(sizeof(JD);if(p=NULL)printf(“%s”,“Memory allocation 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告failure”);exit(0);p-data=x;p-link=NULL;r-link=p;return(p);从带头结点的链队列中删除队首元素并存到（*p）指向的变量中，若链队列为空，则函数返回值为空指针，否则函数返回值为r。JD*delqueue(JD*f,JD*r,int*p)JD*s;if(f=r)printf(“Queue Null”);return(NULL);s=f-link;f-link=s-link;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告if(s-link=NULL)r=f;*p=s-data;free(s);return(r);下面给出对链队列进行操作的主函数：#include#include main()JD*r,*f;int q;clrscr();f=r=(JD*)malloc(sizeof(JD);if(f=NULL)printf(“%s”,“Memory allocation failure”);exit(0);r=enlqueue(r,20);名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 12 页 -江西信息应用职业技术学院计算机技术系上机实训报告r=enlqueue(r,30);r=delqueue(f,r,&q);printf(“%dn”,q);r=delqueue(f,r,&q);printf(“%dn”,q);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 12 页 -
