软件技术基础栈和队列上机报告.docx

软件技术基础栈和队列上机报告.docx

《软件技术基础栈和队列上机报告.docx》由会员分享，可在线阅读，更多相关《软件技术基础栈和队列上机报告.docx（16页珍藏版）》请在冰点文库上搜索。

软件技术基础栈和队列上机报告

姓名：

阚姗蕾学号：

2010012030037

上机实验三

ex3_1：

一、程序流程说明

链栈

1）链栈结点类型定义为：

typedefstructnode

{

intdata;

structnode*next;

}node_type;

2）编写进栈函数push

3）编写出栈函数pop

4）编写main函数，首先建立一空链栈；

调用进栈函数，将从键盘输入的数据元素逐个进栈，输入0结束；显示进栈后的数据元素；

调用两次出栈函数，显示出栈后的数据元素。

二、程序代码

#include

#include

//定义链栈

typedefstructnode_type

{

intdata;

structnode_type*next;

}node_type;

typedefstructstack_type

{

node_type*top;

intlength;

}stack_type;

//进栈函数

voidpush（stack_type*s,intnewnode）

{

node_type*p;

p=（node_type*）malloc（sizeof（node_type））;

p->data=newnode;

p->next=s->top;

s->top=p;

s->length++;

}

//出栈函数

intpop（stack_type*s）

{

node_type*p;

intx;

if（s->top==NULL）

{

printf（"ThestackisNULL!

\n"）;

return（0）;

}

else

{

x=s->top->data;

p=s->top;

s->top=s->top->next;

free（p）;

s->length--;

return（x）;

}

}

//遍历并输出

voidshowstack（stack_type*s）

{

inti=0;

intle;

stack_type*s1;

node_type*p;

if（s->length<=0）

{

printf（"Nodata!

\n"）;

return;

}

s1->length=0;

le=s->length;

while（i

{

push（s1,pop（s））;

printf（"%d",s1->top->data）;

i++;

}

while（i--）//返回原栈

push（s,pop（s1））;

}

intmain（）

{

intnum;

stack_typestack;

printf（"\ninsert:

number:

\n"）;

stack.length=0;

while（scanf（"%d",&num）&&num!

=0）push（&stack,num）;

printf（"Thelengthofthestackis:

\n%d",stack.length）;

printf（"\nstackafterpush:

\n"）;

showstack（&stack）;

printf（"\nThelengthofthestackis:

\n%d\n",stack.length）;

printf（"Thefirstnumbertopop\n"）;

printf（"%d\n",pop（&stack））;

printf（"Thesecondnumbertopop\n"）;

printf（"%d\n",pop（&stack））;

printf（"\nstackafterpop:

\n"）;

return0;

}

三、输入与输出

insert:

number:

123450

Thelengthofthestackis:

5

stackafterpush:

54321

Thelengthofthestackis:

5

Thefirstnumbertopop

5

Thesecondnumbertopop

4

stackafterpop:

Processreturned0（0x0）executiontime:

4.415s

Pressanykeytocontinue.

四、上机遇到的问题

1）问题：

在主函数中调用pop函数时总是报错

原因：

pop函数头时这样写的：

node_type*pop（stack_type*s）

解决办法：

把pop改成返回int

2）问题：

程序停止工作或显示thestackisNULL!

原因：

在showstack函数中重复进行了length—

解决办法：

在showstack函数中直接调用push函数进行栈的转移

ex3_2：

一、程序流程说明

循环队列

1）顺序循环队列类型定义为：

#defineN20

typedefstruct

{intdata[N];

intfront,rear;

}queue_type;

2）编写循环队列出队函数dequeue

3）编写循环队列入队函数enqueue

4）编写函数：

voidaa（queue_type*q）；

调用出对函数把队列q中的元素一一出对列，如果是负数直接抛弃；如果是正数，则调用入队函数，插入到q的队尾。

5）编写main函数，首先建立一个队列，其中的数据元素为：

{23-46-58-97-1020}；然后调用aa函数，并将aa函数调用前后队列的数据元素分别输出到屏幕上。

二、程序代码

#include

#include

#include

#defineN20

//定义循环队列

typedefstruct

{intdata[N];

intfront,rear;

}queue_type;

//出队函数

intdequeue（queue_type*q）

{

intout;

if（q->rear==q->front）printf（"thequeueisNULL!

"）;

else{

out=q->data[q->front];

q->front=（q->front+1）%N;

}

return（out）;

}

//入队函数

voidenqueue（queue_type*q,intnewnum）

{

if（（q->rear+1）%N==q->front）printf（"thequeueisFULL!

"）;

else{

q->data[q->rear]=newnum;

q->rear=（q->rear+1）%N;

}

}

//输出

voidshowqueue（queue_type*q）

{

inti;

for（i=q->front;i!

=q->rear;i=（i+1）%N）

printf（"%d",q->data[i]）;

printf（"\n"）;

}

//把队列q中的元素一一出对列，如果是负数直接抛弃；如果是正数，则调用入队函数，插入到q的队尾

voidaa（queue_type*q）

{

intx;

intt;

t=q->rear-q->front+1;

if（（q->rear）<（q->front））

t+=N;

while（t--）{

x=dequeue（q）;

if（x>0）enqueue（q,x）;

}

}

intmain（）

{

queue_typeque;

intx;

que.front=0;

que.rear=0;

while（scanf（"%d",&x）!

=EOF）{

que.data[que.rear]=x;

que.rear++;

}

showqueue（&que）;

aa（&que）;

showqueue（&que）;

}

三、输入与输出

23-46-58-97-1020

^Z

