题目:在CArray类里增加顺序查找方法,加快顺序查找方法,二分法以及递归二分法,并设一个compcount的私有整型变量,初始值为0,在每种查找的算法内,在执行完关键性比较后增加一行代码,对compcount进行加1操作。运行完四种方法后,比较compcount的值。
我的代码如下:
class CArray
{
private static int[] arr;
private int numElements=0;
private static int compCount=0;
public CArray(int size)
{
arr = new int[size];
}
public void Insert(int item)
{
arr[numElements] = item;
numElements++;
}
public void DisplayElements()
{
for (int i = 0; i <arr.Length; i++)
Console.Write(arr[i] + " ");
}
public void BubbleSort()
{
for (int outer = arr.Length-1; outer >= 1; outer--)
{
for (int inner = 0; inner <= outer - 1; inner++)
{
if ((int)arr[inner] > arr[inner + 1])
{
swap(inner, inner + 1);
}
}
}
}
private static void swap(int item1, int item2)
{
int temp = arr[item1];
arr[item1] = arr[item2];
arr[item2] = temp;
}
public int seqSearch(int sValue)
{
for (int index = 0; index < arr.Length; index++)
{
if (arr[index] > sValue)
{
compCount = compCount + 1;
continue;
}
else
if (arr[index] < sValue)
{
compCount = compCount + 1;
continue;
}
else
{
return compCount;
}
}
return compCount; } public static int SeqSearch(int sValue)
{
for (int index = 0; index < arr.Length; index++)
{
if (arr[index] > sValue)
{
compCount = compCount + 1;
continue;
}
else
if (arr[index] < sValue)
{
compCount = compCount + 1;
continue;
}
else
{
compCount = compCount + 1;
swap(index, 0);
return compCount;
}
}
return compCount;
} public int binSearch(int value)
{
int upperBound, lowerBound, mid;
upperBound = arr.Length - 1;
lowerBound = 0;
while (lowerBound <= upperBound)
{
mid = (upperBound + lowerBound) / 2;
if (arr[mid] == value)
{
return compCount;
}
else
{
if (value < arr[mid])
{
compCount = compCount + 1;
upperBound = mid - 1;
}
else
{
compCount = compCount + 1;
lowerBound = mid + 1;
}
}
}
return compCount;
}
public int RbinSearch(int value, int lower, int upper)
{
if (lower > upper)
{
return compCount;
} else
{
int mid = (upper + lower) / 2;
if (value == arr[mid])
{
return compCount;
}
else
{
if (value < arr[mid])
{
compCount = compCount + 1;
return RbinSearch(value, lower, mid - 1);
}
else
{
compCount = compCount + 1;
return RbinSearch(value, mid+1, upper);
}
}
}
} static void Main(string[] args)
{
Random random = new Random();
CArray mynums = new CArray(1000);
for (int i = 0; i < 1000; i++)
mynums.Insert(random.Next(1000));
Console.WriteLine(" 顺序查找比较了: " + mynums.seqSearch(734) + " 次");
Console.WriteLine("自组织数据查找比较了: " + CArray.SeqSearch(734) + " 次");
mynums.BubbleSort();
Console.WriteLine(" 二分法比较了: " + mynums.binSearch(734) + " 次");
Console.WriteLine(" 递归二分法比较了: " + mynums.RbinSearch(734, 0, 999) + " 次");出现的结果如下:没有找到的情况下是:
顺序查找比较了:1000 次");
自组织数据查找比较了:2000 次");
二分法比较了:2010 次");
递归二分法比较了:2020 次");找到的情况下是:
顺序查找比较了:206 次");
自组织数据查找比较了:413 次");
二分法比较了:421 次");
递归二分法比较了:429 次");按理说前2种方法和后2种方法本质上是一样的,为什么这里显示的次数都不一样呢??请求各位大侠帮忙找错解答啊。。
我的代码如下:
class CArray
{
private static int[] arr;
private int numElements=0;
private static int compCount=0;
public CArray(int size)
{
arr = new int[size];
}
public void Insert(int item)
{
arr[numElements] = item;
numElements++;
}
public void DisplayElements()
{
for (int i = 0; i <arr.Length; i++)
Console.Write(arr[i] + " ");
}
public void BubbleSort()
{
for (int outer = arr.Length-1; outer >= 1; outer--)
{
for (int inner = 0; inner <= outer - 1; inner++)
{
if ((int)arr[inner] > arr[inner + 1])
{
swap(inner, inner + 1);
}
}
}
}
private static void swap(int item1, int item2)
{
int temp = arr[item1];
arr[item1] = arr[item2];
arr[item2] = temp;
}
public int seqSearch(int sValue)
{
for (int index = 0; index < arr.Length; index++)
{
if (arr[index] > sValue)
{
compCount = compCount + 1;
continue;
}
else
if (arr[index] < sValue)
{
compCount = compCount + 1;
continue;
}
else
{
return compCount;
}
}
return compCount; } public static int SeqSearch(int sValue)
{
for (int index = 0; index < arr.Length; index++)
{
if (arr[index] > sValue)
{
compCount = compCount + 1;
continue;
}
else
if (arr[index] < sValue)
{
compCount = compCount + 1;
continue;
}
else
{
compCount = compCount + 1;
swap(index, 0);
return compCount;
}
}
return compCount;
} public int binSearch(int value)
{
int upperBound, lowerBound, mid;
upperBound = arr.Length - 1;
lowerBound = 0;
while (lowerBound <= upperBound)
{
mid = (upperBound + lowerBound) / 2;
if (arr[mid] == value)
{
return compCount;
}
else
{
if (value < arr[mid])
{
compCount = compCount + 1;
upperBound = mid - 1;
}
else
{
compCount = compCount + 1;
lowerBound = mid + 1;
}
}
}
return compCount;
}
public int RbinSearch(int value, int lower, int upper)
{
if (lower > upper)
{
return compCount;
} else
{
int mid = (upper + lower) / 2;
if (value == arr[mid])
{
return compCount;
}
else
{
if (value < arr[mid])
{
compCount = compCount + 1;
return RbinSearch(value, lower, mid - 1);
}
else
{
compCount = compCount + 1;
return RbinSearch(value, mid+1, upper);
}
}
}
} static void Main(string[] args)
{
Random random = new Random();
CArray mynums = new CArray(1000);
for (int i = 0; i < 1000; i++)
mynums.Insert(random.Next(1000));
Console.WriteLine(" 顺序查找比较了: " + mynums.seqSearch(734) + " 次");
Console.WriteLine("自组织数据查找比较了: " + CArray.SeqSearch(734) + " 次");
mynums.BubbleSort();
Console.WriteLine(" 二分法比较了: " + mynums.binSearch(734) + " 次");
Console.WriteLine(" 递归二分法比较了: " + mynums.RbinSearch(734, 0, 999) + " 次");出现的结果如下:没有找到的情况下是:
顺序查找比较了:1000 次");
自组织数据查找比较了:2000 次");
二分法比较了:2010 次");
递归二分法比较了:2020 次");找到的情况下是:
顺序查找比较了:206 次");
自组织数据查找比较了:413 次");
二分法比较了:421 次");
递归二分法比较了:429 次");按理说前2种方法和后2种方法本质上是一样的,为什么这里显示的次数都不一样呢??请求各位大侠帮忙找错解答啊。。
不过csdn女纸太多
->429(變化8和你上次一樣)
zhangandli
(人生无悔)