顺序表

题目描述

 给出顺序表的初始数据，实现顺序表的定义、创建、插入、删除与查找操作。

输入

 测试次数t

每组测试数据格式如下：

第一行: 正整数n，后跟n个整数

第二行: 插入位置 插入元素

第三行: 删除位置

第四行: 删除元素

第五行: 查找元素

输出

对每个顺序表，首先输出建表后的顺序表。 

插入、删除操作，操作成功，输出操作后的顺序表。操作不成功，输出ERROR。

查找操作，查找成功，输出:1 元素位置（位置从1开始）比较次数。查找不成功，输出:0 0 比较次数。

样例输入

2

5 10 20 14 25 50

1 13

10

10

23

7 88 99 77 11 22 33 44

7 100

1

80

22

样例输出

5 10 20 14 25 50

6 13 10 20 14 25 50

ERROR

5 13 20 14 25 50

0 0 6

7 88 99 77 11 22 33 44

8 88 99 77 11 22 33 100 44

7 99 77 11 22 33 100 44

ERROR

1 4 4

实现细节：

代码注释中

代码：

#include <iostream>
#include <queue>
#include <string>
using namespace std;
class StaticSearchTable{
public:
    int length;                 //顺序表长度
    int *elem;                  //顺序表数组
    int really_length;          //顺序表所开的数组的实际长度
public:
    StaticSearchTable(){
        cin>>length;
        really_length=2*length;        //顺序表为方便插入，数组所开的实际长度为长度的2倍
        elem = new int[really_length];
        for(int i = 1; i< length+1; i++)    //0位置作为哨兵，从1位置开始存入顺序表元素
            cin>>elem[i];
    }
    ~StaticSearchTable(){};
    void PrintTable();
    bool Insert(int loc,int temp_elem);
    bool Delete_loc(int loc);
    bool Delete_elem(int key);
    int Search(int key);
};
void StaticSearchTable::PrintTable()    //先输出顺序表长度，后输出内容
{
    cout<<length<<' ';
    for(int i = 1; i< length+1; i++)
            cout<<elem[i]<<' ';
    cout<<endl;
}
bool StaticSearchTable::Insert(int loc,int temp_elem)    //插入操作，成功则返回true
{
    if(loc <= 0 || loc>length+1)
        return false;
    length++;
    if(length>really_length)        //插入时要先判断长度是否超过实际长度，如果超过，则需要把实际空间放大，通常是翻倍
    {
        really_length=2*really_length;
        int *new_elme = new int [really_length];
        for(int i = 0; i < length+1; i++)
            new_elme[i] = elem[i];
        delete[] elem;
        elem = new_elme;
    }
    for(int i = length; i > loc; i--)    //插入元素
        elem[i]=elem[i-1];
    elem[loc]=temp_elem;
    return true;
}
bool StaticSearchTable::Delete_loc(int loc)    //按下标删除，成功则返回true
{
    if(loc <= 0 || loc>length ||length == 0)
        return false;
    for(int i=loc;i<length;i++)
        elem[i]=elem[i+1];
    length--;
    return true;
}
int StaticSearchTable::Search(int key)    //查找操作，返回查找元素的下标，如果找不到，则返回顺序表长度+1，表示比较次数
{
    if(length==0)
        return 0;
    elem[0]=key;
    int i;
    for(i = length; i >= 0; i--)
        if(elem[i] == elem[0])
            break;
    if(i==0)
        return length+1;
    else
        return i;
}
bool StaticSearchTable::Delete_elem(int key)    //按值删除，成功则返回true
{
    int loc = Search(key);        //直接找要删除的值在顺序表中的下标
    if(loc != length+1)            //如果找得到
    {
        Delete_loc(loc);            //则按下标删除元素
        return true;
    }
    else
        return false;
}
int main()
{
    int loc,temp_elem,key;
    int t;
    cin>>t;
    while(t--)
    {
        StaticSearchTable test;
        test.PrintTable();

        cin>>loc>>temp_elem;
        if(test.Insert(loc,temp_elem))
            test.PrintTable();
        else
            cout<<"ERROR"<<endl;

        cin>>loc;
        if(test.Delete_loc(loc))
            test.PrintTable();
        else
            cout<<"ERROR"<<endl;

        cin>>key;
        if(test.Delete_elem(key))
            test.PrintTable();
        else
            cout<<"ERROR"<<endl;

        cin>>key;
        int temp = test.Search(key);
        if(temp == 0)
            cout<<0<<' '<<0<<' '<<0<<endl;
        else if(temp != test.length+1)
            cout<<1<<' '<<temp<<' '<<test.length-temp+1<<endl;
        else
            cout<<0<<' '<<0<<' '<<test.length+1<<endl;
    }
}