リスト、コレクション

リストと集合はすべての資料構造とアルゴリズムの基礎となる資料構造である.だから、私はこれについて勉強します.
インベントリ
特長
リスト、または線形リストは、プロジェクトの順序でリストされる線形資料構造です.リスト内のアイテムには、順序または場所があります.コレクションとは異なり、リストには順序があります.
LIST ADT
List()
insert(pos, e)
delete(pos)
isEmpty()
getEntry(pos)
size()
clear()
find(item)
replace(pos, item)
sort()
merge(lst)
display()
append(e)
上記の機能は、リストで実行できます.
もちろん、これらの機能の大部分はPythonがすでに内蔵しているリストや、類似の組み合わせで使用されている機能です.しかし、私たちは一生Pythonだけを使っているわけではないので、これらの機能の実現を知ることが重要です.
リストの実装
リストは次のとおりです.
1.配列構造
2.接続構造
2つの構造に表すことができます.
アレイ構造
Array構造は、ほとんどのプログラミング言語で使用される同じデータ型のデータを一度に作成するために使用されます.[]インデックス演算子を使用してアクセスします.これは、資料が連続したアドレスにあるからです.(コンピュータ構造を参照)
配列がどんなに大きくても,インデックス番号さえ分かれば,すなわち,アドレスさえ分かれば直接アクセスでき,エントリアクセス時間はO(1)である.ただし、アイテムを追加または削除すると、時間の複雑さが増します.
接続構造
チェーン時計というもの.以降の実施において詳細に説明する.
プロジェクトアクセスの時間的複雑さはO(k)である.
保証書
PythonのリストはC、JAVAのArrayとは異なり、スマートなダイナミックな並びです.既存のシナリオでは、シナリオのサイズを予め指定する必要があります.データ量を見積もることができない配列であれば、実際に使用することが困難であるという欠点があり、Python Listはこれらの問題を考慮せずに配列・実施することができる.
Pythonリストの時間的複雑さ
append()の時間的複雑さ:O(1)*O(n)を追加するには、時々すべての容量を増やす必要があります.
Insert():すべての項目をコピーして真ん中に挿入するので、O(n)です.
pop():上と同じです.
インプリメンテーションコード

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

    def insert(self, pos, elem):
        self.items.insert(pos, elem)

    def delete(self, pos):
        return self.items.pop(pos)

    def isEmpty(self):
        return self.size() == 0

    def getEntry(self, pos):
        return self.items[pos]

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

    def clear(self):
        self.items = []

    def find(self, item):
        return self.items.index(item)

    def replace(self, pos, elem):
        self.items[pos] = elem

    def sort(self):
        self.items.sort()

    def merge(self, lst):
        self.items.extend(lst)

    def display(self, msg='ArrayList'):  # default argument
        print(msg, self.size(), self.items)

特に難しい機能はないので説明は省略します.
しゅうごう
特長
リストに似た概念または集合では、要素の重複は許可されず、要素間に順序はありません.
Sets ADT
set()
size()
contains(e)
insert(e)
delete(e)
equals(setB)
union(setB)-集約演算
交差(setB)-交差演算
差分(setB)-差分演算
display()
インプリメンテーションコード

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

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

    def display(self, msg):
        print(msg, self.items)

    def contains(self, item):
        return item in self.items

    def insert(self, elem):
        if elem not in self.items:
            self.items.append(elem)

    def delete(self, elem):
        if elem in self.items:
            self.items.remove(elem)

    def union(self, setB):
        setC = Set()
        setC.items = list(self.items)
        for elem in setB.items:
            if elem not in self.items:
                setC.items.append(elem)
        return setC

    def intersect (self, setB):
        setC = Set()
        for elem in setB.items:
            if elem in self.items:
                setC.items.append(elem)
        return setC

    def diff(self, setB):
        setC = set()
        for elem in self.items:
            if elem not in setB.items:
                setC.items.append(elem)
        return setC

集合固有の演算集合、交差、差集合関数について説明する
しゅうごう

    def union(self, setB):
        setC = Set()
        setC.items = list(self.items)
        for elem in setB.items:
            if elem not in self.items:
                setC.items.append(elem)
        return setC

セーブセットの新しいセットCを宣言します.Cに自分のすべての要素を格納し、集合Bのすべての要素をチェックします.これらの要素が現在自分の集合に存在しない場合、すべてCに格納されます.
交差

    def intersect (self, setB):
        setC = Set()
        for elem in setB.items:
            if elem in self.items:
                setC.items.append(elem)
        return setC

交差を格納する新しい集合Cを宣言する.集合Bのすべての要素を確認し、その要素がA自身の要素にもある場合はCに入れる.
ダイバーシティ

    def diff(self, setB):
        setC = set()
        for elem in self.items:
            if elem not in setB.items:
                setC.items.append(elem)
        return setC

サブセットを保存する新しい集合Cを宣言する.また,交点とは逆に,B中の要素がすべて確認され,自分の要素と重複する要素がない場合はCに格納する.
接続リスト
特長
一番上のリスト部分の説明から見ると、リストには接続の構造、すなわち接続リストによって実現できる説明があります.接続リストは、その名の通り接続のリストです.

Pythonのリストしか書かないと接続リストはあまり必要ないと思われるかもしれませんが、基本原理を知ると助かります.

のいくつかの調査結果によると、Pythonのリストは接続リストとも呼ばれている.これは後で検証する必要がある情報です.

メリットとデメリット

容量に制限はありません.
アレイ構造は順番に格納され、容量が所定の範囲を超えている場合は、アレイ全体をコピーして新しいアレイを作成する複雑なプロセスが必要ですが、接続リストはアドレスをリンクするだけで問題はありません.

