应用题   请使用VC6或使用【答题】菜单打开proj3下的工程proj3,其中声明了SortedList类,是一个用于表示有序数据表的类。其成员函数insert的功能是将一个数据插入到一个有序表中,使得该数据表仍然保持有序。请编写这个insert函数。程序的正确输出应为:
    插入前:
    1,2,4,5,7,8,10
    插入6和3后:
    1,2,3,4,5,6,7,8,10
    要求:
    补充编制的内容写在“// ********333********”与“// ********666********”之间。不得修改程序的其他部分。
    注意:程序最后将结果输出到文件out.dat中。输出函数writeToFile已经编译为obj文件,并且在本程序中调用。
    //SortedList.h
    #include <iostream>
    using namespace std;
    class SortedList {  //有序数据表类
    int len;
    double * d;
    public:
    SortedList (int len, double data[] = NULL);
    ~SortedList() {delete [] d;}
    int length() const {return len;}  //有序数据表长度(即元素的个数)
    double getElement (int i) const {return d[i];}
    void insert (double data);
    void show() const;  //显示有序数据表
    };
    void writeToFile (char *, const SortedList &);        //main.cpp
    #include 'SortedList.h'        SortedList::SortedList (int len, double data[]):len(len){
    d = new double[len];
    for(int k = 0; k < len; k++)
    d[k] = (data == NULL? 0.0:data[k]);
    for(int i = 0; i < len-1; i++) {
    int m=i;
    for(int j = i; j < len; j ++)
    if(d[j] < d[m]) m=j;
    if (m > i) {
    double t = d[m];
    d[m] = d[i];
    d[i] = t;
    }
    }
    }
    void SortedList::insert (double data) {
    // ********333********
        // ********666********
    }
    void SortedList::show() const {  //显示有序数据表
    for(int i = 0; i < len - 1; i++)
    cout << d[i] << ',';
    cout << d[len - 1] << endl;
    }
    int main() {
    double s[] = {5,8,1,2,10,4,7};
    SortedList list(7,s);
    cout << '插入前:' << endl;
    list.show();
    list.insert(6.0);
    list.insert(3.0);
    cout << '插入6和3后:' << endl;
    list.show();
    writeToFile(' ', list);
    return 0;
    }
 
【正确答案】for(int i = 0; i < len; ++i) //遍历数组d if(data < d[i]) //如果data小于d[i] { len++; //数组d的长度自加1 double * dd = new double[len]; //分配长度为len空间 for (int k = len; k>i; k--) //在数组d中从k等于len到i做遍历 dd[k] = d[k-1]; //把d[k-1]赋值给dd[k] dd[i] = data; //把data赋值给dd[i] for (int j = 0; j < i; j ++) //把数组d从0到i做遍历 dd[j] = d[j]; //把d[j]赋值给dd[j] delete []d; //删d分配的空间 d = new double[len]; //给d分配长度为len的空间 for (int index = 0; index < len; ++index) //遍历数组dd从0到len d[index] = dd[index]; //地dd[index]赋值给d[index] delete []dd; //删dd分配的空间 break; //跳出循环 } 答案考生文件夹
【答案解析】[考点] 主要考查SortedList类,其中涉及动态数组、构造函数、析构函数、const函数和排序算法。插入算法有两个步骤,一是比较,即要插入的元素在哪里;二是插入元素,后面的元素要逐个后移一位,为新加入的元素空出位置。 主要考查考生对插入算法的掌握,题目要求insert函数的功能是将一个数据插入到一个有序表中,使得该数据表仍保持有序。可以知道数据表d是一组有序的数组,那么就采取先比较再插入的步骤完成即可。 要注意动态数组d的长度是确定的,要添加元素,就要重新分配空间。