课程：《程序设计与数据结构》
班级： 1823
姓名： 赵沛凝
学号：20182301
实验教师：王志强
实验日期：2019年11月1日
必修/选修： 必修
public static void selectionSort(Comparable[] data) {
int min;
for(int index=0;index<data.length-1;index++){
min=index;
for(int scan=index+1;scan<data.length;scan++)
if(data[scan].compareTo(data[min])<0)
min=scan;
swap(data,min,index);
}
}
private static void swap(Comparable[] data,int index1,int index2){
Comparable temp=data[index1];
data[index1]=data[index2];
data[index2]=temp;
}public static Comparable linearSearch(Comparable[] data,Comparable target){
Comparable result = null;
int index = 0;
while(result == null && index < data.length){
if(data[index].compareTo(target)==0)
result = data[index];
index++;
}
return result;
} player[0] = new Contact("d", "j", "2301");
Contact target1 = new Contact("","","0505");
Contact found[] = new Contact[10];
found[0] = (Contact) Searching.linearSearch(player,target1);
for(int i=0;i<8;i++){
System.out.println("Test"+(i+1)+":");
if(found[i] == null)
System.out.println("Player was not found.");
else
System.out.println("Found: "+ found[i]);
}public static int linearSearch(int[] data,int target){
int result = 0;
int index = 0;
while(result == 0 && index < data.length){
if(data[index]==target)
result = data[index];
index++;
}
return result;
}public static int InsertionSearch(int[] a, int x , int left, int right){
if(x<a[0]||x>a[a.length-1]){ //不加这句会抛出异常，若找的数不在范围内，则mid可能越界//
return -1; }
int mid = left + (x-a[left])/(a[right]-a[left])*(right-left);
if(left>right){
return -1; }
if(x<a[mid]){
return InsertionSearch(a,x,left,mid-1);
} else if(x>a[mid]){
return InsertionSearch(a,x,mid+1,right);
} else{
return a[mid];
}
}
public static void fibonacci(int[] f){
f[0]=0;
f[1]=1;
for(int i=2;i<f.length;++i){
f[i]=f[i-1]+f[i-2];
}
}
public static int FibonacInsearch(int[] a, int x){
int left=0, right=a.length-1;
int k=0;
int FIB_MAX = 20;
int[] f = new int[FIB_MAX];
fibonacci(f);
while(a.length>f[k]-1){
k++;
}
int[] tmp = new int[f[k]-1];
System.arraycopy(a,0,tmp,0,a.length);//拷贝a元素到tmp中
for(int i=a.length;i<f[k]-1;++i){ //right以后的值都相同
tmp[i]=a[right];
}
while(left<=right){
int mid = left+f[k-1]-1;
if(x<a[mid]){
right=mid-1;
k-=1;
}
else if(x>a[mid]){
left=mid+1;
k-=2;
}
else{
if(mid<a.length)
return a[mid];
else //扩展里找到x，返回a的最后一个下标
return a.length-1;
}
}
return -1;
}//二叉树查找
private static Node root;
private Node temp;
public Searching2() {
root = null;
}
public void add(int data1) {//向二叉树插入元素
if (this.root == null) {
root = new Node(data1);
temp = root;//存下第一个节点
} else {
addW(root,data1);
}
}
public void addW(Node x,int data1) {//判定插入元素的位置
//当数据大于等于节点时，放右子树
if (data1 >= x.getData()) {
if (x.getRight() == null) {
x.setRight(new Node(data1));
} else {
addW(x.getRight(),data1);
}
}
else {//数据小于节点时，放左子树
if (x.getLeft() == null) {
x.setLeft(new Node(data1));
} else {
this.addW(x.getLeft(),data1);
}
}
}
public void print() {
root.print(); System.out.println();
}
public Node BSTreesearch(Node x,int data2) {//在二叉树中寻找元素
if(x==null)
return null;
if(data2==x.getData()){
return x;
}
else if(data2<x.getData()){
return BSTreesearch(x.getLeft(),data2);
}
else {
return BSTreesearch(x.getRight(),data2);
}
}
public int BS(int target){
Node k =BSTreesearch(root,target);
int po = k.getData();
return po;
}
public Node getRoot() {
return root;
}public static int blocksearch(int[] index,int[] data,int target,int m){
int i = Bsearch(index,target);
System.out.println("在第"+i+"块");
if(i>=0){
int j = m*i;
int k = m*(i+1);
for(;j<k;j++){
if(data[j]==target)
return data[j];
}
}
return -1;
}public static int[] addhashlinear(int[] data){
int[] result=new int[13];
for(int i=0;i<data.length;i++){
int m=data[i]%13;
while(result[m]!=0)
m++;
result[m]=data[i];
}
return result;
}
public static int hashlinear(int[] data,int target){
int m = target%13;
while(data[m]!=target&&m<data.length-1){
m++;
}
return data[m];
}
public class shell {
public static void main(String[] args){
int gap,a,d,count=0,temp,l,okk;
int[] c=new int[10];
Arrays.fill(c,0);
String e,ok="";
Scanner scan=new Scanner(System.in);
System.out.println("输入数组数字：(空格隔开)");
e=scan.nextLine();
String[] f=e.split(" ");
count=f.length;
for(a=0;a<f.length;a++){
c[a]= Integer.parseInt(f[a]);
}
for(gap=f.length/2;gap>0;gap=gap/2){
for(d=gap;d<=f.length-1;d++){
l=d;
temp=c[l];
if(c[l]<c[l-gap]){
while(l-gap>=0&&temp<c[l-gap]){
c[l]=c[l-gap];
l-=gap;
}
c[l]=temp;
}
}
}
for(okk=0;okk<f.length;okk++){
ok+=c[okk]+" ";
}
System.out.println(ok);
}
}public class dui {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a, b, c, d, dd,head, kk, temp, i = 1;
String e;
System.out.println("请输入堆元素（以空格隔开）");
e = scan.nextLine();
String[] f = e.split(" ");
int[] count = new int[f.length];
// int[] fin=new int[f.length];
//以数组形式构造树
for (a = 0; a < f.length; a++) {
count[a] = Integer.parseInt(f[a]);
}
kk = count.length;//待排序的元素个数
String pp="";
for(int oo=0;oo<count.length;oo++){
pp=pp+count[oo]+" ";
}
System.out.println("堆排序前"+pp);
//排序
temp = kk;//排序中的下标
while (kk >= 3) {
temp = kk;
i=1;
while (temp > 1) {
c = temp / 2 - 1;
if (c==-1)
c=0;
if (i == 1) {
if (kk % 2 == 0) {
if (count[c * 2 + 1] > count[c]) {
int kkk = count[c];
count[c] = count[c * 2 + 1];
count[c * 2 + 1] = kkk;
}
}
if (kk % 2 != 0) {
if (count[c * 2 + 1] > count[c * 2 + 2] && count[c * 2 + 1] > count[c]) {
int kkk = count[c];
count[c] = count[c * 2 + 1];
count[c * 2 + 1] = kkk;
} else if (count[c * 2 + 2] > count[c * 2 + 1] && count[c * 2 + 2] > count[c]) {
int kkk = count[c];
count[c] = count[c * 2 + 2];
count[c * 2 + 2] = kkk;
}
}
} else {
if (count[c * 2 + 1] > count[c] || count[c * 2 + 2] > count[c]) {
if (count[c * 2 + 1] > count[c * 2 + 2]) {
int kkk = count[c];
count[c] = count[c * 2 + 1];
count[c * 2 + 1] = kkk;
} else {
int kkk = count[c];
count[c] = count[c * 2 + 2];
count[c * 2 + 2] = kkk;
}
}
}
temp--;
i++;
}
b = count[0];
count[0] = count[kk - 1];
count[kk - 1] = b;
kk--;
i++;
}
for(d=0;d<3;d++){
for(dd=d;dd<3;dd++){
if(count[dd]<count[d]){
head=count[dd];
count[dd]=count[d];
count[d]=head;
}
}
}
String ll="";
for(int hh=0;hh<count.length;hh++){
ll=ll+count[hh]+" ";
}
System.out.println("堆排序后"+ll);
}
}public class tree {
public static void main(String[] args){
int a,b,c,d,count;
int[] h=new int[10];
Arrays.fill(h,0);
leaf root=null;
String f,g;
Scanner scan=new Scanner(System.in);
System.out.println("请输入数组数字(空格隔开)");
f=scan.nextLine();
String[] e=f.split(" ");
for(c=0;c<e.length;c++){
h[c]= Integer.parseInt(e[c]);
}
//构造树
for(a=0;a<e.length;a++){
leaf temp=new leaf(h[a]);
if(root==null){
root=temp;
}
else{
leaf current=root;
while(true) {
if (temp.root > current.root) {
if(current.right==null) {current.right=temp; break;}
else current=current.right;
}
if(temp.root<current.root){
if(current.left==null){current.left=temp;break;}
else current=current.left;
}
}
}
}
root.dayin(root);
}
}
public int BS(int target){
Node k =BSTreesearch(root,target);
int po = k.getData();
return po;
}@Test
public void testTestSearch() {
Node root;
Node temp;
int[] number = new int[]{20,18,23,1,9,10};
Searching2 tree = new Searching2();
for(int m=0;m<number.length;m++){
tree.add(number[m]);
}
assertEquals(1,tree.BS(1));
assertEquals(23,tree.BS(23));
}最后测试成功
问题3：在使用虚拟机的命令行代码时，出现了如下问题：
本次实现较为简单，基本上是复习老师上课讲的内容，以后自己也要多多复习。
20182301 2019-2020-1 《数据结构与面向对象程序设计》实验7报告
原文：https://www.cnblogs.com/zhaopeining/p/11878191.html