国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > Python > 正文

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

2020-02-23 00:49:32
字體:
來源:轉載
供稿:網(wǎng)友

本文實例講述了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的內(nèi)建類型list底層是由C數(shù)組實現(xiàn)的,list在功能上更接近C++的vector(因為可以動態(tài)調(diào)整數(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 = newnextclass 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 countif __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()))            
發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 海丰县| 阿尔山市| 南木林县| 惠水县| 仙游县| 沙洋县| 通州市| 南和县| 靖远县| 启东市| 当涂县| 武邑县| 新蔡县| 开原市| 桃江县| 绥阳县| 施甸县| 府谷县| 广南县| 泰州市| 肥西县| 新绛县| 石林| 石景山区| 珠海市| 平湖市| 靖远县| 南皮县| 驻马店市| 辉南县| 神农架林区| 满洲里市| 邮箱| 通化县| 宝清县| 和林格尔县| 托克托县| 扎囊县| 永嘉县| 城口县| 句容市|