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

《数据结构》实验指导实验二：单链表的存储及操作
一、实验目的
1、掌握单链表抽象数据类型的定义。
2、掌握单链表的存储实现。
3、掌握单链表的操作算法实现。
4、了解单链表的应用。
二、实验学时
2学时三、实验类型
验证性实验四、实验需求
1、硬件
每位学生配备计算机一台；
2、软件
Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。
五、实验理论与预备知识
1、数据结构的基本概念
2、顺序存储结构的特点
3、线性表的特点和基本运算
4、线性表顺序存储结构下的操作算法六、实验任务
1、单链表抽象数据类型的代码实现
2、编写应用程序，用相关数据验证运算算法七、实验内容及步骤
1、任务一：有一个单链表对象L,设计一个算法查找最后一个值为x的结点的逻辑序号。并分析算法的时间和空间复杂度。
实验步骤：
(1) 启动Visual Studio 2010,创立窗体应用程序。
(2) 增加单链表类，代码参考如下:
〃定义单链表结点类
〃存放数据元素
//指向下一个结点的字段
public class LinkList(
public string data; public LinkList next;}；
class LinkListClasspublic LinkList head = new LinkList();〃单链表头结点
//-单链表的基本运算算法public void CrcatcListF(string[] split) 〃头插法建立单链表
{LinkList s;
int i;=null;〃将头结点的next字段置为null
for (i = 0; i < h; i++)〃循环建立数据结点{
s = new LinkList();s.data = split[i];〃创立数据结点s
s.next =; 〃将s结点插入到开始结点之HU,头结点之后public void CrcatcListR(string[] split) 〃尾插法建立单链表
{LinkList s, r;
int i;r = head;//r始终指向尾结点，开始时指向头结点
for (i = 0; i < h; i++) 〃循环建立数据结点{
s = new LinkList();s.data = splitfi];〃创立数据结点s
r.next = s;〃将s结点插入r结点之后

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

public string DispList()〃将单链表所有结点值构成一个字符串返同

string str =
LinkList p;
P =；
//p指向开始结点
if (p == null) str ="空串"； while (p != null)
//p不为null,输出p结点的data字段

str += p.data + " p = p.next;
〃p移向下一个结点
return sir;
1
public int ListLength()
〃求单链表数据结点个数

int n = 0;
LinkList p; p = head;
//p指向头结点,n置为0（即头结点的序号为0）
while (p.next != null) (n++;
p = p.next;
}
return (n);
〃循环结束,p指向尾结点,其序号n为结点个数

public bool GetElem(int i, ref string e) 〃求单链表中某个数据元素值 {intj = O;
LinkList p;
p = head; while (j < i && p != null)
//p指向头结点,j置为0（即头结点的序号为0） 〃找第i个结点p

j++；
p = p.next;
}
if (p == null) return false;
〃不存在第i个数据结点，返回false
else
//存在第i个数据结点，返回true
c = p.data;
return true;
//按元素值查找
public int LocateElcm(string c)
int i= 1;
LinkList p;
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);} _
public bool Listlnsert(int i, string e) //插入数据元素{
int j = 0;
LinkList s, p;
if(i< 1)//i<l 时 i 错误，返回 false
return false;
p = head;//p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != null)〃查找第 i-1 个结点
{
j++；
p = p.next;
}
if(p ==null)〃未找到第i-l个结点，返回false
return false;
else〃找到第i-l个结点p,插入新结点并返回true
(
s = new LinkList();
s.data = e;〃创立新结点s,其data字段置为e
s.ncxt = p.next;〃将s结点插入到p结点之后
p.next = s;
return true;
}}
public bool ListDele(e(inl i, ref string e) 〃删除数据元素{
int j = 0;
LinkList q, p;
if (i < 1)〃ivl 时 i 错误，返回 false
return false;
p = head;//p指向头结点j置为0(即头结点的序号为0)
while (j < i - 1 && p != null)//查找第 i-l 个结点
j++；
p = p.ncxt;if (p == null) return false;
else〃未找到第i-1个结点，返回false
〃找到第i-1个结点pq = p.next; if (q == null) return false;
c = q.data; p.next = q.next;q = null;
return true;
〃q指向第i个结点〃假设不存在第i个结点，返回false
〃从单链表中删除q结点〃释放q结点
〃返回（rue表示成功删除第i个结点

public int Findlast(LinkListClass L. string x)LinkList p = L.; inti = O,j = i; while (p != null)
i++；if (p.data == x)
j = i；
p = p.next;
return j;
}（3）设计窗体，界面参考如下:

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

〃单链表L
LinkListClass L = new LinkListClassO;private void Forml_Load(object sender, Event Args e)
(=”2,3,1,5,6,2,3,8”；
}private void buttonl_Click(object sender, Event Args e)
(string str = .Trini();
if (str ===”操作提示:必须输入元素”；
else{
string[] split = (new Char[] {'});L.CreateListR(split);
ed = false;ed = true;
=”操作提示:成功创立单链表”；}
}private void button2_Click(object sender, Event Args e)
(int i;
string elem;elem =;
i = L.Findlast(L, elem);if(i == 0)
=”操作提示:在单链表中没有找到该元素”；else
=i.ToStringO;=”操作提示:在单链表中找到该元素”;
（5） 选择【调试】—►【开始执行（不调试）】命令或按【CtH+F5】组合键运行程序，并观 察运行情况。
八、实验分析
1、分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册；
2、单链表的存储和运算的代码实现；
3、数据结构的应用特点。
九、课外自主实验
1、设计一个算法，逆置单链表对象L中的所有结点。并分析算法的时间和空间复杂度。在单链 表类中增加相应方法，在窗体中增加相应控件和代码，调试运彳j•并观察运行结果。