文档介绍：江西信息应用职业技术学院计算机技术系
上机实训报告
课程： 数据结构
任课教师： 夏侯赞
实训场所及日 期：
综303机房；
2008-10-23
姓名：
学号：
专业及班级：
实训：
栈与队列的 基本操作
实训序号：
3
■卜 口 I 、“人 成贝人数：
1
一、 实训目的及要求
掌握栈与队列的基本操作，并能对其进 行简单应用。
2•掌握栈与队列输入与输出，栈与队列的 基本操作。
二、 实训设备状况
正常。
三、 实训内容
1、 利用栈的基本操作将一个十进制的正 整数转换成二进制数据，并将其转换结果 输出。
2、 对于输入的任意括号串进行匹配进行 配对检测；若配对，则返回"right冷若不配 对则返回5,error5,o
3、 在链队列上的入队和出队操作。
四、 实训步骤
1、
步骤1进入编程环境，建立一新文件
步骤2存储定义
步骤3建立建立链栈的几个基本操作
步骤4实现十进制转换成二进制
步骤5编译运行程序，观察运行情况和 输出结果
2、
步骤4实现括号匹配配对检测运算
3、
步骤3建立有两个元素的链队列。
步骤4实现链队列上的入队和出队
五、 调试过程及实训结果
六、 总结
1、 掌握栈与队列的基本操作：入栈、 出栈，入队、出队。
2、 掌握对栈的操作都是在栈顶进行。
3、 掌握入队操作在队尾，出队操作在 队尾。
4、 在链队列上的入队和出队操作是在 单链表上插入和删除操作的特殊情况，只是 需要修改队尾或队首指针。
5、 栈与队列在实际应用中非常广泛。
七、 附录(源程序清单等)
： /进制的转换/ 算法描述:初始化栈
只要x不为0重复做下列动作 将x%2入栈
x=x/2
只要栈不为空重复做下列动作:栈顶出栈， 输出栈顶元素
广进制转换*/
main()
int k,ij,a[8]5x;
i=0;
printf("please input the number:"); scanf("%d",&x);
while(x!=O)
{
k=x%2;
a[i++]=k;
x=x/2;
} for(j=i-1;j>=0;j-) printf("%dn,a[j]); printf('^\n'^);
}
： /括号匹配/
算法描述：从左至右扫描表达式，遇左括 号入栈，遇右括号与栈顶元素比较：若左右 括号匹配，则继续扫描；否则说明不匹配， 结束。在上述操作中，若栈为空，或扫描结 束后栈不为空，均说明不匹配。
广括号匹配检测*/
#include <>
#include <>
#define NULLO
typedef struct node {
char data;
struct node *next;
Jstackn ode/Lin kStack;
initstack(LinkStack s)
{
s= NULL;
}
char gettop(LinkStack s) { return (s->data);
}
push(LinkStack s,char e) { LinkStack p;
p = (LinkStack) malloc( sizeof( stacknode));
p->data = e; p->next = s;
s = p;
}
pop(LinkStack s, char *e) { LinkStack p;
*e = s->data;
p = s;
s = s->next; free(p);
}
main() {LinkStack s,p; char ch;
int bool;
s= NULL;
p = (LinkStack)
malloc( sizeof( stacknode));//构造空栈 p->data = #; 〃表示括号串的开始 p->next = s;
s = p;
ch=getchar();
bool=1;
while (ch!='\rT&&bool)
{if(ch==lO
{p = (LinkStack)
malloc( sizeof( stacknode)); //如遇左括号, 则左括号进栈
p->data =
p->next = s;
s = P；}
if(ch==T)
if( (s->data)==,#*) //取栈顶元素与#比 较，
bool=0;〃无左括号配对，令bool=0 else s = s->next; 〃有左括号配对，
则消解左括号
ch=getchar();
}
if( (s->dat