沈阳建筑大学信息学院上机指导书-实验2

2.1 实验目的

1、理解并掌握栈的结构特点。

2、掌握栈先进后出的操作原则以及基本运算方法。

3、掌握队列的类型定义方法，理解和掌握循环队列解决假溢出的方法。

2.2 实验内容

2.2.1 栈的实验部分

1、实验准备

顺序栈的基本运算包括：初始化顺序栈、进栈、出栈等操作。下面是顺序栈基本运算的C程序实例，试比较顺序栈算法设计与程序的区别。要求阅读程序时给出函数具体执行的详细注释。

#include #include //变量的宏定义

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 //顺序栈的类型定义 typedef struct{ int *base; int *top; int stacksize; } sqstack; //初始化顺序栈

int initstack(sqstack *s) {

s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); s->top=s->base;

s->stacksize=STACK_INIT_SIZE; return OK; }

//顺序栈进栈运算

void push(sqstack *s,int e)

{

if(s->top - s->base>=s->stacksize) {

s->base=(int*)realloc(s->base,

(s->stacksize+STACKINCREMENT)*sizeof(int)); if (!s->base) exit(-1);

s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; }

*(s->top++)=e; }

//顺序栈出栈运算

int pop(sqstack *s,int *e) {

if(s->top==s->base) return ERROR; *e=*(--s->top); return (*e); }

//完成各种运算测试的主程序

当顺序栈的基本运算函数设计好后，给出以下主程序调用这些基本操作函数，读者可以对照程序执行后的结果进行分析，进一步体会顺序栈的各种操作的实现过程。

int main() {

sqstack s; int n, m, e; initstack(&s);

system(\"CLS\"); //清DOS屏幕 scanf(\"%d %d\ while(n) {

push(&s,n%m); n=n/m; }

while(!(s.top==s.base)) {

pop(&s,&e); printf(\"%d\\n\ } return 0; }

2、实验设计

要求读者能够独立完成算法分析和程序设计，之后可以参考相应提示内容，分析算法的不足，以提高自己程序设计能力。

（1）编写程序，实现顺序栈如下基本运算：取栈顶元素、遍历顺序栈、置空顺序栈，并设计主程序完成各种运算。

提示：

① 顺序栈入栈时，首先判断栈是否为满，栈满的条件为：p->top==MAXNUM-1，栈满时，不能入栈；否则出现空间溢出，引起错误，这种现象称为“上溢”。

② 出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常将栈空作为一种控制转移的条件。

③ 注意：

（a）顺序栈中的元素用应该具有动态分配空间的功能。

（b）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置。

（2）编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：初始化链栈、链栈置空、入栈、出栈、取栈顶元素、遍历链栈。

提示：

① 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 ② 注意：

（a）链栈结构类型的定义应能在函数体中修改top指针本身。

（b）若要记录链栈中元素个数，可将元素个数属性放在链栈类型中定义。 （c）链栈中的结点是动态分配的，所以可以不考虑“上溢”。

2.2.2 队列的实验部分

1、实验准备

（1）理解顺序队列的类型定义：

#define QueueSize 100 //队列的容量 typedef struct sqQueue

{ ElemType data[QueueSize]; //保存队中的元素 int front, rear; //队头和队尾指针 } sqQueue;

（2）假设元素A、B、C、D依次有进队和出队的操作，则此顺序队列有如下几种状态： ① 空队列，sq.rear = sq.front = 0；

② 若某元素A进队后，sq.rear = 1，sq.front = 0；

③ 若后续3个元素B、C、D依次进队后，sq.rear = 4，sq.front = 0； ④ 若元素A出队后，sq.rear = 4，sq.front = 1； ⑤ 若元素B、C、D出队后，sq.rear = sq.front = 4。

2、实验设计

（1）编写程序，实现顺序队列的如下基本运算：初始化队列、建立顺序队列、入队、出队、判断队列是否为空、取队头元素、遍历队列，并设计主程序完成各种操作。

提示：

① 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

② 入队时，将新元素插入rear所指的位置，然后将rear加1。出队时将front加1并返回被删元素。

③ 顺序队列中的溢出现象：

“下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

“真上溢”现象：当队列满时，做进队列运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

“假上溢”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于存储空间的规模时，也可能由于尾指针已超越存储空间的上界而不能做入队操作。该现象称为“假上溢”现象。

④ 注意：

（a）当头尾指针相等时，队列为空。

（b）在非空队列里，队头指针始终指向队头元素，尾指针则指向队尾元素的下一位置。 （2）编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：初始化并建立链队列、入链队列、出链队列、遍历链队列。

提示：

① 队列的链式存储结构简称为链队列，是仅限制在表头删除和表尾插入的单链表。 ② 注意：

（a）和链栈类似，无须考虑判断队满的运算及队列上溢情况。

（b）在出队算法中，一般只需修改队头指针。但当原队列中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。

（c）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。

2.3 实验要求

1、写出上述算法的完整程序，并上机调试运行。 2、算法要具有较好的健壮性。 3、记录运行结果及程序清单。

2.4实验拓展

1、在2.2.1节，栈的实验设计第1题中，试述：

（1）读栈顶元素的算法与退栈顶元素的算法有何区别？

（2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？

2、在2.2.1节，栈的实验设计第2题中，试述：

（1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？

（2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？

3、比较2.2.1节和2.2.2节实验设计部分栈和队列的基本操作，试述： （1）栈和队列的共同点和不同点。它们为什么属于线性表？

（2）在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，但事实上队列中可能还有空位置。此时若有元素入列，就会发生“假溢出”。如何解决这个问题？

4、在2.2.2节，队列的实验设计第2题中，试问：

（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？

（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？

5、编写程序实现数制转换，将一个非负的十进制数N转换成八进制数据M，将其调试通过。在此基础上修改程序，实现十进制数N向r进制（2或8或16）的转换。

提示：将十进制数N转换为r进制的数，其转换方法利用辗转相除法。算法思想如下：当N>0时，重复下面步骤：

（1）若N不等于0，则将N%r压入栈s中，执行（2）；若N等于0，将栈s的内容依次出栈，算法结束。 （2）用N/r代替N。

6、已知一个队列，其结点的数据域为一个自然数。输入一个自然数n，与队头结点数据配对。如果相等，则删除队头结点；如果不相等或队列为空，则把n插入队列中。如果输入数为0，则结束处理。

提示：把输入的数存入n。先判断n为何值，若n=0，就终止算法；否则判断队列是否为空，若为空则执行队列插入操作；若队列不为空，则与队头结点比较，比较相等，则执行队列的删除操作；否则执行插入操作。重复此过程，直到输入0时结束。