Data Structure Sequence Table

Data Structure Sequence Table

Main member functions: (excluding constructors and destructors)

Function name function
int Size()const Return the size of the sequential table
int Length()const Returns the number of elements in the actual table
int Search(T&x)const Returns the location of x in the table
int Locate(int i)const Return the legal position represented by i
bool getData(int i, T& x)const Returns whether the value at i exists, and if so, stores it in x
void setData(int i, T& x) Set the value at i to x
bool insert(int i ,T& x) Inserting x into i and returning whether the insertion was successful
bool remove(int i, T& x) Delete the value at i and return whether the deletion was successful, while storing the deleted value in x
bool isEmpty() Is the return table empty?
bool isFull() Is the return table full?

Its class definition:

#include<iostream>
#include<cstdlib>
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList{
protected:
 T* data;
 int maxSize;
 int last;
 void reSize(int newSize);
 public:
 SeqList(int size=defaultSize);//Note the default initialization of size here, where you can also enter the size you want.
 ~SeqList();
 SeqList(SeqList<T>& L);
 int Size()const { return maxSize; }//Marking const improves the readability of the program and ensures that the values of class members are not changed within the function.
 int length()const { return last + 1; }
 int Search(T& x)const;
 int Locate(int i)const;
 bool getData(int i, T& x)const;
 void setData(int i, T& x);
 bool insert(int i ,T& x);
 bool remove(int i, T& x);
 bool isEmpty() { return last == -1; }
 bool isFull() { return last + 1 == maxSize; }
 void input();//It is easier to construct a new order table with input function
 void output();
 SeqList<T>operator=(SeqList<T>& L);
};

In particular, it is proposed that:

 bool getData(int i, T& x)const;

This method does not return data directly with function values, but uses bool type, which is more secure. It can first analyze the input data is not valid and then proceed to the next operation, which is not easy to be dangerous.
Passing values by reference is simpler and easier to operate

Pay special attention to the resize() function:
Originally I wrote:

template<class T>
void SeqList<T>::reSize(int newSize)
{
 maxSize += newSize;
 T* newData;
 newData = new T[maxSize];
 for (int i = 0; i <= last; i++)
   newData[i] = data[i];
 data = newData;
 delete[]newData;
}

The code on the book:

template<class T>
void SeqList<T>::reSize(int newSize)
{
 if (newSize <=0)
 {
  cerr << "Invalid large array size" << endl; return;
 }
 if (newSize != maxSize)
  {
  T* newarray = new T[newSize];
  if (newarray == NULL)
  {
   cerr << "Allocation error" << endl; exit(1);
  }
  int n = last + 1;
  T* temp1 = data;
    T* temp2 = newarray;
  while (n--)* temp2++ = *temp1++;
  delete[]data;
  data = newarray;
  maxSize = newSize;
   }
}

The comparison shows that 1. Special value should be judged.
2. When allocating memory, it is necessary to check whether the allocation is successful, because it is possible that the allocation will fail, affecting subsequent operations.
3. Be careful not to use cout instead of cerr when re-exporting error messages.
4. # # If you operate like me, you will delete the stored value first, because data and new data point to the same address, and then delete first. Otherwise, after conversion, the original memory address will be lost and the original memory can not be cleaned up.

Make sure that all memory allocations are successful before proceeding to the next step.

Total code:

#include<iostream>
#include<cstdlib>
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList{
protected:
	T* data;
	int maxSize;
	int last;
	void reSize(int newSize);

public:
	SeqList(int size=defaultSize);
	~SeqList();
	SeqList(SeqList<T>& L);
	int Size()const { return maxSize; }
	int length()const { return last + 1; }
	int Search(T& x)const;
	int Locate(int i)const;
	bool getData(int i, T& x)const;
	void setData(int i, T& x);
	bool insert(int i ,T& x);
	bool remove(int i, T& x);
	bool isEmpty() { return last == -1; }
	bool isFull() { return last + 1 == maxSize; }
	void input();
	void output();
	SeqList<T>operator=(SeqList<T>& L);
};
template<class T>
void SeqList<T>::reSize(int newSize)
{
	if (newSize <=0)
	{
		cerr << "Invalid large array size" << endl; return;
	}
	if (newSize != maxSize)
	{
		T* newarray = new T[newSize];
		if (newarray == NULL)
		{
			cerr << "Allocation error" << endl; exit(1);
		}
		int n = last + 1;
		T* temp1 = data;
		T* temp2 = newarray;
		while (n--)* temp2++ = *temp1++;
		delete[]data;
		data = newarray;
		maxSize = newSize;
	}
}
template<class T>
SeqList<T>::SeqList(int size) {
	maxSize = size;
	data = new T[maxSize];
	last = -1;
}
template<class T>
SeqList<T>::~SeqList()
{
	delete[]data;
}
template<class T>
SeqList<T>::SeqList(SeqList<T>& L)
{
	maxSize = L.maxSize;
	last = L.last;
	data = new T[maxSize];
	for (int i = 0; i <= last; i++)
	{
		data[i] = L.getData[i];
	}
}

template<class T>
int SeqList<T>::Search(T& x)const
{
	for (int i = 0; i <= last; i++)
	{
		if (data[i] == x)
		{
			return i+1;
		}
	}
	return 0;
}
template<class T>
int SeqList<T>::Locate(int i)const//Here i is the number of elements
{
	if (i >= 1 && i <= last + 1)return i;
	return 0;
}
template<class T>
bool SeqList<T>::getData(int i, T& x)const
{
	if (Locate(i)) {
		x = data[i-1];
		return true;
	}
	else
		return false;
}
template<class T>
void SeqList<T>::setData(int i, T& x)
{
	if (Locate(i))
	{
		data[i - 1] = x;
	}
}
template<class T>
bool SeqList<T>::insert(int i, T& x)
{
	if (isFull() || !Locate(i))return false;
	for (int j = last; j >= i; j--)
	{
		data[j + 1] = data[j];
	}
	data[i] = x;
	last++;
	return true;
}
template<class T>
bool SeqList<T>::remove(int i, T& x)
{
	if (!Locate(i)||isEmpty())return false;
	x = data[i - 1];
	for (int j = i; j <= last; j++)
	{
		data[j - 1] = data[j];
	}
	last--;
	return true;
}
template<class T>
void SeqList<T>::input()
{
	cout << "Please enter the number of elements and their values." << endl;
	cin >> last;
	for (int i = 0; i <= last; i++)
		cin >> data[i];
}
template<class T>
void SeqList<T>::output()
{
	for (int i = 0; i <= last; i++)
		cout << data[i] << " ";
		cout << endl;
}
template<class T>//I'm lazy here. Actually, it's almost like a copy constructor.
SeqList<T> SeqList<T>::operator=(SeqList<T>& L)
{
	SeqList<T> temp(L);
	return temp;
}

Posted on Fri, 06 Sep 2019 23:57:32 -0700 by knford