实验一、顺序表基本操作的实现
实验目的
1 理解顺序表类的定义；
2掌握顺序表存储基本操作；
3学会设计实验数据验证程序。
实验环境
计算机，window xp操作系统，VC++6.0
实验内容
顺序表类的定义
#include <iostream>
#include <cstdlib>
#include <cassert>
#include<iostream>
#include<stdlib.h>
using namespace std;
const int defaultSize = 100;
template <typename T>class SeqList{
protected:
T *data;
int maxSize;
int last;
public:
SeqList(int sz = defaultSize);
SeqList(SeqList<T> &L);
~SeqList(){
delete []data;
}
void reSize(int newSize);
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{//改
if(i>0 && i<=last+1){
x=data[i-1];
return true;
}
else return false;
}
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);
}
bool IsFull(){
return (last == maxSize-1);
}
void Sort();
void input();
void output();
SeqList<T> operator = (SeqList<T> &L);
friend istream& operator >> (istream &in, SeqList<T> &R){
R.last = -1;//先清空
while (!in.eof()){
R.last++;
if (R.last == R.maxSize) R.reSize(2*R.maxSize);
assert(in >> R.data[R.last]);
}
return in;
}
friend ostream& operator << (ostream &out, SeqList<T> &R){
for (int i = 0; i <= R.last; i++){
cout << "#" << i+1 << ":\t" << R.data[i] << endl;
}
return out;
}
};
template <typename T>SeqList<T>::SeqList(int sz){
if (sz > 0){
maxSize = sz;
last = -1;
data = new T[maxSize];
if (data == NULL){
cerr << "Memory allocating error!" << endl;
exit(1);
}
}
}
template <typename T>SeqList<T>::SeqList(SeqList<T> &L){
maxSize = L.Size();
last = L.Length() - 1;
data = new T[maxSize];
if (data == NULL){
cerr << "Memory allocating error!" << endl;
exit(1);
}
for (int i = 1; i <= last+1; i++) data[i-1] = *(L.getData(i));
}
template<typename T>void SeqList<T>::reSize(int newSize){
if (newSize <= 0){
cerr << "Invalid array index!" << endl;
return;
}
if (newSize != maxSize){
T *newarray = new T[newSize];
if (newarray == NULL){
cerr << "Memory allocating error!" << endl;
exit(1);
}
int n = last;//改
T *srcptr = data;
T *destptr = newarray;
while (n--) *destptr++ = *srcptr++;
delete []data;
data = newarray;
maxSize = newSize;
}
}
template<typename 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<typename T>int SeqList<T>::Locate(int i)const{
if (i >= 1 && i <= last+1) return i;
else return 0;
}
template<typename 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<typename 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;
}
template<typename T>void SeqList<T>::Sort(){
for (int i = 1; i <= last; i++){
for (int j = last; j >= i; j--){
if (data[j-1] > data[j]){
T tmp = data[j-1];
data[j-1] = data[j];
data[j] = tmp;
}
}
}
}
template<typename T>void SeqList<T>::input(){
cout << "Input the size of the list which will be created:";
while (1) {
assert(cin >> last);
last--;
if (last < 0){
cout << "Input error, the size must be positive!\n";
cout << "Input the size again:";
}
else if (last > maxSize-1){//改一改可以扩大
cout << "Input error, the size must be less than maxSize!\n";
cout << "Input the size again:";
}
else break;
}
cout << "\nInput the data for each element to create the list:" << endl;
for (int i = 0; i <= last; i++){
cout << "#" << i+1 << ":";
assert(cin >> data[i]);
}
}
template<typename T>void SeqList<T>::output(){
cout << "\nThe size of the list is:" << last+1 << endl;
for (int i = 0; i <= last; i++) cout << "#" << i+1 << ":\t" << data[i] << endl;
}
template<typename T>SeqList<T> SeqList<T>::operator = (SeqList<T> &L){//改
maxSize = L.Size();
last = L.Length()-1;
delete []data;//先清空
data = new T[maxSize];
if (data == NULL){
cerr << "Memory allocating error!" << endl;
exit(1);
}
for (int i = 1; i <= last+1; i++) data[i-1] = L.getData(i);
}
(1) 建立一个有20个数据的顺序表La，各节点值依次为：2,4,6,8,10,12，….,38,40
(2) 输出顺序表La
(3) 删除第8个结点；删除第30个结点；
(4) 输出表长；
(5) 在第五个结点后插入一个结点11；
(6) 分别查找值为28,45的元素；
(7) 建立线性表Lb，各结点值依次为：3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78
(8) 将La和Lb合并为线性表Lc；
(9) 输出La，Lb，Lc的以及各表的表长；
(10) 清空线性表La，Lb；
(11) 输出La，Lb的表长；
#include <iostream>
#include <cstdlib>
#include <cassert>
#include<iostream>
#include<stdlib.h>
using namespace std;
const int defaultSize = 100;
template <typename T>class SeLa {
protected:
T* data;
int maxSize;
int last;
public:
SeLa(int sz = defaultSize);
SeLa(SeLa<T>& L);
~SeLa() {
delete[]data;
}
void reSize(int newSize);
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 {//改
if (i > 0 && i <= last + 1) {
x = data[i - 1];
return true;
}
else return false;
}
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);
}
bool IsFull() {
return (last == maxSize - 1);
}
void Sort();
void input();
void output();
SeLa<T> operator = (SeLa<T>& L);
friend istream& operator >> (istream& in, SeLa<T>& R) {
R.last = -1;//先清空
while (!in.eof()) {
R.last++;
if (R.last == R.maxSize) R.reSize(2 * R.maxSize);
assert(in >> R.data[R.last]);
}
return in;
}
friend ostream& operator << (ostream& out, SeLa<T>& R) {
for (int i = 0; i <= R.last; i++) {
cout << "#" << i + 1 << ":\t" << R.data[i] << endl;
}
return out;
}
};
template <typename T>SeLa<T>::SeLa(int sz) {
if (sz > 0) {
maxSize = sz;
last = -1;
data = new T[maxSize];
if (data == NULL) {
cerr << "Memory allocating error!" << endl;
exit(1);
}
}
}
template <typename T>SeLa<T>::SeLa(SeLa<T>& L) {
maxSize = L.Size();
last = L.Length() - 1;
data = new T[maxSize];
T value;
bool isBoolean;
if (data == NULL) {
cerr << "Memory allocating error!" << endl;
exit(1);
}
for (int i = 1; i <= last + 1; i++) {
isBoolean = L.getData(i, value);
if (isBoolean)
data[i - 1] = value;
}
}
template<typename T>void SeLa<T>::reSize(int newSize) {
if (newSize <= 0) {
cerr << "Invalid array index!" << endl;
return;
}
if (newSize != maxSize) {
T* newarray = new T[newSize];
if (newarray == NULL) {
cerr << "Memory allocating error!" << endl;
exit(1);
}
int n = last + 1;//改
T* srcptr = data;
T* destptr = newarray;
while (n--)
*destptr++ = *srcptr++;
delete[]data;
data = newarray;
maxSize = newSize;
}
}
template<typename T>int SeLa<T>::Search(T& x)const {
for (int i = 0; i <= last; i++) {
if (data[i] == x) return i + 1;
}
return 0;
}
template<typename T>int SeLa<T>::Locate(int i)const {
if (i >= 1 && i <= last + 1) return i;
else return 0;
}
template<typename T>bool SeLa<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<typename T>bool SeLa<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;
}
template<typename T>void SeLa<T>::Sort() {
for (int i = 1; i <= last; i++) {
for (int j = last; j >= i; j--) {
if (data[j - 1] > data[j]) {
T tmp = data[j - 1];
data[j - 1] = data[j];
data[j] = tmp;
}
}
}
}
template<typename T>void SeLa<T>::input() {
cout << "Input the size of the list which will be created:";
while (1) {
assert(cin >> last);
last--;
if (last < 0) {
cout << "Input error, the size must be positive!\n";
cout << "Input the size again:";
}
else if (last > maxSize - 1) {//改一改可以扩大
cout << "Input error, the size must be less than maxSize!\n";
cout << "Input the size again:";
}
else break;
}
cout << "\nInput the data for each element to create the list:" << endl;
for (int i = 0; i <= last; i++) {
cout << "#" << i + 1 << ":";
assert(cin >> data[i]);
}
}
template<typename T>void SeLa<T>::output() {
cout << "The size of the list is:" << last + 1 << endl;
for (int i = 0; i <= last; i++) cout << "#" << i + 1 << ":\t" << data[i] << endl;
}
template<typename T>SeLa<T> SeLa<T>::operator = (SeLa<T>& L) {//改
maxSize = L.Size();
last = L.Length() - 1;
delete[]data;//先清空
data = new T[maxSize];
if (data == NULL) {
cerr << "Memory allocating error!" << endl;
exit(1);
}
for (int i = 1; i <= last + 1; i++) data[i - 1] = L.getData(i);
}
int main() {
SeLa<int>La;
//(1) 建立一个有20个数据的顺序表La，各节点值依次为：2,4,6,8,10,12，….,38,40
int value;
for (int i = 1; i <= 20; i++) {
value = 2 * i;
La.Insert(i - 1, value);
}
//(2) 输出顺序表La
cout << "La:" << endl; La.output();
//(3) 删除第8个结点；删除第30个结点；
cout << "删除第8个结点" << (La.Remove(8 - 1, value) ? "true" : "false") << endl;
cout << "删除第30个结点" << (La.Remove(30 - 1, value) ? "true" : "false") << endl;
// (4) 输出表长；
cout << "La Length:\t" << La.Length() << endl;
//(5) 在第五个结点后插入一个结点11；
value = 11;
cout << (La.Insert(5, value) ? "true" : "false") << endl;
// (6) 分别查找值为28,45的元素；
value = 28;
cout << "查找值为28的元素 " << (La.Search(value) ? "true" : "false") << endl;
value = 45;
cout << "查找值为45的元素 " << (La.Search(value) ? "true" : "false") << endl;
//(7) 建立线性表Lb，各结点值依次为：3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78
int values[] = { 3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78 };
SeLa<int>Lb;
for (int i = 0; i < sizeof(values) / sizeof(int); i++) {
Lb.Insert(i, values[i]);
}
//cout << "Lb:" << endl; Lb.output();
//(8) 将La和Lb合并为线性表Lc；
SeLa<int>Lc(La);
int LaLength = La.Length(), LbLength = Lb.Length();
bool isBoolean;
Lc.reSize(LaLength + LbLength);
for (int i = 0; i < LbLength; i++) {
isBoolean = Lb.getData(i + 1, value);
if (isBoolean)
Lc.Insert(LaLength + i, value);
}
//(9) 输出La，Lb，Lc的以及各表的表长；
cout << "La:" << endl; La.output(); cout << "La Length:"; cout << La.Length() << endl;
cout << "Lb:" << endl; Lb.output(); cout << "Lb Length:"; cout << Lb.Length() << endl;
cout << "Lc:" << endl; Lc.output(); cout << "Lc Length:"; cout << Lc.Length() << endl;
//(10) 清空线性表La，Lb；
while (!La.IsEmpty()) {
La.Remove(1, value);
}
while (!Lb.IsEmpty()) {
Lb.Remove(1, value);
}
//(11) 输出La，Lb的表长；
cout << "La Length:"; cout << La.Length() << endl;
cout << "Lb Length:"; cout << Lb.Length() << endl;
}