浅谈Python单向链表的实现-Python チュートリアル-php.cn

ホームページ

バックエンド開発

Python チュートリアル

浅谈Python单向链表的实现

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 10, 2016 pm 03:07 PM

python

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。

删除操作可以通过修改一个指针来实现。

插入操作需要执行两次指针调整。

1. 单向链表的实现

1.1 Node实现

每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。

class Node():
  __slots__=['_item','_next']  #限定Node实例的属性
  def __init__(self,item):
    self._item=item
    self._next=None   #Node的指针部分默认指向None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext

ログイン後にコピー

1.2 SinglelinkedList的实现

class SingleLinkedList(): 
  def __init__(self):
    self._head=None  #初始化链表为空表
    self._size=0

ログイン後にコピー

1.3 检测链表是否为空

def isEmpty(self):
  return self._head==None

ログイン後にコピー

1.4 add在链表前端添加元素

def add(self,item):
  temp=Node(item)
  temp.setNext(self._head)
  self._head=temp

ログイン後にコピー

1.5 append在链表尾部添加元素

def append(self,item):
  temp=Node(item)
  if self.isEmpty():
    self._head=temp  #若为空表，将添加的元素设为第一个元素
  else:
    current=self._head
    while current.getNext()!=None:
      current=current.getNext()  #遍历链表
    current.setNext(temp)  #此时current为链表最后的元素

ログイン後にコピー

1.6 search检索元素是否在链表中

def search(self,item):
  current=self._head
  founditem=False
  while current!=None and not founditem:
    if current.getItem()==item:
      founditem=True
    else:
      current=current.getNext()
  return founditem

ログイン後にコピー

1.7 index索引元素在链表中的位置

def index(self,item):
  current=self._head
  count=0
  found=None
  while current!=None and not found:
    count+=1
    if current.getItem()==item:
      found=True
    else:
      current=current.getNext()
  if found:
    return count
  else:
    raise ValueError,'%s is not in linkedlist'%item

ログイン後にコピー

1.8 remove删除链表中的某项元素

def remove(self,item):
  current=self._head
  pre=None
  while current!=None:
    if current.getItem()==item:
      if not pre:
        self._head=current.getNext()
      else:
        pre.setNext(current.getNext())
      break
    else:
      pre=current
      current=current.getNext()

ログイン後にコピー

1.9 insert链表中插入元素

def insert(self,pos,item):
  if pos<=1:
    self.add(item)
  elif pos>self.size():
    self.append(item)
  else:
    temp=Node(item)
    count=1
    pre=None
    current=self._head
    while count<pos:
      count+=1
      pre=current
      current=current.getNext()
    pre.setNext(temp)
    temp.setNext(current)

ログイン後にコピー

全部代码

class Node():
  __slots__=['_item','_next']
  def __init__(self,item):
    self._item=item
    self._next=None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext
     
class SingleLinkedList(): 
  def __init__(self):
    self._head=None #初始化为空链表
  def isEmpty(self):
    return self._head==None
  def size(self):
    current=self._head
    count=0
    while current!=None:
      count+=1
      current=current.getNext()
    return count
  def travel(self):
    current=self._head
    while current!=None:
      print current.getItem()
      current=current.getNext()
  def add(self,item):
    temp=Node(item)
    temp.setNext(self._head)
    self._head=temp
 
  def append(self,item):
    temp=Node(item)
    if self.isEmpty():
      self._head=temp  #若为空表，将添加的元素设为第一个元素
    else:
      current=self._head
      while current.getNext()!=None:
        current=current.getNext()  #遍历链表
      current.setNext(temp)  #此时current为链表最后的元素
  def search(self,item):
    current=self._head
    founditem=False
    while current!=None and not founditem:
      if current.getItem()==item:
        founditem=True
      else:
        current=current.getNext()
    return founditem
  def index(self,item):
    current=self._head
    count=0
    found=None
    while current!=None and not found:
      count+=1
      if current.getItem()==item:
        found=True
      else:
        current=current.getNext()
    if found:
      return count
    else:
      raise ValueError,'%s is not in linkedlist'%item       
  def remove(self,item):
    current=self._head
    pre=None
    while current!=None:
      if current.getItem()==item:
        if not pre:
          self._head=current.getNext()
        else:
          pre.setNext(current.getNext())
        break
      else:
        pre=current
        current=current.getNext()           
  def insert(self,pos,item):
    if pos<=1:
      self.add(item)
    elif pos>self.size():
      self.append(item)
    else:
      temp=Node(item)
      count=1
      pre=None
      current=self._head
      while count<pos:
        count+=1
        pre=current
        current=current.getNext()
      pre.setNext(temp)
      temp.setNext(current)
 
if __name__=='__main__':
  a=SingleLinkedList()
  for i in range(1,10):
    a.append(i)
  print a.size()
  a.travel()
  print a.search(6)
  print a.index(5)
  a.remove(4)
  a.travel()
  a.insert(4,100)
  a.travel()

ログイン後にコピー

このウェブサイトの声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

ホットツール

ホットトピック

Gmailメールのログイン入り口はどこですか？

7450

CakePHP チュートリアル

1374

Steamのアカウント名の形式は何ですか

