溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
為了表示每個(gè)數(shù)據(jù)元素與其直接后繼之間的邏輯關(guān)系，數(shù)據(jù)元素除過(guò)存儲(chǔ)本身的信息之外，還需要存儲(chǔ)其后繼元素的地址信息。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的邏輯結(jié)構(gòu)：
單鏈表中的節(jié)點(diǎn)定義：
注意：這里的struct是用來(lái)定義一個(gè)類，與class的訪問(wèn)屬性相反，默認(rèn)為public
單鏈表的內(nèi)部結(jié)構(gòu)：
頭節(jié)點(diǎn)在單鏈表中的意義是：輔助數(shù)據(jù)元素的定位，方便插入和刪除，因此，頭節(jié)點(diǎn)不存儲(chǔ)實(shí)際的數(shù)據(jù)。
插入：
node->value = e;
node->next = current->next;
Current->next = node;刪除：
執(zhí)行操作
toDel = current->next;
current->next = toDel->nex;
delete toDel;類族結(jié)構(gòu)：
— 類模板，通過(guò)頭節(jié)點(diǎn)訪問(wèn)后繼節(jié)點(diǎn)
— 定義內(nèi)部節(jié)點(diǎn)的類型Node，用于描述數(shù)據(jù)域和指針域
— 實(shí)現(xiàn)線性表的關(guān)鍵操作，增、刪、查等。
template < typename T >
class LinkList : public List<T>
{
protected:
struct Node : public Object
{
Node * next;
T value;
};
int m_length;
mutable Node m_header;
// 當(dāng)前所找到的節(jié)點(diǎn)不是要直接操作的節(jié)點(diǎn)，要操作的是該節(jié)點(diǎn)的next
Node *position(int i) const
public:
LinkList()
bool insert(const T& e)
bool insert(int index, const T& e)
bool remove(int index)
bool set(int index, const T& e)
T get(int index)
bool get(int index, T& e) const
int length() const
void clear()
~LinkList()
};優(yōu)化：
代碼中多個(gè)函數(shù)存在對(duì)操作節(jié)點(diǎn)的定位邏輯。可以將該段代碼實(shí)現(xiàn)為一個(gè)position函數(shù)。
Node *position(int i) const
{
Node *ret = reinterpret_cast<Node*>(&m_header);
for(int p=0; p<i; p++)
{
ret = ret->next;
}
return ret;
}隱患：
LinkList<Test> L; // 拋出異常，分析為什么我們沒(méi)有定義 Test 對(duì)象，但確拋出了異常
原因在于單鏈表頭節(jié)點(diǎn)構(gòu)造時(shí)會(huì)調(diào)用泛指類型的構(gòu)造函數(shù)
解決方案：
頭節(jié)點(diǎn)構(gòu)造時(shí)，避免調(diào)用泛指類型的構(gòu)造函數(shù)，也即是說(shuō)要自定義頭節(jié)點(diǎn)的類型，并且該類型是一個(gè)匿名類型
mutable struct : public Object
{
char reserved[sizeof(T)];
Node *next;
}m_header;注意：這里我們自定義都頭結(jié)點(diǎn)類型和Node的內(nèi)存結(jié)構(gòu)上要一模一樣（不要將兩個(gè)成員變量的位置交換）。
template <typename T>
class LinkList : public List<T>
{
protected:
int m_length;
int m_step;
struct Node : public Object
{
Node* next;
T value;
};
// 游標(biāo),獲取游標(biāo)指向的數(shù)據(jù)元素,遍歷開(kāi)始前將游標(biāo)指向位置為0的數(shù)據(jù)元素,通過(guò)節(jié)點(diǎn)中的next指針移動(dòng)游標(biāo)
Node* m_current;
// 構(gòu)造頭節(jié)點(diǎn)時(shí)，會(huì)調(diào)用泛指類型的構(gòu)造函數(shù)，如果泛指類型構(gòu)造函數(shù)中拋出異常，將導(dǎo)致構(gòu)造失敗
//mutable Node m_header;
// 為了避免調(diào)用泛指類型的構(gòu)造函數(shù)，自定義頭節(jié)點(diǎn)的類型(內(nèi)存結(jié)構(gòu)上要一模一樣)，并且該類型是一個(gè)匿名類型（沒(méi)有類型名）
mutable struct : public Object
{
Node *next;
char reserved[sizeof(T)];
}m_header;
Node* position(int index) const
{
Node* ret = reinterpret_cast<Node*>(&m_header);
for(int p=0; p<index; p++)
{
ret = ret->next;
}
return ret;
}
virtual Node* create()
{
return new Node();
}
virtual void destroy(Node* pNode)
{
delete pNode;
}
public:
LinkList()
{
m_header.next = NULL;
m_length = 0;
m_step = 0;
m_current = NULL;
}
int find(const T& e) const
{
int ret = -1;
Node* node = m_header.next;
for(int i=0; i<m_length; i++)
{
if(node->value == e)
{
ret = i;
break;
}
node = node->next;
}
return ret;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
bool insert(int index, const T& e)
{
bool ret = (index>=0) && (index<=m_length);
if(ret)
{
Node* node = create();
if(NULL != node)
{
Node* current = position(index);
node->next = current->next;
current->next = node;
node->value =e;
m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "no enough memory to insert node.");
}
}
return ret;
}
bool remove(int index)
{
bool ret = (index>=0) && (index<=m_length);
if(ret)
{
Node* current = position(index);
Node* toDel = current->next;
if( toDel == m_current)
{
m_current = toDel->next; // 確保當(dāng)前元素刪除后m_current指向正確的位置
}
current->next = toDel->next;
destroy(toDel);
m_length--;
}
return ret;
}
bool set(int index, const T& e)
{
bool ret = (index>=0) && (index<=m_length);
if(ret)
{
Node* current = position(index);
current->next->value = e;
}
return ret;
}
virtual T get(int index) const
{
T ret;
if(get(index, ret))
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "index out of range.");
}
}
bool get(int index, T& e) const
{
bool ret = (index>=0) && (index<=m_length);
if(ret)
{
Node* current = position(index);
e = current->next->value;
}
return ret;
}
void traverse(void) //O(n^2)
{
for(int i=0; i<length(); i++)
{
cout << (*this).get(i) << endl;
}
}
void traverse_r(int i, int step = 1) //O(n)
{
for((*this).move(i, step);!(*this).end();(*this).next()) //(*this).move(0,2)
{
cout << (*this).current() << endl;
}
}
virtual bool move(int i, int step = 1) // O(n)
{
bool ret = (0<=i)&&(i<m_length)&&(step>0);
if(ret)
{
m_current = position(i)->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,"No value at current position...");
}
}
virtual bool next()
{
int i =0;
while((i<m_step)&&!end())
{
m_current = m_current->next;
i++;
}
return(i == m_step);
}
int length() const
{
return m_length;
}
void clear()
{
while(m_header.next)
{
Node* toDel = m_header.next;
m_header.next = toDel->next;
destroy(toDel);
m_length--;
}
}
~LinkList()
{
clear();
}
};1.查找操作：
可以為線性表list增加一個(gè)查找操作， int find (const T& e) const
參數(shù)為待查找的元素，返回值為查找到的元素首次出現(xiàn)的位置，沒(méi)有找到返回 -1
2.比較操作：
當(dāng)我們定義的了上述查找函數(shù)之后，線性表中的數(shù)據(jù)為類類型時(shí)，查找函數(shù)編譯出錯(cuò)，原因在于我們沒(méi)有重載==操作符。
解決的辦法，在頂層父類Object中重載==和!=操作符，并且讓自定義的類繼承自頂層父類Object。
單鏈表和順序表的時(shí)間復(fù)雜度對(duì)比：
問(wèn)題：
順序表的整體時(shí)間復(fù)雜度比單鏈表低，那么單鏈表還有使用的價(jià)值嗎？實(shí)際工程中為什么單鏈表反而用的比較多？
——實(shí)際工程中，時(shí)間復(fù)雜度只是效率的一個(gè)參考指標(biāo)
遍歷一個(gè)單鏈表的方法：通過(guò)for循環(huán)來(lái)調(diào)用get函數(shù)即可實(shí)現(xiàn)。
for(int i=0; i<list.length(); i++)
{
cout << list.get(i) << endl;
}這段代碼的時(shí)間復(fù)雜度為O（n^2）,所以我們希望對(duì)其優(yōu)化，得到一個(gè)線性階的遍歷函數(shù)。
bool move(int i, int step = 1);
bool end();
T current();
bool next();單鏈表內(nèi)部的一次封裝：
virtual Node *create()
{
return new Node();
}
virtual void destory(Node *pn)
{
delete pn;
}進(jìn)行上述封裝得到意義：增加程序的可擴(kuò)展性
長(zhǎng)時(shí)間使用單鏈表對(duì)象頻繁的增加和刪除數(shù)據(jù)元素，會(huì)導(dǎo)致堆空間產(chǎn)生大量的內(nèi)存碎片，導(dǎo)致系統(tǒng)運(yùn)行緩慢。
新的線性表：
在單鏈表的內(nèi)部增加一片預(yù)留的空間，所有的node對(duì)象都在這篇空間中動(dòng)態(tài)創(chuàng)建和動(dòng)態(tài)銷毀。
層次結(jié)構(gòu)：
template < typename T, int N>
class StaticLinkList : public LinkList<T>
{
protected:
// (1)注意這里不能直接寫(xiě)為Node，編譯報(bào)錯(cuò)，原因是Node中涉及泛指類型T，所以要聲明 LinkList<T>::Node
// (2)上面的寫(xiě)法在某些編譯情況下依然會(huì)報(bào)錯(cuò)，原因在于，編譯器不知道這里的Node是一個(gè)類對(duì)象，還是一個(gè)靜態(tài)成員對(duì)象，
// 所以前面還需使用template聲明Node是一個(gè)類對(duì)象。
typedef typename LinkList<T>::Node Node;
struct SNode : public Node
{
void *operator new (unsigned int size, void *p)
{
(void)size;
return p;
}
};
unsigned char m_space[sizeof(SNode) *N];
unsigned int m_used[N];
Node *create()
{
SNode *ret = NULL;
for(int i=0; i<N; i++)
{
if( !m_used[i] ) // 0為空，1為有數(shù)據(jù)元素，不可用
{
ret = reinterpret_cast<SNode*>(m_space) + i;
ret = new(ret)SNode; //返回指定內(nèi)存地址
m_used[i] = 1;
break;
}
}
return ret;
}
void destroy(Node *pn)
{
SNode *space = reinterpret_cast<SNode *>(m_space);
SNode *spn = dynamic_cast<SNode*>(pn);
for(int i=0; i<N; i++)
{
if( pn == (space + i) )
{
m_used[i] = 0;
spn->~SNode(); //直接調(diào)用析構(gòu)函數(shù)
}
}
}
public:
StaticLinkList()
{
for(int i=0; i<N; i++)
{
m_used[i] = 0;
}
}
};上節(jié)封裝create和destroy的意義：
為了本節(jié)實(shí)現(xiàn)StaticList 做準(zhǔn)備，兩者的不同之處在于鏈表節(jié)點(diǎn)內(nèi)存分配的不同，因此將僅有的不同封裝與父類和子類的虛函數(shù)中。最終通過(guò)多態(tài)技術(shù)，來(lái)實(shí)現(xiàn)。
template <typename T, int N>
class StaticLinkList : public LinkList<T>
{
protected:
// typename 表明Node是一個(gè)類而非靜態(tài)成員變量，Node中包含泛指類型，所以使用 LinkList<T>指明
typedef typename LinkList<T>::Node Node;
struct SNode : public Node
{
// 重載后的結(jié)果，返回指定內(nèi)存空間
void* operator new(unsigned int size, void* p)
{
(void)size;
return p;
}
};
unsigned int m_space[N];
unsigned int m_used[N];
Node* create(void)
{
SNode* ret = NULL;
for(int i=0; i<N; i++)
{
if(!m_used[i])
{
ret = reinterpret_cast<SNode*>(m_space) + i;
ret = new(ret) SNode(); //返回指定內(nèi)存空間
break;
}
}
return ret;
}
void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* spn = dynamic_cast<SNode*>(pn);
for(int i=0; i<N; i++)
{
if(pn == space+i)
{
m_used[i] = 0;
spn->~SNode();
break;
}
}
}
public:
StaticLinkList()
{
for(int i=0; i<N; i++)
{
m_used[i] = 0;
}
}
int capacity(void)
{
return N;
}
/**
析構(gòu)函數(shù)定義的原則：對(duì)于一個(gè)獨(dú)立類，構(gòu)造函數(shù)中沒(méi)有使用系統(tǒng)資源，則可以不用定義析構(gòu)函數(shù)，使用系統(tǒng)默認(rèn)系統(tǒng)的即可。
但對(duì)于StaticLinkList這個(gè)類，繼承制LinkList，當(dāng)我們沒(méi)有定義該類的析構(gòu)函數(shù)時(shí)：在對(duì)象析構(gòu)時(shí)，會(huì)默認(rèn)去調(diào)用編譯器自己提供的析構(gòu)函數(shù)，然后再調(diào)用其父類的析構(gòu)函數(shù)，再其父類的析構(gòu)函數(shù)中會(huì)調(diào)用clear函數(shù)，最終會(huì)調(diào)用父類的destroy函數(shù)。
在父類的destroy 中會(huì)使用delete去釋放堆空間，而我我們StaticLinkList中的數(shù)據(jù)并不是在堆空間的，所以會(huì)導(dǎo)致程序的不穩(wěn)定。
解決辦法：自定義析構(gòu)函數(shù)，最終調(diào)用子類的destroy函數(shù)。
**/
~StaticLinkList()
{
this->clear();
}
};
1.什么是循環(huán)鏈表？
概念上：任意元素有一個(gè)前驅(qū)和后繼，所有數(shù)據(jù)元素的關(guān)系構(gòu)成一個(gè)環(huán)
實(shí)現(xiàn)上：循環(huán)鏈表是一種特殊的鏈表，尾節(jié)點(diǎn)的指針保存了首節(jié)點(diǎn)的地址。
邏輯構(gòu)成：
實(shí)現(xiàn)思路：
1.通過(guò)模板定義CircleList類，繼承自LinkList類
2.定義內(nèi)部函數(shù)last_to_first()用于將單鏈表首尾相連
3.特殊處理：
首元素的插入和刪除操作：
插入首元素時(shí)，先將頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的指針指向要插入的元素，然后將要插入元素的指針指向之前的首節(jié)點(diǎn)；
刪除首節(jié)點(diǎn)時(shí)，首先將尾節(jié)點(diǎn)和頭的指針指向要?jiǎng)h除節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)）。
4.重新實(shí)現(xiàn)：清空操作和遍歷操作，注意異常安全（注意異常安全）。
循環(huán)鏈表可用于解決約瑟夫環(huán)的問(wèn)題。
循環(huán)鏈表聲明：
template < typename T >
class CircleList : public LinkList<T>
{
protected:
Node* last() const
void last_to_first() const
int mod(int i) const
public:
bool insert(const T& e)
bool insert(int index, const T& e)
bool remove(int index)
bool set(int index, const T& e)
bool get(int index, const T& e) const
T get(int index) const
int find (const T& e) const
void clear()
bool move(int i, int step)
bool end()
~CircleList()
};注意：循環(huán)鏈表的實(shí)現(xiàn)中，查找和遍歷及清空操作要注意異常安全。不能改變鏈表的狀態(tài)（比如先將循環(huán)鏈表改為單鏈表，然后直接調(diào)用單鏈表的相關(guān)實(shí)現(xiàn)，最后再將鏈表首尾相連。這樣操作如果再過(guò)程中調(diào)用了泛指類型的構(gòu)造函數(shù)，而且拋出異常，將導(dǎo)致循環(huán)鏈表變成單鏈表）。
template < typename T >
class CircleLinkList : public LinkList<T>
{
protected:
typedef typename LinkList<T>::Node Node;
int mod(int i)
{
return ( (this->m_length == 0) ? 0 : (i % this->m_length));
}
Node* last()
{
return this->position(this->m_length-1)->next;
}
void last_to_first()
{
last()->next = this->m_header.next;
}
public:
bool insert(const T& e)
{
return insert(this->m_length, e);
}
bool insert(int index, const T& e)
{
bool ret = true;
index = index % (this->m_length + 1); // 可插入點(diǎn)=length+1
ret = LinkList<T>::insert(index, e);
if(index == 0)
{
last_to_first();
}
return ret;
}
bool remove(int index)
{
bool ret = true;
index = mod(index);
if(index == 0)
{
Node* toDel = this->m_header.next;
if(toDel != NULL) // 類似于判斷index是否合法
{
this->m_header.next = toDel->next;
this->m_length--;
if(this->m_length > 0)
{
last_to_first();
if(this->m_current == toDel)
{
this->m_current = toDel->next;
}
}
else
{
this->m_current = NULL;
this->m_header.next = NULL;
this->m_length = 0;
}
}
else
{
ret = false;
}
}
else
{
ret = LinkList<T>::remove(index);
}
return ret;
}
T get(int index)
{
return LinkList<T>::get(mod(index));
}
bool get(int index, T& e)
{
return LinkList<T>::get(mod(index), e);
}
bool set(int index, const T& e)
{
return LinkList<T>::set(mod(index), e);
}
int find(const T& e) const
{
int ret = -1;
Node* node = this->m_header.next;
for(int i=0; i<this->m_length; i++)
{
if(node->value == e)
{
ret = i;
break;
}
node = node->next;
}
return ret;
}
bool move(int i, int step)
{
return LinkList<T>::move(mod(i), step);
}
bool end()
{
return ( (this->m_current == NULL) || (this->m_length == 0) );
}
void clear()
{
if(this->m_length > 1)
{
remove(1);
}
if(this->m_length == 1)
{
Node* toDel = this->m_header.next;
this->m_current = NULL;
this->m_header.next = NULL;
this->m_length = 0;
this->destroy(toDel);
}
}
~CircleLinkList()
{
clear();
}
};
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