实验报告-栈和队列的基本操作

计算机学院实验报告专用纸

数据结构_实验三_栈和队列及其应用

实验编号：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 << "你的选择是：" ; } 链式储存： 代码部分： 栈"<>select; switch (select){ case 0:break; case 1: cout<<"push data:"; cin>>e; if(push(L,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，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

3 栈和队列答案

第3章栈和队列 一、基础知识题 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点? 3.3 循环队列的优点是什么? 如何判别它的空和满? 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) { x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); } (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) { i=Pop(&T); Push(S,i);

实验二 堆栈和队列基本操作的编程实现

实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（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、转换子程序

PTA第三章栈与队列练习题

1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组

栈的操作(实验报告)

实验三栈和队列 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 #include #define MAXNUM 20

栈和队列的基本操作

《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。 2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。 实验容 题目1： 进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数 算法提示： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈输出栈顶元素 题目2： 利用队列的方式实现辉三角的输出。 算法设计分析 （一）数据结构的定义 1、栈的应用 实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。 栈抽象数据结构描述 typedef struct SqStack /*定义顺序栈*/ { int *base; /*栈底指针*/ int *top; /*栈顶指针*/ int stacksize; /*当前已分配存储空间*/ } SqStack;

2、队列的应用 由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。 队列抽象数据结构描述 typedef struct SeqQueue { int data[MAXSIZE]; int front; /*队头指针*/ int rear; /*队尾指针*/ }SeqQueue; （二）总体设计 1、栈 （1）主函数：统筹调用各个函数以实现相应功能 int main() （2）空栈建立函数：对栈进行初始化。 int StackInit(SqStack *s) （3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出辉三角函数：按一定格式输出辉三角。 void YangHui(int n)

队列实验报告

一．实验项目名称 循环队列和链式队列的创建 二、实验目的 1、掌握队列的特点 (先进先出 FIFO) 及基本操作 ,如入队、出队等， 2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在 实际问题背景下灵活应用。 三、实验内容 1．链式队列的实现和运算 2．循环队列的实现和运算 四、主要仪器设备及耗材 VC++6.0 运行环境实现其操作 五．程序算法 (1)循环队列操作的算法 1>进队列 Void enqueue (seqqueue &q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout<< ” overflow”; else { q.rear=(q.rear+1)%maxsize; // 编号加 1 或循环回第一个单元 q.queue[q.rear]=x; } } 2>出队列 Void dlqueue(seqqueue &q ) { if (q.rear= =q.front)cout<< ” underflow”; else q.front =(q.front+1)%maxsize; } 3>取对头元素

elemtype gethead(seqqueue q ) { if(q.rear= =q.front) { cout<<” underflow；” return NULL;} else return q.queue[(q.front+1)%maxsize]; //front 指向队头前一个位置 } 4>判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) else return 0; reurn 1; } （2）.链队列操作的算法 1>.链队列上的初始化 void INIQUEUE( linkqueue&s) {link *p; p=new link; p->next=NULL;//p 是结构体指针类型，用 s.front=p;//s 是结构体变量，用. s.rear=p;//头尾指针都指向头结点 -> } 2>.入队列 void push(linkqueue &s, elemtype x) { link*p;//p 是结构体指针类型，用-> p=new link; p->data=x; p->next=s.rear->next;//s 是结构体变量，用s.rear->next=p; s.rear=p;//插入最后 . } 3>判队空 int empty( linkqueue s ) {if (s.front= =s.rear) return 1; else return 0; } 4>.取队头元素 elemtype gethead( linkqueue s ) { if (s.front= =s.rear) else retuen return NULL; s.front->next->data; }

栈和队列(必备)

栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。 顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。 栈的定义和实现 #ifndef Stack_H #define Stack_H #include "List.h" template class Stack : List//栈类定义 { public: void Push(Type value) { Insert(value); } Type Pop() { Type p = *GetNext(); RemoveAfter(); return p; }

Type GetTop() { return *GetNext(); } List ::MakeEmpty; List ::IsEmpty; }; #endif 队列的定义和实现 #ifndef Queue_H #define Queue_H #include "List.h" template class Queue : List//队列定义{ public: void EnQueue(const Type &value) { LastInsert(value); } Type DeQueue() {

Type p = *GetNext(); RemoveAfter(); IsEmpty(); return p; } Type GetFront() { return *GetNext(); } List ::MakeEmpty; List ::IsEmpty; }; #endif 测试程序 #ifndef StackTest_H #define StackTest_H #include "Stack.h" void StackTest_int() { cout << endl << "整型栈测试" << endl;

栈和队列的基本操作的实现

封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______2010\4\12

【实验目的】 1.理解并掌握栈和队列的逻辑结构和存储结构； 2.理解栈和队列的相关基本运算； 3.编程对相关算法进行验证。 【实验内容】 （一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）： 1.构造一个栈S，将构造好的栈输出； 2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出； 3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。（二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）： 1.构造一个队列Q，将构造好的队列输出； 2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出； 3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。

【要求】 1.栈和队列中的元素要从终端输入； 2.具体的输入和输出格式不限； 3.算法要具有较好的健壮性，对运行过程中的错误 操作要做适当处理。 三、实验步骤 1．本实验用到的数据结构 (1)逻辑结构：线性结构 (2)存储结构：程序一、四（顺序存储结构）； 程序二、三（链式存储结构）； 2．各程序的功能和算法设计思想 程序一：顺序栈 # include # include # include #define STACKINITISIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 # define OVERFLOW -2 typedef int SElemtype; typedef int status; typedef struct { SElemtype *base; SElemtype *top; int stacksize; }sqstack; void Initstack (sqstack *s) { (*s).base = (SElemtype *)malloc(STACKINITISIZE * sizeof (SElemtype)); if(!(*s).base) exit(OVERFLOW);

建立堆栈和队列的库函数

建立堆栈和队列的库函数 摘要 堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。 队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。 关键词：堆栈；队列；线性表；存储结构

第1章前言 栈和队列是两种常用的数据结构，广泛应用在编译软件和程序设计，操作系统、事物管理等各类软件系统中。从数据结构角度看，栈和队列是受限制的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；从抽象数据类型角度看，栈和队列又是两种重要的抽象数据类型。 第2章堆栈和队列定义 2.1 定义 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。 队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”的线性表。 2.2 队列基本操作 2.2.1栈的建立和初始化： voidInitStack(SqStack * &s)

栈和队列综合实验报告

栈和队列综合实验报告 一、实验目的 （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．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。

栈溢出实验报告

华中科技大学计算机学院《信息系统应用安全》实验报告 实验名称团队成员： 注：团队成员贡献百分比之和为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）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include #define MAXSIZE 100 #define OK 1; #define ERROR 0; typedef struct { int *base; int front; int rear; }SqQueue;//队列的存储结构 int InitQueue(SqQueue &Q) {

Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q)

