《数据结构》实验指导/实验一:顾序表的存储及操作1 《数据结构》实验指导 实验一:顺序表的存储及操作 、实验目的 1、掌握顺序表抽象数据类型的定义 2、掌握顺序表的存储实现。 3、掌握顺序表的操作算法实现 4、了解顺序表的应用 实验学时 2学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台 2、软件 Windows XP/ Windows7操作系统;开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、顺序存储结构的特点 3、线性表的特点和基本运算 4、线性表顺序存储结构下的操作算法 六、实验任务 1、顺序表抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共6页第1页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 1 管理科学与工程学科 / 共6页,第1页 《数据结构》实验指导 实验一:顺序表的存储及操作 一、实验目的 1、 掌握顺序表抽象数据类型的定义。 2、 掌握顺序表的存储实现。 3、 掌握顺序表的操作算法实现。 4、 了解顺序表的应用。 二、实验学时 2 学时 三、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台; 2、软件 Windows XP/ Windows 7 操作系统;开发工具软件:Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、顺序存储结构的特点 3、线性表的特点和基本运算 4、线性表顺序存储结构下的操作算法 六、实验任务 1、顺序表抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法
《数据结构》实验指导/实验-:顺序表的存储及操作 2 七、实验内容及步骤 1、任务一:对于含有n个元素的顺序表L,设计一个算法将其中所有元素逆置,并分析算法的 时间复杂度和空间复杂度。 实验步骤: (1)启动 isual Studio2010,创建窗体应用程序。 (2)增加顺序表类,代码参考如下 class SqlistClass const int MaxSize =100 public stringl data ∥放顺序表中元素 public int length ∥放顺序表的长度 public Sqlistclasso data=new string[ MaxSizel ∥-顺序表的基本运算算法 public void CreateList( string[ split)∥由splt中的元素建立顺序表 for(i=0; 1< split. Length; 1++) data1]=split[1 public string DispListo ∥将顺序表L中的所有元素构成一个字符串返回 for(i=1,i< length;i+)∥扫描顺序表中各元素值 mystr +="" datai 管理科学与工程学科/共6页第2页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 2 管理科学与工程学科 / 共6页,第2页 七、实验内容及步骤 1、任务一:对于含有 n 个元素的顺序表 L,设计一个算法将其中所有元素逆置,并分析算法的 时间复杂度和空间复杂度。 实验步骤: (1) 启动 Visual Studio 2010,创建窗体应用程序。 (2) 增加顺序表类,代码参考如下: class SqListClass { const int MaxSize = 100; public string[] data; //存放顺序表中元素 public int length; //存放顺序表的长度 public SqListClass() { data = new string[MaxSize]; length = 0; } //-----------------顺序表的基本运算算法-------------------------------- public void CreateList(string[] split) //由 split 中的元素建立顺序表 { int i; for (i = 0; i 0) { string mystr = data[0]; for (i = 1; i < length; i++) //扫描顺序表中各元素值 mystr += " " + data[i];
《数据结构》实验指导/实验-:顺序表的存储及操作 eturn else return"空串"; public int ListLength( ∥求顺序表的长度 return length public bool GetElem(inti, ref string e)∥求线性表中某序号的元素值 (i length return false ∥参数错误时返回 false ∥取元素值 return tr ∥成功找到元素时返回true blic int Locate Elem(string e) ∥按元素值查找其序号 while(i=length) ∥找到时返回0 eturn 0 else return i+ I ∥找到后返回其逻辑序号 public bool ListInsert(inti, string e)∥/插入数据元素 Int ]; f(1=i,j-)将 data[i-1及后面元素后移一个位置 0=data[j-1 管理科学与工程学科/共6页第3页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 3 管理科学与工程学科 / 共6页,第3页 return mystr; } else return "空串"; } public int ListLength() //求顺序表的长度 { return length; } public bool GetElem(int i, ref string e) //求线性表中某序号的元素值 { if (i length) return false; //参数错误时返回 false e = data[i - 1]; //取元素值 return true; //成功找到元素时返回 true } public int LocateElem(string e) //按元素值查找其序号 { int i = 0; while (i = length) //未找到时返回 0 return 0; else return i + 1; //找到后返回其逻辑序号 } public bool ListInsert(int i, string e) //插入数据元素 { int j; if (i length + 1) return false; //参数错误时返回 false for (j = length; j >= i; j--) //将 data[i-1]及后面元素后移一个位置 data[j] = data[j - 1];
《数据结构》实验指导/实验-:顺序表的存储及操作 data[i-1=e, 插入元素 length++ 顺序表长度增1 return true ∥成功插入返回true public bool ListDelete( int i ref string e)∥删除数据元素 Int if(ilength) ∥参数错误时返回 false return false for(=i-1i;j< length-1;j计+)∥将data[之后的元素前移一个位置 ∥顺序表长度减1 return true ∥成功删除返回true public void Reverse(ref sqlistclass L 1顺序表逆置 Int 1. string tmp for(i=0; 1< L length/2; 1++) tmp=L data[i; L data[=L dataL length L data[ L length -1-1]=tmp; (3)设计窗体,界面参考如下 管理科学与工程学科/共6页第4页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 4 管理科学与工程学科 / 共6页,第4页 data[i - 1] = e; //插入元素 e length++; //顺序表长度增 1 return true; //成功插入返回 true } public bool ListDelete(int i, ref string e) //删除数据元素 { int j; if (i length) //参数错误时返回 false return false; e = data[i]; for (j = i - 1; j < length - 1; j++) //将 data[i]之后的元素前移一个位置 data[j] = data[j + 1]; length--; //顺序表长度减 1 return true; //成功删除返回 true } public void Reverse(ref SqListClass L) //顺序表逆置 { int i; string tmp; for (i = 0; i < L.length / 2; i++) { tmp = L.data[i]; L.data[i] = L.data[L.length - i - 1]; L.data[L.length - i - 1] = tmp; } } } (3) 设计窗体,界面参考如下:
《数据结构》实验指导/实验一:顾序表的存储及操作5 区 操作步骤1-建立顺序表 输入元素:1234561789 建立顺序表 例如输入:a,b,c,d 操作步骤2—产生两个顺序表 逆置顺序表 逆置后的顺序表:987654321 操作提示:成功逆置顺序表 (4)编写窗体中按钮等控件的代码,调用顺序表类,参考如下 SqlistClass L= new Sqlist Class(; private void Forml Load(object sender, EventArgs e) textbox. text="1,2,34,56,78,9"; private void button Click(object sender, eventArgs e) string str= text BoxlText TrimO; infolabel. Text="操作提示必须输入元素 stringll split= str Split(new Charll',,,.,: ) L. CreateList(split) button 1. enabled falses button2 Enabled true: infolabel. Text=操作提示成功创建顺序表"; 管理科学与工程学科/共6页第5页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 5 管理科学与工程学科 / 共6页,第5页 (4) 编写窗体中按钮等控件的代码,调用顺序表类,参考如下: SqListClass L = new SqListClass(); private void Form1_Load(object sender, EventArgs e) { textBox1.Text = "1,2,3,4,5,6,7,8,9"; } 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.CreateList(split); button1.Enabled = false; button2.Enabled = true; infolabel.Text = "操作提示:成功创建顺序表"; } }
《数据结构》实验指导/实验-:顺序表的存储及操作 6 private void button2 Click(object sender, EventArgs e) L Reverse(ref l); text Box2Text=L. Displisto; infolabel. Text="操作提示:成功逆置顺序表 (5)选择【调试】—【开始执行(不调试)】命令或按【curl+F5】组合键运行程序,并观 察运行情况 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册: 2、顺序表的存储和运算的代码实现 3、数据结构的应用特点。 九、课外自主实验 1、假设两个递增有序顺序表L1和L2,分别含有n和m个元素,设计一个算法将它们的所有 元素归并为一个递增有序顺序表L3。在顺序表类中增加相应方法,在窗体中增加相应控件和代 码,调试运行并观察运行结果。 管理科学与工程学科/共6页第6页
《数据结构》实验指导 / 实验一:顺序表的存储及操作 6 管理科学与工程学科 / 共6页,第6页 private void button2_Click(object sender, EventArgs e) { L.Reverse(ref L); textBox2.Text = L.DispList(); infolabel.Text = "操作提示:成功逆置顺序表"; } (5) 选择【调试】 【开始执行(不调试)】命令或按【Ctrl+F5】组合键运行程序,并观 察运行情况。 八、实验分析 1、 分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册; 2、 顺序表的存储和运算的代码实现; 3、 数据结构的应用特点。 九、课外自主实验 1、假设两个递增有序顺序表 L1 和 L2,分别含有 n 和 m 个元素,设计一个算法将它们的所有 元素归并为一个递增有序顺序表 L3。在顺序表类中增加相应方法,在窗体中增加相应控件和代 码,调试运行并观察运行结果