亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++和python實現(xiàn)單鏈表及其原理

 更新時間：2022年03月11日 10:17:56   作者：機器學習入坑者  
這篇文章主要介紹了C++和python實現(xiàn)單鏈表及其原理,單鏈表是鏈表家族中的一員，每個節(jié)點依舊由數(shù)據(jù)域（data）和指針域（next）組成，鏈表的具體概念下面文章將詳細介紹，需要的小伙伴可以參考一下

一、鏈表的基本概念

鏈表是數(shù)據(jù)元素的線性集合（Linear Collection），物理存儲不連續(xù)。那么，這種設(shè)計的優(yōu)點是什么？缺點又是什么？

鏈表的基本結(jié)構(gòu)：

鏈表是由一系列的“節(jié)點”組成在一起的集合，節(jié)點（Node）由數(shù)據(jù)域（data）和指針域（next）組成。

從功能上看，data負責存儲數(shù)據(jù)，next負責存儲下一個節(jié)點的位置。當然，用更加嚴格的語句來講，next存儲的是其直接后繼的地址，關(guān)于直接后繼的定義見：

鏈表的分類：

常見的鏈表種類有：單向鏈表、雙向鏈表、單向循環(huán)鏈表、雙向循環(huán)鏈表，將會在后面文章中單獨介紹各種鏈表的結(jié)構(gòu)和代碼實現(xiàn)，以及對應(yīng)的鏈表操作。

鏈表的基本操作：

鏈表的基礎(chǔ)操作包含：插入、刪除、查找、合并等，此外還有：反轉(zhuǎn)、排序、深度復(fù)制等。

鏈表的優(yōu)點：

  • 插入和刪除快；
  • 存儲空間不受限制，可動態(tài)申請擴充，不需事先開辟內(nèi)存；

鏈表的缺點：

  • 相比于數(shù)組，鏈表的需要更多的存儲空間（需存儲指針）；
  • 存儲不連續(xù)導(dǎo)致其訪問時間長；
  • 從反向訪問角度，單向鏈表難以反向訪問，擴展為雙向鏈表則需要額外存儲反向指針；
  • 每次節(jié)點訪問都需要從頭部開始；

二、單鏈表

基本結(jié)構(gòu)：

單鏈表的結(jié)構(gòu)含有四個概念：頭指針、頭結(jié)點、普通Node、尾結(jié)點，下面分別介紹：

  • 頭指針指向頭結(jié)點，是單鏈表的表示，必不可少；
  • 頭結(jié)點是單鏈表的第一個節(jié)點，其數(shù)據(jù)域內(nèi)容一般無效；
  • 普通Node即用于數(shù)據(jù)存儲和直接后繼指針存儲的節(jié)點；
  • 尾結(jié)點即鏈表中最后一個節(jié)點，其指針域next為空，其后無節(jié)點；

單鏈表的基本操作：

針對單鏈表常見的操作有：增、改、查、刪等，

常用的操作如下：

（1）增

對鏈表添加元素一般有三種方法：頭插法(add)、尾插法(append)、任意位置插入法(insert)。

（2）改

改動鏈表中某個節(jié)點的data。

（3）查

查找分為按值查找和按位置查找兩種，前者表示按照值查找對應(yīng)位置，后者表示按位置查找對應(yīng)值；

（4）刪

刪除分為按值刪除和按位置刪除兩種；前者表示按照值刪除對應(yīng)節(jié)點，后者表示按照位置刪除對應(yīng)節(jié)點；

實現(xiàn)說明：

按照自己目前所看的資料，一般都會實現(xiàn)下面介紹的這些函數(shù)，具體介紹放在python和C++實現(xiàn)中。

1.python實現(xiàn)

（1）節(jié)點設(shè)計

按照單鏈表的定義可知，節(jié)點包含數(shù)據(jù)域data和指針域next：

但是由于next和python的內(nèi)置函數(shù)next()重名，所以指針域使用pointer表示。

代碼如下：

class Node:
? ? def __init__(self, data):
? ? ? ? """
? ? ? ? Args:
? ? ? ? ? ? data: data of node, any type?
? ? ? ? """
? ? ? ? self.data = data
? ? ? ? self.pointer = None

