欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表詳解

 更新時間:2015年04月22日 14:50:01   作者:RussellLuo  
這篇文章主要介紹了Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表,詳細分析了鏈表的概念、定義及Python實現(xiàn)與使用鏈表的相關技巧,非常具有實用價值,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表。分享給大家供大家參考。具體分析如下:

一、概述

鏈表(linked list)是一組數(shù)據(jù)項的集合,其中每個數(shù)據(jù)項都是一個節(jié)點的一部分,每個節(jié)點還包含指向下一個節(jié)點的鏈接。
根據(jù)結構的不同,鏈表可以分為單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表等。其中,單向鏈表和單向循環(huán)鏈表的結構如下圖所示:

二、ADT

這里只考慮單向循環(huán)鏈表ADT,其他類型的鏈表ADT大同小異。單向循環(huán)鏈表ADT(抽象數(shù)據(jù)類型)一般提供以下接口:

① SinCycLinkedlist() 創(chuàng)建單向循環(huán)鏈表
② add(item) 向鏈表中插入數(shù)據(jù)項
③ remove(item) 刪除鏈表中的數(shù)據(jù)項
④ search(item) 在鏈表中查找數(shù)據(jù)項是否存在
⑤ empty() 判斷鏈表是否為空
⑥ size() 返回鏈表中數(shù)據(jù)項的個數(shù)

單向循環(huán)鏈表操作的示意圖如下:

三、Python實現(xiàn)

Python的內建類型list底層是由C數(shù)組實現(xiàn)的,list在功能上更接近C++的vector(因為可以動態(tài)調整數(shù)組大小)。我們都知道,數(shù)組是連續(xù)列表,鏈表是鏈接列表,二者在概念和結構上完全不同,因此list不能用于實現(xiàn)鏈表。
在C/C++中,通常采用“指針+結構體”來實現(xiàn)鏈表;而在Python中,則可以采用“引用+類”來實現(xiàn)鏈表。在下面的代碼中,SinCycLinkedlist類代表單向循環(huán)鏈表,Node類代表鏈表中的一個節(jié)點:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
  def __init__(self, initdata):
    self.__data = initdata
    self.__next = None
  def getData(self):
    return self.__data
  def getNext(self):
    return self.__next
  def setData(self, newdata):
    self.__data = newdata
  def setNext(self, newnext):
    self.__next = newnext
class SinCycLinkedlist:
  def __init__(self):
    self.head = Node(None)
    self.head.setNext(self.head)
  def add(self, item):
    temp = Node(item)
    temp.setNext(self.head.getNext())
    self.head.setNext(temp)
  def remove(self, item):
    prev = self.head
    while prev.getNext() != self.head:
      cur = prev.getNext()
      if cur.getData() == item:
        prev.setNext(cur.getNext())
      prev = prev.getNext()
  def search(self, item):
    cur = self.head.getNext()
    while cur != self.head:
      if cur.getData() == item:
        return True
      cur = cur.getNext()
    return False
  def empty(self):
    return self.head.getNext() == self.head
  def size(self):
    count = 0
    cur = self.head.getNext()
    while cur != self.head:
      count += 1
      cur = cur.getNext()
    return count
if __name__ == '__main__':
  s = SinCycLinkedlist()
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  s.add(19)
  s.add(86)
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  print('86 is%s in s' % ('' if s.search(86) else ' not',))
  print('4 is%s in s' % ('' if s.search(4) else ' not',))
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  s.remove(19)
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

運行結果:

$ python sincyclinkedlist.py
s.empty() == True, s.size() == 0
s.empty() == False, s.size() == 2
86 is in s
4 is not in s
s.empty() == False, s.size() == 2
s.empty() == False, s.size() == 1

希望本文所述對大家的Python程序設計有所幫助。

相關文章

  • macOS M1(AppleSilicon) 安裝TensorFlow環(huán)境

    macOS M1(AppleSilicon) 安裝TensorFlow環(huán)境

    蘋果為M1芯片的Mac提供了TensorFlow的支持,本文主要介紹了如何給使用M1芯片的macOS安裝TensorFlow的環(huán)境,感興趣的可以了解一下
    2021-08-08
  • Python實現(xiàn)TCP通信的示例代碼

    Python實現(xiàn)TCP通信的示例代碼

    這篇文章主要介紹了Python實現(xiàn)TCP通信的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-09-09
  • python使用梯度下降算法實現(xiàn)一個多線性回歸

    python使用梯度下降算法實現(xiàn)一個多線性回歸

    這篇文章主要為大家詳細介紹了python使用梯度下降算法實現(xiàn)一個多線性回歸,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-03-03
  • 詳解Selenium 元素定位和WebDriver常用方法

    詳解Selenium 元素定位和WebDriver常用方法

    這篇文章主要介紹了詳解Selenium 元素定位和WebDriver常用方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • python自定義函數(shù)實現(xiàn)最大值的輸出方法

    python自定義函數(shù)實現(xiàn)最大值的輸出方法

    今天小編就為大家分享一篇python自定義函數(shù)實現(xiàn)最大值的輸出方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-07-07
  • 基于pytorch的RNN實現(xiàn)字符級姓氏文本分類的示例代碼

    基于pytorch的RNN實現(xiàn)字符級姓氏文本分類的示例代碼

    當使用基于PyTorch的RNN實現(xiàn)字符級姓氏文本分類時,我們可以使用一個非常簡單的RNN模型來處理輸入的字符序列,并將其應用于姓氏分類任務,本文給大家舉了一個基本的示例代碼,需要的朋友可以參考下
    2023-12-12
  • python讀取文件名稱生成list的方法

    python讀取文件名稱生成list的方法

    下面小編就為大家分享一篇python讀取文件名稱生成list的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-04-04
  • Python實現(xiàn)單詞拼寫檢查

    Python實現(xiàn)單詞拼寫檢查

    這篇文章主要介紹了Python實現(xiàn)單詞拼寫檢查,本文講解了單詞拼寫檢查的一些知識并給出兩種實現(xiàn)方法,需要的朋友可以參考下
    2015-04-04
  • 詳解 Python中LEGB和閉包及裝飾器

    詳解 Python中LEGB和閉包及裝飾器

    這篇文章主要介紹了詳解 Python中LEGB和閉包及裝飾器的相關資料,主要介紹了函數(shù)作用域和閉包的理解和使用方法及Python中的裝飾器,需要的朋友可以參考下
    2017-08-08
  • 淺談Python的正則表達式

    淺談Python的正則表達式

    這篇文章主要介紹了淺談Python的正則表達式,正則表達式本身是獨立于編程語言的知識,但是它又依附于編程語言,需要的朋友可以參考下
    2023-04-04

最新評論