实验二 栈和队列(基本操作)

1、实验目的：

（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作

在栈的顺序存储结构和链式存储结构上的实现；

（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基

本操作在队列的顺序存储结构和链式存储结构上的实现。

2、实验要求：

（1） 复习课本中有关栈和队列的知识；

（2） 用C语言完成算法和程序设计并上机调试通过；

（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括

时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

3、实验内容

[实验1] 栈的顺序表示和实现

实验内容与要求:

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈

分析:

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

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

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

（1）顺序栈中元素用向量存放

（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

参考程序:

#include #include #define MAXNUM 20

1

#define ElemType int

/*定义顺序栈的存储结构*/ typedef struct

{ ElemType stack[MAXNUM]; int top; }SqStack;

/*初始化顺序栈*/

void InitStack(SqStack *p) { if(!p) printf(\"Eorror\"); p->top=-1; }

/*入栈*/

void Push(SqStack *p,ElemType x) { if(p->toptop=p->top+1; p->stack[p->top]=x; } else printf(\"Overflow!\\n\"); }

/*出栈*/

ElemType Pop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; printf(\"以前的栈顶数据元素%d已经被删除！\\n\ p->top=p->top-1; return(x); } else { printf(\"Underflow!\\n\"); return(0); } }

/*获取栈顶元素*/

ElemType GetTop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; return(x); } else { printf(\"Underflow!\\n\");

2

return(0); } }

/*遍历顺序栈*/

void OutStack(SqStack *p) { int i; printf(\"\\n\"); if(p->top<0) printf(\"这是一个空栈！\"); printf(\"\\n\"); for(i=p->top;i>=0;i--) printf(\"第%d个数据元素是：%6d\\n\}

/*置空顺序栈*/

void setEmpty(SqStack *p) {

p->top= -1; }

/*主函数*/ main()

{ SqStack *q; int y,cord;ElemType a; do{ printf(\"\\n\"); printf(\"第一次使用必须初始化！\\n\"); printf(\"\\n\"); printf(\"\\n 主菜单 \\n\"); printf(\"\\n 1 初始化顺序栈 \\n\"); printf(\"\\n 2 插入一个元素 \\n\"); printf(\"\\n 3 删除栈顶元素 \\n\"); printf(\"\\n 4 取栈顶元素 \\n\"); printf(\"\\n 5 置空顺序栈 \\n\"); printf(\"\\n 6 结束程序运行 \\n\"); printf(\"\\n--------------------------------\\n\"); printf(\"请输入您的选择( 1, 2, 3, 4, 5,6)\"); scanf(\"%d\ printf(\"\\n\"); switch(cord) { case 1: { q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q); OutStack(q); }break; case 2:

3

{ printf(\"请输入要插入的数据元素：a=\"); scanf(\"%d\ Push(q,a); OutStack(q); }break; case 3: { Pop(q); OutStack(q); }break; case 4: { y=GetTop(q); printf(\"\\n栈顶元素为：%d\\n\ OutStack(q); }break; case 5: { setEmpty(q); printf(\"\\n顺序栈被置空！\\n\"); OutStack(q); }break; case 6: exit(0); } }while (cord<=6); }

[实验2] 栈的链式表示和实现

实验内容与要求:

编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化链栈 （2）链栈置空 （3）入栈 （4）出栈

（5）取栈顶元素 （6）遍历链栈

分析:

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

（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身

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

4

参考程序:

#include \"stdio.h\" #include \"malloc.h\" #include \"stdlib.h\" typedef int Elemtype; typedef struct stacknode { Elemtype data; stacknode * next; }StackNode; typedef struct { stacknode * top; //栈顶指针 }LinkStack; /*初始化链栈*/

void InitStack(LinkStack * s) { s->top=NULL; printf(\"\\n已经初始化链栈！\\n\"); }

/*链栈置空*/

void setEmpty(LinkStack * s) { s->top=NULL;

printf(\"\\n链栈被置空！\\n\"); }

/*入栈*/

void pushLstack(LinkStack * s, Elemtype x) { StackNode * p; p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。 p->data=x; p->next=s->top; //由于是在栈顶pushLstack，所以要指向栈顶。 s->top=p; //插入 }

/*出栈*/

Elemtype popLstack(LinkStack * s) { Elemtype x; StackNode * p; p=s->top; //指向栈顶 if (s->top ==0) { printf(\"\\n栈空，不能出栈！\\n\"); exit(-1); } x=p->data; s->top=p->next; //当前的栈顶指向原栈的next free(p); //释放 return x; }

5

/*取栈顶元素*/

Elemtype StackTop(LinkStack *s) { if (s->top ==0) { printf(\"\\n链栈空\\n\"); exit(-1); } return s->top->data; }

/*遍历链栈*/

void Disp(LinkStack * s)

{ printf(\"\\n链栈中的数据为：\\n\"); printf(\"=======================================\\n\"); StackNode * p; p=s->top; while (p!=NULL) { printf(\"%d\\n\ p=p->next; } printf(\"=======================================\\n\"); }

void main()

{ printf(\"================= 链栈操作=================\\n\\n\"); int i,m,n,a; LinkStack * s; s=(LinkStack *)malloc(sizeof(LinkStack)); int cord; do{ printf(\"\\n\"); printf(\"第一次使用必须初始化！\\n\"); printf(\"\\n\"); printf(\"\\n 主菜单 \\n\"); printf(\"\\n 1 初始化链栈 \\n\"); printf(\"\\n 2 入栈 \\n\"); printf(\"\\n 3 出栈 \\n\"); printf(\"\\n 4 取栈顶元素 \\n\"); printf(\"\\n 5 置空链栈 \\n\"); printf(\"\\n 6 结束程序运行 \\n\"); printf(\"\\n--------------------------------\\n\"); printf(\"请输入您的选择( 1, 2, 3, 4, 5,6)\"); scanf(\"%d\ printf(\"\\n\"); switch(cord) { case 1: { InitStack(s); Disp(s);

6

}break; case 2: {printf(\"输入将要压入链栈的数据的个数：n=\"); scanf(\"%d\ printf(\"依次将%d个数据压入链栈：\\n\ for(i=1;i<=n;i++) {scanf(\"%d\ pushLstack(s,a); } Disp(s); }break; case 3: { printf(\"\\n出栈操作开始!\\n\"); printf(\"输入将要出栈的数据个数：m=\"); scanf(\"%d\ for(i=1;i<=m;i++) {printf(\"\\n第%d次出栈的数据是：%d\ Disp(s); }break; case 4: { printf(\"\\n\\n链栈的栈顶元素为：%d\\n\ printf(\"\\n\"); }break; case 5: { setEmpty(s); Disp(s); }break; case 6: exit(0); } }while (cord<=6); }

[实验3] 队列的顺序表示和实现

实验内容与要求

编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化队列 （2）建立顺序队列 （3）入队 （4）出队

（5）判断队列是否为空 （6）取队头元素

7

（7）遍历队列

分析:

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

入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。 顺序队列中的溢出现象：

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

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

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

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

（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

参考程序:

#include #include #define MAXNUM 100 #define Elemtype int #define TRUE 1 #define FALSE 0 typedef struct

{ Elemtype queue[MAXNUM]; int front; int rear; }sqqueue;

/*队列初始化*/

int initQueue(sqqueue *q) { if(!q) return FALSE; q->front=-1; q->rear=-1; return TRUE; }

/*入队*/

int append(sqqueue *q, Elemtype x)

{ if(q->rear>=MAXNUM-1) return FALSE; q->rear++; q->queue[q->rear]=x; return TRUE; }

8

/*出队*/

Elemtype Delete(sqqueue *q) { Elemtype x; if (q->front==q->rear) return 0; x=q->queue[++q->front]; return x; }

/*判断队列是否为空*/ int Empty(sqqueue *q)

{ if (q->front==q->rear) return TRUE; return FALSE; }

/*取队头元素*/

int gethead(sqqueue *q)

{ if (q->front==q->rear) return 0; return(q->queue[q->front+1]); }

/*遍历队列*/

void display(sqqueue *q) { int s; s=q->front;

if (q->front==q->rear) printf(\"队列空!\\n\"); else

{printf(\"\\n顺序队列依次为：\"); while(srear) {s=s+1; printf(\"%d<-\ } printf(\"\\n\");

printf(\"顺序队列的队尾元素所在位置:rear=%d\\n\ printf(\"顺序队列的队头元素所在位置:front=%d\\n\ } }

/*建立顺序队列*/

void Setsqqueue(sqqueue *q) { int n,i,m; printf(\"\\n请输入将要入顺序队列的长度:\"); scanf(\"%d\

printf(\"\\n请依次输入入顺序队列的元素值:\\n\"); for (i=0;i{ scanf(\"%d\ append(q,m);} }

9

main()

{ sqqueue *head; int x,y,z,select;

head=(sqqueue*)malloc(sizeof(sqqueue)); do{printf(\"\\n第一次使用请初始化！\\n\"); printf(\"\\n请选择操作(1--7):\\n\"); printf(\"===================================\\n\"); printf(\"1 初始化\\n\"); printf(\"2 建立顺序队列\\n\"); printf(\"3 入队\\n\"); printf(\"4 出队 \\n\"); printf(\"5 判断队列是否为空\\n\"); printf(\"6 取队头元素 \\n\"); printf(\"7 遍历队列\\n\"); printf(\"===================================\\n\"); scanf(\"%d\ switch(select) {case 1: { initQueue(head); printf(\"已经初始化顺序队列！\\n\"); break; } case 2: { Setsqqueue(head); printf(\"\\n已经建立队列！\\n\"); display(head); break; } case 3: { printf(\"请输入队的值:\\n \"); scanf(\"%d\ append(head,x); display(head); break; } case 4: { z=Delete(head); printf(\"\\n队头元素%d已经出队！\\n\ display(head); break; } case 5: { if(Empty(head)) printf(\"队列空\\n\");

10

else printf(\"队列非空\\n\"); break; } case 6: { y=gethead(head); printf(\"队头元素为:%d\\n\ break; } case 7: { display(head); break; } } }while(select<=7); }

[实验4[ 队列的链式表示和实现

实验内容与要求:

编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化并建立链队列 （2）入链队列 （3）出链队列 （4）遍历链队列

分析:

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

（1）和链栈类似，无须考虑判队满的运算及上溢。

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

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

#include #include #define ElemType int typedef struct Qnode { ElemType data; struct Qnode *next; }Qnodetype; typedef struct

{ Qnodetype *front;

11

Qnodetype *rear; }Lqueue;

/*初始化并建立链队列*/ void creat(Lqueue *q) { Qnodetype *h; int i,n,x; printf(\"输入将建立链队列元素的个数：n= \"); scanf(\"%d\ h=(Qnodetype*)malloc(sizeof(Qnodetype)); h->next=NULL; q->front=h; q->rear=h; for(i=1;i<=n;i++) { printf(\"链队列第%d个元素的值为：\ scanf(\"%d\ Lappend(q,x); } }

/*入链队列*/

void Lappend(Lqueue *q,int x) { Qnodetype *s; s=(Qnodetype*)malloc(sizeof(Qnodetype)); s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; }

/*出链队列*/

ElemType Ldelete(Lqueue *q) { Qnodetype *p; ElemType x; if(q->front==q->rear) { printf(\"队列为空!\\n\"); x=0; } else { p=q->front->next; q->front->next=p->next; if(p->next==NULL) q->rear=q->front; x=p->data; free(p); } return(x);

12

}

/*遍历链队列*/

void display(Lqueue *q) { Qnodetype *p; p=q->front->next; /*指向第一个数据元素节点 */ printf(\"\\n链队列元素依次为：\"); while(p!=NULL) { printf(\"%d-->\ p=p->next; } printf(\"\\n\\n遍历链队列结束！ \\n\"); }

main()

{ Lqueue *p; int x,cord; printf(\"\\n*****第一次操作请选择初始化并建立链队列！*****\\n \"); do { printf(\"\\n 链队列的基本操作\\n \"); printf(\"=========================================\\n\"); printf(\" 主菜单 \\n\"); printf(\"=========================================\\n\"); printf(\" 1 初始化并建立链队列 \\n\"); printf(\" 2 入链队列 \\n\"); printf(\" 3 出链队列 \\n\"); printf(\" 4 遍历链队列 \\n\"); printf(\" 5 结束程序运行 \\n\"); printf(\"==========================================\\n\"); scanf(\"%d\ switch(cord) { case 1: { p=(Lqueue *)malloc(sizeof(Lqueue)); creat(p); display(p); }break; case 2: { printf(\"请输入队列元素的值：x=\"); scanf(\"%d\ Lappend(p,x); display(p); }break; case 3: { printf(\"出链队列元素：x=%d\\n\ display(p); }break;

13

}

case 4: {display(p);}break; case 5: {exit (0);} }

}while (cord<=5);

14