实验三 栈、队列的实现及应用
一、实验目的及要求
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 二、实验学时
2学时 三、实验任务
1. 实现栈的顺序存储 2. 利用栈实现数制转换
四、实验重点、难点
1. 进栈、出栈栈顶指针都要改变。 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==MAXSIZE-1) return 1; else return 0; }
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf(\ return 0; }
else { s->data[s->top]=x;
s->top++; }
}
void Display(SeqStack *s) {if(s->top==0)
printf(\ else{ while(s->top!=0)
{ printf(\ s->top=s->top-1;
- 12 -
}
} }
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(\ InitStack(p);
printf(\ scanf(\ for(i=0;i { printf(\ scanf(\ Push(p,k); } printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\ switch(select) {case 1:{ Display(p); break;} case 2:{ printf(\ scanf(\ Push(p,h); Display(p); break;} case 3:{ x1=Pop(p); printf(\ Display(p); break; } case 4:{ x2=StackTop(p); printf(\ break; } } （二）利用栈实现数制转换 # define MAXSIZE 100 typedef int ElemType； /*将顺序栈的元素定义为整型*/ typedef struct { ElemType data[MAXSIZE]; - 13 - } 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(\ return 0; } else { s->data[s->top]=x; s->top++; } } ElemType Pop(SeqStack *s) { ElemType y; if(StackEmpty(s)){ printf(\ 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(\。\； return； } if(!N) Push(S,0)； while(N) /*自右向左产生八进制的各位数字，并将其进栈*/ { Push(S，N%8)； /*余数入栈 */ N=N/8； /*商作为被除数*/ } printf(\ while(StackEmpty(S)) /*栈非空时退栈输出*/ - 14 - { x=Pop(S)； printf(“%d”,x)； } printf(\} main( ) { int n; printf(\scanf(\Dec_to_Ocx (n); } 六、注意事项 1、进栈、出栈栈顶指针都要改变。 2、数制转换余数入栈后商作为被除数。 七、思考题 1、实现循环队列的顺序存储 实验四 树与二叉树 一、实验目的及要求 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验学时 4学时 三、实验任务 1、 以二叉链表作存储结构，编写前序、中序、后序及层次顺序遍历二叉树的算法。 2、 以二叉链表作存储结构，编写计算二叉树深度、所有结点总数、叶子结点数、 双孩子结点个数、单孩子结点个数的算法 四、实验重点、难点 1、前序、中序、后序及层次顺序遍历二叉树的算法。 2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。 五、操作要点 （一）以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。 #define M 10 typedef int DataType;/*元素的数据类型*/ typedef struct node { DataType data; struct node *lchild,*rchild; }BitTNode,*BiTree; int front=0,rear=0; BitTNode *que[10]; BitTNode *creat() {BitTNode *t; - 15 -