班级： 学号： 姓名： 实验组别：
实验日期： 报告日期： 成绩：
报告内容：（目的和要求、原理、步骤、数据、计算、小结等）
1.掌握各种不同查找算法的思想及高级语言程序实现。
2.掌握二叉排序树的构造和查找方法。
package D_Search;
import java.util.Scanner;
import D_Sort.KeyType;
import D_Sort.RecordNode;
import D_Sort.SeqList;
public class SearchDemo {
/**
* ??????????????,????
*/
static SeqList ST = null;
public static void createSearchList() throws Exception{
int maxSize = 20;
ST = new SeqList(maxSize);
int curlen;
Scanner s = new Scanner(System.in);
System.out.print("?????????:");
curlen = s.nextInt();
KeyType[] k = new KeyType[curlen];
System.out.print("??????:");
for(int i=0;i
k[i] = new KeyType(s.nextInt());
}
for(int i=0;i
RecordNode r = new RecordNode(k[i]);
ST.insert(ST.length(), r);
}
}
public static void main(String[] args) throws Exception{
//1.???????
createSearchList();
Scanner s = new Scanner(System.in);
System.out.print("??????????:");
KeyType key1 = new KeyType(s.nextInt());
KeyType key2 = new KeyType(s.nextInt());
System.out.println("?????: "+key1.getKey()+" = "+ST.binarySearch(key1));
System.out.println("?????: "+key2.getKey()+" = "+ST.binarySearch(key2));
//2.???????????????????
BSTree bsTree = new BSTree();
int[] k = {50,13,63,8,36};
String[] element = {"??","??","??","??","??"};
KeyType[] key = new KeyType[k.length];
System.out.println("????????:");
for (int i = 0; i < k.length; i++) {
key[i] = new KeyType(k[i]);//???????
if (bsTree.insertBST(key[i], element[i])) {
System.out.print("{"+key[i]+","+element[i]+"}");
}
}
System.out.print("\r???????????:");
int q = s.nextInt();
KeyType keyvalue = new KeyType();
keyvalue.setKey(q);//????????
RecordNode found = (RecordNode) bsTree.removeBST(keyvalue);
if (found != null) {
System.out.println("?????: "+keyvalue+" ,??!???????: "+found.getElement());
} else {
System.out.println("?????:"+keyvalue+",??!");
}
}
}
package D_Search;
import B_Stack.LinkQueue;
import C_Tree.BiTreeNode;
import D_Sort.KeyType;
import D_Sort.RecordNode;
/**
* ?????
*/
public class BSTree {
protected BiTreeNode root;
public BSTree(){
root = null;
}
//?????????
public boolean insertBST(Comparable
if (key == null|| !(key instanceof Comparable)) {//??????????????????
return false;
}
if (root == null) {
root = new BiTreeNode(new RecordNode(key, theElement));//?????
return true;
}
return insertBST(root, key, theElement);
}
private boolean insertBST(BiTreeNode p,Comparable
if (key.compareTo((KeyType) ((RecordNode)p.getData()).getKey()) == 0) {
return false;//????????????
}
if (key.compareTo((KeyType) ((RecordNode)p.getData()).getKey()) < 0) {
if (p.getLchild() == null) {//?p??????
p.setLchild(new BiTreeNode(new RecordNode(key,theElement)));//????????p????
return true;
}
else {//?p?????
return insertBST(p.getLchild(), key, theElement);//???p??????
}
}
else if (p.getRchild() == null) {
p.setRchild(new BiTreeNode(new RecordNode(key,theElement)));
return true;
}
else {
return insertBST(p.getRchild(), key, theElement);
}
}
//???????
public Object removeBST(Comparable
if (root == null|| key == null|| !(key instanceof Comparable)) {
return null;
}
//??root?????????????????elemKey???
return removeBST(root,key,null);
}
private Object removeBST(BiTreeNode p,Comparable
if (p!=null) {
if (elemKey.compareTo((KeyType) ((RecordNode)p.getData()).getKey()) < 0) {//???????
return removeBST(p.getLchild(), elemKey, p);//?????????
}
else if (elemKey.compareTo((KeyType) ((RecordNode)p.getData()).getKey()) > 0) {//???????
return removeBST(p.getRchild(), elemKey, p);//?????????
}
else if (p.getLchild() != null&& p.getRchild() != null) {//???????????
BiTreeNode innext = p.getRchild();//??p???????????innext
while (innext.getLchild() != null) {
innext = innext.getLchild();//???????????
}
p.setData(innext.getData());//???????p
return removeBST(p.getRchild(), ((RecordNode)p.getData()).getKey(), p);//??????p
}
else {
if (parent == null) {//?????,?p == root
if (p.getLchild() != null) {
root = p.getLchild();
} else {
root = p.getRchild();
}
return p.getData();//???????p
}
}
if (p == parent.getLchild()) {//p?parent????
if (p.getLchild() != null) {
parent.setLchild(p.getLchild());//?p???????
} else {
parent.setRchild(p.getRchild());
}
}
else if (p.getLchild() != null) {//p?parent?????p??????
parent.setRchild(p.getLchild());
}
else {
parent.setRchild(p.getRchild());
}
return p.getData();
}
return null;
}
// ??????????????(????)
public void levelTraverse() throws Exception {
BiTreeNode T = root;
if (T != null) {
LinkQueue L = new LinkQueue();
L.offer(T);// ??????
while (!L.isEmpty()) {
T = (BiTreeNode) L.pool();
System.out.print(T.getData());// ????
if (T.getLchild() != null) {// ?????,???
L.offer(T.getLchild());
}
if (T.getRchild() != null) {
L.offer(T.getRchild());
}
}
}
}
}
package D_Sort;
public class RecordNode {
private Comparable
private Object element;
public RecordNode(Comparable
this.key = key;
}
public RecordNode(Comparable
this.key = key;
this.element = element;
}
public Comparable
return key;
}
public void setKey(Comparable
this.key = key;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
}
package D_Sort;
public class KeyType implements Comparable
private int key;
public KeyType(){}
public KeyType(int key){
this.key = key;
}
public int getKey(){
return key;
}
public void setKey(int key){
this.key = key;
}
public String toString(){
return key+"";
}
public int compareTo(KeyType another) {
int thisVal = this.key;
int anotherVal = another.key;
return (thisVal
}
}
package D_Sort;
public class SeqList {
private RecordNode[] r;
private int curlen;//??????,?????
public SeqList(int maxSize){
this.r = new RecordNode[maxSize];
this.curlen = 0;
}
public RecordNode[] getR() {
return r;
}
public void setR(RecordNode[] r) {
this.r = r;
}
public int length(){
return curlen;
}
//????????i???????????x
public void insert(int i,RecordNode x) throws Exception{
if(curlen == r.length){
throw new Exception("?????!");
}
if(i<0||i>curlen){
throw new Exception("???????!");
}
for(int j=curlen;j>i;j--){
r[j] = r[j-1];//??????????????
}
r[i] = x;
this.curlen++;
}
//?????
public int binarySearch(Comparable
if(length()>0){
int low=0,high=length()-1;//????
while(low<=high){
int mid = (low+high)/2;//????
if(r[mid].getKey().compareTo((KeyType) key) == 0){
return mid;//????
}
else if(r[mid].getKey().compareTo((KeyType) key)>0){
high = mid -1;//??????????
}
else{
low = mid +1;//??????????
}
}
}
return -1;//????
}
}
建立有序表,采用折半查找实现某一已知的关键字的查找。(采用顺序表存储结构)
实验结果：
?????????:5
??????:12 23 34 45 56
??????????:34 54
?????: 34 = 2
?????: 54 = -1
随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树
实验结果：
????????:
{50,??}{13,??}{63,??}{8,??}{36,??}
在以上二叉排序树中删除某一指定关键字元素
实验结果：
???????????:36
?????: 36 ,??!???????: ??
通过本次试验理解了折半查找的适用条件，建立二叉排序树相同元素的处理，理解了静态查找、动态查找概念，并且掌握了比较各种查找算法的各自特点,能够根据实际情况选择合适的查找方法。
本文来源：https://www.2haoxitong.net/k/doc/9fd12c355727a5e9856a61a2.html
文档为doc格式