数据结构还真是有点难....
emmmm....
这次是查找以及排序的数据结构,其中,排序的函数如下,该排序是<b>快速排序</b>
基本思路是:利用递归,遍历数组,并将其分为枢轴的左右两边,然后再将左右两边也分开,所以该递归函数需要传递两个参数,low和high,
至于枢轴,枢轴是进行一次排序后,返回的值。
<blockquote>
int partition(int low,int high) { 
       //不能取地址,否则会将原来的值覆盖而导致low,high循环一次到相同位置之后无法再循环
    int key;
    key = a[low];//将子表的第一个记录作为枢轴
    while (low< high) { 
        while (low<high&&a[high]>key) high--;
        swap(a[low], a[high]);//将枢轴右边比枢轴小的交换到低端
        //谁与谁交换??high指针所指的比数轴小的数与low指针所指的数交换
        while (low < high&&a[low] < key) low++;
        swap(a[low], a[high]);//将枢轴左边比枢轴大的交换到高端
    }
    return low;//此时的low==high,前面的while循环遍历了一遍数组
}//一次快速排序的算法,扫描一遍,并返回下一次排序枢轴的位置
void Qsort(int low,int high) {
    if (low < high) {
        int key = partition(low, high);//枢轴
        Qsort(low, key);//枢轴左边进行排序
        Qsort(key+1, high);//枢轴右边进行排序
    }
}//快速排序
</blockquote>
<b>查找</b>本次实验用的是二分查找,主要是遍历数组,判断key与middle的大小,并不断调整区间,查找较为简单,以下是二分查找的代码
<blockquote>
int Search(int key,int n) {
    int low = 0,high = n;
    while(low <= high) { //等号需存在,因为可能两个指针都指向同一个数,且该数就是需要查找的数的情况
        int mid = (low + high) / 2;
        if (a[mid] < key) low = mid+1;
        if (a[mid] > key) high = mid-1;
        if (a[mid] == key) return mid;
    }
    return -1;
}//二分查找
</blockquote>