（2）鏈表類：Single_Linked_List

上述Node類對象即為鏈表的基本組成結(jié)構(gòu)，可以用于實現(xiàn)頭結(jié)點、普通節(jié)點和尾結(jié)點。

因此，鏈表類只需要提供頭指針：

class Single_Linked_List:
? ? def __init__(self, node=None):
? ? ? ? self.__head = node

（3）判斷鏈表是否為空：is_empty()函數(shù)

實際上，只需要判斷頭指針是否指向Node類對象（或是否等于None），就可判斷一個鏈表是否為空：

def is_empty(self):
? ? """判斷鏈表是否為空"""
? ? if self.__head == None:
? ? ? ? return True
? ? else:
? ? ? ? return False

（4）頭插法：add()函數(shù)

在鏈表頭進行節(jié)點插入是很常見的插入操作，這種方式使得“先插入的節(jié)點在鏈表尾部”。頭插法需要將頭指針指向新的節(jié)點，并讓新的節(jié)點指向原來的頭結(jié)點：

def add(self, data):
? ? """Add dnode into head
? ? """?
? ? # 創(chuàng)建新節(jié)點
? ? node = Node(data)
? ? # 令新的節(jié)點指向原來的頭結(jié)點
? ? node.pointer = self.__head
? ? # 令頭指針指向新的節(jié)點
? ? self.__head = node

（5）尾插法：append()函數(shù)

如果想要鏈表節(jié)點次序和插入次序相同，就需要使用尾插法。在插入之前需要判斷鏈表是否為空，如果不為空才能進行插入（可以調(diào)用前面定義的is_empty()函數(shù)，但是下述代碼沒有）。

此外，還需要進行鏈表的遍歷操作，找到最后一個節(jié)點。單鏈表只能從表頭開始訪問，所以每次尾插都必須遍歷。

def append(self, data):
? ? """ append node into tail
? ? """
? ? node = Node(data)
? ??
? ? # 頭指針為空時即為首節(jié)點
? ? if self.__head == None:
? ? ? ? self.__head = node
? ? # 頭指針不為空時進行遍歷
? ? else:
? ? ? ? current = self.__head
? ? ? ? while current.pointer != None:
? ? ? ? ? ? current = current.pointer
? ? ? ? current.pointer = node

（6）在任意位置插入：insert()函數(shù)

前面介紹的頭插法和尾插法，其原理相對簡單，但是并不能完全滿足插入需求。如果知道目標插入的位置，可以采用insert()函數(shù)實現(xiàn)任意位置的節(jié)點插入。

需要注意的是，在實現(xiàn)insert()函數(shù)時必須考慮到“position”參數(shù)可能出現(xiàn)的幾種情況。比如python中并沒有明確的類型要求，所以要檢查“position”是不是int類型。

對于核心的節(jié)點插入實現(xiàn)功能，需要找到目標插入位置對應(yīng)的節(jié)點，并使得這個節(jié)點指向新節(jié)點，讓新節(jié)點指向原位置節(jié)點的后一個節(jié)點。這個過程類似于鐵鏈中加入鐵環(huán)的過程，要保證新鐵環(huán)和原來的兩個鐵環(huán)相連接。

def insert(self, position, data):
? ? """在任意位置插入節(jié)點
? ? Args:
? ? ? ? position:插入節(jié)點的位置,int
? ? ? ? data:插入節(jié)點的值
? ? """
? ??
? ? 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
? ? ? ? # 首先：必須使得當前節(jié)點的pointer指針指向新建的node
? ? ? ? # 其次：必須保證新建的node的pointer指向當前節(jié)點的后一個節(jié)點
? ? ? ? node.pointer = current.pointer
? ? ? ? current.pointer = node

（7）計算鏈表長度：get_length()函數(shù)

對于調(diào)用者和類內(nèi)部的其它函數(shù)來做，鏈表長度是一個非常有用的值。比如在插入函數(shù)insert()中，需要判斷插入位置是不是大于鏈表長度。

計算鏈表長度的實現(xiàn)比較簡單，只需要遍歷鏈表的所有節(jié)點，并用計數(shù)器來統(tǒng)計節(jié)點的數(shù)目即可。

