《数据结构》实验指导实验二单链表的存储及操作.docx
数据结构实验指导实验二：单链表的存储及操作一、实验目的1、掌握单链表抽象数据类型的定义。2、掌握单链表的存储实现。3、掌握单链表的操作算法实现。4、了解单链表的应用。二、实验学时2学时三、实验类型验证性实验四、实验需求1、硬件每位学生配备计算机一台；2、软件WindowsXP/Windows7操作系统；开发工具软件：MicrosoftVisualStudio2010。五、实验理论与预备知识1、数据结构的基本概念2、顺序存储结构的特点3、线性表的特点和基本运算4、线性表顺序存储结构下的操作算法六、实验任务1、单链表抽象数据类型的代码实现2、编写应用程序，用相关数据验证运算算:法七、实验内容及步骤1、任务一：有一个单链表对象L,设计一个算法查找最后一个值为X的结点的逻辑序号。并分析算法的时间和空间复杂度。实验步骤：(1)启动VisualShIdio2010,创立窗体应用程序。(2)增加单链表类，代码参考如下：定义单链表结点类存放数据元素指向下一个结点的字段publicclassLinkLisl(publicstringdata;publicLinkListnext;：classLinkLisiciasspubIicLinkListhead=newLinkLiSt();单链表头结点-单链表的基本运算算法PUbIiCvoidCrCatCLiStF(Stringsplit)头插法建立单链表LinkLists;inti;=null;将头结点的next字段置为nullfor(i=0;i<h;i+)循环建立数据结点s=newLinkList();s.data=spliti;',创立数据结点Ss.next=;将S结点插入到开始结点之HU,头结点之后publicvoidCrcatcListR(stringsplit)尾插法建立单链表LinkLists,r;inti;r=headj/r始终指向尾结点，开始时指向头结点for(i=();i<h;i+)"循环建立数据结点s=newLinkList();s.data=splitfi;创立数据结点Sr.next=s;将S结点插入r结点之后r.next=null;将尾结点的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移向下一个结点求单链表数据结点个数p指向头结点,n置为0（即头结点的序号为0）循环结束,p指向尾结点,其序号n为结点个数publicboolGetElem(inti,refstringe)求单链表中某个数据元素值intj=O;LinkListp;p=head;while(j<i&&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;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(i<l)i<l时i错误，返回falsereturnfalse;P=headp指向头结点,j置为()(即头结点的序号为0)whileOVi-I&&P!=null)查找第i-1个结点(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(i<l)"ivl时i错误，返回falsereturnfalse;p=head;/p指向头结点j置为0(即头结点的序号为0)while(j<i-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=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;=”操作提示:成功创立单链表”；privatevoidbutton2_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并观察运行结果。