Win11 Activation Key Permanent

NYTの接続はヒントと回答です

Related knowledge

PSが荷重を見せ続ける理由は何ですか？ Apr 06, 2025 pm 06:39 PM

PSの「読み込み」の問題は、リソースアクセスまたは処理の問題によって引き起こされます。ハードディスクの読み取り速度は遅いか悪いです。CrystaldiskInfoを使用して、ハードディスクの健康を確認し、問題のあるハードディスクを置き換えます。不十分なメモリ：高解像度の画像と複雑な層処理に対するPSのニーズを満たすためのメモリをアップグレードします。グラフィックカードドライバーは時代遅れまたは破損しています：ドライバーを更新して、PSとグラフィックスカードの間の通信を最適化します。ファイルパスが長すぎるか、ファイル名に特殊文字があります。短いパスを使用して特殊文字を避けます。 PS独自の問題：PSインストーラーを再インストールまたは修理します。

PSの負荷速度をスピードアップする方法は？ Apr 06, 2025 pm 06:27 PM

Slow Photoshopの起動の問題を解決するには、次のような多面的なアプローチが必要です。ハードウェアのアップグレード（メモリ、ソリッドステートドライブ、CPU）。時代遅れまたは互換性のないプラグインのアンインストール。システムのゴミと過剰な背景プログラムを定期的にクリーンアップします。無関係なプログラムを慎重に閉鎖する。起動中に多数のファイルを開くことを避けます。

PSが開始されたときにロードの問題を解決する方法は？ Apr 06, 2025 pm 06:36 PM

ブートがさまざまな理由によって引き起こされる可能性がある場合、「読み込み」に巻き込まれたPS：腐敗したプラグインまたは競合するプラグインを無効にします。破損した構成ファイルの削除または名前変更。不十分なプログラムを閉じたり、メモリをアップグレードしたりして、メモリが不十分であることを避けます。ソリッドステートドライブにアップグレードして、ハードドライブの読み取りをスピードアップします。 PSを再インストールして、破損したシステムファイルまたはインストールパッケージの問題を修復します。エラーログ分析の起動プロセス中にエラー情報を表示します。

HTML次ページ関数 Apr 06, 2025 am 11:45 AM

<p>次のページ関数は、HTMLを介して作成できます。手順には、コンテナ要素の作成、コンテンツの分割、ナビゲーションリンクの追加、他のページの隠し、スクリプトの追加が含まれます。この機能により、ユーザーはセグメント化されたコンテンツを閲覧でき、一度に1つのページのみを表示し、大量のデータやコンテンツを表示するのに適しています。 </p>

遅いPSの読み込みはコンピューター構成に関連していますか？ Apr 06, 2025 pm 06:24 PM

PSの負荷が遅い理由は、ハードウェア（CPU、メモリ、ハードディスク、グラフィックスカード）とソフトウェア（システム、バックグラウンドプログラム）の影響を組み合わせたものです。ソリューションには、ハードウェアのアップグレード（特にソリッドステートドライブの交換）、ソフトウェアの最適化（システムガベージのクリーンアップ、ドライバーの更新、PS設定のチェック）、およびPSファイルの処理が含まれます。定期的なコンピューターのメンテナンスは、PSのランニング速度を改善するのにも役立ちます。

PSがファイルを開いたときにロードの問題を解決する方法は？ Apr 06, 2025 pm 06:33 PM

「ロード」は、PSでファイルを開くときに発生します。理由には、ファイルが大きすぎるか破損しているか、メモリが不十分で、ハードディスクの速度が遅い、グラフィックカードドライバーの問題、PSバージョンまたはプラグインの競合が含まれます。ソリューションは、ファイルのサイズと整合性を確認し、メモリの増加、ハードディスクのアップグレード、グラフィックカードドライバーの更新、不審なプラグインをアンインストールまたは無効にし、PSを再インストールします。この問題は、PSパフォーマンス設定を徐々にチェックして使用し、優れたファイル管理習慣を開発することにより、効果的に解決できます。

PSが常にロードされていることを常に示しているときに、ロードの問題を解決する方法は？ Apr 06, 2025 pm 06:30 PM

PSカードは「ロード」ですか？ソリューションには、コンピューターの構成（メモリ、ハードディスク、プロセッサ）の確認、ハードディスクの断片化のクリーニング、グラフィックカードドライバーの更新、PS設定の調整、PSの再インストール、優れたプログラミング習慣の開発が含まれます。

H5ページの制作と従来のWebページの違いは何ですか Apr 06, 2025 am 07:03 AM

従来のWebページでのH5ページの重要な違いは、モバイルの優先順位と柔軟性であり、モバイルデバイスにより適しており、開発効率が高まり、クロスプラットフォームの互換性が向上しています。具体的には、H5ページでは、セマンティックタグ、マルチメディアサポート、オフラインストレージ、地理的位置などの新機能を紹介し、モバイルエクスペリエンスを向上させます。

See all articles

浅谈Python单向链表的实现

ホットAIツール

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

人気の記事

ホットツール

メモ帳++7.3.1

SublimeText3 中国語版

ゼンドスタジオ 13.0.1

ドリームウィーバー CS6

SublimeText3 Mac版

ホットトピック