目录
- 一、数据结构
- 1.1 算法与数据结构的区别
- 二、顺序表
- 2.1 顺序表的基本形式【重点】
- 2.2 顺序表的两种基本实现方式【重点】
- 1、一体式结构：
- 2、分离式结构:
- 2.3 元素存储区替换与扩充
- 1. 元素存储区的替换
- 2. 元素存储区的扩充
- 2.4 顺序表的操作
- 1. 增加元素
- 2. 删除元素
- 2.5 Python中的顺序表
一、数据结构
- 数据结构指数据对象中数据元素之间的关系。
- 计算机只有三种数据类型：int、float、char。在内存中，1个int占4个字节。
1.1 算法与数据结构的区别
- 程序 = 数据结构 + 算法
- 算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体。
- 抽象数据类型(Abstract Data Type)：抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。
- 常用的数据运算有五种：插入、删除、修改、查找、排序
二、顺序表
-
线性表：将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。线性表是最基本的数据结构之一，根据线性表的实际存储方式，分为两种实现模型：顺序表、链表。
-
顺序表：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
-
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁。
2.1 顺序表的基本形式【重点】
- 数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc(ei) = Loc(e0) + c*i
- 查找的时间复杂度为O(1)：
顺序表的结构决定了访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。
- 元素外置的顺序表（被称为对实际数据的索引）：
元素的大小不统一，则须采用元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。
注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。
- 一个顺序表的完整信息包括两部分：一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息（主要包括元素存储区的容量和当前表中已有的元素个数两项）。
2.2 顺序表的两种基本实现方式【重点】
1、一体式结构：
- 存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对概念：象。
一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
2、分离式结构:
- 概念：表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。
2.3 元素存储区替换与扩充
1. 元素存储区的替换
-
一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。
-
分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。
2. 元素存储区的扩充
-
采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。
-
扩充的两种策略：
1、线性增长：每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置。
特点：节省空间，但是扩充操作频繁，操作次数多。2、每次扩充容量加倍，如每次扩充增加一倍存储空间。
特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。
2.4 顺序表的操作
1. 增加元素
- 尾端加入元素：直接在尾部加入即可，时间复杂度为O(1)；
- 非保序加入元素：将插入位置的原元素调换到末尾，时间复杂度为O(1)；
- 保序的加入元素：在某一位置插入元素后，原位置的元素依次后移。时间复杂度为O(n)。
2. 删除元素
- 删除末尾元素：直接删除，时间复杂度为O(1)；
- 非保序的删除元素：元素删除后，直接将末尾的元素插入到删除位置。时间复杂度为O(1)；
- 保序的元素删除：元素删除后，删除位置后面的元素依次前移。时间复杂度为O(n)。
2.5 Python中的顺序表
-
Python中的顺序表：list、tuple
-
list就是一种采用分离式技术实现的动态顺序表。
-
list为什么采用分离式顺序表？
list的特征是：允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。
为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。 -
list的实现策略：
在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。
