数据结构 栈的基本操作及其应用 课程设计 实验报告

数据结构 栈的基本操作及其应用 课程设计 实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 数 据 结 构 课 程 设 计 设计题目: 栈的基本操作 课题名称 栈的基本操作及其应用 院 系 年级专业 学 号 姓 名 成 绩 1、课题设计目的: (1)掌握栈的基本运算。如:置空栈、判断栈空、进栈、退栈、取 栈顶元素。 (2)栈的顺序存储结构及运算实现栈的顺序存储结构。 (3)掌握栈在程序中的使用 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。 (4)掌握栈的几个基本应用。如:数值转换，判断字符串的中心对 称，(递归调用，表达式的求值等)。 (5)理解算法的设计思想。 课题设计 2、课题设计意义:通过这次课程设计使我懂得了理论与实际相结合 的重要性。我们不仅要牢固的掌握理论知识更要把所学到的理论与目的与 实践相结合。从实践中得出理论，才是真正的知识，才能提高自己 设计意义 的实际动手能力和独立思考的能力。 (2).在此次课程设计当中遇到了很多困难，发现自己原本的很多知 识也没有掌握好，通过这自己动手操作让我学会了很多，对以前的 知识也加深了印象。当然，这也让我对栈及其基本操作和应用有了 更为深刻的了解。 指导教师: 年 月 日 前 言 本课程设计涉及的主要 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 是对栈进行基本操作和实现栈的一些实际应用，在课程设计中，系统开发平台为Windows 2000，程序设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。 本学期我们学了很多关于栈的问题，栈在我们解决实际问题中起了很大的作用。 本次课程设计主要介绍栈的概念和栈的基本操作和栈的两种存储结构极其应用。其中栈的基本操作主要包括置空栈、判断栈空、进栈、出栈、取栈顶元素。栈的两种存储结构是顺序存储结构和链式存储结构。栈是一种简单的数据结构，但在程序设计中却有着广泛的应用，很多程序都需要用栈来做存储结构。如:判断字符串的中心对称，数制转换，函数的递归调用，文字编辑器的设计，算术表达式求值，树或图的遍历，拓扑排序，关键路径。在此次课程设计中做了栈的其中两种应用，即数制转换和判断字符串是否中心对称。 本程序主要是由C语言辅助完成，在Visual C++6.0平台实现的，我们大一的时候学过C语言的，对C语言有着一定的熟练度，有因为有Visual C++6.0这个较好的平台，因此我使用了C语言进行了对栈的操作。 刘磊 2012年12月18日 目 录 第一章 需求分析 ...................................................................................................... 1 1.1栈的定义及基本运算 ........................................................................................... 1 1.2栈的两种存储结构 .............................................................................................. 1 1.3 栈的基本应用..................................................................................................... 1 第二章 实验要求 ............................................................................................................. 2 第三章 实验设计内容 ............................................................................................... 3 第四章 概要设计 ...................................................................................................... 4 第五章 详细设计 ...................................................................................................... 7 1.1置空栈 ................................................................................................................ 7 1.2判断栈空 ............................................................................................................ 7 1.3进栈 ................................................................................................................... 8 1.4出栈 ................................................................................................................... 8 1.5取栈顶元素 ......................................................................................................... 8 第六章 运行结果分析.............................................................................................. 9 第七章 实验总结与 心得体会 决胜全面小康心得体会学党史心得下载党史学习心得下载军训心得免费下载党史学习心得下载 ......................................................................................11 参考文献.........................................................................................................................11 附录(源代码) ............................................................................................................. 12 第一章 需求分析 1.1栈的定义及基本运算 1.定义:栈是限制仅在表尾进行插入和删除定义或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)，不含元素的栈成为空栈。 (注意:栈的修改是是按照后进先出的原则进行的) 2.栈的基本运算(栈的基本运算有五种) (1)置空栈SETNULL(S):将S置成空栈; (2)判断栈是否为空EMPTY(S):这是一个布尔函数，若S为空，则函数值为“真”，否则为“假” ; (3)进栈PUSH(S，x):在S的顶部插入(亦称为压入)元素x; (4)退栈POP(S):删除(亦称弹出)栈S的顶部元素，若要在退栈的同时返回被删除的栈顶元素，则将POP(S)定义为一个类型和栈元素相同的函数; (5)取栈顶TOP(S);取栈S的顶部元素。与POP(S)不同之处是:TOP(S)不改变栈的状态。 1.2栈的两种存储结构 1. 栈的顺序存储结构(简称为数序栈) 顺序栈是利用一批地址连续顺序存储结构的存储单元依次存放自栈底到栈顶的数据元素。 2. 栈的链式存储结构(简称为链栈) 它是运算收限制的单链表，其插入和删除操作只能在表头位置上进行。 1.3 栈的基本应用 栈是一种简单的数据结构，但在程序设计中却有着广泛的应用，很多程序都需要用栈来做存储结构。如:判断字符串的中心对称，数制转换，函数的递归调用，算术表达式求值，树或图的遍历，拓扑排序，关键路径。 在此次课程设计中做了栈的其中两种应用，即数制转换和判断字符串是否为中心对称。 1 第二章 实验要求 1.硬件设备:安装有Visual C++ 的PC机一台，10GB以上的硬盘，64MB以上的内存环境，Windows XP 操作系统 Microsoft记事本程序。 Microsoft Visual C++编译器 2.加深理解栈座位一种受限制的特殊线性表的特殊性所在。 3.掌握栈的基本操作，初始化栈、判栈空、入栈、出栈等运算在两种存储结构上的实现(进行栈的基本操作时要注意栈的“后进先出”的特性)。 4.利用栈解决一些实际性的问题，即栈的应用，这次课程设计介绍的是栈在数制转换和判断字符串是否为中心对称问题中的应用。 2 第三章 实验设计内容 实验设计的主要内容有: 1.首先要知道什么是栈。栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 2(了解栈的两种存储结构。即顺序存储和链式存储。 (1)顺序栈。栈的顺序存储结构称为顺序栈，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指向栈顶元素在顺序栈的位置。通过顺序栈的位置。通过顺序栈的实现进而对栈进行栈的基本操作。 (2)链式栈。栈的链式存储结构称为链式栈， 3..学会使用栈的几种基本运算。栈的基本运算有五种，即:置空栈、判栈空、进栈、出栈、取栈顶元素。栈的这五种运算都是要在顺序表中进行的。 4.函数的实现。 在此次课程设计当中需要用到很多的函数。如:建空栈、判栈空、进栈、出栈、取栈顶元素等函数的定义和使用。在制转换和字符串中心对称判断过程中的使用的一些函数，主函数的使用，即主函数中调用前面的一些函数，还有在整个算法实现的过程中用到的一些循环语句和选择语句。 5.程序编码完成以后要进行运行、编译和调试。 6.最后写出一篇课程设计的实验报告。 3 第四章 概要设计 这次课程设计主要做的是栈的一些基本操作和栈的两个应用。分析如下: 1.栈的一些基本操作。即:创建一个顺序栈，在顺序栈上实现栈的五种基本操作: 置空栈、判断栈空、进栈、出栈、取栈顶元素。 (1)创建顺序栈，顺序栈的类型定义如下: #include #include #include # define m 10 typedef struct { int a[m]; int top; }stack; void main() {int isempty(stack *s); int isfull(stack *s); int gettop(stack *s,int x); int get(stack *s,int b); void push(stack *s,int x); void pop(stack*s); int i,x,b,c,j=0; stack *s; s=(stack *)malloc(sizeof(stack)); s->top=0; printf("please enter 10 numbers\n"); for(i=0;i<=m-1;i++) { scanf("%d",&x); push(s,x); } if(isempty(s))printf("空栈\n"); else printf("非空\n"); if(isfull(s))printf("满栈\n"); else printf("非满\n"); gettop(s,x); printf("最后一个进栈元素为%d\n",x); printf("请输入要找第几号元素,\n"); scanf("%d",&b); 4 c=get(s,b); printf("第%d元素为%d\n",b,c); printf("是否出栈,出栈请输入1\n"); scanf("%d",&j); printf("原栈中元素为:\n"); if(j)pop(s); else printf("出栈失败～\n"); } int isempty(stack *s) { if(s->top==0) return 1; else return 0; } int isfull(stack *s) { if(s->top==m) return 1; else return 0; } int gettop(stack *s,int x) {int i; i=isempty(s); if(i)printf("empty"); else x=s->a[s->top-1]; return x; } void push(stack *s,int x) {int i; i=isfull(s); if(i)printf("overflow"); else { s->a[s->top]=x; s->top++; } } int get(stack *s,int b) { 5 int c; c=s->a[b-1]; return c; } void pop(stack*s) {int i,j,t; t=s->top; for(i=0;ia[s->top-1]); s->top--;} printf("%d\n",s->a[s->top-1]); s->top--; j=isempty(s); if(j)printf("出栈成功～\n"); } 6 第五章 详细设计 首先创建一个栈(初始化)。确定栈是否为空。确定栈是否为满。去的栈顶元素。出栈(删除)元素运算。入栈(插入)元素运算。建一个顺序栈，正如顺序表一样，可以用一维数组来表示栈，一个数组元素可以保存一个栈元素。可以使用数组的一端作为“栈顶”，由于栈在栈顶进行操作，所以要保存栈顶的位置，可以设置一个栈顶指针Top来指向栈顶。Top的初值很重要。第一种情形:当栈空时，可以设置栈顶指针Top不指向任何元素，即Top=-1，这样Top>-1时，Top指向的位置即栈顶的元素。第二种情形:让Top指针总是指向栈顶元素上面第一个未用的数组元素位置。如栈顶元素位于i，则栈的指针Top为i+1，栈空时即对应Top=0,Top的初值影响了栈的基本操作，前者出栈时要取得栈顶元素值，再让栈顶指针Top的值减1，入栈时要先让栈顶指针加1，再把元素存入新栈顶位置。后者出栈时，现要把栈顶指针减1，然后再取得当前指针所在元素，进栈时则是先把栈顶元素放入到指针Top指向的数组位置，Top指针再加1。在此次算法程序中用的是第一种情形的。 先建一个顺序栈 顺序栈的类型和变量定义如下: typeddef int datatype ; #define maxsize 64 typedef struct {datatype data[maxsize]; int Top }seqstack; seqstack *s; 5.1置空栈 SETNULL(s) /*将顺序栈s置为空*/ Seqstack *s; { s->Top=-1 } 5.2判断栈空 Int EMPTY(s) Seqtack *s; { if(s->Top>=0) 7 return 0; else return 1; } 5.3进栈 ,,,,(,，,) 进栈时，首先要判断栈是否为满，如果栈为满，则返回NULL，否则将栈顶指针加1，然后将x插入当前栈顶。 5.4出栈 ,,,(,) 出栈(亦称删除)，所以首先要判断栈是否为空，可以直接调用判断栈是否为空的函数，如果栈为空，则返回NULL，否则删除栈顶元素。 5.5取栈顶元素 ,,,(,) 首先判断栈是否为空，若为空则返回,,,,，否则取栈,的栈顶。 8 第六章 运行结果分析 在设计的过程中遇到了许多问题，并最终得到解决，其分析过程如下: 1. 利用栈的调试结果分析如图1所示: 图1 输入十个元素 图2 输入的第几号元素 9 图3 出栈 10 第七章 实验总结与心得体会 本程序利用栈的一些基本操作及其他函数的应用实现了数制转换和判断字符串是否中心对称的问题。在这些程序的实现过程中遇到了很多的问题。在数制转换的过程中，一开始没有考虑到转化为十六进制(大于10)的情况，了解以后，利用菜单，做了一个转化为十六进制的情况，小于10的数以整型输出，大于十的数以字符型输出。顺序栈只参与其中的十进制整数转换部分。在判断字符串是否为中心对称的算法操作过程中，利用了栈的后进先出原则， 通过本次说数据结构的课程设计，我学习了很多在上课时没有真正理解的知识，并对栈的一些基本操作及利用栈实现数制转换和判断字符串是否为中心对称问题的算法上有了更加深刻的了解，巩固了在课堂上学习有关栈的知识，真正学会了一种算法。当求解一个算法时，不是拿到问题就不假思索地做，而是首先要先对它有个大概的了解，接着再详细的分析每一步该怎么做。 这次课程设计中出现了很多不该有的错误，但在自己的不断修改和老师、同学们的帮助下，完成了这次课程设计的程序编写的过程。这不仅是课程设计，更是锻炼我们处理问题的能力，同时也使我了解到团队合作的重要性，编写程序是一件细心的事，稍不留神就会出错，这就必须要求我们对待事情要认真。在边洗程序的过程中，错误不断出现，错误的类型有很多，如:少写了一个符号，写错了一个字母等等。这考验我们待事的细心、耐心，能不能坚持到底，不能半途而废。在这次程序编写中，我们一起讨论、一起分析，错了再写，写了再改，经过了多次修改，终于完成了一个正确的程序编码。 我也从中找到了字的快乐，每当自己完成一个函数时，都会很激动，因为那是自己努力后的收获，同时也使我感受到了学习的快乐。 参考文献 [1] 徐德民.最新C语言程序设计.电子工业出版社.1992 [2] 张国锋.C++语言及其程序设计教程.电子工业出版社.1992 11 附录(源代码) #include #include #include typedef struct { int data; int a; struct Lnode *next; }Lnode; void main() { int m,n,i;Lnode *p,*q,*r; Lnode *establish_h(Lnode*p,int n); Lnode *nizhi(Lnode *p); printf("请输入人数\n"); scanf("%d",&n); p=establish_h(p,n); p=nizhi(p); printf("请输入m初值\n"); scanf("%d",&m); printf("出列序列为\n"); while(p->a<=n&&p->a>0) { for(i=1;inext; } m=p->data; printf("%d\n",p->a); q=p->next; r->next=q; free(p); p=q; 12 } } Lnode *establish_h(Lnode*p,int n) {Lnode *q;int i;int t; p=(Lnode*)malloc(sizeof(Lnode)); p->data=n;//头节点存储元素个数 p->next=NULL; i=1;//第二个节点开始存储元素 while(i<=p->data) { q=(Lnode*)malloc(sizeof(Lnode)); printf("请输入密码(用回车隔开)\n"); scanf("%d",&t); q->data=t; q->a=i; q->next=p->next; p->next=q; i++; } return p; } Lnode *nizhi(Lnode *p) { Lnode *q,*w;int i;int t; Lnode *r;Lnode *l; q=p->next; l=(Lnode*)malloc(sizeof(Lnode)); l->data=p->data; l->a=p->a; l->next=NULL; i=1;//第二个节点开始存储元素 while(i<=l->data) 13 { r=(Lnode*)malloc(sizeof(Lnode)); r->data=q->data; r->a=q->a; q=q->next; r->next=l->next; l->next=r; i++; } p=l; q=p->next; printf("起始密码顺序为:\n"); for(i=1;q->next;i++) { printf("%d\n",q->data); q=q->next; } printf("%d\n",q->data); q->next=p->next; p=q->next; return p; } 14 15 16