实验日期 2010.4.26 教师签字 成绩
实 验 报 告
【实验名称】 第三章栈和队列的基本操作及应用
【实验目的】
（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；
（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。
【实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
】
1. 链栈的基本操作（链栈的初始化、进栈、出栈以及取栈顶的值）
#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;
}
/*取栈顶元素*/
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->data);
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",&cord);
printf("\n");
switch(cord)
{
case 1:
{ InitStack(s);
Disp(s);
}break;
case 2:
{printf("输入将要压入链栈的数据的个数：n=");
scanf("%d",&n);
printf("依次将%d个数据压入链栈：\n",n);
for(i=1;i<=n;i++)
{scanf("%d",&a);
pushLstack(s,a);
}
Disp(s);
}break;
case 3:
{
printf("\n出栈操作开始!\n");
printf("输入将要出栈的数据个数：m=");
scanf("%d",&m);
for(i=1;i<=m;i++)
{printf("\n第%d次出栈的数据是：%d",i,popLstack(s));}
Disp(s);
}break;
case 4:
{
printf("\n\n链栈的栈顶元素为：%d\n",StackTop(s));
printf("\n");
}break;
case 5:
{
setEmpty(s);
Disp(s);
}break;
case 6:
exit(0);
}
}while (cord<=6);
}
2. 顺序栈的基本操作（顺序栈的初始化、进栈、出栈以及取栈顶的值）
#include
#include
#include
#define STACKSIZE 100
#define STACKINCREMENT 10
#define null 0
typedef struct {
int *base;
int *top;
int stacksize;
}SqStack;
SqStack Initstack()
{
SqStack S;
S.base=(int *)malloc(STACKSIZE*sizeof(int));
if(!S.base){printf("\n存储分配失败\n");exit(0);}
S.top=S.base;
S.stacksize=STACKSIZE;
return S;
}
int StackEmpty(SqStack S)
{
if(S.top==S.base) return 1;
else return 0;
}
int StackLength(SqStack S)
{
int *p;
p=S.base;
for(int i=0;p!=S.top;p++,i++);
return i;
}
int GetTop(SqStack S)
{
int e;
if(StackEmpty(S)) {printf("当前栈为空，不能执行此操作\n");exit(0);}
e=*(S.top-1);
return e;
}
int Push(SqStack &S,int e)
{
if(StackLength(S)>=S.stacksize){
S.base=(int *)realloc(S.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));
if(!S.base){printf("\n再分配存储失败\n");return 0;}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}
int Pop(SqStack &S)
{
int e;
if(StackEmpty(S)){printf("当前栈为空，不能执行此操作\n");exit(0);}
e=*--S.top;
return e;
}
void main()
{
int i=0,e;
int *p;
SqStack S;
S=Initstack();
printf("\n 1.元素进栈\n 2.元素出栈\n 3.取栈顶元素\n 4.求栈的长度\n 5.判栈空\n 6.退出\n");
for(;i!=6;){
printf("\n请选择你要进行的操作：");
scanf("%d",&i);
switch(i){
case 1:printf("\n请输入进栈元素：");
scanf("%d",&e);
Push(S,e);p=S.base;
printf("\n当前栈中元素：");
if(StackEmpty(S))printf("当前栈为空\n");
while(p!=S.top){printf("%d ",*p);p++;}
break;
case 2:printf("\n%d已出栈\n",Pop(S));
printf("\n当前栈中元素：");
if(StackEmpty(S))printf("当前栈为空\n");
p=S.base;
while(p!=S.top){printf("%d ",*p);p++;}
break;
case 3:printf("\n栈顶元素为：%d\n",GetTop(S));break;
case 4:printf("\n栈的长度为：%d\n",StackLength(S));break;
case 5:if(StackEmpty(S))printf("\n当前栈为空\n");
else printf("\n当前栈不空\n");
break;
default:printf("\n退出程序\n");
}
}
}
3.顺序队列的基本操作（顺序队的初始化、进队、出对以及取对头）
#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;
}
/*出队*/
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<-", q->queue[s]);
}
printf("\n");
printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear);
printf("顺序队列的队头元素所在位置:front=%d\n",q->front);
}
}
/*建立顺序队列*/
void Setsqqueue(sqqueue *q)
{
int n,i,m;
printf("\n请输入将要入顺序队列的长度:");
scanf("%d",&n);
printf("\n请依次输入入顺序队列的元素值:\n");
for (i=0;i
#include
#define ElemType int
typedef struct Qnode
{
ElemType data;
struct Qnode *next;
}Qnodetype;
typedef struct
{
Qnodetype *front;
Qnodetype *rear;
}Lqueue;
/*初始化并建立链队列*/
void creat(Lqueue *q)
{
Qnodetype *h;
int i,n,x;
printf("输入将建立链队列元素的个数：n= ");
scanf("%d",&n);
h=(Qnodetype*)malloc(sizeof(Qnodetype));
h->next=NULL;
q->front=h;
q->rear=h;
for(i=1;i<=n;i++)
{
printf("链队列第%d个元素的值为：",i);
scanf("%d",&x);
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);
}
/*遍历链队列*/
void display(Lqueue *q)
{
Qnodetype *p;
p=q->front->next; /*指向第一个数据元素节点 */
printf("\n链队列元素依次为：");
while(p!=NULL)
{
printf("%d-->",p->data);
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",&cord);
switch(cord)
{
case 1:
{
p=(Lqueue *)malloc(sizeof(Lqueue));
creat(p);
display(p);
}break;
case 2:
{
printf("请输入队列元素的值：x=");
scanf("%d",&x);
Lappend(p,x);
display(p);
}break;
case 3:
{
printf("出链队列元素：x=%d\n",Ldelete(p));
display(p);
}break;
case 4:
{display(p);}break;
case 5:
{exit (0);}
}
}while (cord<=5);
}
5.循环队列的基本操作：
#include
#include
#include
#define maxsize 100
struct Queue
{
int *base;
int front;
int rear;
};
void initQueue(Queue &Q)
{
Q.base=(int *)malloc(maxsize*sizeof(int));
Q.front=Q.rear=0;
}
int QueueLen(Queue Q)
{
return(Q.rear-Q.front+maxsize)%maxsize;
}
void EnQueue(Queue &Q,int e)
{
if((Q.rear+1)%maxsize==Q.front)
cout<<"队列已满，无法插入!"<>i;
switch(i)
{
case(1):
{
int e;
cout<<"请输入要插入的元素:"<<'\t';
cin>>e;
EnQueue(Q,e);
goto loop;
}
case(2):
{
int e;
DeQueue(Q,e);
goto loop;
}
case(3):
{
int l;
l=QueueLen(Q);
cout<<"队列的长度为:"<<'\t'<
#include
#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//队列由两个栈S1,S2构成
typedef struct
{
SqStack S1;
SqStack S2;
}Queue;
void InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base) exit(0);
S->top=S->base; S->stacksize=STACK_INIT_SIZE;
}
void 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) exit(0);
S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;
}
*(S->top)++=e;
}
void pop(SqStack *S,SElemType *e)
{
if(S->top==S->base) exit(0);
S->top--; *e=*(S->top);
}
//队列的相关操作
void InitQueue(Queue *Q)
{
InitStack(&(Q->S1));InitStack(&(Q->S2));
}
void EnQueue(Queue *Q,SElemType e)
{
push(&(Q->S1),e);
}
void DeQueue(Queue *Q,SElemType *e)
{
if((Q->S2).top==(Q->S2).base)
{
while((Q->S1).top!=(Q->S1).base){pop(&(Q->S1),e);push(&(Q->S2),*e);}
pop(&(Q->S2),e);
}
else pop(&(Q->S2),e);
}
int QueueEmpty(Queue Q)
{
if(Q.S1.base==Q.S1.top&&Q.S2.base==Q.S2.top) return 0;
else return 1;
}
void main()
{
SElemType e; Queue Q; int i;
InitQueue(&Q);
for(i=0;i<10;i++) EnQueue(&Q,'a'+i);
while(QueueEmpty(Q)!=0)
{
DeQueue(&Q,&e); cout<
#include
#include
#define null 0
typedef struct QNode{
int data;
struct QNode *next;
struct QNode *prior;
}QNode;
typedef struct{
QNode *front1,*front2;
QNode *rear1,*rear2;
}LinkDeque;
LinkDeque InitQueue()
{
LinkDeque Q;
Q.front1=Q.rear1=(QNode *)malloc(sizeof(QNode));
if(!Q.front1){printf("\n存储分配失败\n");exit(0);}
Q.front2=Q.rear2=(QNode *)malloc(sizeof(QNode));
if(!Q.front2){printf("\n存储分配失败\n");exit(0);}
Q.front1->next=Q.front2;
Q.front2->next=Q.front1;
return Q;
}
int EnDeque(LinkDeque &Q,int e)
{
QNode *p;
p=(QNode *)malloc(sizeof(QNode));
if(!p){printf("\n存储分配失败\n");exit(0);}
p->data=e;
p->next=Q.front2;
p->prior=Q.rear1;
Q.rear1->next=p;
Q.rear1=p;
Q.rear2=Q.front1->next;
return 1;
}
int DeDeque(LinkDeque &Q)
{
int e;
QNode *p;
if(Q.front1==Q.rear1){printf("栈为空，不能执行删除操作\n");return 0;}
p=Q.rear1;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
Q.rear1=p->prior;
if(Q.front1==Q.front2){Q.rear1=Q.front1;Q.rear2=Q.front2;}
free(p);
return e;
}
int DequeLength(LinkDeque Q)
{
int len=0;
QNode *p;
p=Q.front1->next;
while(p!=Q.front2){len++;p=p->next;}
return len;
}
int Gethead(LinkDeque Q)
{
QNode *p;
if(Q.front1!=Q.rear1){p=Q.rear1;return p->data;}
}
void main()
{
int i=0,e;
LinkDeque Q;
QNode *p;
Q=InitQueue();
printf("\n 1.元素进栈\n 2.元素出栈\n 3.求栈的长度\n 4.取栈顶元素\n 5.退出\n");
for(;i!=5;){
printf("\n请选择你要进行的操作：");
scanf("%d",&i);
switch(i){
case 1:printf("\n请输入进栈元素：");
scanf("%d",&e);
EnDeque(Q,e);
if(Q.front1!=Q.rear1){
printf("\n当前栈元素:");p=Q.front1->next;
while(p!=Q.front2){printf("%d ",p->data);p=p->next;}
}
else printf("当前栈为空\n");
break;
case 2:if(Q.front1!=Q.rear1)printf("\n已删除%d\n",DeDeque(Q));else printf("栈为空，不能此删除操作\n");
if(Q.front1!=Q.rear1){
printf("\n当前栈元素:");p=Q.front1->next;
while(p!=Q.front2){printf("%d ",p->data);p=p->next;}
}
else printf("当前栈为空\n");
break;
case 3:printf("\n栈的长度：%d",DequeLength(Q));break;
case 4:if(Q.front1!=Q.rear1)printf("\n栈顶元素:%d\n",Gethead(Q));else printf("栈为空，不能此删除操作\n");break;
default:printf("\n结束程序\n");
}
}
}
8.约瑟夫队列:
#include
#include
#include
#define len sizeof(struct QNode)
struct QNode
{
int data;
QNode *next;
};
void main()
{
int m,n,k,i,e,num=1;
cout<<"请输入总人数:"<>n;
cout<<"请输入出局数:"<>m;
cout<<"请输入开始报数人的编号:"<>k;
QNode *Q,*p,*r,*t;
Q=(QNode *)malloc(len);Q->next=Q;Q->data=1;
p=Q;
for(i=2;i<=n;i++)
{
p->next=(QNode *)malloc(len);
p=p->next;p->data=i;
}
p->next=Q;r=Q;t=r;
for(i=1;i<=k-1;i++){t=r;r=r->next;}
cout<<"出队顺序为:"<next;}
e=r->data;t->next=r->next;r=t->next;cout<
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个头指针和一个尾指针。
3. 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，但事实上队列中可能还有空位置。此时若有元素入列，就会发生“假溢出”。
浙公网安备 33021202002483