/*
@content 线性链表之顺序表
@date 2017-3-21 1:06
@author Johnny Zen
*/
/*
线性表
顺序表
链式表[带头指针/不带头指针]
单链表
循环单链表
双向链表
循环双链表
ADT
List{
属性：
length 长度
DataList; 数据
操作：
init(array[]) 表初始化
Destory() 表销毁
int getLength() 返回表的长度
void InsertNode(int i,node) 按照位置i，插入表的结点
void DeleteNode(int i,node) 按照位置i,删除表的结点
void Delete(data) 按值删除表的结点
int Location(data) 按值查找,返回位置i[实际位置]
Data Get(i) 按位置查找，返回结点数据
void sort() 结点排序
bool Empty() 判空
void print() 遍历表
}
*/
//=================================
//顺序表
#include<iostream>
using namespace std;
const int MaxSize = 100;
template<class T>
class SeqList{
public:
SeqList();
SeqList(T a[],int n);
~SeqList();
int Length(){ return length; }
void Insert(int x,T data);
void Delete(int x);
int Location(T data);
T Get(int i);
void print();
bool Empty();
private:
int length;
T datas[MaxSize];
};
/***************方法实现区*******************/
template<class T>
SeqList<T>::SeqList(){
length = 0;
}
template<class T>
SeqList<T>::SeqList(T a[],int n){
if(n>MaxSize){
throw "数组长度超出!!";
}
for(int i = 0;i<n;i++){
datas[i] = a[i];
}
length = n;
}
template<class T>
SeqList<T>::~SeqList(){ }
//插入到第i个位置上（实际位置）
// 1 2 45 75 | 75 45 45 1 2
// 0 1 2 3 | 4 5 6 7 8
// 12 12 56 | 78 11
// i = 5
// [5] = [4]
// [4] = [3]
// [3] = [2]
// [2] = [1]
// [1] = [0]
template<class T>
void SeqList<T>::Insert(int x,T data){
if(x>length+1||x<1)
throw "位置超界！！！";
if(length>=MaxSize)
throw "位置溢出!!!";
for(int i=length;i>=x;i--){
this->datas[i] = this->datas[i-1]; //最关键代码：从后面[length]开始往前走，元素向后挪
}
this->datas[x-1] = data;
length++;
}
//按位置i(实际位置)删除结点
// 1 2 45 75 | 75 45 45 1 2
// 0 1 2 3 | 4 5 6 7 8
// 12 12 56 | 78 11
template<class T>
void SeqList<T>::Delete(int x){
if(x<1||x>length)
throw "位置异常";
for(int i=x-1;i<length-1;i++)
this->datas[i] = this->datas[i+1];
length--;
}
//按值查找，返回位置(实际位置)
template<class T>
int SeqList<T>::Location(T data){
datas[length] = data; //在最后一个结点的后面设置哨兵
int i = 0;
while(datas[i]!=data)
i++;
if(i==length) return -1;
return ++i;
}
//按位置(实际位置)查找，返回结点值
template<class T>
T SeqList<T>::Get(int i){
if(i<1||i>length)
throw "位置超界！！！";
return datas[i-1];
}
//遍历顺序表
template<class T>
void SeqList<T>::print(){
for(int i = 0;i<this->Length();i++)
cout<<datas[i]<<"\t";
}
template<class T>
bool SeqList<T>::Empty(){
if(length>0)
return false; //0
return true; //1
}
//=================================
int main(){
int arr[]= {12,23,45,56,78};
SeqList<int> test(arr,5);
cout<<test.Get(5)<<endl;
cout<<test.Empty()<<endl;
test.print();
return 0;
}