溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
我們在之前學習了線性表和單鏈表的相關特性，本節博客我們就來看看它們的區別。首先提出一個問題：如何判斷某個數據元素是否存在于線性表中？那肯定是直接遍歷一遍了，我們來看看代碼
#include <iostream>
#include "LinkList.h"
using namespace std;
using namespace DTLib;
int main()
{
LinkList<int> list;
for(int i=0; i<5; i++)
{
list.insert(0, i);
}
for(int i=0; i<list.length(); i++)
{
if( list.get(i) == 3 )
{
cout << list.get(i) << endl;
}
}
return 0;
}我們判斷 3 是都存在于當前線性表中，如果存在，便輸出。看看輸出結果
我們看到在查找的時候還得去手動遍歷一遍，感覺很麻煩。那么我們在之前的實現中，少了一個操作，那便是查找操作 find。它可以為線性表（List）增加一個查找操作，原型為 int find(const T& e) const; 參數為帶查找的數據元素；返回值：>=0 時，則表示數據元素在線性表中第一次出現的位置；為 -1 時，則表示數據元素不存在。下面我們看看數據元素查找的示例代碼，如下
LinkList<int> list;
for(int i=0; i<5; i++)
{
list.insert(0, i);
}
cout << list.find(3) << endl; // ==> 1下來我們在 List.h 源碼中添加 find 操作，如下
List.h 源碼
#ifndef LIST_H
#define LIST_H
#include "Object.h"
namespace DTLib
{
template < typename T >
class List : public Object
{
protected:
List(const List&);
List& operator= (const List&);
public:
List() {}
virtual bool insert(const T& e) = 0;
virtual bool insert(int i, const T& e) = 0;
virtual bool remove(int i) = 0;
virtual bool set(int i, const T& e) = 0;
virtual bool get(int i, T& e) const = 0;
virtual int find(const T& e) const = 0;
virtual int length() const = 0;
virtual void clear() = 0;
};SeqList.h 源碼
#ifndef SEQLIST_H
#define SEQLIST_H
#include "List.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class SeqList : public List<T>
{
protected:
T* m_array;
int m_length;
public:
bool insert(int i, const T& e)
{
bool ret = ((0 <= i) && (i <= m_length));
ret = ret && (m_length < capacity());
if( ret )
{
for(int p=m_length-1; p>=i; p--)
{
m_array[p+1] = m_array[p];
}
m_array[i] = e;
m_length++;
}
return ret;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
for(int p=i; p<m_length-1; p++)
{
m_array[p] = m_array[p+1];
}
m_length--;
}
return ret;
}
bool set(int i, const T& e)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
m_array[i] = e;
}
return ret;
}
bool get(int i, T& e) const
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
e = m_array[i];
}
return ret;
}
int find(const T& e) const // O(n)
{
bool ret = -1;
for(int i=0; i<m_length; i++)
{
if( m_array[i] == e )
{
ret = i;
break;
}
}
return ret;
}
int length() const
{
return m_length;
}
void clear()
{
m_length = 0;
}
T& operator[] (int i)
{
if( (0 <= i) && (i < m_length) )
{
return m_array[i];
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
}
}
T operator[] (int i) const
{
return (const_cast<SeqList<T>&>(*this))[i];
}
virtual int capacity() const = 0;
};
}
#endif // SEQLIST_HLinkList.h 源碼
#ifndef LINKLIST_H
#define LINKLIST_H
#include "List.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class LinkList : public List<T>
{
protected:
struct Node : public Object
{
T value;
Node* next;
};
mutable struct : public Object
{
char reserved[sizeof(T)];
Node* next;
} m_header;
int m_length;
Node* position(int i) const
{
Node* ret = reinterpret_cast<Node*>(&m_header);
for(int p=0; p<i; p++)
{
ret = ret->next;
}
return ret;
}
public:
LinkList()
{
m_header.next = NULL;
m_length = 0;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
bool insert(int i, const T& e)
{
bool ret = ((0 <= i) && (i <= m_length));
if( ret )
{
Node* node = new Node();
if( node != NULL )
{
Node* current = position(i);
node->value = e;
node->next = current->next;
current->next = node;
m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
}
}
}
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
Node* current = position(i);
Node* toDel = current->next;
current->next = toDel->next;
delete toDel;
m_length--;
}
return ret;
}
bool set(int i, const T& e)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
position(i)->next->value = e;
}
return ret;
}
T get(int i) const
{
T ret;
if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element ...");
}
}
bool get(int i, T& e) const
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
e = position(i)->next->value;
}
return ret;
}
int find(const T& e) const
{
int ret = -1;
int i = 0;
Node* node = m_header.next;
while( node )
{
if( node->value == e )
{
ret = i;
break;
}
else
{
node = node->next;
i++;
}
}
return ret;
}
int length() const
{
return m_length;
}
void clear()
{
while( m_header.next )
{
Node* toDel = m_header.next;
m_header.next = toDel->next;
delete toDel;
}
m_length = 0;
}
~LinkList()
{
clear();
}
};
}
#endif // LINKLIST_H那么此時的 main.cpp 就可以寫成這樣的了
#include <iostream>
#include "LinkList.h"
using namespace std;
using namespace DTLib;
int main()
{
LinkList<int> list;
for(int i=0; i<5; i++)
{
list.insert(0, i);
}
cout << list.find(3) << endl;
return 0;
}我們來看看結果
我們來查找下 -3 呢
我們看到如果查找的元素在里面，則返回 1；如果沒有，則返回 -1。那么我們如果查找的是類呢？那程序還會編譯通過嗎？我們來看看，main.cpp 源碼如下
#include <iostream>
#include "LinkList.h"
using namespace std;
using namespace DTLib;
class Test
{
int i;
public:
Test(int v = 0)
{
i = v;
}
};
int main()
{
Test t1(1);
Test t2(3);
Test t3(3);
LinkList<Test> list;
return 0;
}編譯結果如下
編譯報錯了，我們并沒有改動 LinkList 中的代碼，為什么這塊會報錯呢？那么此時我們想要讓兩個類對象進行相等的比較，可是我們并沒有定義 == 操作符，此時肯定會出錯。那么我們在類 Test 中進行 == 操作符的定義，如下
class Test
{
int i;
public:
Test(int v = 0)
{
i = v;
}
bool operator == (const Test& obj)
{
return true;
}
};我們再來編譯下，看看結果
編譯是通過的，那么我們此時便覺得奇怪了。我們為什么要在 Test 類中定義 == 操作符呢，此時最好的解決辦法是在頂層父類 Object 中添加 == 和 ！= 操作符，然后將 Test 類繼承自 Object 類就可以了。
Object.h 源碼
#ifndef OBJECT_H
#define OBJECT_H
namespace DTLib
{
class Object
{
public:
void* operator new (unsigned int size) throw();
void operator delete (void* p);
void* operator new[] (unsigned int size) throw();
void operator delete[] (void* p);
bool operator == (const Object& obj);
bool operator != (const Object& obj);
virtual ~Object() = 0;
};
}
#endif // OBJECT_HObject.cpp 源碼
#include "Object.h"
#include <cstdlib>
namespace DTLib
{
void* Object::operator new (unsigned int size) throw()
{
return malloc(size);
}
void Object::operator delete (void* p)
{
free(p);
}
void* Object::operator new[] (unsigned int size) throw()
{
return malloc(sizeof(size));
}
void Object::operator delete[] (void* p)
{
free(p);
}
bool Object::operator == (const Object& obj)
{
return (this == &obj);
}
bool Object::operator != (const Object& obj)
{
return (this != &obj);
}
Object::~Object()
{
}
}此時的 main.cpp 代碼如下
#include <iostream>
#include "LinkList.h"
using namespace std;
using namespace DTLib;
class Test : public Object
{
int i;
public:
Test(int v = 0)
{
i = v;
}
bool operator == (const Test& obj)
{
return (i == obj.i);
}
};
int main()
{
Test t1(1);
Test t2(3);
Test t3(3);
LinkList<Test> list;
list.insert(t1);
list.insert(t2);
list.insert(t3);
cout << list.find(t2) << endl;
return 0;
}我們來看看編譯輸出結果
那么我們在 main.cpp 測試代碼中將 t1, t2, t3 對象插入到 list 中，然后查找 t2 是否存在，那么它肯定是存在的，因此會輸出 1。那么我們來分析下順序表和單鏈表的時間復雜度的對比，如下
我們看到順序表只有三個 O(n) ，而單鏈表幾乎是全部是 O(n)。從時間復雜度上來看，似乎順序表更占優勢，那么我們在平時的開發中，為什么經常見到的是單鏈表而不是順序表呢？在實際的工程開發中，時間復雜度只是一個參考指標，對于內置基礎類型，順序表和單鏈表的效率不相上下，而對于自定義類型來說，順序表在效率上低于單鏈表。在插入和刪除操作中，順序表涉及大量數據對象的復制操作，而單鏈表只涉及指針操作，效率與數據對象無關。對于數據訪問，順序表是隨機訪問，可直接定位數據對象；而對于單鏈表來說是順序訪問，必須從頭訪問數據對象，無法直接定位。
一般在工程開發中，順序表主要用于：數據元素類型相對簡單，不涉及深拷貝；數據元素相對穩定，訪問操作遠多于插入和刪除操作。單鏈表主要用于：數據元素的類型相對復雜，復制操作相對耗時；數據元素不穩定，需要經常插入和刪除，訪問操作較少的情況。通過今天的學習，總結如下：1、線性表中元素的查找依賴于相等比較操作符（==）；2、順序表適用于訪問需求量較大的場合（隨機訪問）；3、單鏈表適用于數據元素頻繁插入刪除的場合（順序訪問）；4、當數據類型相對簡單時，順序表和單鏈表的效率不相上下。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