def get_length(self):
? ? """ 獲取鏈表的長度"""
? ? # 沒有任何node
? ? if self.__head == None:
? ? ? ? return 0
? ? # 節(jié)點數(shù)統(tǒng)計
? ? else:
? ? ? ? current = self.__head
? ? ? ? length = 0
? ? ? ? while current != None:
? ? ? ? ? ? current = current.pointer
? ? ? ? ? ? length += 1
? ? ? ? return length

（8）遍歷所有節(jié)點：traversal()函數(shù)

鏈表、樹、圖等結(jié)構(gòu)都需要遍歷操作，其中鏈表的遍歷比較簡單，只需要依次的訪問所有節(jié)點即可。

def traversal(self):
? ? current = self.__head
? ? i = 0
? ? # 循環(huán)結(jié)束的條件依舊是節(jié)點的pointer指向不為空
? ? while current != ?None:
? ? ? ? print("Element {} is {} ".format(i, current.data))
? ? ? ? current = current.pointer
? ? ? ? i += 1

（9）搜索：search()函數(shù)

前面提到搜索有按值搜索和按位置搜索兩種，它們的原理和實現(xiàn)都十分相似，所以僅以按值搜索為例。

需要注意的是，insert()函數(shù)需要判斷鏈表是否為空，并且需要考慮到目標值不在鏈表中的情況，分別對應(yīng)不同的返回值。

def search(self, data):
? ? """ 返回值為data的第一個節(jié)點"""
? ? if self.__head == None:
? ? ? ? return -1
? ? else:
? ? ? ? current = self.__head
? ? ? ? current_position = 0
? ? ? ? # 遍歷節(jié)點
? ? ? ? while current != None:
? ? ? ? ? ? # 目標值搜索成功
? ? ? ? ? ? if current.data == data:
? ? ? ? ? ? ? ? return current_position
? ? ? ? ? ? # 目標值搜索不到則繼續(xù)搜索 ? ? ??
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? current_position += 1
? ? ? ? ? ? ? ? current = current.pointer
? ? # 目標值不存在于鏈表中 ? ? ? ??
? ? return False

（10）刪除：delete()函數(shù)

上述的查找中以“按值查找”為例，這次刪除中同樣以“按值刪除”為例，“按位置刪除”的實現(xiàn)與之類似。

按值刪除，即刪除目標值對應(yīng)的目標節(jié)點。在進行遍歷時，需要記錄當前節(jié)點和當前節(jié)點的前一個節(jié)點。因為，一旦查找大目標值所在的目標節(jié)點，需要令目標節(jié)點的前一個節(jié)點指向目標節(jié)點的下一個節(jié)點，即完成節(jié)點的刪除。

def delete(self, data):
? ? """ 刪除值為data的第一個節(jié)點"""
? ? if self.is_empty():
? ? ? ? return None
? ??
? ? # 記錄當前節(jié)點和前一個節(jié)點
? ? current = self.__head
? ? piror = None
? ? while current != None:
? ? ? ? # 查找成功分為兩種情況
? ? ? ? if current.data == data:
? ? ? ? ? ? # 目標節(jié)點為頭結(jié)點
? ? ? ? ? ? if current == self.__head:
? ? ? ? ? ? ? ? self.__head = self.__head.pointer
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ?# 目標節(jié)點不是頭結(jié)點
? ? ? ? ? ? ?# 令目標節(jié)點的前一個節(jié)點指向目標節(jié)點的后一個節(jié)點 ??
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? piror.pointer = current.pointer
? ? ? ? ? ? ? ? return True
? ? ? ? ?# 更新當前節(jié)點和前一個節(jié)點
? ? ? ? ?else:
? ? ? ? ? ? piror = current
? ? ? ? ? ? current = current.pointer
? ? return False ??

2.C++實現(xiàn)

前面的python實現(xiàn)中已經(jīng)分析了各個函數(shù)的作用，以及對應(yīng)的實現(xiàn)過程。雖然python和C++的語法不同，但是核心過程是類似的，所以下面不再重復(fù)對過程的敘述。

