乐趣区

关于数据结构和算法:数据结构与算法

jiezi

一、算法

1.1、算法根底

概念：算法是独⽴存在的⼀种解决问题的⽅法和思维
算法的个性：

  1. 输出：算法具备 0 个或多个输⼊
  2. 输入: 算法⾄少有 1 个或多个输入
  3. 有穷性: 算法在无限的步骤之后会⾃动完结⽽不会⽆限循环，并且每⼀个步骤能够在可承受的工夫内实现
  4. 确定性：算法中的每⼀步都有确定的含意，不会呈现⼆义性
  5. 可⾏性：算法的每⼀步都是可⾏的，也就是说每⼀步都可能执⾏无限的次数实现

1.2、算法效率掂量

⼤ O 记法 对于枯燥的整数函数 f，如果存在⼀个整数函数 g 和实常数 c >0，使得对于充沛⼤的 n 总有 f(n)<=c*g(n)，就说函数 g 是 f 的⼀个渐近函数（疏忽常数），记为 f(n)=O(g(n))。也就是说，在趋势⽆穷的极限意义下，函数 f 的增⻓速度受到函数 g 的束缚，亦即函数 f 与函数 g 的特色类似
工夫复杂度 假如存在函数 g，使得算法 A 解决规模为 n 的问题示例所⽤工夫为 T(n)=O(g(n))，则称 O(g(n))为算法 A 的渐近工夫复杂度，简称工夫复杂度，记为 T(n)

了解“⼤ O 记法”

对于算法的工夫性质和空间性质，最重要的是其数量级和趋势，这些是剖析
算法效率的次要局部。⽽计量算法基本操作数量的规模函数中那些常量因⼦
能够忽略不计。例如，能够认为 3n^2 和 100n^2 属于同⼀个量级，如果两个算法
解决同样规模实例的代价别离为这两个函数，就认为它们的效率“差不多”，都为 n^2 级
复杂度分类 解释阐明 剖析哪个复杂度为最优
最优工夫复杂度 算法实现⼯作起码须要多少基本操作 价值不⼤，因为它没有提供什么有⽤信息，其反映的只是最乐观最现实的状况，没有参考价值
最坏工夫复杂度 算法实现⼯作最多须要多少基本操作 提供了⼀种保障，表明算法在此种水平的基本操作中⼀定能实现⼯作
均匀工夫复杂度 算法实现⼯作均匀须要多少基本操作 对算法的⼀个全⾯评估，因而它残缺全⾯的反映了这个算法的性质。但另⼀⽅⾯，这种掂量并没有保障，不是每个计算都能在这个基本操作内实现。⽽且，对于均匀状况的计算，也会因为应⽤算法的实例散布可能并不平均⽽难以计算

因而，只需关注算法的最坏状况，亦即最坏工夫复杂度

工夫复杂度的计算规定：
1. 基本操作，即只有常数项，认为其工夫复杂度为 O(1)
2. 程序构造，工夫复杂度按加法进⾏计算
3. 循环构造，工夫复杂度按乘法进⾏计算
4. 分⽀构造，工夫复杂度取最⼤值
5. 判断⼀个算法的效率时，往往只须要关注操作数量的最⾼次项，其它主要项和常数项能够疏忽
6. 在没有非凡阐明时，咱们所剖析的算法的工夫复杂度都是指最坏工夫复杂度

空间复杂度 S(n)

空间复杂度 (SpaceComplexity) 是对⼀个算法在运⾏过程中长期占⽤存储空间⼤⼩的量度
算法的工夫复杂度和空间复杂度合称为算法的复杂度

1.3、常见的工夫复杂度

执行次数函数 阶 非正式术语
100 O(1) 常数阶
2n+1 O(n) 线性阶
3n²+2n+1 O(n²) 平方阶
4n³+3n²+2n+1 O(n³) 立方阶
2^n O(2^n) 指数阶
5log2n + 1 O(logn) 对数阶
3nlog2n + 2n + 1 O(nlogn) nlogn 阶

留神，将 log2n（以 2 为底的对数）简写成 logn

常⻅工夫复杂度之间的关系

所耗费的工夫从⼩到⼤
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) <O(n^n)

二、数据结构

2.1、数据结构根底

数据是⼀个形象的概念，将其进⾏分类后失去程序设计语⾔中的根本类型。如：int，float，char，bool 等。数据元素之间不是独⽴的，存在特定的关系，这些关系便是构造(eg: 一个人有名字和年龄，名字和年龄都属于这个人，因而数据元素不是独立的)
数据结构指数据对象中数据元素之间的关系

2.2、算法和数据结构的区别

算法 数据结构
⾼效的程序须要在数据结构的根底上设计和抉择算法 数据结构只是动态的形容了数据元素之间的关系
算法是为了解决理论问题⽽设计的 数据结构是算法须要解决的问题载体

