实验七--查找算法

本是古典何须时尚 2022-06-04 06:24 208阅读 0赞

一、 实验目的：

1. 熟练掌握常用的顺序查找法，折半查找法等查找算法。

2. 深入理解各种查找算法的结构特点及各算法之间的区别。

二、 实验内容：

1．常用的一些查找算法。

2．各种查找算法的结构特点及各算法之间的区别。

三、 实验要求:

阅读以下四个类：

RecordNode.java

SeqList\_Sort.java

Search\_Manager.java

Sort\_Test.java

将SeqList\_Sort.java中的三个查找方法补充完整。

源程序见附件

RecordNode.java

\----------------------RecordNode.java ---------------------

package Search;

import java.util.Scanner;

public class RecordNode

publicint key ; // 关键字,用整型可以直接用关系运算符比较大小

publicString element; // 记录的其它部分，用字符串，方便输出

Scannersin = new Scanner(System.in);

publicRecordNode()

System.out.println("请输入关键字：");

this.key=sin.nextInt();

System.out.println("请输入元素值：");

this.element=sin.next();

publicRecordNode(int key)

this.key=key;

publicRecordNode(int key , String element)

this.element= element;

this.key=key;

publicString toString()

returnthis.key+" "+this.element+" ";

\----------------------RecordNode.java ---------------------

\-------------------- SeqList\_Search.java-------------------

/\*\*

\*构造用于排序的线性表，

\*元素位置从下标1开始

\*分别设置各种不同的查找算法

\*查找成功，返回 位序，查找失败，返回 0

\*\*/

package Search;

import Search.RecordNode;

import java.util.Scanner;

import java.util.Random;

public class SeqList\_Search

publicRecordNode \[ \] r;

publicint curlen;

publicSeqList\_Search(int maxSize) //构造方法，用参数做为线性表的初始空间大小

this.curlen=0;

this.r= new RecordNode\[maxSize\];

publicSeqList\_Search() //构造方法，以默认100做为初始空间大小

this(100);

publicvoid create(int n) // 输入生成线性表，参数为输入元素个数

Scanner sin =new Scanner(System.in);

System.out.println("\\t输入"+n+"个线性表的元素：");

for(inti=1;i<=n;i++)

try\{

RecordNodenewdata=new RecordNode ();

this.insert(i,newdata);

catch(Exceptione)

System.out.println("\\t插入位置不合适，无法创建");

publicvoid create( )// 随机数生成10个元素

System.out.println("\\t生成"+10+"个线性表的元素");

for(inti=1;i<=10;i++)

try\{

Randomrd = new Random();

RecordNodenewdata = new RecordNode(rd.nextInt(100),"A"+i);

this.insert(i,newdata);

catch(Exceptione)

System.out.println("\\t插入位置不合适，无法创建");

publicvoid clear()//清空

this.curlen=0;

publicboolean isEmpty() //判断是否为空

if( this.curlen ==0 )

return true;

else

return false;

publicint length() //求长度

returnthis.curlen;

publicRecordNode get(int i) throws Exception //求指定位置元素

if( i < this.curlen)

return this.r\[i\];

else

thrownew Exception("elem no."+i+" not exist!");

publicvoid insert(int i,RecordNode x)throws Exception //在指定的位置上插入数据元素

if(this.curlen == this.r.length)

// throw new Exception("overflow!");

RecordNode newlist\[\]=newRecordNode\[2\*this.curlen\];

for(int j=this.curlen;j>0;j--)

newlist\[j\]=this.r\[j\];

this.r=newlist;

if(i<1|| i>this.curlen+1)

thrownew Exception("position error!");

for(intj =this.curlen ; j >=i ; j-- )

this.r\[j+1\] =this.r\[j\] ;

this.r\[i\]=x;

this.curlen++;

publicvoid remove(int i) //删除指定位置上的元素

for(int j = i+1 ; j<= this.curlen ; j++)

this.r\[j-1\]=this.r\[j\];

this.curlen--;

publicint indexOf(RecordNode x)

int i;

for( i=this.curlen; i>0 ; i--)

if(this.r\[i\].equals(x))

break;

return i;

\}//查找指定元素的位置

publicvoid display()

System.out.println("\\n\\t线性表的元素是");

for(int i = 1; i <= curlen ;i++)

System.out.println("\\t"+this.r\[i\]);

System.out.println();

\}//输出线性表的所有元素值

