数据结构栈的基本操作,进栈,出栈

第五次实验报告——

顺序栈、链栈的插入和删除一需求分析

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={|ai-1,ai ∈D, i=2,...,n } 基本操作：

InitStack(SqStack &S)

操作结果：构造一个空栈

Push(L,e)

操作结果：插入元素e为新的栈顶元素

Status Pop(SqStack &S)

操作结果：删除栈顶元素

}ADT List；

2、链栈可能需要用到有序表的抽象数据类型定义：ADT List{

数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作：

LinkStack(SqStack &S)

操作结果：构造一个空栈

Status Push(L,e)

操作结果：插入元素e为新的栈顶元素

Status Pop(SqStack &S)

操作结果：删除栈顶元素}ADT List；

3、顺序栈程序包含的主要模块： (1) 已给定的函数库：

（2）顺序栈结构体：

（3）顺序栈初始化及创建:

(4)元素插入

(5)元素删除

（6）主程序：

4、链栈程序包含的主要模块： (1) 已给定的函数库：

（2）链栈结构体：

（3）链栈初始化及创建:

(4)元素插入

(5)元素删除

(6)主程序：

三详细设计

线性栈：

结构体（邱建美）

#define STACK_INIT_SIZE 100//存储空间初始分配量

#define STACKINCREMENT 10//存储空间分配增量

typedef struct

{

int *base;//在构造栈之前和销毁之后，base的值为NULL

int *top;//栈顶指针

int stacksize;//当前已分配的存储空间，以元素为单位

}SqStack#include"Base.h"

主函数（涛）

#include"construction.h"

#include"stack_operation.c"

int main()

{

SqStack S;

int choice,e;

S=InitStack();

S=Input_Sq(S);

printf("请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice=");

scanf("%d",&choice);

switch(choice)

{

case 1:

{

printf("请输入插入元素的值e=");

scanf("%d",&e);

S=Push(S,e);

printf("执行入栈操作后的线性栈为");

Print_Stack(S);

};break;

case 2:

{S=Pop(S);

printf("执行出栈操作后的线性栈为");

Print_Stack(S);

};break;

default : printf("您输入的值不合法");

}

}

线性栈的创建（峰）

SqStack InitStack()//线性栈的创建

{

SqStack S;

S.base=(int*)malloc(STACK_INIT_SIZE * sizeof(int));//分配存储空间

if(!S.base)

exit(OVERFLOW);//存储分配失败S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return S;

}

输入函数（胡高飞）

SqStack Input_Sq(SqStack S)//输入函数{

int n,i;

printf("请输入元素个数n=");

scanf("%d",&n);

printf("请输入%d个元素",n);

for(i=0;i

{

scanf("%d",S.top);

S.top++;

}

return S;

}

进栈函数（峰）

SqStack Push(SqStack S,int e)//进栈函数

{

if(S.top-S.base>=S.stacksize)//判断栈是否为满，追加存储空间

{

S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(int));

if(!S.base)

exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;//插入元素

return S;

}

出栈函数（邱建美）

SqStack Pop(SqStack S)//删除函数

{

int e;

if(S.top==S.base)

printf("线性栈为空");

e=*--S.top;

return S;

}

输出函数(方傲侠)

void Print_Stack(SqStack S)//打印函数{

int i;

while(S.base!=S.top)

{

for(i=0;i

{

S.top--;

printf("%5d",*S.top);

}

printf("\n");

}

库函数

* Base.h (程序名) */

#include

#include

#include /* malloc()等 */ #include /* INT_MAX等 */

数据结构实验二_栈的基本操作

青岛理工大学课程实验报告

s->top=s->base; s->stacksize=stack_init_size; return 1; } int Push(sqstack *s,int e) { if(s->top-s->base>=s->stacksize) { s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int)); if(!s->base) return 0; s->top=s->base+s->stacksize; s->stacksize+=stackincrement; } *(s->top++)=e; return e; } int Pop(sqstack *s,int e) { if(s->top==s->base) return 0; e=*--s->top; return e; } int stackempty(sqstack *s) { if(s->top==s->base) { return 1; } else Push(s,n%flag); n=n/flag; } while(!stackempty(s)) { e=Pop(s,e); switch(e) { case 10: printf("A"); break; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break; default: printf("%d",e); } } printf("\n"); return 0; } int main() { sqstack s; StackInit(&s); conversion(&s); return 0; }

数据结构中栈的介绍

