数据结构定义一个顺序表,数据结构顺序表的创建和输出
目录、数据结构1.1算法与数据结构的区别2.1序列表的基本形式【要点】2.2序列表的两种基本实现方法【要点】1 .一体式结构：2.3分离式结构：2.3元素存储区1的更换和扩展。元素存储区的替换和扩展2.4序列表1的操作。Python中元素的添加2 .元素的删除2.5
一、数据结构数据结构是指数据对象中数据元素之间的关系。计算机的数据类型只有三种：int，float，char。在内存中，一个int占用4个字节。1.1算法和数据结构的区别程序=数据结构算法算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题的载体。抽象数据类型：抽象数据类型(ADT)的含义是指一个数学模型和在这个数学模型上定义的一组操作。也就是说，数据类型和对数据类型的操作被捆绑在一起并封装。引入抽象数据类型的目的是将数据类型的表示和对数据类型的操作的实现从程序中对这些数据类型和操作的引用中分离出来，使它们相互独立。有五种常用的数据操作：插入、删除、修改、查找、排序。第二，序列表。
线性表：要把一组数据元素(通常是同一类型)作为一个整体来管理和使用，就需要创建这样的元素组，用变量记录，传入传出函数等。线性表是最基本的数据结构之一。根据线性表的实际存储方式，可以分为顺序表和链表两种实现模式。
顺序：元素按顺序存储在一个连续的存储区域中，元素之间的顺序关系自然用它们的存储顺序来表示。
为了建表，需要提前知道数据大小才能申请连续存储空间，扩展时需要移动数据。
2.1序列表的基本形式[重点]
数据本身是连续存储的，每个元素占用相同的存储单元大小，元素的下标是其逻辑地址，而元素的物理地址(实际内存地址)可以通过将存储区域的初始地址Loc (e0)与逻辑地址(第I个元素)的乘积与存储单元大小(C)相加来计算，即Loc(ei)=Loc(e0) c*i lookup。
表的结构决定了在访问指定元素时，可以通过计算得到相应的地址，其时间复杂度为O(1)。
元素的外部顺序表(称为实际数据的索引):
如果元素大小不统一，实际数据元素要以外部元素的形式单独存储，对应元素的地址信息(即链接)要存储在序列表中的各个单元位置。因为每个链接都需要相同的存储量，所以通过上面的公式，可以计算出元素链接的存储位置，然后沿着链接找到实际存储的数据元素。注意，图B中的C不再是数据元素的大小，而是存储一个链接地址所需的存储量，通常很小。
顺序表的完整信息包括两部分：一是表中元素的集合，二是为了实现正确操作需要记录的信息，即关于表整体情况的信息(主要包括元素存储区的容量和当前表中元素的个数)。
2.2序列表的两种基本实现方法【要点】1。集成结构：
存储表信息的单元和元素存储区以连续的方式排列在一个存储区中，两部分数据的整体形成一个完整的顺序表对概念：image。集成结构整体性强，易于管理。然而，由于数据元素存储区是表对象的一部分，所以在创建顺序表之后，元素存储区是固定的。
2.分离结构：
概念：表对象中只存储与整个表相关的信息(即容量和元素个数)，实际的数据元素存储在另一个独立的元素存储区，与基本表对象相链接。2.3元件储存区1的更换和扩建。元素存储区集成结构的替换由于序列表信息区和数据区是连续存储在一起的，如果要替换数据区，只能整体移动，即整个序列表对象(存储序列表结构信息的区域)发生了变化。
如果split结构想要改变数据区，只需要更新表信息区中数据区的链接地址，而顺序表对象保持不变。
2.元素存储区的扩展采用独立结构的顺序表。如果将数据区替换为具有更大存储空间的区域，则可以在不改变表对象的情况下扩展数据存储区，并且不需要修改所有使用该表的地方。这种技术实现的序列表称为动态序列表，因为它的容量可以在使用中动态变化。
两种扩张策略：
1.线性增长：为每次扩展添加固定数量的存储位置，例如每次扩展10个元素位置。
特点：节省空间，但是扩展操作频繁，操作次数多。
2.每次扩展的容量加倍，例如每次扩展的存储空间加倍。
特点：减少了扩展操作的执行次数，但可能会浪费空间资源。用空间换时间，推荐方式。
2.4序列表1的操作。添加元素
添加尾部元素：直接在尾部添加即可，时间复杂度为O(1)；无序添加元素：将插入位置的原始元素更改到末尾，时间复杂度为O(1)；按顺序添加元素：在某个位置插入元素后，原位置的元素依次向后移动。时间复杂度为O(n)。2.删除元素
删除最后一个元素：直接删除，时间复杂度为O(1)；无序删除元素：删除元素后，将最后一个元素直接插入删除位置。时间复杂度为O(1)；顺序元素删除：删除元素后，删除位置后的元素依次前移。时间复杂度为O(n)。2.5 Python中的序列表：列表，元组
链表是一种动态序列表，采用分离技术实现。
为什么list使用单独的顺序表？
list的特点是可以添加任何元素，在添加元素的过程中，表对象的标识符(由函数id得到的值)保持不变。
为了满足这个特性，需要能够改变元素存储区域，并且要保证存储区域改变时列表对象的id不变，只能采用分离实现技术。
清单的实施策略：
当创建一个空表(或者很小的表)时，系统分配一个可以容纳8个元素的存储区域；当执行插入操作(插入或追加)时，如果元素存储区已满，则用4倍大的存储区替换它。但如果此时牌桌已经很大了(目前的门槛是50000)，那就改变策略，翻倍。引入这种策略改变是为了避免过多的空闲存储位置。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。