快速排序与折半查找

readme

关于本程序中的EOF说明：由于程序包含标准输入，以EOF结束循环。
win下EOF为“Enter”+“Ctrl Z”+“Enter”;
lunux下为“Enter”+“Ctrl D”

并且注意源代码主函数末尾有两个getchar()方便查看窗口信息。

注意c++中关于标准输入缓存区残留字符问题。在第二次标准输入之前需要有

cin.clear(); //清除错误标记  
cin.sync(); //清空缓冲区  

对缓存区先进行清除。

源代码

#include <iostream>

#define MAX 100

using namespace std;

typedef enum
{
    OK = 1,
    ERROR = 0
} Status;

typedef int ElemType;

typedef struct{
    ElemType name;
    int n;
} Apple;

int Partition(ElemType R[],int s,int t){
    int i = s, j = t;
    ElemType temp = R[i];
    while(i<j){
        while(j>i&&R[j]>=temp){
            j--;
        }
        R[i] = R[j];
        while(i<j&&R[i]<=temp){
            i++;
        }
        R[j] = R[i];
    }
    R[i] = temp;
    return i;
}

void QuickSort(ElemType R[],int s, int t){
    int i;
    if(s<t){
        i = Partition(R, s, t);
        QuickSort(R, s, i - 1);
        QuickSort(R, i + 1, t);
    }
}

Status BinSearch(ElemType R[],Apple *peach,int s,int t){
    int i = s, j = t;
    int mid;
    while(i<=j){
        mid = (i + j) / 2;
        if((*peach).name==R[mid]){
            (*peach).n++;
            if(mid!=s){
                if(R[mid-1]==R[mid]){
                    (*peach).n++;
                }
            }
            if(mid!=t){
                if(R[mid+1]==R[mid]){
                    (*peach).n++;
                }
            }
            return OK;
        }
        if((*peach).name<R[mid]){
            j = mid - 1;
        }
        else{
            i = mid + 1;
        }
    }
    return ERROR;
}


int main(void){
    int n = 0;
    Status status;
    ElemType A[MAX],temp;
    Apple banana;
    cout << "please enter a series of chaotic numbers divided by space(enter 'EOF' at the end of the inputs): ";
    while(cin>>temp){
        A[n++] = temp;
    }
    QuickSort(A, 0, n-1);
    cout << "The ordered array: ";
    for(int i=0;i<n;i++){
        cout << A[i]<<' ';
    }
    cin.clear(); //清除错误标记
    cin.sync(); //清空缓冲区
    cout <<endl<< endl<<"Please enter a number that you want to search(enter 'EOF' to drump out of the inputing circle): ";
    while(cin>>banana.name){
        banana.n = 0;
        status=BinSearch(A, &banana, 0, n - 1);
        if(status=OK){
            if(banana.n>1){
                cout << "Succeed! The \""<<banana.name<<"\" has more than 1 equal elements in the array!"<<endl;
            }
            else{
                cout << "Succeed! The \""<<banana.name<<"\" has 1 equal element in the array!"<<endl;
            }
        }
        else{
            cout << "Failed! The \""<<banana.name<<"\" has no element in the array!" << endl;
        }
        cout <<endl<< "Please enter a number that you want to search(enter 'EOF' to drump out of the inputing circle): ";
    }
    getchar();
    getchar();
    return 0;
}

运行结果

TIM图片20180616110922.png