溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關C++和python如何實現單鏈表的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
鏈表是數據元素的線性集合（Linear Collection），物理存儲不連續。那么，這種設計的優點是什么？缺點又是什么？
鏈表的基本結構：
鏈表是由一系列的“節點”組成在一起的集合，節點（Node）由數據域（data）和指針域（next）組成。
從功能上看，data負責存儲數據，next負責存儲下一個節點的位置。當然，用更加嚴格的語句來講，next存儲的是其直接后繼的地址，關于直接后繼的定義見：
鏈表的分類：
常見的鏈表種類有：單向鏈表、雙向鏈表、單向循環鏈表、雙向循環鏈表，將會在后面文章中單獨介紹各種鏈表的結構和代碼實現，以及對應的鏈表操作。
鏈表的基本操作：
鏈表的基礎操作包含：插入、刪除、查找、合并等，此外還有：反轉、排序、深度復制等。
鏈表的優點：
插入和刪除快；
存儲空間不受限制，可動態申請擴充，不需事先開辟內存；
鏈表的缺點：
相比于數組，鏈表的需要更多的存儲空間（需存儲指針）；
存儲不連續導致其訪問時間長；
從反向訪問角度，單向鏈表難以反向訪問，擴展為雙向鏈表則需要額外存儲反向指針；
每次節點訪問都需要從頭部開始；
基本結構：
單鏈表的結構含有四個概念：頭指針、頭結點、普通Node、尾結點，下面分別介紹：
頭指針指向頭結點，是單鏈表的表示，必不可少；
頭結點是單鏈表的第一個節點，其數據域內容一般無效；
普通Node即用于數據存儲和直接后繼指針存儲的節點；
尾結點即鏈表中最后一個節點，其指針域next為空，其后無節點；
單鏈表的基本操作：
針對單鏈表常見的操作有：增、改、查、刪等，
常用的操作如下：
（1）增
對鏈表添加元素一般有三種方法：頭插法(add)、尾插法(append)、任意位置插入法(insert)。
（2）改
改動鏈表中某個節點的data。
（3）查
查找分為按值查找和按位置查找兩種，前者表示按照值查找對應位置，后者表示按位置查找對應值；
（4）刪
刪除分為按值刪除和按位置刪除兩種；前者表示按照值刪除對應節點，后者表示按照位置刪除對應節點；
實現說明：
按照自己目前所看的資料，一般都會實現下面介紹的這些函數，具體介紹放在python和C++實現中。
按照單鏈表的定義可知，節點包含數據域data和指針域next：
但是由于next和python的內置函數next()重名，所以指針域使用pointer表示。
代碼如下：
class Node: def __init__(self, data): """ Args: data: data of node, any type """ self.data = data self.pointer = None
上述Node類對象即為鏈表的基本組成結構，可以用于實現頭結點、普通節點和尾結點。
因此，鏈表類只需要提供頭指針：
class Single_Linked_List: def __init__(self, node=None): self.__head = node
實際上，只需要判斷頭指針是否指向Node類對象（或是否等于None），就可判斷一個鏈表是否為空：
def is_empty(self): """判斷鏈表是否為空""" if self.__head == None: return True else: return False
在鏈表頭進行節點插入是很常見的插入操作，這種方式使得“先插入的節點在鏈表尾部”。頭插法需要將頭指針指向新的節點，并讓新的節點指向原來的頭結點：
def add(self, data): """Add dnode into head """ # 創建新節點 node = Node(data) # 令新的節點指向原來的頭結點 node.pointer = self.__head # 令頭指針指向新的節點 self.__head = node
如果想要鏈表節點次序和插入次序相同，就需要使用尾插法。在插入之前需要判斷鏈表是否為空，如果不為空才能進行插入（可以調用前面定義的is_empty()函數，但是下述代碼沒有）。
此外，還需要進行鏈表的遍歷操作，找到最后一個節點。單鏈表只能從表頭開始訪問，所以每次尾插都必須遍歷。
def append(self, data): """ append node into tail """ node = Node(data) # 頭指針為空時即為首節點 if self.__head == None: self.__head = node # 頭指針不為空時進行遍歷 else: current = self.__head while current.pointer != None: current = current.pointer current.pointer = node
前面介紹的頭插法和尾插法，其原理相對簡單，但是并不能完全滿足插入需求。如果知道目標插入的位置，可以采用insert()函數實現任意位置的節點插入。
需要注意的是，在實現insert()函數時必須考慮到“position”參數可能出現的幾種情況。比如python中并沒有明確的類型要求，所以要檢查“position”是不是int類型。
對于核心的節點插入實現功能，需要找到目標插入位置對應的節點，并使得這個節點指向新節點，讓新節點指向原位置節點的后一個節點。這個過程類似于鐵鏈中加入鐵環的過程，要保證新鐵環和原來的兩個鐵環相連接。
def insert(self, position, data):
"""在任意位置插入節點
Args:
position:插入節點的位置,int
data:插入節點的值
"""
if not isinstance(position, int):
raise ValueError("expect type is 'int', but got {}".format(position.__class__))
# 頭插法
if position <= 0:
self.add(data)
# 尾插法
elif position > self.get_length():
self.append(data)
else:
current = self.__head
current_position = 0
node = Node(data)
# 目的：計算出插入位置
while current_position < position -1:
current_position += 1
current = current.pointer
# 首先：必須使得當前節點的pointer指針指向新建的node
# 其次：必須保證新建的node的pointer指向當前節點的后一個節點
node.pointer = current.pointer
current.pointer = node對于調用者和類內部的其它函數來做，鏈表長度是一個非常有用的值。比如在插入函數insert()中，需要判斷插入位置是不是大于鏈表長度。
計算鏈表長度的實現比較簡單，只需要遍歷鏈表的所有節點，并用計數器來統計節點的數目即可。
def get_length(self): """ 獲取鏈表的長度""" # 沒有任何node if self.__head == None: return 0 # 節點數統計 else: current = self.__head length = 0 while current != None: current = current.pointer length += 1 return length
鏈表、樹、圖等結構都需要遍歷操作，其中鏈表的遍歷比較簡單，只需要依次的訪問所有節點即可。
def traversal(self):
current = self.__head
i = 0
# 循環結束的條件依舊是節點的pointer指向不為空
while current != None:
print("Element {} is {} ".format(i, current.data))
current = current.pointer
i += 1前面提到搜索有按值搜索和按位置搜索兩種，它們的原理和實現都十分相似，所以僅以按值搜索為例。
需要注意的是，insert()函數需要判斷鏈表是否為空，并且需要考慮到目標值不在鏈表中的情況，分別對應不同的返回值。
def search(self, data): """ 返回值為data的第一個節點""" if self.__head == None: return -1 else: current = self.__head current_position = 0 # 遍歷節點 while current != None: # 目標值搜索成功 if current.data == data: return current_position # 目標值搜索不到則繼續搜索 else: current_position += 1 current = current.pointer # 目標值不存在于鏈表中 return False
上述的查找中以“按值查找”為例，這次刪除中同樣以“按值刪除”為例，“按位置刪除”的實現與之類似。
按值刪除，即刪除目標值對應的目標節點。在進行遍歷時，需要記錄當前節點和當前節點的前一個節點。因為，一旦查找大目標值所在的目標節點，需要令目標節點的前一個節點指向目標節點的下一個節點，即完成節點的刪除。
def delete(self, data): """ 刪除值為data的第一個節點""" if self.is_empty(): return None # 記錄當前節點和前一個節點 current = self.__head piror = None while current != None: # 查找成功分為兩種情況 if current.data == data: # 目標節點為頭結點 if current == self.__head: self.__head = self.__head.pointer return True # 目標節點不是頭結點 # 令目標節點的前一個節點指向目標節點的后一個節點 else: piror.pointer = current.pointer return True # 更新當前節點和前一個節點 else: piror = current current = current.pointer return False
前面的python實現中已經分析了各個函數的作用，以及對應的實現過程。雖然python和C++的語法不同，但是核心過程是類似的，所以下面不再重復對過程的敘述。
由于C++的指針必須指定類型，所以需要使用空指針NULL作為pointer的值。
class Node{
public:
int data;
Node *pointer=NULL;
};遵循聲明和實現分類的策略，先對各個函數進行聲明。
class SingleLinkedList {
public:
SingleLinkedList();
bool isEmpty();
int getLength();
void add(int data);
void append(int data);
void insert(int position, int data);
void traversal();
int search(int data);
void remove(int data);
private:
Node *head;
};bool SingleLinkedList::isEmpty() {
// 頭結點不指向任何結點，為空
if (head->pointer == NULL) {
return true;
}
else {
return false;
}
}void SingleLinkedList::add(int data) {
// 當原列表僅有頭結點時，直接插入新節點即可
if (head->pointer == NULL) {
head->pointer = new Node;
head->pointer->data = data;
}
// 當原列表頭結點后面含有后繼節點時
// 令頭結點直接后繼為新節點
// 并令新節點的直接后繼為原來頭結點的直接后繼
else {
// 臨時存儲頭結點的直接后繼
Node *temp = head->pointer;
head->pointer = new Node;
head->pointer->data = data;
head->pointer->pointer = temp;
}
}void SingleLinkedList::append(int data) {
Node *current = head->pointer;
// 找到列表的最后一個節點的位置current
// current的指針域為NULL
while (current->pointer!=NULL)
{
current = current->pointer;
}
// 令current的指針域指向新節點，完成插入
current->pointer = new Node;
current->pointer->data = data;
}void SingleLinkedList::insert(int position, int data) {
// 頭插法
if (position <= 0) {
add(data);
}
// 尾插法
else if (position > getLength()){
append(data);
}
else {
// 令頭指針所在的位置為0
int current_position = 0;
Node *current = head;
Node *prior = NULL;
// 查找目標節點位置current，并記錄其直接前驅節點piror
while (current_position<position)
{
// 更新當前節點和直接前驅
prior = current;
current = current->pointer;
current_position++;
}
// 目標位置的直接前驅prior指向新節點
// 新節點指向目標位置的節點
prior->pointer = new Node;
prior->pointer->data = data;
prior->pointer->pointer = current;
}
};int SingleLinkedList::getLength() {
int counter = 0;
Node *current = head;
// 遍歷鏈表，直到最后一個元素
while (current->pointer!=NULL)
{
counter++;
current = current->pointer;
}
return counter;
}void SingleLinkedList::traversal() {
Node *current;
// 指向頭結點的直接后繼
current = head->pointer;
int counter = 1;
// 遍歷鏈表，輸出每個節點的值
while (current!=NULL)
{
printf("Element in %d is %d \n", counter, current->data);
counter++;
current = current->pointer;
}
}int SingleLinkedList::search(int data) {
int current_position = 1;
Node *current = head->pointer;
while (current!=NULL)
{
// 搜索成功返回當前位置
if (current->data == data) {
return current_position;
}
// 繼續更新位置；
current = current->pointer;
current_position++;
}
// 搜索失敗，返回-1
return -1;
}void SingleLinkedList::remove(int data) {
Node *current = head->pointer;
Node *prior = head;
// 遍歷鏈表
while (current!=NULL)
{
// 查找到目標位置
if (current->data == data) {
// 令目標位置的直接前驅指向目標節點的直接后繼
prior->pointer = current->pointer;
break;
}
// 更新當前節點和其前驅節點
prior = current;
current = current->pointer;
}
}感謝各位的閱讀！關于“C++和python如何實現單鏈表”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
