顺序表

顺序表是线性表基于数组的存储表示。

类定义及操作

类声明

#include <iostream.h>
#include <stdlib.h>
#include "linearList.h"
const int defaultSize = 100;
template <class T>
class SeqList: public LinearList<T> {
	protected:
		T *data;
		int maxSize;
		int last;
		void reSize(int newSize);
		
	public:
		SeqList(int sz = defaultSize);
		SeqList(SeqList<T>& L);
		~SeqList() {delete[] data;}
		int Size() const {return maxSize;}
		int Length() const {return last + 1;}
		int Search(T& x) const;
		int Locate(int i) const;
		T* getData(int i) const {
			return (i > 0 && i <= last + 1) ? &data[i - 1] : NULL;}
		void setData(int i, T& x) {
			if (i > 0 && i <= last + 1) data[i - 1] = x;}
		bool Insert(int i, T& x);
		bool Remove(int i, T& x);
		bool IsEmpty() {return (last == -1) ? true : false;}
		bool IsFull() {return (last == maxSize - 1) ? true : false;}
		void input();
		void output();
		SeqList<T> operator=(SeqList<T>& L);
}

注意，const成员函数执行时不能调用非const成员函数。

构造函数和复制构造函数

template <class T>
SeqList<T>::SeqList(int sz) {
	if (sz > 0) {
		maxSize = sz;
		last = -1;//空表
		data = new T[maxSize];
		if (data == NULL) {
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
	}
}

template <class T>
SeqList<T>::SeqList(SeqList<T>& L) {
	maxSize = L.Size();
	last = L.Length() - 1;
	data = new T[maxSize];
	if (data == NULL) {
		cerr << "存储分配错误！" << endl;
		exit(1);
	}
	for (int i = 1; i <= last + 1; i ++) {
		data[i - 1] = L.getData(i);
	}
}

修改存储空间大小

template <class T>
void SeqList<T>::reSize(int newSize) {
	if (newSize <= 0) {
		cerr << "无效的数组大小" << endl;
		return;
	}
	if (newSize != maxSize) {
		T* newarray = new T[newSize];
		if (newarray == NULL) {
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
		int n = last + 1
		T* srcptr = data;
		T* destptr = newarray;
		while (n--) {
			*destptr ++ = *scrptr ++;
		}
		delete []data;
		data = newarray;
		maxSize = newSize;
	}
}

搜索和定位

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 {
	if (i >= 1 && i <= last + 1) {
		return i;
	} else {
		return 0;
	}
}

插入与删除

template <class T>
bool SeqList<T>::Insert(int i, T& x) {
	if (last == maxSize - 1) {
		return false;
	}
	if (i < 0 || i > last + 1) {
		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 (last == -1) {
		return false;
	}
	if (i < 1 || i > last + 1) {
		return false;
	}
	x = data[i - 1];
	for (int j = i; j <= last; j++) {
		data[j - 1] = data[j];
	}
	last--;
	return true;
}

各个表元素必须相继存放于一个内存空间内，不准跳跃存放。这也是顺序表与一维数组的差别，一维数组只有两个操作：下标存或下标取，这样，在一维数组中数据可能是跳跃的、不连续存放的。