3．2 栈的顺序存储结构---顺序栈
栈的顺序存储结构简称顺序栈，它是运算受限的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置。
3．2．1 顺序栈的类型定义
类似于顺序表，用一维数组描述顺序栈中的数据元素的存储区域，并预设一个数组的最大空间。描述顺序栈的通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定是从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定两个常量：STACKCSL（存储空间初始分配量）和STACKZL（存储空间分配增量）。下面给出顺序栈的类型定义：
#include"stdlib.h"
#define STACKCSL 64 /*顺序栈存储空间初始分配量*/
#define STACKZL 8 /*顺序栈存储空间分配增量*/
typedef int ElemT ype; /*栈元素的数据类型定义，它可以是任意的，具体问题时
只需根据需要修改本定义语句即可*/
typedef struct
{ ElemT ype *top; /*栈顶指针*/
ElemT ype *bottom; /*栈底指针*/
int stacksize; /*当前已分配的存储空间，以栈元素为单位*/
}seqstack; /*顺序栈类型定义*/
seqstack *seqs; /*seqs是顺序栈类型指针*/
其中，stacksize指示栈的当前可使用的最大容量，初始化栈时，stacksize 的值等于STACKCSL，以后根据需要按分配增量STACKZL增长。
bottom是栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值等于NULL ，就意味着栈结构不存在。
top是栈顶指针，其初值指向栈底，也就是说top=bottom可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减一。所以，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
图3.2表示了栈顶指针top和顺序栈中数据元素之间的对应关系。
top
top
top
bottom bottom bottom
(a)空栈 (b) 元素5、8、1进栈 (c)元素1出栈 top
bottom bottom bottom
(d)元素4、3进栈 (e)元素3出栈 （f ）栈满
图3.2 栈顶指针与数据元素的关系 3．2．2 基本运算的实现
上述顺序栈的类型定义以及本小节将介绍的基本运算操作均放在文件
“seqstack.c ”中，使用时需要用命令：#include"seqstack.c"将其包含到具体的应用程序中去。
由于顺序栈的插入、删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多。在顺序栈上可以实现初始化栈、进栈、出栈、判栈空、取栈顶元素等几种基本运算，具体算法如下： 1． 初始化栈
该算法用于建立一个容量为STACKCSL 的空顺序栈ss 。建立时首先使用malloc 函数进行内存储区的分配，并将所分配的存储区的起始地址赋给栈底指针bottom 。
如果bottom不为空，说明分配成功，否则说明分配失败。成功时进行置空栈的操作，失败则退出。具体算法如下：
算法3.1
void initstack (seqstack *ss)
/*初始化一个顺序栈ss*/
{
ss->bottom=(ElemT ype *)malloc(STACKCSL*sizeof(ElemT ype));
if(!ss->bottom) { printf(“初始化栈失败”);return;};
ss->top=ss->bottom;
ss->stacksize= STACKCSL;
printf("初始化栈成功！");
}
2.进栈
该算法用于向顺序栈ss的栈顶插入一个元素x。算法首先判断栈是否已满，如果栈不满，就直接进行插入操作，否则就使用reallo c函数为该顺序栈再多分配增量STACKZL个元素的存储空间。如果分配成功，则修改栈顶指针top的位置和栈的容量stacksize，然后将元素x插入在栈顶位置。具体算法如下：
算法3.2
Void push(seqstack *ss, ElemType x)
/*将元素x插入顺序栈ss的顶部*/
{
if(ss->top-ss->bottom>=ss->stacksize) /*判断顺序栈是否已满*/
{
ss->bottom=(ElemT ype *)realloc(ss->bottom,(ss->stacksize+STACKZL)* sizeof(ElemT ype));
if(!ss->bottom) { printf(“栈容量扩充失败”);return;};
ss->top=ss->bottom+ss->stacksize;
ss->stacksize=ss->stacksize+STACKZL;
}
*ss->top=x;
ss->top++;
}
注意：如果在顺序栈已满的情况下再执行进栈操作时，就会发生“上溢出”的错误，必须进行栈容量的扩充。
3.判栈空
该算法用于判断顺序栈ss是否为空栈。算法以栈顶指针top和栈底指针bottom 是否指向同一位置为判断条件。这是因为对于栈来说，bottom永远指向栈底的位置，只有栈中没有元素时，top和bottom才可能指向同一个位置。具体算法如下：算法3.3
int stackempty(seqstack *ss)
/*判断顺序栈ss是否为空*/
{
if(ss->top==ss->bottom) return 1;
else
return 0;
}
4．出栈
该算法用于从顺序栈ss的栈顶删除一个元素，并将该元素的值通过x返回。算法进行时，首先判断栈是否为空，如果为空则是错误操作，不空则将栈顶指针向下移动一个位置。具体算法如下：
算法3.4
void pop(seqstack *ss，ElemType x)
/*从顺序栈ss中弹出栈顶元素置于x中*/
{
if(ss->top==ss->bottom) return ERROR;
ss->top--;
x=*ss->top;
}
需要注意的是:在该算法中，删去栈顶元素只要将栈顶指针减1即可，但该元素在下次进栈操作之前仍然是存在的，因此函数pop中应利用变量x返回被删元素。
另外，当顺序栈为空时，进行出栈操作会发生“下溢出”错误，应尽量避免。
5．取栈顶元素
将顺序栈ss的栈顶元素通过变量x返回。该算法与pop操作有所类似，只是此算法中栈顶指针不发生变化。
算法3.5
Void gettop (seqstack *ss, ElemType x)
/*取顺序栈ss的栈顶元素置于x中*/
{
if(ss->top==ss->bottom) exit(0);
x=*(ss->top-1);
}
在以上顺序栈的实现算法中，虽然设置了一个存储空间分配增量STACKZL用于堆栈容量不够时进行扩容调整，但是还是要面对“溢出”问题。尤其堆栈的使用非常广泛，经常出现在一个程序中需要同时使用多个堆栈的情形。为了避免出现溢出，需要为每个堆栈分配一个足够大小的空间。然而，要做到这一点往往是很不容易的，原因之一是各个堆栈所需要的空间大小很难估计；原因之二是由于堆栈是个动态结构，各个堆栈的实际大小在使用过程中都会发生动态变化，有时其中一个堆栈发生了上溢出，而其他各堆栈还保留很多可用空间。这就要求设法来解决多栈共享空间的问题。
3．2．3多栈共享空间
假设将多个堆栈顺序地映射到一个已知大小为m的存储空间上。如果只有两个堆栈来共享这m个存储空间，问题比较容易解决：只需要让第一个栈的栈底位于1处，
让另一个栈的栈底位于m 处。在使用堆栈时，两栈各自向中间伸展，仅当两个栈的栈顶指针相遇时才发生上溢出。这样，两个堆栈之间就做到了余缺互补，互相调剂，从而大大减少了空间的浪费现象，如图3.3所示。
图3.3 两个栈共享向量空间示意图
如果有两个以上的堆栈共享空间m ，问题的处理就要复杂一些。当然，如果事先知道每个堆栈可能存放的元素的最多个数，那也可以将这m 个空间根据各个堆栈的大小合理分配。但是，更多的情况是人们事先并不知道各个堆栈的最大容量。一个解决的办法就是：先将m 个存储空间平均分配给n 个（n>2）栈，每个栈占?m/n ? (不大于m/n 的最大整数)个存储空间，当其中任意一个堆栈发生上溢出而整个空间并未占满时，就要进行再调整。
进行调整操作时，首先设top[1..n]为n 个堆栈的栈顶指针的集合，top[i]为第i 个堆栈的栈顶指针；设bot[1..n+1]为n+1个栈底指针的集合，bot[i]为第i 个堆栈的栈底指针，位于第i 个堆栈实际栈底元素的前一个位置(为了方便对应描述，数组元素top[0]和bot[0]不使用)。其中设置第n+1个栈底指针bot[n+1]的目的是为了测试第n 个堆栈栈满与否。
初始状态如图3.4所示：
bot[i]=top[i]=（i-1）*（?m/n ?）（1≤i ≤n ） bot[n+1]=m 1 m
top[1] top[2] top[i] top[n] bot[n+1] bot[1] bot[2] bot[i] bot[n]
图3.4 多栈共享空间初始状态示意图
当没有发生溢出时，各个栈底指针的位置固定不动，只有栈顶指针随各栈的元素增减而移动。经过一段时间以后，整个空间中各个堆栈的状态可能会改变为如图3.5所示的情形。
bot[1] top[1] bot[2] top[2] bot[i] top[i] bot[n] top[n] bot[n+1]
图3.5 多栈共享空间一般状态示意图
很显然，表示第i个堆栈为栈空的条件是：top[i]=bot[i] （1≤i≤n），表示第i 个堆栈为栈满的条件是：top[i]=bot[i+1] （1≤i≤n）
在上述情况中，很容易出现“假溢出”的情况，也就是当用户想在第i个堆栈中插入一个新元素，此时第i个堆栈已满，而其他堆栈实际上可能还很空，整个存储空间可能还有剩余。要想有效利用其他堆栈的剩余存储空间，调整第i个堆栈空间，使得该新元素能够插入到第i个堆栈中，可以进行以下调整：
方法一：右移法。该方法在i≤j≤n中确定有可用空间的最小j，也就是找到第i个栈右边的第1个有可用空间的栈j（此时必然有top[j] 方法二：左移法。该方法相对于右移法而言，当第i个栈的右边不再有可用空间时，就在1≤j≤i中确定有可用空间的最大j，也就是找到第i个栈左边的第1个有可用空间的栈j，然后将第j+1、j+2……第i个栈的所有元素连同栈底指针与栈顶指针都左移一个位置，使得第i个栈空出一个空间。 只有当所有的堆栈都找过以后，都没有发现自由空间，这时才说明整个空间全部被占用，真正发生了溢出。 多个堆栈共享空间的优点之一就是节省空间，但这种处理方法的弊病仍旧是要移动大量的数据元素，这也正是顺序存储结构固有的缺点。 3．2．4 典型应用举例 在计算机软件设计中，栈的应用非常广泛。子程序嵌套调用、递归的实现、中断的处理、表达式的计算等都是栈的实际应用。只要问题求解具有后进先出的天然特性，则其求解过程中必然需要利用“栈”。下面举例说明栈的应用。 例3.1数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其转换算法基于下列原理： N=(N div d)*d+N mod d （其中：div为整除运算， mod为求余数运算） 例如：（234）10=（11101010）2，其运算过程如下： N N div 2 N mod 2 234 117 0 117 58 1 58 29 0 29 14 1 14 7 0 7 3 1 3 1 1 1 0 1 现需设计一算法实现十进制到二进制的数制转换：对于输入的任意一个非负十进制整数，打印输出与其等值的二进制数。由于上述计算过程是从低位到高位顺序产生二进制的各个数位，而打印输出，一般来说应从高位到低位进行，刚好和计算过程相反，这与栈的先进后出的特性相吻合。因此，若将计算过程中得到的二进制 数的各位顺序进栈，则按出栈序列打印输出的就是与输入对应的二进制数。 算法3.6 #include"seqstack.c" void conversion(seqstack *ss) /*十进制到二进制的数制转换*/ { initstack (ss); /*构造空栈*/ scanf("请输入十进制非负整数：%d"，&n); while(n) { push(ss,n%2); /*余数入栈*/ n=n/2; /*“商”继续运算*/ } printf("\n对应的二进制数为：")； while(!stackempty(ss)) /* 依次弹出栈中元素 */ { pop(ss,a); printf("% d",a); } } 若将算法3.6改为主程序main(),则该程序的执行结果为： 请输入十进制非负整数：234 对应的二进制数为：11101010 这是利用栈后进先出特性的最简单例子。类似还可解决如“从键盘上输入一批整数，然后按照相反次序打印出来”一类的问题。 例3.2括号匹配 括号匹配问题在高级语言编译系统中是一个基本的检测操作,它的检测方法就是通过堆栈的应用实现的。 在一个程序段中，若允许出现的括号有三种：“{}”、“[]”、“（）”，则它们必须成对出现，允许嵌套，但不能有交叉现象出现。 例如：{{[（）]}}是正确的， {[{（}}]和（{}[）]都是错误的。 利用堆栈实现检测方法的算法描述如下： 算法3.7 先建立左括号栈，然后从左至右扫描该程序段： 1．若扫描到左括号，将该左括号进栈； 2．若扫描到右括号，则对左括号栈的栈顶元素进行考察： 1）二者相匹配，栈顶括号元素出栈； 2）二者不匹配，则停止扫描该程序段； 3．以上情况1），则继续扫描程序段，直至全部扫描完； 4．最后考察左括号栈： 1）栈为空，且该程序段已扫描完，则该程序段中括号均相匹配； 2）否则，此程序段中有不匹配的括号。 下面我们来看两个实例： 1）{{[（）]}} 该实例中各个括号进、出栈的情况如图3.6所示： 其扫描过程如下： a）依次扫描到“{{[（”，则分别进栈； b）扫描到“）”，与栈顶的“（”相匹配，则“（”出栈； c）扫描到“]”，与栈顶的“[”相匹配，则“[”出栈； d）扫描到“}”，与栈顶的“{”相匹配，则“{”出栈； e）扫描到“}”，与栈顶的“{”相匹配，则“{”出栈； f）扫描结束，左括号栈为空。 可以判断：该程序段的括号均匹配。 2）（{}[）] 该实例中各个括号进、出栈的情况如图3.7所示： a）依次扫描到“（{”，则分别进栈； b）扫描到“}”，与栈顶的“{”相匹配，则“{”出栈； c）扫描到“[”，进栈； d）扫描到“）”，与栈顶的“[”不匹配，则停止扫描； f）扫描未结束，左括号栈不为空。 可以判断：该程序段的括号不匹配。 例3.3表达式求值 表达式的计算与括号匹配一样是程序设计语言编译系统中的一个基本问题，它的实现是堆栈应用的一个典型实例。 任何一个表达式都是由运算对象（也称操作数）和运算符（也称操作符）以及分界符组成的。这些运算对象、运算符以及分界符称为单词。根据运算符的类型，通常可以把表达式分为逻辑表达式、关系表达式和算术表达式三类。为了简化问题而又不失一般性，这里仅仅讨论只含二元运算符的算术表达式的求值问题，读者不难将它推广到一般表达式。 先要说明的是，通常在数学中看到的或者出现在程序中的算术表达式都称为中缀表达式，中缀表达式中的运算符一般出现在两个运算对象之间（单目运算符除外）。例如， a-(b+c*d)/e 在计算机系统内多遍处理的编译程序中，在处理这样的表达式并将其生成一系列机器指令或者直接求值之前，往往先将它变换成另外一种形式，即后缀表达式形式。顾名思义，后缀表达式就是表达式中的运算符出现在运算对象之后。在后缀表达式中，不存在括号，也不存在运算符优先级的差别，计算过程完全按运算符出现的先后次序进行；整个计算过程仅需一遍扫描便可完成，比中缀表达式的计算简单得多。例如，前面给出的中缀表达式写成后缀形式为： abcd*+e/- 这样处理的好处是：编译程序处理表达式时，首先从左至右一次扫描后缀表达式的各个单词，如果读到的一个单词为运算符，就对该运算符前面的两个运算对象施以该运算符所代表的运算；然后将结果存入一个临时单元T i中（i≥1），并作为一个新的运算对象重复进行上述过程，直到表达式处理完毕。例如：abcd*+e/-的运算过程如表3.1所示。 表3.1 后缀表达式的计算过程 从上面的讨论知道，后缀表达式之所以容易被编译程序处理，是由于它具有以下特点： （1）后缀表达式中不出现括号； （2）后缀表达式与中缀表达式的运算对象的先后次序相同，只是所读到的运算符先后次序可能有所改变。 正是由于后缀表达式具有以上特点，所以，处理时不必考虑运算符的优先关系。在具体的处理过程中，需要设置一个堆栈，用来保存已经读到的运算对象。也就是说，从左至右依次扫描后缀表达式，每读到一个运算对象就将其压入堆栈；每读到一个运算符，就从堆栈中取出相应的运算对象进行该运算符所代表的操作，并把运 算结果作为一个新的运算对象压入堆栈。表达式最后的计算结果就是位于堆栈中栈顶的值。 综上所述，表达式的值的计算过程需要经过两个步骤：一是把中缀表达式变换为后缀表达式；二是根据后缀表达式产生计算表达式的机器指令序列。相对而言，第二个步骤较为简单些，我们先讨论实现第二个步骤的算法。 算法3.8 #include"seqstack.c" Void evalution() { char c; int op1,op2,c1,result,x=0,val(); seqstack *opd; /*栈opd存放操作数及计算结果*/ initstack(opd); /*初始化栈*/ printf(“请从键盘输入后缀表达式：”）； while(c=getchar()!='\n') /*后缀表达式未结束*/ { if(c==' ') continue; /*空格则读入下一个字符*/ if((c>='0')&&(c<='9')) /*若读入字符是数字*/ { c1=c-'0'; /*将字符数字转化为数值数字*/ push(opdata(opd,c1);} /*将该数值数字作为操作数进栈*/ else if((c=='+')||(c=='-')||(c=='*')||(c=='/'))/*若读入字符为运算符*/ { op1=pop(opd,x); op2=pop(opd,x); result=val(c,op2,op1);/*两操作数出栈，进行运算*/ push(opd,result);/*运算结果进栈*/ } } printf(" 该后缀表达式的值为：%d"，pop(opd,x));/*计算完后栈中只剩计算结果*/ } 算法3.9 int val(char tag, int a1, int a2) /*函数val进行算术运算*/ { switch(tag) { case '+': return (a1+a2);break; case '-': return (a1-a2);break; case '*': return (a1*a2);break; case '/': return (a1/a2); } } 下面来讨论如何把中缀表达式变换为后缀表达式。 首先，已知中缀表达式与后缀表达式的运算对象的排列次序完全相同，只是运算符按某种规则可能改变了位置。根据这个特点，可以从左到右依次扫描中缀表达式，每读到一个运算对象就把它作为后缀表达式的一部分输出。关键在于处理运算符时要事先设置一个运算符栈，每读到一个运算符，就将其与栈顶位置的运算符的优先级进行比较，以决定所读到的运算符是该进栈还是该将栈顶位置的运算符作为后缀表达式的一部分输出。 表3.2给出的是+、-、*、/四则运算以及圆括号的优先关系。其中，“#”为中缀表达式的左、右分界符，符号opt1代表栈顶运算符，opt2代表当前扫描到的运算符。该表格给出的优关系不外乎三种：>、<、=，表中的空格处表示无优先关系。 表3.2 优先关系表 根据这个优先关系表，每读到中缀表达式中的一个运算符opt2,先将opt2与opt1的优先级进行比较，如果opt2>opt1,则将opt2进栈，然后读下一个单词；如果opt2 算法3.10 #include"seqstack" zztohz() { /*设opt为运算符栈，op为运算符集合，super（）为运算符优先比较函数*/ seqstack *opt; char c,x; initstack(opt); push(opt,'#'); c=getchar(); while(c!='#' || gettop(opt)!= '#') { if(!In(c,op)) { putchar(c); /*不是运算符就将其作为后缀表达式的部分输出*/ c=getchar（）; } else switch(super(gettop(opt),c) { case '<': push(opt,c);/*栈顶元素优先权低，当前运算符进栈*/ c=getchar(); break; case '=':pop(opt,x);/*优先级相等则将栈中括号出栈*/ c=getchar(); break; case '>':putchar(pop(opt,x));/*栈顶元素优先权高，栈顶元素 退栈并输出为后缀表达式*/ break; } } } 利用上述算法，中缀表达式a-(b+c*d)/e转换成后缀表达式的过程如表3.3所示：表3.3 中缀表达式转换为后缀表达式示例 （1）开始界面（2）初始化线性表 3.插入:下面是插入第一个元素的图（3），插入后再一次插入其他元素，最终插完元素，见图（4） (4)插入最后一个元素（第五个） 5.取栈顶元素，如图（ (5)删除栈顶元素（6）取栈顶元素 6.置空顺序栈，如图（7） （7）置空顺序表 7. 数值转换（将一个十进制数转换为任意进制） 三进制数2220。 （9）回文数判断a （10）回文数判断b 实验结论：实验成功 八．我对本次实验的总结： 1.通过对该程序的调试和运行，使的对顺序栈的功能及其构成有了进一步的了解。 2.通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中 可以重新熟悉函数在编程中的设置方法 void InitStack(SqStack *p) {if(!p) printf("内存分配失败!"); p->top =-1; } /*入栈*/ void Push(SqStack *p,ElemType x) {if(p->top 第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是 遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0 三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作 五、代码： #include 实验三栈和队列 3.1实验目的： （1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现； （2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。 3.2实验要求： （1）复习课本中有关栈和队列的知识； （2）用C语言完成算法和程序设计并上机调试通过； （3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 3.3基础实验 [实验1] 栈的顺序表示和实现 实验内容与要求: 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 参考程序: #include 1.上机题目 顺序栈的建立及基本操作实现，要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。 2.需求分析 本次程序设计要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。 （1）输入形式为从键盘输入，用户根据界面的提示从键盘直接输入所对应的数即可。输入的值为正数或字符，用户输入其他的数据会产生 错误。 （2）系统按照用户输入的数据类型，将会把相应的输出结果显示到界面上。 （3）测试：按照提示建立一个单链表，按照提示进行初始化、入栈、出栈、栈的清空、栈中元素计数等操作测试程序是否正确。 3.概要设计 （1）数据结构定义： #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; typedef char SElemType; // 定义栈元素类型 (2)画出各模块之间的调用关系图。 用伪码给出主程序的主要处理过程。 4.详细设计 InitStack（&S)构造一个空栈。 Push(&S，e)插入元素为e的新栈顶。 Pop（&s，&e）删除栈顶元素用e返回 ClearStack(&s)清空栈 StackEmpty(s)栈是否为空 GetTop(s,&e)用e返回s的栈顶元素 StackLength(&s)计算栈长度 (2)主要伪代码： 插入元素为e的新栈顶。 Status Push(SqStack &S){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc(S.base, (S.stacksize+=STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; 栈的顺序表示和实现 2.2基础实验 2.2.1实验目的 （1）掌握栈的顺序表示和实现 （2）掌握栈的链式表示和实现 （3）掌握队列的顺序表示和实现 （4）掌握队列的链式表示和实现 2.2.2实验内容 实验一：栈的顺序表示和实现 【实验内容与要求】 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能: （1）初始化顺序栈 （2 ）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 【知识要点】 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1 ，栈满时，不能入栈;否则岀现空间溢岀，引起错误，这种现象称为上溢。 岀栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top （通常称top为栈顶指针）来指示当前栈顶位置 【实现提示】 /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void lnitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack)/* 申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ 第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 实验四、栈的顺序和链式存储的表示和实现 实验目的： 1.熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。 2.掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。 实验内容： 1.栈的顺序表示和实现 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。 （1）初始化顺序栈 （2）插入一个元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 #include elemtype stack[MAXNUM]; int top; }sqstack; //初始化顺序栈 void initstack(sqstack *p) { if(!p) printf("error"); p->top=-1; } //入栈 void push(sqstack *p,elemtype x) { if(p->top elemtype pop(sqstack *p) { elemtype x; if(p->top!=0) { x=p->stack[p->top]; printf(" 以前的栈顶数据元素%d 已经被删除!\n",p->stack[p->top]); p->top=p->top-1; return(x); } else { printf("栈为空\n"); return(0); } } //获取栈顶元素 elemtype gettop(sqstack *p) { elemtype x; #include 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（ B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（ D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶 实验三栈的顺序和链式存储的表示和实现 实验目的： 1.熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。 2.掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。 实验内容： 1.栈的顺序表示和实现 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。 （1）初始化顺序栈 （2）插入一个元素 （3）删除栈顶元素 （4）取栈顶元素 （5）便利顺序栈 （6）置空顺序栈 #include //获取栈顶元素 elemtype gettop(sqstack *p) { elemtype x; if(p->top!=-1) { x=p->stack[p->top]; return x; } else { printf("Underflow!\n"); return 0; } } //遍历顺序栈 void outstack(sqstack *p) { int i; printf("\n"); if(p->top<0) printf("这是一个空栈！\n"); for(i=p->top;i>=0;i--) printf("第%d个数据元素是：%6d\n",i,p->stack[i]); } //置空顺序栈 void setempty(sqstack *p) { } //主函数 main() { sqstack *q; int y,cord; elemtype a; 数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算 ?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include 淮海工学院计算机科学系实验报告书 课程名：《数据结构》 题目：线性表数据结构实验 班级：^ ^ 学号：^ ^ 姓名：^ ^ 线性数据结构算法实现与应用报告要求 1目的与要求: 1）掌握栈与队列的数据类型描述及特点； 2）掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7）认真书写实验报告，并按时提交。 2 实验内容或题目 以下题目学生根据自己的兴趣和能力可选作一道作为实验题目： 1）根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作（出栈和入栈等）； 2）根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作（出入队列等）； 3）参考书上表达式求值例题，应用栈的基本操作实现带括号表达式求值运算及其进出栈模拟过程（给出程序执行过程中栈的变化过程）； 4）阅读P83栈与递归的实现一节内容和3阶汉诺塔问题。使用栈数据结构解决3阶汉诺塔问题，编写程序并模拟栈及其汉诺塔的搬运过程（给出程序执行过程栈的变化过程与圆盘的搬动状态）。 5）其它实际应用举例(如打印杨辉三角形)。 3 实验步骤与源程序 选1） 顺序栈 #include LRU算法的顺序栈实现 一、需求分析 1、本演示程序是对页面置换算法中的最近最久未使用的置换算法（LRU）的顺序栈的实现，并计算缺页率。 2、演示程序以用户和计算机对话的方式执行，即在计算机终端上显示“提示信息”下，用户可输入模拟缓存的大小（即cache值），并输入由文件的模拟页面流，最终进行计算缺页率。 3、最后对结果做出简单分析，包括对各组数据得出的结果的简单分析和对算法的进一步改进给予解释。 二、概要设计 1、本程序中顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={a[i]|a[i]∈ElemSet,i=1,2,3,..,n,n>0} 数据关系: R1={ { If来解决在栈未满的情况 Else if 来解决栈已满的情况 } } 输出缺页率 } 三、详细设计 根据LRU算法的特点，进行栈的顺序实现，并在实现在c源文件中/*------------------------------基本操作的函数原型-----------------------------*/ #define STACK_INIT_SIZE 100 //栈的初始化大小 typedef int ElemType; typedef struct{ //顺序栈的结构定义 ElemType *base; ElemType *top; int stacksize; //栈的大小 }SqStack; InitStack(SqStack *s) //初始化栈 { s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); //if(!s->base) exit(0); s->top=s->base; s->stacksize=STACK_INIT_SIZE; } Push(SqStack *s,ElemType e) //元素压入栈顶 { //本算法忽略栈满追加栈元素的情况，因为不会发生 *(s->top)=e; s->top++; } Pop(SqStack *s,int *p) //删除栈中某个元素，并一定为栈底 { while(p栈的顺序表示和实现
目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)
顺序栈的基本操作讲解
栈的操作(实验报告)
数据结构上机顺序栈建立
用顺序结构表示栈并实现栈地各种基本操作
完整版数据结构习题集第3章栈和队列
数据结构栈的基本操作,进栈,出栈
第三章+栈和队列(参考答案)
实验二栈队列的实现及应用
实验四、栈的顺序和链式存储的表示和实现
数据结构——顺序栈的基本操作
第3章 栈与队列习题参考答案
栈的顺序和链式存储的表示和实现
(完整word版)顺序栈基本操作实验报告
数据结构 顺序栈 链栈
LRU算法的顺序栈实现
相关主题
文本预览