《数据结构》实验指导/实验二:单链表的存储及操作1 《数据结构》实验指导 实验二:单链表的存储及操作 、实验目的 1、掌握单链表抽象数据类型的定义。 2、掌握单链表的存储实现。 3、掌握单链表的操作算法实现 4、了解单链表的应用 实验学时 2学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台 2、软件 Windows XP/ Windows7操作系统;开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、顺序存储结构的特点 3、线性表的特点和基本运算 4、线性表顺序存储结构下的操作算法 六、实验任务 1、单链表抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共7页第1页
《数据结构》实验指导 / 实验二：单链表的存储及操作 1 管理科学与工程学科 / 共7页,第1页 《数据结构》实验指导 实验二：单链表的存储及操作 一、实验目的 1、 掌握单链表抽象数据类型的定义。 2、 掌握单链表的存储实现。 3、 掌握单链表的操作算法实现。 4、 了解单链表的应用。 二、实验学时 2 学时 三、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、顺序存储结构的特点 3、线性表的特点和基本运算 4、线性表顺序存储结构下的操作算法 六、实验任务 1、单链表抽象数据类型的代码实现 2、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验二:单链表的存储及操作 2 七、实验内容及步骤 1、任务一:有一个单链表对象L,设计一个算法查找最后一个值为x的结点的逻辑序号。并分 析算法的时间和空间复杂度。 实验步骤: (1)启动 isual Studio2010,创建窗体应用程序。 (2)增加单链表类,代码参考如下: public class Linklist ∥定义单链表结点类 ublic string da ∥放数据元素 ublic Link List next ∥指向下一个结点的字段 public Linklist head= new Linklisto ∥单链表头结点 ∥---单链表的基本运算算法 public void Createlisth( (stringl] split)∥头插法建立单链表 Int 1. head next = null 将头结点的next字段置为nul ∥循环建立数据结点 data=split[[] ∥创建数据结点 s next=head. next ∥将s结点插入到开始结点之前,头结点之后 head next=s public void CreateListR( stringI] split)∥尾插法建立单链表 作r始终指向尾结点,开始时指向头结点 ∥循环建立数据结点 data=split[[] ∥创建数据结点 将s结点插入r结点之后 S 将尾结点的next字段置为nul 管理科学与工程学科/共7页第2页
《数据结构》实验指导 / 实验二：单链表的存储及操作 2 管理科学与工程学科 / 共7页,第2页 七、实验内容及步骤 1、任务一：有一个单链表对象 L，设计一个算法查找最后一个值为 x 的结点的逻辑序号。并分 析算法的时间和空间复杂度。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加单链表类，代码参考如下： public class LinkList //定义单链表结点类 { public string data; //存放数据元素 public LinkList next; //指向下一个结点的字段 }; class LinkListClass { public LinkList head = new LinkList(); //单链表头结点 //---------------单链表的基本运算算法----------------------------- public void CreateListF(string[] split) //头插法建立单链表 { LinkList s; int i; head.next = null; //将头结点的 next 字段置为 null for (i = 0; i < split.Length; i++) //循环建立数据结点 { s = new LinkList(); s.data = split[i]; //创建数据结点 s s.next = head.next; //将 s 结点插入到开始结点之前,头结点之后 head.next = s; } } public void CreateListR(string[] split) //尾插法建立单链表 { LinkList s, r; int i; r = head; //r 始终指向尾结点,开始时指向头结点 for (i = 0; i < split.Length; i++) //循环建立数据结点 { s = new LinkList(); s.data = split[i]; //创建数据结点 s r.next = s; //将 s 结点插入 r 结点之后 r = s; } r.next = null; //将尾结点的 next 字段置为 null
《数据结构》实验指导/实验二:单链表的存储及操作 3 public string DispList( ∥将单链表所有结点值构成一个字符串返回 Linklist p= head next; p指向开始结点 f(p=nu)str="空串" while(p!=null) 作不为nu输出p结点的data字段 str +=p data +" p-p. next p移向下一个结点 return str public int ListLengtho ∥|求单链表数据结点个数 LinkList p p= head 指向头结点n置为0即头结点的序号为0) while(p. next !=null n++ return (n) 循环结束p指向尾结点其序号n为结点个数 public bool GetElem(inti, ref string e)∥求单链表中某个数据元素值 int j=0 LinkList p p=head 指向头结点j置为即头结点的序号为0) while g<i&& p I=null) 找第i个结点 H+; if (p== null) 不存在第i个数据结点返回 false return false. else 存在第i个数据结点返回true return true: public int Locate Elem(string e) ∥按元素值查找 管理科学与工程学科/共7页第3页
《数据结构》实验指导 / 实验二：单链表的存储及操作 3 管理科学与工程学科 / 共7页,第3页 } public string DispList() //将单链表所有结点值构成一个字符串返回 { string str = ""; LinkList p; p = head.next; //p 指向开始结点 if (p == null) str = "空串"; while (p != null) //p 不为 null,输出 p 结点的 data 字段 { str += p.data + " "; p = p.next; //p 移向下一个结点 } return str; } 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) //求单链表中某个数据元素值 { int j = 0; LinkList p; p = head; //p 指向头结点,j 置为 0(即头结点的序号为 0) while (j < i && p != null) //找第 i 个结点 p { j++; p = p.next; } if (p == null) //不存在第 i 个数据结点,返回 false return false; else //存在第i个数据结点,返回true { e = p.data; return true; } } public int LocateElem(string e) //按元素值查找 {
《数据结构》实验指导/实验二:单链表的存储及操作 inti=1. LinkList p p= head. next p指向开始结点i置为1(即开始结点的序号为1) while(pl=null&& p data=e)∥查找data值为e的结点,其序号为 P-p if (p== null) ∥不存在元素值为e的结点,返回0 rn(0); ∥在元素值为e的结点返回其逻辑序号i return(i) public bool ListInsert(inti, string e)∥/插入数据元素 int j=0 LinkList s, p: if(<1) ∥i<1时i错误,返回 false return false. p=head p指向头结点j置为0(即头结点的序号为0) while(<i-1&&p I=null) ∥渣找第i-1个结点 if (p== null) ∥找到第i-1个结点返回 false return false. else ∥找到第i1个结点p插入新结点并返回true s=new LinkListo: ∥创建新结点s其data字段置为e s next=p. next 将s结点插入到p结点之后 p next=s return true: public bool List Delete(inti, ref string e)∥删除数据元素 int j=0 LinkList q, p: if(i<1 ∥i<1时i错误,返回 false return false. p=head p指向头结点j置为0(即头结点的序号为0 while(<i-1&& p I=null) ∥渣找第-1个结点 管理科学与工程学科/共7页第4页
《数据结构》实验指导 / 实验二：单链表的存储及操作 4 管理科学与工程学科 / 共7页,第4页 int i = 1; LinkList p; p = head.next; //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 ListInsert(int i, string e) //插入数据元素 { int j = 0; LinkList s, p; if (i < 1) //i<1 时 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-1 个结点,返回 false return false; else //找到第 i-1 个结点 p,插入新结点并返回 true { s = new LinkList(); s.data = e; //创建新结点 s,其 data 字段置为 e s.next = p.next; //将 s 结点插入到 p 结点之后 p.next = s; return true; } } public bool ListDelete(int i, ref string e) //删除数据元素 { int j = 0; LinkList q, p; if (i < 1) //i<1 时 i 错误,返回 false return false; p = head; //p 指向头结点,j 置为 0(即头结点的序号为 0) while (j < i - 1 && p != null) //查找第 i-1 个结点 { j++;
《数据结构》实验指导/实验二:单链表的存储及操作 5 if (p==null) ∥未找到第i-1个结点,返回 false else ∥找到第i-1个结点p 指向第i个结 f(q==null) ∥若不存在第i个结点返回fase turn false p next =q.next 从人单链表中删除q结点 null /释放q结点 return true ∥返回true表示成功删除第i个结点 public int Findlast( LinkList Class L, string x) LinkList p= L head.next int 1=0, j while(p !=null) f(p data==x return (3)设计窗体,界面参考如下: 操作步骤1-建立单链表 输入元素:2,3,156,23,8 建立单链表 操作步骤2查找最后一个值为x的元素序号 查找 最后元素序号:6 操作提示:在单链表中找到该元素 (4)编写窗体中按钮等控件的代码,调用单链表类,参考如下: 管理科学与工程学科/共7页第5页
《数据结构》实验指导 / 实验二：单链表的存储及操作 5 管理科学与工程学科 / 共7页,第5页 p = p.next; } if (p == null) //未找到第 i-1 个结点,返回 false return false; else //找到第 i-1 个结点 p { q = p.next; //q 指向第 i 个结点 if (q == null) //若不存在第 i 个结点,返回 false return false; e = q.data; p.next = q.next; //从单链表中删除 q 结点 q = null; //释放 q 结点 return true; //返回true 表示成功删除第 i 个结点 } } public int Findlast(LinkListClass L, string x) { LinkList p = L.head.next; int i = 0, j = i; while (p != null) { i++; if (p.data == x) j = i; p = p.next; } return j; } } （3） 设计窗体，界面参考如下： （4） 编写窗体中按钮等控件的代码，调用单链表类，参考如下：
《数据结构》实验指导/实验二:单链表的存储及操作 6 LinkList Class L=new LinkListClasso ∥单链表L private void Forml Load(object sender, EventArgs e) textBoxl. Text=2, 3, 1, 5, 6, 2, 3. 8 private void button1 Click(object sender, EventArgs e) tring str= text BoxlText Trimo infolabel. Text="操作提示必须输入元素"; stringll split= str Split(new Charll',,,.,: '1) CreatelistR(split); button1. Enabled= false button2 Enabled= true; infolabel. Text="操作提示成功创建单链表 private void button2 Click(object sender, Eventargs e) int i elem text Box2. Text: i=L Findlast(L, elem); if(i==0) infolabel. text="操作提示在单链表中没有找到该元素; else text Box3Text=iToString(; 管理科学与工程学科/共7页第6页
《数据结构》实验指导 / 实验二：单链表的存储及操作 6 管理科学与工程学科 / 共7页,第6页 LinkListClass L = new LinkListClass(); //单链表 L private void Form1_Load(object sender, EventArgs e) { textBox1.Text = "2,3,1,5,6,2,3,8"; } private void button1_Click(object sender, EventArgs e) { string str = textBox1.Text.Trim(); if (str == "") infolabel.Text = "操作提示:必须输入元素"; else { string[] split = str.Split(new Char[] { ' ', ',', '.', ':' }); L.CreateListR(split); button1.Enabled = false; button2.Enabled = true; infolabel.Text = "操作提示:成功创建单链表"; } } private void button2_Click(object sender, EventArgs e) { int i; string elem; elem = textBox2.Text; i = L.Findlast(L, elem); if (i == 0) infolabel.Text = "操作提示:在单链表中没有找到该元素"; else { textBox3.Text = i.ToString();
《数据结构》实验指导/实验二:单链表的存储及操作 infolabel. text="操作提示:在单链表中找到该元素"; (5)选择【调试】一→【开始执行(不调试)】命令或按【Crl+F5】组合键运行程序,并观 察运行情况 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、单链表的存储和运算的代码实现 3、数据结构的应用特点。 九、课外自主实验 1、设计一个算法,逆置单链表对象L中的所有结点。并分析算法的时间和空间复杂度。在单链 表类中增加相应方法,在窗体中增加相应控件和代码,调试运行并观察运行结果 管理科学与工程学科/共7页第7页
《数据结构》实验指导 / 实验二：单链表的存储及操作 7 管理科学与工程学科 / 共7页,第7页 infolabel.Text = "操作提示:在单链表中找到该元素"; } } （5） 选择【调试】 【开始执行（不调试）】命令或按【Ctrl+F5】组合键运行程序，并观 察运行情况。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 单链表的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、设计一个算法，逆置单链表对象 L 中的所有结点。并分析算法的时间和空间复杂度。在单链 表类中增加相应方法，在窗体中增加相应控件和代码，调试运行并观察运行结果