《数据结构》实验指导/实验八:查找方法的实现1 《数据结构》实验指导 实验八:查找方法的实现 、实验目的 1、掌握查找的基本概念。 2、掌握线性表的查找方法 3、掌握树表的查找方法。 4、了解哈希表的查找方法 二、实验学时 、实验类型 综合性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、查找的基本概念。 2、线性表的查找方法。 3、树表的查找方法。 4、哈希表的查找方法 六、实验任务 1、顺序查找和折半查找的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共5页第1页
《数据结构》实验指导 / 实验八:查找方法的实现 1 管理科学与工程学科 / 共5页,第1页 《数据结构》实验指导 实验八:查找方法的实现 一、实验目的 1、 掌握查找的基本概念。 2、 掌握线性表的查找方法。 3、 掌握树表的查找方法。 4、 了解哈希表的查找方法 二、实验学时 2 学时 三、实验类型 综合性实验 四、实验需求 1、硬件 每位学生配备计算机一台; 2、软件 Windows XP/ Windows 7 操作系统;开发工具软件:Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、查找的基本概念。 2、 线性表的查找方法。 3、 树表的查找方法。 4、 哈希表的查找方法 六、实验任务 1、顺序查找和折半查找的代码实现 2、编写应用程序,用相关数据验证运算算法
《数据结构》实验指导/实验八:查找方法的实现 七、实验内容及步骤 任务:代码实现顺序表的创建、显示、查找:编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)创建顺序表的存储结构,包括创建、显示、查找等方法,代码参考如下: struct RecType ∥记录类型 放关键字 i public string data; ∥存放其他数据 class SqlistSearch Class const int max Size 100 ∥顺序表中最多元素个数 public RecTypell r; ∥顺序表 public int length; ∥放顺序表的长度 string sstr 用于返回结果 public sqlistSearchClasso ∥构造函数,用于顺序表的初始化 R=new RecType MaxSizel ∥--0顺序表的基本运算算法一 public void Createlist(stringl split) /由 split中的元素建立顺序表 for(i=0; i0) string mystr= RIO. key ToString(; for(i=1: i< length; i++) 描顺序表中各元素值 mystr+=+ Ri. key ToString(; return mystr; else return"空串"; 管理科学与工程学科/共5页第2页
《数据结构》实验指导 / 实验八:查找方法的实现 2 管理科学与工程学科 / 共5页,第2页 七、实验内容及步骤 任务:代码实现顺序表的创建、显示、查找;编写应用程序,用相关数据验证运算算法。 实验步骤: (1) 启动 Visual Studio 2010,创建窗体应用程序。 (2) 创建顺序表的存储结构,包括创建、显示、查找等方法,代码参考如下: struct RecType //记录类型 { public int key; //存放关键字 public string data; //存放其他数据 } class SqListSearchClass { const int MaxSize = 100; //顺序表中最多元素个数 public RecType[] R; //顺序表 public int length; //存放顺序表的长度 string sstr; //用于返回结果 public SqListSearchClass() //构造函数,用于顺序表的初始化 { R = new RecType[MaxSize]; length = 0; } //-----------------顺序表的基本运算算法-------------------------------- public void CreateList(string[] split) //由 split 中的元素建立顺序表 { int i; for (i = 0; i 0) { string mystr = R[0].key.ToString(); for (i = 1; i < length; i++) //扫描顺序表中各元素值 mystr += " " + R[i].key.ToString(); return mystr; } else return "空串";
《数据结构》实验指导/实验八:查找方法的实现 3 各种查找算法 public int Seqsearch(int k, ref int cn 顺序查找算法 ∥统计关键字比较次数 while(i length ∥未找到返回0 return 0: cn++: return i+l 找到返回逻辑序号i+1 (3)通过一串整数的输入,创建数据元素为整数的顺序表,显示顺序表,实现查找操作 设计界面,参考如下: 管理科学与工程学科/共5页第3页
《数据结构》实验指导 / 实验八:查找方法的实现 3 管理科学与工程学科 / 共5页,第3页 } //--------------------各种查找算法--------------------------------------- public int SeqSearch(int k, ref int cn) //顺序查找算法 { int i = 0; cn = 0; //统计关键字比较次数 while (i = length) //未找到返回 0 return 0; else { cn++; return i+1; //找到返回逻辑序号 i+1 } } (3) 通过一串整数的输入,创建数据元素为整数的顺序表,显示顺序表,实现查找操作。 设计界面,参考如下:
《数据结构》实验指导/实验八:查找方法的实现 图For1 操作步骤1-建立顺序表 输入关键字序列 26,749,1,5,3,8,0 建立顺序表 例如输入:3,8,2,4,最多不超过100个元素 操作步骤2输出顺序表 输出顺序表2674915380 操作步骤3查找最大元素和最小元素 查找 最大元素:9最小元素:0 操作步骤3-查找指定元素是否存在 查找元素:7 查找 该元素为顺序表中的第3个元素,比较了3次 (4)编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下 private void Forml Load(object sender, EventArgs e) text Boxl.Text="2,6,7,4,9,1,53,8,0"; private void button1_ Click(object sender, EventArgs e) tring str= text BoxlText Trimo if(st infolabel. Text="操作提示:必须输入关键字序列 stringll split=str Split(, ) L. CreateList(split) if (Llength<= 3) 管理科学与工程学科/共5页第4页
《数据结构》实验指导 / 实验八:查找方法的实现 4 管理科学与工程学科 / 共5页,第4页 (4) 编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下: SqListSearchClass L = new SqListSearchClass(); private void Form1_Load(object sender, EventArgs e) { textBox1.Text = "2,6,7,4,9,1,5,3,8,0"; } private void button1_Click(object sender, EventArgs e) { string str = textBox1.Text.Trim(); if (str == "") infolabel.Text = "操作提示:必须输入关键字序列"; else { string[] split = str.Split(','); L.CreateList(split); if (L.length <= 3)
《数据结构》实验指导/实验八:查找方法的实现 5 infolabel. Text="操作提示输入的关键字个数太少 return private void button2 Click(object sender, EventArgs e) text Box2Text=L. Displisto infolabel. Text=操作提示待查找的数据显示完毕"; private void button3_ Click(object sende;, EventArgs e)∥求顺序表中的最大值 和最小值 private void button 4 Click(object sender, EventArgs e) nt num= int. Parse(text Box6.Text) int p=L SeqSearch(num, ref a); if(p==0) infolabe.iet="进行了”+a+"比较,该元素不存在!"; else infolabel Text="该元素为顺序表中的第”+p+"个元素,比较了"+a+"次 (5)调试运行,并观察运行情况 (6)在类中增加查找最大值最小值的方法: public void MaxMin( ref int min, ref int max)。 (7)在窗体中增加相应控件和代码,调用步骤(6)中的方法,调试运行并观察运行结果 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、查找方法实现; 3、数据结构的应用特点 九、课外自主实验 1、编写折半查找的方法,并调试运行。 管理科学与工程学科/共5页第5页
《数据结构》实验指导 / 实验八:查找方法的实现 5 管理科学与工程学科 / 共5页,第5页 { infolabel.Text = "操作提示:输入的关键字个数太少"; return; } } } private void button2_Click(object sender, EventArgs e) { textBox2.Text = L.DispList(); infolabel.Text = "操作提示:待查找的数据显示完毕"; } private void button3_Click(object sender, EventArgs e) //求顺序表中的最大值 和最小值 { } private void button4_Click(object sender, EventArgs e) { int num = int.Parse(textBox6.Text); int a = 0; int p = L.SeqSearch(num, ref a); if (p == 0) infolabel.Text = "进行了"+a+"比较,该元素不存在!"; else infolabel.Text = "该元素为顺序表中的第"+p+"个元素,比较了"+a+"次。 "; } (5) 调试运行,并观察运行情况。 (6) 在类中增加查找最大值最小值的方法:public void MaxMin( ref int min, ref int max)。 (7) 在窗体中增加相应控件和代码,调用步骤(6)中的方法,调试运行并观察运行结果。 八、实验分析 1、 分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册; 2、 查找方法实现; 3、 数据结构的应用特点。 九、课外自主实验 1、编写折半查找的方法,并调试运行