線性表類模闆:
template < class T >
class List
{y
void clear(); //線性表置空
bool isEmpty(); //線性表為空時,傳回true
bool append(const T value); //在表尾添加一個元素value,表的長度增1
bool insert(const int p, const T value);
//在位置p上插入一個元素value,表的長度增1
bool delete(const int p); //删除位置p上的元素value,表的長度減1
bool getPos(int & p, const T value);
//查找值為value的元素并傳回其位置
bool getValue(const int p, T& value);
//把位置p上的元素值傳回到變量value中
bool setValue(const int p, const T value);
//用value修改位置p的元素值
};
順序表類定義
class arrList :public List <T>
{
private:
T *aList;
int maxSize;
int curLen;
int postion;
public:
arrList(const int size)
{
maxSize = size;
aList = new T[maxSize];
curLen = postion = 0;
}
~arrList()
{
delete[] aList;
}
void clear()
{
delete[] aList;
curLen = postion = 0;
aList = new T[maxSize];
}
int length();
bool append(const T value); //在表尾添加一個元素value,表的長度增1
bool insert(const int p, const T value);
//在位置p上插入一個元素value,表的長度增1
bool delete(const int p); //删除位置p上的元素value,表的長度減1
bool getPos(int & p, const T value);
//查找值為value的元素并傳回其位置
bool getValue(const int p, T& value);
//把位置p上的元素值傳回到變量value中
bool setValue(const int p, const T value);
//用value修改位置p的元素值
};
順序表的插入算法
//設元素的類型為T,aList是存儲順序表的數組,maxSize是其最大長度
//p是新元素value的插入位置,插入成功則傳回true,否則傳回false
template <class T> bool arrList<T>::insert(const int p, const T value)
{
int i;
if (curLen >= maxSize)
{
cout << "The List is overflow" << endl;
return false;
}
if (p < 0 || p > curLen)
{
cout << "Insertion point is illegal" << endl;
return false;
}
for (i = curLen; i > p; i--)
aList[i] = aList[i - 1];
aList[p] = value;
curLen++;
return true;
}
順序表的删除算法
template <class T>
bool arrList<T>::delete(const int p)
{
int i;
if (curLen <= 0)
{
cout << "No element to delete \n" << endl;
return false;
}
if (p < 0 || p > curLen - 1)
{
cout << "deletion is illegal \n" << endl;
return false;
}
for (i = p; i < curLen - 1; i++)
arrList[i] = arrList[i + 1];
curLen--;
return true;
}
單連結清單的節點定義
template<class T>
class Link
{
public:
T data; //用于儲存節點元素的内容
Link<T> *next; //指向後繼節點的指針
Link(const T info, const Link<T>* nextValue = NULL)
{
data = info;
next = nextValue;
}
Link(const Link<T>* nextValue)
{
next = nextValue;
}
};
單連結清單定義
template<class T>
class lnkList : public List<T>
{
private:
Link<T> *head, *tail;
Link<T> *setPos(const int p);
public:
lnkList(int s);
~lnkList();
void clear(); //線性表置空
bool isEmpty(); //線性表為空時,傳回true
bool append(const T value); //在表尾添加一個元素value,表的長度增1
bool insert(const int p, const T value);
//在位置p上插入一個元素value,表的長度增1
bool delete(const int p); //删除位置p上的元素value,表的長度減1
bool getPos(int & p, const T value);
//查找值為value的元素并傳回其位置
bool getValue(const int p, T& value);
//把位置p上的元素值傳回到變量value中
bool setValue(const int p, const T value);
//用value修改位置p的元素值
};
查找單連結清單中的第i個節點
//函數傳回值是找到的節點指針
template<class T>
Link<T> *lnkList<T>::setPos(int i)
{
int count = 0;
if (i == -1)
return head;
Link<T> *p = new Link<T>(head->next);
while (p != NULL && count < i)
{
p = p->next;
count++;
}
return p;
}
單連結清單删除算法
template<class T>
bool lnkList::delete(const int i)
{
Link<T> *p, *q;
if ((p = setPos(i - 1)) == NULL || p == tail)
{
cout << "非法删除點" << endl;
return false;
}
q = p->next;
if (q == tail)
{
tail = p;
p->next = NULL;
delete q;
}
else if (q != NULL)
{
p->next = q->next;
delete q;
}
return true;
}