溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
單鏈表只能從頭結點開始訪問鏈表中的數據元素，如果需要逆序訪問單鏈表中的數據元素將極其低效。
雙鏈表是鏈表的一種，由節點組成，每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。
template <typename T>
class DualLinkedList:public List<T>
{
protected:
struct Node:public Object
{
T value;//數據域
Node* next;//后繼指針域
Node* pre;//前驅
};
mutable struct:public Object
{
char reserved[sizeof(T)];//占位空間
Node* next;
Node* pre;
}m_header;
int m_length;
int m_step;
Node* m_current;
}
bool insert(int index, const T& value)
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index <= m_length);
if(ret)
{
//創建新的結點
Node* node = createNode();
if(node != NULL)
{
//當前結點定位到目標位置
Node* current = position(index);
//當前結點的下一個結點
Node* next = current->next;
//修改插入結點的值
node->value = value;
//將當前位置的下一個結點作為插入結點的下一個結點
node->next = next;
//將要插入結點作為當前結點的下一個結點
current->next = node;
if(current != reinterpret_cast<Node*>(&m_header))
{
node->pre = current;
}
else
{
node->pre = NULL;
}
if(next != NULL)
{
next->pre = node;
}
m_length++;//鏈表結點長度加1
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
}
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
}
return ret;
}
bool insert(const T& value)
{
return insert(m_length, value);
}
bool remove(int index)
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//當前結點指向頭結點
Node* current = position(index);
//使用toDel指向要刪除的結點
Node* toDel = current->next;
Node* next = toDel->next;
if(m_current == toDel)
{
m_current = next;
}
//將當前結點的下一個結點指向要刪除結點的下一個結點
current->next = next;
if(next != NULL)
next->pre = current;
m_length--;//鏈表結點長度減1
destroy(toDel);//釋放要刪除的結點的堆空間
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}template <typename T>
class DualLinkedList:public List<T>
{
protected:
struct Node:public Object
{
T value;//數據域
Node* next;//后繼指針域
Node* pre;//前驅
};
mutable struct:public Object
{
char reserved[sizeof(T)];//占位空間
Node* next;
Node* pre;
}m_header;
int m_length;
int m_step;
Node* m_current;
protected:
Node* position(int index)const
{
//指針指向頭結點
Node* ret = reinterpret_cast<Node*>(&m_header);
//遍歷到目標位置
for(int i = 0; i < index; i++)
{
ret = ret->next;
}
return ret;
}
public:
DualLinkedList()
{
m_header.next = NULL;
m_header.pre = NULL;
m_length = 0;
m_step = 1;
m_current = NULL;
}
virtual ~DualLinkedList()
{
clear();
}
bool insert(int index, const T& value)
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index <= m_length);
if(ret)
{
//創建新的結點
Node* node = createNode();
if(node != NULL)
{
//當前結點定位到目標位置
Node* current = position(index);
//當前結點的下一個結點
Node* next = current->next;
//修改插入結點的值
node->value = value;
//將當前位置的下一個結點作為插入結點的下一個結點
node->next = next;
//將要插入結點作為當前結點的下一個結點
current->next = node;
if(current != reinterpret_cast<Node*>(&m_header))
{
node->pre = current;
}
else
{
node->pre = NULL;
}
if(next != NULL)
{
next->pre = node;
}
m_length++;//鏈表結點長度加1
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
}
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
}
return ret;
}
bool insert(const T& value)
{
return insert(m_length, value);
}
bool remove(int index)
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//當前結點指向頭結點
Node* current = position(index);
//使用toDel指向要刪除的結點
Node* toDel = current->next;
Node* next = toDel->next;
if(m_current == toDel)
{
m_current = next;
}
//將當前結點的下一個結點指向要刪除結點的下一個結點
current->next = next;
if(next != NULL)
next->pre = current;
m_length--;//鏈表結點長度減1
destroy(toDel);//釋放要刪除的結點的堆空間
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
bool set(int index, const T& value)
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//將當前結點指向頭結點
Node* current = position(index);
//修改目標結點的數據域的值
current->next->value = value;
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
bool get(int index, T& value)const
{
//判斷目標位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//當前結點指向頭結點
Node* current = position(index);
//遍歷到目標位置
//獲取目標結點的數據域的值
value = current->next->value;
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
//重載版本
T get(int index)const
{
T ret;
if(get(index, ret))
return ret;
}
int length()const
{
return m_length;
}
int find(const T& value)const
{
int ret = -1;
//指向頭結點
Node* node = m_header.next;
int i = 0;
while(node)
{
//找到元素，退出循環
if(node->value == value)
{
ret = i;
break;
}
else
{
node = node->next;
i++;
}
}
return ret;
}
void clear()
{
//遍歷刪除結點
while(m_header.next)
{
//要刪除的結點為頭結點的下一個結點
Node* toDel = m_header.next;
//將頭結點的下一個結點指向刪除結點的下一個結點
m_header.next = toDel->next;
m_length--;
destroy(toDel);//釋放要刪除結點
}
}
virtual bool move(int pos, int step = 1)
{
bool ret = (0 <= pos) && (pos < m_length) && (0 < step);
if(ret)
{
m_current = position(pos)->next;
m_step = step;
}
return ret;
}
virtual bool end()
{
return m_current == NULL;
}
virtual T current()
{
if(!end())
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "Invalid Operation...");
}
}
virtual bool next()
{
int i = 0;
while((i < m_step) && (!end()))
{
m_current = m_current->next;
i++;
}
return (i == m_step);
}
virtual bool pre()
{
int i = 0;
while((i < m_step) && (!end()))
{
m_current = m_current->pre;
i++;
}
return (i == m_step);
}
virtual Node* createNode()
{
return new Node();
}
virtual void destroy(Node* node)
{
delete node;
}
};免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
