肇庆学院计算机系实验报告格式
肇庆学院计算机科学系
实验报告
专业:计算机科学与技术班级:科技1班姓名:汪勇学号:201124131103 课程名称:数据结构
学年:2011 --2012 学期: 2 课程类别:专业必修
●实验内容:实验时间:2012 年4月25日
1.编写函数,采用链式存储实现栈的初始化、入栈、出栈操作。
2.编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。
3.编写函数,采用链式存储实现队列的初始化、入队、出队操作。
4.编写函数,采用顺序存储实现队列的初始化、入队、出队操作。
5.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。
●实验目的及要求:
1.掌握栈、队列的思想及其存储实现
2.掌握栈、队列的常见算法的程序实现
●实验内容、方法与步骤:(使用附页填写并附在本页后)
详见附页
●实验结果:
小结:
分数:批阅老师:200 年月日
第页/ 共页
肇庆学院计算机科学系
实验报告(附页)
#include
#include
#define MAXSIZE 256 typedef int datatype; //顺序栈typedef struct
{
datatype data[MAXSIZE];
int top;
}SeqStack;
void menu();
SeqStack * init_SeqStack();
int Empty_SeqStack(SeqStack *S);
int Push_SeqStack(SeqStack *S,datatype x);
int Pop_SeqStack(SeqStack *S,datatype *p);
datatype Top_SeqStack(SeqStack *S); void conversion(int n,int r); //链栈typedef struct node
{
datatype data;
struct node *next;
}StackNode,*LinkStack;
void menu2();
LinkStack Init_LinkStack();
int Empty_LinkStack(LinkStack top); LinkStack Push_LinkStack(LinkStack top,datatype x);
LinkStack Pop_LinkStack(LinkStack top,datatype *s); //顺序队
typedef struct
{
datatype data[MAXSIZE];
int front,rear;
int num;
}C_SeQueue;
void menu3();
C_SeQueue *init_SeQueue();
int In_SeQueue(C_SeQueue *q,datatype x);
int Out_SeQueue(C_SeQueue *q,datatype *p);
int Empty_SeQueue(C_SeQueue *q); //链队
typedef struct qnode
{
datatype data;
struct qnode *next; }QNode;
typedef struct
{ QNode *front,*rear;
}LQueue;
void menu4();
LQueue *Init_LQueue();
void In_LQueue(LQueue *q,datatype x);
int Empty_LQueue(LQueue *q);
int Out_LQueue(LQueue *q,datatype *s);
int main()
{ int temp;
do
{ printf("=============== ===============\n");
printf("\t1.顺序栈\t2.链栈\n\t3.顺序队\t4.链队\n");
printf("请选择:");
scanf("%d",&temp);
int n,m=1;
switch(temp)
{
case 1:
{
SeqStack *S;
/*clrscr();*/
while(m)
{
menu();
scanf("%d",&n);
switch(n)
{
case
1:S=init_SeqStack();break;
case 2:{
int
i,success;
success=Empty_SeqStack(S);
if(success!=1)
{
for(i=0;i<=S->top;i++)
{ printf("%5d",S->data[i]);
}
}
else printf(" empty stack!\n");
break;
}
case 3:{
int
i,success;
datatype x;
printf("please input x:\n");
scanf("%d",&x);
success=Push_SeqStack(S,x);
if(success==1)
{
for(i=0;i<=S->top;i++)
{ printf("%5d",S->data[i]);
}
}
else printf("stack full!\n");
break;
}
case 4:{
int
i,success;
datatype x,*p;
p=&x;
success=Pop_SeqStack(S,p);
if(success==1)
{
for(i=0;i<=S->top;i++)
{ printf("%5d",S->data[i]);
} printf("\n%5d\n",x);
}
else printf("stack empty!\n");
break;
}
case 5:{
int i;
datatype x;
x=Top_SeqStack(S);
if(x!=-1)
{
for(i=0;i<=S->top;i++)
{ printf("%5d",S->data[i]);
} printf("\n%5d\n",x);
}
else printf("stack empty!\n");
break;
}
case 0:m=0;
}
}
break;
}
case 2:
{
LinkStack
L=NULL;
while(m)
{
menu2();
scanf("%d",&n);
switch(n)
{
case 1: L=Init_LinkStack();
break;
case 2:{ StackNode *p=L->next;
int flag;
flag=Empty_LinkStack(L);
if(flag==0)
{ while(p)
{ printf("%5d",p->data);
p=p->next;
}
}
else printf("stack empty!\n");
break;
}
case 3:{
LinkStack p;
datatype x;
printf("please input a value x:\n");
scanf("%d",&x);
L=Push_LinkStack(L,x);
p=L->next;
while(p)
{ printf("%5d",p->data);
p=p->next;
} break;
}
case 4:{ datatype x,*s;
LinkStack p;
s=&x;
L=Pop_LinkStack(L,s);
p=L->next;
while(p)
{ printf("%5d",p->data);
p=p->next;
}
printf("\n%5d\n",x);
break;
}
case
0:m=0;
}
}
break;
}
case 3:
{
C_SeQueue *Q;
/*clrscr();*/
while(m)
{
menu3();
scanf("%d",&n);
switch(n)
{
case
1:Q=init_SeQueue();break;
case 2:{
int i,flag,number;
datatype x;
printf("please input x:\n");
scanf("%d",&x);
flag=In_SeQueue(Q,x);
number=Q->num;
if(flag==1)
{ for(i=(Q->front+1)%MAXSIZE;n umber>0;number--,i=(i+1)%MAXSIZ E)
{
printf("%5d",Q->data[i]);
}
}
else printf("queue full!\n");
break;
}
case 3:{
int i,flag,number;
datatype x,*p;
p=&x;
flag=Out_SeQueue(Q,p);
number=Q->num;
if(flag==1)
{ for(i=(Q->front+1)%MAXSIZE;n umber>0;number--,i=(i+1)%MAXSIZ E)
{ printf("%5d",Q->data[i]);
} printf("\n%5d\n",x);
}
else printf("queue empty!\n");
break;
}
case 4:{
int i,flag,number;
flag=Empty_SeQueue(Q);
number=Q->num;
if(flag!=1)
{ for(i=(Q->front+1)%MAXSIZE;n umber>0;number--,i=(i+1)%MAXSIZ E)
{ printf("%5d",Q->data[i]);
}
}
else printf("queue empty!\n");
break;
}
case
0:m=0;
}
}
break;
}
case 4:
{
LQueue
*Q=NULL;
/*clrscr();*/
while(m)
{
menu4();
scanf("%d",&n);
switch(n)
{
case 1: Q=Init_LQueue();
break;
case 2:{ datatype x;
QNode *p;
printf("please input a value x:\n");
scanf("%d",&x);
In_LQueue(Q,x);
p=Q->front->next;
while(p!=NULL)
{ printf("%5d",p->data);
p=p->next;
} break;
}
case 3:{
int flag;
QNode *p;
flag=Empty_LQueue(Q);
p=Q->front->next;
if(flag!=1)
{ while(p!=NULL)
{ printf("%5d",p->data);
p=p->next;
}
}
else printf("queue empty!\n");
break;
}
case 4:{
int flag;
datatype x,*s;
QNode *p;
s=&x;
flag=Out_LQueue(Q,s);
p=Q->front->next;
if(flag==1)
{ while(p!=NULL)
{ printf("%5d",p->data);
p=p->next;
} printf("\n%5d\n",x);
}
else printf("queue empty!\n");
break;
}
case 0:m=0;
}
}
break;
}
}
}while(temp!=0);
return 0;
}
void menu()
{
/*clrscr();*/
printf("\n你选择的是顺序栈\n请选择一下功能:\n");
printf("\t\t1.initialization\n\n");
printf("\t\t2.empty\n\n");
printf("\t\t3.push stack\n\n");
printf("\t\t4.pop stack\n\n");
printf("\t\t5.get element\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
SeqStack * init_SeqStack()
{
SeqStack *S;
S=(SeqStack*)malloc(sizeof(SeqSt ack));
S->top=-1;
return S;
}
int Empty_SeqStack(SeqStack *S) {
if(S->top==-1)
return 1;
else
return 0;
}
int Push_SeqStack(SeqStack *S,datatype x)
{
if(S->top==MAXSIZE-1)
{
return(0);
}
else
{
S->top++;
S->data[S->top]=x;
return(1);
}
}
int Pop_SeqStack(SeqStack *S,datatype *p)
{
if(Empty_SeqStack(S)==1)
{
return 0;
}
else
{
*p=S->data[S->top];
S->top--;
return 1;
}
}
datatype Top_SeqStack(SeqStack *S) {
if(Empty_SeqStack(S)==1)
return -1;
else
return(S->data[S->top]);
}
void menu2()
{
/*clrscr();*/
printf("\n你选择的是链栈\n请选择一下功能:\n");
printf("\t\t1.stack zhi kong\n\n");
printf("\t\t2.empty stack\n\n");
printf("\t\t3.push stack\n\n");
printf("\t\t4.pop stack\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
LinkStack Init_LinkStack()
{
StackNode *L;
L=(StackNode*)malloc(sizeof(Stac kNode));
L->data=-32767;
L->next=NULL;
return L;
}
int Empty_LinkStack(LinkStack top) {
if(top->next==NULL)
return 1;
else
return 0;
}
LinkStack Push_LinkStack(LinkStack top,datatype x)
{
StackNode *s;
s=(StackNode*)malloc(sizeof(Stac kNode));
s->data=x;
s->next=top->next;
top->next=s;
return top;
}
LinkStack Pop_LinkStack(LinkStack top,datatype *s)
{
StackNode *p;
int j=0;
p=top->next;
if(p!=NULL)
{
*s=p->data;
top->next=p->next;
free(p);
}
return top;
}
void menu3()
{
/*clrscr();*/
printf("\n你选择的是顺序队\n请选择一下功能:\n");
printf("\t\t1.initialization\n\n");
printf("\t\t2.into queue\n\n");
printf("\t\t3.out queue\n\n");
printf("\t\t4.empty queue\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
C_SeQueue *init_SeQueue()
{
C_SeQueue *q;
q=(C_SeQueue*)malloc(sizeof(C_ SeQueue));
q->front=q->rear=MAXSIZE-1;
q->num=0;
return q;
}
int In_SeQueue(C_SeQueue *q,datatype x)
{
if(q->num==MAXSIZE)
{
return(-1);
}
else
{
q->rear=(q->rear+1)%MAXSIZE ;
q->data[q->rear]=x;
q->num++;
return(1);
}
}
int Out_SeQueue(C_SeQueue *q,datatype *p)
{
if(q->num==0)
{
return -1;
}
else
{
q->front=(q->front+1)%MAXSIZ E;
*p=q->data[q->front];
q->num--;
return 1;
}
}
int Empty_SeQueue(C_SeQueue *q) {
if(q->num==0)
return 1;
else
return 0;
}
void menu4()
{
/*clrscr();*/
printf("\n你选择的是链队\n请选择一下功能:\n");
printf("\t\t1.jian you tou jie dian queue\n\n");
printf("\t\t2.into queue\n\n");
printf("\t\t3.empty queue\n\n");
printf("\t\t4.out queue\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
LQueue *Init_LQueue()
{
LQueue *q;
QNode *p;
q=(LQueue*)malloc(sizeof(LQueu e));
p=(QNode*)malloc(sizeof(QNode) );
p->next=NULL;
q->front=q->rear=p;
return q;
}
void In_LQueue(LQueue *q,datatype x)
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode) );
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
int Empty_LQueue(LQueue *q)
{
if(q->front==q->rear)
return 1;
else
return 0;
}
int Out_LQueue(LQueue *q,datatype *s)
{
QNode *p;
if(Empty_LQueue(q)==1)
{
return 0;
}
else
{
p=q->front->next;
q->front->next=p->next;
*s=p->data;
free(p);
if(q->front->next==NULL)
q->rear=q->front;
return 1;
}
}
分数:批阅老师:200 年月日
实验编号: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 << "你的选择是:" ; } 链式储存: 代码部分: 栈"<
(封面) 学生实验报告 学院:国际经贸学院 课程名称:数据结构 专业班级: 09电子商务 姓名: 学号: 学生实验报告
(经管类专业用) 一、实验目的及要求: 1、目的 通过实验,实现顺序栈的各种基本运算。 2、内容及要求 编写一个程序,实现顺序栈的各种基本运算,并在此基础上设计一个主程序完成下列功能: (1)初始化栈S。 (2)判断栈S是否非空。 (3)依次进栈元素a,b,c,d,e。 (4)判断栈S是否非空。 (5)输出栈的长度。 (6)输出从栈顶到栈底的元素。 (7)输出出栈序列; (8)判断链栈S是否为空; (9)释放链栈 二、仪器用具: 三、实验方法与步骤:
一、查阅顺序栈等相关资料,熟悉顺序栈基本概念和流程 二、“开展”顺序栈实验流程 三、整理实验数据和文档,总结实验的过程,编写实验报告 四、实验结果与数据处理: 1、顺序栈的代码: #include
实验二栈和队列 一、实验目的 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.熟悉队列这种特殊线性结构的特性; 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理: 堆栈顺序存储结构下的基本算法; 堆栈链式存储结构下的基本算法; 队列顺序存储结构下的基本算法;队列链式存储结构下的基本算法;实验内容: 3-18链式堆栈设计。要求 (1)用链式堆栈设计实现堆栈,堆栈的操作集合要求包括:初始化Stacklnitiate (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个数据元素入栈,然后出栈并在屏幕上显示出栈的数据元素。 3-19对顺序循环队列,常规的设计方法是使用対尾指针和对头指针,对尾指针用于指示当 前的対尾位置下标,对头指针用于指示当前的対头位置下标。现要求: (1)设计一个使用对头指针和计数器的顺序循环队列抽象数据类型,其中操作包括:初始化,入队列,出队列,取对头元素和判断队列是否为空; (2)编写一个主函数进行测试。 实验结果: 3-18 typedef struct snode { DataType data; struct snode *n ext; } LSNode; /* 初始化操作:*/
实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________
一、实验内容: 本次实验主要内容是表达式求值,主要通过栈和队列来编写程序,需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用,其中包含优先级的判断。 二、设计思想 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班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: 1 ?熟悉掌握栈的定义、结构及性质; 2. 能够实现创建一个顺序栈,熟练实现入栈、出栈等栈的基本操作; 3?了解和掌握栈的应用。 二、实验环境: Microsoft Visual C++ 6.0
三、实验内容及要求: 栈是一种特殊的线性表,逻辑结构和线性表相同,只是其运算规则有更多的限制,故又称为受限的线性表。 建立顺序栈,实现如下功能: 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计: 1、通过循环,由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数,完成子函数模块如下。 3、调用子函数,实现菜单调用功能,完成顺序表的相关操作
五、代码: #include
实验一进程管理 一、目的 进程调度是处理机管理的核心内容。本实验要求编写和调试一个简单的进程调度程序。通过本实验加深理解有关进程控制块、进程队列的概念,并体会和了解进程调度算法的具体实施办法。 二、实验内容及要求 1、设计进程控制块PCB的结构(PCB结构通常包括以下信息:进程名(进程ID)、进程优先数、轮转时间片、进程所占用的CPU时间、进程的状态、当前队列指针等。可根据实验的不同,PCB结构的内容可以作适当的增删)。为了便于处理,程序中的某进程运行时间以时间片为单位计算。各进程的轮转时间数以及进程需运行的时间片数的初始值均由用户给定。 2、系统资源(r1…r w),共有w类,每类数目为r1…r w。随机产生n进程P i(id,s(j,k),t),0<=i<=n,0<=j<=m,0<=k<=dt为总运行时间,在运行过程中,会随机申请新的资源。 3、每个进程可有三个状态(即就绪状态W、运行状态R、等待或阻塞状态B),并假设初始状态为就绪状态。建立进程就绪队列。 4、编制进程调度算法:时间片轮转调度算法 本程序用该算法对n个进程进行调度,进程每执行一次,CPU时间片数加1,进程还需要的时间片数减1。在调度算法中,采用固定时间片(即:每执行一次进程,该进程的执行时间片数为已执行了1个单位),这时,CPU时间片数加1,进程还需要的时间片数减1,并排列到就绪队列的尾上。 三、实验环境 操作系统环境:Windows系统。 编程语言:C#。 四、实验思路和设计 1、程序流程图
2、主要程序代码 //PCB结构体 struct pcb { public int id; //进程ID public int ra; //所需资源A的数量 public int rb; //所需资源B的数量 public int rc; //所需资源C的数量 public int ntime; //所需的时间片个数 public int rtime; //已经运行的时间片个数 public char state; //进程状态,W(等待)、R(运行)、B(阻塞) //public int next; } ArrayList hready = new ArrayList(); ArrayList hblock = new ArrayList(); Random random = new Random(); //ArrayList p = new ArrayList(); int m, n, r, a,a1, b,b1, c,c1, h = 0, i = 1, time1Inteval;//m为要模拟的进程个数,n为初始化进程个数 //r为可随机产生的进程数(r=m-n) //a,b,c分别为A,B,C三类资源的总量 //i为进城计数,i=1…n //h为运行的时间片次数,time1Inteval为时间片大小(毫秒) //对进程进行初始化,建立就绪数组、阻塞数组。 public void input()//对进程进行初始化,建立就绪队列、阻塞队列 { m = int.Parse(textBox4.Text); n = int.Parse(textBox5.Text); a = int.Parse(textBox6.Text); b = int.Parse(textBox7.Text); c = int.Parse(textBox8.Text); a1 = a; b1 = b; c1 = c; r = m - n; time1Inteval = int.Parse(textBox9.Text); timer1.Interval = time1Inteval; for (i = 1; i <= n; i++) { pcb jincheng = new pcb(); jincheng.id = i; jincheng.ra = (random.Next(a) + 1); jincheng.rb = (random.Next(b) + 1); jincheng.rc = (random.Next(c) + 1); jincheng.ntime = (random.Next(1, 5)); jincheng.rtime = 0;
实验二栈、队列的实现及应用 实验课程名:数据结构与算法 专业班级:学号::
/*构造空顺序栈*/ 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
实验三栈和队列 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
一.实验项目名称 循环队列和链式队列的创建 二、实验目的 1、掌握队列的特点 (先进先出 FIFO) 及基本操作 ,如入队、出队等, 2、队列顺序存储结构、链式存储结构和循环队列的实现,以便在 实际问题背景下灵活应用。 三、实验内容 1.链式队列的实现和运算 2.循环队列的实现和运算 四、主要仪器设备及耗材 VC++6.0 运行环境实现其操作 五.程序算法 (1)循环队列操作的算法 1>进队列 Void enqueue (seqqueue &q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout<< ” overflow”; else { q.rear=(q.rear+1)%maxsize; // 编号加 1 或循环回第一个单元 q.queue[q.rear]=x; } } 2>出队列 Void dlqueue(seqqueue &q ) { if (q.rear= =q.front)cout<< ” underflow”; else q.front =(q.front+1)%maxsize; } 3>取对头元素
elemtype gethead(seqqueue q ) { if(q.rear= =q.front) { cout<<” underflow;” return NULL;} else return q.queue[(q.front+1)%maxsize]; //front 指向队头前一个位置 } 4>判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) else return 0; reurn 1; } (2).链队列操作的算法 1>.链队列上的初始化 void INIQUEUE( linkqueue&s) {link *p; p=new link; p->next=NULL;//p 是结构体指针类型,用 s.front=p;//s 是结构体变量,用. s.rear=p;//头尾指针都指向头结点 -> } 2>.入队列 void push(linkqueue &s, elemtype x) { link*p;//p 是结构体指针类型,用-> p=new link; p->data=x; p->next=s.rear->next;//s 是结构体变量,用s.rear->next=p; s.rear=p;//插入最后 . } 3>判队空 int empty( linkqueue s ) {if (s.front= =s.rear) return 1; else return 0; } 4>.取队头元素 elemtype gethead( linkqueue s ) { if (s.front= =s.rear) else retuen return NULL; s.front->next->data; }
第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 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={
百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名:数据结构与算法 专业班级:_ 学号:__________ 姓名: _ 实验时间: ____ 实验地点:指导教师:冯珊__________ 一、实验目的 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
《数据结构与算法》实验报告
一、实验内容 1.栈的实现 2.顺序栈的基本操作 二、实验目的及要求 熟悉栈的基本操作在顺序栈的实现。通过具体应用实例在复习高级编程语言使用方法的基础上初步了解数据结构的应用。 三、设计分析与算法描述 顺序栈的存储结构: typedef struct { int elem[Stack_Size]; int top; }SeqStack; void InitStack(SeqStack *S)//构造一个空栈(初始化) int Push(SeqStack *S,int x)//进栈 int Pop(SeqStack *S,int *x)//出栈 int IsEmpty(SeqStack *S)//判栈是否空 int IsFull(SeqStack *S)//判栈是否满 int GetTop(SeqStack *S,int *x)//读栈顶 四、附件:带注释的源程序 #include"iostream.h" #define Stack_Size 50 #define false 0 #define true 1
typedef struct { int elem[Stack_Size]; int top; }SeqStack; void InitStack(SeqStack *S)//构造一个空栈(初始化) { S->top=-1; } int Push(SeqStack *S,int x)//进栈 { if(S->top==Stack_Size-1)//栈已满 return (false); S->top++; S->elem[S->top]=x; return (true); } int Pop(SeqStack *S,int *x)//出栈 { if(S->top==-1)//栈已空 return (false); else { *x=S->elem[S->top];
实验二栈和队列 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)熟悉C语言的上机环境,进一步掌握C语言的结构特点。 (2)掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三:队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空); 2、入队; 3、出队; 4、求队列长度; 5、判断队列是否为空; 【源程序】 #include
Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q)
数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 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
陕西科技大学实验报告 班级信工082 学号200806030202 姓名李霄实验组别 实验日期2010-12-20 室温报告日期2010-12-20 成绩 报告内容:(目的和要求,原理,步骤,数据,计算,小结等) 实验名称:实验三队列的表示及实现 实验目的: 1、通过实验进一步理解队列的“先进先出”特性。 2、掌握队列的逻辑结构及顺序存储结构和链式存储结构。 3、熟练运用C语言实现队列的基本操作。 4、灵活运用队列解决实际问题。 实验内容: 1、实现链队列,并编写主函数进行测试。测试方法为:依次10、20、 30、40,然后,出对3个元素。再次入队50、60,然后出队3个元 素。查看屏幕上显示的结果是否与你分析的结果一致。 2、在1的基础上,再出队1个元素。查看屏幕上显示的结果是否与你 分析的结果一致。 3、编写主函数比较取队头元素操作和出队操作。 实验学时:2学时 实验程序 #include "stdio.h" #include "conio.h" typedef int DataType; typedef struct { DataType data; struct QNode* next; }LQNode,*PQNode; typedef struct { PQNode front,rear; }LinkQueue; int InitQueue(LinkQueue *Q) { Q->front=Q->rear=(PQNode)malloc(sizeof(LQNode));
if (!Q->front){printf("errors\n");return 0;} Q->front->next=NULL; return 1; } int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } int EnQueue(LinkQueue *Q,DataType e) { PQNode p; p=(PQNode)malloc(sizeof(LQNode)); if(!p) { printf("\n\nerrors\n\n"); return 0; } p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return 1; } int DeQueue(LinkQueue *Q,DataType *e) { PQNode p; if( Q->front==Q->rear) { printf("\nerrors\n");