#pragma once

#include <iostream>

using namespace std;

template <typename T>

class MyList {

public :

MyList(int _size = 32); // 構造一個線性表，默認32位 ? ?數組底層，有序

~MyList();// 銷毀線性表

void clearList(); // 清空線性表

bool listEmpty(); // 判空

int listLength(); // 線性表實際大小

int locateElem(T &elem); // 返回第一個滿足elem的數組的元素位置

void travelList(); // 遍歷數組

bool isIndexArr(int index); //判斷index是否越界

void expend(); // 擴容

bool getElemPrior(T &current, int index ,T &proir); // 獲取指定下標的前驅（上一個位置的值）

bool getElem(T &elem,int index); // 獲取指定下標的值，返回獲取的值

bool getElemNext(T &current, int index, T &next); // 獲取指定下標的后繼（下一個位置的值）

bool insertElem(T &elem, int index); // 向指定位置插入元素，如果線性表滿，則擴從 N*2+1

bool deleteElem(T &elem, int index); // 刪除指定位置元素，并返回一個被刪除的值

private :

T *myList; // 線性表

int size; //線性表容量

int length; //線性表實際大小

};

template <typename T>

MyList<T>::MyList(int _size) {

size = _size;

myList = new T[_size];

clearList();

} // 構造一個線性表，默認32位 ? ?數組底層，有序

template <typename T>

MyList<T>::~MyList(){ ?

delete []myList;

myList = NULL;

}// 銷毀線性表

template <typename T>

void MyList<T>::clearList(){ ??

length = 0;

} // 清空線性表

template <typename T>

bool MyList<T>::listEmpty(){ ?

return 0 == length ? true : false;

} // 判空

template <typename T>

int MyList<T>::listLength(){ ?

return length;

} // 線性表實際大小

template <typename T>

int MyList<T>::locateElem(T &elem){ ?

for (int i = 0; i < length; i++) {

if (myList[i] == elem)

return i;

}

return -1;

} // 返回第一個滿足elem的數組的元素位置?

template <typename T>

void MyList<T>::travelList() {

if (listEmpty())

return;

for (int i = 0; i < length; i++)

cout << myList[i];

} // 遍歷數組

template <typename T>

bool MyList<T>::isIndexArr(int index) {

return index >= length||index <0 ? true : false;

} //判斷index是否越界

template <typename T>

void MyList<T>::expend() {

if (length < size)

return;

T *cacheList = myList;

myList = new T[size << 1 + 1];

for (int i = 0; i < length; i++)

myList[i] = cacheList[i];

delete[]cacheList;

cacheList = NULL;

} // 擴容

template <typename T>

bool MyList<T>::getElemPrior(T &current, int index, T &proir){ ??

if (isIndexArr(index))

return false;

current = myList[index];

0 == index ? proir = NULL : proir = myList[index - 1];

return true;

} // 獲取指定下標的前驅（上一個位置的值）

template <typename T>

bool MyList<T>::getElem(T &elem, int index){

if (isIndexArr(index))

return false;

elem = myList[index];

return true;

} // 獲取指定下標的值，返回獲取的值

template <typename T>

bool MyList<T>::getElemNext(T &current, int index, T &next){

if (isIndexArr(index))

return false;

current = myList[index];

index == length - 1 ? next = NULL : next = myList[index + 1];

return true;

} // 獲取指定下標的后繼（下一個位置的值）

template <typename T>

bool MyList<T>::insertElem(T &elem, int index){

if (index > length)

return false;

expend();

for (int i = size - 1; i > index; i--)

myList[i] = myList[i - 1];

myList[index] = elem;

length++;

return true;

} // 向指定位置插入元素， - 如果線性表滿，則擴從 N*2+1

template <typename T>

bool MyList<T>::deleteElem(T &elem, int index){

if (isIndexArr(index))

return false;

elem = myList[index];

for (int i = index; i < length - 1; i++)?

myList[i] = myList[i+1];

length--;

return true;

} // 刪除指定位置元素，并返回一個被刪除的值