数据结构实验指导手册4
- 格式：doc
- 大小：54.00 KB
- 文档页数：7
实验四 栈、队列的实现及应用
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验内容
1、实现栈的顺序存储
# define MAXSIZE 100
typedef int ElemType;
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;
void InitStack(SeqStack *s)
{s->top=0;
return 1;
}
int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}
int StackFull(SeqStack *s)
{ if(s->top==MAXSIZE-1) return 1;
else return 0;
}
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}
void Display(SeqStack *s)
{if(s->top==0)
printf("the stack is empty!\n");
else{ while(s->top!=0)
{ printf("%d->",s->data[s->top]); s->top=s->top-1;
}
}
}
ElemType Pop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[--s->top];
}
ElemType StackTop(SeqStack *s)
{ int i;
if(StackEmpty(s)) return 0;
else { i=s->top-1;
return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/
}
main(SeqStack *p)
{int n,i,k,h,x1,x2,select;
printf("create a empty stack!\n");
InitStack(p);
printf("input a stack length:\n");
scanf("%d",&n);
for(i=0;i
{ printf("input a stack value:\n");
scanf("%d",&k);
Push(p,k);
}
printf("select 1:Display()\n");
printf("select 2:Push()\n");
printf("select 3:Pop()\n");
printf("select 4:StackTop()\n");
printf("input a your select(1-4):\n");
scanf("%d",&select);
switch(select)
{case 1:{ display(p);
break;}
case 2:{ printf("input a push a value:\n");
scanf("%d",&h);
Push(p,h);
display(p);
break;}
case 3:{ x1=Pop(p); printf("x1->%d\n",x1);
display(p);
break;
}
case 4:{ x2=StackTop(p);
printf("x2->%d",x2);
break;
}
}
}
2、利用栈实现数制转换
# define MAXSIZE 100
typedef int ElemType； /*将顺序栈的元素定义为整型*/
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;
void InitStack(SeqStack *s)
{s->top=0;
return 1;
}
int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}
int StackFull(SeqStack *s)
{ if(s->top==m-1) return 1;
else return 0;
}
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}
ElemType Pop(SeqStack *s) { ElemType y;
if(StackEmpty(s)){ printf("the stack is empty!\n");
return 0;
}
else { y=s->data[s->top];
s->top=s->top-1;
return y;
}
}
ElemType StackTop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[s->top];
}
void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/
{
SeqStack *S； /*定义一个顺序栈*/
ElemType x；
Init_SeqStack(S)； /*初始化栈*/
if(N<0)
{
printf("\nError,The number must be over 0。")；
return；
}
if(!N) Push(S,0)；
while(N) /*自右向左产生八进制的各位数字，并将其进栈*/
{ Push(S，N%8)； /*余数入栈 */
N=N/8； /*商作为被除数*/
}
printf("Number %d converted to OCT:",N);
while(StackEmpty(S)) /*栈非空时退栈输出*/
{ x=Pop(S)；
printf(“%d”,x)；
}
printf("\n");
}
main( )
{ int n;
printf("Input a number to convert to OCT:\n");
scanf("%d",&n);
Dec_to_Ocx (n);
}
3、实现循环队列的顺序存储 #define maxsize 100
typedef struct
{int data[maxsize];
int front;
int rear;
}seqqueue;
int sqinit(seqqueue *p)
{
p->front=0;p->rear=0;
return 1;}
int enqueue(seqqueue *q, int e)
{if((q->rear+1)%maxsize==q->front)
return 0;
else
q->data[q->rear]=e;
q->rear=(q->rear+1)%maxsize;
return 1;
}
int dequeue(seqqueue *q)
{int e;
if (q->front==q->rear)
return 0;
e=q->data[q->front];
q->front=(q->front+1)%maxsize;
return e;
}
int empty(seqqueue *q)
{int v;
if (q->front==q->rear)
v=1;
else v=0;
return v; }
int gethead(seqqueue *q)
{int e;
if (q->front==q->rear) e=-1;
else e=q->data[q->front];
return e;
}
