实验报告一--链接栈与顺序队列的基本运算
课程实验报告
题目 链接栈与顺序队列的基本运算
班级 2010信息与计算科学班 姓名笑嘻嘻小 学号 笑嘻嘻 完成日期 笑嘻嘻小
㈠实验要求: 编程实现链接栈与顺序队列的基本运算。
链接栈:插入元素,删除栈顶元素,读出栈顶元素,判断栈是否为空。
顺序队列:队列的插入,队列的删除,读队头元素,判断队列是否为空。
实验目的:熟练掌握链接栈,顺序队列的基本运算。
链接栈的结点结构与单链表的结点结构完全相同,即,将链接栈组织成单链表形
式。注意,链接栈中指针的方向是从栈顶指向栈底。
顺序队列是用顺序存储方法存储的队列。分配一片连续的存储空间,存放队列中
的表目,并用两个变量分别指向队头和队尾。
㈡I. 链接栈的基本运算
I .1实验代码:#include
#include
#define LEN sizeof(struct node)
#define NULL 0
struct node
{int info;
struct node*link;
};
struct linklist
{struct node*T;
};
//*主函数*//
void main()
{int x;
struct linklist L;
L.T=(struct node*)malloc(LEN);
L.T=NULL;
struct linklist push(struct linklist L,int x);
struct linklist pop(struct linklist L);
int top(struct linklist L);
int sempty(struct linklist L); /*函数声明*/
for(x=10;x
L=push(L,x); /*向栈顶插入五个元素10,20,30,40,50*/ printf("向栈顶插入五个元素后,");
printf("栈顶元素为%d。\n",L.T->info);
for(x=1;x
L=pop(L);
printf("连续删除链接栈3个元素后,");
printf("栈顶元素为%d。\n",L.T->info);
x=top(L);
printf("读出的栈顶元素为%d。\n",x);
if(sempty(L))printf("调用sempty (L )函数,栈已空。\n");
else printf("调用sempty (L )函数,栈不空。\n");}
/*栈的插入函数*/
struct linklist push(struct linklist L,int x)
{struct node*p;
p=(struct node*)malloc(LEN);
p->info=x;
p->link=L.T;
L.T=p;
return (L); }
/*栈的删除函数*/
struct linklist pop(struct linklist L)
{struct node*p;
if(L.T==NULL)printf("栈空。\n");
else {p=L.T;L.T=L.T->link;free(p);}
return (L);}
/*读出栈顶元素*/
int top(struct linklist L)
{if(L.T==NULL){printf("栈空。\n");return 0;}
else return(L.T->info);}
/*判断栈是否为空*/
int sempty(struct linklist L)
{if(L.T==NULL)return(1);
else return(0);}
I.2
实验结果:
I.3调试过程及其分析
①T 始终指向的是栈顶元素,因此,T 总是指向新插入的结点。
②在进行栈的删除,读栈顶元素,判断栈是否为空运算时,首先要判断栈是否为空。
II .顺序队列的基本运算
II .1实验代码:#include
#define m0 20
struct queue
{int q[m0+1];
int f,r;};
//*主函数*//
int main()
{struct queue qu,*p;
int x;
p=&qu;
qu.f=1;
qu.r=1;
void enq(struct queue*p,int x);
void deq(struct queue*p);
int front(struct queue qu);
int qempty(struct queue qu); /*函数声明*/
for(x=10;x
enq(p,x);
printf("向顺序队列依次插入5个元素后,");
printf("队头元素为%d,队尾元素为%d。\n",qu.q[qu.f],qu.q[qu.r-1]); for(x=1;x
deq(p);
printf("连续删除顺序队列的3个元素后,");
printf("队头元素为%d,队尾元素为%d。\n",qu.q[qu.f],qu.q[qu.r-1]); x=front(qu);
printf("读出的队头元素为%d。\n",x);
if(qempty(qu))printf("调用函数qempty (qu ),顺序队列已空。\n");
else printf("调用函数qempty (qu ),顺序队列不空。\n");
return 0;}
/*顺序队列的插入函数*/
void enq(struct queue*p,int x)
{if((p->r%m0)+1==p->f)printf("队列已满。\n");
else {p->q[p->r]=x;p->r=(p->r%m0)+1;}
}
/*顺序队列的删除函数*/
void deq(struct queue*p)
{if(p->r==p->f)printf("队列已空。\n");
else p->f=(p->f%m0)+1;}
/*读顺序队列队头元素*/
int front(struct queue qu)
{if(qu.r==qu.f){printf("顺序队列已空。\n");return 0;}
else return(qu.q[qu.f]);}
/*判断顺序队列是否为空*/
int qempty(struct queue qu)
{if(qu.r==qu.f)return(1);
else return (0);}
II.2实验结果:
II.3调试过程及其分析
顺序队列会出现“假溢出”现象,该程序使用的是循环队列来解决此现象。循环队列即将顺序队列的存储区首尾相接,臆造为一个环状空间。