顺序栈,循环队列的基本操作及其应用

数据结构实验报告贰

题目:顺序栈,循环队列的基本操作及其应用

班级：信息一班

姓名：

学号：

得分：____ （满分5分）

//顺序栈

#include

#define OK 1

#define ERROR 0

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

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

typedef int Status;

typedef int SElemType;

typedef struct

{

SElemType *base; //数组首地址,在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针

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

}SqStack;

Status InitStack(SqStack &S)

{

//构造一个空栈S

S.base=new SElemType[STACK_INIT_SIZE];

if(!S.base) return ERROR; //储存分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}//InitStack

int StackLength(SqStack S)

{

//返回S的元素个数，即栈的长度

return (S.top-S.base);

}//StackLength

void StackTraverse(SqStack S)

{

if(S.top )

{

for(int i=0;i

cout<< *(S.base+i ) <<"\t";

}

else cout<<"此顺序栈为空！"<

}//StackTraverse

int GetTop(SqStack S, SElemType &e)

{

//若栈不空，则用e返回S的栈顶元素

//否则返回ERROR

if(S.top==S.base) return ERROR; //栈空

e=*(S.top-1);

return e;

}//GetTop

Status StackEmpty(SqStack S)

{

//若栈空，返回OK；否则返回ERROR。

if(S.top==S.base) return OK; //栈空

else return ERROR;

}//StackEmpty

Status Push(SqStack &S, SElemType e)

{

//插入元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize)

{//栈满，追加空间

S.base=new SElemType[S.stacksize+STACKINCREMENT];

if(! S.base) return ERROR;

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

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}//Push

int Pop(SqStack &S, SElemType &e)

{

//若栈不空，则删除栈顶元素，用e返回其值

//否则返回ERROR

if(S.top==S.base) return ERROR; //栈空

e=*--S.top;

return e;

}//Pop

void main()

{

int m ;

SqStack S;

cout<<"栈的初始化"<

cout<<"判栈空"<

cout<<"数字1、2、3、4、5分别进栈"<

Push(S,1);

Push(S,2);

Push(S,3);

Push(S,4);

Push(S,5);

cout<<"栈的遍历"; StackTraverse(S );cout<

cout<<"栈的长度为"<

cout<<"此时栈顶元素为"<

cout<<"数字6进栈"<

cout<<"此时栈顶元素为"<

cout<<"删除栈顶元素并返回"<

cout<<"此时栈顶元素为"<

}

//循环队列

#include

#define OK 1

#define ERROR 0

#define MAXQSIZE 100 //队列数组的大小

typedef int QElemType;

typedef int Status;

typedef struct

{

QElemType *base; //队列数组首地址

int front; //队头指针，指向队头元素

int rear; //队尾指针，指向队尾元素的下一个位置}SqQueue;

Status InitQueue(SqQueue &Q)

{

//初始化一个空队列

Q.base=new QElemType[MAXQSIZE];

if(!Q.base) return ERROR;

Q.front=Q.rear=0;

return OK;

}//InitQueue

bool QueueEmpty(SqQueue Q)

{

return Q.front==Q.rear ? true : false;

}//QueueEmpty

int QueueLength(SqQueue Q)

{

return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;

}//QueueLength

void QueueTraverse(SqQueue Q)

{

if(!(Q.front==Q.rear) )

{

for(int i=0;i< (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE ;i++) cout<< *(Q.base+i ) <<"\t";

}

else cout<<"此循环队列为空！"<

}//QueueTraverse

Status EnQueue(SqQueue &Q, int e)

{

//入队操作,元素e成为新的队尾元素

if(Q.front==(Q.rear+1)%MAXQSIZE)

return ERROR; //队列已满

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1) % MAXQSIZE; //修改队尾指针

return OK;

}//EnQueue

int DeQueue(SqQueue &Q, int &e)

{

//用e返回队头元素的值，队头元素出队，

if(Q.front==Q.rear) return ERROR; //队空

e=Q.base[Q.front];

Q.front=(Q.front+1)% MAXQSIZE; //修改队头指针

return e;

}//DeQueue

Status DestroyQueue(SqQueue &Q)

{

delete(Q.base);

return OK;

}//DestroyQueue

void main()

{

int e;

SqQueue Q;

cout<<"队列的初始化"<

cout<<"判断队列是否为空"<

cout<<"数字1、2、3、4、5分别入队"<

EnQueue( Q, 1);

EnQueue( Q, 2);

EnQueue( Q, 3);

EnQueue( Q, 4);

EnQueue( Q, 5);

cout<<"队列的长度为"<

cout<<"队列的遍历";QueueTraverse(Q);cout<

cout<<"1出队"<

cout<<"再次遍历";QueueTraverse(Q);cout<

cout<<"销毁队列"<

}

//栈的应用之数制转换

#include

#define OK 1

#define ERROR 0

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

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

typedef int Status;

typedef int SElemType;

typedef struct

{

SElemType *base; //数组首地址,在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针

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

}SqStack;

Status InitStack(SqStack &S)

{

//构造一个空栈S

S.base=new SElemType[STACK_INIT_SIZE];

if(!S.base) return ERROR; //储存分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}//InitStack

Status StackEmpty(SqStack S)

{

//若栈空，返回OK；否则返回ERROR。

if(S.top==S.base) return OK; //栈空

else return ERROR;

}//StackEmpty

Status Push(SqStack &S, SElemType e)

{

//插入元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize)

{//栈满，追加空间

S.base=new SElemType[S.stacksize+STACKINCREMENT];

if(! S.base) return ERROR;

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

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}//Push

int Pop(SqStack &S, SElemType &e)

{

//若栈不空，则删除栈顶元素，用e返回其值

//否则返回ERROR

if(S.top==S.base) return ERROR; //栈空

e=*--S.top;

return e;

}//Pop

void conversion ()

{

int N,e;

SqStack S;

InitStack(S); // 构造空栈

cin>>N; //输入一个十进制数

while (N)

{

Push(S, N % 8); // "余数"入栈

N = N/8; //非零"商"继续运算

}

while (!StackEmpty(S))

{ //

和"求余"所得相逆的顺序输出八进制的各位数

Pop(S,e);

cout<

}

} // conversion

void main()

{

cout<<"输入一个十进制数";

conversion (); cout<<" 此为转换所得八进制数"<

栈的顺序表示和实现

（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 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]; printf("\n栈顶元素为:%d\n",x); return(x); } else { printf("Underflow! \n"); return(0); } } /*遍历顺序表*/ void OutStack(SqStack *p) { int i;

栈的类型定义与基本操作

循环队链的出队 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; } 顺序栈的类型定义与基本操作：

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

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

C语言之循环队列的基本操作

1）：循环队列的基本操作 #include #include #define OK 1 #define ERROR 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等typedef int QElemType; #define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1) typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; Status InitQueue(SqQueue &Q) { Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) { return ERROR; } Q.front=Q.rear=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue &Q, QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }

顺序栈的基本操作讲解

遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范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 {

栈的基本操作与应用

实验报告 课程名称数据结构实验名称栈的基本操作与应用 姓名王灵慧专业班级软工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 #include #include #define true 1 #define null 0 #define ok 1 #define error 0 #define overflow -1 #define stack_init_size 100 #define stackincrement 10 using namespace std; typedef int selemtype; typedef int status; typedef struct { selemtype *base; selemtype *top; int stacksize; } sqstack; status initstack(sqstack &s) { s.base=(selemtype *)malloc(stack_init_size * sizeof(selemtype)); if(!s.base)exit(overflow);

栈和队列的基本操作

《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 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班 学号： 2731 学生姓名：邓雪 指导教师：杨红颖 完成时间： 2015年12月25号

一、实验目的： 1．熟悉掌握队的定义、结构及性质；? 2. 熟练掌握循环队列的操作及应用,掌握循环队列的入队和出队等基本操作。? 3. 加深对队列结构的理解，逐步培养解决实际问题的编程能力 二、实验环境： Windows Microsoft Visual c++ 三、实验内容及要求： 掌握队列的概念及性质，并建立顺序队，实现如下功能： 1.建立一个顺序队 2.输出队 3.求队长 4.判队空 5.取队头 6.入队 7.出队 8. 清空栈 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序队。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作。

#include <> #include <> #define maxsize 1024 typedef int datatype; //定义结构体 typedef struct { datatype data[maxsize]; int front,rear; }sequeue; sequeue *sq; //建立顺序队 sequeue *SET() { sequeue *sq; datatype x; sq=(sequeue *)malloc(sizeof(sequeue)); sq->front=maxsize-1; sq->rear=maxsize-1; printf("请输入要存入的结点值(以0结尾)\n"); scanf("%d",&x); while(x!=0) { sq->rear=(sq->rear+1)%maxsize; sq->data[sq->rear]=x; scanf("%d",&x); } printf("顺序队输入成功\n\n"); return sq; }

栈的操作(实验报告)

实验三栈和队列 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 #include #define MAXNUM 20

栈和队列的基本操作的实现

封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______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 # include # include #define STACKINITISIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 # define OVERFLOW -2 typedef int SElemtype; typedef int status; typedef struct { SElemtype *base; SElemtype *top; int stacksize; }sqstack; void Initstack (sqstack *s) { (*s).base = (SElemtype *)malloc(STACKINITISIZE * sizeof (SElemtype)); if(!(*s).base) exit(OVERFLOW);

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

北京理工大学珠海学院实验报告 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)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (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、在演示程序中，出现的元素以数字出现定义为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)元素删除

用顺序结构表示栈并实现栈地各种基本操作

栈的顺序表示和实现 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->toptop=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");

队列的基本操作代码

队列的基本操作代码： #include #include #define MAXQSIZE 100 #define OVERFLOW 0 #define ERROR 0 #define OK 1 typedef int QElemType; typedef int Status; typedef struct { QElemType *base; int front; int rear; int tag; }SqQueue; Status InitQueue(SqQueue &Q) { Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) exit(OVERFLOW);//存储分配失败 Q.front=Q.rear=0; tag=0; return OK; } int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;//返回Q的元素个数，即队列的长度} Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;//队列满 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front];

实验4顺序循环队列基本操作

实验4: 顺序循环队列基本操作 一、实验目的 1．熟悉并能实现顺序循环队列的定义和基本操作。 2．了解用队列解决实际应用问题。 二、实验要求 1．进行队列的基本操作时要注意队列“先进先出”的特性。 2．复习关于栈操作的基础知识。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三、实验内容 1．任意输入队列长度和队列中的元素值，构造一个队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。 2．约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i 上的人开始报数，数到m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为 Josephus 问题。 例如：当n=8,m=4,i=1时，得到的新序列为： 4，8，5，2，1，3，7，6 编写程序选择循环队列（也可换为自己熟悉的数据结构）作为存储结构模拟整个过程，并依次输出出列的各人的编号。 3．(选做实验)设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 程序编写提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

栈和队列的基本操作实现及其应用

实验二栈和队列的基本操作实现及其应用 一_一、实验目的 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 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<<"存储分配失败!!!"<

实验三 栈的基本操作及应用

实验三栈的基本操作及应用 实验时间：第7周 实验目的：掌握栈的初始化、判空、出栈、入栈等基本操作 实验要求： 1．认真阅读和掌握教材上和本实验相关的算法。 2．上机将相关算法实现。 3．实现下面实验内容要求的功能，并输出程序的运行结果，结合程序进行分析。 实验内容： 利用栈的基本操作编程实现将任意一个十进制整数N转换为d进制整数。 算法提示： 1、定义栈的顺序存取结构（也可以用链栈） 2、分别定义栈的基本操作（初始化栈、判空、出栈、入栈等） 3、定义一个函数用来实现数制转换问题： 十进制整数N和d作为形参 初始化栈 只要N不为０重复做下列动作 将N％d入栈 N = N/d 只要栈不为空重复做下列动作 栈顶元素出栈 输出栈顶元素 注意：如果你完成上述任务还有时间，仔细分析、单步调试下面程序。目的有两个：一是消化、分析C++中的引用；二是练习使用VC中的调试器。 #include void fun(int &a)

{ a=8; } void main() { int x=1; //int &y=x; fun(x); //x=4; cout << x <