1データ構造とアルゴリズム初歩スタックキュー順序テーブルチェーンテーブル

50212 ワード
データ構造とアルゴリズムの入門
データ構造とアルゴリズムの初歩
1データ構造とアルゴリズム
1.1紹介
データ構造は、データを格納するだけでなく、データへのアクセスと処理の操作をサポートする形式でデータを整理する集合です.アルゴリズムは問題を解く際に従う必要がある、明確に指定された簡単な命令の集合であり、問題を解くための実現構想や思想を表す.優れたアルゴリズムは,プログラムが短時間でリソースを消費することの少ない条件下で実行結果を得ることができる.データ構造とアルゴリズム思想は広範な汎用性を持ち、どの言語でも使用でき、文法に違いがあるだけだ.
1.2アルゴリズムと時間複雑度
1.2.1例
a a a,b b,c cを計算する.a + b + c = 1000 a 2 + b 2 = c 2 a + b + c = 1000\\a^2 + b^2 = c^2 a+b+c=1000a2+b2=c2
方法1
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a + b + c == 1000 and a ** 2 + b ** 2 == c ** 2:
                print(a, b, c)

方法2
for a in range(0,1001):
    for b in range(0,1001):
        c = 1000-a-b
        if a+b+c == 1000 and a**2+b**2 == c**2:
            print(a, b, c)

2つの方法の計算結果は同じであるが,方法1の実行時間は方法2の実行時間よりもはるかに長いため,実行時間の観点から方法2の方が優れている.
1.2.2プログラムの優劣を評価する方法
  • は、データがコードから直接取得できず、コンピュータのハードウェア条件に関連しているため、コンピュータのリソースと実行効率を消費することは推奨されない.
  • 計算プログラムの実行時間は、コンピュータのハードウェア条件および実行環境の影響を受けるため、適切に推奨されます.
  • 時間複雑度推奨
    • 1.2.3リスト操作時間とtimeitモジュール
    操作:リストに要素を追加し、異なる方法で取得するのに時間がかかります.ここでtimeitモジュールは、コードを取得するのに時間がかかります.
    class timeit.Timer(stmt='pass', setup='pass', timer=)

    
stmt：       ；
setup：               ；
timer：    。
stmt   setup       'pass'，        ，               。

    空のリストをインスタンス化し、1000の数値をリストに追加します.
    def test1():
    alist = []
    for i in range(1000):
        alist.append(i)

def test2():
    alist = []
    for i in range(1000):
        alist = alist + [i]

def test3():
    alist = [i for i in range(1000)]

def test4():
    alist = list(range(1000))

    from timeit import Timer

if __name__ == '__main__':
    t1 = Timer('test1()', 'from __main__ import test01')
    print(t1.timeit(1000))  # 0.04284289999986868
    
    t1 = Timer('test2()', 'from __main__ import test02')
    print(t1.timeit(1000))  # 0.8767927999999756
    
    t1 = Timer('test3()', 'from __main__ import test03')
    print(t1.timeit(1000))  # 0.022221100000024308
    
    t1 = Timer('test4()', 'from __main__ import test04')
    print(t1.timeit(1000))  # 0.009096400000089488

    1.2.4時間複雑度
    アルゴリズムの時間複雑度は関数であり,アルゴリズムの実行ステップ数を量子化し,アルゴリズムの実行時間を定性的に記述したり,入力値が無限に近づくときのアルゴリズムの実行状況を理解したりすることができる.時間的複雑度は大O記号で表されることが多い(大O記法).例えば、上記の例では、方法1の時間的複雑度はO(n 3)O(n^3)O(n 3)、方法2の時間的複雑度はO(n 2)O(n^2)O(n 2)である.
    一般的な時間複雑度ソートO(1)1.3データ構造
    1.3.1紹介
    データ構造はデータの何らかの組織方式であり、主にデータがどのような形式で保存またはアクセス操作されるかを研究している.アルゴリズムは実際の問題を解決するために設計され,データ構造はアルゴリズムが問題を処理する必要がある担体である.
    1.3.2例
    [{'name': 'name1', 'score': 'score1'},
 {'name': 'name2', 'score': 'score2'},
 {'name': 'name3', 'score': 'score3'}]

    方式1におけるクエリ動作の時間的複雑度はO(n)O(n)O(n)である.
    [('name1', 'score1'), ('name2', 'score2'), ('name3', 'score3')]

    方式2におけるクエリ動作の時間的複雑度はO(n)O(n)O(n)である.
    {'name1': {'score': 'score1'}, 'name2': {'score': 'score2'}, 'name3': {'score': 'score3'}}

    方式3におけるクエリ操作の時間的複雑度はO(1)O(1)O(1)である.
    2スタックとキュー
    2.1紹介
    スタックスタックStackとキューQueueは、データを格納するためのデータ構造です.スタック:後入先出キュー:後入先出
    2.2スタック
    スタックを作成します.
    Stack()       ，     。
push(item)   (  )  ，            。
pop()   (  )  ，          。
peek()          ，      0。
isEmpty()        。
size()          。

    class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)  #     

    def pop(self):
        return self.items.pop()  #     

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)

    def peek(self):
        return len(self.items) - 1

    s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek())  # 2
print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

    2.3キュー
    キューを作成します.
    Queue()        。
enqueue(item)     ，          。 
dequeue()     ，       。
isEmpty()         。
size()           。

    class Queue():
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)  #     

    def dequeue(self):
        return self.items.pop()  #     

    def size(self):
        return len(self.items)

    def isEmpty(self):
        return self.items == []

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.dequeue())  # 2
print(q.dequeue())  # 3

    2.4ジョセフ問題
    手をやけどした芋は6人の子供が輪になっていて、最初の子供は手をやけどした芋を持っていて、タイマーが計時してから1秒後に次の子供に伝える必要があります.タイマーは7秒ごとに、手に芋を持っている子供がゲームを終了し、1人の子供しか残っていない.キューを使ってこのゲーム戦略を実現してください.何番目の位置にいる子供が勝つでしょう.
    #  6         
