#ifndef SeqList_h
#define SeqList_h
#include <iostream>
using namespace std;
 
const int defaultSize = 100;
 
template<class T>
class SeqList{
public:
 SeqList(int sz = defaultSize); // 構(gòu)造函數(shù)
 SeqList(SeqList<T>& L); // 復(fù)制構(gòu)造函數(shù)
 ~SeqList(); // 析構(gòu)函數(shù)
 int Size(); // 重載虛函數(shù)：計算表最大可容納表項個數(shù)，限制權(quán)限，類外無法直接獲取maxSize
 int Length(); // 計算表長度
 int Search(T x); // 搜索x在表中位置，函數(shù)返回表項序號
 int Locate(int i); // 定位第i個表項，函數(shù)返回表項序號
 bool getData(int i, T& x); // 取第i個表項的值
 void setData(int i, T x); // 用x修改第i個表項的值
 bool Insert(int i, T x); // 在第i個表項后插入元素x
 bool Remove(int i, T& x); // 刪除第i個表項，通過x返回
 bool isEmpty(); // 判斷表是否為空，空則返回true;否則，返回false
 bool isFull(); // 判斷表滿否，滿則返回true;否則，返回false
 void Input(); // 輸入數(shù)據(jù)建立表
 void Output(); // 打印表
 void Sort(); // 排序
 SeqList<T> operator=(SeqList<T>& L); // 表整體賦值
private:
 T *data; // 存放數(shù)組
 int maxSize; // 最大可容納表項的項數(shù)
 int last; // 當(dāng)前已存表項的最后位置（從0開始）
 void reSize(int newSize); // 改變數(shù)組空間大小
};
 
template <class T>
SeqList<T>::SeqList(int sz) {
 // 構(gòu)造函數(shù),通過指定參數(shù)sz定義數(shù)組的長度
 if(sz > 0) {
 maxSize = sz;
 last = -1; // 置表的實際長度為空
 data = new T[maxSize]; // 創(chuàng)建順序表存儲數(shù)組
 if(data == NULL) {
 cerr << "動態(tài)內(nèi)存分配失敗!" << endl;
 exit(1);
 }
 }
}
 
template <class T>
SeqList<T>::SeqList(SeqList<T>& L) {
 // 復(fù)制構(gòu)造函數(shù)，用參數(shù)表中給出的已有順序表初始化新建的順序表
 // 如果沒有定義復(fù)制構(gòu)造函數(shù)，系統(tǒng)會自動建立一個復(fù)制構(gòu)造函數(shù)
 maxSize = L.Size(); // 最大可容納的個數(shù)
 last = L.Length() - 1; // 數(shù)組最后的位置
 T value;
 data = new T[maxSize]; // 創(chuàng)建順序表存儲數(shù)組
 if(data == NULL) {
 cerr << "動態(tài)內(nèi)存分配失敗!" << endl;
 exit(1);
 }
 for(int i = 1; i <= last+1; i++) {
 L.getData(i, value); // 取第i個位置的值
 data[i-1] = value;
 }
}
 
template <class T>
SeqList<T>::~SeqList() {
 // 析構(gòu)函數(shù)
 delete []data;
}
 
template <class T>
void SeqList<T>::reSize(int newSize) {
 // 私有函數(shù)：擴充順序表的存儲數(shù)組空間大小，新數(shù)組的元素個數(shù)為newSize
 if(newSize <= 0) { // 檢查參數(shù)的合理性
 cerr << "無效的數(shù)組大小" << endl;
 return;
 }
 if(newSize != maxSize) { // 修改
 T *newArray = new T[newSize]; // 建立新數(shù)組
 if(newArray == NULL) {
 cerr << "動態(tài)內(nèi)存分配失敗!" << endl;
 exit(1);
 }
 int n = last + 1;
 T *srcPtr = data; // 源數(shù)組首地址
 T *destPtr = newArray; // 目的數(shù)組首地址
 while(n--)
 *destPtr++ = *srcPtr++; // 復(fù)制：只是數(shù)據(jù)
 delete []data; // 刪除舊數(shù)組
 data = newArray; // 復(fù)制新數(shù)組
 maxSize = newSize; // 復(fù)制新數(shù)組：數(shù)據(jù)和內(nèi)存空間
 }
}
 