数据结构中栈的介绍 1.栈的概念 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。 栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为LIFO表。 如图1所示：假设一个栈S中的元素为a n,a n-1,..,a1，则称a1为栈底元素，a n为栈顶元素。 图1 图 2 2.栈的存储与操作 由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t（称为栈顶指针）来指示栈顶元素的当前位置。 我们用一个数组s[1..m]来表示一个栈时，将栈底固定在数组的底部，即s[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当t=0时，表示这个栈为一个空栈。当t=m时，表示这个栈已满。 可以用下列方式定义栈： const m=栈表目数的上限; type stack=array[1..m] of stype; {栈的数据类型} var s:stack; t:integer; {栈顶指针} 进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）： (1)进栈过程（push） ①若t≥m时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②置t=t+1（栈指针加１，指向进栈地址）； ③S(t)=x，结束（x为新进栈的元素）； procedure push(var s:stack; x:integer;var t:integer); begin if t=m then writeln('overflow') else begin

顺序栈的基本操作讲解

遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0

三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作

五、代码： #include #include #define maxsize 64 typedef int datatype; //定义结构体typedef struct { datatype data[maxsize]; int top; }seqstack; //建立顺序栈seqstack *SET(seqstack *s) { int i; s=(seqstack*)malloc(sizeof(seqstack)); s->top=-1; printf(" 请输入顺序栈元素(整型，以scanf("%d",&i); do{ s->top++; s->data[s->top]=i; scanf("%d",&i); 0 结束)："); }while(i!=0); printf(" 顺序栈建立成功\n"); return s; } //清空栈void SETNULL(seqstack *s) { s->top=-1;} //判断栈空 int EMPTY(seqstack *s) { if(s->top>=0) return 0; else return 1;} //进栈 seqstack *PUSH(seqstack *s) { int x; printf(" 你想要插入的数字："); scanf("%d",&x); if(s->top==maxsize-1) { printf("overflow"); return NULL; } else {

数据结构栈的定义及基本操作介绍

北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）

四、程序清单(包含注释) 1、2. #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 #define INCREASEMENT 10 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

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、在演示程序中，出现的元素以数字出现定义为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={|ai-1,ai ∈D, i=2,...,n } 基本操作： InitStack(SqStack &S) 操作结果：构造一个空栈 Push(L,e) 操作结果：插入元素e为新的栈顶元素

Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： LinkStack(SqStack &S) 操作结果：构造一个空栈 Status Push(L,e) 操作结果：插入元素e为新的栈顶元素 Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 3、顺序栈程序包含的主要模块： (1) 已给定的函数库： （2）顺序栈结构体： （3）顺序栈初始化及创建: (4)元素插入 (5)元素删除

数据结构栈的应用

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

} 改写以上程序，实现功能如下： 调用栈操作函数实现判别一个算术表达式中的圆括号和方括号配对是否正确匹配。 2.C/C++的库函数中已经实现了栈，实例如下： #include //引入栈 using namespace std; int main() { int a; stacks; scanf("%d",&a); s.push(a); //入栈 printf("%d\n",s.top()); //取得栈顶元素输出 s.pop(); //出栈 return 0; } 请根据以上程序，设计算法如下： 判别一个算术表达式中的圆括号配对是否正确。 四、分析与讨论 1. 2.

对上机实践结果进行分析，上机的心得体会。 五、教师评语 成绩 签名： 日期： 附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef char ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空 { return (st->top==-1); } void Push(SqStack *st,ElemType x) //元素进栈 {

if(st->top==MaxSize-1) { printf("栈上溢出!\n"); } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } } void Pop(SqStack *st,ElemType *e) //出栈 { if(st->top==-1) { printf("栈下溢出\n"); } else { *e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置 } } int main() { SqStack L; SqStack *st=&L; ElemType e,a[MaxSize]; int i,j=1,k; do{ InitStack(st); gets(a); for(i=0;a[i]!='\0';i++) { if(a[i]=='('||a[i]=='{'||a[i]=='[') //左括号入栈Push(st,a[i]); if(a[i]==')') { if(StackEmpty(st) ==1)//判断栈是否为空 { printf("多了“(”，不匹配\n"); break; }

数据结构——顺序栈的基本操作

#include using namespace std; # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 typedef struct { int * base; int * top; int stacksize;//当前栈可使用的最大容量 } SqStack; void InitStack(SqStack &S)//构造一个空栈 { S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) {cout<<"存储分配失败!!!"<=S.stacksize) { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) cout<<"存储分配失败!!!"<

