《数据结构》实验指导

《数据结构》实验指导

实验八：查找方法的实现

一、实验目的

1、掌握查找的基本概念。

2、掌握线性表的查找方法。

3、掌握树表的查找方法。

4、了解哈希表的查找方法

二'实验学时

2学时

三'实验类型

综合性实验

四、实验需求

1、硬件

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

2、软件

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

五'实验理论与预备知识

1、查找的基本概念。

2、线性表的查找方法。

3、树表的查找方法。

4、哈希表的查找方法

六'实验任务

1、顺序查找和折半查找的代码实现

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

七'实验内容及步骤

任务：代码实现顺序表的创建、显示、查找；编写应用程序，用相关数据验证运算算法。

实验步骤：

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

(2)创建顺序表的存储结构，包括创建、显示、查找等方法，代码参考如下:

structRecType〃记录类型

publicintkey;〃存放关键字

publicstringdata;〃存放其他数据

)

classSqListSearchClass

(

constintMaxSize=100;〃顺序表中最多元素个数

publicRecType[]R;〃顺序表

publicintlength;〃存放顺序表的长度

stringsstr;〃用于返回结果

publicSqListSearchClass()〃构造函数，用于顺序表的初始化

(

R=newRecType[MaxSize];

length=0;

)

//...........顺序表的基本运算算法

publicvoidCreateList(string[]split)〃由split中的元素建立顺序表

inti;

for(i=0;i<split.Length;i++)

R[i].key=Convert.ToInt32(split[i]);

length=i;

publicstringDispList()〃将顺序表L中的所有元素构成一个字符串返回

(

inti;

if(length>0)

(

stringmystr=R[0].key.ToString();

for(i=1;i<length;i++)〃扫描顺序表中各元素值

mystr+=""+R[i].key.ToString();

returnmystr;

elsereturn"空串

)

//.............各种查找算法.......

publicintSeqSearch(intk,refintcn)〃顺序查找算法

{

inti=0;

cn=0;〃统计关键字比较次数

while(i<length&&R[i].key!=k)〃从表头往后找

(

cn++;

i++；

)

if(i>=length)〃未找到返回0

return0;

else

{

cn++;

returni+1;〃找到返回逻辑序号i+1

（3）通过一串整数的输入，创建数据元素为整数的顺序表，显示顺序表，实现查找操作。

设计界面，参考如下：

9Fond□0B

操作步豢”建立感序表

洽入关催字序列:

2,6,749,1,5,3,8,0

建立顺序表

例如给入：3,8,2,4.最多不超过100个元素

操作步骤2-输出J*序表

输出顺序表2674915380

操作步骤3-查找最大元素和最小元素

查找最大元素：9最小元素：0

操作步骤3-查找指定元素是否存在

查找元素：7查找

该元素为顺序表中的第3个元素，比较了3次.

(4)编写窗体中按钮等控件的代码，调用循环顺序队列类，参考如下:

SqListSearchClassL=newSqListSearchClass();

privatevoidForml_Load(objectsender,EventArgse)

(

textBoxl.Text="2,6,7,4,9J,5,3,8,0”;

)

privatevoidbuttonl_Click(objectsender,EventArgse)

{

stringstr=textBoxl.Text.Trim。；

if(str==

infolabel.Text="操作提示:必须输入关键字序列”；

else

{

string[]split=str.Split(\');

L.CreateList(split);

if(L.length<=3)

infolabel.Text=”操作提示:输入的关键字个数太少”；

return;

}

)

}

privatevoidbutton2_Click(objectsender,EventArgse)

(

textBoxl.Text=L.DispListO;

infolabel.Text=”操作提示:待查找的数据显示完毕”；

)

privatevoidbutton3_Click(objectsender,EventArgse)〃求顺序表中的最大值

和最小值

(

)

privatevoidbutton4_Click(objectsender,EventArgse)

(

intnum=int.Parse(textBox6.Text);

inta=0;

intp=L.SeqSearch(num,refa);

if(p==0)

infolabel.Text="进行了"+a+”比较，该元素不存在！］

else

infolabel.Text="该元素为顺序表中的第“+p+”个元素，比较了“+a+”次。

»».

)

(5)调试运行，并观察运行情况。

(6)在类中增加查找最大值最小值的方法：publicvoidM