若栈采用链式存储且仅设头指针，则 (37) 时入栈和出栈操作最方便。

2015年下半年上午试卷综合知识

第 37 题


知识点	栈指针
关键词	指针
章/节	常用数据结构

A. 采用不含头结点的单链表且栈顶元素放在表尾结点

B. 采用不含头结点的单链表且栈顶元素放在表头结点

C. 采用含头结点的单循环链表且栈顶元素随机存放在链表的任意结点

D. 采用含头结点的双向链表且栈顶元素放在表尾结点

相关试题队列、栈

第38题

2012年下半年

栈和队列的主要区别是（38）。

第35题

2019年上半年

某循环队列Q的定义中用front和rear两个整型域变量表示队列状态，其中front 指示队头元素的位置、rear指示队尾元素之后的位置（如下图所示，front的值为5、rear的值为1）。若队列容量为M（下图中..

第36题

2017年上半年

对于一个相始为空的栈，其入栈序列为1、2、3、…、n (n>3) ，若出栈序列的第一个元素是1，则出栈序列的第n个元素（）

知识点讲解

· 栈

· 指针

栈

栈的定义

栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（Last In First Out, LIFO）。

下图是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。

栈的出入示意图

栈的基本操作

栈的基本操作主要有以下6种。

.InitStack（&S）：初始化操作，构造一个空栈S。

.StackEmpty（S）：若栈S为空栈，返回1，否则返回0。

.Push（&S, e）：插入元素e为新的栈顶元素。

.Pop（&S,&e）：删除S的栈顶元素，并用e返回其值。

.GetTop（S,&e）：用e返回S的栈顶元素。

.ClearStack（&S）：将S清为空栈。

栈的顺序存储结构

栈的顺序存储用向量作为栈的存储结构，向量S表示栈，m表示栈的大小，用指针top指向栈顶位置，S[top]表示栈顶元素，当在栈中进行插入、删除操作时，都要移动栈指针；而当top=m-1时，则栈满，当top=-1时，表示栈空。同时为了避免浪费空间可以采用双栈机制，即向量的两端为栈底。

栈的顺序存储结构的C语言描述如下：

栈的说明如下。

.由于C语言的数组下标的范围从0至StackSize-1，初始化设置sq.top=-1。

.栈空条件为sq.top=-1，栈满条件为sq.top=StackSize-1。

.栈顶元素为sq.data[sq.top]。

.元素压栈的规则为：在栈不满时，先改变栈顶指针（top=top+1），再压栈。出栈时，在桟非空时，先取栈顶元素的值，再修改栈顶指针（top=top-1）。

.栈中元素的个数为当前栈顶指针加1。

在顺序栈上实现基本操作的有关函数如下。

1）初始化InitStack（SqStack *S）

