2023年新版数据结构C语言版实验报告.docx

《2023年新版数据结构C语言版实验报告.docx》由会员分享，可在线阅读，更多相关《2023年新版数据结构C语言版实验报告.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（C语言版）实验报告专业:计算机科学与技术、软件工程学号:班级:软件二班姓名:朱海霞指导教师:刘遵仁青岛大学信息工程学院2023年1 0月“abba”是回文，而“aba b”不是回文。实验重要环节(1)数据从键盘读入；(2)输出要判断的字符串；(3)运用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出 “No”。程序代码：#include#incl u d e # d e fi n e TRUE 1d e f ine FALSE 0# def i ne OK 1def i ne ERROR 0# define OVERFLOW -2define N 10 0#

2、define STACKJN I T_SIZElOo 0#def i ne S T ACKINCREMENTl 0，typedef structint * b ase; 刈 在栈构造之前和销毁之后,ba s e的值为NULLin t * t op;/栈顶指针intsta c ksize;。当前已分派的存储空间,以元素为单位 SqS t ack；int InitSt a c k( S q S t a ck &S) /构造一个空栈Sif(!(S.base=(int*) m al 1 oc (STACK_INIT_S IZE* s i zeo f ( i n t ) exit(OVERFLOW);

3、/存储分派失败S . t o p=S.base；S.stac ksiz e = S TACK INIT S I ZE;r e turn O K;)i nt St a c kEmp t y (SqS t a ck S)/若栈S为空栈，则返回TRUE,否则返回FALSEif( S . top=S.b a se)return TRU E ；els ereturnFALSE;)int Push(Sq S ta c k & S , i n t e)/插入元素e为新的栈顶元素i f( S .t o p -S. b a s e= S .sta c ksize) / 栈满，追加存储空间S. base = (i

4、nt *) realloc(S .base, ( S.stacks i z e + S TACK I N C R E MENT)*sizeof(int);if(! S .base)exit (OVERFLOW);/存储分派失败S t op=S.bas e + S .st a cks i z e；S.st a cksi ze+=STA CKIN C R EMENT;* (S.to p )+=e;re t urn OK;i n t P o p( S qS t ack & S 9int &e) /若栈不空，则删除s的栈顶元素，用e返回其值,并返回OK;否则返回ERRORif(S. t o p=S.

5、b a se)r e tur n ERROR;e =*-S.top;r e t ur n OK；i n t ma i n()S q Stack s;int i,ej,k=l;ch a r c h N = 0 ,*p, b N = 0；if(InitSta c k( s ) /初始化栈成功(printf (”请输入表达式：nn)；g ets(ch);P =ch ；wh i le(*p) /没到串尾Push(s,*p+);for( i =0； i N； i+)i f (!S t a ckEmpty(s) / / 栈不空Pop ( s ,e); /弹出栈顶元素b i=e;6)6 f o r( i =

6、 0 ； i n ,&G- e );/ /输入顶点数和边数sea n f(c “，&a);p rin t f(nInp u t Verte x st r i ng:);fo r( i =0； in;i+) o scanf(n% c n,&a);3 G-V e X s i = a ;/ /读入顶点信息，建立顶点表f or(i=0; i n ; i +)。 f or(j=0;j n ; j +)3G-e dges i j=0;初始化邻接矩阵pr i n t f(nInpu t edg e s, C re a t A d jacenc y Matr i xnn);fo r (k=0;ke;k+ +)

7、 / /读入e条边,建立邻接矩阵。sea nf(”d%d”,&i, &j);输入边(V i , Vj)的顶点序号o G-edges i j =1;。G- e d gesj / /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句)/ / = = = = 定义标志向量，为全局变量 = =t yped e f e n um FALSE, T RUE Bo o 1 e a n ；B o ol e an visitedM a x Vert e xNum;/ = = DFS :深度优先遍历的递归算法=vo i d DFSM(MGra ph *G,int i ) 以Vi为出发点对邻接矩阵表达的图G进行

8、DFS搜索，邻接矩阵是0,1矩阵给出你的编码= = =BFS :广度优先遍历= = =voi d B FS (MGraph * G, int k) / /以Vk为源点对用邻接矩阵表达的图G进行广度优先搜索给出你的编码= = = =主程序 ma i n =vo i d mai n ()(in t i ；MG r aph * G；G=(MGraph *)m a lloc(sizeof(MG r aph); 为图 G 申请内存空间C r eatMGra p h (G);/建立邻接矩阵printf(n Prin t G r ap h DFS: );DFS(G)；/深度优先遍历p r intf(HnH)

9、;prin t f(n P rint G r ap h BFS : )；BFS(G,3)；以序号为3的顶点开始广度优先遍历pri n tf(n nn);2.邻接链表作为存储结构#i n c 1 u d eMstdio. h # i ncl u d e n stdli b . h n边表结点边表结点/ /定义最大顶点数int a d jvex；stru c t node *next;邻接点域/链域 Ed g e N o de;t y pedef str u c t v n odecha r vertex;/ /顶点表结点顶点域E d geNode * f ir s te d ge; 边表头指针V

10、e r t e x N od e ；typede f V e rt e xNode AdjLis t M a xVertexN u m;类型/AdjL i s t是邻接表ty p e d ef s t ruct Ad j List adjlist；i n t n ,e; ALG r aph;/ /邻接表/图中当前顶点数和边数/图类型= = = =建立图的邻接表= = = = =v oid CreatA L Grap h (A L Graph *G)rint i,j, k;char a;E d g eNod e *s；/定义边表结点p r intf(nInp u t V ertexNum( n

11、) an d Edge s Num(e): )；s c anf( H % d , %dM,&G-n,&G-e) ;/读入顶点数和边数s can f(%c& a );printf(nInput V e rtex s t ring： );for(i=0;in;i+ +)/ /建立边表#defin e M a xVertexNum 5 0 ty p e d e f struct n o d e scanf( n %cn,&a)；G- adj li s ti. v e rtex=a;读入顶点信息G adjl i st i .first e d ge=NULL；边表置为空表prin t f(n I n

12、p u t edges,C r e a t Ad j a cen c y L i s t n);for ( k =0； k e ；k+) 建立边表oscanfC%d%d &i, &j);读入边(V i ,V j )的顶点对序号s=(EdgeNode *) malloc(s i zeof (Ed geNode);生成边表结点os-adj v ex=j ；/邻接点序号为jis-next= G a d jl i s t i . f i rs t edge；G-adj 1 i st i .first e d g e =s;将新结点* S插入顶点Vi的边表头部s=(EdgeN ode *)mall o

13、c(s i ze o f(EdgeNode);sadjv e x=i；邻接点序号为is-ne x t =Gadjlistj . f i rstedge；G adjli s tj. firs t e dge=s;/ /将新结点* S插入顶点Vj的边表头部)/=定义标志向量，为全局变量= = =t ypedef enum F ALSE,TRUE Boolean;Bool e an visite d MaxVert e xNum;/=dfs：深度优先遍历的递归算法=void DFSM(ALGraph *G,inti) 以V i为出发点对邻接链表表达的图G进行DFS搜索给出你的编码实验1实验题目：顺序

14、存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性 能分析。实验规定：建立一个数据域定义为整数类型的线性表，在表中允许有反复的数据;根据输入的数据, 先找到相应的存储单元，后删除之。实验重要环节：1、分析、理解给出的示例程序。2、调试程序，并设计输入一组数据(3, 5, 6, 82-5,4, 7, -9),测试程序的如下功能:根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。程序代码：# i n c ludeincl u de# d e f ine OK 1de f ine ERROR 0# d e fine OVERF

15、LOW -2de f ine LI S T_INIT_ S IZE 100# def i n e LISTINCREMENT 10 typ e d e f str u ctH-H-= BFS:广度优先遍历void BFS(A L Gra p h *G,int k)/ /以Vk为源点对用邻接链表表达的图G进行广度优先搜索给出你的编码void m a in ()inti;ALGrap h *G;G=(ALGraph *)malloc(si z e o f (ALGraph)；C r eatALGrap h (G)； pri n tf CP r int G r a ph DFS:”);DFS(G);

16、p rintfCnn)；P rintf ( P rint Gr a p h B FS: )；BFS(G,3)；pr i n t f (Hn )；实验结果:1 .邻接矩阵作为存储结构.邻接链表作为存储结构心得体会:承验6实验题目：二分查找算法的实现实验目的：掌握二分查找法的工作原理及应用过程，运用其工作原理完毕实验题目中的内容。实验规定：编写程序构造一个有序表L,从键盘接受一个关键字key,用二分查找法在L中查找 key,若找到则提醒查找成功并输出key所在的位置,否则提醒没有找到信息。实验重要环节：1 .建立的初始查找表可以是无序的，如测试的数据为3, 7, 11, 15, 17,21, 35

17、,4 2, 50或者1 1, 21, 7 , 3, 15, 5 0, 4 2 , 35, 17。2 .给出算法的递归和非递归代码；3 .如何运用二分查找算法在一个有序表中插入一个元素x,并保持表的有序性？程序代码实验结果：心得体会:实验7实验题目:排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根 据实际问题的特点和规定选择合适的排序方法。实验规定：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运营速度。实验重要环节：程序代码实验结果：心得体会:Ant* el e m；“n t le n gth;i n t lists i z e

18、 ;JSqlist;int I n i t List_ S q(Sql i st & L ) ?L. elem= (i n t*)mal 1 o c (LI S T_ I NIT _ S IZE*si z e of(i nt);(!L.e 1 e m) re t u r n -1;L. leng t h=0;Lli s tsize= L I ST_INIT_SIZE;return 0 K;int Lis t I nsert_S q (Sqli s t&L,int i,int e)A f (iL.leng t h +1) r e turn ERRO R ；“f(L.len g th= =L. l

19、ist s ize)Mnt *ne w b ase;。 ne wba s e=( i nt*)re a lloc(L. elem,(L.lists i ze+LISTINCREMENT)*sizeo f (int);。i f (! new b a s e ) r etu r n -1 ；6L.elem = n e wb a se；L.listsi z e+=LIST I NCREMENT;int * p,* q ;oq=&(L.el e mi 1);efor (p & (L.e 1 emL.length-l)； p=q;p)*(p+l)=*p;o* q =e;o+L. 1 ength；retu

20、r n OK;int ListDelet e _S q(Sql i s t &L,int i,int e )in t * p ,* q ;if(iL.le n g t h)ret u rn E RR 0 R;p = &(L. elem i - 1);oe=*p;q=L. e 1 em+L.l e ng t h 1 ；ofo r (+p; P =q； +p)*(p-l)=*p；L . 1 engt h ;vet urn OK;)int ma i n () S qlis t L;4n i tL i st_Sq(L);/ / 初始化i n t i, a =3,-5,6,8,2,-5,4,7,9;0f

21、o r (i= 1 ;i10; i +)L i stl n sert_Sq(L, i, ai- 1 )；for(i=0;i 9 ;i+)。 pri n tf(n %d,L.e 1 em i);叩rin t f (n )； / /插入9个数。L istlnser t _Sq(L,3, 2 4);。f o r (i=0; i 10;i+ + )p r in t f( %d n ,L.elemi);printf(n)； / /插入一个数 gint e;Lis t Delete_S q (L,2,e);for( i =0;i9;i+)叩 rin t f (% d ，L.elemi)；/ 删除一个数p

22、rintf (”n)。 r e t u r n 0;实验结果：3,-5, 6, 8,2,-5,4,7, -93,-5 , 2 4,6,8,2, -5,4,7,-93, 24,6,8, 2, -5,4,7,-9心得体会：顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结 构简朴，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插 入和删除元素需要移动大量元素，消耗大量时间；需要一个连续的存储空间;插入 元素也许发生溢出;自由区中的存储空间不能被其他数据共享实验2实验题目:单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法

23、及相关的时间性 能分析。实验规定:建立一个数据域定义为字符类型的单链表，在链表中不允许有反复的字符；根据输入的 字符，先找到相应的结点，后删除之。实验重要环节：3、分析、理解给出的示例程序。4、调试程序，并设计输入数据(如：A,C, E, F,H, J, Q,M),测试程序的如下功能:不允许 反复字符的插入；根据输入的字符，找到相应的结点并删除。5、修改程序：(1) 增长插入结点的功能。(2) 建立链表的方法有“前插”、“后插”法。程序代码：# i nc 1 udei n cl u de# de f i ne NULL 0define OK 1# d e fine ERROROtyped e

24、f str u c t LNodein t da t a;struct LNode * n ext; L Node 产 Link Lis t ;int I n i tLi s t_L(Lin k L i s t &L)L =(Li n kList)mall o c (s i zeof(LN o de);，L-next=NULL;r et u r n OK; int Lis t I ns e rt_L(LinkLi s t &L,int i, i nt e ) L ink L i s t p9s；in t j;dP=L; j=0;ow h ile( p &jnext； +j;nf(!p I Ui

25、- 1)ddretur n E RRO R;。s =(Link L i s t)mal 1 oc(siz e of(LNo de)；s- d ata=e；s- next =p-next;叩n e xt=s;dreturn OK;)i n t L i s tD e 1 e te_L (LinkL i st&L,int i, in toL i n kL i st p, q ；nnt j ;dp=L; j =0;whi 1 e(p-ne x t&jnex t ;+j;)dif(!(p-n e x t) I |jnext;p- n e x t=q n ext;e =q-dat a ; f ree( q

26、 );retu r n OK;int m a i n() dLinkListLjp；char a8=/A，Ef,Mn t ij;4ni t List_L(L)；for( i =1, j =0； i=8,jn e xt;ow h i 1 e ( p !=NUL L) 3 p rintf (n%ctn,p-data);p =p-next；) 插入八个字符dprin t f(nnn);i=2；i nt e；Li s tlnse r t_L (L,i, B);p = L -n e xt;while (p! =NULL)gpr i n t f (%ct , p -data)； ddp=p-nex t ;

27、/插入一个字符叩rin t f(nnn)；，i=3；L istDelete_L( Le);p=Lnext;while(p!=N ULL) ， pr i n tf(n % c t n, p - d ata); P=p-next;Win t f (Hnn)；r e turn 0;实验结果：A CEFH J Q UABC EFHJ QUAB EFH J QU心得体会：单链表是通过扫描指针P进行单链表的操作;头指针唯一标记点链表的存在；插 入和删除元素快捷,方便。实验3实验题目：栈操作设计和实现实验目的：1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈的特点，即后进先出和先进先出的原则。3、掌握栈的基本运算，如:入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。实验规定：回文判断:对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如