1. 線性表抽象類
#pragma once template <class T> class LinearList { public: // 線性表是否為空 virtual bool empty() const = 0; // 線性表大小 virtual int size() const = 0; // 根據(jù)ID獲取線性表元素 virtual T& get(int theIndex) const = 0; // 根據(jù)元素獲取元素對(duì)應(yīng)ID virtual int indexOf(const T& theElement) const = 0; // 刪除ID處的元素 virtual void erase(int theIndex) = 0; // 在ID處插入元素 virtual void insert(int theIndex, const T& theElement) = 0; // 輸出線性表 virtual void output() = 0; };
2. 線性表的數(shù)組描述
#include"linearList.h" #include<iostream> using namespace std; template<class T> class ArrayList :public LinearList<T> { protected: T* element; // 線性表元素指針 int arrayLength; // 容量 int listSize; // 元素個(gè)數(shù) bool checkIndex(int theIndex) const; // 檢查索引是否有效 void changeLength(); // 擴(kuò)充數(shù)組長(zhǎng)度 public: // 構(gòu)造函數(shù) ArrayList(int initialCapacity = 10); // 拷貝構(gòu)造函數(shù) ArrayList(const ArrayList<T>& theList); // 析構(gòu)函數(shù) ~ArrayList() { delete[] element; } // 線性表是否為空 bool empty() const { return listSize == 0; } // 線性表大小 int size() const { return listSize; } // 線性表容量 int capacity() const { return arrayLength; } // 根據(jù)ID獲取線性表元素 T& get(int theIndex) const; // 根據(jù)元素獲取元素對(duì)應(yīng)ID int indexOf(const T& theElement) const; // 刪除ID處的元素 void erase(int theIndex); // 在ID處插入元素 void insert(int theIndex, const T& theElement); // 輸出線性表 void output(); }; // 構(gòu)造函數(shù) template<class T> ArrayList<T>::ArrayList(int initialCapacity) { if (initialCapacity < 1) { cout << "初始化容量必須大于0" << endl; return; } this->arrayLength = initialCapacity; this->element = new T[arrayLength]; listSize = 0; } // 復(fù)制構(gòu)造函數(shù) template<class T> ArrayList<T>::ArrayList(const ArrayList<T>& theList) { this->arrayLength = theList.arrayLength; this->listSize = theList.listSize; this->element = new T[arrayLength]; copy(theList.element, theList.element + listSize, element); } // 越界, false 表示越界, true 表示沒(méi)有越界 template<class T> bool ArrayList<T>::checkIndex(int theIndex) const { bool ret = !(theIndex < 0 || theIndex > listSize); return ret; } // 獲取元素 template<class T> T& ArrayList<T>::get(int theIndex) const { if (checkIndex(theIndex)) { return element[theIndex]; } } // 根據(jù)元素獲取ID template<class T> int ArrayList<T>::indexOf(const T& theElement) const { int theIndex = (int)find(element, element + listSize, theElement); return theIndex == listSize ? -1 : (theIndex-(int)element)/sizeof(T); } // 刪除ID處元素 template<class T> void ArrayList<T>::erase(int theIndex) { if (checkIndex(theIndex)) { copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T(); } } // 擴(kuò)充數(shù)組長(zhǎng)度 template<class T> void ArrayList<T>::changeLength() { T* temp = new T[arrayLength * 2]; copy(element, element + arrayLength, temp); delete[] element; element = temp; arrayLength = 2 * arrayLength; } // 在ID處插入元素 template<class T> void ArrayList<T>::insert(int theIndex, const T& theElement) { if (!checkIndex(theIndex)) { cout << "無(wú)效索引" << endl; return; } if (listSize == arrayLength) { changeLength(); } copy_backward(element + theIndex, element + listSize, element + listSize + 1); element[theIndex] = theElement; listSize++; } // 輸出線性表 template<class T> void ArrayList<T>::output() { for (int i = 0; i < listSize; i++) { cout << element[i] << " "; } cout << endl; }
3. 線性表的鏈?zhǔn)矫枋?/h2>
3.1 結(jié)點(diǎn)結(jié)構(gòu)體
#pragma once
#include<iostream>
using namespace std;
template <class T>
struct ChainNode
{
// 數(shù)據(jù)成員
T element;
ChainNode<T>* next;
// 方法
ChainNode() {}
ChainNode(const T& element)
{
this->element = element;
}
ChainNode(const T& element, ChainNode<T>* next)
{
this->element = element;
this->next = next;
}
};
3.2 線性表實(shí)現(xiàn)
#include"linearList.h"
#include"chianNode.h"
#include<iostream>
using namespace std;
template<class T>
class Chain :public LinearList<T>
{
protected:
ChainNode<T>* firstNode;
int listSize;
bool checkIndex(int theIndex) const;
public:
Chain(int initialCapacity = 10);
Chain(const Chain<T>&);
~Chain();
bool empty() const { return listSize == 0; };
// 線性表大小
int size() const { return listSize; }
// 根據(jù)ID獲取線性表元素
T& get(int theIndex) const;
// 根據(jù)元素獲取元素對(duì)應(yīng)ID
int indexOf(const T& theElement) const;
// 刪除ID處的元素
void erase(int theIndex);
// 在ID處插入元素
void insert(int theIndex, const T& theElement);
// 輸出線性表
void output();
};
// 普通的構(gòu)造函數(shù)
template<class T>
Chain<T>::Chain(int initialCapacity)
{
if (initialCapacity < 1)
{
cout << "初始容量設(shè)置必須大于0" << endl;
}
firstNode = NULL;
listSize = 0;
}
// 拷貝構(gòu)造函數(shù)
template<class T>
Chain<T>::Chain(const Chain<T>& theList)
{
listSize = theList.listSize;
if (listSize == 0)
{
firstNode = NULL;
return;
}
ChainNode<T>* sourceNode = theList.firstNode;
firstNode = new ChainNode<T>(sourceNode->element);
sourceNode = sourceNode->next;
ChainNode<T>* targetNode = firstNode;
while (sourceNode != NULL)
{
targetNode->next = new ChainNode<T>(sourceNode->element);
targetNode = targetNode->next;
sourceNode = sourceNode->next;
}
targetNode->next = NULL;
}
// 析構(gòu)函數(shù)
template<class T>
Chain<T>::~Chain()
{
while (firstNode != NULL)
{
ChainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
template<class T>
T& Chain<T>::get(int theIndex) const
{
if (checkIndex(theIndex))
{
ChainNode<T>* currentNode = firstNode;
for (int i = 0; i < theIndex; i++)
{
currentNode = currentNode->next;
}
return currentNode->element;
}
}
template<class T>
int Chain<T>::indexOf(const T& theElement) const
{
ChainNode<T>* currentNode = firstNode;
int index = 0;
while (currentNode->element != theElement && currentNode != NULL)
{
currentNode = currentNode->next;
index++;
}
return currentNode == NULL ? -1 : index;
}
template<class T>
void Chain<T>::erase(int theIndex)
{
if (checkIndex(theIndex))
{
ChainNode<T>* deleteNode;
if (theIndex == 0)
{
deleteNode = firstNode;
firstNode = firstNode->next;
}
else if (theIndex < listSize - 1)
{
ChainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1; i++)
{
p = p->next;
}
deleteNode = p->next;
p->next = p->next->next;
}
else
{
ChainNode<T>* p = firstNode;
for (int i = 0; i < theIndex; i++)
{
p = p->next;
}
deleteNode = p;
p->next = NULL;
}
listSize--;
delete deleteNode;
}
}
template<class T>
void Chain<T>::insert(int theIndex, const T& theElement)
{
if (checkIndex(theIndex))
{
if (theIndex == 0)
{
firstNode = new ChainNode<T>(theElement, firstNode);
}
else
{
ChainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1; i++)
{
p = p->next;
}
p->next = new ChainNode<T>(theElement, p->next);
}
listSize++;
}
}
template<class T>
void Chain<T>::output()
{
ChainNode<T>* currentNode = firstNode;
while (currentNode != NULL)
{
cout << currentNode->element << " ";
currentNode = currentNode->next;
}
cout << endl;
}
template<class T>
bool Chain<T>::checkIndex(int theIndex) const
{
bool ret = !(theIndex < 0 || theIndex > listSize);
return ret;
}
#pragma once #include<iostream> using namespace std; template <class T> struct ChainNode { // 數(shù)據(jù)成員 T element; ChainNode<T>* next; // 方法 ChainNode() {} ChainNode(const T& element) { this->element = element; } ChainNode(const T& element, ChainNode<T>* next) { this->element = element; this->next = next; } };
#include"linearList.h" #include"chianNode.h" #include<iostream> using namespace std; template<class T> class Chain :public LinearList<T> { protected: ChainNode<T>* firstNode; int listSize; bool checkIndex(int theIndex) const; public: Chain(int initialCapacity = 10); Chain(const Chain<T>&); ~Chain(); bool empty() const { return listSize == 0; }; // 線性表大小 int size() const { return listSize; } // 根據(jù)ID獲取線性表元素 T& get(int theIndex) const; // 根據(jù)元素獲取元素對(duì)應(yīng)ID int indexOf(const T& theElement) const; // 刪除ID處的元素 void erase(int theIndex); // 在ID處插入元素 void insert(int theIndex, const T& theElement); // 輸出線性表 void output(); }; // 普通的構(gòu)造函數(shù) template<class T> Chain<T>::Chain(int initialCapacity) { if (initialCapacity < 1) { cout << "初始容量設(shè)置必須大于0" << endl; } firstNode = NULL; listSize = 0; } // 拷貝構(gòu)造函數(shù) template<class T> Chain<T>::Chain(const Chain<T>& theList) { listSize = theList.listSize; if (listSize == 0) { firstNode = NULL; return; } ChainNode<T>* sourceNode = theList.firstNode; firstNode = new ChainNode<T>(sourceNode->element); sourceNode = sourceNode->next; ChainNode<T>* targetNode = firstNode; while (sourceNode != NULL) { targetNode->next = new ChainNode<T>(sourceNode->element); targetNode = targetNode->next; sourceNode = sourceNode->next; } targetNode->next = NULL; } // 析構(gòu)函數(shù) template<class T> Chain<T>::~Chain() { while (firstNode != NULL) { ChainNode<T>* nextNode = firstNode->next; delete firstNode; firstNode = nextNode; } } template<class T> T& Chain<T>::get(int theIndex) const { if (checkIndex(theIndex)) { ChainNode<T>* currentNode = firstNode; for (int i = 0; i < theIndex; i++) { currentNode = currentNode->next; } return currentNode->element; } } template<class T> int Chain<T>::indexOf(const T& theElement) const { ChainNode<T>* currentNode = firstNode; int index = 0; while (currentNode->element != theElement && currentNode != NULL) { currentNode = currentNode->next; index++; } return currentNode == NULL ? -1 : index; } template<class T> void Chain<T>::erase(int theIndex) { if (checkIndex(theIndex)) { ChainNode<T>* deleteNode; if (theIndex == 0) { deleteNode = firstNode; firstNode = firstNode->next; } else if (theIndex < listSize - 1) { ChainNode<T>* p = firstNode; for (int i = 0; i < theIndex - 1; i++) { p = p->next; } deleteNode = p->next; p->next = p->next->next; } else { ChainNode<T>* p = firstNode; for (int i = 0; i < theIndex; i++) { p = p->next; } deleteNode = p; p->next = NULL; } listSize--; delete deleteNode; } } template<class T> void Chain<T>::insert(int theIndex, const T& theElement) { if (checkIndex(theIndex)) { if (theIndex == 0) { firstNode = new ChainNode<T>(theElement, firstNode); } else { ChainNode<T>* p = firstNode; for (int i = 0; i < theIndex - 1; i++) { p = p->next; } p->next = new ChainNode<T>(theElement, p->next); } listSize++; } } template<class T> void Chain<T>::output() { ChainNode<T>* currentNode = firstNode; while (currentNode != NULL) { cout << currentNode->element << " "; currentNode = currentNode->next; } cout << endl; } template<class T> bool Chain<T>::checkIndex(int theIndex) const { bool ret = !(theIndex < 0 || theIndex > listSize); return ret; }
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-711778.html
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-711778.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】1.線性表的數(shù)組描述和鏈?zhǔn)矫枋龅奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
