栈和队列的基本操作实现及其应用
实验二栈和队列的基本操作实现及其应用
一_一、实验目的
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)
{
=(SElemType *)malloc(10*sizeof(SElemType));
if(! //判断有无申请到空间
return -1; //没有申请到内存,参数失败返回-1
=;
=STACK_INIT_SIZE;
=new SElemType;
return 0;
}
2、判断栈是否是空
/*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/
int StackEmpty(SqStack S)
{
if== return -1;
else return 0;
}
3、入栈
/*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */
int Push(SqStack &S,SElemType e)
{
if {
=(SElemType *)realloc,+1) * sizeof(SElemType));
//重新分配空间
if(! return -1;
=+;
+=STACKINCREMENT;
}
*++=e; //插入操作
return 0;
}
4、出栈
/*函数功能:在栈中删除元素。参数;栈(SqStack S),元素(SElemtype e)。成功删除返回0,否则返回-1 */
int Pop(SqStack &S,SElemType &e)
{
if== return -1;
e=*; //删除操作
return 0;
}
5、判断是否为回文
/*函数功能:判断栈中的字符串是否为回文。参数; 栈(SqStack S)。是回文时返回1,否则返回0*/
int IsReverse(SqStack &S)
{
int i;
char a;
for(i=0;i { Pop(S,a); if(a!=b[i]) return 0; } return 1; } 一_四、函数的调用 主函数主要设计： int lpp; char ch; SqStack p; InitStack(p); cout<<"请输入字符："; while((ch=())&&ch!='@') { Push(p,ch); b[j]=ch; j++; } if (StackEmpty(p)==-1) { cout<<"此为空栈"< return 0; } lpp=IsReverse(p); if(lpp==0) cout<<"此字符串不是回文。"< else cout<<"此字符串是回文。"< 一_五、实验总结 通过这次试验我熟悉了对栈的基本操作，对基本的栈操作有了很好的掌握，知道自己容易在什么地方出错，。 一_六、程序清单 #include using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 char b[STACK_INIT_SIZE+STACKINCREMENT]; int j=0; typedef char SElemType; typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack; int InitStack(SqStack &S) { =(SElemType *)malloc(10*sizeof(SElemType)); if(! return -1; =; =STACK_INIT_SIZE; =new SElemType; return 0; } int StackEmpty(SqStack S) { if== return -1; else return 0; } int Push(SqStack &S,SElemType e) { if { =(SElemType *)realloc,+1) * sizeof(SElemType)); if(! return -1; =+; +=STACKINCREMENT; } *++=e; return 0; } int Pop(SqStack &S,SElemType &e) { if== return -1; e=*; return 0; } int IsReverse(SqStack &S) { int i; char a; for(i=0;i { Pop(S,a); if(a!=b[i]) return 0; } return 1; } int main() { int lpp; char ch; SqStack p; InitStack(p); cout<<"请输入字符："; while((ch=())&&ch!='@') { Push(p,ch); b[j]=ch; j++; } if (StackEmpty(p)==-1) { cout<<"此为空栈"< return 0; } lpp=IsReverse(p); if(lpp==0) cout<<"此字符串不是回文。"< else cout<<"此字符串是回文。"< return 0; } 二_一、实验目的 2、会用栈和队列解决简单的实际问题。 二_二、实验内容 题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。 相关常量及结构定义： typedef int QElemType; typedef struct QNode { QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; int count; }LinkQueue; 设计相关函数声明： InitQueue(LinkQueue &Q) EnQueue(LinkQueue &Q,QElemType e) DeQueue(LinkQueue &Q,QElemType &e) QueueLength(LinkQueue Q) QueueTraverse(LinkQueue Q) QueueFind(LinkQueue Q,QElemType e) 二_三、数据结构与核心算法的设计描述1、初始化队列 int InitQueue(LinkQueue &Q) { ==(QueuePtr)malloc(sizeof(QNode)); if(! return -1; >next=NULL; return 0; } 2、入队列 int EnQueue(LinkQueue &Q,QElemType e) { QueuePtr lpp; lpp=(QueuePtr)malloc(sizeof(QNode)); if(!lpp) return -1; lpp->data=e; lpp->next=NULL; if==NULL) { >next=lpp; =lpp; } else { >next=lpp; =lpp; } return 0; } 3、出队列 int DeQueue(LinkQueue &Q,QElemType &e) { QueuePtr lpp; if== return -1; lpp=>next; e=lpp->data; >next=lpp->next; if==lpp) =; delete lpp; return 0; } 4、统计队列的长度 int QueueLength(LinkQueue Q) { QueuePtr lpp=; int i=0; while(lpp!= { i++; lpp=lpp->next; } return i; } 5、查找队列的某个元素 int QueueFind(LinkQueue Q,QElemType e) { QueuePtr p; p=>next; while(p) { if(p->data==e) return 1; p=p->next; } return 0; } 6、遍历队列 int QueueTraverse(LinkQueue Q) { QueuePtr p; p=>next; while(p) { cout< p=p->next; } cout< return 0; } 7、主界面函数 void zhujiemian() { cout< cout<<"【\t\t 数据结构实验二】"< cout<<" 【\t\t---------------------------------------------------------------------】"< cout<<"【\t\t 1 队列初始化】"< cout<<"【\t\t 2 出队列】"< cout<<"【\t\t 3 入队列】"< cout<<"【\t\t 4 队列长度】"< cout<<"【\t\t 5 在队列中查找元素】"< cout<<"【\t\t 6 遍历队列】"< cout<<"【\t\t 其他键退出】"< cout<<" 【\t\t---------------------------------------------------------------------】"< cout<<"【\t\t 请选择要进行操作的序号（1--6）】:"; } 二_四、函数调用及主函数设计 主函数主要涉及： LinkQueue Q; int a,b,c; zhujiemian(); cin>>a; while(a!=1) { cout<<"输入错误，必须先初始化，请重新输入："; cin>>a; } cout< do { switch(a) { case 1: if(InitQueue(Q)==0) cout<<"初始化成功！"< else cout<<"初始化失败！"< break; case 2: if(QueueLength(Q)==0) { cout<<"队列为空无法出队！"< break; } if(DeQueue(Q,c)==0) cout<<"删除成功！"< else cout<<"删除失败！"< break; case 3: cout<<"输入你要入队元素"< cin>>c; if(EnQueue(Q,c) ==0) cout<<"入队成功！"< else cout<<"入队失败！"< break; case 4: b=QueueLength(Q); cout<<"队列的长度为："< break; case 5: cout<<"您要查找的元素："; cin>>b; if(QueueFind(Q,b)==1) cout<<"恭喜您，队列中有您要找的元素"< else cout<<"不好意思，队列中没有您要找的元素"< break; case 6: QueueTraverse(Q); break; default: break; } zhujiemian(); cin>>a; cout< }while(a>0&&a<=6); 说明： 通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在1—6内的函数将结束，否则将继续进行。 二_五、程序调试及运行结果分析 程序第一步必须执行初始化，否则程序不能运行。 在程序第一步必须执行初始化后，程序完美运行，在进行任何函数操作程序都是正常运行，而且本程序对插入和删除时进行错误检测如有的地方不可以插入，有点地方不能删除，如果队列为空时则程序会输出队列为空，并继续进行其他操作，大大减少了程序的bug。 二_六、程序清单 #include using namespace std; typedef int QElemType; typedef struct QNode { QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; int count; }LinkQueue; int InitQueue(LinkQueue &Q) { ==(QueuePtr)malloc(sizeof(QNode)); if(! return -1; >next=NULL; return 0; } int EnQueue(LinkQueue &Q,QElemType e) { QueuePtr lpp; lpp=(QueuePtr)malloc(sizeof(QNode)); if(!lpp) return -1; lpp->data=e; lpp->next=NULL; if==NULL) { >next=lpp; =lpp; } else { >next=lpp; =lpp; } return 0; } int DeQueue(LinkQueue &Q,QElemType &e) { QueuePtr lpp; if== return -1; lpp=>next; e=lpp->data; >next=lpp->next; if==lpp) =; delete lpp; return 0; } int QueueLength(LinkQueue Q) { QueuePtr lpp=; int i=0; while(lpp!= { i++; lpp=lpp->next; } return i; } int QueueTraverse(LinkQueue Q) { QueuePtr p; p=>next; while(p) { cout< p=p->next; } cout< return 0; } int QueueFind(LinkQueue Q,QElemType e) { QueuePtr p; p=>next; while(p) { if(p->data==e) return 1; p=p->next; } return 0; } void zhujiemian() { cout< cout<<"【\t\t 数据结构实验二】"< cout<<" 【\t\t---------------------------------------------------------------------】"< cout<<"【\t\t 1 队列初始化】"< cout<<"【\t\t 2 出队列】"< cout<<"【\t\t 3 入队列】"< cout<<"【\t\t 4 队列长度】"< cout<<"【\t\t 5 在队列中查找元素】"< cout<<"【\t\t 6 遍历队列】"< cout<<"【\t\t 其他键退出】"< cout<<" 【\t\t---------------------------------------------------------------------】"< cout<<"【\t\t 请选择要进行操作的序号（1--6）】:"; } int main() { LinkQueue Q; int a,b,c; zhujiemian(); cin>>a; while(a!=1) { cout<<"输入错误，必须先初始化，请重新输入："; cin>>a; } cout< do { switch(a) { case 1: if(InitQueue(Q)==0) cout<<"初始化成功！"< else cout<<"初始化失败！"< break; case 2: if(QueueLength(Q)==0) { cout<<"队列为空无法出队！"< break; } if(DeQueue(Q,c)==0) cout<<"删除成功！"< else cout<<"删除失败！"< break; case 3: cout<<"输入你要入队元素"< cin>>c; if(EnQueue(Q,c) ==0) cout<<"入队成功！"< else cout<<"入队失败！"< break; case 4: b=QueueLength(Q); cout<<"队列的长度为："< break; case 5: cout<<"您要查找的元素："; cin>>b; if(QueueFind(Q,b)==1) cout<<"恭喜您，队列中有您要找的元素"< else cout<<"不好意思，队列中没有您要找的元素"< break; case 6: QueueTraverse(Q); break; default: break; } zhujiemian(); cin>>a; cout< }while(a>0&&a<=6); return 0; } 循环队链的出队 bool Dequeue( CSQueue &q, QElemType &e ) { int front; if( q.length == 0 ) return false; front = ( q.rear + 1 - q.length + MAXQSIZE ) % MAXQSIZE; e = q.elem[ front ]; q.length --; return true; } 循环队链的入队 bool Enqueue( CSQueue &q, QElemType e ) { if( q.length == MAXQSIZE ) return false; q.rear = ( q.rear + 1 ) % MAXQSIZE; q.elem[ q.rear ] = e; q.length ++; return true; } 链队的入队 void Enqueue( LQueue &q, QElemType e ) { LQueuePtr p; p = new QNode; p->data = e; p->next = q.rear->next; q.rear->next = p; q.rear = p; } 链队的出队 bool Dequeue( LQueue &q, QElemType &e ) { LQueuePtr p; if( q.rear->next == q.rear ) return false; p = q.rear->next; e = p->next->data; q.rear->next = p->next; delete p; return true; } 顺序栈的类型定义与基本操作： 实验名称：实验四队列的基本操作 实验目的 掌握队列这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序队列或链式队列，并完成下列操作： （1）初始化队列； （2）队列是否为空； （3）出队； （4）入队。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; //链表单链表 typedef struct Node *PNode; int dui; dui =1; struct Node { int info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; （二）总体设计 程序由主函数、创建队列函数、判断是否为空队列函数、入队函数、出队函数、取数函数、显示队列函数、菜单函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 main() { PLinkQueue a; //定义链表a int b,c,e; //b 菜单选择c选择继续输入e输入元素 do { //菜单选择 mune(); scanf("%d",&b); switch(b) { case 1://初始化 a=create(); //初始化队列 case 2: //入队 do { printf("\n请输入需要入队的数："); if(e!=NULL) { scanf("%d",&e); enQueue(a,e); } printf("是否继续入队？(是:1 否：0)\n"); scanf("%d",&c); } while(c==1); break; case 3: //出队 c=frontQueue(a); deQueue(a); if(dui!=0) { printf("\n出队为:%d\n",c); } dui=1; break; case 4: //显示队中元素 showQueue(a); break; case 5: return; default: printf("输入错误，程序结束!\n"); return; } } while(a!=5); { return 0; } } （三）各函数的详细设计： Function1: PLinkQueue create(void)//创队 队列的基本操作代码： #include 实验三栈和队列的应用 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 ) /* 栈空 */ 实验报告 课程名称数据结构实验名称栈的基本操作与应用 姓名王灵慧专业班级软工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 《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 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) 广西工学院计算机学院 《数据结构》课程实验报告书实验四队列的基本操作及其应用 学生姓名：李四 学号：2012 班级：计Y124 指导老师：王日凤 专业：计算机学院软件学院 提交日期：2013年6月20日 1．实验目的 1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。 2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。 3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。 2.实验内容 （1）建立一个含n个数据的队列，实现队列的基本操作。包括： ?//1. 初始化,构造一个空队列 void initQueue(Queue &Q) ?//2. 判断队列空, 空则返回true bool QueueEmpty(seqQueue &Q) ?//3. 判断队列满, 满则返回true bool QueueFull(seqQueue &Q) ?//4. 取队头元素, 用x返回队头元素，返回true；空队列则返回false Bool QueueHead(seqQueue &Q, elementType &x) ?//5. 入队列，在队尾插入新元素x （流程图） bool pushQueue (seqQueue &Q, elementType x) ?//6. 出队列，用x带回队头元素，并在队头删除，返回true，队列空则返回false（流程图）bool popQueue (seqQueue &Q, elementType &x) ?//7. 输出队列,从队头到队尾依次输出 void printQueue(seqQueue Q) （2）队列应用：利用队列操作打印杨辉三角形的前n行（如n=7）。 3．实验要求 （1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。 （2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。 （3）实验课上进行答辩。 （4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。 实验编号：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班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0 三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作 五、代码： #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 数据结构实验报告 ----试验三循环队列的基本操作及应用 一、问题描述： 熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。 二、数据结构设计： #define MAXQSIZE 10 //最大队列长度 struct SqQueue { QElemType *base; //初始化动态分配存储空间 Int front; // 头指针，若队列不空，只想对列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的 //下一个位置 }; 三、功能设计： 程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) //构造一个空队列Q Status DestroyQueue(SqQueue &Q) //销毁队列Q,Q不再存在 Status ClearQueue(SqQueue &Q) //将Q清为空队列 Status QueueEmpty(SqQueue Q) //若队列Q为空队列，则 //返回TRUE，否则返回FALSE int QueueLength(SqQueue Q) //返回Q的元素个数，即队列长度Status GetHead(SqQueue Q,QElemType &e)//若队列不空，则用e返回Q的对 //头元素，并返回OK，否则返回ERROR Status EnQueue(SqQueue &Q,QElemType e)//插入元素e为Q的新的队尾元素Status DeQueue(SqQueue &Q,QElemType &e)//若队列不空，则删除Q的队头 //元素，用e返回其值，并返回 //OK，否则返回ERROR Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))//从队头到队尾依次 //对队列Q中每个元素调用函数 //vi()。一旦vi失败，则操作失败四、源程序： // c1.h (程序名) #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、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“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)); 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ 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 栈的顺序表示和实现 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、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 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 栈和队列及其应用 栈和队列通常用来存储程序执行期间产生的一些临时信息。这两种特殊表结构的共同特点是，只做插入和删除，不做查找，而且所有的插入和删除只在端点进行。 栈是一种特殊的表结构，满足先进后出策略（LIFO:last in first out）,栈的插入和删除操作只在同一端点进行。 可以进行插入的端点叫栈顶(top)，另一个端点叫栈底(bottom)。 栈的插入操作又叫进栈(push)或压栈，栈删除操作又叫退栈(pop)或出栈。 栈的结构示意图 注意：进栈和退栈可以不定期地、反复交替进行。 生活中类似栈的应用的例子：装药片的小圆桶，军用子弹卡等。 思考：假设有编号为1，2，3的3辆车，如果按照编号为1，2，3的顺序入栈，那么可能的出栈顺序有几种情况？？？ 栈的存储方式： 1.顺序存储 2.链式存储 栈的常见操作（顺序存储方式实现） 数组s[M]存储一个栈（M代表栈的容量），top变量指示栈顶指针（下标）。 M=6时： 进栈算法： //宏定义 #define M 6 #define EMPTY -1 void pushs(int s[],int &top) { int x,k; cout<<"请输入要进栈的元素值x="; cin>>x; if(top==M-1) { cout<< "栈已经满，进栈失败!"<栈的类型定义与基本操作
数据结构(C语言)队列的基本操作
队列的基本操作代码
实验三 栈和队列的应用
栈的基本操作与应用
栈和队列的基本操作
队列的基本操作及其应用
数据结构_实验三_栈和队列及其应用
顺序栈的基本操作讲解
栈和队列的基本操作的实现
试验 --循环队列的基本操作及应用
数据结构栈的定义及基本操作介绍
栈和队列的基本操作实现及其应用
实验二_栈、队列地实现与应用
用顺序结构表示栈并实现栈地各种基本操作
数据结构 栈和队列的基本操作实现及其应用
栈和队列及其应用7
相关文档
- 数据结构实验二-栈和队列的基本操作与应用
- 第三章栈和队列习题_数据结构
- 《数据结构》(C语言版)第三章 栈和队列
- 栈和队列的基本操作实现及其应用
- 3 栈和队列答案
- 数据结构栈和队列实验报告
- 栈和队列的基本操作实现及其应用
- 实验报告-栈和队列的基本操作
- 实验二-栈和队列(基本操作)
- 实验二栈和队列(基本操作)讲解
- 栈和队列的定义及基本操作
- 实验二 堆栈和队列基本操作的编程实现
- 栈和队列基本操作的实现与应用C++
- 栈和队列练习题
- 栈和队列教案
- 实验二栈队列的实现及应用
- 数据结构第3章栈与队列习题
- 栈和队列基本操作实验报告
- 顺序栈,循环队列的基本操作及其应用
- 栈和队列的基本操作的实现