链表.cpp [数据结构实现 之 线性表]

#include   
#include   
#include   
#include   
using namespace std;  
  
const int OVERFLOW = -2;  
const int LIST_INIT_SIZE = 100;  
const int LISTINCREMENT = 10;  
  
enum status {success,underflow,overflow,range_error};  
class SqList  
{  
private:  
    int *data;  
    int length;  
  
protected:  
    int listSize;  
  
public:  
    SqList();  
    ~SqList();  
  
    bool empty(void) const;  
    int size(void) const;  
  
    status create(int num);  
    status insert(int position,const int &item);  
    status replace(int position,const int &item);  
    status remove(int position);  
  
    status get(int position,int &item) const;  
    status traverse(void) const;  
  
    status invert(void);  
};  
SqList::SqList()  
{  
    data = (int *)malloc(LIST_INIT_SIZE * sizeof(int));  
    if (!data)  
        exit(OVERFLOW);  
    length = 0;  
    listSize = LIST_INIT_SIZE;  
}  
SqList::~SqList()  
{  
    free(data);  
    data = NULL;  
    length = listSize = 0;  
}  
  
bool SqList::empty(void) const  
{  
    return (length == 0);  
}  
int SqList::size(void) const  
{  
    return length;  
}  
  
status SqList::create(int num)  
{  
    cout << "Please input " << num << " numbers: ";  
    while (listSize < num)  
    {  
  
        int *newbase = (int *)realloc(data,(listSize + LISTINCREMENT)*sizeof(int));  
        if (!newbase)  
            exit(OVERFLOW);  
        data = newbase;  
        listSize += LISTINCREMENT;  
    }  
    length = num;  
    for (int i = 0; i < length; i++)  
        cin >> data[i];  
  
    return success;  
}  
status SqList::insert(int position,const int &item)  
{  
    if (position < 1 || position > length + 1)  
        return overflow;  
  
    if (length >= listSize)  
    {  
        int *newBase = (int *)realloc(data,(listSize+LISTINCREMENT)*sizeof(int));  
        if (!newBase)  
            exit(OVERFLOW);  
        data = newBase;  
        listSize += LISTINCREMENT;  
    }  
    int *q = &(data[position - 1]);  
    for (int *p = &(data[length-1]); p >





= q; --p)  
        *(p+1) = *p;  
    *q = item;  
    ++length;  
    return success;  
}  
status SqList::replace(int position,const int &item)  
{  
    if (position < 1 || position > length)  
        return range_error;  
    if (empty())  
        return underflow;  
    data[position-1] = item;  
    return success;  
}  
status SqList::remove(int position)  
{  
    if (empty())  
        return underflow;  
    if (position < 1 || position > length)  
        return range_error;  
    for (int i = position - 1; i < length-1; i++)  
        data[i] = data[i+1];  
    length--;  
    return success;  
}  
  
status SqList::get(int position,int &item) const  
{  
    if (empty())  
        return underflow;  
    if (position < 1 || position > length)  
        return range_error;  
    item = data[position-1];  
    return success;  
}  
status SqList::traverse(void) const  
{  
    if (empty())  
        return underflow;  
  
    cout << "All the data :" ;  
    for (int i = 0; i < length; i++)  
        cout << ' ' << setw(3) << data[i];  
    cout << endl;  
    return success;  
}  
  
status SqList::invert(void)  
{  
    int halfpos,tempdata;  
    if (empty())  
        return underflow;  
    halfpos = length / 2;  
    for (int i = 0; i < halfpos; i++)  
    {  
        tempdata = data[i];  
        data[i] = data[length-i-1];  
        data[length-i-1] = tempdata;  
    }  
    return success;  
}  
int main()  
{  
    freopen("input.txt","r",stdin);  
    SqList L;  
    L.create(5);  
    for (int i = 6; i < 20; i++)  
        L.insert(i,i*10);  
    L.traverse();  
    cout << L.size() << endl;  
    L.remove(1);  
    L.traverse();  
    cout << L.size() << endl;  
    L.invert();  
    L.traverse();  
    int item;  
    L.get(2,item);  
    cout << "Item is: " << item << endl;  
}