2023年实验一线性表操作实验报告.docx

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

1、中国矿业大学计算机学院实验报告课程名称数据结构实验名称 线性表实验报告规定：L实验目的3.实验环4.运营结果4.运营结果5.流程图一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。2A熟悉并掌握顺序表的存储结构、基本操作 和具体的函数定义。A3熟悉VC+程序的基本结构，掌握程序中的用户头文献、实现文献 和主文献之间的互相关系及各自的作用。4熟悉VC+操作环境的使用以及多文献的输入、编辑、调试和运营的全过程。二、实验规定1实验之前认真准备，编写好源程序。2a实验中认真调试程序，对运营结果进行分析，注意 程序的对的性和健壮性的验证。3不断积累程序的调试方法。三、实验内容基本题：1对元素类型为整型

2、的顺序存储的线性表进行插入、删除和查找操作。嵋序：# inc 1 u d e #in c lude# in c 1 u d e con s t LIST INIT SI Z E=10;const LIST I NCREMENT=1;t y p e d ef s t ruct(，i nt * el e m; i nt length;in t 1 istsi z e；SqList;void I nitL i s t_Sq(SqList&L)/ /构造一个空的线性表 L( L.elem = (int*)ma 1 I o c(LIST_IN I T_SI Z E* s izeof( i nt);i f

