实验二-栈和队列(基本操作)说课讲解.doc

精品文档
实验二 栈和队列
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 <stdio.h>
#include <malloc.h>

typedef int SElemType;
typedef int Status;
#define INIT_SIZE 100
#define STACKINCREMENT 10
#define Ok 1
#define Error 0
#define True 1
#define False 0
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//初始化栈
Status InitStack(SqStack *s)
{
s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
if(!s->base)
{
puts("存储空间分配失败！");
return Error;
}
s->top = s->base;
s->stacksize = INIT_SIZE;
return Ok;
}

//清空栈
Status ClearStack(SqStack *s)
{
s->top = s->base;
return Ok;
}

//栈是否为空
Status StackEmpty(SqStack *s)
{
if(s->top == s->base)
return True;
else
return False;
}

//销毁栈
Status Destroy(SqStack *s)
{
free(s->base);
s->base = NULL;
s->top = NULL;
s->stacksize=0;
return Ok;
}

//获得栈顶元素
Status GetTop(SqStack *s, SElemType &e)
{
if(s->top == s->base) return Error;
e = *(s->top - 1);
return Ok;
}

//压栈
Status Push(SqStack *s, SElemType e)
{
if(s->top - s->base >= s->stacksize)
{
s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!s->base)
{
puts("存储空间分配失败！");
return Error;
}
s->top = s->base + s->stacksize;
s->stacksize += STACKINCREMENT;

}
*s->top++ = e;
return Ok;
}

//弹栈
Status Pop(SqStack *s, SElemType *e)
{
if(s->top == s->base) return Error;
--s->top;
*e = *(s->top);
return Ok;
}

//遍历栈
Status StackTraverse(SqStack *s,Status(*visit)(SElemType))
{
SElemType *b = s->base;
SElemType *t = s->top;
while(t > b)
visit(*b++);
printf("\n");
return Ok;
}

Status visit(SElemType c)
{
printf("%d ",c);
return Ok;
}

int main()
{
SqStack a;
SqStack *s = &a;
SElemType e;
InitStack(s);
int n;
puts("请输入要进栈的个数：");
scanf("%d", &n);
while(n--)
{
int m;
scanf("%d", &m);
Push(s, m);
}
StackTraverse(s, visit);
puts("");
Pop(s, &e);
printf("%d\n", e);
printf("%d\n", *s->top);
Destroy(s);
return 0;
}

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

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

分析:
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
注意：
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
#include <stdio.h>
#include <malloc.h>

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;

typedef struct node
{
ElemType data;
struct node *next;
}StackNode;

typedef struct
{
StackNode *top;
}LinkStack;

//初始化
void InitStack(LinkStack *s)
{
s->top = NULL;
puts("链栈初始化完成！");
}

//将链栈置空
Status SetEmpty(LinkStack *s)
{
StackNode *p = s->top;
while(p)
{
s->top = p->next;
free(p);
p = s->top;
}
puts("链栈已置空！");
return OK;
}

//压栈
Status Push(LinkStack *s, ElemType e)
{
StackNode *p;
p = (StackNode *)malloc(sizeof(StackNode));
p->data = e;
p->next = s->top;
s->top = p;
return OK;
}

//弹栈
Status Pop(LinkStack *s, ElemType &e)
{
StackNode *p = s->top;
if(s->top == NULL)
{
puts("栈空, 不能进行弹栈操作!");
return ERROR;
}
s->top = p->next;
e = p->data;
free(p);
return OK;
}

//打印栈
Status PrintStack(LinkStack *s)
{
StackNode *p;
p = s->top;
while(p)
{
printf("%d ", p->data);
p = p->next;
}
puts("");
return OK;
}

int main()
{
LinkStack s;
InitStack(&s);
int n;
printf("请输入链栈长度:\n");
scanf("%d", &n);
puts("请输入要录入的数据:");
while(n--)
{
int x;
scanf("%d", &x);
Push(&s, x);
}
PrintStack(&s);
SetEmpty(&s);
return 0;
}

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

实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列

