程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置： 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Python實現簡單的數據結構

編輯：Python

目錄

      • 單鏈表
      • 單向循環鏈表
      • 雙向鏈表
      • 棧
      • 隊列
      • 冒泡排序
      • 選擇排序
      • 插入排序
      • 希爾排序
      • 快速排序
      • 歸並排序

單鏈表

class SingleNode(object):
"""單個的節點"""
def __init__(self, item):
# item存放數據元素
self.item = item
# next是下一個節點的標識(指針)
self.next = None
class SingleLinkList(object):
"""單鏈表"""
# 空的單鏈表 self.__head = None
# 非空的單鏈表 self.__head = node
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""判斷鏈表是否為空"""
if self.__head == None:
return True
else:
return False
# return self.__head == None
def length(self):
"""鏈表長度"""
# 空鏈表的情況下
# cur游標 指向首節點 用來遍歷
cur = self.__head # None
count = 0
while cur != None:
count += 1
# 將游標後移動一位
cur = cur.next
return count
def travel(self):
"""遍歷整個鏈表"""
cur = self.__head
while cur != None:
# 節點中的數據
print(cur.item, end=' ')
cur = cur.next
print("")
def append(self, item):
"""鏈表尾部添加元素"""
# item 你要具體插入的數據
node = SingleNode(item)
# 考慮空鏈表
if self.is_empty():
self.__head = node
else:
cur = self.__head # None node
# AttributeError: 'NoneType' object has no attribute 'next'
while cur.next != None:
# 找到最後一個節點
cur = cur.next
cur.next = node
def add(self, item):
"""鏈表頭部添加元素"""
# item 你要具體插入的數據
node = SingleNode(item)
# 將新節點的鏈接區next指向頭結點
node.next = self.__head
# 將鏈表的頭指向新節點
self.__head = node
def insert(self, pos, item): # insert(2,100) insert(-1,100) insert(10,100)
"""指定位置添加元素"""
# item 你要具體插入的數據
# 頭部插入
if pos <= 0:
self.add(item)
# 尾部插入
elif pos > self.length()-1:
self.append(item)
else:
# 指定位置插入
node = SingleNode(item)
pre = self.__head
count = 0
while count < (pos - 1):
count += 1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
"""刪除節點"""
# remove(100) [100,200,100] 刪除一個100
cur = self.__head # 空鏈表 None
pre = None
while cur != None:
# 找到了指定的元素
if cur.item == item:
# 刪除第一個元素
if cur == self.__head:
self.__head = cur.next
else:
# 刪除
pre.next = cur.next
break
else:
# 繼續移動
pre = cur
cur = cur.next
def search(self, item):
"""查找節點是否存在"""
cur = self.__head
while cur != None:
if cur.item == item:
return True
else:
# 讓游標繼續執行
cur = cur.next
return False
s = SingleLinkList()
"""測試結果"""
print(s.is_empty()) # 單鏈表是否為空
print(s.length()) # 單鏈表的長度
# 向單鏈表尾部加五個數據
s.append(10)
s.append(23)
s.append(13)
s.append(5)
s.append(34)
print(s.is_empty())
print(s.length())
s.travel() # 遍歷單鏈表
# 向指定位置插入數據
s.insert(-1, 6)
s.insert(10, 77)
s.insert(2, 11)
s.insert(1, 33)
s.travel()
print(s.search(77)) # 查找數據77是否在單鏈表中
s.remove(33) # 刪除數據33
s.travel() # 再次遍歷單鏈表

單向循環鏈表

class Node(object):
"""節點"""
def __init__(self, item):
# item存放數據元素
self.item = item
# next是下一個節點的標識(指針)
self.next = None
class SinCycLinkList(object):
"""單項循環鏈表"""
# 空的單鏈表 self.__head = None
# 非空的單鏈表 node.next = node
def __init__(self, node=None):
self.__head = None
if node:
node.next = node
def is_empty(self):
"""判斷鏈表是否為空"""
if self.__head == None:
return True
else:
return False
def length(self):
"""返回鏈表的長度"""
# 空鏈表的情況下
if self.is_empty():
return 0
# cur游標 指向首節點 用來遍歷
cur = self.__head # None
# is 對象 == 數值是否相等
count = 1
while cur.next != self.__head:
count += 1
# 將游標後移動一位
cur = cur.next
return count
def travel(self):
"""遍歷"""
# 空鏈表
if self.is_empty():
return None
cur = self.__head
while cur.next != self.__head:
# 節點中的數據
print(cur.item, end=' ')
cur = cur.next
# 退出循環的時候,cur指向尾結點,但是尾結點並沒有打印
print(cur.item)
def add(self, item):
"""鏈表頭部添加元素"""
# item 你要具體插入的數據
node = Node(item)
# 空鏈表
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head # None
while cur.next != self.__head:
cur = cur.next
# 找到尾節點
# 添加的節點指向原先的頭節點
node.next = self.__head
# __head指向node
self.__head = node
# 尾結點指向新的節點
cur.next = node
def append(self, item):
"""鏈表尾部添加元素"""
node = Node(item)
# 空鏈表
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# 找到尾節點
# 將尾結點指向node
cur.next = node
# 將node指向__head
node.next = self.__head
def insert(self, pos, item):
"""指定位置添加元素"""
# 頭部插入
if pos <= 0:
self.add(item)
# 尾部插入
elif pos > self.length() - 1:
self.append(item)
else:
# 指定位置插入
node = Node(item)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def search(self, item):
"""查找節點是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.item == item:
return True
else:
# 讓游標繼續執行
cur = cur.next
# 循環退出 cur指向尾節點
if cur.item == item:
return True
return False
def remove(self, item):
"""刪除節點"""
# 空鏈表
if self.is_empty():
return
cur = self.__head
pre = None
# 頭節點的元素就是要刪除的元素
if cur.item == item:
# 鏈表中的節點不止一個
if cur.next != self.__head:
while cur.next != self.__head:
cur = cur.next
# 循環結束 cur 指向尾結點
cur.next = self.__head.next
self.__head = cur.next
else:
self.__head = None
# 第一個節點不是要刪除的
else:
while cur.next != self.__head:
if cur.item == item:
# 刪除
pre.next = cur.next
return
else:
# 游標繼續往下走
pre = cur
cur = cur.next
if cur.item == item:
pre.next = cur.next
s = SinCycLinkList()
"""測試結果"""
print(s.is_empty()) # 判斷是否為空鏈表
print(s.length()) # 判斷鏈表長度
s.add(1) # 在頭部添加數據
s.add(2)
s.add(3)
s.add(4)
s.append(6) # 在尾部添加數據
s.append(8)
s.travel() # 遍歷單向循環鏈表
s.insert(2, 7) # 在指定位置插入數據
s.insert(2, 7)
s.travel() # 遍歷單向循環鏈表
s.remove(6) # 刪除數據
s.remove(7)
s.travel() # 再次遍歷

