2023年栈的操作实验报告.docx

《2023年栈的操作实验报告.docx》由会员分享，可在线阅读，更多相关《2023年栈的操作实验报告.docx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三栈和队列3.1 实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在 栈的顺序存储结构和链式存储结构上的实现；熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操 作在队列的顺序存储结构和链式存储结构上的实现。3.2 实验规定：（1） 复习课本中有关栈和队列的知识；（2）用C语言完毕算法和程序设计并上机调试通过；（3） 撰写实验报告，给出算法思绪或流程图和具体实现（源程序）、算法分析结果（涉及时 间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运营结果（必要时给出 多种也许的输入数据和运营结果）。3.3基础实验实验11栈

2、的顺序表达和实现实验内容与规定：编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：（1 ）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5 ）遍历顺序栈（6）置空顺序栈分析:v o id main ()叩rin t f(= 链栈操作=nn);Li n k S ta c k * s ;0s=( L inkStack * ) malloc(siz e o f (Li n k Stack);。int co r d次使用必须初始化!n）；次使用必须初始化!n）；ad o op rintfgpri n tf(第op rin( f (n)pr i ntf (n

3、gpri n tf(n 1叩rin t f (n pr i ntf ( ngpri n tf( n叩rin t f (n叩rin t f (n主菜单初始化链栈2 人栈3 出栈4 取栈顶元素5 置空链栈6 结束程序运营n);n)；n)n)；n );n ); n );Oprin t f( n-n)；叩ri ntf (请输入您的选择(1, 2, 3, 4,5,6)”);wsca n f (%d &cord);Oprin t f( n-n)；叩ri ntf (请输入您的选择(1, 2, 3, 4,5,6)”);wsca n f (%d &cord);sprint f( nn);as wit c h (

4、cord)00000000Dis p (s); b rea k ； b rea k ；aca s e 2:g。printf(输入将要压入链栈的数据的个数:n=)；scanf (%d ，&n)；pri n tf(依次将d个数据压入链栈：n,n);g for (i=l;i = n; i +)a H scanf (%d, &a);a叩us h L stack( s , a);000 |g D i s p(s);g b r eak;8cas e 3 ：。 pr i nt f (” n出栈操作开始!n)；的prin t f (输入将要出栈的数据个数：m=);scan f (% d ,&m); o for

5、(i= 1 ； i=m;i+)皿p r i ntf(n 第 d 次出栈的数据是：% d ,i, popLsta c k(s);。Di s p (s);。)brea k;s case 4：。 p rintf (nn 链栈的栈顶元素为:dn ,S t ac kTo p (s)； 3 opr i n t f (n);。 br e ak;case 5:gos e t E mp t y(s);。Disp(s);break；cas e 6：aex i t(0);ajwhil e (c o rd= 6 );实验3队列的顺序表达和实现实验内容与规定编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主

6、程序，完毕如下功能:(1)初始化队列(2)建立顺序队列(3)入队(4 )出队(5)判断队列是否为空(6)取队头元素(7)遍历队列分析：队列的顺序存储结构称为顺序队列，顺序队列事实上是运算受限的顺序表。入队时，将新元素插入rear所指的位置,然后将re a r加1。出队时，删去f ron t所指的元素,然后将front加1并返回被删元素。顺序队列中的溢出现象：(1)“下溢现象。当队列为空时，做出队运算产生的溢出现象。下溢是正常现象，常用作 程序控制转移的条件。(2) “真上溢”现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种犯错 状态,应设法避免。(3) “假上溢现象。由于入队和

7、出队操作中，头尾指针只增长不减小，致使被删元素的空 间永远无法重新运用。当队列中实际的元素个数远远小于向量空间的规模时,也也许由于尾 指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。注意：(1)当头尾指针相等时，队列为空。(2)在非空队列里，队头指针始终指向队头元素,尾指针始终指向队尾元素的卜一位置。参考程序：# i n c 1 u de #includ e # define MAXNUM 100define El e mty p e i n t#de f i ne TRUE I#define FALSE 0t ypcde f s t ruct El e m t y p e

8、 qu e u e MAXNUM;int f r o n t;int rear; s q q ue u e；/*队列初始化*/int i nitQueue (sqqu e u e * q ) i f(!q) r e turn FALSE;q -fron t = 1;q-rcar= 1;re t urn TRUE;/*入队*/i n t ap p e n d( s qq u eue *q, El e m t ype x) i f (q-rear=MAXNUM-l) r etu r n FALSE;*q- r ear+;q-q u eue q -re a r=x;r e t urn TRUE;I/

9、*出队*/E lemlype Delete( s qqueue * q )o E lemtype x：if (q-front=q- r ea r ) r e turn 0； ax=q- q ueue+q-fro n t ;o r e t urn x ;/*判断队列是否为空水 /in t Empty (sqqueue *q)if (q-fr o n t =q-r e ar) retur n TRUE;r eturn FAL S E;/火取队头元素*/i n t g e t head( s q q u eue *q) i f (q-f r on t =qrca r ) rc t ur n 0 ;r

10、e turn(q-queueq-f r o nt+l)；/火遍历队列*/v oid di s play( s qq u eue * q ) int s;s= q -f r ont;。i f ( q - f r ont= q -r e a r)o p rintf(队列空！ n );el s eprintf(”n顺序队列依次为:);while (srear)s=s+l;g p r intf(u%d q u e ue s );9)oprintf (Xn1);P rin t f(顺序队列的队尾元素所在位置：rear=% d n,q-rear);p r intf(顺序队列的队头元素所在位置：fron t

11、 =% d nM,q-tron t ); o/*建立顺序队列* /voi d Se t s qque u e(sqqucue *q) int n,i, m；printf (”n请输入将要入顺序队列的长度：”)； scanf(d”, &n);p r in t f( ii请依次输入入顺序队列的元素值:n );o f o r (i=0;in; i +) scan f (%d.&m);a ppend (q, m);。main() s qq u eue *hea d ;i nt x ,y, z , s el e c t ;h e ad= ( s qqueu e * )ma 1 Io c (siz e o

12、 f(sqq u eue);g d oprint f ( n第一次使用请初始化! n )：。prin tf( n 请选择操作(1 一一7): n );printf(M= = = =5);-print f( 1 初始化n”);叩rin t f(2建立顺序队列n)；8P rin t f (3 入队n ”)；gpri n t f ( 4 出队 n );printf(5判断队列是否为空n”)；。pr i n t f (6取队头元素n)：gprin t f(7 遍历队列n);g p r i nt f ( = = = = n);wscanf ( %d, & select);o s witch(selec

13、t)case 1: i nitQueu e (head)；prin t f(已经初始化顺序队列！ n);g break;00 Ic ase 2：g S etsq q ueu e (he a d);prin t f( n已经建立队列!n);di s p lay(head)；break;0case 3:。 pr i ntf(”请输入队的值:n );。 scanf(% d ,&x)；。 append (he a d, x); 。d isp 1 ay(h e a d); b r eak;00 )a case 4: z = Dele t e(head);。 g p r i ntf(n队头元素%(1已经出

14、队!n, z);。 disp 1 a y (h e a d );brea k ；a o。 case 5:。 E mpty(head)o 。 叩rin t f(队列空n”)；s oo e 1 se。Printf(队列非空 n)；break;0 )cas e 6 ：8 * y =get h ead(head);opri n t f(队头元素为:d n, y );brea k;00。case 7:g。Misplay (head)；a b r e ak;00 00 |wh i le ( s clcct=7);0 )实验4队列的链式表达和实现实验内容与规定：编写一个程序实现链队列的各种基本运算，并在此基

15、础上设计一个主程序，完毕如下功能：(1 )初始化并建立链队列(2)入链队列(3)出链队列(4)遍历链队列分析：队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：(1)和链枝类似，无须考虑判队满的运算及上溢。(2)在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。(3)和单链表类似，为了简化边界条件的解决,在队头结点前可附加一个头结点。参考程序：# i n clu d ei nc 1 ud e # define EI e mTy p e i n ttype d ef struct

16、 Qn o d e E 1 em Type data;struct Qnode *next；Qn ode t ypc;typedef structQ n odetyp e *fr o n t ；Qnodety p e *re a r; Lqueu e :/ *入链队列*/void La p p e nd ( L queue * q , i nt x )oQno detype * s ；*s= (Qn o detyp e *)mall o c (sizeo f (Q n o d e ty p e);s-da t a=x；s-next= NULL;q-r e ar- n e x t= s ;。q

17、-rear=s;)/*初始化并建立链队列大/void cr e a t (Lqu e uc * q )sQno det ype *h;aint i,n,x;叩rinlf(输入将建立链队列元素的个数:n=);栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对于顺序栈，入栈时，一方面判断栈是否为满，栈满的条件为：p-top= =MAXNUM1,栈 满时，不能入栈；否则出现空间溢出，引起错误,这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一 种控制转移的条件。注意：(1)顺序栈中元素用向量存放(2)栈底位置是固定不变的,可设立在向量两端的任意一

18、个端点(3)栈顶位置是随着进校和退栈操作而变化的，用个整型量top (通常称top为栈顶指针)来 指示当前栈顶位置参考程序：# inckide#include#def ine MAXNUM 20#dc f in e ElemTy p e int/*定义顺序栈的存储结构*/type def stru c t E 1 emTy p e stac k MAXNUM;“nt top； S qStack：/ *初始化顺序栈可void I n itS t ack(SqSt a ck *p)if (!p)叩rin t f( Eor r o r * )；oscanf (%d,& n)；3 h =(Qn o d

19、etype *)malloc ( s i z e of ( Q n odetype)；oh-ne x t=NULL；q- f r ont=h:q-r ear =h；fbr(i=l;i= n ;i+)。叩rin t f(锥队列第 d个元素的值为：,i)；-sc a nfC%d, &x);。 Lap p en d (q, x )；)/*出链队列*/Ele mType Ldel e te (Lqueue * q) Qnodet y pe * p ;oElem T y pc x;if( q -front= q -rear)叩rin tf(队列为空！ n)；x=0；Ielseap=q-fr o n t

20、- n ex t ;q - f ro n t n ext=p- next;i f( p -nex t =NUL L)gqre a r=q-front;*x=p-dat a ；fre e (p)；re t u r n (x);/*遍历链队列文/void displa y ( L queue * q) Q node t ypc *p;p = q- f ront-nex t ;/ *指向第一个数据元素节点 */pr i ntf(n链队列元素依次为：)；wh i 1 e(p ! =NULL)printf(,%d-.p- d ata);叩=p -n e xt：)p rintf(n n遍历链队列结束！ n

21、 )；m a i n() L q u e u e *p;int x , c o rd；叩r in t f(n * * *第一次操作请选择初始化并建立链队列！ * n );Hl。 printf( n链队列的基本操作n )；print f (主菜单n);cScf ( - ) J lllj ygprintff1初始化并建立链队列n)；pri n t f(pri n t f(入链队列n)；出链队列出链队列wpr i n(f(printf ( 4 遍历链队列n);叩rint f(”5 结束程序运营n“)；00 p mi l Hiias c anf(% d ,&cord)； sw i t ch( c or

22、 d )。 ocase 1:g p=(Lq u e u e *)mal 1 o c( s i z e o f (Lque u e )；。 ocreat( p )；38 dis p lay ( p );。 b re a k；， case 2：8g叩r i nt f (请输入队列元素的值:x=);a 。 s canf( %d,& x );。 oLappen d (p, x )；3di s play(p)；3 g break；。 cas e 3:a。 pr i n t f (出链队列元素：x=%dn,Ld e lete( p );。 displa y (p);。 b r ea k ; cas e 4

23、 ：。d i s p 1 ay(p);break; e xit (0);) e xit (0);)s case 5 ： 00000“wh i Ie (co r d=5)；3.4提高实验实验11迷宫的求解实验内容与规定：迷宫只有两个门，一个叫做人口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的 入口处赶进迷宫。迷宫中设立很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处 放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到 出口的途径。分析：迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及 时纠正错误的搜索方法。从入口出发，按某一

24、方向向前探索，若能走通（未走过的），即某处 可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一 点，换下一个方向再继续试探，直到所有也许的通路都探索到，或找到一条通路，或无路可走 又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能对的返回前一点以 便继续从下一个方向向前试探，则需要用一个栈保存所可以到达的每一点的下标及从该点前 进的方向,栈中保存的就是一条迷宫的通路。为了保证程序可以终止，调整时，必须保证曾被放弃过的填数序列不被再次实验，即规定按 某种有序模型生成填数序列。给解的候选者设定一个被检查的顺序，按这个顺序逐个生成候 选者

25、并检查。参考程序:# i n c ludei nclu d e# de fine n I 10#def i n e n2 10typ e de f st r u c t node(i nt x ; / /存x坐标i n t y ; 存丫坐标intc; /存该点也许的下点所在的方向.1表达向右,2向上，3向左,4向右 linkstack;I i nkstac k t op10 0 ;迷宫矩阵int maze n 1 n2 = 1,1, 1,1,1, 1,1,1, 1,1,0,0 , 0,1 ,0,0,0,1, 0, 1,1 J,0,1,0,0, 0,1 , 0,1,1 , 0,0,0, 0 ,

26、1 ,1,0,0, 1 ,1,0,1 JJ,0,0,0, 0,1,1 ,0,0,01，0 , 0, 0,0。1, 0 J, 0,0,0 , 1,0, 0 , 1,1,0, 1, 1, 1 ,0, 1 , 1,0, 1,1, 1, 0, 0 ,0, 0,0, 0,0,1,b 1,1, 1,1,1,1, 1,1, 1,;in t i,j,k,m=0;ma i n() / /初始化top 口，置所有方向数为左fo r (i=0; i n I*n2； i+)topi ,c=l;)p r intf(n t he m a ze i s :n );打印原始迷宫矩阵for(i=0;inl;i+) f or(

27、j =0;jn2;j+ + )p rintf(m a zei j ?*);prin t f( n ); i=0;to P ij. x = l;to p i. y=0;maze 1 0 =2;/*回溯算法*/d o if(top i .c5)”还可以向前试探if( t op i .x=5 & topi .y= 9) 已找到一个组合( 打印途径p r i n I f (The way % d is:n ,m+);f or(j=0； j ,topf j .x,topj.y);|p r intf(n)；打印选出途径的迷宫for(j=0; j n 1 ;j+)for (k=0； kn2;k+)if (m

28、azej k=0)prin t f()；els e if (maz e j k=2) pri n tf(O );else printfC* )； p rin t f(*n ); ma z ei o pi. x to p i . y = 0 ;t op i ,c = 1;i -top i. c += I;c ontinue； switch (topi .c)向前试探(cas e 1： i f (ma z et o pi. x t o pi.y+ 1 =0)i+；t o pi.x=to p i 1 . x ;topi. y=topi-l .y+1;ma z etop i . x top i.y=2

29、； e 1 se t opi .c += 1;b reak;ca s e 2:i f (maze t opi.x-1 lop i . y =0) i+；topi . x =lopi-l .x-1 ；t op i .y= t o p i-l.y；maze to p i J. xjtop i J.y=2;)e Isetop i .c += 1 ： b reak;ca s e 3:if(ma z eto pi .x top i .y-l =0)i+ + ;t opi.x=top i- 1 .x：top i . y=topi-1 .yI;m a ze t op i .x top i . y =2;el

30、se t opfi .c += 1 ； br e a k； c ase 4:i f (maze t opi. x + 1 t op i . y = =0) i +；topi.x=t o p i I .x+1;topi.y=topL i -1. y;ma z e top i.xtop i. yl=2;else to p i.c += 1;b reak;)e Ise / /回溯i f (i=0) return：已找完所有解maze topi.xto p i.y=0;topi. c = 1;i-;t o pi.c += 1;w h ile(l )；【实验21停车场管理实验内容与规定：设停车场内只有一

31、个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在 停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆 车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后 开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原顺序进入车场, 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述规定进行管理的模拟程序。分析：综合运用栈和队列模拟停车场管理，学习运用栈和队列解决实际问题。以栈模拟停车场，以队列

32、模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管 理。每组输入数据涉及三个数据项：汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜 别的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车 场内或便道上的停车位置；若是车拜别;则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要拜别的汽车让路而从停车场退出来的汽车，也用顺序存储结构 实现。输入数据按到达或拜别的时刻有序。栈中每个元素表达一辆汽车，包含两个数据项： 汽车的牌照号码和进入停车场的时刻。设 n=2,输入数据为：(火,1

33、, 5), CAS 2 , 1 0), (D, 1,15),A,3, 20) , C A、, 4,2 5),CA;5,30) ,(D,2,35) ,(D, 4, 40 ) , (EQ, 0)。每一组输入数据涉及三个数据项: 汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻，其中A，表达成达；，表达 拜别，下，表达输入结束。参考程序:。#includei nc 1 u de# i n c 1 udedef ine MAX 2 /*车库容量刃#def i ne pr i c e 0.05 /*每车每分钟费用* / typedef s t rue t t ime in t hour;in

