C语言中堆和栈的区别(搜集整理)
2011-04-18 17:36
堆(heap)和栈(stack)有什么区别??
简单的可以理解为:
heap:是由malloc之类函数分配的空间所在地。地址是由低向高增长的。
stack:是自动分配变量,以及函数调用的时候所使用的一些空间。地址是由高向低减少的。
预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。- 程序结束后有系统释放
4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
二、例子程序
这是一个前辈写的,非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456在常量区,p3在栈上。
static int c =0;全局(静态)初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。
}
二、堆和栈的理论知识
2.1申请方式
stack:
由系统自动分配。例如,声明在函数中一个局部变量int b; 系统自动在栈中为b开辟空间heap:
需要程序员自己申请,并指明大小,在c中malloc函数
如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = (char *)malloc(10);
但是注意p1、p2本身是在栈中的。
2.2
申请后系统的响应
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
2.3申请大小的限制
栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M (也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
2.4申请效率的比较:
栈由系统自动分配,速度较快。但程序员是无法控制的。
堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.
另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度,也最灵活2.5堆和栈中的存储内容
栈:在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。
堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
2.6存取效率的比较
char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的;
而bbbbbbbbbbb是在编译时就确定的;
但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。
比如:
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指edx中,在根据edx读取字符,显然慢了。
?
2.7小结:
堆和栈的区别可以用如下的比喻来看出:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
堆和栈的区别主要分:
操作系统方面的堆和栈,如上面说的那些,不多说了。
还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
第二个解释的:
在C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。
自由存储区,就是那些由malloc等分配的内存块,他和堆是十分相似的,不过它是用free 来结束自己的生命的。
全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的C语言中,全局
变量又分为初始化的和未初始化的,在C++里面没有这个区分了,他们共同占用同一块内存区。
常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改(当然,你要通过非正当手段也可以修改,而且方法很多,在《const的思考》一文中,我给出了6种方法)明确区分堆与栈
在bbs上,堆与栈的区分问题,似乎是一个永恒的话题,由此可见,初学者对此往往是混淆不清的,所以我决定拿他第一个开刀。
首先,我们举一个例子:
void f() { int* p=new int[5]; }
这条短短的一句话就包含了堆与栈,看到new,我们首先就应该想到,我们分配了一块堆内存,那么指针p呢?他分配的是一块栈内存,所以这句话的意思就是:在栈内存中存放了一个指向一块堆内存的指针p。在程序会先确定在堆中分配内存的大小,然后调用operator new分配内存,然后返回这块内存的首地址,放入栈中,他在VC6下的汇编代码如下:00401028 push 14h
0040102A call operator new (00401060)
0040102F add esp,4
00401032 mov dword ptr [ebp-8],eax
00401035 mov eax,dword ptr [ebp-8]
00401038 mov dword ptr [ebp-4],eax
这里,我们为了简单并没有释放内存,那么该怎么去释放呢?是delete p么?澳,错了,应该是delete []p,这是为了告诉编译器:我删除的是一个数组,VC6就会根据相应的Cookie 信息去进行释放内存的工作。
好了,我们回到我们的主题:堆和栈究竟有什么区别?
主要的区别由以下几点:
1、管理方式不同;
2、空间大小不同;
3、能否产生碎片不同;
4、生长方向不同;
5、分配方式不同;
6、分配效率不同;
管理方式:对于栈来讲,是由编译器自动管理,无需我们手工控制;对于堆来说,释放工作由程序员控制,容易产生memory leak。
空间大小:一般来讲在32位系统下,堆内存可以达到4G的空间,从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲,一般都是有一定的空间大小的,例如,在VC6下面,默认的栈空间大小是1M(好像是,记不清楚了)。当然,我们可以修改:
打开工程,依次操作菜单如下:Project->Setting->Link,在Category 中选中Output,然后在Reserve中设定堆栈的最大值和commit。
注意:reserve最小值为4Byte;commit是保留在虚拟内存的页文件里面,它设置的较大会使栈开辟较大的值,可能增加内存的开销和启动时间。
碎片问题:对于堆来讲,频繁的new/delete势必会造成内存空间的不连续,从而造成大量的碎片,使程序效率降低。对于栈来讲,则不会存在这个问题,因为栈是先进后出的队列,他们是如此的一一对应,以至于永远都不可能有一个内存块从栈中间弹出,在他弹出之前,在他上面的后进的栈内容已经被弹出,详细的可以参考数据结构,这里我们就不再一一讨论了。
生长方向:对于堆来讲,生长方向是向上的,也就是向着内存地址增加的方向;对于栈来讲,它的生长方向是向下的,是向着内存地址减小的方向增长。
分配方式:堆都是动态分配的,没有静态分配的堆。栈有2种分配方式:静态分配和动态分配。静态分配是编译器完成的,比如局部变量的分配。动态分配由alloca函数进行分配,但是栈的动态分配和堆是不同的,他的动态分配是由编译器进行释放,无需我们手工实现。分配效率:栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。堆则是C/C++函数库提供的,它的机制是很复杂的,例如为了分配一块内存,库函数会按照一定的算法(具体的算法可以参考数据结构/操作系统)在堆内存中搜索可用的足够大小的空间,如果没有足够大小的空间(可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,然后进行返回。显然,堆的效率比栈要低得多。
从这里我们可以看到,堆和栈相比,由于大量new/delete的使用,容易造成大量的内存碎片;由于没有专门的系统支持,效率很低;由于可能引发用户态和核心态的切换,内存的申请,代价变得更加昂贵。所以栈在程序中是应用最广泛的,就算是函数的调用也利用栈去完成,函数调用过程中的参数,返回地址,EBP和局部变量都采用栈的方式存放。所以,我们推荐大家尽量用栈,而不是用堆。
虽然栈有如此众多的好处,但是由于和堆相比不是那么灵活,有时候分配大量的内存空间,还是用堆好一些。
无论是堆还是栈,都要防止越界现象的发生(除非你是故意使其越界),因为越界的结果要么是程序崩溃,要么是摧毁程序的堆、栈结构,产生以想不到的结果,就算是在你的程序运行过程中,没有发生上面的问题,你还是要小心,说不定什么时候就崩掉,那时候debug 可是相当困难的:)
对了,还有一件事,如果有人把堆栈合起来说,那它的意思是栈,可不是堆,呵呵,清楚了?
栈的应用:C实现简单计算器(表达式的计算) 作为栈的著名应用,表达式的计算可以用下面方法实现: 首先建立两个栈,操作数栈NUM_S和运算符栈OPR_S。 其中,操作数栈用来存储表达式中的操作数;运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W 做如下不同的处理: 1.若W为操作数,则将W压入操作数栈NUM_S,且继续扫描下一个字符; 2.若W为运算符,则根据运算符的性质做相应的处理: (0)若符号栈为空,无条件入栈当前指针指向的字符 (1)若w为不大于运算符栈栈顶的运算符,则从操作数栈NUM_S中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈 OPR_S中弹出一个运算符,比如为+,然后作运算a+b,并将运算结果压入操作数栈NUM_S。 (2)若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符,则将运算符W 压入运算符栈OPR_S,并继续扫描下一个字符。 (3)若运算符W为右括号,循环操作(设先后弹出的操作数为a、b,再从运算符栈OPR_S中弹出一个运算符,比如为+,然后作运 算a+b, 并将运算结果压入操作数栈NUM_S),直到从运算符栈中弹出第一个左括号。 (4)若运算符W为表达式结束符‘=’,循环操作(设先后弹出的操作数为a、b,再从运算符栈OPR_S中弹出一个运算符,比如为 +,然后作运算a+b, 并将运算结果压入操作数栈NUM_S),直到运算符栈为空为止。此时,操作数栈栈顶元素即为表达式的 值。 ====================================================================== === 举例:计算3+(5-2*3)/4-2= (1)开始栈为空,3入栈,+入栈,(无条件入栈,5入栈,-号优先级比(高,所以-号入栈,2入栈,*优先级比目前栈顶的-号优先级高,所以*入栈,3入栈,接着扫描到)括号,)括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - |
C语言栈的使用 #include
while(N!=0) {Push (&s,N%r); N=N/r; } while(!StackEmpty(&s)) { Pop(&s,e); cout<
目录 题目一.二叉树操作(1)二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18)
题目一.二叉树操作(1)二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程,为了让大家更好地理解与运用所学知识,提高动手能力,我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识,还要求学生具备一定的C语言基础和编程能力。 (1)题目一的目的: 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 (2)题目二的目的: 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 (1)题目一的内容和要求: 1、编写已知二叉树的先序、中序序列,恢复此二叉树的程序 2、编写求二叉树深度的程序 (2)题目二的内容和要求: 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数,运算符为 加减乘除,界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值
三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列,依次从先序遍历序列中取结点,由先序序列确定根结点(就是第一个字母),每次取出一个结点就与中序遍历的序列进行比较,当相等的时候,中序遍历序列就被分成以该结点为根的二叉树子树,该结点左部分为左子树,右部分为右子树,直到取完先序列里的所有结点,则二叉树构造完毕(树用链式存储结构存储),用递归实现! 由建好的二叉树,先判断这棵树是否为空,若不为空则找数的左子树,统计它的高度,然后找树的右子树,统计它的高度,比较左子树和右子树的高度,然后返回其中大的那个值加一,则求出数的高度。这里用递归实现! 2、算法描述 main ( )(主函数) 先构造一颗二叉树,初始化为空,用来存储所构造的二叉树,并输入一棵树的先序序列和中序序列,并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)(由先序序列和中序序列构造二叉树) 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素,则又有, 在前序序列中,紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树,而构造左子树问题其实跟构造整个二叉树问题一样,只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现! int Depth(BiTree T)(求树的深度) 当所给的参数T是NULL时,返回0。说明这个树只有一个叶子节点深度为0,当所给的参数不是NULL时,函数调用自己看看这个参数的左分支是不是NULL,
#include
实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数,建一个顺序栈或链式栈,并完成下列操作: (1)初始化栈; (2)判栈为空; (3)出栈; (4)入栈。 算法设计分析 (一)数据结构的定义 struct stackNode{ int data; struct stackNode *nextPtr; }; typedef struct stackNode listStact; typedef listStact *stackNodePtr; (二)总体设计 程序由主函数、入栈函数,出栈函数,删除函数判官是否为空函数和菜单函数组成。 (1)主函数:调用各个函数以实现相应功能
(三)各函数的详细设计: Function1: void instruct() //菜单 (1):使用菜单显示要进行的函数功能; Function2:void printStack(stackNodePtr sPtr) //输出栈 (1):利用if判断栈是否为空; (2):在else内套用while(头指针不为空条件循环)循环输出栈元素; Function3:void push(stackNodePtr *topPtr,int value //进栈 (1):建新的头指针; (2):申请空间; (3):利用if判断newPtr不为空时循环进栈 (4):把输入的value赋值给newPtr,在赋值给topPtr,再指向下一个位置; Function4:int pop(stackNodePtr*topPtr) //删除 (1):建新的头指针newPtr; (2):利用if判断newPtr是否为空,再删除元素。 (3):把topPtr等于newPtr,把头指针指向的数据赋值给topValue,输出要删除的数据值,头指针指向下一个位置,并清空newPtr; (4):完成上述步骤后,return toPvalue,返回;
详解堆栈的几种实现方法——C语言版 基本的抽象数据类型(ADT)是编写C程序必要的过程,这类ADT有链表、堆栈、队列和树等,本文主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈(stack)的显著特点是后进先出(Last-In First-Out, LIFO),其实现的方法有三种可选方案:静态数组、动态分配的数组、动态分配的链式结构。 静态数组:特点是要求结构的长度固定,而且长度在编译时候就得确定。其优点是结构简单,实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制,适用于知道明确长度的场合。 动态数组:特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活,缺点是由此会增加程序的复杂性。 链式结构:特点是无长度上线,需要的时候再申请分配内存空间,可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件,里面包含了各个方案下的函数原型,放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码: [cpp]view plaincopy 1./* 2.** 堆栈模块的接口 stack.h 3.*/ 4.#include
C语言用栈实现进制转换 #include
使用C++中STL的stack,只有C++中有,C标准库没有STL。 程序:(单整数) #include
题目: 实现顺序栈的各种基本运算,并在此基础上设计一个主程序完成如下功能: (1) 初始化栈S; (2) 判断栈S是否为空; (3) 依次使元素a, b, c, d, e进栈; (4) 判断栈S是否为空; (5) 输出栈的长度; (6) 输出从栈顶到栈底元素; (7) 输出出栈序列; (8) 判断顺序栈S是否为空; (9) 释放栈 代码; #include
{ return(s->top==-1); } //进栈 int Push(SqStack *&s,ElemType e) { if(s->top==MaxSize-1) return 0; s->top++; s->data[s->top]=e; return 1; } //出栈 int Pop(SqStack *&s,ElemType &e) { if(s->top==-1) return 0; e=s->data[s->top]; s->top--; return 1; } //取出栈顶元素 int GetTop(SqStack *s, ElemType &e) { if(s->top==-1) return 0; e=s->data[s->top]; return 1; } //显示栈中元素 void DispStack(SqStack *s) { int i; for(i=s->top;i>=0;i--) printf("%c ",s->data[i]); printf("\n"); } int main() { ElemType e; SqStack *s; printf(" 初始化栈s\n ");
数据结构与算法实验报告
基于栈的C语言迷宫问题与实现 一.问题描述 多年以来,迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是,老鼠过迷宫问题就此产生,这是一个很有趣的计算机问题,主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门,一个叫做入口,另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁,对前进方向形成了多处障碍,在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题,即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示,0表示能通过,1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫,编写算法,寻求一条从右下角[m,n] 出去的路径。下图是一个迷宫的示意图: 入口 出口
迷宫示意图 二.算法基本思想 迷宫求解问题是栈的一个典型应用。基本算法思想是:在某个点上,按照一定的顺序(在本程序中顺序为上、右、下、左)对周围的墙、路进行判断(在本程序中分别用1、0)代替,若周围某个位置为0,则移动到该点上,再进行下一次判断;若周围的位置都为1(即没有通路),则一步步原路返回并判断有无其他通路,然后再次进行相同的判断,直到走到终点为止,或者确认没有任何通路后终止程序。 要实现上述算法,需要用到栈的思想。栈里面压的是走过的路径,若遇到死路,则将该位置(在栈的顶层)弹出,再进行下一次判断;若遇到通路,则将该位置压栈并进行下一次判断。如此反复循环,直到程序结束。此时,若迷宫有通路,则栈中存储的是迷宫通路坐标的倒序排列,再把所有坐标顺序打印后,即可得到正确的迷宫通路。 三.程序具体部分的说明 1.迷宫的生成 根据题目的要求,迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1,以表示边界。 2.栈的C语言实现 为了实现栈的功能,即清空、压栈、弹出、返回栈顶元素,在程序中编写了相应的函数。 MakeNULL 清空栈 Push 将横、纵坐标压栈 Topx 返回栈顶存储的横坐标 Topy 返回栈顶存储的纵坐标 Pop 弹出栈顶元素 3.具体的判断算法
/////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include
#define_CRT_SECURE_NO_WARNINGS #include
#include
stack.h #ifndef _STACK_H_ #define _STACK_H_ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 // 栈储存空间的初始分配量 #define STACKINCREMENT 10 // 储存空间分配增量 typedef int Status typedef char SElemType typedef struct { SElemType *base;// 储存数据元素的数组 SElemType *top; // 栈顶指针 int stacksize; // 当前分配的栈空间大小,以sizeof(SElemType)为单位 }SqStack;
//** 构造一个空栈 Status InitStack(SqStack *S); //** 销毁栈 Status DestroyStack(SqStack *S); //** 栈是否为空 Status StackEmpty(SqStack *S); //** 入栈 Status Push(SqStack *S,SElemType e); //**取栈顶 SElemType GetTop(SqStack *S); //** 出栈 SElemType Pop(SqStack *S); //** 栈长度 int StackLength(SqStack *S);
//** 遍历 Status StackTraverse(SqStack *S,Status( *visit)(SElemType)); Status visit(SElemType e); #endif stack.c #include
实验报告 课程名称:数据结构 年级班级:计算机1712 学号姓名:查玉坤 2017116128 任课教师:康长青
实验目的 设计算法,把十进制整数转换为二至九进制之间的任一进制输出。 实验内容 代码如下: #include
for(i=S->top-1;i>=0;i--) printf("%d",S->base[i]); printf("\n"); } int main(){ int a,b,Jin,x,X,size; a=1; printf("输入一个十进制数\n"); scanf("%d",&x); X=x; printf("需要转化为多少进制数?\n"); scanf("%d",&Jin); sqstack S; initstack(&S); while(x>=Jin){ a=(x%Jin); b=(x/Jin); push(&S,a); x=b; } push(&S,x); printf("转换的%d进制数为:",Jin); list(&S); printf("验证:\n"); for(int i=S.top;i>0;i--){ if(i-1!=0) printf("%d*(%d^%d)+",S.base[i-1],Jin,i-1); else printf("%d*(%d^0)=%d\n",S.base[i-1],Jin,X); } return 0; }
实验3-1 链栈 [目的] 掌握链栈的实现和简单的应用。 [源代码] /**************************************************** @title: 数据结构实验 @name: <实验3-1> 栈的链式存储结构 @object: [实验目的] 采用链式存储结构实现栈的基本操作 [实验提示] 1. 在stack.h中实现栈的基本操作, 在链式存储结构中可是省去头结点。 2. 在dsp0301.cpp中编写适当的代码,进行测试 @include: stack.h [*] 栈的链式实现 @usage: 请查看"TO-DO列表",根据要求完成代码 @copyright: BTC 2004, Zhuang Bo @author: Zhuang Bo @date: 2004 @description: *****************************************************/ #include
while(!StackEmpty(s)) { Pop(s,x); printf("%4d",x); } //------------------------------------- // TODO (#1#): 其它测试程序 //------------------------------------- DestroyStack(s); //销毁栈 system("PAUSE"); return 0; } /* Name: 栈的链式实现 Copyright: Author: Date: Description: */ #ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED #include "ds.h" //for Status,OK ... #ifndef ElemType #define ElemType int /* 数据元素类型默认为int */ #define ELEMTYPE_TAG #endif /////////////////////////////////////////////////////////// //链栈的存储结构定义 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; typedef LinkList LinkStack; //链栈类型
C、C++语言实现的数据结构课程设计的计算器(堆栈) /* // 我真诚地保证: // 我自己独立地完成了整个程序从分析、设计到编码的所有工作。 // 如果在上述过程中,我遇到了什么困难而求教于人,那么,我将在程序实习报告中// 详细地列举我所遇到的问题,以及别人给我的提示。 // 我的程序里中凡是引用到其他程序或文档之处, // 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, // 我都已经在程序的注释里很清楚地注明了引用的出处。 // 我从未没抄袭过别人的程序,也没有盗用别人的程序, // 不管是修改式的抄袭还是原封不动的抄袭。 // 我编写这个程序,从来没有想过要去破坏或妨碍其他计算机系统的正常运转。 // <李雷阳> */ /******************************************************************** 用堆栈做的计算器程序* 创建者:李雷阳* 创建时间:2011.03.12 * 最后修改时间:2011.03.15 * /******************************************************************** /******************************************************************** 本程序功能:实现用堆栈处理计算表达式 具体内容: I: 如果算式里面有计算式不应该出现的字符,则将其智能略去 如:将(1.4a54+2f.6)*3.09s+4ff看成(1.454+2.6)*3.09+4 II: 检查括号是否匹配,如果匹配,再检查是否出现在合法位置 如:(8*(7-4)不匹配,以及65*(72+98)(70-45)匹配但是不合法 III: 检查计算数与计算符号的数量是否合格 如:+23-4* 、23-4*、+23-4 等等
C语言栈的指针实现 #include
Error("Echausted memory."); else return p; } //数据成员element 存储栈元素,next 是指向下一个结点的指针,函数NewStackNode()创建一个新结点 //用指针实现的链栈 typedef struct Istack *Stack; typedef struct Istack { slink top; //栈顶结点指针 }Lstack; /*top 是指向栈顶结点的指针*/ Stack StackInit() //将top 置为空指针,创建一个空栈 { Stack S = (Lstack *)malloc(sizeof*S); S->top = 0; return S; } int StackEmpty(Stack S) //简单的检测指向栈顶的指针top 是否为空指针 { return S->top == 0; } int StackFull(Stack S) //通过StackMenFull()为栈S试分配一个新结点,检测栈空间是否
堆和栈的区别 一、预备知识—程序的内存分配 一个由c/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。 3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放 4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放 5、程序代码区—存放函数体的二进制代码。 二、例子程序 这是一个前辈写的,非常详细 //main.cpp int a = 0; 全局初始化区 char *p1; 全局未初始化区 main() { int b; 栈 char s[] = "abc"; 栈 char *p2; 栈 char *p3 = "123456"; 123456\0在常量区,p3在栈上。 static int c =0;全局(静态)初始化区 p1 = (char *)malloc(10); p2 = (char *)malloc(20); 分配得来得10和20字节的区域就在堆区。 strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。 } 二、堆和栈的理论知识 2.1申请方式 stack: 由系统自动分配。例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间heap: 需要程序员自己申请,并指明大小,在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = (char *)malloc(10); 但是注意p1、p2本身是在栈中的。 2.2
#include