3、 ( ! L. e lem)exit(O);存储分派失败教师评价I优IW用I及格用友格教师署名I一叵期空表长度为0 /初始存储容最3。cout=L. 1 ist s i ze)/ / i值不合法/当前存储空间已满，增长分派L.length=O;。L.lis t si z e= L IST_ I NIT_SIZE;acoutOK! e n dl;)void Lis t I n s e r t _Sq(SqL i st&L, i nt i,int j)/在顺序线性表L中第i个位置之前插入新的元素j ,/i的合法值为l=i=L i stlns e r t_Sq(L)+ 1if (iL. Ie n g

4、th+ 1 )int * n ewba s e = ( i n t*)rea 1 loc ( L .elem,( L Jis t siz e +LISTINCREMEN T )*sizeof (int); i f (! n ewbas e )存储分派失败新基址/增长存储容量存储分派失败新基址/增长存储容量。exit(O);。L.e 1 e m=n e wbase：f L.listsiz e+= LISTINCREMENT；。int *q=&(L.el e m i -1);o for(int*p=&(L. e I e mL.I e ngth -1); p =q;-p)*(p+l)=* p;*q=

5、j：+ L .length;。coutOK! endl；/Li s t lnsert_S qvoid ListDelete_Sq (Sq List & L,int i, int& j )在顺序线性表L中删除第i个元素，并用j返回其值/ i的合法值为l=i=L i st Insert_Sq(L)。if(iL. 1 ength)cou t ERROR! end 1 ;int *p=&(L.elem i-1);P；int * q =L.elem+L.I e ng t h-1；Mo r (4-+ p ； p= q ;+p)。* (p-1) =*p;。一L.lists i z e;cout OK!end

6、l； / / ListDe 1 e t e_Sq/i值不合法/p为被删除元素的位置被删除元素的值赋给j表尾元素的位置/被删除元素之后的元素左移 表长减1boo 1 compa re ( i nt m,i n t n)(if (m=n)r e t u rn t rue;e 1 sereturn false;/在顺序线性表L中查找第1个值与j/若找到，则返回其在L中的/i的初值为第1个元素的位序/P的初值为第1个元素的存储位/在顺序线性表L中查找第1个值与j/若找到，则返回其在L中的/i的初值为第1个元素的位序/P的初值为第1个元素的存储位i nt Locate EI e m_Sq(SqL i s

7、 t LJnt j)满足compare。的元素的位序位序，否则返回0(。int i= 1 ;int * p=L. e lem；置o wh i le i = L . Ie n gth& & !compare(* p ,j)。(+i；叩+十；)i f(i= L . length) return i；o el s e。 return 0： / / Locat e E lem_S qvoid disp( S q L i s t&L)(i n t *p= L .elem;o f o r (in t i= 0 ；i L .listsize;i + +)(3 C OU t * p3 O P + + ； )v

8、oid main()(SqLi s t List;In i tL i s t _Sq (List);int *p=Li s t .el e m；。int m,n,j, k , x,y;。f or(int i= 0 ; i List.listsiz e ;i+)。cinx;。* p =x;oop+;o List.Ie n g th+;C o Utv 插入请按1 ；删除请按2 ；寻找请按3 endl; for(k= 0 ;k= 1 0;k+)c iny;o i f (y=l)。c outn;。 Listlnse r t _Sq (Li s t,m,n)：。disp(L i st);0 )oo e

9、Ise i f(y=2)。c o utV”请输入要删除第几个元素：Vendl;。c inm;ListDelet e _S q (List,m, j )： ocoutje n d 1 ;。d i sp (Li s t);。e 1 se(cout请输入所要查找的元素：m;。cou t Lo c at e 曰 e m_Sq (Us t ,m) e ndl;)couten d I;运营结果：OE:学文件敦据结构实验一实聆l-lDebug实验IT. exeK? 112345789 10否人请按L删除请按2;寻找请按3育输入插入位置和元素的值： ，6I育输入要删除第几个元素：1JK?0 112345678

10、9 土输入所要查找的元素：加强、提高题：以、编写一个求解J。sephus问题的函数。用整数序列1, 2, 3,，n 表达Jl|页序围坐在圆桌周边的人。然后使用n = 9, s = 1, m = 5,以及n = 9, s = 1, m = 0,或者n =9, s = 1, m = 1 0作为输入数据，检查你的程序的对的性和健壮性。最后分析 所完毕算法的时间复杂度。定义J。sephusCi rc 1 e类,其中含完毕初始化、报数出圈成员函数、 输出显示等方法。(可以选做其中之一)a加强题：1A、采用数组作为求解过程中使用的数据结构。峨 高题：2、采用循环链表作为求解过程中使用的数据结构。运营时允许

11、指定任意n、s、m数值,直至输入n = 0退出程序。源程序：(1)加强:#i n c 1 ude #in c lude# i nclu de int a10 0 ;int josephus (int n,int s,int m) (。i f(! (n*s*m)。 co ut输入错误!！ ! e n d I： exit(0);。i n t x =l,y=n; int i =s-l;。i nt j;s whi 1 e (y) (s fo r (i=0; i n;i+)if(ai +1)0 ai =x+；3。if(ai=m)。 “a i =-1 ;oo co u t Vi+1 出局! a y-； 。

12、)sofo r (j=O;j n ；j+)。if( a DJ+1)。 aj=x +；a i f (ajl=m)。j=- 1 ;。x=l; 。丫;o i f (! y)。break;。e I s ecoutj+l出局！ endl;)。)o r e turn (j+1);void ma i n ()( int n, s , m,y=0;int x;d o oo for(inti=0； i 100； i +)0 a i=0;cout 请输入参与游戏的总人数：n;。c o utV”请输入开始人的位置与报数长度： s ;s cinm；。x=j o s e phus(n,s, m);co u t Vx胜出

13、! e nd 1 ; c ou t 请选择：end 1 ;coutl.重新游戏。2.退出程序。：y;whil e (y= 1 ); g e t ch ();运营结果: 国.E: 学习文件,数据结构实睑一实验1-2 （加强）Debug实装1-2 （加强）.exe叫涮八荽加阳乐见心人姒- 12请输入开始人的位置与报数长度:3 66出局！ 127出局？ 2出同？10 8 tl 5t 9H Iti 11 4出局？ b胜出？k重新油戏。2.退出程序。：(2)提高： i n c I u deu s i ng n ame s p a ce std;typed e f struct L Node( struc

14、t L Node *next;。int a;LN o de,*L i n k L i s t;c 1 ass Jo s eph o u C ir c Ie /定义一个类涉及三个元素 (pub lie：void Se t Value ();v oid Pi c kOu t ();pr i vate：int n;i n t s;o in t m;)；void J osep h ouCi r c Ie:： Se t V a lue () 设立初值的大小 coutn;3 cout请输入开始人的位置:“ s ；co u t n e xt=N ULL;LNo d e* r ;r=L；f o r (int

15、i=l;i p-Z a = i；。p- n ext = NULL;r-ne x t = p ;r=p;)p -next=L-next;p = L-next； j =1；whilef p & j n e x t;+j；。f o r ( i =l;i=n;i+)八oofor (j = l； jnext：q=p- next;p-n e x t=q-ne x t：。p =q - nex t ； k=q-a;。cou t输出的结果为:Vkendl； o free(q);) i nt mai n (in t argc,c h ar* a rgv) (Joseph o uC i r cle J o 1 ；J

16、o 1 . S etVa 1 ue();J o l.PickOut()：re t urn 0;)运营结果：H E:学习文件数据结构实验一实验1-2（提高八Debug实验1-2 （提高）.exe02iBvByByByBvByBy 已、FzFzFzBF 3 3 日 7 07 S3 57 3 3一 4s主月2A3 -AAM-A3IA、Au-A3一ay-A fAY Y y 出出出出出出出出出出出出s s er p呈口口口士呈口土呈呈呈口吉士口Ln四、实验体会与总结1、对于线性链表和顺序表都属于线性表问题，但是线性链表比顺序表要灵活,方便：2、线性表在做元素寻找的操作的时候,必须从头结点开始寻找。体会：在编程序的时候，我们每个人肯定会碰到许多问题,我碰到的问题是：当我在运营程序的 时候,在输入个元素后，程序就不继续做下面的操作也不断止运营，自己寻找并修改了好久 都没发现问题的所在，最后实在没办法,就去问同学，结果终于发现是一条语句在编写时出现 了错误。所以，以后再写程序的时候我一定要再认真仔细一点仔细点。