Pythonによるデータ構造とアルゴリズム入門



データ構造
データ構造は、格納されたデータ上の操作をより効率的に行うことができるような方法でコンピュータにデータを整理して格納する特殊な手段である

アルゴリズム
有限量の労力を持つ有限時間の問題を解くための段階的手順である.
効率的なアルゴリズムは何ですか?関数の値が小さい方、または入力のサイズの成長に比べてゆっくりと成長します.

データ構造の種類
Pythonはデータ構造を暗黙のうちにサポートしており、データの格納とアクセスを可能にします.これらの構造体をリスト、辞書、集合、タプルと呼ぶ
Pythonはまた、ユーザーが独自のデータ構造を作成し、その機能を完全に制御することができます.最も顕著なデータ構造は
スタック、キュー、ツリー、リンクリスト、グラフ**および*ハッシュテーブル.

1 .リスト
整数位置でインデックス付けされた項目のシーケンスを表すには、1つのデータ構造を使用できます.リストには、0個以上の要素が含まれ、異なる型の要素を含めることができます.リストは、柔軟な方法で要素を追加、削除、または変更することができる要素のmutableな意味の順序変更順序です
アクセスリスト項目
リスト要素は、割り当てられたインデックスによってアクセスされます.リストの開始インデックスは0であり、終了インデックスはn - 1で、nは要素数です.
学生[ 0 ]はリストの最初の要素を得る
Count学生[ 0 ] = ' amina 'はリスト項目をオフセットで変更します.
学生[ 0 : 2 ]は、オフセットで項目を抽出するためにスライスをスライスします.この例は、学生の最初の2つの要素を返します.
リスト項目を追加します
を指定します.
あるいは、1つのリストを別のリストに組み込む.
insert ()は、オフセットの前に項目を追加します.
リスト項目を削除する
remove ()は、リストから項目の値を削除します.
pop ()は、最後の(または指定した)要素を削除します.
delリストの位置によって項目を削除します.delはPython文で、リストメソッドではありません.
結合されたリスト項目の文字列を返します.join ()の引数は文字列あるいはiterableシーケンスの文字列です.
cy len ()は、リストの項目数/長さを返します.
radius count ()は指定した値の出現数を返します.
#defining  a list 
students = ['sam', 'pam', 'rocky', 'austin', 'steve', 'banner']
#acessing element in a list 
print(students[0])
print(students[-3])
print(students[1:3])

#adding element in a list 
students.append("amina")
print(students)

#deleting element in a list
students.pop(0)
print(students)

#printing the len of the list 
print(len(students))

#join string in a list
name = "-".join(["Jack", "O", "Lantern"])
print(name)

output:
sam
austin
['pam', 'rocky']
['sam', 'pam', 'rocky', 'austin', 'steve', 'banner', 'amina']
['pam', 'rocky', 'austin', 'steve', 'banner', 'amina']
6
Jack-O-Lantern

2辞書
オフセットを使用する代わりに、辞書は各値に関連付けるキーを使用します.これは、順序が追跡されず、辞書を使用する場合は問題ではないことを意味します.辞書キーは不変でユニークですが、辞書は変更可能ですキー値の要素を追加、削除、または変更することができます
を使用して辞書を作成します.dict ()を使用したtypecast
辞書のアクセス値
book [' key ']キーで項目を取得する
*辞書で値を更新する*.
book [' key ']=' value 'はキーを付加します(あるいは存在している場合は変更します).
num update ()は、1つの辞書のキーと値をマージします.
*辞書の値を削除する
del指定したキーで項目を削除します.delはPython文で、辞書メソッドではありません.
keys ()はすべての辞書キーを返します.values ()は、辞書内のすべての値を返します.すべての辞書キー値の組を返します.
# dictionaries help us store complicated data, which is not single valued like a number or a string
book = {
    'title': "How to be awesome",
    'author': "john doe",
    'isbn': "1234-23-15-12-3",
    'date_published': "23-21-2010",
    'year': 2010}
# access value in a dict
book_title = book['title']
print(book_title)
# update value in a dict
book['title'] = "2020 what went wrong"
print(book["title"])
# get all the keys in this dictionary
keys = book.keys()
print(keys)

#deleting item from dictionary 
del book['isbn']
print (book)

#adding item to dictonary 
book['page']=450
print(book)

#Checking if a Key exists
if "year" in book:
  print("Yes, the keyword exists in the dictionary")
else:
  print('No, the keyword does not exist in the dictionary')