//---------------------Search---------------------------

//---------------------seqSearch---------------------------

public int seqSearch(int Key)

//顺序查找

int i = 1,n = length();

while(i<n&&r\[i\].key!=Key)

i++;

if(i<n)

return i;

else

return 0;

//---------------------seqSearchWithGuard---------------------------

publicint seqSearchWithGuard(int Key)

r\[0\]= new RecordNode(Key);

//带岗哨的顺序查找

inti = length();

r\[0\].key= Key;

while(r\[i\].key!=Key)

i--;

if(i>0)

returni;

else

return0;

//---------------------binarySearch---------------------------

publicint binarySearch(int Key)

//折半查找

if(length()>0)

int low = 0,high =length()-1;

while(low<=high)

int mid = (low+high)/2;

if(r\[mid\].key==Key)

return mid;

elseif(r\[mid\].key!=Key)

high = mid - 1;

else

low = mid+1;

return 0;

//---------------------seqSearch------------------------

\---------------------SeqList\_Search.java-------------------

\---------------------SeqList\_Manager.java------------------

package Search;

import Search.RecordNode;

import Search.SeqList\_Search;

import java.util.Scanner;

public class Search\_Manager

staticScanner sin = new Scanner(System.in);

SeqList\_Search test ;

publicSearch\_Manager()

test= new SeqList\_Search ();

private void seqSearch() throws Exception

test.create();

test.display();

int Search\_Key ;

int Search\_result = 0 ;

System.out.println("输入待查找的关键字值：");

Search\_Key= sin.nextInt();

Search\_result =test.seqSearch(Search\_Key);

if(Search\_result != 0)

System.out.println("查找成功，查找结果是：");

System.out.println(test.get(Search\_result).toString());

test.clear();

private void seqSearchWithGuard() throws Exception

test.create();

test.display();

int Search\_Key ;

int Search\_result = 0 ;

System.out.println("输入等查找的关键字值：");

Search\_Key= sin.nextInt();

Search\_result=test.seqSearchWithGuard(Search\_Key);

if(Search\_result != 0)

System.out.println("查找成功，查找结果是：");

System.out.println(test.get(Search\_result).toString());

test.clear();

private void binarySearch() throws Exception

System.out.println("请按关键字有序输入创建查找表：");

test.create(10);

test.display();

int Search\_Key ;

int Search\_result = 0 ;

System.out.println("输入要查找的关键字的值：");

Search\_Key = sin.nextInt();

Search\_result=test.binarySearch(Search\_Key);

if(Search\_result != 0)

System.out.println("查找成功，查找结果是：");

System.out.println(test.get(Search\_result).toString());

test.clear();

voidrun () throws Exception

System.out.println(" ---------Menu--------");

System.out.println(" 1 seqSearch");

System.out.println(" 2 seqSearchWithGuard ");

System.out.println(" 3 binarySearch");

System.out.println(" 0 Quit ");

System.out.println(" ---------end----------");

System.out.print(" 请选择查找算法：");

intchoice = sin.nextInt();

if(choice == 0 )

System.exit(0);

switch(choice)

case1: seqSearch();

break;

case2: seqSearchWithGuard();

break;

case3: binarySearch();

break;

default:System.out.println("error,end");break;

System.out.println("\_\_\_\_\_\_\_请继续选择\_\_\_\_\_\_\_\_\_");

\} while(true);

\---------------------SeqList\_Manager.java------------------

\---------------------SeqList\_Test.java---------------------

package Search;

import Search.Search\_Manager;

import java.util.Scanner;

public class Search\_Test

publicstatic void main(String \[\] args) throws Exception

newSearch\_Manager().run();

\---------------------SeqList\_Test.java---------------------

远行结果如下：

![Center][]

![Center 1][]

![Center][]

![Center 2][]

[Center]: /images/20220604/1b4f39657334477e8e7aef32382355bf.png
[Center 1]: /images/20220604/b7759222426644b6a2464537e082d600.png
[Center 2]: /images/20220604/d5fcb48b0ea2493894123c796f86d8bc.png

实验七--查找算法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关七种查找算法

相关 Java数据结构与算法（七）：查找

相关查找实验报告

相关实验七--查找算法

相关 C语言实现七大查找算法（一）

相关实验七

相关实验七

相关七大查找算法详解

相关实验七

相关实验七