C++ 程序 查找排序 高手帮我编这个程序

2025-02-27 06:40:19
推荐回答(1个)
回答1:

确定是C++程序? 下面的代码,只是输入输出部分使用了c++,其他部分,还是c。 除了主函数main,还定义了3个函数:selectionSort - 选择排序;binarySearch - 折半(二分)查找;printArray - 这是辅助函数,打印array里面的数据(排序前、后,供对比用)。

#include 
#include 

using namespace std;

int selectionSort(int data[], const size_t length);
int binarySearch(int data[], int low, int high, const int key);
void printArray(const int arr[], const size_t len);

int main(int argc, char** argv) 
{    
    const size_t SIZE(15); // 可修改
    int pos, key, i;
    int a[SIZE];

    //任务1 - 输入排序
    cout << "Please input " << SIZE << " numbers:" << endl;
    //强制检验用户的输入为整数
    i = 0;
    while (i < SIZE ) {
        cout << i+1 << ": ";        
        cin >> a[i];
        if( cin.fail() ) {            
            cin.clear();
            cin.ignore(numeric_limits::max(),'\n');
            cout << "  invalid input, try again." << endl;
            continue;
        }            
        cin.ignore(numeric_limits::max(),'\n');
        if (cin.gcount() > 1) {
            cout << "  error, try input again." << endl;
            continue;
        }
        i++;
    }    

    //排序前、后的输出对比 - 可注释掉
    printArray(a, SIZE); // print out array before sorting.
    selectionSort(a, SIZE);
    printArray(a, SIZE); // print out after sorting.

    //任务2 - 输入查找
    cout << "Input a number for searching." << endl;
    //用户输入校验 - 必须是整数
    while (true) {
        cin >> key;
        if (cin.fail()) {
            cin.clear()    ;
            cin.ignore(numeric_limits::max(), '\n');
            cout << "invalid, try again." << endl;
            continue;
        }
        cin.ignore(numeric_limits::max(), '\n');
        if (cin.gcount() > 1) {
            cout << "invalid, try again." << endl;
            continue;
        }
        break;
    }

    //折半查找
    pos = binarySearch(a, 0, SIZE-1, key);    
    if (pos == -1)
        cout << key << " not found." << endl;
    else // 注意: pos+1 (换成基于1开始), 
        cout << "The key is the no." << pos+1 << " element." << endl;

    return 0;
}

int selectionSort(int data[], const size_t length) 
{
    int i, j, _temp, min;

    if (length == 0) return 0;
    if (data == 0) return -1;
    
    for (i = 0; i < length-1; i++)    
    {
        min = i;
        for (j = i+1; j < length; j++)
            if (data[min] < data[j])
               min = j;
        
        if (min != i)                      
        {
            _temp = data[min];
            data[min] = data[i];
            data[i] = _temp;
        }
    }

    return 0;
}

void printArray(const int arr[], const size_t len)
{
    int i;
    
    for (i = 0; i < len; i++)
        cout << arr[i] << " ";        
        
    cout << endl;            
}

int binarySearch(int data[], int low, int high, const int key)
{
    size_t mid;
    
    while (high >= low)
    {
        mid = low + ((high-low) >> 1);
        if (data[mid] == key)
            return mid;
        else if (data[mid] > key) /* Array is descendent !!!*/
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

输出:

Please input 15 numbers:
1: a
  invalid input, try again.
1: 1
2: 2
3: 3
4: 123b
  error, try input again.
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15 this is demo
  error, try input again.
15: 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Input a number for searching.
8
The key is the no.8 element.