template <class T>
int SeqList<T>::Size(){
 // 計算表最大可容納表項個數(shù)
 return maxSize;
}
 
template <class T>
int SeqList<T>::Length(){
 // 計算表長度
 return last+1;
}
 
template <class T>
int SeqList<T>::Search(T x){
 // 搜索x在表中位置，函數(shù)返回表項序號:在表中的第幾個位置；搜索失?。悍祷?
 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){
 // 定位第i個表項，函數(shù)返回第i（1<= i <= last+1）個表項的位置，否則函數(shù)返回-1，表示定位失敗
 if(i >= 1 && i <= last+1)
 return i-1; // 數(shù)組下標(biāo)從0開始
 return -1;
}
 
template <class T>
bool SeqList<T>::getData(int i, T& x){
 // 取第i個表項的值
 if(i > 0 && i <= last+1) {
 x = data[i-1];
 return true;
 }
 return false;
}
 
template <class T>
void SeqList<T>::setData(int i, T x){
 // 用x修改第i個表項的值
 if(i > 0 && i <= last+1)
 data[i-1] = x;
}
 
template <class T>
bool SeqList<T>::Insert(int i, T x) {
 // 在第i個表項后插入元素x
 if(last == maxSize-1) // 表滿，不能插入
 return false;
 if(i < 0 || i > last+2) // 參數(shù)i不合理，不能插入, last+2表示數(shù)組的最后面插入
 return false;
 for(int j = last; j >= i; j--)
 data[j+1] = data[j]; // 依次后移，空出第i號位置
 data[i] = x; // 插入
 last++; // 最后位置加1
 return true; // 插入成功
}
 
template <class T>
bool SeqList<T>::Remove(int i, T& x) {
 // 刪除第i個表項，通過x返回
 if(last == -1) // 表空，不能刪除
 return false;
 if(i < 0 || i > last+1) // 參數(shù)i不合理，不能插入
 return false;
 x = data[i-1];
 for(int j = i-1; j < last; j++)
 data[j] = data[j+1];
 last--; // 最后位置減1
 return true; // 刪除成功
}
 
template <class T>
bool SeqList<T>::isEmpty(){
 // 判斷表是否為空，空則返回true;否則，返回false
 return (last == -1 ? true : false);
}
 
template <class T>
bool SeqList<T>::isFull(){
 // 判斷表滿否，滿則返回true;否則，返回false
 return (last == maxSize-1 ? true : false);
}
 