2）判空StackEmpty(SqStack S）

3）压栈Push（SqStack *S, ElemType e）

4）出栈Pop（SqStack *S, ElemType *e）

5）取栈顶GetTop（SqStack *S, ElemType*e）

6）清栈ClearStack（SqStack *S）

栈的链式存储结构

栈的链式存储也叫链栈，我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链栈操作比较方便。

链栈的节点类型定义如下：

链栈的约定与说明如下。

.栈以链表的形式出现，链表（不带头节点）首指针为S，即栈顶为S，链表尾节点为栈底。

.初始化时，S=NULL（不带头节点）；S=（LStack *），malloc（sizeof（LStack）），S→next=NULL（带头节点）。

.栈顶指针的引用为S（不带头节点）或S→next（带头节点），栈顶元素的引用为S→data（不带头节点）或S→next→data（带头节点）。

.栈空条件为S==NULL（不带头节点）或S→next=NULL（带头节点）。

.进栈操作和出栈操作与单链表在开始节点的插入和删除操作一致。

对不带头节点的链栈，其基本操作函数如下。

1）初始化initstack（LStack *S）

2）压栈（入栈）push（LStack *S, ElemType x）

3）退栈（出栈）pop（LStack *S, ElemType *x）

4）读栈顶元素gettop（LStack *S, ElemType *x）

5）判栈空isempty（LStack *S）

栈的应用

栈具有广泛的应用，例如，求表达式的值及递归到非递归等。

1）表达式求值

在源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X=4+8×2-3；，其正确的计算结果应该是17，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X=12×2-3=24-3=21。这个结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先法。

2）递归到非递归

将一个递归算法转换为功能等价的非递归算法有很多方法，可以使用栈保存中间结果。其一般形式如下：

例如，求n！的递归函数如下：

使用转换成等价的非递归算法如下：

其中，st[top][0]用于存放n值，st[top][1]用于存放n！值，在初始时，设置st[top][1]为0，表不n！尚未求出。

指针

简单来说，指针是内存单元的地址，它可能是变量的地址、数组空间的地址，或者是函数的入口地址。存储地址的变量称为指针变量，简称为指针。指针是C语言中最有力的武器，能够为程序员提供极大的编程灵活性。

指针的定义

指针类型的变量是用来存放内存地址的，下面是两个指针变量的定义：

变量ptr1和ptr2都是指针类型的变量，ptr1用于保存一个整型变量的地址（称ptr1指向一个整型变量），ptr2用于保存一个字符型变量的地址（称ptr2指向一个字符变量）。

使用指针时需明确两个概念：指针对象和指针指向的对象。指针对象是明确命名的指针变量，如上例中的ptr1、ptr2；指针指向的对象是另一个变量，用“*”和指针变量联合表示，如上例中的整型变量*ptr1和字符变量*ptr2，由于上面的定义中未对ptr1和ptr2进行初始化，它们的初始值是随机的，也就是*ptr1和*ptr2可视为并不存在。

借助指针变量可以针对指定的地址进行操作，例如，设置地址为0x1234开始的存储空间存放一个整型变量的值0x5678，代码如下。

定义指针变量时需要在每个变量名前加“*”，如下：

指针的加减运算

对指针变量进行加减运算时，是以指针所指向的数据类型存储宽度为单位计算的。

例如，下面的指针p和s在进行加1运算时有不同的结果。

p+1实际上是按照公式p+1*sizeof（int）来计算的，s+1则是按照s+1*sizeof（char）进行计算。

空指针

标准预处理宏NULL（它的值为0，称为空指针常量）常用来表示指针不指向任何内存单元，可以把NULL赋给任意类型的指针变量，以初始化指针变量。例如：

需要注意：全局指针变量会被自动初始化为NULL，局部指针变量的初始值是随机的。编程时常见的一个错误是没有给指针变量赋初值。未初始化的指针变量可能表示了一个非法的地址，导致程序运行时出现内存访问错误，从而使程序异常终止。

“&”和“*”

“&”称为地址运算符，其作用是获取变量的地址。“*”称为间接运算符，其作用是获取指针所指向的变量。

例如，下面的语句“pa=&b；”执行后，变量pa就得到了b的地址（称为指针pa指向b），*pa表示pa指向的变量（也就是变量b）。

例如：

在上面的例子中，通过指针pa修改了变量b的值，本质上是对b的间接访问。在程序中通过指针访问数据对象或函数对象，提供了运算处理上的灵活性。

如果指针变量的值是空指针或者是随机的，通过指针来访问数据就是一种错误（在编译时报错，或者在运行时发生异常），下面的语句会产生一个运行时错误（vp可能表示了一个非法的地址，因此它所指向的对象*vp也是非法的）。

void*类型可以与任意的数据类型匹配。void指针在被使用之前，必须转换为明确的类型。例如：

指针与堆内存

在程序运行过程中，堆内存能够被动态地分配和释放，在C程序中通过malloc（或calloc、realloc）和free函数实现该处理要求。

例如：

在堆中分配的内存块的生存期是由程序员自己控制的，应在程序中显式地释放。例如：

注意：指针为空（指针值为0或NULL）时表示不指向任何内存单元，因此释放空指针没有意义。

因为内存资源是有限的，所以若申请的内存块不再需要就及时释放。如果程序中存在未被释放（由于丢失其地址在程序中也不能再访问）的内存块，则称为内存泄漏。持续的内存泄漏会导致程序性能降低，甚至崩溃。嵌入式系统存储空间非常有限，一般情况下应尽量采用静态存储分配策略。

指针与数组

通过指针访问数组元素

在C程序中，常利用指针访问数组元素，数组名表示数组在内存中的首地址，即数组中第一个元素的地址。可以通过下标访问数组元素，也可以通过指针访问数组元素。

例如：

数组arr的元素可以用*ptr、*（ptr+1）、*（ptr+2）、*（ptr+3）来引用。

数组名是常量指针，数组名的值不能改变，因此arr++是错误的，而ptr++是允许的。例如，下面的代码通过修改指针ptr来访问数组中的每个元素。

一般情况下，一个int型变量占用4个字节的内存空间，一个char型变量占用一个字节的空间，所以str是字符指针的话，str++就使str指向下一个字符；而整型指针ptr++则使ptr指向下一个int型整数，即指向数组的第二个元素。

可以用指针访问二维数组元素。例如，对于一个m行、n列的二维整型数组，其定义为

由于二维数组元素在内存中是以线性序列方式存储的，且按行存放，所以用指针访问二维数组的关键是如何计算出某个二维数组元素在内存中的地址。二维数组a的元素a[i][j]（ii][j]之前的元素所占空间形成的偏移量，概念上表示为a+（i×n+j）*sizeof（int），在程序中需要表示为（&a[0][0]+i×n+j）。

