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

《数据结构》实验指导

实验二：单链表的存储及操作

一'实验目的

1、掌握单链表抽象数据类型的定义。

2、掌握单链表的存储实现。

3、掌握单链表的操作算法实现。

4、了解单链表的应用。

二'实验学时

2学时

三'实验类型

验证性实验

四、实验需求

1、硬件

每位学生配备计算机一台；

2、软件

WindowsXP/Windows7操作系统；开发工具软件：MicrosoftVisualStudio2010。

五'实验理论与预备知识

1、数据结构的基本概念

2、顺序存储结构的特点

3、线性表的特点和基本运算

4、线性表顺序存储结构下的操作算法

六'实验任务

1、单链表抽象数据类型的代码实现

2、编写应用程序，用相关数据验证运算算法

七、实验内容及步骤

1、任务一：有一个单链表对象L,设计一个算法查找最后一个值为x的结点的逻辑序号。并分

析算法的时间和空间复杂度。

实验步骤：

(1)启动VisualStudio2010,创建窗体应用程序。

(2)增加单链表类，代码参考如下:

publicclassLinkList〃定义单链表结点类

(

publicstringdata;〃存放数据元素

publicLinkListnext;〃指向下一个结点的字段

);

classLinkListClass

publicLinkListhead=newLinkListQ;〃单链表头结点

//---------单链表的基本运算算法--------------------

publicvoidCreateListF(string[]split)〃头插法建立单链表

(

LinkLists;

inti;

=null;〃将头结点的next字段置为null

for(i=0;i<h;i++)//循环建立数据结点

(

s=newLinkList();

s.data=split[i];〃创建数据结点s

s.next=;//将s结点插入到开始结点之前，头结点之后

)

publicvoidCreateListR(string[]split)//尾插法建立单链表

(

LinkLists,r;

inti;

r=head;//r始终指向尾结点，开始时指向头结点

for(i=0;i<h;i++)〃循环建立数据结点

(

s=newLinkList();

s.data=split[i];〃创建数据结点s

r.next=s;〃将s结点插入r结点之后

r=s;

)

r.next=null;//将尾结点的next字段置为null

publicstringDispList()〃将单链表所有结点值构成一个字符串返回

stringstr=

LinkListp;

P=；〃p指向开始结点

if(p==null)str="空串”；

while(p!=null)//p不为null,输出p结点的data字段

(

str+=p.data+””；

p=p.next;//p移向下一个结点

)

returnstr;

}

publiciniListLength()〃求单链表数据结点个数

(

intn=0;

LinkListp;

p=head;//p指向头结点,n置为0（即头结点的序号为0）

while(p.next!=null)

(

n++;

p=p.next;

)

return(n);〃循环结束,p指向尾结点,其序号n为结点个数

)

publicboolGetElem(inti,refstringe)〃求单链表中某个数据元素值

(

intj=0;

LinkListp;

p=head;//p指向头结点,j置为0（即头结点的序号为0）

while(j<i&&p!=null)〃找第i个结点p

(

j++;

p=p.next;

)

if(p==null)〃不存在第i个数据结点，返回false

returnfalse;

else〃存在第i个数据结点，返回true

(

e=p.data;

returntrue;

)

)

publicintLocateElem(stringe)〃按元素值查找

inti=1;

LinkListp;

p=;〃p指向开始结点,i置为1(即开始结点的序号为1)

while(p!=null&&p.data!=e)〃查找data值为e的结点，其序号为i

(

p=p.next;

i++；

)

if(p==null)〃不存在元素值为e的结点，返回0

return(0);

else〃存在元素值为e的结点，返回其逻辑序号i

return(i);

)

publicboolListlnsert(inti,stringe)//插入数据元素

(

intj=0;

LinkLists,p;

if(i<1)//i<l时i错误，返回false

returnfolse;

p=head;〃p指向头结点,j置为0(即头结点的序号为0)

while(j<i-1&&P!=null)〃查找第i-1个结点

(

j++；

p=p.next;

)

if(p==null)〃未找到第i-1个结点，返回false

returnfalse;

else〃找到第i-1个结点p,插入新结点并返回true

(

s=newLinkList();

s.data=e;〃创建新结点s,其data字段置为e

s.next=p.next;〃将s结点插入到p结点之后

p.next=s;

returntrue;

)

)

publicboolListDelete(inti,refstringe)〃删除数据元素

(

intj=O;

LinkListq,p;

if(i<1)//i<l时i错误，返回false

returnfalse;

p=head;//p指向头结点,j置为0(即头结点的序号为0)

while(j<i-1&&p!=null)〃查找第i-1个结点

j++；

p=p.next;

)

if(p==null)〃未找到第i-1个结点，返回false

returnfalse;

else//找到第i-1个结点p

(

q=p.next;//q指向第i个结点

if(q==null)〃若不存在第i个结点，返回false

returnfalse;

e=q.data;

p.next=q.next;〃从单链表中删除q结点

q=null;〃释放q结点

returntrue;〃返回true表示成功删除第i个结点

)

)

publicintFindlast(LinkListClassL,stringx)

(

LinkListp=L.;

inti=OJ=i;

while(p!=null)

i++；

if(p.data==x)

j二i；

p=p.next;

)

returnj;

)

(3)设计窗体，界面参考如下:

(4)编写窗体中按钮等控件的代码，调用单链表类，参考如下:

LinkListClassL=newLinkListClassO;//单链表L

privatevoidForml_Load(objectsender,EventArgse)

{

="2,34,5,6,2,3,8"；

)

privatevoidbuttonl_Click(objectsender,EventArgse)

(

stringstr=,Trim();

if(str==

=”操作提示:必须输入元素”；

else

(

string[]split=(newChai•口{