数据结构与算法实验一顺序表,算法的顺序结构

　　Yyds干货库存

　　在程序中，经常需要将一组数据元素(通常是同一类型)作为一个整体来管理和使用。需要创建这样的元素组，用变量记录，传入传出函数等。一组数据中包含的元素数量可能会改变(可以添加或删除元素)。

　　对于这种需求，最简单的解决方法就是把这样一组元素看成一个序列，利用序列中元素的位置和顺序来表达一些实际应用中有意义的信息或者数据之间的某种关系。

　　这样一组序列元素的组织形式可以抽象为一个线性表。线性表是某些元素的集合，它还记录了元素之间的顺序关系。线性表是最基本的数据结构之一，在实际程序中有着广泛的应用，它经常被用作实现更复杂的数据结构的基础。

　　根据线性表的实际存储方式，有两种实现模式：

　　顺序表，将元素按顺序存储在一个连续的存储区域中，元素之间的顺序关系自然用它们的存储顺序来表示。链表，将元素存储在由链接构造的一系列存储块中。一、序列表的基本形成

　　图A显示了序列表的基本形式。数据元素是连续存储的，每个元素占用相同的存储单元大小，元素的下标是其逻辑地址。元素的物理地址(实际存储器地址)可以通过将存储区域Loc (e0)的起始地址和逻辑地址(第I个元素)的乘积与存储单元大小(C)相加来计算，即：

　　Loc(ei)=Loc(e0) c*i

　　因此，在访问指定元素时，可以通过计算得到相应的地址，其时间复杂度为O(1)。

　　如果元素大小不统一，则应采用图B中元素的外部形式单独存储实际数据元素，并将对应元素的地址信息(即链接)存储在序列表中的各个单元位置。因为每个链接都需要相同的存储量，通过上面的公式，我们可以计算出元素链接的存储位置，然后顺着链接找到实际存储的数据元素。注意，图B中的C不再是数据元素的大小，而是存储一个链接地址所需的存储量，通常很小。

　　像图B这样的序列表也叫实际数据的索引，是最简单的索引结构。

　　二、序列表的结构与实现2.1序列表的结构

　　顺序表的完整信息包括两部分，一部分是表中的元素集(数据区)，另一部分是正确操作需要记录的信息(表头信息)，即关于表整体情况的信息。这部分信息主要包括元素存储区的容量和当前表中已有元素的数量。

　　2.2序列表的两种基本实现方法

　　图A是一个整体结构。存储表信息的单元和元素存储区以连续的方式排列在存储区中，这两部分数据的整体形成一个完整的顺序表对象。

　　集成结构整体性强，易于管理。然而，由于数据元素存储区是表对象的一部分，所以在创建顺序表之后，元素存储区是固定的。

　　图B是一个分离的结构，只有与整个表相关的信息(即容量和元素个数)存储在表对象中，实际的数据元素存储在另一个独立的元素存储区，与基本的表对象相链接。

　　2.3元素存储区替换集成结构由于序列表信息区和数据区是连续存储在一起的，如果要替换数据区，只能整体移动，即整个序列表对象(存储序列表结构信息的区域)发生了变化。

　　如果split结构想要改变数据区，只需要更新表信息区中数据区的链接地址，而顺序表对象保持不变。

　　2.4元件存储区的扩展采用独立结构的顺序表。如果将数据区替换为具有更大存储空间的区域，则可以在不改变表对象的情况下扩展数据存储区，并且不需要修改所有使用该表的地方。只要程序的运行环境(计算机系统)还有空闲存储，这个表结构就不会满而导致操作无法进行。人们称这种技术实现的序列表为动态序列表，因为它的容量可以在使用中动态变化。

　　两种扩张策略

　　为每次扩展添加固定数量的存储位置的策略，例如为每次扩展添加10个元素位置，可以称为线性增长。

　　特点：节省空间，但是扩展操作频繁，操作次数多。每次扩展的容量加倍，例如每次扩展的存储空间加倍。

　　特点：减少了扩展操作的执行次数，但可能会浪费空间资源。用空间换时间，推荐方式。三。3.1添加元素序列表的基本操作如图所示，向序列表添加新元素111有三种方式

　　a)在末尾添加元素，时间复杂度为O(1)

　　b)时间复杂度为O(1)的非保序添加元素(不常见)

　　c)增加保序元素，时间复杂度为O(n)

　　3.2删除元素

　　a)删除页脚元素，时间复杂度为O(1)

　　b)时间复杂度为O(1)的无序(不常见)元素删除

　　c)保序元素删除，时间复杂度为O(n)

　　四。Python中的序列表。Python中的list和tuple采用了序列表的实现技术，拥有前面讨论的序列表的所有属性。

　　Tuple是不可变类型，即不可变序列表，所以不支持任何改变其内部状态的操作。在其他方面，它类似于list。

　　4.1 list Python标准类型list的基本实现技术list是一个元素个数可变的线性表，可以添加和删除元素，在各种操作中保持已有元素的顺序(即保序)。此外，它还具有以下行为特征：

　　对于基于下标(位置)的高效元素访问和更新，时间复杂度应为O(1)；

　　为了满足这个特性，应该采用顺序表技术，表中的元素存储在一个连续的存储区域中。可以添加任何元素，在不断添加元素的过程中，表对象的标识符(由函数id获得的值)保持不变。

　　为了满足这个特性，需要能够改变元素存储区域，并且要保证存储区域改变时列表对象的id不变，只能采用分离实现技术。在Python的官方实现中，list是一种动态序列表，通过分离技术实现。这就是为什么使用list.append(x)(或list.insert(len(list)，x)，即在尾部插入)比在指定位置插入元素更高效的原因。

　　在Python的正式实现中，list实现采用了以下策略：在创建一个空表(或者非常小的表)时，系统分配一个可以容纳8个元素的存储区域；当执行插入操作(插入或追加)时，如果元素存储区已满，则用4倍大的存储区替换它。但如果此时牌桌已经很大了(目前的门槛是50000)，那就改变策略，翻倍。引入这种策略改变是为了避免过多的空闲存储位置。

　　转载请联系作者取得转载授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。