kids = ['A', 'B', 'C', 'D', 'E', 'F']
q = Queue()
for kid in kids:
    q.enqueue(kid)

while q.size() > 1:  #        
    #       
    for i in range(6):  #        =     -1
    	#             
        kid = q.dequeue()
        q.enqueue(kid)
        
    #                   （           ）
    q.dequeue()
print(q.dequeue())  # E

    2.5 2つのキュー実装スタック
    q1 = Queue()
q2 = Queue()
items = [1, 2, 3, 4, 5, 6]
for item in items:
    q1.enqueue(item)

while q1.size() >= 1:
    #  q1   n-1     ，     q2     
    while q1.size() > 1:
        item = q1.dequeue()
        q2.enqueue(item)

	#              ，    ，          。
    print(q1.dequeue())
    #     
    q1, q2 = q2, q1

    2.6両端キュー
    通常のキューと比較して、両端キューはヘッダーとテールの両端でデータの挿入と削除を行うことができます.
    Deque()     deque。
add_front(item)       deque   。
add_rear(item)       deque   。
remove_front()  deque       。
remove_rear()  deque       。
is_empty()   deque    。
size()   deque      。

    class Dequeue():
    def __init__(self):
        self.items = []

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
    	return self.items.pop(0)
        
    def remove_rear(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

    デュアル・エンド・キュー・アプリケーション・ケース:レビュー・チェック
    def is_huiwen(input_str):
    d = Dequeue()
    for each_char in input_str:
        d.add_front(each_char)
    flag = True
    while d.size()>1:
        if d.remove_front() != d.removeRear():
            flag = False
    return flag 

print(is_huiwen('abaa'))  # False

    3シーケンステーブルとチェーンテーブル
    3.1順序表
    すべての要素を連続したメモリ領域のセットに順次無停止に格納します.このストレージ構造はシーケンス構造です.シーケンスストレージ構造を用いた線形テーブルをシーケンステーブル(Contiguous List)と呼び,シーケンステーブル内の要素はシーケンステーブルである.シーケンステーブルは、単一データ型とマルチデータ型に分けられ、Pythonのリストとメタグループがマルチデータ型に属するシーケンステーブルである.
    利点アクセス操作は簡単で効率的で、要素を下付きで直接操作します.欠点シーケンステーブルを作成する前に、メモリに連続した記憶領域を申請するために、記憶されるデータの数とタイプを予め決定する必要がある.内部の要素を挿入または削除する必要がある場合は、データの移行に相当する要素を並べ替えるために、順序テーブル全体を巡回して移動する必要があります.
    3.2チェーンテーブル
    3.2.1紹介
    チェーンテーブル(Linked List)は、物理記憶ユニット上の非連続、非順序の記憶構造であり、要素の論理順序はチェーンテーブル内のポインタリンク順序によって実現される.チェーンテーブルの要素は下付きではなく、格納されている各要素は1つのノードと呼ばれ、各ノードは2つの部分を含む:データ要素を格納するデータドメインと、次のノードアドレスを格納するポインタドメイン.
    3.2.2チェーンテーブルの構築
    ノードデータ構造のカプセル化
    class Node():
    def __init__(self, item):
        self.item = item
        self.next = None

    is_empty()：      
length()：    
travel()：      
add(item)：        
append(item)：        
insert(pos, item)：        
remove(item)：    
search(item)：        

    class LinkedList():
    def __init__(self):  #         
        self._head = None  #           

    def add(self, item):
        node = Node(item)
        node.next = self._head
        self._head = node

    def traval(self):
        cur = self._head
        while cur:
            print(cur.item)
            cur = cur.next

    def length(self):
        count = 0
        cur = self._head
        while cur:
            count += 1
            cur = cur.next
        return count

    def is_empty(self):
        return self._head == None

    def search_item(self, item):
        find = False
        cur = self._head
        while cur:
            cur_item = cur.item  #            
            if item == cur_item:
                find = True
                break
            cur = cur.next
        return find

    def append(self, item):  #          
        node = Node(item)

        if self._head == None:  #     
            self._head = node
            return
        #      
        cur = self._head
        pre = None  #     cur      
        while cur:
            pre = cur
            cur = cur.next
        #      pre           ，cur   
        pre.next = node

    def insert(self, pos, item):  #          
        node = Node(item)
        pre = None
        cur = self._head
        if (pos < 0) or (pos > self.length()):
            print('    ，    ！！！')
            return
        if pos == 0:
            node.next = self._head
            self._head = node
            return
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur

    def remove(self, item):  #        
        cur = self._head
        pre = None
        #               
        if self._head.item == item:
            self._head = cur.next
            return
        while cur:
            pre = cur
            cur = cur.next
            if cur.item == item:
                break
        pre.next = cur.next

    l = LinkedList()
l.append(1)
l.append(2)
l.append(3)
l.append(4)
l.append(5)
l.remove(5)
l.traval()

    3.2.3チェーンテーブルの逆転
    class LinkedList():
	def reverse(self):
        if self.is_empty():
            return None
        
        previous_node = None
        current_node = self._head
        next_node = current_node.next
        
        while True:
        	#       ，     。
            current_node.next = previous_node
            #     
            previous_node = current_node
            current_node = next_node
            if next_node:
                next_node = next_node.next
            else:
            	break
            	
        self._head = previous_node
    でんしん
    NOJ-1641誤ったアルゴリズム