淮海工学院数据结构第2次实验.doc

淮海工学院计算机科学系 实验报告书 课程名： 《数据结构》 题 目： 线性数据结构实验 （栈与对立队列及其应用） 班 级： 学 号： 2012122693 姓 名：  线性表算法实现与应用报告要求 1目的与要求: 1）掌握栈与队列的数据类型描述及特点； 2）掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式和循环存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数的运行过程抓获相关屏面验证程序设计的正确性； 7）由于国庆节占用授课时间，所以本次实验将不做统一上机安排，要求同学们节日期间自行完成实验任务，并于第6周周4以前按时提交实验报告。 2 实验内容或题目 （一）必做题： 1、实现顺序栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等），并给出栈的每次操作变化状态； 2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等），要求给出栈的操作变化过程； 3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等），并实时给出队列的操作变化状态； 4、实现链式队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等），并实时给出队列的操作变化状态； （二）选做题（视自己能力而定，数量不限）：任选一个或多个源程序（已经发给学委），并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示； 1、实现表达式求值算法程序； 2、用递归算法实现汉诺塔问题算法程序； 3、使用循环队列实现打印杨辉三角形算法程序。 3 实验步骤与源程序 第一题： #include stdio.h #include stdlib.h #define TRUE 1 #define FALSE 0 #define Size 50 typedef struct { int elem[Size]; int top; }SeqStack; void InitStack(SeqStack *S) { S-top =-1; } int IsEmpty(SeqStack *S) { return(S-top==-1?TRUE:FALSE);//判断栈空 为空是真 反之为假 } int IsFull(SeqStack *S) { return(S-top==Size-1?TRUE:FALSE);//判断栈满 为满是真 反之为假 } int Push(SeqStack *S,int x)//压栈 { if(S-top==Size-1) return(FALSE); S-top++; S-elem[S-top] = x; return(TRUE); } int Pop(SeqStack *S,int *x)//弹出 { if(S-top == -1) return(FALSE); else { *x = S-elem[S-top]; S-top--; return(TRUE); } } void main() { SeqStack S; int x,y,i,l; InitStack(S); if(!IsFull(S)) printf(栈空：\n); printf(输入要压入的元素个数（50以内）:\n); scanf(%d,l); printf(输入要压入的元素：\n); for(i=0;il;i++) { scanf(%d,y); Push(S,y); } printf(弹出：\n); while(!IsEmpty(S)) { Pop(S,x); printf(%d\n,x); } } 第二题： #define TRUE 1 #define FALSE 0 #include stdio.h #include stdlib.h typedef struct node { int data; struct node *next; }LinkStackNode; typedef LinkStackNode *LinkStack; int IsEmpty(LinkStack S) { return NULL==S-nex