实验二栈和队列
1、实验目的：
（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；
（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。
2、实验要求：
（1）复习课本中有关栈和队列的知识；
（2）用C语言完成算法和程序设计并上机调试通过；
（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
3、实验内容
[实验1] 栈的顺序表示和实现
实验内容与要求:
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
分析:
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
#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
{
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)
{
Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType));
if (Q.base == NULL)
{
puts("分配内存空间失败！");
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return 0;
}
//将循环队列清空
int ClearQueue(SqQueue &Q)
{
Q.front = Q.rear = 0;
}
//求队列元素的个数
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MaxQSize) % MaxQSize;
}
//插入元素到循环队列
int EnSqQueue(SqQueue &Q, QElemType e)
{
if ((Q.rear + 1) % MaxQSize == Q.front)
return ERROR; //队列满
Q.base[Q.rear] = e; //元素e入队
Q.rear = (Q.rear + 1) % MaxQSize; //修改队尾指针
return OK;
}
//从循环队列中删除元素
int DeSqQueue(SqQueue &Q, QElemType &e)
{
if (Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front]; //取队头元素至e
Q.front = (Q.front + 1) % MaxQSize; //修改队头指针,如果超内存，循环return OK;
}
//判断一个循环队列是否为空队列
int isQueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
int main()
{
int i, e;
SqQueue Q;
InitQueue(Q);
for (i=0; i EnSqQueue(Q, 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、实验目的 （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、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 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.为实现运算符优先使用两个栈：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++支持取地址符&。 五、实验总结 实验二堆栈和队列 实验目的： 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、掌握栈和队列的特点，即先进后出与先进先出的原则。 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、实验目的： （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塔问题 实验三栈和队列的操作 一.实验目的和要求 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）：栈 #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）：队列 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：栈和队列 班级：自动化 姓名：李玉书 学号：0704090303 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：曹劼学号：0704080123 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：栈和队列 三、实验学时：4学时 四、实验原理： 用栈实现顺序表的操作 五、实验目的： 1、掌握栈的数据类型描述，栈的特点及栈的存储结构； 2掌握栈的基本运算及应用。 六、实验内容： 设车辆厂生产了硬座车厢和软座车厢共N节，混合在一起要求用顺序栈的5种运算使所有的硬座车厢排列到软座车厢前面。请完善主函数实现上述功能。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 车厢数5，初始顺序SSHSH 测试结果 十、实验结论： 该程序能够判断是否输入错误，并且能够对正确情况下进行栈的数据处理，但是占用了额外的储存量，并且计算次数过多。并且函数不具有通用性。 十一对本实验过程及方法、手段的改进建议： 完善了主函数的功能，使其能够达到排序的目的，但是浪费了一个数组的空间量和运算次数多。 附：源程序 报告评分： #include 《数据结构》课程实验实验报告三 第三章栈和队列的操作 实验题目：实验三栈和队列的操作 学号：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进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 【基本要求】 首先初始化一个顺序栈，通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例：顺序队列的入队和出队操作。 实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：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) 《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验二栈和队列的基本操作。 实验目的 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为栈类型 调用函数建立空栈 栈和队列基本操作实验报告 实验二堆栈和队列基本操作的编程实现【实验目的】 堆栈和队列基本操作的编程实现 要求: 堆栈和队列基本操作的编程实现(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. 栈的顺序存储和链表存储的差异, 答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。数据结构_实验三_栈和队列及其应用
实验三 栈和队列的应用
实验二 栈和队列
数据结构实验二-栈和队列的基本操作与应用
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
实验二栈队列的实现及应用
实验二 堆栈和队列基本操作的编程实现
数据结构实验三栈和队列的应用
实验二栈和队列
实验二 栈与队列操作实验题目
实验三 栈和队列的操作
栈和队列实验报告
实验2栈和队列
实验三 栈和队列
实验二栈和队列基本操作与应用
实验三 栈和队列
栈和队列的基本操作讲解
栈和队列基本操作实验报告
相关主题
文本预览