用顺序结构表示栈并实现栈的各种基本操作讲解学习
栈的顺序表示和实现
2.2基础实验
2.2.1实验目的
（1）掌握栈的顺序表示和实现
（2）掌握栈的链式表示和实现
（3）掌握队列的顺序表示和实现
（4）掌握队列的链式表示和实现
2.2.2实验内容
实验一：栈的顺序表示和实现
【实验内容与要求】
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
【知识要点】
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
【实现提示】
/*定义顺序栈的存储结构*/
typedef struct {
ElemType stack[MAXNUM];
int top;
}SqStack;
/*初始化顺序栈函数*/
void InitStack(SqStack *p)
{q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/
void Push(SqStack *p,ElemType x)
{if(p->top {p->top=p->top+1; /*栈顶+1*/ p->stack[p->top]=x; } /*数据入栈*/ } /*出栈函数*/ ElemType Pop(SqStack *p) {x=p->stack[p->top]; /*将栈顶元素赋给x*/ p->top=p->top-1; } /*栈顶-1*/ /*获取栈顶元素函数*/ ElemType GetTop(SqStack *p) { x=p->stack[p->top];} /*遍历顺序栈函数*/ void OutStack(SqStack *p) { for(i=p->top;i>=0;i--) printf("第%d个数据元素是：%6d\n",i,p->stack[i]);} /*置空顺序栈函数*/ void setEmpty(SqStack *p) { p->top= -1;} 【参考程序】 #include #include #define MAXNUM 20 #define ElemType int /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈*/ void InitStack(SqStack *p) { if(!p) printf("Eorror"); p->top=-1; } /*入栈*/ void Push(SqStack *p,ElemType x) { if(p->top { p->top=p->top+1; p->stack[p->top]=x; } else printf("Overflow!\n"); } /*出栈*/ ElemType Pop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]); p->top=p->top-1; return(x); } else { printf("Underflow!\n"); return(0); } } /*获取栈顶元素*/ ElemType GetTop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; return(x); } else { printf("Underflow!\n"); return(0); } } /*遍历顺序栈*/ void OutStack(SqStack *p) { int i; printf("\n"); if(p->top<0) printf("这是一个空栈！"); printf("\n"); for(i=p->top;i>=0;i--) printf("第%d个数据元素是：%6d\n",i,p->stack[i]); } /*置空顺序栈*/ void setEmpty(SqStack *p) { p->top= -1; } /*主函数*/ main() { SqStack *q; int y,cord;ElemType a; do{ printf("\n"); printf("第一次使用必须初始化！\n"); printf("\n"); printf("\n 主菜单\n"); printf("\n 1 初始化顺序栈\n"); printf("\n 2 插入一个元素\n"); printf("\n 3 删除栈顶元素\n"); printf("\n 4 取栈顶元素\n"); printf("\n 5 置空顺序栈\n"); printf("\n 6 结束程序运行\n"); printf("\n--------------------------------\n"); printf("请输入您的选择( 1, 2, 3, 4, 5,6)"); scanf("%d",&cord); printf("\n"); switch(cord) { case 1: { q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q); OutStack(q); }break; case 2: { printf("请输入要插入的数据元素：a="); scanf("%d",&a); Push(q,a); OutStack(q); }break; case 3: { Pop(q); OutStack(q); }break; case 4: { y=GetTop(q); printf("\n栈顶元素为：%d\n",y); OutStack(q); }break; case 5: { setEmpty(q); printf("\n顺序栈被置空！\n"); OutStack(q); }break; case 6: exit(0); } }while (cord<=6); } 【思考与提高】 （1）读栈顶元素的算法与退栈顶元素的算法有何区别？ （2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？ 实验二：栈的链式表示和实现 【实验内容与要求】 编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化链栈 （2）链栈置空 （3）入栈 （4）出栈 （5）取栈顶元素 （6）遍历链栈 【知识要点】 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 注意： （1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身 （2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。 （3）链栈中的结点是动态分配的，所以可以不考虑上溢。 【实现提示】 typedef int Elemtype; typedef struct stacknode { Elemtype data; stacknode * next; }StackNode; /*定义链栈*/ typedef struct { stacknode * top; //栈顶指针 }LinkStack; /*初始化链栈函数*/ void InitStack(LinkStack * s) { s=(LinkStack *)malloc(sizeof(LinkStack));/*初始化申请空间*/ s->top=NULL;} /*链栈置空函数*/ void setEmpty(LinkStack * s) { s->top=NULL;} /*入栈函数*/ void pushLstack(LinkStack * s, Elemtype x) { p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。 p->data=x; p->next=s->top; //指向栈顶。 s->top=p; //插入 } /*出栈函数*/ Elemtype popLstack(LinkStack * s) {x=p->data; s->top=p->next; //当前的栈顶指向原栈的next free(p); //释放 } /*取栈顶元素函数*/ Elemtype StackTop(LinkStack *s) { return s->top->data;} /*遍历链栈函数*/ void Disp(LinkStack * s) {while (p!=NULL) { printf("%d\n",p->data); p=p->next; } } 【参考程序】 #include "stdio.h" #include "malloc.h" #include "stdlib.h" typedef int Elemtype; typedef struct stacknode { Elemtype data; stacknode * next; }StackNode; typedef struct { stacknode * top; //栈顶指针 }LinkStack; /*初始化链栈*/ void InitStack(LinkStack * s) { s->top=NULL; printf("\n已经初始化链栈！\n"); } /*链栈置空*/ void setEmpty(LinkStack * s) { s->top=NULL; printf("\n链栈被置空！\n"); } /*入栈*/ void pushLstack(LinkStack * s, Elemtype x) { StackNode * p; p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。 p->data=x; p->next=s->top; //由于是在栈顶pushLstack，所以要指向栈顶。 s->top=p; //插入 } /*出栈*/ Elemtype popLstack(LinkStack * s) { Elemtype x; StackNode * p; p=s->top; //指向栈顶 if (s->top ==0) { printf("\n栈空，不能出栈！\n"); exit(-1); } x=p->data; s->top=p->next; //当前的栈顶指向原栈的next free(p); //释放 return x; } /*取栈顶元素*/ Elemtype StackTop(LinkStack *s) { if (s->top ==0) { printf("\n链栈空\n"); exit(-1); } return s->top->data; } /*遍历链栈*/ void Disp(LinkStack * s) { printf("\n链栈中的数据为：\n"); printf("=======================================\n"); StackNode * p; p=s->top; while (p!=NULL) { printf("%d\n",p->data); p=p->next; } printf("=======================================\n"); } void main() { printf("=================链栈操作=================\n\n"); int i,m,n,a; LinkStack * s; s=(LinkStack *)malloc(sizeof(LinkStack)); int cord; do{ printf("\n"); printf("第一次使用必须初始化！\n"); printf("\n"); printf("\n 主菜单\n"); printf("\n 1 初始化链栈\n"); printf("\n 2 入栈\n"); printf("\n 3 出栈\n"); printf("\n 4 取栈顶元素\n"); printf("\n 5 置空链栈\n"); printf("\n 6 结束程序运行\n"); printf("\n--------------------------------\n"); printf("请输入您的选择( 1, 2, 3, 4, 5,6)"); scanf("%d",&cord); printf("\n"); switch(cord) { case 1: { InitStack(s); Disp(s); }break; case 2: {printf("输入将要压入链栈的数据的个数：n="); scanf("%d",&n); printf("依次将%d个数据压入链栈：\n",n); for(i=1;i<=n;i++) {scanf("%d",&a); pushLstack(s,a); } Disp(s); }break; case 3: { printf("\n出栈操作开始!\n"); printf("输入将要出栈的数据个数：m="); scanf("%d",&m); for(i=1;i<=m;i++) {printf("\n第%d次出栈的数据是：%d",i,popLstack(s));} Disp(s); }break; case 4: { printf("\n\n链栈的栈顶元素为：%d\n",StackTop(s)); printf("\n"); }break; case 5: { setEmpty(s); Disp(s); }break; case 6: exit(0); } }while (cord<=6); } 【思考与提高】 （1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？ （2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？ 实验三：队列的顺序表示和实现 【实验内容与要求】 编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化队列 （2）建立顺序队列 （3）入队 （4）出队 （5）判断队列是否为空 （6）取队头元素 （7）遍历队列 【知识要点】 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。 入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front 加1并返回被删元素。 顺序队列中的溢出现象： （1）"下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 （2）"真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 （3）"假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。 注意： （1）当头尾指针相等时，队列为空。 （2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 【实现提示】 /*定义队列*/ typedef struct { Elemtype queue[MAXNUM]; int front; int rear; }sqqueue; /*队列初始化函数*/ int initQueue(sqqueue *q) {q=(sqqueue*)malloc(sizeof(sqqueue)); /*初始化申请空间*/ q->front=-1; q->rear=-1; } /*入队函数*/ int append(sqqueue *q, Elemtype x) { q->rear++; q->queue[q->rear]=x;} /*出队函数*/ Elemtype Delete(sqqueue *q) { x=q->queue[++q->front];} /*判断队列是否为空函数*/ int Empty(sqqueue *q) { if (q->front==q->rear) return TRUE;} /*取队头元素函数*/ int gethead(sqqueue *q) {return(q->queue[q->front+1]);} /*遍历队列函数*/ void display(sqqueue *q) { while(s {s=s+1; printf("%d<-", q->queue[s]); } } /*建立顺序队列函数*/ void Setsqqueue(sqqueue *q) { for (i=0;i { scanf("%d",&m); append(q,m);} } /*利用入队函数快速输入数据*/【参考程序】 #include #include #define MAXNUM 100 #define Elemtype int #define TRUE 1 #define FALSE 0 typedef struct { Elemtype queue[MAXNUM]; int front; int rear; }sqqueue; /*队列初始化*/ int initQueue(sqqueue *q) { if(!q) return FALSE; q->front=-1; q->rear=-1; return TRUE; } /*入队*/ int append(sqqueue *q, Elemtype x) { if(q->rear>=MAXNUM-1) return FALSE; q->rear++; q->queue[q->rear]=x; return TRUE; } /*出队*/ Elemtype Delete(sqqueue *q) { Elemtype x; if (q->front==q->rear) return 0; x=q->queue[++q->front]; return x; } /*判断队列是否为空*/ int Empty(sqqueue *q) { if (q->front==q->rear) return TRUE; return FALSE; } /*取队头元素*/ int gethead(sqqueue *q) { if (q->front==q->rear) return 0; return(q->queue[q->front+1]); } /*遍历队列*/ void display(sqqueue *q) { int s; s=q->front; if (q->front==q->rear) printf("队列空!\n"); else {printf("\n顺序队列依次为："); while(s {s=s+1; printf("%d<-", q->queue[s]); } printf("\n"); printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear); printf("顺序队列的队头元素所在位置:front=%d\n",q->front); } } /*建立顺序队列*/ void Setsqqueue(sqqueue *q) { int n,i,m; printf("\n请输入将要入顺序队列的长度:"); scanf("%d",&n); printf("\n请依次输入入顺序队列的元素值:\n"); for (i=0;i { scanf("%d",&m); append(q,m);} } main() { sqqueue *head; int x,y,z,select; head=(sqqueue*)malloc(sizeof(sqqueue)); do{printf("\n第一次使用请初始化！\n"); printf("\n请选择操作(1--7):\n"); printf("===================================\n"); printf("1初始化\n"); printf("2建立顺序队列\n"); printf("3入队\n"); printf("4出队\n"); printf("5判断队列是否为空\n"); printf("6取队头元素\n"); printf("7遍历队列\n"); printf("===================================\n"); scanf("%d",&select); switch(select) {case 1: { initQueue(head); printf("已经初始化顺序队列！\n"); break; } case 2: { Setsqqueue(head); printf("\n已经建立队列！\n"); display(head); break; } case 3: { printf("请输入队的值:\n "); scanf("%d",&x); append(head,x); display(head); break; } case 4: { z=Delete(head); printf("\n队头元素%d已经出队！\n",z); display(head); break; } case 5: { if(Empty(head)) printf("队列空\n"); else printf("队列非空\n"); break; } case 6: { y=gethead(head); printf("队头元素为:%d\n",y); break; } case 7: { display(head); break; } } }while(select<=7); } （1）开始界面（2）初始化线性表 3.插入:下面是插入第一个元素的图（3），插入后再一次插入其他元素，最终插完元素，见图（4） (4)插入最后一个元素（第五个） 5.取栈顶元素，如图（ (5)删除栈顶元素（6）取栈顶元素 6.置空顺序栈，如图（7） （7）置空顺序表 7. 数值转换（将一个十进制数转换为任意进制） 三进制数2220。 （9）回文数判断a （10）回文数判断b 实验结论：实验成功 八．我对本次实验的总结： 1.通过对该程序的调试和运行，使的对顺序栈的功能及其构成有了进一步的了解。 2.通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中 可以重新熟悉函数在编程中的设置方法 void InitStack(SqStack *p) {if(!p) printf("内存分配失败!"); p->top =-1; } /*入栈*/ void Push(SqStack *p,ElemType x) {if(p->top 实验报告 课程名称数据结构实验名称栈的基本操作与应用 姓名王灵慧专业班级软工18104 学号 201817040409 试验日期 2019-11-06试验地点E3-502指导老师邹汉斌成绩 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈在递归和非递归算法的应用。 二、实验要求 1．进行栈的基本操作时要注意栈“后进先出”的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2.已知函数t(n)=2*t(n/2)+n 其中t(0)=0，n为整数。编写程序实现： (1)计算t(n)的递归算法。 (2)分别用链式栈和顺序栈实现计算t(n)的非递归算法。 四、思考与提高 1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？ 五、实验步骤（每个实验内容包含代码、输入、输出、错误分析）： 1、实验内容（1）： #include 封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______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 遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0 三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作 五、代码： #include 实验三栈和队列 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 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); } 1.上机题目 顺序栈的建立及基本操作实现，要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。 2.需求分析 本次程序设计要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。 （1）输入形式为从键盘输入，用户根据界面的提示从键盘直接输入所对应的数即可。输入的值为正数或字符，用户输入其他的数据会产生 错误。 （2）系统按照用户输入的数据类型，将会把相应的输出结果显示到界面上。 （3）测试：按照提示建立一个单链表，按照提示进行初始化、入栈、出栈、栈的清空、栈中元素计数等操作测试程序是否正确。 3.概要设计 （1）数据结构定义： #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; typedef char SElemType; // 定义栈元素类型 (2)画出各模块之间的调用关系图。 用伪码给出主程序的主要处理过程。 4.详细设计 InitStack（&S)构造一个空栈。 Push(&S，e)插入元素为e的新栈顶。 Pop（&s，&e）删除栈顶元素用e返回 ClearStack(&s)清空栈 StackEmpty(s)栈是否为空 GetTop(s,&e)用e返回s的栈顶元素 StackLength(&s)计算栈长度 (2)主要伪代码： 插入元素为e的新栈顶。 Status Push(SqStack &S){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc(S.base, (S.stacksize+=STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; 第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ 栈的顺序表示和实现 2.2基础实验 2.2.1实验目的 （1）掌握栈的顺序表示和实现 （2）掌握栈的链式表示和实现 （3）掌握队列的顺序表示和实现 （4）掌握队列的链式表示和实现 2.2.2实验内容 实验一：栈的顺序表示和实现 【实验内容与要求】 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能: （1）初始化顺序栈 （2 ）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 【知识要点】 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1 ，栈满时，不能入栈;否则岀现空间溢岀，引起错误，这种现象称为上溢。 岀栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top （通常称top为栈顶指针）来指示当前栈顶位置 【实现提示】 /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void lnitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack)/* 申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 实验二栈和队列的基本操作实现及其应用 一_一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack; 设计相关函数声明： 判断函数：int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 一_三、数据结构与核心算法的设计描述 1、初始化栈 /* 函数功能：对栈进行初始化。参数：栈(SqStack S)。 成功初始化返回0,否则返回-1 */ int InitStack(SqStack &S) { S.base=(SElemType *)malloc(10*sizeof(SElemType)); if(!S.base) //判断有无申请到空间 return -1; //没有申请到内存,参数失败返回-1 S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.base=new SElemType; return 0; } 2、判断栈是否是空 /*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/ int StackEmpty(SqStack S) { if(S.top==S.base) return -1; else return 0; } 3、入栈 /*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */ int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType)); #include 第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。 数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算 ?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include 实验四、栈的顺序和链式存储的表示和实现 实验目的： 1.熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。 2.掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。 实验内容： 1.栈的顺序表示和实现 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。 （1）初始化顺序栈 （2）插入一个元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 #include elemtype stack[MAXNUM]; int top; }sqstack; //初始化顺序栈 void initstack(sqstack *p) { if(!p) printf("error"); p->top=-1; } //入栈 void push(sqstack *p,elemtype x) { if(p->top elemtype pop(sqstack *p) { elemtype x; if(p->top!=0) { x=p->stack[p->top]; printf(" 以前的栈顶数据元素%d 已经被删除!\n",p->stack[p->top]); p->top=p->top-1; return(x); } else { printf("栈为空\n"); return(0); } } //获取栈顶元素 elemtype gettop(sqstack *p) { elemtype x; #include 栈的类型定义与基本操 作 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 循环队链的出队 bool Dequeue( CSQueue &q, QElemType &e ) { int front; if( == 0 ) return false; front = ( + 1 - + MAXQSIZE ) % MAXQSIZE; e = [ front ]; --; return true; } 循环队链的入队 bool Enqueue( CSQueue &q, QElemType e ) { if( == MAXQSIZE ) return false; = ( + 1 ) % MAXQSIZE; [ ] = e; ++; return true; } 链队的入队 void Enqueue( LQueue &q, QElemType e ) { LQueuePtr p; p = new QNode; p->data = e; p->next = >next; >next = p; = p; } 链队的出队 bool Dequeue( LQueue &q, QElemType &e ) { LQueuePtr p; if( >next == ) return false; p = >next; e = p->next->data; >next = p->next; delete p; return true; } 顺序栈的类型定义与基本操作： const StackInitSize=100; const StackInc=10; struct SStack { SElemType *base,*top; isited=false; for(i=1;i<=;i++) if(![i].visited) { visit[i].data); [i].visited=true; Enqueue(q,i); while(Dequeue(q,j)) for(p=[j].firstarc;p;p=p->nextarc) { k=p->adjvex; if(![k].visited) { visit(G>Vexs[k].data); [k].visited=true; Enqueue; } } } } 深度优先搜索遍历 void DFS(ALGraph &G, int i, void visit(VexType)) { int j; Arcptr p; visit[i].data); [i].visited=true; for(p=[i].firstarc ;p; p=p->nextarc) { J=p->adjvex; if(![j].visited) DFS(G,j,visit); } } 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（ B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（ D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶 实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序栈或链式栈，并完成下列操作： （1）初始化栈； （2）判栈为空； （3）出栈； （4）入栈。 算法设计分析 （一）数据结构的定义 struct stackNode{ int data; struct stackNode *nextPtr; }; typedef struct stackNode listStact; typedef listStact *stackNodePtr; （二）总体设计 程序由主函数、入栈函数，出栈函数，删除函数判官是否为空函数和菜单函数组成。 （1）主函数：调用各个函数以实现相应功能 （三）各函数的详细设计： Function1: void instruct() //菜单 （1）：使用菜单显示要进行的函数功能； Function2：void printStack(stackNodePtr sPtr) //输出栈 （1）：利用if判断栈是否为空； （2）：在else内套用while（头指针不为空条件循环）循环输出栈元素； Function3：void push(stackNodePtr *topPtr,int value //进栈 （1）：建新的头指针； （2）：申请空间； （3）：利用if判断newPtr不为空时循环进栈 （4）：把输入的value赋值给newPtr，在赋值给topPtr，再指向下一个位置； Function4：int pop(stackNodePtr*topPtr) //删除 （1）：建新的头指针newPtr； （2）：利用if判断newPtr是否为空，再删除元素。 （3）：把topPtr等于newPtr，把头指针指向的数据赋值给topValue，输出要删除的数据值，头指针指向下一个位置，并清空newPtr； （4）：完成上述步骤后，return toPvalue，返回；栈的顺序表示和实现
栈的基本操作与应用
栈和队列的基本操作的实现
顺序栈的基本操作讲解
栈的操作(实验报告)
数据结构栈的定义及基本操作介绍
数据结构上机顺序栈建立
数据结构栈的基本操作,进栈,出栈
用顺序结构表示栈并实现栈地各种基本操作
栈和队列的基本操作实现及其应用
栈的基本操作c语言
第三章+栈和队列(参考答案)
(完整word版)顺序栈基本操作实验报告
实验四、栈的顺序和链式存储的表示和实现
数据结构——顺序栈的基本操作
栈的类型定义与基本操作
第3章 栈与队列习题参考答案
数据结构(C语言)栈的基本操作
- 用顺序栈进行栈的基本操作-C++源程序
- 实验二 栈和队列(基本操作)
- 栈的操作(实验报告)
- 顺序栈的基本操作讲解
- 数据结构实验5顺序栈的基本操作
- 实现顺序栈的出栈,取栈顶元素操作
- 数据结构栈的基本操作,进栈,出栈
- c++实现顺序栈的基本操作 实验
- 数据结构实验2顺序栈的建立及基本操作 PPT
- 数据结构栈的基本操作,进栈,出栈
- 顺序栈的基本操作讲解
- 顺序栈基本操作实验报告
- 顺序栈,循环队列的基本操作及其应用
- 栈的顺序表示和实现
- 用顺序结构表示栈并实现栈的各种基本操作
- (完整word版)顺序栈基本操作实验报告
- 栈的基本操作c语言
- 顺序栈基本操作实验报告记录
- 顺序栈、链栈的插入和删除实验报告
- 顺序栈的出栈入栈操作实现C++版