（1）節(jié)點設(shè)計

由于C++的指針必須指定類型，所以需要使用空指針NULL作為pointer的值。

class Node{
public:
?? ?int data;
?? ?Node *pointer=NULL;
};

（2）鏈表類：SingleLinkedList

遵循聲明和實現(xiàn)分類的策略，先對各個函數(shù)進行聲明。

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;
};

（3）判斷鏈表是否為空：isEmpty()函數(shù)

bool SingleLinkedList::isEmpty() {
?? ?// 頭結(jié)點不指向任何結(jié)點，為空
?? ?if (head->pointer == NULL) {
?? ??? ?return true;
?? ?}
?? ?else {
?? ??? ?return false;
?? ?}
}

（4）頭插法：add()函數(shù)

void SingleLinkedList::add(int data) {
?? ?// 當原列表僅有頭結(jié)點時，直接插入新節(jié)點即可
?? ?if (head->pointer == NULL) {
?? ??? ?head->pointer = new Node;
?? ??? ?head->pointer->data = data;
?? ??? ?
?? ?}
?? ?// 當原列表頭結(jié)點后面含有后繼節(jié)點時
?? ?// 令頭結(jié)點直接后繼為新節(jié)點
?? ?// 并令新節(jié)點的直接后繼為原來頭結(jié)點的直接后繼
?? ?else {
?? ??? ?// 臨時存儲頭結(jié)點的直接后繼
?? ??? ?Node *temp = head->pointer;
?? ??? ?head->pointer = new Node;
?? ??? ?head->pointer->data = data;
?? ??? ?head->pointer->pointer = temp;
?? ?}
}

（5）尾插法：append()函數(shù)

void SingleLinkedList::append(int data) {
?? ?Node *current = head->pointer;
?? ?// 找到列表的最后一個節(jié)點的位置current
?? ?// current的指針域為NULL
?? ?while (current->pointer!=NULL)
?? ?{
?? ??? ?current = current->pointer;
?? ?}
?? ?// 令current的指針域指向新節(jié)點，完成插入
?? ?current->pointer = new Node;
?? ?current->pointer->data = data;
}

（6）在任意位置插入：insert()函數(shù)

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;
?? ??? ?// 查找目標節(jié)點位置current，并記錄其直接前驅(qū)節(jié)點piror
?? ??? ?while (current_position<position)
?? ??? ?{
?? ??? ??? ?// 更新當前節(jié)點和直接前驅(qū)
?? ??? ??? ?prior = current;
?? ??? ??? ?current = current->pointer;
?? ??? ??? ?current_position++;
?? ??? ?}
?? ??? ?// 目標位置的直接前驅(qū)prior指向新節(jié)點
?? ??? ?// 新節(jié)點指向目標位置的節(jié)點
?? ??? ?prior->pointer = new Node;
?? ??? ?prior->pointer->data = data;
?? ??? ?prior->pointer->pointer = current;
?? ?}
};

（7）計算鏈表長度：getLength()函數(shù)

int SingleLinkedList::getLength() {
?? ?int counter = 0;
?? ?Node *current = head;
?? ?// 遍歷鏈表，直到最后一個元素
?? ?while (current->pointer!=NULL)
?? ?{
?? ??? ?counter++;
?? ??? ?current = current->pointer;
?? ?}
?? ?return counter;
}

（8）遍歷所有節(jié)點：traversal()函數(shù)

void SingleLinkedList::traversal() {
?? ?Node *current;
?? ?// 指向頭結(jié)點的直接后繼
?? ?current = head->pointer;
?? ?int counter = 1;
?? ?// 遍歷鏈表，輸出每個節(jié)點的值
?? ?while (current!=NULL)
?? ?{
?? ??? ?printf("Element in %d is %d \n", counter, current->data);
?? ??? ?counter++;
?? ??? ?current = current->pointer;
?? ?}
}

（9）搜索：search()函數(shù)