综上：程序 = 数据结构 + 算法

2.3、抽象数据类型(ADT)

抽象数据类型 面向对象中的封装
指⼀个数学模型以及定义在此数学模型上的⼀组操作 class 蕴含属性和办法，属性就是存储的数据，办法就是对数据的操作
抽象数据类型就相当于面向对象中的封装，因而相当于 class 的概念

罕用的数据运算：插入、删除、批改、查找、排序

2.4、根本的数据结构

2.4.1、程序表

2.4.1.1、程序表概念相干

将一组元素看成一个序列，用元素在序列里的地位和程序，示意理论利用中的某种有意义的信息，或者示意数据之间的某种关系，这样的一组序列元素的组织模式，形象的称为 线性表，一个线性表是某类元素的一个汇合，还记录着元素之间的一种程序关系；

线性表两种存储模式：

  1. 程序表，将元素程序地寄存在⼀块间断的存储区⾥，元素间的程序关系由它们的存储程序⾃然示意
  2. 链表，将元素寄存在通过链接结构起来的⼀系列存储块中
2.4.1.2、程序表的模式
图 a 图 b
程序表的根本模式，数据元素自身间断存储，每个元素所占的存储单元⼤⼩固定雷同 如果元素的⼤⼩不统⼀，则须采⽤图 b 的元素外置的模式，将理论数据元素另⾏存储，⽽程序表中各单元地位保留对应元素的地址信息（即链接）
元素的下标是其逻辑地址，⽽元素存储的物理地址（理论内存地址）能够通过存储区的起始地址 Loc (e)加上逻辑地址（第 i 个元素）与存储单元⼤⼩（c）的乘积计算⽽得，即：Loc(e) = Loc(e) + c* 图 b 中的 c 不再是数据元素的⼤⼩，⽽是存储⼀个链接地址所需的存储量，这个量通常很⼩

** 拜访指定元素时⽆需从头遍历，通过计算便可取得对应地址，其工夫复
杂度为 O(1)**

2.4.1.3、程序表的构造与实现

构造：

程序表的残缺信息蕴含两个局部：

1、表中的元素汇合
2、实现正确操作而需记录的信息(无关表的整体状况的信息，这部分信息次要包含存储区的 ** 容量 ** 和以后表中已有的 ** 元素个数 **)

两种实现形式：

图 a 图 b
⼀体式构造, 存储表信息的单元与元素存储区以间断的⽅式安顿在⼀块存储区⾥，两局部数据的整体造成⼀个残缺的程序表对象 分离式构造，表对象⾥只保留与整个表无关的信息（即容量和元素个数），理论数据元素寄存在另⼀个独⽴的元素存储区⾥，通过链接与根本表对象关联。
⼀体式构造整体性强，易于治理。然而因为数据元素存储区域是表对象的⼀局部，程序表创立后，元素存储区就固定了

元素存储区替换

⼀体式构造 分离式构造
因为程序表信息区与数据区间断存储在⼀起，所以若想更换数据区，则只能整体搬迁，即整个程序表对象（指存储程序表的构造信息的区域）扭转了 若想更换数据区，只需将表信息区中的数据区链接地址更新即可，⽽该程序表对象不变

元素存储区裁减

采⽤分离式构造的程序表，若将数据区更换为存储空间更⼤的区域，则能够
在不扭转表对象的前提下对其数据存储区进⾏了裁减，所有使⽤这个表的地
⽅都不用批改，这种技术实现的程序表称为动静程序表，因为其容量能够在使⽤中动态变化

裁减的两种策略：

每次裁减减少固定数⽬ 每次裁减容量加倍
每次裁减减少固定数⽬的存储地位，如每次裁减减少 10 个元素地位，这种策略可称为线性增⻓ 每次裁减容量加倍，如每次裁减减少⼀倍存储空间
特点：节俭空间，然而裁减操作频繁，操作次数多 特点：缩小了裁减操作的执⾏次数，但可能会节约空间资源。以空间换工夫，举荐的⽅式
2.4.1.4、程序表的操作

减少元素：
a、尾端加⼊元素，工夫复杂度为 O(1)
b、保序的元素加⼊，工夫复杂度为 O(n)

删除元素：
a、删除表尾元素，工夫复杂度为 O(1)
b、保序的元素删除，工夫复杂度为 O(n)

2.4.1.5、Python 中的程序表
list 和 tuple 两种类型采⽤了程序表的实现技术，tuple 是不可变类型，即不变的程序表，因而不⽀持扭转其外部状态的任何操作，⽽其余⽅⾯，则与 list 的性质相似

2.4.2、链表