34、t min; Time; / *时间结点*/t y p e de f s tr u c t no d ech a r num 10;Time re a ch;T ime 1 eave;CarNode; /*车辆信息结点*/typede f struct NODEC arNode *stackM AX+1;i n t top; Se q Stac k C ar； /*模拟车站号typedef s tru c( ca r (Ca r N o de *da t a；st r u ct car *next; Q u e u e Node；typ e d e f s t ruct NodcQu e ue

35、N ode * head;Q ueu e No d e *rcar;L i n k Qu e u e Car; / * 模拟通道* /)/*入栈*/void Push (SqStac k * p, ElemT y p e x )aif(p-top1。p =p-t o p + 1 ;。叩- s tack p-topl= x ;)oel s epr i n t f(Overflow!n)；)/ *出栈*/EI e mType Po P (Sq S tack *p)。E 1 emType x ;if( p - t o p!=0) x=p- s t a c kp-to p ;叩r i n t f (以

36、前的栈顶数据元素d已经被删除! n,p- s ta c k p-top)；p-top=p- t o p -1;return (x);1。e 1 s e p ri n tf(uUnderf 1 ow! n);retum( 0 );0)/*获取栈顶元素* /E 1 emTyp e Ge t T o p( S qStack * p ) void InitS t ack(SeqStack Ca r *); /*初始化栈*/i n t InitQueue(Link QueueCar*);/*初始化便道* /i n t A r r i val(SeqS t ackCa r*,Link Que u eCar

37、 *)； /*车辆到达*/v o id Leave (Se q StackCar *, S eqStackCar *, L inkQueueCar *); / * 车辆离开* / vo i d L i s t (S eqStackC a r,LinkQu e u eCar) ; /*显示存车信息* /void main() S cqS t ac k Ca r E n t e r,Temp；Link QueueCar W a it;i n t ch;Ini t S tack( & En t er); /*初始化车站 */I n itS t ack (&Temp ) ;/*初始化让路的临时栈*/I

