实验二栈和队列
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 为栈顶指
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
// 初始化栈
Status InitStack(SqStack *s)
{
s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType)); if(!s->base) {
puts(" 存储空间分配失败！"); return Error;
}
s->top = s->base; s->stacksize = INIT_SIZE;
return Ok;
}
// 清空栈
Status ClearStack(SqStack *s)
{
s->top = s->base; return Ok;
}
// 栈是否为空
Status StackEmpty(SqStack *s)
{
if(s->top == s->base) return True;
else
return False;
} // 销毁栈
Status Destroy(SqStack *s)
free(s->base); s->base = NULL; s->top = NULL; s->stacksize=0; return Ok;
}
// 获得栈顶元素
Status GetTop(SqStack *s, SElemType &e) {
if(s->top == s->base) return Error;
e = *(s->top - 1);
return Ok;
}
// 压栈
Status Push(SqStack *s, SElemType e)
{
if(s->top - s->base >= s->stacksize)
{
s->base = (SElemType *)realloc(s->base,
(s->stacksize + STACKINCREMENT* ) sizeof(SElemType));
if(!s->base)
{
puts(" 存储空间分配失败！"); return Error;
}
s->top = s->base + s->stacksize; s->stacksize += STACKINCREMENT;
}
*s->top++ = e; return Ok;
}
// 弹栈
Status Pop(SqStack *s, SElemType *e) {
if(s->top == s->base) return Error;
--s->top;
*e = *(s->top);
return Ok;
}
// 遍历栈
Status StackTraverse(SqStack *s,Status(*visit)(SElemType)) { SElemType *b = s->base;
SElemType *t = s->top;
while(t > b)
visit(*b++);
printf("\n");
return Ok;
}
Status visit(SElemType c)
{
printf("%d ",c);
return Ok;
} int main()
{
SqStack a;
SqStack *s = &a;
SElemType e;
InitStack(s);
int n;
puts(" 请输入要进栈的个数："); scanf("%d", &n);
while(n--)
{
int m;
scanf("%d", &m);
Push(s, m);
}
StackTraverse(s, visit); puts("");
Pop(s, &e); printf("%d\n", e); printf("%d\n", *s->top);
Destroy(s);
return 0;
}
[ 实验2] 栈的链式表示和实现实验内容与要求: 编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈分析:
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
（1）LinkStack 结构类型的定义可以方便地在函数体中修改top 指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack 类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
#include <>
#include <> #define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0 typedef int ElemType;
typedef int Status;
typedef struct node
{
ElemType data; struct node *next;
}StackNode;
typedef struct
{
StackNode *top;
}LinkStack;
// 初始化
void InitStack(LinkStack *s)
{
s->top = NULL;
puts(" 链栈初始化完成！");
// 将链栈置空
Status SetEmpty(LinkStack *s)
{
StackNode *p = s->top;
while(p)
{
s->top = p->next;
free(p);
p = s->top;
}
puts(" 链栈已置空！");
return OK;
}
}
// 压栈
Status Push(LinkStack *s, ElemType e)
{
StackNode *p;
p = (StackNode *)malloc(sizeof(StackNode)); p->data = e;
p->next = s->top;
s->top = p;
return OK;
}
// 弹栈
Status Pop(LinkStack *s, ElemType &e)
{
StackNode *p = s->top;
if(s->top == NULL)
{
puts(" 栈空, 不能进行弹栈操作!"); return ERROR;
}
s->top = p->next;
e = p->data;
free(p);
return OK;
}
// 打印栈
Status PrintStack(LinkStack *s)
{
StackNode *p;
p = s->top;
while(p)
{
printf("%d ", p->data); p = p->next;
}
puts("");
return OK;
}
int main（）
{
LinkStack s;
InitStack（&s）;
int n;
printf（" 请输入链栈长度:\n"）;
scanf（"%d", &n）;
puts（" 请输入要录入的数据:"）;
while（n--）
{
int x;
scanf（"%d", &x）;
Push（&s, x）;
}
PrintStack（&s）;
SetEmpty（&s）;
return 0;
}
?
[ 实验3] 队列的顺序表示和实现
实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程
完成如下功能：序，
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear 所指的位置，然后将rear 加1。出队时，删去front 所指的元素，然后将front 加 1 并返回被删元素。
顺序队列中的溢出现象：
（1）" 下溢" 现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）" 真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）" 假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
(1)当头尾指针相等时，队列为空。
(2)在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
#include <>
#include <>
typedef int QElemType;
typedef int Status;
#define MaxQSize 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef struct
{
QElemType *base;
int front, rear;
}SqQueue;
// 初始化循环队列
int InitQueue(SqQueue &Q)
{
= (QElemType*)malloc(MaxQSize*sizeof(QElemType));
if == NULL)
{
puts(" 分配内存空间失败！");
exit(OVERFLOW);
}
= = 0;
return 0;
}
// 将循环队列清空
int ClearQueue(SqQueue &Q)
}
// 求队列元素的个数
{
= = 0;
int QueueLength(SqQueue Q)
{ return - + MaxQSize) % MaxQSize;
}
// 插入元素到循环队列
int EnSqQueue(SqQueue &Q, QElemType e)
{ if ( + 1) % MaxQSize == return ERROR; // 队列满[] = e; // 元素 e 入队
= + 1) % MaxQSize; // 修改队尾指针
return OK;
}
// 从循环队列中删除元素
int DeSqQueue(SqQueue &Q, QElemType &e)
{ if == return ERROR; e = []; // 取队头元素至 e
= + 1) % MaxQSize; // 修改队头指针, 如果超内存，循环
return OK;
}
// 判断一个循环队列是否为空队列
int isQueueEmpty(SqQueue Q)
{ if == return TRUE; else return FALSE;
}
int main()
{ int i, e; SqQueue Q; InitQueue(Q); for (i=0; i i = QueueLength(Q); printf(" 队列里的元素有%d个\n", i); for (i=0; i<3; i++) { DeSqQueue(Q, e); printf("%d ", e); } printf("\n"); i = QueueLength(Q); printf(" 队列里的元素有%d个\n", i); for (i=10; i<12; i++) EnSqQueue(Q, i); i = QueueLength(Q); printf(" 队列里的元素有%d个\n", i); ClearQueue(Q); i = QueueLength(Q); printf(" 队列里的元素有%d个\n", i); return 0; } [ 实验4[ 队列的链式表示和实现实验内容与要求: 编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化并建立链队列 （2）入链队列 （3）出链队列 （4）遍历链队列分析: 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 （1）和链栈类似，无须考虑判队满的运算及上溢。 （2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。 （3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。 #include <> #include <> typedef int ElemType; typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef struct Node ElemType data; struct Node *next; { }Node; typedef struct { Node *front; Node *rear; }LinkQueue; Status InitQueue(LinkQueue *q) { q->front = NULL; q->rear = NULL; return OK; }//InitQueue Status DestroyQueue(LinkQueue *q) { Node *p = q->front; while(p) { q->front = p->next; free(p); p = q->front; } puts(" 队列已销毁！"); return OK; } bool isEmpty(LinkQueue *q) { if(q->front ==NULL && q->rear == NULL) return TRUE; return FALSE; }//isEmpty Status Push(LinkQueue *q, ElemType e) { Node *p = (Node*)malloc(sizeof(Node)); if(!p) { puts(" 存储空间分配失败!"); return ERROR; } p->data = e; p->next = NULL;// 防止出现野指针if(isEmpty(q))// 如果是空队列，则front 指向p(第一个元素) q->front = p; else q->rear->next = p; q->rear = p;//q->rear 指向队尾 return OK; }//Push Status Pop(LinkQueue *q, ElemType *e) { Node *p = q->front; if(isEmpty(q)) { puts(" 队列为空！"); return ERROR; } *e = p->data; q->front = p->next; free(p); if(q->front == NULL)// 如果出队列后队列空了，则q->rear 应指向NULL，q->rear = NULL; return OK; }//Pop Status createQueue(LinkQueue *q) { InitQueue(q); puts(" 请输入要输入的队列元素个数："); int n; scanf("%d", &n); while(n--) { int m; scanf("%d", &m); Push(q, m); } return OK; }//createQueue Status PrintQueue(LinkQueue *q) { Node *p = q->front; puts(" 队列中有以下元素:"); while(p) { printf("%d ", p->data); p = p->next; } puts(""); return OK; } int main() { LinkQueue q; int e; createQueue(&q); PrintQueue(&q); Pop(&q, &e); puts(" 出队列的元素是："); printf("%d\n", e); PrintQueue(&q); Push(&q, 8); puts("8 进队列后："); PrintQueue(&q); DestroyQueue(&q); 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、实验目的 （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++支持取地址符&。 五、实验总结 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ 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、实验目的： （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)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (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塔问题 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：栈和队列 班级：自动化 姓名：李玉书 学号：0704090303 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：曹劼学号：0704080123 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：栈和队列 三、实验学时：4学时 四、实验原理： 用栈实现顺序表的操作 五、实验目的： 1、掌握栈的数据类型描述，栈的特点及栈的存储结构； 2掌握栈的基本运算及应用。 六、实验内容： 设车辆厂生产了硬座车厢和软座车厢共N节，混合在一起要求用顺序栈的5种运算使所有的硬座车厢排列到软座车厢前面。请完善主函数实现上述功能。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 车厢数5，初始顺序SSHSH 测试结果 十、实验结论： 该程序能够判断是否输入错误，并且能够对正确情况下进行栈的数据处理，但是占用了额外的储存量，并且计算次数过多。并且函数不具有通用性。 十一对本实验过程及方法、手段的改进建议： 完善了主函数的功能，使其能够达到排序的目的，但是浪费了一个数组的空间量和运算次数多。 附：源程序 报告评分： #include 栈和队列综合实验报告 一、实验目的 （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。 实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（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、转换子程序 实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：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）同一小组的同学在上机前讨论确定问题可以采用的数据结构、流程的安排、模块的划分等，共同完成上机前的准备工作，并对要编制的代码进行分工； 数据结构实验报告 实验名称：栈和队列及其应用 班级：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 实验三栈和队列的操作 一.实验目的和要求 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，头文件为 实验四栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 1、顺序栈： 2、链栈： 3、循环队列： 4、链队 三、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #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. 栈的顺序存储和链表存储的差异, 答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。 班级：计算机11-1 学号：姓名：成绩：_________ 实验一顺序表操作验证 一、实验目的 （1）掌握栈的顺序存储结构； （2）掌握栈的操作特性； （3）掌握基于顺序栈的基本操作的实现方法。 （4）掌握队列的链接存储结构； （5）掌握队列的操作特性； （6）掌握基于链队列的基本操作的实现方法。 二、实验内容 （1）建立一个空栈； （2）对已建立的栈进行插入、删除、取栈顶元素等基本操作； （3）建立一个空队列； （4）对已建立的队列进行插入、删除、取队头元素等基本操作。三、设计与编码 #include public: LinkQueue( ); //构造函数，初始化一个空的链队列 ~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue(); //将队头元素出队 T GetQueue(); //取链队列的队头元素 private: Node 实验三栈和队列 一、目的和要求 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指向队尾元素结点。 《数据结构》实验指导及报告书 2014 / 2015 学年第 1学期 姓名： 学号： 班级： 指导教师：徐江 计算机科学与工程学院 2014 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include数据结构_实验三_栈和队列及其应用
实验二 栈和队列
实验三 栈和队列的应用
数据结构实验二-栈和队列的基本操作与应用
实验二_栈、队列地实现与应用
实验二栈队列的实现及应用
实验二栈和队列
实验二 栈与队列操作实验题目
实验2栈和队列
栈和队列综合实验报告
实验二 堆栈和队列基本操作的编程实现
实验二栈和队列基本操作与应用
栈和队列及其应用实验报告
实验三 栈和队列的操作
《数据结构》实验指导及实验报告栈和队列
栈和队列基本操作实验报告
实验五 栈和队列验证实验报告
数据结构-栈和队列-实验
《数据结构》实验二 栈和队列
相关主题
文本预览