日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
Python數(shù)據(jù)結(jié)構(gòu)之單鏈表

本文轉(zhuǎn)載自微信公眾號(hào)「python與大數(shù)據(jù)分析」，作者一只小小鳥(niǎo)鳥(niǎo)。轉(zhuǎn)載本文請(qǐng)聯(lián)系python與大數(shù)據(jù)分析公眾號(hào)。

創(chuàng)新互聯(lián)建站主要從事成都做網(wǎng)站、成都網(wǎng)站建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)石城,10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108

今天終于把大學(xué)都沒(méi)想明白的鏈表數(shù)據(jù)結(jié)構(gòu)整明白了，也算小小的收獲，挺好玩的。文后附鏈表操作示意圖。

單向鏈表(單鏈表)是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)信息域(元素域)和一個(gè)鏈接域。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值。

  • isempty(self) 鏈表是否為空
  • length(self) 鏈表長(zhǎng)度
  • travel(self) 遍歷整個(gè)鏈表
  • add(self,item) 鏈表頭部添加元素
  • append(self,item) 鏈表尾部添加元素
  • insert(self,item,index) 指定位置添加元素
  • deletebyitem(self,item) 根據(jù)數(shù)據(jù)項(xiàng)刪除節(jié)點(diǎn)
  • deletebyindex(self,index) 根據(jù)索引位置刪除節(jié)點(diǎn)
  • search(self,item) 根據(jù)數(shù)據(jù)項(xiàng)查找節(jié)點(diǎn)是否存在
  • update(self,index,item) 暫無(wú)實(shí)現(xiàn)
  • getitem(self,index) 獲取索引位置對(duì)應(yīng)的數(shù)據(jù)項(xiàng)
  • getindex(self,item) 獲取數(shù)據(jù)項(xiàng)對(duì)應(yīng)的索引位置

