《2023年新版数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《2023年新版数据结构实验报告.docx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、SHUJU7JIEGOUTC YUYAN BAN薮相结施l（Ci1言版） 1姓名：关宏新学号：班级：计084班指导教师：储岳中g e t ch ();c： *C: Docuents and $6七七11185411115七百上01桌面实睑内容1源代码$1口61118.插入前的顺序表为：01491625插入后的顺庠表为：01491655删除前的顺序表为：01491625删除后的顺序表为:01492536检索的内容下标为：436 49 64 8125 36 49 64 8136 49 64 8149 64 81实验二栈的基本操作一、实验目的掌握栈的基本操作:初始化栈、判栈为空、出栈、入栈等运算。二
2、、实验规定认真阅读和掌握本实验的算法。1. 上机将本算法实现。2. 保存程序的运营结果，并结合程序进行分析。三、实验内容运用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等)3、定义一个函数用来实现上面问题：十进制整数X和R作为形参(2)初始化栈 (3)只要X不为0反复做下列动作将X % R入栈，X=X/R (4)只要栈不为空反复做下列动作栈顶出栈，输出栈顶元索四、程序流程图、算法及运营结果2-1ttinclude # i nclude tfinclude #defi n e s tac k_in i
3、 t _s i ze 10 0define s t ackincrem e nt 10typ e def s t ruct s q sta c k(int *base;in t *top;int stac k s ize; sq s t a ck;int Stacklni t (sqs t ack *s)(s-b a se=(int *)m a Hoc(stac k_init_siz e * s iz e o f (int);i f(! sbase)r e t urn 0；s -top= s b a se;s- s ta c ksiz e =stac k_i n i t_s i ze；re t
4、 urn 1；i nt Push (s q stack *s, i nt e)if (s- t op- s -base= s -stacksiz e )(s-ba s e=(int *) rea 1 1 oc(s -bas e , (s- s t ac k siz e +s t acki n crement) *size o f ( i n t)；if (! s-ba s e)ret u rn 0；s-to p = s -base+s- s tacksize;s s tack s i z e += s tac k increm e nt;*(s-t o p+)=e;r etu r n e;)i
5、 n t Pop ( s qs t a c k *s, int e)(i f ( s - t op=sb a s e)return 0;e=*s-top；r et u rn e;)int st a ckemp t y (sqst a c k *s)(i f ( s top= s - b a s e )re t urn 1；)el s e(ret urn 0;)int c o nver s i on(sqstack *s)(i nt n, e=0, flag=0；printf (输入要转化的十进制数:n );sc a nf (%d”, &n)；printf (要转化为多少进制：2进制、8进制、1
6、6进制填数字!n);scanf (% d ”, &f 1 a g);pri n tf (将十进制数%d转化为%d进制是:n M, n , flag);w h i 1 e(n)(Push(s, n% f lag)；n= n / flag；)wh ile(! s t a c kempty( s )(e=Pop(s, e)；sw i t ch (e)(cas e 10: printf(M A*);br e ak;ca s e 11: p r i ntf (B);bre a k ;ca s e 12: printf(*C*);brea k ；ca s e 13: p r in t f (D)； bre
7、 a k;ca s e 14： p rin t f (*E )； break;case 1 5: pr i ntf(F)； break;d e f au 1 t: p ri n tf (*%d , e); )p r i ntf ( n*);retu r n 0;)int main ()(sqst acks;StackIn it(&s);conve r sio n (&s);retu rn 0;c C:DocuMents and $61:1:1185人（1:111：15112101桌面实验内容1源代码!输入要转化的十进制数:矍转化为多少进制：2进制、8进制、16进制填数字！2将十进制数25转化为
8、2进制是：11001Press any key to continue.2- 2# i ncl u de#de f i n e MAXSIZE 1 00 st r u c t s t a ck(int data MAXSIZE;in t top;)；v o id i ni t (str u c t stac k *s)(s-top=-l;)in t emp ty(st ruct sta c k *s)(i f (s-top=- 1) r e turn 1;e Iseretu r n 0 ;) void pus h (struct s tack *s, int i)i f (s- top=M A
9、X SIZE-1) p r i ntf (Stack i s full. n );r e t ur n ;)s-to p +;s-d a tas-t o p =i；in t po p(struct stack * s)(if (emp t y (s)p r i ntf (Stack is empty.);ret u rn - 1 ;)ret urn (s-datas-top)；)void t rans (i nt num)struc t s t ack s;int k；in i t(& s );wh i le(n u m) k = n um% 1 6 ;push(&s, k);num= num
10、/16;while(!em p ty(&s) k=pop(&s);i f(k10)p r intfk);e 1 sep r i ntf(M%c”, k+55)；)pr i nt f ( n);)m a i n()(in t num；clrsc r ()；print f (*Inpu t a num (-1 t o qui t ) : n )； s c anf &num);wh i 1 e(num!=- 1) trans(num);scanf&num);)getch ();3 C:DOCU!E-lADnn1桌面,实验内1源代码S22TInput a nun： 452D实验三串的模式匹配一、实验目
11、的1 .运用顺序结构存储串，并实现串的匹配算法。2 .掌握简朴模式匹配思想，熟悉KMP算法。二、实验规定A 1 .认真理解简朴模式匹配思想，高效实现简朴模式匹配：2 .结合参考程序调试KMP算法,努力算法思想；.保存程序的运营结果,并结合程序进行分析。三、实验内容1、通过键盘初始化H的串和模式串，通过简朴模式匹配算法实现串的模式匹配，匹配成功后规定输出模式 串在目的串中的位置；2、参考程序给出了两种不同形式的ne xt数组的计算方法，请完善程序从键盘初始化一目的串并设计 匹配算法完整调试KMP算法,并与简朴模式匹配算法进行比较。四、程序流程图、算法及运营结果3-1#i n clude # in
12、clu d e #def i ne MAXS I ZE 10 0i nt Str I ndex_BF(char sMAXSI ZE , ch a r t MAX SIZE)(i nt i =1, j= 1 ;whi 1 e ( i =s0 & jt0)ret urn ( i -t0);el s ereturn -1;in t ma i n ()(char s MAXSIZE;char tMAXSIZE;i n t answe r , i;p r i n t f (*S S t ring -n );gets(s )；printf(*T String n )；g e ts( t)；prin t f
13、Strindex_BF (s, t) ；/ * 验证*/实验一线性表基本操作的实现一、实验目的I、掌握使用Turbo C2. 0上机调试线性表的基本方法；2、掌握线性表的基本操作:插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。二、实验规定1、链表插入、删除和查找算法的代码；2、 程序运营结果及分析；3、实验总结。三、实验内容1、认真阅读和掌握本实验的参考程序。2、上机运营本程序,并完善删除、查找等运算。3、保存程序的运营结果,并结合程序进行分析。4、按照你对链表操作需要，重新改写算法并运营，实现链表的插入、删除、查找等运算，并保存运营结 果。四、程序流程图、算法及运营结果1-1#
14、in c lud e s tdio.h # i nclude st d 1 i b. h *#de f ine MAXS I ZE 100s truct Seq Listi nt dataMAXSIZE；int 1 e n g t h;）；type d e f struct SeqList *PS e qL i st;PSe q L ist c r eaeNull L is t _seq()i f (an s wer=S t rind e x_BF(s, t)= 0 )prin t f (*n );prin t f (%s n M , s)；for (i = 0; i asdfdsassdT
15、String ass-1Pattern NOT FOUND.3-2#i n c 1 ude # i n c lude #d e f i ne MAXSIZE 100 v o id g et_nex t val (u n signed char pa t , i nt ne x t v a 1 ) i nt le n g th = st r le n (pat);int i = 1 ;i n t j=0;next v a 1 l=0;while (ilength)(if(j=0| | pa t i-1 =patj- 1 )+i;+j ；if (pat i 1 !=p a tj 1 ) n e x
16、t v a 1 i = j ;else nex tva 1 i=n e x t v a lj；)eIse j =nextvalj;)nex t v al)nex t v al)i nt Ind ex_KMP (unsi gnedchar t ext , un s ig n e d char pat, i n t(int i =1；in t j =1;int t_len = strlen(tex t)；in t p_ 1 en = s trlen(pat);wh ile(i= t _len& j P_ 1 en) retu r n i- 1 - p_len ;else ret u rn - 1
17、；i n t mai n ()(un s igned ch a r tex t MAXS I ZE;u nsigned char pat MAX SI ZE；int ne x tvalMAXS I ZE ;i nt a nswe r, i；prin t f (M nBoy e r-Moor e String S e a r c h i ng Pr o g r am); p r intf (*n= = = =*).p r i ntf ( nnTex t Str i n g ”);gets (text);pri n t f ( *nPatte r n Stri ng );g ets (pat);g
18、 et_nex t val (p a t, n e x t v al);i f (an swer= I nd e x_KMP (text, pa t, ne x tval)=0)(prin t f (” n );printf(* %s n”, tex t );f or (i = 0； i asdfdddssaPattern String dsasdfdddssa dsPattern Found at location 63-3#i n c lu d e *stdi o . h v o id GetNex t 1 (char * t, i nt nex t )(int i=l, j=0;ne x
19、 tl =0;while( i =9)if(j=O I |t i = t j )+i; +j ； nex t i =j; elsej=nextj;)v oid GetNext2(cha r *t , i n t n e x t )(in t i= 1, j = 0；nextl= 0;while ( i =l & t i != t j)j = nextj;i+； j +；i f ( t i=tj ) n e xti = ne xtj;els ene x ti = j ;)void main ()(ch a r *p=*abcaabab c ;i n t i , s t r10;Ge t Next
20、 1 (p, str);p rint f (M Put out:n);f or(i= 1 ;i10;i+)pr i nt f ( %d*, s tr i);G e t N e x t2 (p, str);pr i ntf(n);for (i=l;i=m)/*无效结点* /re t urn NULL；p = (B i nTre e *)m a Hoc (si z eof (Bi nTr e e) ;/* 生成新结点 */p-data=stri;p-lch i 1 d=c re_t ree(str, 2 * i +1, m) ;/* 创建新结点的左子树/p -r c h i ld= c re_tr
21、ee ( s tr, 2* i +2, m) ;/* 创建新结点的右子树 */ retu r n p;)vo i d mai n ()(i nt i, n；char str max；B inTree *roo t ;/* 根结点 */P r intf (请输入二叉树的结点数:)；s canf &n);getch ar () ;/* 输入数字 * /print f(请输入长度为%d的字符串n);for(i=0； in; i +)scanf C% c ,&s t r i );print f (* n );r o ot=cre_t r ee(s t r, 0, n)；pr i ntf (二叉树已成功
22、创建!结点序列为:);fo r (i=0;idata);ch i 1 d)(p r intf (-);pr e o r der ( t -lc h i 1 d)；)i f (t rc h i 1 d)p r in t f (一)；p reo r der(t- r c h i Id);)v o id inorder (B i nTree * t)(i f (t ! =NULL)(i n o r der(t-lc h il d )；p r intf ( %c , t d ata)；i n o r d er(t-rc h i 1 d);)v oid po s t o rd e r(BinTree *
23、t)(if(t!=NULL)(po s tor d er (t- 1c h i 1 d );p o s t o r d e r (t-rc h i Id);p r i n t f (M %c *, t -da t a);)in t leafs (Bi nTree *b)/* 求叶子数 * /P S eqL i st pali s t= (PS e q Li s t) mal 1 oc(si z eof (str u ct S eqLis t);if(palist! =NULL)(palist-l e n g th= 0 ;r eturn (palist);)printf (M Out of s
24、 pa c el! n*)； r e tu r n NULL;) i nt i s NullLi s t_seq(PSeqL i st pal i st)(return (pa 1 ist-length=O);)i n t i nser t Pre_ s eq (PS eqLis t p al i st, int p, int x) (int q；if ( pal i st- 1 en g th=MAXSIZE：)(printf(o v erflow!n)；ret urn ( 0 );)if ( p palist-le n gt h)p r i n t f (Not exist!n);r e
25、tur n ( 0 )；int numl, num 2 ;i f (b=NULL) retur n (0);e Ise i f (b-lc h i 1 d =NU L L & b- r c h i 1 d = NULL) return (1)； else(numl=leaf s (b- 1 child)；num 2 =leaf s (b- r chi 1 d);r etu r n (n uml+num2)；)int tr e edeep (Bi nTre e * p ) /* 求树的深度 */(int 1 deep, rd e e p , dee p ;if (p=NULL) d e ep=0
26、；elseIde ep=t r ee d e ep (p 1 c h i 1 d);rde e p=tre e dee p (p-rc h ild);d e e p= ( 1 deeprdeep? 1 dee p ： r de e p)+l;)r eturn deep；B inT r ee *swap (B i n Tree *p )/*互换二叉树的所有结点的左右子树*/(BinTre e * s t ack ma x ;int k= 0 ;st a c kk =NULL ;if ( p !=NULL)s tack+4-k=p1 c hil d ;p 1 child =p-rchi 1 d ；
27、p-r c h i ld=st a c k k;p -lchild=sw a p (p-lchi Id);p-rch i 1 d =swa p (p-rc h i Id);retu rn p；)c：（ *C: Docu*ent s and $6七111854（111115t1七01桌面实娑内容1源代码54。61）11即请输入二叉树的结点越：8请输入长度为8的字符串：asdfqwer二叉树己成功创建？结点序列为：a s d f q w e r先根遍历结果：a - s - - r - q - d - w - e中根遍历结果：nFsqawde后根遍历结果：i fqsweda叶子数为：4树的深度为：4
28、交换左右子树后先序遍历序列为：a - d - e - w - s - q - f - rPress any key to continue实验五图的创建与遍历.一、实验目的.掌握图的含义；1 .掌握用邻接矩阵和邻接表的方法描述图的存储结构；.理解并掌握深度优先遍历和广度优先遍历的存储结构。二、实验规定.认真阅读和掌握本实验的参考程序。1 .按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。2 .保存程序的运营结果，并结合程序进行分析。三、实验内乱以下参考程序是按邻接表的方法创建图,然后用深度优先遍历方法遍历图.请认真理解程序,然后实现图的广度优先遍历。四、程序流程图、算法及运营结果5
29、-1# includ e *stdio. h#d e fine max s ize 1 02 4/*假定线性表的最大长度为1 0 2 4 */ftdefine nlOO/*图的顶点最大个数*/t y pede f i nt dat a type；/*假定线性表元素的类型为整型文/typede f c har VEXTYPE； /* 顶点的数据类型 */typedef f 1 oat ADJ TYPE； /* 权值类型 */t y pede f str u c t(VEXTYPE vexsn ;/* 顶点信息数组 */ADJTYPE ar csn n ; /* 边权数组 */i nt num ;
30、/*顶点的实际个数*/ GRAPH;/* 1.置空图*/void Graphin it (GRAPH * L)L-n u m= 0 ;/* 2.求结点数*/int GraphVexs (GRAPH *L)(r e tur n (L-num);/* 3.创建图*/void Grap hCreate (GRAPH *L)(int i, j;Graph I ni t (L)；printf (请输入顶点数目：”)；sc a n f (%d”, &L- num);printf (请输入各顶点的信息(单个符号)：);for (i=0; inum; i+)(fflu s h(s t di n);s can
31、f ( % c , &L- v e x s i );print f。请输入边权矩阵的信息：”)；fo r (i= 0 ;inum;i+)(fo r (j=0; j num; j +)scan f &L- a rcsi j)；pr i ntf(图已经创建完毕!”)； )/* 4.图的输出*/vo i d Gr aphOut(GRAPH L) (i nt i, j;pri n t f ( n 图的顶点数目为：%d*, L. num); printf(n图的各顶点的信息为：n);for(i=0； i L. num; i +)pr i ntf (*%c ”, L. v e x s i);printf(
32、n图的边权矩阵的信息为：n);for (i=0; i L. num; i+) (f or (j= 0 ; j L. num; j +)(p r intf C%6. 2 f , L. arcsi j ); p ri n t f (M n*);)pri n tf(图己经输出完毕!)；/* 5.图的深度环游*/ vo i d DFS(GRAPH g, i n t q idian, i n t m a r k )/*从第q i dian个点出发深度优先环游图g中能访问的各个顶点* /int v 1;markqidia n =1；printf(%c *, g. ve x sq i dian);fo r
33、( v 1 = 0； vlg. num； vl+)(i f ( g. a rc s qi d i a n vl! =0& &ma r k v 1 = 0 ) DFS( g , v 1, m a r k);)/* 6 .图的深度环游*/void GraphDFS(GRAPH g )/ *深度优先环游图g中能访问的各个顶点*/(i n t qidia n, v, vl, mar k maxsize;P r i ntf (*n深度环游：)；prin t f (n请输入起点的下标:)；s c a n f (*% d , &q i d ian);for (v= 0 ； v g . num; v+)(ma
34、rkv= 0 ;f or (v= q i d i a n ; v f r ont=0;s q-rear=0；)int QueuelsEmp t y (SEQQUEUE s q)/*假如顺序循环队列sq为空,成功返回1,否则返回0 */(i f ( s q. re ar=sq. f r ont)r eturn(1);elsr et urn(O); i nt QueueFr o nt(SEQQUEUE s q, DA T ATYPE *e)/*将顺序循环队列sq的队头元素保存到e所指地址，成功返回1,失败返回0 */ (if (Q u eu e IsEmpty ( s q) printf (que
35、ue is emp ty! n)； r e turn 0; e 1 se * e =sq. data (sq. fron t); return 1; in t Queu e I n (SEQQUEU E * s q , DA T ATYPE x)/*将元素x入队列sq的队尾,成功返回1,失败返回0 * / (i f ( s qf r on t = ( s q- r ear+ 1 )%max s ize) (printf (*queue is full!n*)；re t ur n 0；) els e(sq- data sq-rear =x;sqrear= (sq-r e a r 4-1) % maxsize;r e tu r n ( 1);i nt QueueOut (SEQ Q U EUE * s q)/将队列sq队首元素出队列,成功返回1,失败返回0 */(i f (Queue I s Empty (* s q)(pri n t f (* q u e ue is e mp t y! n n );retu r n 0;)e 1 se(sq- f ron t =( s q- front +1) %max s i ze； return 1;)/* 7.图的广度环游*/void BFS(GRAPH g, int v, int mar k )/*从v出发广度优先