雙向鏈表

class Node(object):
"""節點"""
def __init__(self, item):
# item存放數據元素
self.item = item
# next是下一個節點的標識
self.next = None
# perv是上一個節點的表示
self.prev = None
class DoubleLinkList(object):
"""雙向鏈表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""判斷鏈表是否為空"""
if self.__head == None:
return True
else:
return False
def length(self):
"""返回鏈表的長度"""
# 空鏈表的情況下
if self.is_empty():
return 0
# cur游標 指向首節點 用來遍歷
cur = self.__head
# is 對象 == 數值是否相等
count = 0
while cur != None:
count += 1
# 將游標後移動一位
cur = cur.next
return count
def travel(self):
"""遍歷"""
# 空鏈表
if self.is_empty():
return None
cur = self.__head
while cur != None:
# 節點中的數據
print(cur.item, end=' ')
cur = cur.next
print("")
# 退出循環的時候,cur指向None
def add(self, item):
"""鏈表頭部添加元素"""
# item 你要具體插入的數據
node = Node(item)
if self.is_empty():
self.__head = node
else:
# 將node的next指向__head的頭節點
node.next = self.__head
# 將__head的頭節點的prev指向node
self.__head.prev = node
# 將__head指向node
self.__head = node
def append(self, item):
"""鏈表尾部添加元素"""
# item 你要具體插入的數據
node = Node(item)
# 考慮空鏈表
if self.is_empty():
self.__head = node
else:
cur = self.__head # None node
while cur.next != None:
# 找到最後一個節點
cur = cur.next
# 循環結束之後,cur指向尾節點
cur.next = node
node.prev = cur
def insert(self, pos, item): # insert(2,100) insert(-1,100) insert(10,100)
"""指定位置添加元素"""
# item 你要具體插入的數據
# 頭部插入
if pos <= 0:
self.add(item)
# 尾部插入
elif pos > self.length()-1:
self.append(item)
else:
# 指定位置插入
node = Node(item)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
# 循環結束,找到插入位置的前一個結點
# 將node的prev指向cur
node.prev =cur
# 將node的next指向cur的下一個結點
node.next = cur.next
# 將cur的下一個結點的prev指向node
cur.next.prev = node
# 將cur的next指向node
cur.next = node
def search(self, item):
"""查找節點是否存在"""
cur = self.__head
while cur != None:
if cur.item == item:
return True
else:
# 讓游標繼續執行
cur = cur.next
return False
def remove(self, item):
"""刪除節點"""
# remove(100) [100,200,100] 刪除一個100
if self.is_empty():
return
else:
cur = self.__head # 空鏈表 None
# 如果首結點的元素就是要刪除的元素
if cur.item == item:
print(1)
# 如果鏈表只有一個結點
if cur.next == None:
self.__head = None
else:
cur.next.prev = None
self.__head = cur.next
return
while cur != None:
if cur.item == item:
print(2)
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break
cur = cur.next
d = DoubleLinkList()
"""測試結果"""
print(d.is_empty())
print(d.length())
d.add(1)
d.add(2)
d.add(3)
d.append(4)
d.append(10)
d.travel()
d.insert(-1, 0)
d.insert(-5, 0)
d.travel()