代碼基本為原創(chuàng)，經(jīng)過(guò)大量重寫(xiě)

 
 
 
 
      
  
  
  
  1. class Node(object): 
    2.   
  
  
  
  2.     def __init__(self, item): 
    3.   
  
  
  
  3.         self.item = item 
    4.   
  
  
  
  4.         self.next = None 
    5.   
  
  
  
  5.     def __repr__(self): 
    6.   
  
  
  
  6.         pass 
    7.   
  
  
  
  7.     def __str__(self): 
    8.   
  
  
  
  8.         return str(self.item) 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10. class SingleLinkList(object): 
    11.   
  
  
  
  11.     def __init__(self): 
    12.   
  
  
  
  12.         self.header = None 
    13.   
  
  
  
  13.         self.currentnum=0 
    14.   
  
  
  
  14.  
    15.   
  
  
  
  15.     def isempty(self): 
    16.   
  
  
  
  16.         return self.header == None 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18.     def length(self): 
    19.   
  
  
  
  19.         return self.currentnum 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21.     def travel(self): 
    22.   
  
  
  
  22.         cur =self.header 
    23.   
  
  
  
  23.         while cur !=None: 
    24.   
  
  
  
  24.             print("{}".format(cur.item),end=" ") 
    25.   
  
  
  
  25.             cur=cur.next 
    26.   
  
  
  
  26.         print("\r") 
    27.   
  
  
  
  27.  
    28.   
  
  
  
  28.     def add(self,item): 
    29.   
  
  
  
  29.         node=Node(item) 
    30.   
  
  
  
  30.         # 新節(jié)點(diǎn)的鏈接指向頭節(jié)點(diǎn) 
    31.   
  
  
  
  31.         node.next=self.header 
    32.   
  
  
  
  32.         # 鏈表的頭指向新節(jié)點(diǎn) 
    33.   
  
  
  
  33.         self.header=node 
    34.   
  
  
  
  34.         self.currentnum+=1 
    35.   
  
  
  
  35.  
    36.   
  
  
  
  36.     def append(self,item): 
    37.   
  
  
  
  37.         tempnode=self.header 
    38.   
  
  
  
  38.         node=Node(item) 
    39.   
  
  
  
  39.         if self.isempty(): 
    40.   
  
  
  
  40.             self.add(node) 
    41.   
  
  
  
  41.         else: 
    42.   
  
  
  
  42.             while tempnode.next!=None: 
    43.   
  
  
  
  43.                 tempnode=tempnode.next 
    44.   
  
  
  
  44.             tempnode.next=node 
    45.   
  
  
  
  45.             self.currentnum+=1 
    46.   
  
  
  
  46.  
    47.   
  
  
  
  47.     def insert(self,item,index): 
    48.   
  
  
  
  48.         node=Node(item) 
    49.   
  
  
  
  49.         tempnode=self.header 
    50.   
  
  
  
  50.         if index>self.currentnum+1 or index<=0: 
    51.   
  
  
  
  51.             raise IndexError("{} is not find in Linklist".format(index)) 
    52.   
  
  
  
  52.         # 指定位置為第一個(gè)即在頭部插入 
    53.   
  
  
  
  53.         if index==1: 
    54.   
  
  
  
  54.             self.add(node) 
    55.   
  
  
  
  55.         elif index>self.currentnum-1: 
    56.   
  
  
  
  56.             self.append(node) 
    57.   
  
  
  
  57.         else: 
    58.   
  
  
  
  58.             for i in range(1,index-1): 
    59.   
  
  
  
  59.                 tempnode=tempnode.next 
    60.   
  
  
  
  60.             node.next=tempnode.next 
    61.   
  
  
  
  61.             tempnode.next=node 
    62.   
  
  
  
  62.             self.currentnum+=1 
    63.   
  
  
  
  63.  
    64.   
  
  
  
  64.     def deletebyitem(self,item): 
    65.   
  
  
  
  65.         tempnode=self.header 
    66.   
  
  
  
  66.         prenode=None 
    67.   
  
  
  
  67.         while tempnode!=None: 
    68.   
  
  
  
  68.             if tempnode.item==item: 
    69.   
  
  
  
  69.                 if tempnode==self.header: 
    70.   
  
  
  
  70.                     self.header=tempnode.next 
    71.   
  
  
  
  71.                 else: 
    72.   
  
  
  
  72.                     prenode.next=tempnode.next 
    73.   
  
  
  
  73.                 break 
    74.   
  
  
  
  74.             else: 
    75.   
  
  
  
  75.                 prenode=tempnode 
    76.   
  
  
  
  76.                 tempnode=tempnode.next 
    77.   
  
  
  
  77.  
    78.   
  
  
  
  78.  
    79.   
  
  
  
  79.     def deletebyindex(self,index): 
    80.   
  
  
  
  80.  
    81.   
  
  
  
  81.         if index>self.currentnum or index<=0: 
    82.   
  
  
  
  82.             raise IndexError("{} is not find in Linklist".format(index)) 
    83.   
  
  
  
  83.  
    84.   
  
  
  
  84.         i=1 
    85.   
  
  
  
  85.         tempnode=self.header 
    86.   
  
  
  
  86.         prenode=self.header 
    87.   
  
  
  
  87.  
    88.   
  
  
  
  88.         if index==1: 
    89.   
  
  
  
  89.             self.header = tempnode.next 
    90.   
  
  
  
  90.             self.currentnum-=1 
    91.   
  
  
  
  91.             return 
    92.   
  
  
  
  92.  
    93.   
  
  
  
  93.         while tempnode.next and i  
  
  
  
  94.             prenode = tempnode 
    95.   
  
  
  
  95.             tempnode = tempnode.next 
    96.   
  
  
  
  96.             i+=1 
    97.   
  
  
  
  97.  
    98.   
  
  
  
  98.         if i==index: 
    99.   
  
  
  
  99.             prenode.next=tempnode.next 
    100.   
  
  
  
  100.             self.currentnum-=1 
    101.   
  
  
  
  101.  
    102.   
  
  
  
  102.  
    103.   
  
  
  
  103.     def search(self,item): 
    104.   
  
  
  
  104.         tempnode=self.header 
    105.   
  
  
  
  105.         while tempnode!=None: 
    106.   
  
  
  
  106.             if tempnode.item==item: 
    107.   
  
  
  
  107.                 return True 
    108.   
  
  
  
  108.             else: 
    109.   
  
  
  
  109.                 tempnode=tempnode.next 
    110.   
  
  
  
  110.         return False 
    111.   
  
  
  
  111.  
    112.   
  
  
  
  112.     def update(self,index,item): 
    113.   
  
  
  
  113.         pass 
    114.   
  
  
  
  114.  
    115.   
  
  
  
  115.     def getitem(self,index): 
    116.   
  
  
  
  116.         if index<=0 or index>self.currentnum: 
    117.   
  
  
  
  117.             raise IndexError("{} is not find in Linklist".format(index)) 
    118.   
  
  
  
  118.         tempnode=self.header 
    119.   
  
  
  
  119.         i=1 
    120.   
  
  
  
  120.         while i  
  
  
  
  121.             tempnode=tempnode.next 
    122.   
  
  
  
  122.             i+=1 
    123.   
  
  
  
  123.         return tempnode.item 
    124.   
  
  
  
  124.  
    125.   
  
  
  
  125.     def getindex(self,item): 
    126.   
  
  
  
  126.         tempnode = self.header 
    127.   
  
  
  
  127.         i=0 
    128.   
  
  
  
  128.         flag=False 
    129.   
  
  
  
  129.         while tempnode != None: 
    130.   
  
  
  
  130.             i+=1 
    131.   
  
  
  
  131.             if tempnode.item == item: 
    132.   
  
  
  
  132.                 flag=True 
    133.   
  
  
  
  133.                 return i 
    134.   
  
  
  
  134.             else: 
    135.   
  
  
  
  135.                 tempnode = tempnode.next 
    136.   
  
  
  
  136.         if flag==False: 
    137.   
  
  
  
  137.             return 0 
    138.   
  
  
  
  138.  
    139.   
  
  
  
  139. if __name__ == '__main__': 
    140.   
  
  
  
  140.     a = SingleLinkList() 
    141.   
  
  
  
  141.     a.add(1)  # 1 
    142.   
  
  
  
  142.     print('a.add(1)') 
    143.   
  
  
  
  143.     a.travel() 
    144.   
  
  
  
  144.     a.add(2)  # 2 1 
    145.   
  
  
  
  145.     print('a.add(2)') 
    146.   
  
  
  
  146.     a.travel() 
    147.   
  
  
  
  147.     a.append(3)  # 2 1 3 
    148.   
  
  
  
  148.     print('a.append(3)') 
    149.   
  
  
  
  149.     a.travel() 
    150.   
  
  
  
  150.     a.insert(4, 2)  # 2 1 4 3 
    151.   
  
  
  
  151.     print('a.insert(2, 4)') 
    152.   
  
  
  
  152.     a.travel() 
    153.   
  
  
  
  153.     print('a.search(1)=',a.search(1)) 
    154.   
  
  
  
  154.     print('a.search(5)=', a.search(5)) 
    155.   
  
  
  
  155.     print('a.getindex(1)=',a.getindex(1)) 
    156.   
  
  
  
  156.     print('a.getindex(5)=', a.getindex(5)) 
    157.   
  
  
  
  157.     print('a.getitem(2)=', a.getitem(2)) 
    158.   
  
  
  
  158.     print('a.getitem(4)=', a.getitem(4)) 
    159.   
  
  
  
  159.     print('a.getitem(3)=', a.getitem(3)) 
    160.   
  
  
  
  160.     # a.deletebyitem(5) 
    161.   
  
  
  
  161.     # print('a.deletebyitem(5)') 
    162.   
  
  
  
  162.     # a.travel() 
    163.   
  
  
  
  163.     # a.deletebyitem(4) 
    164.   
  
  
  
  164.     # print('a.deletebyitem(4)') 
    165.   
  
  
  
  165.     # a.travel() 
    166.   
  
  
  
  166.     # a.deletebyitem(2) 
    167.   
  
  
  
  167.     # print('a.deletebyitem(2)') 
    168.   
  
  
  
  168.     # a.travel() 
    169.   
  
  
  
  169.     a.deletebyindex(4) 
    170.   
  
  
  
  170.     print('a.deletebyindex(4)') 
    171.   
  
  
  
  171.     a.travel() 
    172.   
  
  
  
  172.     a.deletebyindex(2) 
    173.   
  
  
  
  173.     print('a.deletebyindex(2)') 
    174.   
  
  
  
  174.     a.travel() 
    175.   
  
  
  
  175.     a.deletebyindex(1) 
    176.   
  
  
  
  176.     print('a.deletebyindex(1)') 
    177.   
  
  
  
  177.     a.travel() 
    178.

