Python数据结构与算法笔记(1)

ADT

参考:

01_抽象数据类型和面向对象编程 数据结构与算法--ADT

ADT

ADT(abstract data type)是由用户定义的数据类型,它制定了一组数据值的集合及可作用在这些数据值上的一组操作。ADT的定义与它的具体实现无关,因此只关注如何使用它,无需关注它的具体实现。

ADT可以被看做一个黑盒子。用户程序与ADT实例的交互是通过调用定义在ADT接口上的操作进行的。操作集可以分为4类:

  • Constructors:创建和初始化ADT的实例
  • Accessors:返回实例中的数据,而不进行修改
  • Mutators:修改ADT实例的内容
  • Iterators:逐个处理单个数据组件

数据结构

ADT将定义与实现进行了分离。自定义的ADT必须要有一个实现,而实现ADT时我们所做出的选择会影响实现的功能和效率。

数据结构可以通过以下两方面来描述:

1. 它们如何存储和组织单个数据元素

2. 提供哪些操作来存取和处理其上的数据

常用术语定义

  • collection:集合,指一组数据值,单个数据值之间没有隐含的组织关系
  • container:容器,指存储和组织一个集合的数据结构或者ADT。集合中的单个数据值称为容器的元素(element),当容器中没有元素时,称容器为空(empty),Python中容器的例子有:string,tuple,list,dict,set
  • sequence:序列,是一种容器,该同期的元素按线性排列,并且每个元素能通过其位置访问(即通过下标访问)。Python中的序列例子:string、tuple、list
  • sorted sequence:有序序列,元素的位置基于每个元素的前后元素的某种预定关系确定。

数组和列表

参考:

数组和列表

数组array

数组是最常用的一种线性结构,其实python内置了一个array模块,但是大部分人甚至从来没用过它。Python的array是内存连续、存储的都是同一数据类型的结构,而且只能存储数值和字符。

常用的是numpy.array

列表List

操作

平均时间复杂度

list[index]

O(1)

list.append

O(1)

list.insert

O(n)

list.pop(index), default last element

O(1)

list.remove

O(n)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏三好码农的三亩自留地

Java反射—写给自己的总结

上面反射是Oracle官方文档的定义,反射能够突破访问权限控制,这还是很优秀的,但是,问题来了,为什么需要反射或者说什么情况下需要用反射?

17620
来自专栏技术墨客

Spring和性——数据的类型转换

在字符串到实体转换一文中介绍了Spring核心框架中使用PropertyEditor将任何字符串转换为数字、实体的方法。除了字符串到实体,Spring还提供了更...

23430
来自专栏JavaEdge

SpringMVC数据绑定定义支持的数据绑定方式

定义 百度百科定义: 简单绑定是将一个用户界面元素(控件)的属性绑定到一个类型(对象)实例上的某个属性的方法。 例如,如果一个开发者有一个Customer类...

50160
来自专栏光变

3.1 ASM-方法-结构

ASM-方法-结构 本章将会介绍如果使用ASM core API生成或者转换Java编译后的method。 本将开始会展示编译后的method,然后使用很多说...

16520
来自专栏阮一峰的网络日志

Thunk 函数的含义和用法

本文是《深入掌握 ECMAScript 6 异步编程》系列文章的第二篇。 Generator函数的含义与用法 Thunk函数的含义与用法 co函数库的含义与...

33240
来自专栏一个会写诗的程序员的博客

第12章 元编程与注解、反射第12章 元编程与注解、反射

反射(Reflection)是在运行时获取类的函数(方法)、属性、父类、接口、注解元数据、泛型信息等类的内部信息的机制。这些信息我们称之为 RTTI(Run-T...

10220
来自专栏函数式编程语言及工具

Scalaz(46)- scalaz-stream 基础介绍

    scalaz-stream是一个泛函数据流配件库(functional stream combinator library),特别适用于函数式编程。sc...

22570
来自专栏前端架构与工程

JavaScript实现私有属性

JavaScript被很多人认为并不是一种面向对象语言,原因有很多种,比如JavaScript没有类,不能提供传统的类式继承;再比如JavaScript不能实现...

19550
来自专栏owent

VC和GCC内成员函数指针实现的研究(一)

最近在《C++对象模型》一书里说到的virtual的成员函数指针,低于128的被cfront编译器认为是虚表偏移量(支持子类对父类函数的覆盖)。VC只是提了下单...

10730
来自专栏orientlu

FreeRTOS 任务调度 List 组织

前面了解了 FreeRTOS 的内存管理,接下来看看任务调度,这也是一个操作系统中最重要的一部分,而其任务调度大量使用了链表(list.c 实现),调度器使用链...

18140

扫码关注云+社区

领取腾讯云代金券