38、 n i tQ u eue (&Wai t); / *初始化通道*/while(l) printf(n 1 .车辆到达)；P r intf( 2.车辆离开)pr i n t f( 3.列表显示);prin t f ( 4.退出系统n”)；while(l) scanf (%d , &ch);if (ch=I & & c htop= 0 ;for (i=0; i stacks-top =N ULL;int Ini t Que u e(Li n k Q ue u e Car *Q)/*初始化便道火 /Q-head= (Queue N o de *)m a 1 loc( s ize o f( Q ue

39、ueNo de);i f(Q-hea d !=NU L L)Q h e a dnex t =NU L L；Q-rear= Q- h e ad;r e t u r n(l) ;)e 1 s e r e t u rn(-i);void PRINT(CarN ode 火 p, int room) /* 打印出站车的信息 */int AI,A2,B1,B2；p r i ntf(n请输入离开的时间：/*：*/);scanf(%d： % d (p-leave.h our), & ( p leave, m i n );print f ( n离开车辆的车牌号为:“)；p u ts(p-num);printf(

40、 n 其到达时间为:%d:%d .p-re a c h . h o ur,p-r e a c h.min);p r inif(离开时间为：%d： %d, p-l e ave. hour,plcave.min)；A 1 =p- r e ach.hou r ;A2= p -reach, m i n；B 1 =p- 1 eave, hour;B2=p - 1 e a v e.min;printf(n 应交费用为:2. If 元”，(B1-A1)*6O+(B2A 2 )*price);fre e (p);i n t Arri v al(SeqS t ackCar *Ent e r,LinkQu e u

41、eC a r * W) /*车辆到达 * / CarNode * p ;Q u e u eNod e * t ；P =(CarN o de *)mall o c(s i z e of( C arNo d e);flushall ();printf(n请输入车牌号(例:陕A 1 2 3 4):)；gets(p-num);if(Ent e rtop t op+;p ri n t f (n 车辆在车场第d 位置二Ent e r- t op);prin t f( n请输入到达时间:/*: * */)；scanf (%d:%d ,&(p-reach. hou r ) ,& ( p -r e a ch.min)；En t er-sta c kEnter-top=p;r eturn( 1 );else/*车场已满，车进便道*/ p r int f (n该车须在便道等待!”)；t = (Q u eu e N o de*) mallo c (s i z e o f(QueueNode);t -d a(a=p;t nex t =NU L L;W-rear-n e xt= t ;W- r e a r