2023年数据结构实验报告二栈队列与杨辉三角.pdf

数据结构实验报告项目名称 栈、队列与杨辉三角专 业 班 级 软件工程工科实验班_学 号 _姓 名 谢江_实验成绩：批阅教师：2 0 2 3 年 5月 22日实 验1 单链表的建立与约瑟夫问题实验学时：实验地点：寝室与实验室 实验日期:2 0 2 3 年 5月 22日1.需求分析实验2 重要是关于栈。队列的建立以及杨辉三角问题的解决(队列运用)2 .概要设计以及具体设计(1)栈c 1 as s S t ack(p u blic:S t a c k 0 ；bo o 1 emp t y ()；判断栈是否为空T p e ek();/显示栈顶元素。void p u s h(T v a lu e);入栈T p op ()；/出栈in t get S ize();当前栈中元素的数量p r i v at e：T *element s ;/数组指针。i nt s iz e；/栈中的元素数量i nt c a p ac i t y ;/栈的容量vo i d ens u r e C ap a c it y ()；/确认栈的容量是否大于元素数量；(2)队列cl a s s Q u e u e(p u blic：。Q u e u e()；void enQ u e u e(T elem e n t);元素入队T deQ u eu e()；元素出对，假如没有元素,抛出异常int ge t S i z e();获取队列大小p r ivat e：L inkedL i s t li s t;定义表)；3.调试分析内容涉及：调试过程中碰到的问题是如何解决的以及对设计与实现的回顾讨论和分析;算法的时空分析(涉及基本操作和其他算法的时间复杂度和空间复杂度的分析)和改善设想;经验和体会等。个人标记：能建立顺序栈，以及链表顺序队列，对于比较复杂的链栈、循环队列等比较不熟悉,杨辉三角问题存在问题本次报告暂时不交，尚有就是抛出异常的问题,例如：T de Que u e()throw(r untime_ e r ro r);元素出对，假如没有元素，抛出异常会提醒警告：C+ex c e p t i on s pec i f i c a t i o n i gnor e d e x cept to i n die a t e a fun c ti o n is n o t_ d eel sp ec(no t h row)于是尽也许用i f(.)t hr ow r u n t i m e _ e r r or,就不报错了4 .附录(1)栈S t ac k.h*采用数组的方式进行栈的操作#ifndefS T A C K _H#defin e S T A C K _ Ht emp iat ecla s s S t a c k(p u b 1 ic：S t ack()；b 0 ol e m p t y()；判断栈是否为空订p ee k()；/显示栈顶元素voi d p u s h(T valu e);入栈T p op ();出栈int getSize();/当前栈中元素的数量p r iv a t e:。T*e 1 eme n ts;数组指针int size;/栈中的元素数量dint capacit y；/栈的容量void e n s ure C a p a city();确认栈的容量是否大于元素数量)；templat e S tack:Stac k()(capa c i t y =10;/初始枝的大小 s ize=0;/初始元素的数量e 1 e ments=new Tcap a cit y;/建立指针)templatebo o 1 St a c k:：e m p ty()(i f(size=0)r eturn true；elsewet u m fals e;)t e mp 1 a t e只技示栈顶元素并不出栈T S t ack:p e ek()return elem e n tssi z e-1;t empla t e v oid Stac k:e nsureC apac i ty()。i f(s ize=capacity)假如满足进行指针的更换。T*o Id=element s;ca p a city=size+1 ；1 eme n ts=n ew T|c ap a c ity;gfo r(i n t i=0;i size;i+)e 1 emcntsi=o 1 d i;d el e te o 1 d;)t e mp 1 atev o id Stack:push(T va 1 ue)(ensu r eC ap a city();/入栈前进行栈是否溢出的判断0e 1 emen t ssize+=va 1 ue;)t empla t eTStack：:po p()re t ur n e 1 e m e nts-s i z e;)t e mpla t ei n t S tack:getSiz e()re t u rn si z e;)#en d i f*TestSt a ck.c p p*#i n c lude#i n clud e S la c k,husing nam e s p a ce s td；i nt m ain()(Stac k int S;co u t before p u s h si z e o f int S ta c k is:i n t S.g etS i ze()e ndl;记录入栈前栈的大小-for(int i=0;i 10;i+)。(时 n t num;c ou t n um;intS.push(num);0 1o u t Vv now s i z e o f in t S t ack is:cout i n tS.popO o u t M e n dl；1c out a f te r po P si z e of intSta c k i s:M intS.g e t Size()e ndl;/出站后栈的大小system(pa u s e );re t u i n 0;)#(2)队列Li n k e d Li s t.h*#ifn d cf LINKED L IS T _H#defin e LINK E DLIST_H#includeus i ng nam e spa c e s t d；templatec 1 ass Qu e u e;前视定义，否则无法友元t e mp 1 a tec 1 ass Nod e(p u b lie:T e 1 em e n t;/节点数据域N o de *next；/指向下指针Nodc()(next=NU LL;o de(T e 1 em e n t)3 t hi s-elemen t=eleme n t;next=N U LL;；tem p l a t ec 1 ass Linke d Lis t(public:Li n kedList();oT rcmoveFi r s t();移除并返回表头元素v o id a d dLa s t(T eleme n t);/尾 端 入 新 元 素 in t g e t Si z e();获取表的大小p r i v a te:Nodc*hc a d,定义头节点、尾节点i n t siz e;；t e mp 1 a t e Lin k e d Lis t:Lin kedList()初始化链表NULL(he ad=tail=NUL L;si z e=0：t emp 1 a t ev o id Linke d L i s t:：a dd L ast(T e lement)i f(tail=NULL)(hea d=t ail=new Nod e (e 1 e men t);else0(t a i 1 n ex t=n ew No d e(elemen t);tailt a i 1 -n ex t;)size+;/作添力口工作，s iz e+)tem p 1 a teT L i n k ed L ist:removeFi r st()(i f(s i z e=0)。throw r u ntim e _ e rro r(No elem e nts);/抛出异常情况else。删除并返回头节点元素,把下一节点作为新的头节点 N o d e *temp=h e ad;。h ea d=he a d next;if(hea d=NUL L)ta il=N UL L;s iz e -;/作删除工作,s i z e-T e 1 ement=t e mp-e 1 ement;d ele t e tem p;0 r et u rn eleme n t;)tem p 1 a teint Lin k e d Li s t:：g e t S i ze()/返 卜 I s i z e(e turn s i ze;1#en d i f*Queue,h*#I f ndef QU EUE_H#de f incQUEUE_H#include,Link e dList.h”#i n c 1 ud e using n ame spa c e st d;temp 1 atec lass Queue(p u bli c：Q u eu e();v o id en Q ueue(T element);元素入队oT d eQu e ue();/元素出对，假如没有元素，抛出异常int getSi ze()；/获取队列大小pr i va t e：L in k edLis t 1 ist；/定义表1；t e m plate Q ucu e:Queue()()/空的构造函数t cmplatevoi d Qu e ue:enQu e u e(T el e me n t)o 1 i s t.a ddLas t(element);入队(后插)t e mplateT Queu e:deQuc u e()(r e turn li s t.removeFirs t();/出 对(前删)tem plate int Q ueue :：g e t Si z e()(retu r n 1 i st.getS i z e()；)#e ndif*TestQueue.cpp*大*#in c lude#i ncludeH i n clud eQ u eue.h u s ing n amesp ace s td;i nt m a i n()Qu e u e q;笛 o u t before cnQucu e si z e is：q.getSize()e ndl;for(int i=0;i 1 0;i+)(。q.e nQu e u e(i);。cout i *en t er q u euen e ndl;)c out af t er e nQueu e s i ze s i:q,g e tSize()endl;while(q.g e t Size()!=0)(o u t q.de Q u e u e()o ut queue end!：1c o ut af t e r deQ u eue size i s:q.g etS i z e()e ndl;dsys t em(pause )；r et u r n 0;)