通过指针访问字符串常量

可将指针设置为指向字符串常量（存储在只读存储区域），通过指针读取字符串或其中的字符。例如，

不允许在程序运行过程中修改字符串常量。例如，下面代码试图通过修改字符串的第2个字符将“hello”改为“hallo”，程序运行时该操作会导致异常，原因是str指向的是字符串常量“hello”，该字符串在运行时不能被修改。

如果用const进行修饰，这个错误在编译阶段就能检查出来，修改如下：

指针数组

如果数组的元素类型是指针类型，则称之为指针数组。下面的ptrarr是一维数组，数组元素是指向整型变量的指针。

若需要动态生成二维整型数组，则传统的处理方式是先设置一个指针数组arr2，然后将其每个元素的值（指针）初始化为动态分配的“行”。

指针运算

在C程序中，对指针变量加一个整数或减一个整数的含义与指针指向的对象有关，也就是与指针所指向的变量所占用存储空间的大小有关。例如：

常量指针与指针常量

常量指针是指针变量指向的对象是常量，即指针变量可以修改，但是不能通过指针变量来修改其指向的对象。例如，

指针常量是指针本身是个常量，不能再指向其他对象。

在定义指针时，如果在指针变量前加一个const修饰符，就定义了一个指针常量，即指针值是不能修改的。

指针常量定义时被初始化为指向整型变量d。p本身不能修改（即p不能再指向其他对象），但它所指向变量的内容却可以修改，例如，*p=5（实际上是将d的值改为5）。

区分常量指针和指针常量的关键是“*”的位置，如果const在“*”的左边，则为常量指针，如果const在“*”的右边则为指针常量。如果将“*”读作“指针”，将const读作“常量”，内容正好符合。对于定义“int const *p；”p是常量指针，而定义“int* const p；”p是指针常量。

指针与函数

指针可以作为函数的参数或返回值。

指针作为函数参数

函数调用时，用指针作为函数的参数可以借助指针来改变调用函数中实参变量的值。以下面的swap函数为例进行说明，该函数的功能是交换两个整型变量的值。

若有函数调用swap（&x，&y），则swap函数执行后两个实参x和y的值被交换。函数中参与运算的值不是pa、pb本身，而是它们所指向的变量，也就是实参x、y（*pa与x、*pb与y所表示的对象相同）。在调用函数中，是把实参的地址传送给形参，即传送&x和&y，在swap函数中指针pa和pb并没有被修改。

如果在被调用函数中修改了指针参数的值，则不能实现对实参变量的修改。例如，下面函数get_str中的错误是将指针p指向的目标修改了，从而在main中调用get_str后，ptr的值仍然是NULL。