int SingleLinkedList::search(int data) {
?? ?int current_position = 1;
?? ?Node *current = head->pointer;
?? ?while (current!=NULL)
?? ?{
?? ??? ?// 搜索成功返回當前位置
?? ??? ?if (current->data == data) {
?? ??? ??? ?return current_position;
?? ??? ?}
?? ??? ?// 繼續(xù)更新位置；
?? ??? ?current = current->pointer;
?? ??? ?current_position++;
?? ?}
?? ?// 搜索失敗，返回-1
?? ?return -1;
}

（10）刪除：remove()函數(shù)

void SingleLinkedList::remove(int data) {
?? ?Node *current = head->pointer;
?? ?Node *prior = head;
?? ?// 遍歷鏈表
?? ?while (current!=NULL)
?? ?{
?? ??? ?// 查找到目標位置
?? ??? ?if (current->data == data) {
?? ??? ??? ?// 令目標位置的直接前驅(qū)指向目標節(jié)點的直接后繼
?? ??? ??? ?prior->pointer = current->pointer;
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?// 更新當前節(jié)點和其前驅(qū)節(jié)點
?? ??? ?prior = current;
?? ??? ?current = current->pointer;
?? ?}
}

總結(jié)：

在使用python實現(xiàn)時，頭結(jié)點數(shù)據(jù)域data是有效的。這種方式使得代碼中需要很多的“if-else”判斷結(jié)構(gòu)，增加了代碼的復(fù)雜性。

在使用C++實現(xiàn)時，頭結(jié)點數(shù)據(jù)域data是無效的，這種方式使得代碼更加簡潔。

到此這篇關(guān)于C++和python實現(xiàn)單鏈表及其原理的文章就介紹到這了,更多相關(guān)C++,python單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • boost.asio框架系列之定時器Timer

    boost.asio框架系列之定時器Timer

    這篇文章介紹了boost.asio框架系列之定時器Timer，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2022-06-06
  • C++ 中引用和指針的關(guān)系實例詳解

    C++ 中引用和指針的關(guān)系實例詳解

    這篇文章主要介紹了C++ 中引用和指針的關(guān)系實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C++ Virtual關(guān)鍵字的具體使用

    C++ Virtual關(guān)鍵字的具體使用

    這篇文章主要介紹了C++ Virtual關(guān)鍵字的具體使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2020-11-11
  • 最小生成樹算法之Prim算法

    最小生成樹算法之Prim算法

    這篇文章主要講解了普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹,需要的朋友可以參考下
    2015-07-07
  • C語言實現(xiàn)數(shù)據(jù)的壓縮與解壓

    C語言實現(xiàn)數(shù)據(jù)的壓縮與解壓

    數(shù)據(jù)壓縮是通過一系列的算法和技術(shù)將原始數(shù)據(jù)轉(zhuǎn)換為更緊湊的表示形式,以減少數(shù)據(jù)占用的存儲空間,數(shù)據(jù)解壓縮則是將壓縮后的數(shù)據(jù)恢復(fù)到原始的表示形式,本文給大家詳細介紹了C語言實現(xiàn)數(shù)據(jù)壓縮與解壓,需要的朋友可以參考下
    2023-08-08
  • C++中的extern “C”用法詳解

    C++中的extern “C”用法詳解

    這篇文章主要介紹了C++中的extern “C”用法詳解,簡單來說,extern “C”是C++聲明或定義C語言符號的方法,是為了與C兼容,需要的朋友可以參考下
    2015-03-03
  • VC實現(xiàn)將網(wǎng)址解析出所有ip地址的實例代碼

    VC實現(xiàn)將網(wǎng)址解析出所有ip地址的實例代碼

    這篇文章主要介紹了VC實現(xiàn)將網(wǎng)址解析出所有ip地址的實例代碼,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2021-04-04
  • C語言實現(xiàn)電器銷售管理系統(tǒng)

    C語言實現(xiàn)電器銷售管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)電器銷售管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-06-06
  • c++標準輸入輸出流關(guān)系的前世今生

    c++標準輸入輸出流關(guān)系的前世今生

    這篇文章主要給大家介紹了關(guān)于c++標準輸入輸出流關(guān)系的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2021-04-04
  • C++實現(xiàn)LeetCode(139.拆分詞句)

    C++實現(xiàn)LeetCode(139.拆分詞句)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(139.拆分詞句),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-07-07

最新評論