23-46-58-97-1020

3687202

请按任意键继续...

四、上机遇到的问题

1）问题：

程序停止工作

原因：

在showqueue函数头中出现了总是满足的条件（i=q->front;（q->rear+1）%N!

=q->front;（q->front+1）%N）

解决办法：

更改为（i=q->front;i!

=（q->rear+1）;i=（i+1）%N）

2）问题：

程序停止工作

原因：

没有定义que->front和que->rear的值

解决办法：

把主函数中相应片段改为：

que.front=0;

que.rear=0;

while（scanf（"%d",&x）!

=EOF）{

que.data[que.rear]=x;

que.rear++;

}

3）问题：

输出时只有第一个元素按照aa函数的要求进行了处理

原因：

aa函数中没有循环

解决办法：

再定义一个变量t，使算法循环

ex3_3：

一、程序流程说明

书上第12题：

1、创建两个栈公用一个以为数组空间S[m],他们的栈底分别设在一维数组的两端。

2、编写函数，取栈顶元素get（i），其中i为0或1，表示堆栈号。

二、程序代码

#include

#include

#definem100

//创建两个栈公用一个以为数组空间S[m],他们的栈底分别设在一维数组的两端。

typedefstructstack_type

{

intstack[m];

inttop1;

inttop2;

}stacktype;

//出栈

intget（inti,stacktype*s）

{

intout;

if（i==0）

{

out=s->stack[s->top1];

s->top1--;

returnout;

}

else

{

out=s->stack[s->top2];

s->top2++;

returnout;

}

}

intmain（）

{

stack_types;

intdata;

s.top1=0;

s.top2=m-1;

printf（"Pleaseenterthefitststack:

\n"）;

while（scanf（"%d",&data）&&data!

=0）//输入元素，以0为结束

{

s.stack[s.top1]=data;

s.top1++;

}

s.top1--;

printf（"Pleaseenterthesecondstack:

\n"）;

while（scanf（"%d",&data）&&data!

=0）//输入元素，以0为结束

{

s.stack[s.top2]=data;

s.top2--;

}

s.top2++;

printf（"Thetopofstack1is:

%d\n",get（0,&s））;

printf（"Thetopofstack2is:

%d\n",get（1,&s））;

return0;

}三、输入与输出

Pleaseenterthefitststack:

1230

Pleaseenterthesecondstack:

-4-3-2-10

Thetopofstack1is:

3

Thetopofstack2is:

-1

请按任意键继续...

四、上机遇到的问题

1）问题：

[Error]C:

\Users\Administrator\Desktop\大二学习\软基上机\未命名3.cpp:

33:

error:

baseoperandof`->'hasnon-pointertype`stack_type'

原因：

主函数中不能用->代替.

解决办法：

将该行更改为s.stack[count]=data;

2）问题：

输出Thetopofstack1is:

5177344

Thetopofstack2is:

-346788601

原因：

top在输入完成以后指向了栈顶元素的下一个

解决办法：

利用top1--；和top2++；来调整其指向

ex3_4：

一、程序流程说明

书上第13题：

1、创建一维数组Sq[m],存储循环队列的元素

2、设立标志tag，区分头尾指针相同时队列是空是满

2、编写此队列相对应的入队列和出队列函数

二、程序代码

#include

#include

#include

#defineN20

inttag=0;

//定义循环队列

typedefstruct

{

intdata[N];

intfront,rear;

}queue_type;

//出队函数

intdequeue（queue_type*q）

{

intout;

if（q->rear==q->front&&tag==0）printf（"thequeueisNULL!

"）;

else

{

out=q->data[q->front];

q->front=（q->front+1）%N;

}

return（out）;

}

//入队函数

voidenqueue（queue_type*q,intnewnum）

{

if（q->rear%N==q->front&&tag==1）printf（"thequeueisFULL!

"）;

else

{

q->data[q->rear]=newnum;

q->rear=（q->rear+1）%N;

if（q->rearfront）tag=0;

}

}

//输出

voidshowqueue（queue_type*q）

{

inti;

for（i=q->front;i!

=q->rear;i=（i+1）%N）

printf（"%d",q->data[i]）;

printf（"\n"）;

}

intmain（）

{

queue_typeq;

inttag=0,data;

q.front=0;

q.rear=0;

printf（"entertheelementsofthequeue:

\n"）;

while（scanf（"%d",&data）&&（data!

=0））

enqueue（&q,data）;

printf（"thequeueis:

\n"）;

showqueue（&q）;

printf（"thequeueis:

\n"）;

showqueue（&q）;

printf（"deque:

\n%d\n",dequeue（&q））;

return0;

}

三、输入与输出

entertheelementsofthequeue:

123450

thequeueis:

12345

thequeueis:

12345

deque:

1

请按任意键继续...

四、上机遇到的问题

1）问题：

[Error]C:

\Users\Administrator\Desktop\大二学习\软基上机\未命名3.cpp:

27:

error:

toofewargumentstofunction`voidenqueue（queue_type*,int）'

原因：

主函数调用enqueue时没有给予足够的参数，写成了enqueue（&q）;

解决办法：

将该行更改为enqueue（&q,data）;

总结

有了上一次编写链表题的经验以后，这次上机要顺利许多。

但是仍然出现了许多错误，并且很多时候不能迅速地把自己的想法用程序语言表达出来。

所以以后要加强有关方面的练习。

这次的四道题目，充分地体现了顺序存储和链式存储的联系与区别。

编写的时候，虽然觉得顺序存储比较容易写，但是链式存储对于空间的节省让我更加充分地充分感受到了计算机的魅力。