顺序线性表

开发环境：Eclipse

参考书籍：《数据结构》——清华大学出版社——殷人昆

 

 

SeqList.h

 

 

/*
 * SeqList.h
 *
 *  Created on: Jun 5, 2010
 *      Author: limx
 */

#include<iostream.h>
#include<stdlib.h>

const int defaultSize = 100;
template<class T>
class SeqList {
protected:
	T * data;
	//the size of the seqList
	int maxSize;
	//the array subscript of last element
	int last;
	void reSize(int newSize);
public:
	//defaultSize is the default parameter;
	SeqList(int sz = defaultSize);
	virtual ~SeqList();
	//const is mean that the parameter inside can not change
	int size() const {
		return maxSize;
	}
	//get the element at the array subscript i;
	bool getData(int i, T& x);
	T getData(int i);
	//copy the seqlist constructor
	SeqList(SeqList<T>& L);
	int length() const {
		return last;
	}
	//search the element by value x
	int search(T x) const;
	//insert element x into the array at subscript i ;
	bool insert(int i, T & x);
	//remove element of array subscript at i ;
	bool remove(int i, T&x);
	void input();
	void output();
	SeqList<T> operator =(SeqList<T> & L);
};

 

 

SeqList.cpp

 

 

/*
 * SeqList.cpp
 *
 *  Created on: Jun 5, 2010
 *      Author: limx
 */
#include"SeqList.h"
template<class T>
SeqList<T> SeqList<T>::operator =(SeqList<T> & L) {
	maxSize = L.size();
	last = L.length();
	data = new T[maxSize];
	if (data == NULL) {
		{
			cerr << "memory error !" << endl;
			exit(1);
		}
	}
	for (int i = 0; i <= last; i++) {
		data[i] = L.getData(i);
	}
}
template<class T>
T SeqList<T>::getData(int i) {
	if (0 <= i && i <= last) {
		return data[i];
	} else {
		return NULL;
	}
}
template<class T>
bool SeqList<T>::getData(int i, T& x) {
	if (0 <= i && i <= last) {
		x = data[i];
		return true;
	} else {
		return false;
	}
}
template<class T>
SeqList<T>::SeqList(SeqList<T>& L) {
	maxSize = L.size();
	last = L.length();
	data = new T[maxSize];
	if (data == NULL) {
		{
			cerr << "memory error !" << endl;
			exit(1);
		}
	}
	for (int i = 0; i <= last; i++) {
		data[i] = L.getData(i);
	}

}
template<class T>
//delete the element at i ,i is the array subscript;
bool SeqList<T>::remove(int i, T&x) {
	if (last < 0) {
		return false;
	}
	if (i < 0 || i > last + 1) {
		return false;
	}
	x = data[i];
	for (int j = i; j <= last; j++) {
		data[j] = data[j + 1];
	}
	last--;
}
template<class T>
SeqList<T>::SeqList(int sz) {
	// TODO Auto-generated constructor stub
	if (sz > 0) {
		maxSize = sz;
		last = -1;
		data = new T[maxSize];
		//		null must be upper
		if (data == NULL) {
			cerr << "memory error!" << endl;
			exit(1);
		}
	}

}

template<class T>
SeqList<T>::~SeqList() {
	// TODO Auto-generated destructor stub
}
//insert the element at the location at ith,i is an array subscript;
template<class T>
bool SeqList<T>::insert(int i, T & x) {
	if (last == maxSize - 1) {
		return false;
	} else 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>
int SeqList<T>::search(T x) const {
	for (int i = 0; i <= last; i++) {
		if (data[i] == x) {
			return i;
		}
	}
	return -1;
}
template<class T>
void SeqList<T>::input() {
	cout << "begin to create seqlist:" << endl;
	while (1) {
		cin >> last;
		if (last <= maxSize - 1) {
			break;
		}
		cout << "out of index" << maxSize - 1 << ":" << endl;
	}
	cout << "input the elements plz" << endl;
	for (int i = 0; i <= last; i++) {
		cout << i + 1 << ":";
		cin >> data[i];
	}
}

template<class T>
void SeqList<T>::output() {
	cout << "the last element of location in the current list is :" << last
			<< endl;
	for (int i = 0; i <= last; i++) {
		cout << "#" << i << ":" << data[i] << endl;
	}
}

 

main.cpp

 

 

/*
 * main.cpp
 *
 *  Created on: Jun 5, 2010
 *      Author: limx
 */

#include<iostream.h>
#include"SeqList.cpp"
using namespace std;
int main() {
	SeqList<char> sl(20);
	int index;
	char x;
	/*I need to read about array*/
	/*int* x = new int[10];*/
	cout << "input the elements" << endl;
	sl.input();
	sl.output();
	cout << "the size of sl" << sl.size();
	cout << "enter the element to search:" << endl;
	cin >> x;
	cout << "the element to search is at " << sl.search(x) << endl;
	cout << "enter the subscript of the element and the element to insert:"
			<< endl;
	cin >> index >> x;
	sl.insert(index, x);
	sl.output();
	cout << "cope the array of sl" << endl;
	SeqList<char> sl2(20);
	sl2 = sl;
	cout << "the element of sl2 is below:" << endl;
	sl2.output();
	return 0;
}

 

result :

 

 

input the elements
begin to create seqlist:
4
input the elements plz
1:a
2:b
3:c
4:d
5:e
the last element of location in the current list is :4
#0:a
#1:b
#2:c
#3:d
#4:e
the size of sl20enter the element to search:
a
the element to search is at 0
enter the subscript of the element and the element to insert:
5
f
the last element of location in the current list is :5
#0:a
#1:b
#2:c
#3:d
#4:e
#5:f
cope the array of sl
the element of sl2 is below:
the last element of location in the current list is :5
#0:a
#1:b
#2:c
#3:d
#4:e
#5:f