結(jié)果如下

 
 
 
 
      
  
  
  
  1. C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/linklist.py 
    2.   
  
  
  
  2. a.add(1) 
    3.   
  
  
  
  3. 1  
    4.   
  
  
  
  4. a.add(2) 
    5.   
  
  
  
  5. 2 1  
    6.   
  
  
  
  6. a.append(3) 
    7.   
  
  
  
  7. 2 1 3  
    8.   
  
  
  
  8. a.insert(2, 4) 
    9.   
  
  
  
  9. 2 4 1 3  
    10.   
  
  
  
  10. a.search(1)= True 
    11.   
  
  
  
  11. a.search(5)= False 
    12.   
  
  
  
  12. a.getindex(1)= 3 
    13.   
  
  
  
  13. a.getindex(5)= 0 
    14.   
  
  
  
  14. a.getitem(2)= 4 
    15.   
  
  
  
  15. a.getitem(4)= 3 
    16.   
  
  
  
  16. a.getitem(3)= 1 
    17.   
  
  
  
  17. a.deletebyindex(4) 
    18.   
  
  
  
  18. 2 4 1  
    19.   
  
  
  
  19. a.deletebyindex(2) 
    20.   
  
  
  
  20. 2 1  
    21.   
  
  
  
  21. a.deletebyindex(1) 
    22.   
  
  
  
  22. 1  
    23.   
  
  
  
  23.  
    24.   
  
  
  
  24. Process finished with exit code 0 
    25.

鏈表頭部增加節(jié)點(diǎn)示意圖

從鏈表尾部增加節(jié)點(diǎn)示意圖


當(dāng)前標(biāo)題：Python數(shù)據(jù)結(jié)構(gòu)之單鏈表
文章鏈接：http://www.5511xx.com/article/dppiejo.html