实验二之队列
数据结构实验报告
知识范畴：栈与队列完成日期：2017年03月31日
实验题目：基于循环队列的排队买票模拟程序
实验内容及要求：
编程建立循环队列存储结构，对排队买票过程进行模拟。要求程序在控制台屏幕上显示字符菜单：
1. 排队——输入新到达的买票人姓名，加入买票队列中；
2. 售票——排队队列中最前面的人购票成功，显示信息并将其从队列中删除；
3. 查看队列——从队首到队尾依次列出所有正在排队买票人的姓名；
4.结束——退出系统。
“排队”时，若队满，应提示等待（排队不成功）；
“售票”时，若队空，应提示无人排队（售票失败）。
实验目的：掌握循环队列的基本操作。
数据结构设计简要描述：
序言：
这是本学期第二个实验，实验主要目的是让我们熟悉循环队列的创建，入队，出队等操作数据结构设计：
整个实验可分为一个大的模块，其中包含八个函数模块：菜单显示函数（Menu）,初始化队列（InitQueue），添加购票人到队列（enQueue），删除购票成功的人（dlQueue），输出队列中所有人的信息（Putall_Queue），读取到文件函数（write_file）以及判断队空和队满（Empty、Full）共八个函数模块，队列用结构体创建，其中包含整型（int）的队列容量n，队头指针top，队尾指针tail和队列计数变量c，以及string类型的数组elem；最后通过c++语言ofstream将购票人信息保存到文件中和c语言exit(0)退出系统，便完成了整个模拟买票系统的创建。
算法设计简要描述：
1，首先用结构体创建一个保存购票人的信息队列，为string类型；
2，进行队列初始化，为string类型数组new一个动态内存，将队头和队尾置0，并将从键盘输入的n值赋值给队列容量；
3，判断队列为空或者为满，成立返回真，否则返回假；
4，添加购票人信息，将新增的购票人信息添加到队列中去，为避免“假溢”以及搬动元素的操作，在入队时采用r=（r+1）%n，则数组在逻辑上成为圆环形，也即是采用循环队列；
5，将购票成功的人信息显示出来并将其从队列中移除去，也是采用r=（r+1）%n循环队
列来实现；
6，输出显示所有正在购票人信息，先判断若没有人排队，则显示无人购票，否则采用循环队列输出所有人信息；
7，采用ofstream将所有正在购票人信息读取到文件中去保存；
输入/输出设计简要描述：
1，排队：输入购票人“姓名”，若队满，则输出“排队不成功，请等待！”，否则输出“成功加入到购票队列中去”；
2，售票:调用售票函数时，直接输出排队队列中最前面的人购票成功，并输出其“编号和姓名”，并显示将其从队列中删除；
3，查看所有队列：调用查看所有队列函数，输出所有正在排队的人的信息；
4，写入到文件：输入文件名，若队为空，显示“无人购票，写入失败！”，否则输出成功将其写入到文件中去；
5，退出系统：调用退出函数，成功推出系统；
编程语言说明：
1，编程软件，CodeBlocks 16.0；
2，代码均用C++语言实现；
3，输入输出采用C++语言的cout和cin函数；
4，文件读写采用ofstream类型；
5，程序注释采用C/C++规范；
主要函数说明：
int Menu(void);//菜单显示函数
void InitQueue(Queue,int);//初始化队列
int enQueue(Queue, ElemTp);//在队列中添加新的乘客
int dlQueue(Queue);//将购票成功的人从队列中删除
void Putall_Queue(Queue);//输出显示所有队列中的购票人的信息
bool Empty(Queue);//判断队列是否为空
bool Full(Queue);//判断队列是否满
void write_file(Queue);//读取到文件中
程序测试简要报告：
见截图：1，
2， 3， 4，
5， 6， 7，
8，
9，
源程序代码：
#include
#include
#include
#include
#include
using namespace std;
typedef string ElemTp;//ElemTPy一个string类型
typedef struct node
{
ElemTp *elem;
int n;//队列容量
int top;//队头指针
int tail;//队尾指针
int c;//队列计数变量
}*Queue;
//函数声明
int Menu(void);//菜单显示函数
void InitQueue(Queue,int);//初始化队列
int enQueue(Queue, ElemTp);//在队列中添加新的乘客
int dlQueue(Queue);//将购票成功的人从队列中删除
void Putall_Queue(Queue);//输出显示所有队列中的购票人的信息
bool Empty(Queue);//判断队列是否为空
bool Full(Queue);//判断队列是否满
int write_file(Queue);//读取到文件中
//队列初始化
void InitQueue(Queue q,int n)
{
q->elem = new ElemTp [q->n];//先分配一个M大的内存空间
q->top = q->tail = 0;//将队头和队尾置空
q->n = n + 1;//从键盘输入一个队列的长度，并将其赋值给队列长度，这样就可以人为的控制队列的长度
}
//队列为满
bool Full(Queue q)
{
return (q->tail+1)%q->n == (q->top+q->n)%q->n;//判断队是否满
}
//队为空
bool Empty(Queue q)
{
if(q->top == q->tail)//若果队头等于队尾的话，就返回真，说明队空
{
return true;
}
return false;
//添加购票人信息
int enQueue(Queue q, ElemTp name)
{
if(Full(q))
{
cout<<"排队不成功，请等待!\n"< getch(); return 0; } else { q->elem[q->tail] = name;//添加排队人编号到队列中去 q->tail = (q->tail+1)%q->n;//队尾指针进行加1扫描 cout<<"成功加入购票队列中！请按任意键返回.....\n"< } getch();//获得键盘上一个输入， } //删除已购票成功的人信息 int dlQueue(Queue q) { if(Empty(q)) { cout<<"无人排队，售票失败!\n请按任意键返回.....\n"< return 0; } ElemTp name;//定义一个ElemTp类型来保存退出队列的购票人姓名 int i = q->top+1; cout<<"购票成功！\n购票人信息为:\n\n编号: "< q->top = (q->top+1)%q->n;//队头指针指向下一个队头元素，以让下一个人开始购票 cout<<"\n请按任意建返回.....\n"< } //打印所有正在购票人信息 void Putall_Queue(Queue q) { q->c = q->top;//这里用一个计数变量来保存队列，而不直接用q->top,否则打印一次就相当于让一位购票人出队，而不是打印所有购票人信息 int i = q->top+1; cout<<"所有正在购票人信息:\n"< if(q->c == q->tail) { cout<<"无人购票！"< } else { while(q->c != q->tail) { cout<<"\n编号: "< q->c=(q->c+1)%q->n; } } cout< cout<<"\n请按任意建返回.....\n"< //读取到文件中去 void write_file(Queue q) { ofstream in; char filename[10]; cout<<"\n请输入你想写入的文件名:\n"; cin>>filename;//得到写入文件的文件名 in.open(filename);//创建一个文件名，用于保存我们要写入的数据 q->c = q->top;//这里用一个计数变量来保存队列，而不直接用q->top,否则打印一次就相当于让一位购票人出队，而不是打印所有购票人信息 int i = q->top+1; if(q->c == q->tail) { cout<<"无人购票！不能读取到文件！"< } else { while(q->c != q->tail) { in<<"编号："< q->c=(q->c+1)%q->n; } cout<<"成功读取所有购票人信息！"; } in.close();//关闭文件 cout< cout<<"\n请按任意建返回.....\n"< getch(); } //菜单输出显示，共有排队，售票，查看队列以及结束购票等四项功能int Menu(void) { cout<<"\n***欢迎使用模拟排队买票窗口***\n"; cout<<"\n-----------------------------\n"; cout<<"\n|| 1.排队 ||\n"; cout<<"\n|| 2.售票 ||\n"; cout<<"\n|| 3.查看队列 ||\n"; cout<<"\n|| 4.结束 ||\n"; cout<<"\n|| 5.读取到文件 ||\n"; cout<<"\n-----------------------------\n"; } //主函数调用 int main() { Queue p = new struct node ;//创建一个新的队列 int n;//定义队列最大的长度 cout<<"请输入队列的最大长度(输入0返回)：\n"; cin>>n;//输入队列的长度 while(n == 0) { system("cls"); cin>>n;//输入队列的长度 if(n!=0) break; } InitQueue(p,n);//队列初始化，也就是将队头和队尾元素置空，并将输入的长度赋值给队列长度 cout<<"队列创建完成！"; ElemTp Name;//购票人编号变量 int z = 0;//进入系统指令 while(!z) { system("color A");//购票系统颜色显示，这里显示为绿色 Menu();//调用菜单显示 char b;//定义一个从键盘输入的字符，以开始系统 b = getch();//从键盘读取一个字符，并根据字符判断进入菜单中的哪个选项 switch(b) { case '1'://排队子菜单 system("color B");//颜色变换 cout<<"请输入购票人姓名:\n"; cin>>Name;//输入要加入到队列中的购票人的姓名 enQueue(p,Name);//调用排队函数 system("cls");//重新刷新，回到主菜单 case '2'://售票子菜单 system("color C"); dlQueue(p);//调用售票函数 getch(); system("cls");//重新刷新，回到主菜单 break; case '3': system("color D"); Putall_Queue(p);//调用输出所有购票人信息函数 system("cls");//重新刷新，回到主菜单 break; case '4': system("color E"); cout<<"\n成功退出购票系统！\n"; exit(0); break; case '5': write_file(p); system("cls");//重新刷新，回到主菜单 break; default: system("color A"); system("cls"); } } return 0; } 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 1、顺序栈： 2、链栈： 3、循环队列： 4、链队 三、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include }SqStack; int InitStack(SqStack *S); /*构造空栈*/ int push(SqStack *S,ElemType e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/ void PrintStack(SqStack *S); /*出栈并输出栈中元素*/ int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int Push(SqStack *S,ElemType e){ }/*Push*/ int Pop(SqStack *S,ElemType *e){ }/*Pop*/ } /*CreateStack*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\n"); else { printf("Init Fail!\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e)) Push(S,e); 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 实验三栈和队列的应用 1、实验目的 （1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。 （2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； （3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现 （1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。 （2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用 （1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。 提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为0重复做下列动作 将x%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。 (3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。 （4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤 （1）理解栈的基本工作原理； （2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法； （4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。 4、实验帮助 算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X % R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 5、算法描述 （1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */ 实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________ 一、实验内容： 本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用，其中包含优先级的判断。 二、设计思想 1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先 级 2.优先级关系用“>”“<”“=”来表示三种关系 3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作 符栈 4.运用入栈出栈优先级比较等方式完成运算 三、主要算法框架 1.建立两个栈InitStack(&OPTR); InitStack(&OPND); 2.Push“#”到 OPTR 3.判断优先级做入栈出栈操作 If“<” Push(&OPTR, c); If“=” Pop(&OPTR, &x) If“>” Pop(&OPTR, &theta); Pop(&OPND, &b); Pop(&OPND, &a); Push(&OPND, Operate(a, theta, b)); 四、调试报告 遇到的问题与解决 1.C语言不支持取地址符，用*S代替&S来编写代码 2.一开始没有计算多位数的功能只能计算一位数，在几个中间 不含运算符的数字中间做p = p*10+c运算。代码如下：p = p * 10 + c - '0'; c = getchar(); if (In(c)) { Push(&OPND, p); p = 0; } 主要算法改进设想： 1.可以用数组储存优先级 2.可以用C++编写，C++支持取地址符&。 五、实验总结 实验三栈和队列 3.1实验目的： （1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现； （2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。 3.2实验要求： （1）复习课本中有关栈和队列的知识； （2）用C语言完成算法和程序设计并上机调试通过； （3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 3.3基础实验 [实验1] 栈的顺序表示和实现 实验内容与要求: 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 参考程序: #include 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11 01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++; k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。 实验二栈和队列 1、实验目的： （1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现； （2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。 2、实验要求： （1）复习课本中有关栈和队列的知识； （2）用 C 语言完成算法和程序设计并上机调试通过； （3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 3、实验内容 [ 实验1] 栈的顺序表示和实现实验内容与要求: 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈, 它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈 是否为满，栈满的条件为：不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，一种控制转移的条件。 （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量针）来指示当前栈顶位置 #include <> #include <> typedef int SElemType; typedef int Status; #define INIT_SIZE 100 #define STACKINCREMENT 10 #define Ok 1 #define Error 0 #define True 1 #define False 0 typedef struct p->top= =MAXNUM-，1 栈满时， 否则产生错误。通常栈空作为top （通常称top 为栈顶指 华中科技大学计算机学院《信息系统应用安全》实验报告 实验名称团队成员： 注：团队成员贡献百分比之和为1 教师评语： 一.实验环境 ? 操作系统：windows xp sp3 ? 编译平台：visual c++ 6.0 ? 调试环境：ollydbg 二.实验目的 1. 掌握缓冲区溢出的原理； 2. 掌握缓冲区溢出漏洞的利用技巧； 3. 理解缓冲区溢出漏洞的防范措施。 三.实验内容及步骤 1. 缓冲区溢出漏洞产生的的基本原理和攻击方法 ? 缓冲区溢出模拟程序 由于拷贝字符串时产生缓冲区溢出，用“abcd”字符串的值覆盖了原来eip的值，所以 main函数返回时eip指向44434241，引发访问异常。 ? 运行命令窗口的shellcode 由于把main函数的返回eip地址替换成了jmp esp的地址，main函数 返回的时候就会执行我们的shellcode代码。该shellcode，运行命令窗口。 2. ms06-040 缓冲区溢出漏洞分析和利用 ? 溢出点定位 篇二：缓冲区溢出实验报告 缓 冲 区 溢 出 报 告 院系：计算机与通信工程学院 班级：信息安全10-02班 1. 实验目的 掌握缓冲区溢出的原理 掌握常用的缓冲区溢出方法 理解缓冲区溢出的危害性 掌握防范和避免缓冲区溢出攻击的方法 2. 实验工具 溢出对象：ccproxy 7.2 (1) (2)调试工具： 使用vmware虚拟机，安装ccproxy7.2进行实验调试。 3. 实验步骤 了解ccproxy 7.2 代理服务器为大家解决了很多问题，比如阻挡黑客攻击和局域网共享上网等。 ? 国内非 常受欢迎的一款代理服务器软件 ? 设置简单，使用方便 关于ccproxy6.2缓冲区溢出漏洞说明 实验二栈与队列操作 实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。 本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立顺序栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）将栈顶元素出栈。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立带头结点的链栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）完成出栈操作。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 （7）输出链栈的长度。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。 （2）从键盘输入1个元素，执行入队操作，并显示结果。 （3）将队头元素出队，并显示结果。 （4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。 （2）编写带头结点的循环链表的初始化函数，只用尾指针表示。 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。 （2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题 数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的 1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：栈和队列 班级：自动化 姓名：李玉书 学号：0704090303 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：曹劼学号：0704080123 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：栈和队列 三、实验学时：4学时 四、实验原理： 用栈实现顺序表的操作 五、实验目的： 1、掌握栈的数据类型描述，栈的特点及栈的存储结构； 2掌握栈的基本运算及应用。 六、实验内容： 设车辆厂生产了硬座车厢和软座车厢共N节，混合在一起要求用顺序栈的5种运算使所有的硬座车厢排列到软座车厢前面。请完善主函数实现上述功能。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 车厢数5，初始顺序SSHSH 测试结果 十、实验结论： 该程序能够判断是否输入错误，并且能够对正确情况下进行栈的数据处理，但是占用了额外的储存量，并且计算次数过多。并且函数不具有通用性。 十一对本实验过程及方法、手段的改进建议： 完善了主函数的功能，使其能够达到排序的目的，但是浪费了一个数组的空间量和运算次数多。 附：源程序 报告评分： #include 实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 内容： 把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。 【思考问题】 1.栈的顺序存储和链表存储的差异？ 2.还会有数据移动吗？为什么？ 3.栈的主要特点是什么？队列呢？ 4.栈的主要功能是什么？队列呢？ 5.为什么会有环状队列？ 【参考代码】 （一）利用顺序栈实现十进制整数转换转换成r进制 1、算法思想 将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下： N N / 8 （整除）N % 8（求余） 3456 432 0 低 432 54 0 54 6 6 6 0 6 高 所以：（3456）10 =（6600）8 我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 算法思想如下：当N>0时重复1，2 ①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替N 2、转换子程序 栈和队列实验报告 覃孔林数据结构报告 数据结构(2013)实验报告02 班级: 姓名: 实验方式:上机成绩: 教师批阅处: 一、实验名称 栈和队列基本操作的编程实现 二、实验目的 栈和队列基本操作的编程实现(2学时，验证型)，掌握栈和队列的建立、进 栈、出栈、进队、出队等基本操作的编程实现，也可以进一步编程实现实用的功能等操作，具体编程存储结构要求是顺序存储结构(链表存储结构建议作为课外实验)，可以依次完成主要功能来体现功能的正确性，用菜单进行管理完成大部分功能，要求可以重复运行。 三、实验内容 (一)栈基本功能的编程实现 1、实验设计 (1)栈的基本功能清单:数据进栈、数据出栈、输出栈中的数据、求栈中元素的 个数、销毁此栈和结束程序等。栈的所有功能利用链接存储结构实现。 (2)数据进栈的方式采用从键盘逐个输入(没输入一个数据按回车键)，数据出 栈按照“后进先出”的原则输出。 2、界面设计 (1)主菜单: 图 1 第 1 页共 5 页 覃孔林数据结构报告 (2)数据进栈: 图 2 (3)数据出栈: 图 3 (4)显示栈中数据: 图 4 3、栈功能菜单设计特点: 由于考虑到，栈功能的实现必须在先有数据进栈的前提下，才能进行数据出栈、显示栈中所有数据、求栈长度以及读取栈顶数据等功能。所以当用户进入该栈 功能菜单时，如果不是先进行数据进栈操作，而检测后面的功能时，则提示先输入数据，再进行相应操作，比如: 图 5 4、栈操作示意图 (1)当有数据要进栈的时候，便申请一个空间。然后将新的结点的next指向栈顶top，接着移动top指针，使其指向新的结点。示意图如下: linkstacktop 30 20 10 ^ 40 newnodep ^ 图 6 链表的进栈操作示意图 第 2 页共 5 页 覃孔林数据结构报告 (2)当要执行数据出栈操作时，将top指针往后移，指向其next指向的结点，然后删除top之前指向的结点。示意图如下: Linkstacktop 20 30 10 ^ newnodep 图 7 链栈的出栈操作示意图 (二)队列基本功能的编程实现 1、实验设计 (1)队列的基本功能菜单:数据入队、数据出队、显示队列数据、求队列长度、读取对头数据、清空队列和退出程序等功能。队列的基本功能采用链接存储的结构来实现。 实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：2011-4-13，星期三，3，4节10：10—11：50； 地点：信息学院实验中心，弘毅楼D406、407。 班级：信息091-3第一和第二小组； 二、实验内容 【实验目的】 深入理解栈和队列的特性，领会它的应用背景。熟练掌握在不同存储结构、不同的约定中，其基本操作的实现方法与差异。并体会以下几点（注意你所做的约定）： 1、顺序栈（初始化、栈空/栈满条件，入栈/出栈）； 2、链栈（初始化、栈空条件，入栈/出栈）； 3、顺序队列 4、链队列 【实验选题】 选题一、栈的基本操作的实现（1人/组） 实验1要求 1．会定义顺序栈和链栈的结点类型。 2．掌握栈的插入和删除结点在操作上的特点。 3．熟悉对栈的一些基本操作和具体的函数定义。 具体内容 程序1 该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。 选题二、队列基本操作的实现（1人/组） 实验2要求 4．会定义顺序队列和链队的结点类型。 5．掌握队列的插入和删除结点在操作上的特点。 6．熟悉对队列的一些基本操作和具体的函数定义。 具体内容 程序1：链队列表示和实现 程序2：队列运算在顺序存储结构上的实现 假定采用Queue记录类型的对象Q来表示顺序存储的队列，则在Q上进行各种队列运算 三、实验过程要求 1、分组形式：学生自行分组，每组3人，汇总到课代表处，课代表在本周末前mail告 诉我； 2、组内分工与协作： 1）同一小组的同学在上机前讨论确定问题可以采用的数据结构、流程的安排、模块的划分等，共同完成上机前的准备工作，并对要编制的代码进行分工； 栈的顺序表示和实现 一、实验目的 1. 了解栈和队列的特性。 2. 掌握栈的顺序表示和实现。 3. 掌握栈的链式表示和实现。 4. 掌握队列的顺序表示和实现。 5. 掌握队列的链式表示和实现。 6. 掌握栈和队列在实际问题中的应用。 二、实验要求 1.认真阅读和掌握本实验的程序。 2. 上机运行本程序。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照对顺序表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 三、实验内容 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序栈。 （2）插入元素。 （3）删除栈顶元素。 （4）取栈顶元素。 （5）遍历顺序栈。 （6）置空顺序栈。 四，解题思路 五、程序清单 #include { if(p->top数据结构_实验三_栈和队列及其应用
实验二 栈和队列
数据结构堆栈与队列实验报告
实验三 栈和队列的应用
数据结构实验二-栈和队列的基本操作与应用
栈的操作(实验报告)
实验二_栈、队列地实现与应用
实验二栈队列的实现及应用
栈和队列综合实验报告
实验二栈和队列
栈溢出实验报告
实验二 栈与队列操作实验题目
栈和队列及其应用实验报告
数据结构栈和队列实验报告.doc
实验2栈和队列
实验二 堆栈和队列基本操作的编程实现
栈和队列实验报告
实验二栈和队列基本操作与应用
栈和队列实验报告
- 栈和队列基本操作实验报告
- 实验二(栈和队列的应用)
- 数据结构实验二题目一栈和队列实验报告
- 数据结构堆栈与队列实验报告
- 数据结构实验二-栈和队列的基本操作与应用
- 实验二 堆栈和队列基本操作的编程实现
- 实验二-栈和队列(基本操作)
- 栈和队列的基本操作及其应用(回文判断)
- 2数据结构实验报告二(栈和队列及其应用)
- 实验二栈和队列
- 数据结构实验三栈和队列及其应用
- 实验二 栈和队列
- 数据结构实验二(栈和队列)
- 实验二 栈和队列及其应用
- 实验二 栈和队列
- 实验2栈和队列
- 实验二 栈与队列的基本操作与实现
- 2数据结构实验报告二(栈和队列及其应用)
- 2数据结构实验报告二(栈和队列及其应用)
- 实验二栈队列的实现及应用
- 城记韶关5：江心岛传说和通天塔史话
- 师带徒活动实施方案范本十份
- 培养学生的倾听能力,构筑高效课堂
- 构筑理想课堂
- 培养学生主动学习 构建充满活力的课堂
- 开展大单元主题教学，建构语文高效课堂
- 贯彻课标新理念 构筑数学新课堂
- 构建以学生为主体的小学语文高效课堂
- 构筑高中音乐课堂学生“有效参与”的六度空间
- “构筑理想课堂”实施方案
- 构筑理想课堂实施方案
- 构筑学生课堂 改善学生生活
- 新闻稿件：学习实践新教育,构筑高效新课堂
- 有关生产企业年度培训计划5篇
- 生产企业年度培训计划5篇
- 精选车间员工培训计划3篇
- 生产企业培训计划4篇
- 生产车间培训计划(3篇)
- 车间员工培训计划四篇
- 2021年车间员工培训计划四篇