《数据结构》实验指导实验二单链表的存储及操作.docx

《《数据结构》实验指导实验二单链表的存储及操作.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验指导实验二单链表的存储及操作.docx（7页珍藏版）》请在优知文库上搜索。

1、数据结构实验指导实验二：单链表的存储及操作一、实验目的1、掌握单链表抽象数据类型的定义。2、掌握单链表的存储实现。3、掌握单链表的操作算法实现。4、了解单链表的应用。二、实验学时2学时三、实验类型验证性实验四、实验需求1、硬件每位学生配备计算机一台；2、软件WindowsXP/Windows7操作系统；开发工具软件：MicrosoftVisualStudio2010。五、实验理论与预备知识1、数据结构的基本概念2、顺序存储结构的特点3、线性表的特点和基本运算4、线性表顺序存储结构下的操作算法六、实验任务1、单链表抽象数据类型的代码实现2、编写应用程序，用相关数据验证运算算:法七、实验内容及步骤

2、1、任务一：有一个单链表对象L,设计一个算法查找最后一个值为X的结点的逻辑序号。并分析算法的时间和空间复杂度。实验步骤：(1)启动VisualShIdio2010,创立窗体应用程序。(2)增加单链表类，代码参考如下：定义单链表结点类存放数据元素指向下一个结点的字段publicclassLinkLisl(publicstringdata;publicLinkListnext;：classLinkLisiciasspubIicLinkListhead=newLinkLiSt();单链表头结点-单链表的基本运算算法PUbIiCvoidCrCatCLiStF(Stringsplit)头插法建立单链表L

3、inkLists;inti;=null;将头结点的next字段置为nullfor(i=0;ih;i+)循环建立数据结点s=newLinkList();s.data=spliti;,创立数据结点Ss.next=;将S结点插入到开始结点之HU,头结点之后publicvoidCrcatcListR(stringsplit)尾插法建立单链表LinkLists,r;inti;r=headj/r始终指向尾结点，开始时指向头结点for(i=();ih;i+)循环建立数据结点s=newLinkList();s.data=splitfi;创立数据结点Sr.next=s;将S结点插入r结点之后r.next=nul

4、l;将尾结点的next字段置为nullpublic stringDisPLiSt() 将单链表所 有结期植的成J个字符 串返 SjnkList p;P=;if (p = null) Str=空串；while (p != null)str += p.data , p =return Sir p next;1public int ListLength()int n = O;LinkList p; p = head;while (p.next != null) (n+;p = p.next;)return (n);p指向开始结点/p不为null,输出P结点的data字段P移向下一个结点求单链表数据结

5、点个数p指向头结点,n置为0（即头结点的序号为0）循环结束,p指向尾结点,其序号n为结点个数publicboolGetElem(inti,refstringe)求单链表中某个数据元素值intj=O;LinkListp;p=head;while(ji&p!=p指向头结点,j置为()(即头结点的序号为0)nW)找第i个结点Pj+；p=p.nexl;if(p=null)returnfalse;不存在第i个数据结点，返回falseelse存在第i个数据结点，返回c=p.data;returntrue;publicintLocateElcm(stringc)按元素值查找inti=1;1.inkListp

6、;P=;P指向开始结点,i置为1(即开始结点的序号为1)while(p!=null&p.data!=e)查找data值为e的结点,其序号为ip=p.next;i+:)if(p=null)不存在元素值为e的结点，返回0return(0);else存在元素值为e的结点，返回其逻辑序号ireturn(i);_publicboolLisllnsert(inti,stringe)插入数据元素intj=0;1.inkLists,p;if(il)il时i错误，返回falsereturnfalse;P=headp指向头结点,j置为()(即头结点的序号为0)whileOVi-I&P!=null)查找第i-1个结

7、点(j+;p=p.next;)if(p=null)未找到第i-l个结点，返回falsereturnfalse;else找到第i-l个结点p,插入新结点并返回true(s=newLinkList();s.data=e;创立新结点s,其data字段置为es.ncxt=.next;将S结点插入到P结点之后p.next=s;returntrue;)publicboolListDeIe(e(inli,refstringe)删除数据元素intj=O;1.inkListq,p;if(il)ivl时i错误，返回falsereturnfalse;p=head;/p指向头结点j置为0(即头结点的序号为0)whil

8、e(ji-1&P!=null)查找第i-l个结点j+：找到第i-1个结点Pq=p. next; if (q =耍i伽斗细除%；假设不 存在第i个结点，返回false从单链表中删除q结点释放q结 点返回(rue表示成功删除第i个结点 (3)设计窗体，界面参考如下:(4)编写窗体中按钮等控件的代码，调用单链表类，参考如下:P=p.ncxt;if(pe,se就三f1个结点，返回faIsec=q.data;p.nextpubliciniFiIHlheX(IqiffktUiUClaSSL.stringx)LinkList=J.jri=OJ=i;while(p!=null)i+；if(p.data=x)j

9、=i；p=p.next;returnj;LinkListCiassL=newLinkListClassO;private单链表LvoidFOrmLLOad(Objeetsender,EventArgse)(=231,5,6,2,3,8”；privatevoidbuttonLCliCk(ObjeCtsender,EventArgse)(stringstr=.Trini();if(str=G”操作提示:必须输入元素”；elsestringsplit=(newChar1);L.CreateListR(split);ed=false;ed=true;=”操作提示:成功创立单链表”；privatevoi

10、dbutton2_Click(objectsender,EventArgse)(inti;stringclem;elem=;i=L.Findlast(L,e!em);if(i=O)=”操作提示:在单链表中没有找到该元素”；else=LToStringO;=”操作提示:在单链表中找到该元素”；(5)选择【调试】一A【开始执行(不调试)】命令或按【QH+F5】组合键运行程序，并观察运行情况。八、实验分析1、分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册；2、单链表的存储和运算的代码实现；3、数据结构的应用特点。九、课外自主实验1、设计一个算法，逆置单链表对象L中的所有结点。并分析算法的时间和空间复杂度。在单链表类中增加相应方法，在窗体中增加相应控件和代码，调试运彳j并观察运行结果。