データ構造とアルゴリズム--(チェーンテーブル、スタック、キュー)
66933 ワード
データ構造とアルゴリズム–(チェーンテーブル、スタック、キュー)
文書ディレクトリデータ構造とアルゴリズム--(チェーンテーブル、スタック、キュー) チェーンテーブル 定義 一方向チェーンテーブル 機能: 1.ヘッダ追加要素 2.末尾追加要素 3.指定位置追加要素 4.削除ノード 5.ノードが存在するかどうかを確認する 6.チェーンテーブルが空かどうかを判断する 7.現在のチェーンテーブルの長さ 8.チェーンテーブル を巡回する全コード貼付
双方向チェーンテーブル 機能: 1.ヘッダ追加要素 2.末尾追加要素 3.指定位置追加要素 4.削除ノード 5.ノードが存在するかどうかを確認する 6.チェーンテーブルが空かどうかを判断する 7.現在のチェーンテーブルの長さ 8.チェーンテーブル を巡回する全コード貼付
スタック スタックの実装 キュー キューの実装
チェーンテーブル
定義＃テイギ＃
チェーンテーブル:一般的なデータ構造であり、線形テーブルです.シーケンステーブルのようにデータを連続的に格納するのではなく,各ノード(データ記憶手段)に次のノードの位置情報(アドレス)を格納する.
たんほうこうチェーンテーブル
一方向チェーンテーブルは、単一チェーンテーブルとも呼ばれ、チェーンテーブルの中で最も簡単な形式であり、各ノードは2つのドメイン、1つの情報ドメイン(メタドメイン)、および1つのリンクドメインを含む.このリンクはチェーンテーブルの次のノードを指し、最後のノードのリンクドメインは空の値を指します.
機能:
1.ヘッダに要素を追加
2.末尾に要素を追加
3.指定された場所に要素を追加
4.ノードの削除
5.ノードが存在するかどうかを検索
6.チェーンテーブルが空かどうかを判断する
7.現在のチェーンテーブルの長さ
8.チェーンテーブルを巡る
すべてのコードを貼り付け
にほうこうチェーンテーブル
各ノードには2つのリンクがあります.1つは前のノードを指します(このノードが最初のノードの場合、空の値を指します).別のノードは次のノードを指します(このノードが最後のノードの場合、空の値を指します).
機能:
1.ヘッダに要素を追加
2.末尾に要素を追加
3.指定された場所に要素を追加
4.ノードの削除
5.ノードが存在するかどうかを検索
6.チェーンテーブルが空かどうかを判断する
7.現在のチェーンテーブルの長さ
8.チェーンテーブルを巡る
すべてのコードを貼り付け
スタック
データを格納したり、要素にアクセスしたり、要素を削除したりするコンテナです(LIFO)
特徴:容器の一端に要素と出力要素を加えるだけで、いつでもアクセス、削除できる要素がこれまで最後に保存された要素であることを保証します.
スタックの実装
キュー(queue)
一方の端でのみ挿入操作を許可し、他方の端では削除操作を行うリニアテーブル.(FIFO).挿入を許可する一端はキューの末尾であり、削除を許可する一端は対頭である.
キューの実装
文書ディレクトリ
チェーンテーブル
定義＃テイギ＃
チェーンテーブル:一般的なデータ構造であり、線形テーブルです.シーケンステーブルのようにデータを連続的に格納するのではなく,各ノード(データ記憶手段)に次のノードの位置情報(アドレス)を格納する.
たんほうこうチェーンテーブル
一方向チェーンテーブルは、単一チェーンテーブルとも呼ばれ、チェーンテーブルの中で最も簡単な形式であり、各ノードは2つのドメイン、1つの情報ドメイン(メタドメイン)、および1つのリンクドメインを含む.このリンクはチェーンテーブルの次のノードを指し、最後のノードのリンクドメインは空の値を指します.
機能:
1.ヘッダに要素を追加
def add(self,item):
node = Node(item)
# next
node.next=self.__head
# __head
self.__head = node
2.末尾に要素を追加
#
def append(self,item):
node = Node(item)
curNode = self.__head
#
if self.is_empty():
self.__head = node
else:
while curNode.next !=None:
curNode = curNode.next
curNode.next = node
3.指定された場所に要素を追加
#
def insert(self,post,item):
# post 0，
if (post-1)<=0:
self.add(item)
# post ，
elif post>=self.length():
self.append(item)
#
else:
count = 0
preNode = self.__head
node = Node(item)
while count<(post-1):
count += 1
preNode = preNode.next
node.next=preNode.next
preNode.next = node
4.ノードの削除
#
def remove(self,item):
curNode = self.__head
preNode = None
while curNode!=None:
#
if curNode.elem == item:
if preNode == None:
self.__head = curNode.next
else:
preNode.next = curNode.next
break
else:
preNode = curNode
curNode = curNode.next
5.ノードが存在するかどうかを検索
#
def search(self,item):
curNode = self.__head
while curNode != None:
if curNode.elem==item:
return True
curNode = curNode.next
return False
6.チェーンテーブルが空かどうかを判断する
#
def is_empty(self):
return self.__head == None
7.現在のチェーンテーブルの長さ
#
def length(self):
count = 0
curNode = self.__head
while curNode != None:
count += 1
curNode = curNode.next
return count
8.チェーンテーブルを巡る
#
def travel(self):
curNode = self.__head
while curNode != None:
print(curNode.elem,end='\t')
curNode = curNode.next
すべてのコードを貼り付け
class Node(object):
def __init__(self,elem):
#elem：
self.elem=elem
#next：
self.next=None
#
class SingleLinkList:
#
def __init__(self,node=None):
if node!=None:
headNode = Node(node)
self.__head=headNode
else:
self.__head=node
# print(self.__head)
#
def add(self,item):
node = Node(item)
# next
node.next=self.__head
# __head
self.__head = node
#
def append(self,item):
node = Node(item)
curNode = self.__head
#
if self.is_empty():
self.__head = node
else:
while curNode.next !=None:
curNode = curNode.next
curNode.next = node
#
def insert(self,post,item):
# post 0，
if (post-1)<=0:
self.add(item)
# post ，
elif post>=self.length():
self.append(item)
#
else:
count = 0
preNode = self.__head
node = Node(item)
while count<(post-1):
count += 1
preNode = preNode.next
node.next=preNode.next
preNode.next = node
#
def remove(self,item):
curNode = self.__head
preNode = None
while curNode!=None:
#
if curNode.elem == item:
if preNode == None:
self.__head = curNode.next
else:
preNode.next = curNode.next
break
else:
preNode = curNode
curNode = curNode.next
#
def search(self,item):
curNode = self.__head
while curNode != None:
if curNode.elem==item:
return True
curNode = curNode.next
return False
#
def is_empty(self):
return self.__head == None
#
def length(self):
count = 0
curNode = self.__head
while curNode != None:
count += 1
curNode = curNode.next
return count
#
def travel(self):
curNode = self.__head
while curNode != None:
print(curNode.elem,end='\t')
curNode = curNode.next
if __name__ == '__main__':
singleLinkList=SingleLinkList()
# print(' ：',singleLinkList.length())
# print(' :',singleLinkList.is_empty())
# print(' :', end=' ')
# singleLinkList.travel()
# print(' :', singleLinkList.search(20))
# singleLinkList.add(1)
# singleLinkList.add(2)
# singleLinkList.add(3)
singleLinkList.append(1)
singleLinkList.append(2)
singleLinkList.append(3)
singleLinkList.insert(10,4)
singleLinkList.remove(4)
singleLinkList.remove(1)
print(' :', end=' ')
singleLinkList.travel()
にほうこうチェーンテーブル
各ノードには2つのリンクがあります.1つは前のノードを指します(このノードが最初のノードの場合、空の値を指します).別のノードは次のノードを指します(このノードが最後のノードの場合、空の値を指します).
機能:
1.ヘッダに要素を追加
#
def add(self,item):
node = Node(item)
#
if self.is_empty():
self.__head = node
else:
# next
node.next=self.__head
# __head prev node
self.__head.prev = node
# __head
self.__head = node
2.末尾に要素を追加
#
def append(self,item):
node = Node(item)
curNode = self.__head
#
if self.is_empty():
self.__head = node
else:
while curNode.next !=None:
curNode = curNode.next
curNode.next = node
# node
node.prev = curNode
3.指定された場所に要素を追加
#
def insert(self,post,item):
# post 0，
if (post-1)<=0:
self.add(item)
# post ，
elif post>=self.length():
self.append(item)
#
else:
count = 0
preNode = self.__head
node = Node(item)
while count<(post-1):
count += 1
preNode = preNode.next
node.next=preNode.next
node.prev = preNode
preNode.next.prev = node
preNode.next = node
4.ノードの削除
#
def remove(self,item):
curNode = self.__head
while curNode!=None:
#
if curNode.elem == item:
if curNode == self.__head:
self.__head = curNode.next
#
if curNode.next:
curNode.next.prev = None
else:
curNode.prev.next = curNode.next
if curNode.next:
curNode.next.prev = curNode.prev
break
else:
curNode = curNode.next
5.ノードが存在するかどうかを検索
#
def search(self,item):
curNode = self.__head
while curNode != None:
if curNode.elem==item:
return True
curNode = curNode.next
return False
6.チェーンテーブルが空かどうかを判断する
#
def is_empty(self):
return self.__head == None
7.現在のチェーンテーブルの長さ
#
def length(self):
count = 0
curNode = self.__head
while curNode != None:
count += 1
curNode = curNode.next
return count
8.チェーンテーブルを巡る
#
def travel(self):
curNode = self.__head
while curNode != None:
print(curNode.elem,end='\t')
curNode = curNode.next
すべてのコードを貼り付け
class Node(object):
def __init__(self,elem):
self.elem = elem
self.prev = None
self.next = None
#
class DoubleLinkList:
#
def __init__(self,node=None):
if node!=None:
headNode = Node(node)
self.__head=headNode
else:
self.__head=node
# print(self.__head)
#
def add(self,item):
node = Node(item)
#
if self.is_empty():
self.__head = node
else:
# next
node.next=self.__head
# __head prev node
self.__head.prev = node
# __head
self.__head = node
#
def append(self,item):
node = Node(item)
curNode = self.__head
#
if self.is_empty():
self.__head = node
else:
while curNode.next !=None:
curNode = curNode.next
curNode.next = node
# node
node.prev = curNode
#
def insert(self,post,item):
# post 0，
if (post-1)<=0:
self.add(item)
# post ，
elif post>=self.length():
self.append(item)
#
else:
count = 0
preNode = self.__head
node = Node(item)
while count<(post-1):
count += 1
preNode = preNode.next
node.next=preNode.next
node.prev = preNode
preNode.next.prev = node
preNode.next = node
#
def remove(self,item):
curNode = self.__head
while curNode!=None:
#
if curNode.elem == item:
if curNode == self.__head:
self.__head = curNode.next
#
if curNode.next:
curNode.next.prev = None
else:
curNode.prev.next = curNode.next
if curNode.next:
curNode.next.prev = curNode.prev
break
else:
curNode = curNode.next
#
def search(self,item):
curNode = self.__head
while curNode != None:
if curNode.elem==item:
return True
curNode = curNode.next
return False
#
def is_empty(self):
return self.__head == None
#
def length(self):
count = 0
curNode = self.__head
while curNode != None:
count += 1
curNode = curNode.next
return count
#
def travel(self):
curNode = self.__head
while curNode != None:
print(curNode.elem,end='\t')
curNode = curNode.next
if __name__ == '__main__':
doubleLinkList = DoubleLinkList()
doubleLinkList.add(1)
doubleLinkList.add(12)
doubleLinkList.append(21)
doubleLinkList.append(22)
doubleLinkList.insert(2,2)
doubleLinkList.remove(23)
doubleLinkList.travel()
スタック
データを格納したり、要素にアクセスしたり、要素を削除したりするコンテナです(LIFO)
特徴:容器の一端に要素と出力要素を加えるだけで、いつでもアクセス、削除できる要素がこれまで最後に保存された要素であることを保証します.
スタックの実装
class Stack(object):
def __init__(self):
self.__list = []
#
def push(self,item):
self.__list.append(item)
#
def pop(self):
return self.__list.pop()
#
def peek(self):
return self.__list[len(self.__list)-1]
#
def is_empty(self):
return self.__list == []
#
def size(self):
return len(self.__list)
if __name__ == '__main__':
stack = Stack()
#
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
#
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
キュー(queue)
一方の端でのみ挿入操作を許可し、他方の端では削除操作を行うリニアテーブル.(FIFO).挿入を許可する一端はキューの末尾であり、削除を許可する一端は対頭である.
キューの実装
class Queue(object):
def __init__(self):
self.__list = []
#
def enqueue(self,item):
self.__list.append(item)
# self.__list.insert(0,item)
#
def dequeue(self):
return self.__list.pop(0)
# return self.__list.pop()
#
def is_empty(self):
return self.__list == []
#
def size(self):
return len(self.__list)
if __name__ == '__main__':
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.size())
print(queue.dequeue())
print(queue.size())
print(queue.is_empty())