数据结构(C语言)栈的基本操作

实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序栈或链式栈，并完成下列操作： （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，返回；

(完整word版)顺序栈基本操作实验报告

数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 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 using namespace std; #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define OVERFLOW -1 #define OK 1 #define NO -1 #define NULL 0 typedef int Status; typedef char SElemType; typedef struct { SElemType *base; //在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 } SqStack; Status Initstack(SqStack &S)//构造一个空栈S { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; return OK; }//InitStack Status StackEmpty(SqStack &S) { if(S.base==S.top)

数据结构 栈

第一章栈 【上机练习】 1、表达式括号匹配(stack) 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。 【输入文件】 输入文件stack.in包括一行数据，即表达式， 【输出文件】 输出文件stack.out包括一行，即“YES”或“NO”。 【输入输出样例】 【样例输入1】【样例输出1】【样例输入2】【样例输出2】 2*(x+y)/(1-x)@YES(25+x)*(a*(a+b+b)@NO 2、括弧匹配检验(check) 【问题描述】 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［］（））或［（［］［］）］等为正确的匹配，［（］）或（［］（）或( ( ) ) ）均为错误的匹配。 现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？ 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK” ，不匹配就输出“Wrong”。输入一个字符串：［（［］［］）］，输出：OK 【输入格式】 输入仅一行字符（字符个数小于255） 【输出格式】 匹配就输出 “OK” ，不匹配就输出“Wrong”。 【输入样例】 ［（］） 【输出样例】 Wrong 3、字符串匹配问题(strs) 【问题描述】 字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。 【输入格式】 文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。 【输出格式】 在输出文件中有n行，每行都是YES或NO。

栈和队列数据结构的特点

第三章习题 一、基本题 1．填空：线性表、栈和队列都是_____结构，可以在线性表的_____位置插入和删除元素，对于栈只能在_______位置插入和删除元素，对于队只能在______位置插入和______位置删除元素。 2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？ 3．设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。 4．试证明：若借助栈由输入序列1，2，…，n得到输出序列为p1p2…p n (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

数据结构 栈和队列的基本操作实现及其应用

实验二栈和队列的基本操作实现及其应用 一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容（可任选或全做） 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列， 是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 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) 题目二、编程模拟队列的管理，主要包括： 出队列、 入队、 统计队列的长度、 查找队列某个元素e、 及输出队列中元素。 [实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。 题目三、Rails

Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. Input The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 （分数：2.00） A.栈 B.队列√ C.树 D.图 解析： 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 （分数：2.00） A.1 B.2 C.3 √ D.4 解析：解析：按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 （分数：2.00） A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 解析： 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 （分数：2.00） A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d 解析：解析：a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 （分数：2.00） A.3 B.4 √ C.5 D.6

实用数据结构基础(第四版)课后习题知识讲解

一、判断题 （第一章绪论） 1.数据元素是数据的最小单元。 答案：错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确 4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间 答案：正确 （第二章线性表） 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误 9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确 10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误 （第三章栈）

11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误 12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。答案：错误 13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确 14.空栈就是所有元素都为0上的栈。 答案：错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章队列） 16.队列式限制在两端进行操作的线性表。 答案：正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误 18.在循环链列队中无溢出现像。 答案：错误 19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确 20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案：错误 （第五章串） 21.串是n个字母的有限序列。 答案：错误 22.串的堆分配存储是一种动态存储结构。

数据结构实验-栈的基本运算

******************************* 实验题目：栈的基本运算 实验者信息： 班级13007102，姓名庞文正，学号1300710226 实验完成的时间3：00 ****************************** 一、实验目的 1，掌握栈的各种存储结构及基本运算的实现。 2，掌握堆栈后进先出的运算原则在解决实际问题中的应用。3，复习c语言中相关语句及函数的用法。 二、实验内容 括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 2.算法概要设计

给出实验的数据结构描述，程序模块、功能及调用关系首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式，同时将它们保存在一个字符型数组exps[]中。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。 #include #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 typedef int datatype; typedef struct //顺序栈的结构体定义 { datatype stack[MAXSIZE]; int top; }seqstack; void setnull(seqstack *s) //置空栈-由于c语言的数组下标是从0开始的，所以置

栈的定义及基本操作

栈的左义及基本操作 在数据结构中，栈是限制在表的一端进行插入和删除的线性表。在线性表中允许插入、删除的这一端称为栈顶，栈顶的当前位置是动态变化的，这样我们只能在栈顶对栈进行操作；不允许插入和删除的另一端称为栈底，栈底是固左不变得，当表中没有元素时称为空栈。 对栈的常用操作有： 栈初始化：InijStackO 初始条件：栈不存在操作结果：构造了一个空栈 判断空：Empty.StackO 若栈空，则返回为1,否则返回0 入栈： Push_Stack(S, x) 初始条件：栈S己经存在操作结果：在栈S的顶部插入一个元素x,这样x就、成为新的栈顶元素。 出栈： Pop_Stack(S, &x) 初始条件：栈S存在且不为空操作结果：栈S的顶部元素 从栈顶删除，保存在变量x中 取栈顶元素：GetTop_Stack(S)初始条件：栈s存在且不为空操作结果：返回栈S的栈顶元素，且原栈的结构不会变化 销毁栈：Destory_Stack(S)初始条件：栈S已经存在操作结果：销毁一个已经存 在的栈 栈的存储方式：(1)顺序存储(2)链式存储 下面我分别介绍这两种的实现： 顺序存储 顺序存储中用int data [STACKSIZE]来存放所有的入栈元素，栈底的位置可以设置固疋在数组的任意一端，栈顶指示实际的栈顶元素位垃，它是随着插入和删除是动态变化的, 用int top 变量来指示栈顶的位置 将data和top封装在一个结构中 #define MAXSIZE 100 typedef{ DataType data[STACKSIZE]; int top; /SeqStack, *PSeqStack： 下面用一个实例介绍栈的一些基本操作(经过测试)： #include #include #include #define STACKSIZE 100 typedef struct{ int data[STACKSIZE]; int top; /SeqStack, *PSeqStack; PSeqStack Init_SeqStack() { PSeqStack S; S= (PSeqStack)malloc(sizeof(SeqStack)); if(S!=NULL) S_>top二-1; return S; }

顺序栈的基本操作讲解

上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号

一、实验目的： 1．熟悉掌握栈的定义、结构及性质； 2．能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3．了解和掌握栈的应用。 二、实验环境： Microsoft Visual c++ 6.0 三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1.建立一个顺序栈 2.输出栈 3.进栈 4.退栈 5.取栈顶元素 6.清空栈 7.判断栈是否为空 进行栈的基本操作时要注意栈"后进先出"的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作

五、代码： #include #include #define maxsize 64 typedef int datatype; //定义结构体 typedef struct { datatype data[maxsize]; int top; }seqstack; //建立顺序栈 seqstack *SET(seqstack *s) { int i; s=(seqstack*)malloc(sizeof(seqstack)); s->top=-1; printf("请输入顺序栈元素（整型，以0结束）："); scanf("%d",&i); do{ s->top++; s->data[s->top]=i; scanf("%d",&i); }while(i!=0); printf("顺序栈建立成功\n"); return s; } //清空栈 void SETNULL(seqstack *s) { s->top=-1;}

数据结构实验三 顺序栈的实现

实验三顺序栈的实现 实验类型：验证性实验学时：2学时 一、实验目的： 掌握顺序栈的基本操作，如进栈、出栈、判断栈空和栈满，取栈顶元素等运算在顺序存储结构上的运算；并能够运用栈的基本操作解决问题，实现相应算法。 二、实验要求： 1、完成顺序栈的基本操作算法并上机调试通过。 2、撰写实验报告，提供实验结果和数据。 三、实验内容: 设计你的栈的顺序存储结构体，编程实现栈的基本操作。栈中的数据元素类型最好为字符类型，方便今后对字符串的算法设计和应用。 测试数据示例： (1) 以“ABCDEFG”的字符串顺序进栈； (2) 以合适顺序出栈得到序列“CDBAGFE”； (3) 取栈顶元素得到‘F’； (4) 进栈直到栈满和出栈直到栈空，检验对这两种情形的正确判断和处理。 [实验要点及说明]：借助实验一线性表的顺序存储程序进行改进 栈(stack)：是限定仅在表尾进行插入或删除操作的线性表。 栈顶(Top)：允许插入和删除的一端，为变化的一端。 栈底(Bottom):栈中固定的一端。 空栈：栈中无任何元素。 特点：根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。 参考：顺序栈的数据类型C语言描述： #define stacksize 100 //定义栈的最大容量 typedef char elemtype; typedef Struct{ elemtype data[stacksize]; //将栈中元素定义为elemtype类型