削除の自由を挿入します.
配列構造では、削除または挿入を実行する際に、位置全体を一度に押したり引いたりする演算が必要です.ただし、接続リストを挿入する場合は、2つの接続アドレスを変更し、削除する場合は2つの接続アドレスを削除するだけです.したがって,時間的複雑度はO(1)である.

プロジェクトアクセス時間が長い(欠点)
配列はインデックスを介して直接プロジェクトにアクセスできますが、接続リストには、最初からポインタを1つずつプロジェクトにアクセスする必要があるという欠点があります.

接続リストの構造
Node
接続された構造では、1つのボックスをノードと呼びます.ノードには、値付きData Fieldとアドレス付きLink Fieldが存在する.これは,今後接続リスト,スタック,キュー,Deqを越えて,グラフにおいても主に用いられる概念である.
Head Pointer
最初のノードが分かれば、接続リストはリンクを介して他のすべての接続ノードにアクセスできます.したがって、最初のノードのアドレスを保存する必要があります.保存しているのがHead Ponterです.そして最後のノードのlinkはNoneとして指定され、これ以上の接続はなく、ここが終了であることを示します.
接続リストは次のとおりです.

単純接続リスト

デュアル接続リスト

プロトタイプ接続リスト

全部で3種類あります.これは、以降の資料構造で説明する.
接続リストの実装

class Node:
    def __init__(self, elem, link):
        self.data = elem
        self.link = link


class LinkedList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head is None

    def size(self):
        node = self.head
        count = 0
        while node is not None:
            node = node.link
            count += 1
        return count

    def getNode(self, pos):
        if pos < 0:
            return None
        node = self.head
        while pos > 0 and node is not None:
            node = node.link
            pos -= 1
        return node

    def getEntry(self, pos):
        node = self.getNode(pos)
        if node is None:
            return None
        else:
            return node.data

    def replace(self, pos, elem):
        node = self.getNode(pos)
        if node is not None:
            node.data = elem

    def find(self, data):
        node = self.head
        while node is not None:
            if node.data == data:
                return node
            node = node.link
        return node

    def insert(self, pos, elem):
        before = self.getNode(pos - 1)
        if before is None:
            self.head = Node(elem, self.head)
        else:
            node = Node(elem, before.link)
            before.link = node

    def delete(self, pos):
        before = self.getNode(pos - 1)
        if before is None:
            if self.head is not None:
                self.head = self.head.link
        elif before.link is not None:
            before.link = before.link.link


    def object__repr__(self):
        pass

Class Node
ノード群がノードを作成します.self.dataには、要素値elem、selfが含まれます.linkにはlink値が含まれています.link値はDefault Arcgumentを使用し、コンテンツがない場合はNone、コンテンツが追加されている場合は値です.
getNode

    def getNode(self, pos):
        if pos < 0:
            return None

        node = self.head
        while pos > 0 and node is not None:
            node = node.link
            pos -= 1
        return node

ノードの演算を求めて、主に挿入を削除します.
selfノード.headに関連付けられた、すなわち開始ノードに設定します.次にpos値を1つずつ減らし、ノードを次のノードに移動します.posが0の場合、結果が返されます.
挿入、削除操作
まず挿入演算insertです.

    def insert(self, pos, elem):
        before = self.getNode(pos -1)  # the one before the place
        if before == None:
            self.head = Node(elem, self.head)
        else:
            node = Node(elem, before.link)
            before.link = node

before値を設定し、挿入する位置の直前のノードを検索します.次の手順で行います.
1.前のノードがない場合
前のノードがNoneの場合、現在の挿入位置がリストの一番前にあるノードは1つしかありません.だからこの場合あなたはselfですheadには、最初の要素と新しく挿入されたノードが含まれます.この場合、ノードのリンクフィールドはselfです.headの値、つまり自分の住所を追加します.

以前のノード
before値がある場合は、ノード変数に新しく作成したノードを追加します.ノードはbeforeです.linkが示す値を追加します.
その後、before.linkは現在のnodeに変更されました.

1、2、3、4のリストがあり、2と3の間に値を挿入したいです.このとき、新しいノードが3に接続されるように、2が持つアドレス3をノードのアドレスに追加する新しい値ノードを作成します.
演算deleteを削除します.

    def delete(self, pos, elem):
        before = self.getNode(pos - 1)  # the one before the place
        if before == None:
            if self.head is not None:
                self.head = self.head.link
        elif before.link is not None:
            before.link = before.link.link

Insertと同様に、beforeで古い値を検索します.
1.古い値はありません
1-1 self.ヘッドはノーじゃない
この場合、リストは空ではないのでself.headの値はselfです.headが持つlink値に変更します.

より前の値
before.linkの値をbeforeに設定します.linkの値

に変更
1 2 3のときに2を削除するといえば,2が持つ3に関するリンク情報を1のリンクに与える.
もしそうなら、疑問が生じる.拭いたお金はどこに行けばいいですか?パイソンではこれを心配する必要はありません.メモリが自動的に整理されるからです.(Garbage Collection)
時間の複雑さ
コードを見れば分かるように,削除や挿入自体の時間的複雑さはO(1)である.しかし、実際にはそうではない.昔の価値を探すから.getNodeでbefore値を検索します.getNodeのコードは1つずつ参照するコードです.したがって,getNodeはO(n)と同じ時間を必要とする.最終的には,挿入削除演算にO(n)が必要であるといえる.
の最後の部分
このレッスンでは、リスト、コレクション、接続リストについて説明します.接続リストはこれからもよく使われるコンセプトですので、ご注意ください.