愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

PAT-练习3:顺序表操作

定义一个顺序表SeqList,并有基本运算:

void creat(SeqList *p)用于创建顺序表.
void insert(SeqList *p,int item)用于在顺序表中按序插入一个整数item,
void print(SeqList *p)用于输出结果。
顺序表的数据包括:

int *data;
int size;

编程实现:输入一个正整数 T(0<T<=10),表示case数,对于每个case: 输入一个正整数 n(0<n<=9)和一组(n个)升序的整数,再输入一个整数 x,把 x 插入到这组数据中,使该组数据仍然有序。
Input Specification

4 (repeat=4)
5 (数据的个数n=5)
1 2 4 5 7 (5个有序整数)
3 (待插入整数x=3)
4 (数据的个数n=4)
1 2 5 7 (4个有序整数)
-10 (待插入整数x=-10)
3 (数据的个数n=3)
1 2 4 (3个有序整数)
100 (待插入整数x=100)
5 (数据的个数n=5)
1 2 4 5 7 (5个有序整数)
4 (待插入整数x=4)
Output Specification

size=6:1 2 3 4 5 7
size=5:-10 1 2 5 7
size=4:1 2 4 100
size=6:1 2 4 4 5 7
Sample Input:
4
4 2 4 6 8 10
5 1 2 4 6 8 0
2 6 8 12
5 1 2 4 6 8 6
Sample Output:
size=5:2 4 6 8 10
size=6:0 1 2 4 6 8
size=3:6 8 12
size=6:1 2 4 6 6 8

#include <iostream>
#define MAXSIZE 11
using namespace std;

class SeqList {
private:
    int *data;
    int size;
public:
    SeqList() {
        this->data = NULL;
        this->size = 0;
    }
    void create() {
        this->data = new int[MAXSIZE];
    }
    void insert(int item) {
        if(this->size==0) {
            this->data[0] = item;
        } else {
            int i, key = -1;
            for(i=0; i<this->size; i++) {
                if(this->data[i]>=item) {
                    key=i;
                    break;
                }
            }
            if(key == -1) {
                this->data[this->size] = item;
            } else {
                int i, insertValue = item, temp = this->data[key];
                for(i=key; i<=this->size; i++) {
                    this->data[i] = insertValue;
                    insertValue = temp;
                    temp = this->data[i+1];
                }
            }
        }
        this->size++;
    }
    void print() {
        cout << "size=" << this->size << ":";
        for(int i=0; i<this->size; i++) {
            cout << this->data[i];
            if(i+1!=this->size) cout << " ";
        }
    }
};

int main() {
    int i,n,t,T;
    cin >> T;
    while(T>0) {
        SeqList sq;
        sq.create();
        cin >> n;
        for(i=0;i<n;i++) {
            cin >> t;
            sq.insert(t);
        }
        cin >> n;
        sq.insert(n);
        sq.print();
        if(--T>0) cout << endl;
    }
    
    return 0;
}