棧

class Stack(object):
"""用列表的方式來實現棧"""
def __init__(self):
self.__items = []
def is_empty(self):
"""判斷棧是否為空"""
if self.__items == []:
return True
else:
return False
# return self.__items == []
def push(self, item):
"""添加一個新的元素item到棧頂"""
self.__items.append(item)
# self.__items.insert(0, item)
def pop(self):
"""彈出棧頂元素"""
return self.__items.pop()
def peek(self):
"""返回棧頂元素"""
if self.is_empty():
return None
else:
return self.__items[-1]
# return self.__items[len(self.__items)-1]
def size(self):
"""返回棧的元素個數"""
return len(self.__items)
def travel(self):
"""遍歷"""
print(self.__items)
# for item in self.__items:
# print(item)
s = Stack()
"""測試結果"""
print(s.is_empty())
s.push(1)
s.push(2)
s.push(3)
s.pop() # 彈出棧頂item 3
s.travel()
print(s.size())
print(s.is_empty())
print(s.peek()) # 返回棧頂item而不彈出
s.travel()

隊列

class Queue(object):
def __init__(self):
self.__items = []
def enqueue(self, item):
self.__items.append(item)
def dequeue(self):
""" 從隊列頭部刪除一個元素 :return: 隊列頭元素 """
return self.__items.pop(0)
def is_empty(self):
""" 判斷一個隊列是否為空 :return: True or False """
return self.__items == []
def size(self):
return len(self.__items)
def travel(self):
"""遍歷"""
# print(self.__items)
for item in self.__items:
print(item, end=' ')
print('')
q = Queue()
"""測試結果"""
print(q.is_empty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.travel()
q.dequeue() # 隊首item出隊
q.travel() # 再次遍歷

冒泡排序

def bu_sort(lis):
n = len(lis)
for j in range(n-1):
for i in range(0, n-1-j):
if lis[i] > lis[i + 1]:
lis[i], lis[i + 1] = lis[i + 1], lis[i]

選擇排序

""" 首先在未排序列中找到最小元素 放到已排序列的起始位置 然後從未排序列中繼續尋找最小元素 添加到已排序列的末尾 以此類推，直到所有元素均排序完畢。 """
def selection_sort(lis):
n = len(lis)
for i in range(n-1):
# 記錄最小值的位置
min_index = i
# 從min_index 位置到末尾找到最小值 找最小值的下標
for j in range(min_index, n):
if lis[j] < lis[min_index]: # lis[1] < lis[0] 26 < 54 min_index = 1
min_index = j
lis[i], lis[min_index] = lis[min_index], lis[i]

插入排序

""" 首先將數組中的數據分為兩個區間 已排序區間和未排序區間 初始已排序區間只有一個元素 就是數組的第一個元素 插入排序的核心思想是取未排序區間中的元素 在已排序區間中找到合適的插入位置將其插入 並保證已排序區間數據一直有序 重復這個過程，直到未排序區間中元素為空，算法結束 """
def insert_sort(lis):
n = len(lis)
# 從第二個位置,即下標為1的開始向前插入
for i in range(1, n):
# 從第i個元素 向前比較 如果小於前一個元素 交換
for j in range(i, 0, -1):
if lis[j] < lis[j - 1]:
lis[j], lis[j - 1] = lis[j - 1], lis[j]

希爾排序

def shell_sort(lis):
n = len(lis)
gap = n//2 # python2 python3 存在區別
while gap > 0:
for i in range(gap, n):
while i >= gap and lis[i-gap] > lis[i]:
lis[i-gap], lis[i] = lis[i], lis[i-gap]
i -= gap
gap = gap//2

快速排序

def quick_sort(lis, start, end):
if start >= end:
return
mid = lis[start]
low = start
high = end
# 循環退出 low = high
while low < high:
while low < high and lis[high] >= mid:
high -= 1
lis[low] = lis[high]
while low < high and lis[low] < mid:
low += 1
lis[high] = lis[low]
lis[low] = mid
quick_sort(lis, start, low-1)
quick_sort(lis, low+1, end)
lis = [9, 21, 43, 27, 67, 31, 49, 55, 20]
quick_sort(lis, 0, len(lis)-1)

歸並排序

""" 將數組分解最小之後合並兩個有序數組 基本思路是比較兩個數組的最前面的數 誰小就先取誰，取了後相應的指針就往後移一位 然後再比較，直至一個數組為空，最後把另一個數組的剩余部分復制過來即可。 """
def merge_sort(lis):
if len(lis) <= 1:
return lis
# 二分分解
mid_index = len(lis) // 2
left_lis = merge_sort(lis[:mid_index])
right_lis = merge_sort(lis[mid_index:])
l_index = 0
r_index = 0
result = []
while l_index < len(left_lis) and r_index < len(right_lis):
if left_lis[l_index] < right_lis[r_index]:
result.append(left_lis[l_index])
l_index += 1
else:
result.append(right_lis[r_index])
r_index += 1
result += left_lis[l_index:]
result += right_lis[r_index:]
return result # 返回排完序的列表
lis = [14, 26, 63, 17, 77, 31, 44, 55, 20]
s = merge_sort(lis)

  1. 上一篇文章：
  2. 下一篇文章：
Python
【Python】詳解Python列表推導式|迭代器|生成器|匿名函數

詳解python3匿名函數、推導式、迭代器和生成器用法。1、
Detailed explanation of Python TCP concurrent programming and code implementation - Taking the chat room implemented by Bio & NiO & AIO model as an example

Python TCP Concurrent programm
python之函數的返回值

博主簡介：原互聯網大廠tencent員工，網安巨頭Venus
Golden three silver four attack, carefully collated this set of Python number tutorial, limited time free download

The Spring Festival at home ,

Python3.7 machine learning -day2

Source code (https://github.co
python classic font warning: RuntimeWarning: Glyph 33337 missing from current font.font.set_text(s, 0, flags=flag

I. Error analysisRunning YOLOv
相關文章
    没有相关文章
閱讀排行榜
A collection of 40 Python interview questions sorted out by staying up late and working overtime for half a month (with answers) VS code 遠程調試 python 代碼無法識別相對路徑解決方案 How to realize batch processing of Python images Introduction to Python penetration testing: burpsuite generates passwords based on Web page content Django logs in with a picture verification code and an email or mobile number Python full stack series 179 single host uses docker to build Mongo split cluster 2 Python數字人民幣程序設計未解析的引用 Pandas數據顯示不全？快來了解這些設置技巧！ Python openpyxl excel Library Python語言入門-數值，字符串，類型 Palindrome linked list Python
熱門圖文
安裝Exchange 2013後AD中有什麼變化 php的curl獲取有301/302跳轉文件出錯問題解決 PHP使用數組實現隊列 技巧/訣竅：用.NET 3.5創建ToJSON()擴展方法 C#中只接受數字輸入的控件(4) 若何應用NetworkInterface獲得辦事器MAC地址 c語言-新手的簡單問題，謝謝 基於JSP實現數據庫中圖片的存儲與顯示
欄目導航
  • 匯編語言
    •   
  • Delphi
    •   
  • Groovy
    •   
  • WebSphere
    •   
  • Rational
    •   
  • Python
    •   
  • Ruby
    •   
  • 編程解疑
    •   
  • 編程綜合問答
    •   
  • 更多關於編程
    •   
  • 編程問題解答
    • Copyright © 程式師世界 All Rights Reserved