考点

4  线性结构与非线性结构

考试链接：

考点

4在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中

出现的几率为

30%，主要是以填空题出现的形式出现，分值为2分，此考点为识记内容。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类

型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：

（

1）有且只有一个根结点；

（

2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何

一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

 

 

疑难解答：空的数据结构是线性结构还是非线性结构？

一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数

据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

1.3

栈及线性链表

考点

5  栈及其基本运算

考试链接：

考点

5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，

分值为

2分，此考点为重点掌握内容，读者应该掌握栈的运算 。

1．栈的基本概念
栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一

端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删
除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈是按
照

"先进后出"或"后进先出"的原则组织数据的。

2．栈的顺序存储及其运算
用一维数组

S（1

∶m）作为栈的顺序存储空间，其中m为最大容量。

在栈的顺序存储空间

S（1

∶m）中，S（bottom）为栈底元素，S（top）为栈顶元素 。

top=0表示栈空；top=m表示栈满。

栈的基本运算有三种：入栈、退栈与读栈顶元素。
（

1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即

top加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后
一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈

"上溢"错误。

（

2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈

顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即

top减1）。当栈顶指针

为

0时，说明栈空，不可进行退栈操作。这种情况称为栈的

"下溢"错误。

（

3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除

栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为

0时，说明栈空，

读不到栈顶元素。

 

小技巧：

栈是按照

"先进后出"或"后进先出"的原则组织数据，但是出栈方式有多种选择，在考

题中经常考查各种不同的出栈方式。