Data structures — Linear tables (sequential tables)

Linear table is one of the most basic and simplest data structures. There is only a single precursor and successor relationship between data elements.

The order sheet

① Adopt static allocation mode

Using C++ template mechanism to define the template class SeqList.

const int MaxSize = 100; SeqList class SeqList{public: SeqList(); public: SeqList(); SeqList(DataType a[],int n); ~SeqList(){} // destructor int Length(); DataType Get(int I); Int Locate(DataType x); // Locate(DataType x); Void Insert(int I,DataType x); void Insert(int I,DataType x); DataType Delete(int I); // Insert DataType Delete(int I); // Delete the ith element bool Empty(); Void PrintList(); Private: DataType data[MaxSize]; // Array of data elements int length; // The length of the linear table};Copy the code

1. No-parameter constructor

template<typename DataType>
SeqList<DataType>::SeqList(){
    length = 0;
}
Copy the code

template<typename DataType>
SeqList<DataType>::SeqList(DataType a[],int n){
    if (n > MaxSize)
        throw "illegal parameter";
    for (int i=0; i<n; i++)
        data[i] = a[i];
    length = n;
}
Copy the code

template<typename DataType> bool SeqList<DataType>::Empty(){ return length==0? true:false; }Copy the code

template<typename DataType>
int SeqList<DataType>::Length(){
    return length;
}
Copy the code

template<typename DataType>
void SeqList<DataType>::PrintList(){
    for (int i=0; i<length; i++){
        cout << data[i] << "\t";
    }
    cout << endl;
}
Copy the code

Template <typename DataType> DataType SeqList<DataType>::Get(int I){// Find by bit, Time complexity is O (1) if (I < 1 | | I > length) throw "illegal search location"; else return data[i-1]; }Copy the code

Template <typename DataType> int SeqList<DataType>::Locate(DataType x){// Locate by value, time complexity is O(n) for (int I =0; i<length; i++){ if (data[i]==x) return i+1; } return -1; // Exit the loop, indicating that the search failed}Copy the code

Template <typename DataType> void SeqList<DataType>::Insert(int I,DataType x){ O(n) if (length==MaxSize) throw "overflow"; if (i<1 || i>length+1) throw "illegal insertion location"; for (int j=length; j>=i; j--){ data[j] = data[j-1]; } data[i-1] = x; length++; }Copy the code

Template <typename DataType> DataType SeqList<DataType>::Delete(int I){// Delete operation, time complexity is O(n) DataType x; if (length == 0) throw "underflow"; if (i<1 || i>length) throw "illegal deleted location"; x = data[i-1]; for (int j=i; j<length; j++){ data[j-1] = data[j]; } length--; return x; }Copy the code

const int InitSize = 100; Const int IncreSize = 10; Template <typename DataType> // Define the template class SeqList class SeqList{public: SeqList() is the same as the static allocation of the order table; SeqList(DataType a[],int n); ~SeqList(); // destructor int Length(); DataType Get(int I); Int Locate(DataType x); // Locate(DataType x); Void Insert(int I,DataType x); void Insert(int I,DataType x); DataType Delete(int I); // Insert DataType Delete(int I); // Delete the ith element bool Empty(); Void PrintList(); Private: DataType *data; private: DataType *data; Int maxSize; // The maximum length of the current array space int length; // The length of the linear table};Copy the code

In the dynamic assignment mode of the sequential table, the algorithm of the basic operations such as the length of the linear table, bitwise search, value search, delete, nulling and traversal is the same as that of the static assignment mode of the sequential table. The implementation of other basic operations is discussed below.

1. No-parameter constructor

template<typename DataType>
SeqList<DataType>::SeqList(){
    data = new DataType[InitSize];
    maxSize = InitSize; 
    length = 0;
}
Copy the code

2. Parameter constructors

template<typename DataType>
SeqList<DataType>::SeqList(DataType a[],int n){
    data = new DataType[2*n];
    maxSize = 2*n;
    for (int i=0; i<n; i++){
    	data[i] = a[i];
    }
    length = n;
}
Copy the code

destructors

template<typename DataType>
SeqList<DataType>::~SeqList(){
    delete[] data;
}
Copy the code

4. Insert operation O(n)

template<typename DataType> void SeqList<DataType>::Insert(int i,DataType x){ if (i<1 || i>length+1) throw "illegal insertion location"; If (length == maxSize){// If (length == maxSize){DataType *oldData = data; maxSize += IncreSize; data = new DataType[maxSize]; for (int j=0; j<length; j++){ data[j] = oldData[j]; } delete[] oldData; } for (int j=length; j>=i; j--){ data[j] = data[j-1]; } data[i-1] = x; length++; }Copy the code