【python】python数据结构（一）——线性表：顺序表的实现

逃离我推掉我的手 2022-06-07 09:07 252阅读 0赞

## 前言 ##

这一系列文章将介绍基于python语言的数据结构，主要涉及线性表、字符串、栈和队列、二叉树和树、图、字典和集合、排序等。

## 线性表及分类 ##

线性表是一类元素序列的抽象，是某类元素的集合，记录着元素之间的顺序关系。python中的list和tuple都支持线性表的需要，只是tuple中元素固定，而list则灵活的多。

顺序表：将表中元素顺序地存储在一大块连续的存储区内，这样实现的表称为顺序表。

链表：将元素存储在由链接构造起来的一系列存储块内，这样实现的表称为链表。

## 基本操作 ##

### 创建和访问操作 ###

**创建空表**：分配存储区，记录表的容量并将元素计数值设为0，创建新表的存储区后，设置信息记录域（max和num），保证表处于合法状态。

**加入元素**：list.insert(i,x)，将元素x插入到第i个位置

**删除元素**：del list\[i\]，删除第i个元素；list.remove(x)，删除值为x的元素

### 顺序表的优缺点 ###

优点：O(1)时间的按位置访问元素；元素在表里存储紧凑，除表元素存储区外只需要O(1)空间存放少量的辅助信息。

缺点：需要连续存储，一旦确定存储块大小，表的存储容量就确定，更改麻烦，在执行加入和删除操作时，要移动许多元素。

### Python中list基本实现 ###

list是一种采用分离式技术实现的动态记录顺序表。

加入元素：list.insert(len(list),x)，另一种等价写法：list.append(x)

list的实际策略：建立空表时，系统分配8个元素的存储区；在执行插入操作时，如果元素区满就换一块四倍大的存储区；如果表已经过大，换存储区时容量加倍。

## 一些操作的主要性质 ##

len(list)：计算列表元素个数，O(1)

元素访问，尾端加入和尾端删除都是O(1)操作

一般位置的元素插入、删除、替换、表连接(extend)都是O(n)操作

pop操作删除表尾元素复杂度为O(1)，一般元素复杂度为O(n)

list.clear()清除list中所有元素，O(1)操作

list.reverse()元素顺序倒置，复杂度为O(n)

def reverse(self):
        elems = self.elements
        i, j = 0, len(elems)-1
        while i < j:
            elems[i], elems[j] = elems[j], elems[i]
            i, j = i+1, j-1

list.sort()表中元素排序，最好的排序算法的平均和最坏情况的时间复杂度都是O(nlogn)

发表评论取消回复

表情：

评论列表（有 0 条评论，252人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构——线性表——顺序存储结构——C++实现线性表

顺序存储结构C++实现篇：主要实现了线性表的定义、初始化、显示、增、删结点操作。切记亲力亲为，动手实践写代码 main.cpp /

柔情只为你懂/ 2023年10月17日 13:01/ 0 赞/ 143 阅读

相关数据结构—线性结构—(顺序表)

目录定义：存取方式: 两种内存的分配方式：顺序表的基本操作：插入操作：

叁歲伎倆/ 2023年07月18日 14:00/ 0 赞/ 59 阅读

相关【数据结构】线性表（一）：顺序表

线性表 1.顺序表 1.1 概念及特点 1.2 顺序表图解 1.3 顺序表定义的两种方式

小鱼儿/ 2023年02月27日 12:28/ 0 赞/ 14 阅读

相关【数据结构——线性表之顺序表】

【数据结构——线性表之顺序表】目录：【数据结构——线性表之顺序表】一、顺序表的表示 1、静态顺序存储结构

淡淡的烟草味﹌/ 2022年12月10日 11:24/ 0 赞/ 207 阅读

相关数据结构线性表顺序表合并

include <stdio.h> include <stdlib.h> define LIST_INIT_SIZE 100

ゝ一世哀愁。/ 2022年09月18日 14:51/ 0 赞/ 207 阅读

相关数据结构线性表顺序表

include <stdio.h> include <stdlib.h> define LIST_INIT_SIZE 100

左手的ㄟ右手/ 2022年09月18日 14:51/ 0 赞/ 271 阅读

相关【python】python数据结构（一）——线性表：顺序表的实现

前言这一系列文章将介绍基于python语言的数据结构，主要涉及线性表、字符串、栈和队列、二叉树和树、图、字典和集合、排序等。线性表及分类线性表是一类元素序列

逃离我推掉我的手/ 2022年06月07日 09:07/ 0 赞/ 253 阅读

相关数据结构与算法——线性表—顺序表（顺序线性表）

线性表（linear list）是最简单，也是最基本的一种线性数据结构，它有两种存储表示方法：顺序表和链表。它的主要基本操作是插入，删除和查找。 3.1 顺序表（顺序线性表

喜欢ヅ旅行/ 2022年03月16日 12:54/ 0 赞/ 353 阅读

相关数据结构Java实现----线性表与顺序表

一、线性结构：如果一个数据元素序列满足：（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（2）第一个数据元素没有前驱数据元素

我就是我/ 2021年11月08日 21:56/ 0 赞/ 413 阅读

相关数据结构--线性表之顺序表实现

概述线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。基本概念

小鱼儿/ 2021年08月13日 20:24/ 0 赞/ 559 阅读