实验三 栈和队列
实验三栈和队列
1、编写工程shiyan03_1，用顺序栈实现栈的数据结构和基本运算的程序SqStack.cpp，并设计一个主程序SqStackMain.cpp实现如下功能：（头文件为SqStack.h）
（1）初始化栈S。
（2）判断栈S是否非空。
（3）依次进栈元素a，b，c，d，e。
（4）判断栈S是否非空。
（5）输出栈的长度。
（6）输出从栈顶到栈底的元素。
（7）输出出栈序列。
（8）判断栈S是否非空。
（9）释放栈。
2、编写工程shiyan03_2，实现链队列的各种基本运算的程序LinkQueue.cpp，并在此基础上设计一个主程序LinkQueueMain.cpp实现如下功能：（头文件为LinkQueue.h）
（1）初始化队列Q。
（2）判断队列Q是否非空。
（3）依次进队元素a，b，c。
（4）出队一个元素，输出该元素。
（5）输出队列Q的元素个数。
（6）依次进队元素d，e，f。
（7）输出队列Q的元素个数。
（8）输出出队序列。
（9）释放队列。
3、编写工程shiyan03_3，实现顺序循环队列各种基本运算的程序SqQueue.cpp，并在此基础上设计一个主程序SqQueueMain.cpp实现如下功能：（头文件为SqQueue.h）
（1）初始化队列Q。
（2）判断队列Q是否非空。
（3）依次进队元素a，b，c。
（4）出队一个元素，输出该元素。
（5）输出队列Q的元素个数。
（6）依次进队元素2，0，0，9，1，0，0，1。
（7）输出队列Q的元素个数。
（8）输出出队序列。
（9）释放队列。
4、（选做）迷宫问题。请分别用栈和队列的思想求解下列的迷宫问题。
实验三 栈和队列的应用
实验三栈和队列的应用 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 ) /* 栈空 */
数据结构_实验三_栈和队列及其应用
实验编号：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.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 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) /*初始化带头结点链式堆栈*/
实验二_栈、队列地实现与应用
实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：：
/*构造空顺序栈*/ 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、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 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、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ 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
实验二 堆栈和队列基本操作的编程实现
实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（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、转换子程序
数据结构实验三栈和队列的应用
第三章栈和队列的应用 【实验目的】 1．熟练掌握栈和队列的结构，以及这两种数据结构的特点； 2．能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； 3．熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； 第一节知识准备 一、栈： 1. 基本概念 栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。 由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出 （Last In First Out）的线性表，简称LIFO表。 栈示意图见图3-1 2. 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作： InitStack(&S) 构造一个空栈S StackEmpty(S) 判断栈S是否为空 StackLength(S) 返回栈S的元素个数,即栈的长度 GetTop(S,&e) 取栈S的栈顶元素 Push(&S,e) 将元素e入栈 Pop(&S,&e) 删除S的栈顶元素并用e返回其值（即出栈） }ADT Stack
3. 栈的表示： 栈有两种存储表示方法：顺序存储结构和链式存储结构。 (1)顺序存储结构： #define STACK_INIT_SIZE 100； //存储空间初始分配量 #define STACKINCREMENT 10； //存储空间分配增量 typedef struct{ SElemType *base； //栈底指针 SElemType *top； //栈顶指针 int StackSize； //栈的当前容量 }SqStack； (2)链式存储结构： Typedef struct Lnode{ ElemType data; struct Lnode *next; }Lnode, *LinkList; 二、队列： 1. 与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2：────────────── 出队←a1 a2 …… an-1 ←an进队 ────────────── 队头队尾 图3-2 队列 2. 队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作： InitQueue(&Q) 构造一个空队列Q
实验三 栈和队列的操作
实验三栈和队列的操作 一.实验目的和要求 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用栈和队列的各种操作来进行具体的实际应用。 3、加强综合程序的分析、设计能力。 二.实验内容 课后习题4-7 三.实验步骤 1、定义一个函数void QInsert(LNode*&Rear,const ElemType& item)，新建一个结点，如果尾指针为空，则指向新建的结点；否则新结点指向尾指针当前指向的结点，然后尾指针指向新结点，最后新结点成为尾指针。 2、定义一个函数ElemType QDelete(LNode*&Rear)，若删除的是最后一个结点，则删除后尾指针为NULL，尾指针指向被删除结点的后继。 3、定义函数void Print(LNode*&Rear)输出队列，从第一个结点开始依次输出，第一个结点就是尾指针指向的结点。 注意：定义文件后缀为.cpp，头文件为
实验三 栈和队列
《数据结构》课程实验实验报告三 第三章栈和队列的操作 实验题目：实验三栈和队列的操作 学号：11416106 班级：计算机111 姓名：张婷指导教师：游静 实验完成时间：2013.4.22 实验成绩：
实验三栈和队列的操作 一、实验学时 2学时 二、背景知识 1.栈: (1).入栈和进栈操作只能从栈顶一端进行; (2).LIFO(后进先出); (3).栈的两种存储定义:顺序栈和链式栈。 2.队列: (1).入队操作从队尾进行,出队操作从对头进行; (2).FIFO(先进先出); (3).队列的两种存储定义:顺序队和链队。 三、目的要求 1．掌握栈的顺序表示和实现。 Typedef struct{ SelemType *base; SelemType *base; Int stacksize; }sqstack; 2．掌握队列的链式表示和实现以及顺序表示和实现。 链队列： Typedef struct Qnode{ QelemType data; struct Qnode *next; } Qnode,*Queueptr; Typedef struct{ Queueptr front; Queueptr rear; }linkQueue; 顺序队列: #define MAXQSIZE 100 Typedef struct{ Qelemtype *base; int front; int rear; }sqQueue; 四、实验内容 1．顺序栈和循环队列的创建、入栈（队）、出栈（队）等基本操作。 2．数制转换问题 【问题描述】 十进制数N和其它d进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 【基本要求】 首先初始化一个顺序栈，通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例：顺序队列的入队和出队操作。
栈和队列实验报告
实验三：栈和队列 程序代码： （1）：栈 #include
if(p==NULL) { printf("There is no bumber\n"); return; } printf("The remaining numbers are:\n"); while(p!=NULL) { printf("%4d",p->data); p=p->next; } } int pops(node_type **top) { node_type *p; int x; if((*top)==NULL) { printf("error\n"); return 0; } else { x=(*top)->data; printf("\n%d\n",x); p=(*top); (*top)=(*top)->next; return(x); free(p); } } void main() { node_type *h=NULL; pushs(&h); printlst(&h); printf("\nPop a number\n"); pops(&h); printlst(&h); printf("\nPop a number\n"); pops(&h); printlst(&h); } （2）：队列
栈和队列综合实验报告
栈和队列综合实验报告 一、实验目的 （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. 掌握栈和队列的逻辑结构定义和各种存储结构的实现。 2. 熟练运用栈和队列的各种存储结构以及各种基本操作。 3. 根据实际问题的需要，选择栈和队列适合的存储结构解决问题。 二、实验环境 1.WindowsXP操作系统； 2.DEV C++、Visual C++6.0语言环境； 三、实验内容 （一）验证性实验（第1、4题为一组；第2、3题为另一组，每个同学选择一组完成。每个小题一个文件夹，所有文件夹打在一个包中，文件名：“学号”+“姓名”，例如: 13131000张三.rar 。提交码为2014DS3，截止时间：2014年12月14日12：00时。） 1．顺序栈的验证 （1）定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试顺序栈的实现。 （2）修改顺序栈的入栈成员函数push(x)，要求当栈满时，执行私有成员函数stackfull( )进行栈满处理。其功能是：动态创建一个比原来的栈数组大一倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前半部分的位置。 2．链式栈的验证 （1）定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试链式栈的实现。 （2）修改链式栈模板类，用带头结点的单链表作为栈的存储结构。 3．循环队列的验证 （1）定义一个结构体，描述银行排队系统中的客户信息。客户信息包括：客户号、客户类型（企业客户、VIP客户、普通客户）、到达时间（年、月、日、时、分、秒）等。用描述客户信息的结构体作为队列的数据元素类型测试循环队列的实现。 （3）修改教材中循环队列模板类，把成员数据rear改为length表示队列长度，完成修改后各成员函数的实现，并进行测试验证。 4．链队列的验证 （1）定义一个结构体，描述航空订票系统中的航班信息。航班信息包括：航班号、起飞时间（年、月、日、时、分、秒）、起飞地点（8个字符）、抵达时间（年、月、日、时、分、秒）、抵达地点（8个字符）、座位数、空位数、票价等。用描述航班信息的结构体作为队列的数据元素类型测试链队列的实现。 （2）修改教材中的链队列模板类，用一个不带头结点的单循环链表来表示队列（也称为循环链队列），其中只设一个队尾指针rear，不设队头指针，队尾指针rear指向队尾元素结点。
实验二栈和队列基本操作与应用
实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：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）应用队列先进先出的特点，解决一些实际问题。 二、实验内容： 1、使用一个栈，将一个十进制转换成二进制。 粘贴源程序： package Q1; public class SeqStack { public int element[]; public int top; public static SeqStack p; public SeqStack(int size){ this.element=new int[size]; this.top=-1; } public void push(int x){ this.top++; this.element[this.top]=x; } public int pop(){ return this.top==-1 ? -1: (int)this.element[this.top--]; } public int get(){ return this.top==-1 ? -1: (int)this.element[this.top]; } public static void disp(SeqStack p){ int t = -2; while(t!=-1){ t=p.pop(); if(t!=-1) System.out.printf("%d",t); } } public static void fun(int x){ int t; while(x!=1){ t=x%2; x=x/2; p.push(t); } if(x==1)
栈和队列及其应用实验报告
数据结构实验报告 实验名称：栈和队列及其应用 班级：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
栈和队列基本操作实验报告
栈和队列基本操作实验报告 实验二堆栈和队列基本操作的编程实现【实验目的】 堆栈和队列基本操作的编程实现 要求: 堆栈和队列基本操作的编程实现(2学时，验证型)，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验(学时数:2H) 【实验内容】 内容: 把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。【实验分析、说明过程】 分析: 进栈操作 先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下: 将新结点p的指针域指向原栈顶S(执行语句p->next=S)。 将栈顶S指向新结点p(执行语句S=p)。 注:进栈操作的?与?语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。
出栈操作 先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下: 结点p 指针域指向原栈顶S(执行语句p=S)。 栈顶S指向其的下一个结点(执行语句S=S->next) 释放p结点空间(执行语句free(p))。 队列分析:用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。 【思考问题】 1. 栈的顺序存储和链表存储的差异, 答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。
栈和队列的基本操作讲解
《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验二栈和队列的基本操作。 实验目的 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、栈 （1）int main()主函数 定义s为栈类型 调用函数建立空栈
实验报告(栈和队列)
附录A 实验报告 课程：数据结构（c语言）实验名称：栈和队列 系别：数字媒体技术实验日期： 11月15号 专业班级：组别： 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1. 掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满 的条件； 2. 掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中 队头与队尾指针的变化情况； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 栈：只允许在一端插入和删除的线性表，允许插入和删除的一端称为 栈顶(top)，另一端称为栈底(bottom)。 队列: 是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队 头(front)，允许插入的一端叫做队尾(rear)。 2.特点： 栈：后进先出(LIFO) 队列：先进先出(FIFO, First In First Out) 9
3. 表示： 栈：（1）栈的数组表示—顺序栈 （2）栈的链接表示—链式栈 队列：（1）队列的顺序存储结构表示——循环队列 （2）队列的链式表示—链队列 实验内容和要求： 分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准，两边字符完全相同。如：“ABCDEDCBA”。字符串长度小于等于80，用于判断回文的字符串不包括字符串的结束标记符。 基本要求： （1）字符序列可由用户从键盘随意输入； （2）可以连续测试多个字符序列，由用户决定退出测试程序； 算法思想： 判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。 基本操作： 回文判断操作主要包括入栈和入队列、退栈和出队列操作。在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。若使用链式堆栈和链式队列，操作结束后必须销毁链表。 二、实验过程： 程序流程图：