output
How to be awesome
2020 what went wrong
dict_keys(['title', 'author', 'isbn', 'date_published', 'year'])
{'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010}
{'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010, 'page': 450}
Yes, the keyword exists in the dictionary

3つのタプル
タプルはまた、リストのような順序付けられたデータ構造です.しかし、タプルは不変ですタプルが作成された後に項目を追加、削除、または変更できません.タプルは、定義された後に変更することができないので、多くのより少ない関数を持つことによってリストから異なります.タプルには、0以上の要素が含まれ、異なる、不変の型の要素を含めることができます
を使用してタプルを作成します.tuple ()を使用したtypecast
タプル内の要素へのアクセス
タプル内の項目へのアクセスは、リストに似ており、インデックスを使用してタプル内の要素にアクセスできます.インデックス値を指定でき、特定のインデックス値に格納されている項目を返します.
二つのタプルを連結する
vector = (4, 5, 9)
#acessing element in  a tuple
print("x-coordinate:", vector[0])
print("y-coordinate:", vector[1])
print("z-coordinate:", vector[2])

location = 108.7774, 92.5556
latitude, longtitude = location
print("The coordinates are {} x {}".format(latitude, longtitude))

output:
x-coordinate: 4
y-coordinate: 5
z-coordinate: 9
The coordinates are 108.7774 x 92.5556

4 .集合
セットは、値だけでなく、キーだけの辞書のようです.これは、集合が一意であり、連続的でないことを意味します.セットも変更可能です.setは0個以上の要素を含み、異なる、不変の型の要素を含むことができます.set ()を使用してsetを作成します.set ()を使用したtypecast
リストで行う操作
add ()は、設定されていない場合に
remove ()は、指定した項目を
interset ()は2つの組の交点を返す
union ()は2組の集合を返す
set ={1,2,5, "amina"}
print(set)
#acessing item in a set
for x in set:
  print(x)
#add item in a set
set.add("sandra")
print(set)

#deleting element in set 
set.remove("amina")
print(set)

output:
{1, 2, 5, 'amina'}
1
2
5
amina
{1, 2, 5, 'sandra', 'amina'}
{1, 2, 5, 'sandra'}


スタック
スタックは、最後に入力されたデータがアクセスされる最初の最後のin first first(lifo)の原理に基づいた線形データ構造です.これは、配列構造を使用して構築されている操作、すなわち、要素をプッシュ(追加)、要素をポップ(削除)要素とアクセスする要素の先頭のスタックの1つのポイントからのみ.このtopはスタックの現在位置へのポインタです.例:5は4のスタックontopに加えられます、そして、あなたを取り除いている間、5が最初に取り除かれる最上位の要素から始めなければなりませんが、第4によってこのように第1に最初に最後に学ばれます.

スタックでの操作
empty () -スタックが空かどうかを返します.
size () -スタックのサイズを返します.
top () -スタックの最上位要素への参照を返します.
push () -スタックの先頭に要素' a 'を挿入します.
pop () -スタックの最上位要素を削除します.
# implementing stack using List :
myStack = []
#adding item to the stack 
myStack.append(10)
myStack.append(100)
myStack.append(1000)
myStack.append(10000)
print("Initial stack is:",myStack)
#removing utem form the list
print(myStack.pop())
print(myStack.pop())
print(myStack.pop())
print("After Removing elements:",myStack)

output:
Initial stack is: [10, 100, 1000, 10000]
10000
1000
100
After Removing elements: [10]

6 .キュー
待ち行列はまた、最初に入力されたデータが最初にアクセスされる最初のIN First Out(FIFO)の原理に基づいた線形データ構造である.これは、配列構造を使用して構築され、キューの両端から実行することができます操作、すなわち、ヘッドテールまたはフロントバック.要素の追加や削除などの操作はen queueと呼ばれ、dequeueや要素へのアクセスが可能です.

キューで行う操作
enqueue () :キューのキューに要素を追加します.
dequeue () :キューQから最初の要素を削除して返します.
empty () :キューqに見つかった要素がない場合にtrueを返し、そうでない場合にfalseを返します
size ()キュー内の要素数を返します.
# implementing Queue using List :
queue=[]
queue.append(10)
queue.append(100)
queue.append(1000)
queue.append(10000)
print("Initial Queue is:",queue)
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("After Removing elements:",queue)

output
Initial Queue is: [10, 100, 1000, 10000]
10
100
1000
After Removing elements: [10000]

連結リスト
リンクリストは、連続した記憶場所において、要素が記憶されない線形データ構造である.リンクリストの要素はポインターを使用してリンクされます.

連結リストで行う操作
横断:すべてのノードを次々と横断する.
挿入:指定した位置にノードを追加します.
削除:ノードを削除します.
検索:値で要素を検索します.
# A single node of a singly linked list
class Node:
  # constructor
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next
# A Linked List class with a single head node
class LinkedList:
  def __init__(self):  
    self.head = None 
  # insertion method for the linked list
  def insert(self, data):
    newNode = Node(data)
    if(self.head):
      current = self.head
      while(current.next):
        current = current.next
      current.next = newNode
    else:
      self.head = newNode
  # print method for the linked list
  def printLL(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next
# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert("Lux ")
LL.insert("Tech")
LL.insert("Academy")
LL.printLL()

output:
Lux 
Tech
Academy