1. 定义
链表（Linked list）是⼀种常⻅的根底数据结构，是⼀种线性表，然而不像顺
序表⼀样间断存储数据，⽽是在每⼀个节点（数据存储单元）⾥寄存下⼀个
节点的地位信息（即地址）

2. 单向链表
单向链表也叫单链表，是链表中最简略的⼀种模式，它的每个节点蕴含两个
域，⼀个信息域（元素域）和⼀个链接域。这个链接指向链表中的下⼀个节
点，⽽最初⼀个节点的链接域则指向⼀个空值

  • 元素域 elem ⽤来寄存具体的数据
  • 链接域 next ⽤来寄存下⼀个节点的地位（python 中的标识）
  • 变量 p 指向链表的头节点（⾸节点）的地位，从 p 登程能找到表中的任意节点

3. 节点的实现与节点的操作实现

class SingleNode(object):
    """单链表的节点实现"""

    def __int__(self, item):
        self.item = item
        self.next = None


class SingleLinkList(object):
    """单链表的操作实现"""

    def __init__(self):
        self.__head = None

    # 判断链表为空
    def is_empty(self):
        return self.__head is None

    # 链表长度
    def length(self):
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.item)
            cur = cur.next
        print("")

    # 头部增加元素
    def add(self, item):
        node = SingleNode()
        node.item = item
        node.next = self.__head
        self.__head = node

    # 尾部增加元素
    def append(self, item):
        node = SingleNode()
        node.item = item
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    # 指定地位增加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            cur = self.__head
            count = 0
            node = SingleNode()
            node.item = item
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 删除元素
    def remove(self, item):
        cur = self.__head
        pre = None
        while cur is not None:
            if cur.item == item:
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                return
            pre = cur
            cur = cur.next

    # 查找元素
    def search(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

2.4.3、双向链表

每个节点有两个链接：⼀个指向前⼀个节点，当此节点为第⼀个节点时，指向空值；⽽另⼀个指向下⼀个节点，当此节点为最初⼀个节点时，指向空值

双向链表实现与操作：

class DoubleNode(object):
    """双向链表的节点实现"""

    def __int__(self, item):
        self.item = item
        self.next = None
        self.pre = None


class DoubleLinkList(object):
    """双向链表的操作实现"""

    def __init__(self):
        self.__head = None

    # 判断链表为空
    def is_empty(self):
        return self.__head is None

    # 链表长度
    def length(self):
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.item)
            cur = cur.next
        print("")

    # 查找元素
    def search(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

    # 头部增加元素
    def add(self, item):
        node = DoubleNode()
        node.item = item
        node.next = self.__head
        self.__head = node
        if node.next:
            node.next.pre = node

    # 尾部增加元素
    def append(self, item):
        node = DoubleNode()
        node.item = item
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            node.pre = cur
            cur.next = node

    # 指定地位增加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            cur = self.__head
            count = 0
            node = DoubleNode()
            node.item = item
            while count < pos:
                count += 1
                cur = cur.next
            node.next = cur
            node.pre = cur.pre
            cur.pre.next = node
            cur.pre = node

    # 删除元素
    def remove(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:
                        self.__head.pre = None
                else:
                    cur.pre.next = cur.next
                    if cur.next:
                        cur.next.pre = cur.pre
                return
            cur = cur.next

2.4.4、单向循环链表

单链表的⼀个变形是单向循环链表，链表中最初⼀个节点的 next 域不再为
None，⽽是指向链表的头节点

单向循环链表的实习与操作实现：

class SingleNode(object):
    """单向循环链表的节点实现"""

    def __int__(self, item):
        self.item = item
        self.next = None


class SingleLinkList(object):
    """单向循环链表的操作实现"""

    def __init__(self):
        self.__head = None

    # 判断链表为空
    def is_empty(self):
        return self.__head is None

    # 链表长度
    def length(self):
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        if self.is_empty():
            print("")
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.item)
            cur = cur.next
        print(cur.item)

    # 头部增加元素
    def add(self, item):
        node = SingleNode()
        node.item = item
        if self.is_empty():
            self.__head = node
            node.next = node
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        node.next = self.__head
        self.__head = node
        cur.next = self.__head

    # 尾部增加元素
    def append(self, item):
        node = SingleNode()
        node.item = item
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head

    # 指定地位增加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            cur = self.__head
            count = 0
            node = SingleNode()
            node.item = item
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 删除元素
    def remove(self, item):
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.item == item:
                if cur == self.__head:
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    pre.next = cur.next
                return
            pre = cur
            cur = cur.next
        if cur.item == item:
            if cur == self.__head:
                self.__head = None
            else:
                pre.next = self.__head

    # 查找元素
    def search(self, item):
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.item == item:
                return True
            cur = cur.next
        if cur.item == item:
            return True
        return False
退出移动版