template <class T>
void SeqList<T>::Input() {
 // 從標(biāo)準(zhǔn)輸入（鍵盤）逐個數(shù)據(jù)輸入，建立順序表
 int len;
 cout << "開始建立順序表，請輸入表中元素個數(shù):";
 cin >> len;
 if(len > maxSize) {
 cout << "表元素個數(shù)輸入有誤,范圍不超過：" << maxSize << endl;
 return;
 }
 last = len - 1; // 數(shù)組最后位置
 cout << "請輸入建表的數(shù)據(jù):" << endl;
 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>
void SeqList<T>::Sort() {
 int flag;
 T temp;
 
 // 排序:從小到大
 for(int i = 0; i < last; i++) { // 最后一個不用排了
 flag = 0; // 標(biāo)志該輪是否有交換, 0表示沒有交換，1表示有交換
 // 沒有交換，說明已排好序，提前結(jié)束
 for(int j = 0; j < (last - i); j++) { // 向后冒泡
 if(data[j] > data[j + 1]) {
 flag = 1;
 temp = data[j+1];
 data[j+1] = data[j];
 data[j] = temp;
 }
 }
 if(flag == 0) // 沒有交換，提前結(jié)束程序
 break;
 }
 
}
 
template <class T>
SeqList<T> SeqList<T>::operator=(SeqList<T>& L) {
 int size, value;
 
 // 表整體賦值：順序表整體賦值
 size = L.Size();
 if(maxSize != size) { // 表最大可容納數(shù)小于L的
 reSize(size); // 該變數(shù)組大小
 }
 last = L.Length() - 1; // 數(shù)組的最后位置
 for(int i = 1; i <= last+1; i++) {
 L.getData(i, value); // 取第i個位置的值
 data[i-1] = value;
 }
}
 
#endif /* SeqList_h */

#include "SeqList.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
 int choose, len, i, x, maxSize, loc; // val存儲值，choose存儲用戶的選擇
 bool finished = false;
 
 SeqList<int> L; // 聲明SeqList對象
 while(!finished) {
 cout << "1:輸入數(shù)據(jù)建立順序表：" << endl;
 cout << "2:順序表的最大可容納表項個數(shù)：" << endl;
 cout << "3:順序表的長度：" << endl;
 cout << "4:搜索x在表中的位置：" << endl;
 cout << "5:定位第i個表項：" << endl;
 cout << "6:取第i個表項的值：" << endl;
 cout << "7:用x修改第i個表項的值：" << endl;
 cout << "8:在第i個表項后插入元素x：" << endl;
 cout << "9:刪除第i個表項：" << endl;
 cout << "10:判斷表是否為空：" << endl;
 cout << "11:判斷表滿否：" << endl;
 cout << "12:打印順序表中的數(shù)據(jù)：" << endl;
 cout << "13:將順序表排序：" << endl;
 cout << "14:退出：" << endl;
 cout << "請輸入你的選擇[1-14]：" << endl;
 cin >> choose;
 switch(choose) {
 case 1:
 L.Input(); // 建立順序表
 break;
 case 2:
 maxSize = L.Size();
 cout << "順序表的最大可容納表項個數(shù)為：" << maxSize << endl;
 break;
 case 3:
 len = L.Length();
 cout << "順序表的長度為：" << len << endl;
 break;
 case 4:
 cout << "請輸入要搜索的值x:";
 cin >> x;
 i = L.Search(x);
 if(i == 0)
  cout << "沒找到" << x << endl;
 else
  cout << x << "在表中的第" << i << "個位置" << endl;
 break;
 case 5:
 cout << "請輸入要定位的位置i：";
 cin >> i;
 loc = L.Locate(i);
 if(loc != -1)
  cout << "定位成功！在順序表中下標(biāo)為：" << loc << endl;
 else
  cout << "定位失敗!" << endl;
 break;
 case 6:
 cout << "請輸入要取表中元素的位置i:";
 cin >> i;
 if(L.getData(i, x))
  cout << "表中第" << i << "個表項的值為:" << x << endl;
 else
  cout << "取值失敗！檢查是否超范圍取值" << endl;
 break;
 case 7:
 cout << "請輸入要修改的位置i和值x:";
 cin >> i >> x;
 L.setData(i, x);
 break;
 case 8:
 cout << "請輸入要插入的位置i和值x:";
 cin >> i >> x;
 if(L.Insert(i, x))
  cout << "插入成功！" << endl;
 else
  cout << "插入失?。? << endl;
 break;
 case 9:
 cout << "請輸入要刪除的表項的位置i:";
 cin >> i;
 if(L.Remove(i, x))
  cout << "刪除成功！刪除的值為:" << x << endl;
 else
  cout << "刪除失敗!" << endl;
 break;
 case 10:
 if(L.isEmpty())
  cout << "表為空！" << endl;
 else
  cout << "表不為空！" << endl;
 break;
 case 11:
 if(L.isFull())
  cout << "表滿！" << endl;
 else
  cout << "表未滿！" << endl;
 break;
 case 12:
 cout << "表中的數(shù)據(jù)為：" << endl;
 L.Output();
 break;
 case 13:
 cout << "表中的數(shù)據(jù)排序前：" << endl;
 L.Output();
 L.Sort();
 cout << "表中的數(shù)據(jù)排序后：" << endl;
 L.Output();
 break;
 case 14:
 finished = true;
 break;
 default:
 cout << "輸入選擇錯誤，請重新輸入!" << endl;
 }
 }
 return 0;
}