计算机学院实验报告专用纸
实验室：网络实验室 机号：网34 实验日期：20##年4月3日
计算机学院实验报告附页
计算机学院实验报告附页
第二篇：栈和队列的基本操作
/*验四：栈和队列的基本操作
实验内容
1．采用链式存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现栈的初始化、入栈、出栈操作。
3．采用链式存储实现队列的初始化、入队、出队操作。
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
5．在主函数中设计一个简单的菜单，分别测试上述算法。 */
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0
#define OVERFLOW -2
#define OK 1
typedef int SElemType;
typedef int QElemType;
//存储空间初始分配量 //存储空间分配增加量
typedef struct{ //顺序栈的结构
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct SqNode
{
SElemType data;
SqNode *Link;
}*Sqptr,NODE;
typedef struct
{ //链栈的结构单元
Sqptr top; //栈顶指针
}Stack;
int InitStackb(Stack &S) //链式存储实现栈的初始化 {
S.top=(Sqptr)malloc(sizeof(NODE));
if(!S.top) exit (OVERFLOW);
S.top->Link=NULL;
return 1;
}
void Pushb(Stack &S) //链式存储实现栈的入栈操作 {
Sqptr p;
int x;
printf("请输入入栈元素(以0结束):");
scanf("%d",&x);
while(x)
{
p=(Sqptr)malloc(sizeof(NODE));
if(!p) return ;
p->data=x;
p->Link=S.top->Link;
S.top->Link=p;
scanf("%d",&x);
}
}
void Popb(Stack &S) //链式存储实现栈的出栈操作 {
int x;
Sqptr p;
while(S.top->Link)
{
p=S.top->Link;
x=p->data;
S.top->Link=p->Link;
printf("\t删除的栈顶元素是%d\n",x);
free(p);
}
}
int InitStack(SqStack &S) //顺序存储初始化栈 {
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)
exit(-2);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
void createStack(SqStack &S) //顺序栈元素入栈 {
int a;
printf("请输入入栈元素(以0结束):");
scanf("%d",&a);
while(a)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=a;
scanf("%d",&a);
}
}
void Popa(SqStack &S) //顺序存储实现栈的出栈操作 {
SElemType *p;
int x;
while(S.top-S.base)
{
p=S.top;
x=*--S.top;
printf("删除的栈顶元素是%d\n",x);
}
}
typedef struct QNode
{
QElemType data;
struct QNode *next;
}*QueuePtr,QNode;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitQueue(LinkQueue &Q) //链式存储实现队列的初始化 {
} Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front->next=NULL; return 1;
//链式存储实现队列的入队 void EnQueue(LinkQueue &Q)
{
int x;
QueuePtr p;
} printf("请输入队列元素(以0结束)"); scanf("%d",&x); while(x) { p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=x; p->next=NULL; Q.rear->next=p; Q.rear=p; scanf("%d",&x); }
void DeQueue(LinkQueue &Q) //链式存储实现队列的出队 {int x;
QueuePtr p;
while(Q.front!=Q.rear)
{
p=Q.front->next;
x=p->data;
printf("\t删除的队头元素是：%d\n",x);
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
}
}
typedef struct
{
SElemType *base;
int front,rear;
}SqQueue;
int InitQueueb(SqQueue &S) //顺序存储实现队列的初始化 {
} S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.front=S.rear=0; return 1;
//顺序存储实现队列的入队 void EnQueueb(SqQueue &S)
{
int x;
printf("请输入入队元素(以0结束):");
scanf("%d",&x);
while(x)
{
if((S.rear+1)%STACK_INIT_SIZE==S.front) return; S.base[S.rear]=x;
S.rear=(S.rear+1)%STACK_INIT_SIZE;
scanf("%d",&x);
}
}
void DeQueueb(SqQueue &S) //顺序存储实现队列的出队 {int x;
while(S.front!=S.rear)
{
x=S.base[S.front];
printf("\t删除的队头元素是:%d\n",x);
S.front=(S.front+1)%STACK_INIT_SIZE;
}
}
void main()
{
SqStack La;
int menu;
Stack Lb;
LinkQueue Q;
SqQueue S;
Lb.top=NULL;
La.base=NULL;
La.top=NULL;
do{
printf("1 创建顺序桟\n");
printf("2 顺序栈出栈操作\n");
printf("3 创建链栈\n");
printf("4 链栈出栈操作\n");
printf("5 创建链队列\n"); printf("6 连队的出对操作\n"); printf("7 创建顺序队列\n"); printf("8 顺序队列出对操作\n"); printf("0 退出\n"); printf("\n请输入所选菜单（0-10）:"); scanf("%d",&menu); switch(menu) { case 1: InitStack(La); createStack(La); break; case 2: if(La.base==NULL||La.top==NULL) { printf("I am is null,Plase create first\n"); break; } Popa(La); break; case 3: InitStackb(Lb); Pushb(Lb); break; case 4: if(Lb.top==NULL) { printf("这是个空栈,无法执行输出操作\n"); break; } Popb(Lb); break; case 5: InitQueue(Q); EnQueue(Q); break; case 6: DeQueue(Q); break; case 7: InitQueueb(S); EnQueueb(S); break;
} case 8: DeQueueb(S); break; case 0: exit(0); } }while(menu);