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

淮海工学院计算机科学系 实验报告书 课程名： 《数据结构》 题 目： 线性数据结构实验 （栈与队列及其应用） 班 级： 软嵌151 学 号： 2015123352 姓 名： 韩吉  线性表算法实现与应用报告要求 1目的与要求: 1）掌握栈与队列的数据类型描述及特点； 2）掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式和循环存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例的运行过程抓获相关屏面验证程序设计的正确性； 7）希望大家过一个丰富多彩的国庆节，抽出一定时间圆满完成实验，并于第6周周二以前按时提交实验报告，逾期按照旷交处理。 2 实验内容或题目 （一）必做题： 1、实现顺序栈的创建（初始化）、压入（插入）操作（数据、弹出（删除）元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并给出栈的每次操作变化状态； 2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），要求给出栈的操作变化过程； 3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态； 4、实现链式队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态； （注意：必做题需用一个主程序实现所有功能） （二）选做题（视自己能力而定，数量不限）：任选下列一个或多个栈或队列应用源程序（已经发给学委），并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示； 1、实现表达式求值算法程序； 2、用递归算法实现汉诺塔问题算法程序； 3、使用循环队列实现打印杨辉三角形算法程序。 3 实验步骤与源程序 #includestdio.h #includestdlib.h #include windows.h #define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define MAXSIZE 5 void mainmenu(); /*********************************************/ /*顺序栈*/ typedef struct{ int elem[Stack_Size]; int top; }SeqStack; /*链栈*/ typedef struct node { int data; struct node *next; }LinkStackNode; /*循环队列*/ typedef struct{ int element[MAXSIZE]; int front; int rear; }SeqQueue; /*链式队列*/ typedef struct Node{ int data; struct Node *next; }LinkQueueNode; typedef struct{ LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue; /*********************************************/ /********************顺序栈************************/ /*构造一个空栈S*/ void InitStack(SeqStack *S) { S-top = -1; } /*进栈*/ int Push(SeqStack *S,int x) { if(S-top==(Stack_Size-1)) return(FALSE); /*栈已满*/ S-top++; S-elem[S-top]=x; return(TRUE); } /*出栈*/ int Pop(SeqStack *S,int *x) { /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */ if(S-top==-1) /*栈为空*/ return(FALSE); else { *x=S-elem[S-top]; S-top--; /* 修改栈顶指针 */ retur