堆栈和队列

陕西科技大学实验报告 班级：学号：姓名：实验组别： 实验日期：报告日期：成绩： 报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：栈与队列 一、实验目的 1.掌握栈、队列的思想及其存储实现。 2.掌握栈、队列的常见算法的程序实现。 二、实验要求 1.编写函数,采用链式存储实现栈的初始化、入栈、出栈操作。 2.编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。 3.编写函数,采用链式存储实现队列的初始化、入队、出队操作。 4.编写函数,采用顺序存储实现队列的初始化、入队、出队操作。 5.编写一个主函数,在主函数中设计一个简单的菜单,分别调试 上述算法。 三、实验原理（流程图）：

四、实验数据（源代码）： package B_Stack; public class SqLinkStackDemo { // 主函数中设计一个简单的菜单,分别调试上述算法 public static void main(String[] args) throws Exception { /** 顺序栈 */ SqStack s = new SqStack(8); // 顺序栈栈的初始化 s.clear(); // 顺序栈的入栈 System.out.println("顺序栈入栈："); s.push(5); s.push('c'); s.push("Hello"); s.display(); // 顺序栈的出栈 System.out.println('\r' + "顺序栈出栈："); s.pop(); s.display(); /** 链表栈 */ LinkStack ls = new LinkStack(); // 链表栈的初始化 ls.clear(); // 链表栈的入栈 System.out.println('\r' + "链表栈入栈："); ls.push(88); ls.push('Z'); ls.push("HelloWorld"); ls.display(); // 顺序栈的出栈 System.out.println('\r' + "链表栈出栈："); ls.pop(); ls.display(); /** 顺序队列 */ CircleSqQueue circleSqQueue = new CircleSqQueue(8); // 顺序存储实现队列的初始化 circleSqQueue.clear(); // 顺序存储实现队列的入队 System.out.println('\r' + "顺序队列入队："); circleSqQueue.offer(666); circleSqQueue.offer("队列"); circleSqQueue.offer('Q'); circleSqQueue.display();

栈和队列及其应用实验报告

数据结构实验报告 实验名称：栈和队列及其应用 班级：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 #include #define N 2 //可以控制进制转换 using namespace std; typedef struct{ int *top; int *base; int stacksize; }stack;

队列的表示及实现实验报告

陕西科技大学实验报告 班级信工082 学号200806030202 姓名李霄实验组别 实验日期2010-12-20 室温报告日期2010-12-20 成绩 报告内容：(目的和要求，原理，步骤，数据，计算，小结等) 实验名称：实验三队列的表示及实现 实验目的： 1、通过实验进一步理解队列的“先进先出”特性。 2、掌握队列的逻辑结构及顺序存储结构和链式存储结构。 3、熟练运用C语言实现队列的基本操作。 4、灵活运用队列解决实际问题。 实验内容： 1、实现链队列，并编写主函数进行测试。测试方法为：依次10、20、 30、40，然后，出对3个元素。再次入队50、60，然后出队3个元 素。查看屏幕上显示的结果是否与你分析的结果一致。 2、在1的基础上，再出队1个元素。查看屏幕上显示的结果是否与你 分析的结果一致。 3、编写主函数比较取队头元素操作和出队操作。 实验学时：2学时 实验程序 #include "stdio.h" #include "conio.h" typedef int DataType; typedef struct { DataType data; struct QNode* next; }LQNode,*PQNode; typedef struct { PQNode front,rear; }LinkQueue; int InitQueue(LinkQueue *Q) { Q->front=Q->rear=(PQNode)malloc(sizeof(LQNode));

if (!Q->front){printf("errors\n");return 0;} Q->front->next=NULL; return 1; } int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } int EnQueue(LinkQueue *Q,DataType e) { PQNode p; p=(PQNode)malloc(sizeof(LQNode)); if(!p) { printf("\n\nerrors\n\n"); return 0; } p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return 1; } int DeQueue(LinkQueue *Q,DataType *e) { PQNode p; if( Q->front==Q->rear) { printf("\nerrors\n");