分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1） "下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2） "真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3） "假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
#include <stdio.h>
#include <malloc.h>
typedef int QElemType;
typedef int Status;
#define MaxQSize 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef struct
{
QElemType *base;
int front, rear;
}SqQueue;
//初始化循环队列
int InitQueue(SqQueue &Q)
{
Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType));
if (Q.base == NULL)
{
puts("分配内存空间失败！");
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return 0;
}
//将循环队列清空
int ClearQueue(SqQueue &Q)
{
Q.front = Q.rear = 0;
}
//求队列元素的个数
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MaxQSize) % MaxQSize;
}
//插入元素到循环队列
int EnSqQueue(SqQueue &Q, QElemType e)
{
if ((Q.rear + 1) % MaxQSize == Q.front)
return ERROR; //队列满
Q.base[Q.rear] = e; //元素e入队
Q.rear = (Q.rear + 1) % MaxQSize; //修改队尾指针
return OK;
}
//从循环队列中删除元素
int DeSqQueue(SqQueue &Q, QElemType &e)
{
if (Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front]; //取队头元素至e
Q.front = (Q.front + 1) % MaxQSize; //修改队头指针,如果超内存，循环
return OK;
}
//判断一个循环队列是否为空队列
int isQueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}

int main()
{
int i, e;
SqQueue Q;
InitQueue(Q);
for (i=0; i<MaxQSize-1; i++) //只有MaxQSize个数据进队列
EnSqQueue(Q, i);
i = QueueLength(Q);
printf("队列里的元素有%d个\n", i);
for (i=0; i<3; i++)
{
DeSqQueue(Q, e);
printf("%d ", e);
}
printf("\n");
i = QueueLength(Q);
printf("队列里的元素有%d个\n", i);
for (i=10; i<12; i++)
EnSqQueue(Q, i);
i = QueueLength(Q);
printf("队列里的元素有%d个\n", i);
ClearQueue(Q);
i = QueueLength(Q);
printf("队列里的元素有%d个\n", i);
return 0;
}
[实验4[ 队列的链式表示和实现

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

分析:
队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
注意：
（1）和链栈类似，无须考虑判队满的运算及上溢。
（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。
#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;

typedef struct
{
Node *front;
Node *rear;
}LinkQueue;

Status InitQueue(LinkQueue *q)
{
q->front = NULL;
q->rear = NULL;
return OK;
}//InitQueue

Status DestroyQueue(LinkQueue *q)
{
Node *p = q->front;
while(p)
{
q->front = p->next;
free(p);
p = q->front;
}
puts("队列已销毁！");
return OK;
}

bool isEmpty(LinkQueue *q)
{
if(q->front ==NULL && q->rear == NULL)
return TRUE;
return FALSE;
}//isEmpty

Status Push(LinkQueue *q, ElemType e)
{
Node *p = (Node*)malloc(sizeof(Node));
if(!p)
{
puts("存储空间分配失败!");
return ERROR;
}
p->data = e;
p->next = NULL;//防止出现野指针
if(isEmpty(q))//如果是空队列，则front指向p（第一个元素）
q->front = p;
else
q->rear->next = p;
q->rear = p;//q->rear指向队尾
return OK;
}//Push

Status Pop(LinkQueue *q, ElemType *e)
{
Node *p = q->front;
if(isEmpty(q))
{
puts("队列为空！");
return ERROR;
}
*e = p->data;
q->front = p->next;
free(p);
if(q->front == NULL)//如果出队列后队列空了，则q->rear应指向NULL，
q->rear = NULL;
return OK;
}//Pop

Status createQueue(LinkQueue *q)
{
InitQueue(q);
puts("请输入要输入的队列元素个数：");
int n;
scanf("%d", &n);
while(n--)
{
int m;
scanf("%d", &m);
Push(q, m);
}
return OK;
}//createQueue

Status PrintQueue(LinkQueue *q)
{
Node *p = q->front;
puts("队列中有以下元素:");
while(p)
{
printf("%d ", p->data);
p = p->next;
}
puts("");
return OK;
}
int main()
{
LinkQueue q;
int e;
createQueue(&q);
PrintQueue(&q);
Pop(&q, &e);
puts("出队列的元素是：");
printf("%d\n", e);
PrintQueue(&q);
Push(&q, 8);
puts("8进队列后：");
PrintQueue(&q);
DestroyQueue(&q);
return 0;
}
精品文档