数据结构笔记1

发布时间:2024年01月24日

来自《Python数据结构学习笔记》(张清云 编著)

第一章 数据结构基础

1.逻辑结构

  • 集合:结构中的数据元素除了同属于一种类型外,别无其他关系
  • 线性结构:数据元素之间一对一的关系
  • 树形结构:数据元素之间一对多的关系
  • 图状结构或网状结构:结构中的数据元素之间存在多对多的关系

2.物理结构

  • 顺序存储结构
  • 链接存储结构
  • 数据索引存储结构
  • 数据散列存储结构(Hash存储)

3.常用数据结构

  • 数组(Array)
  • 栈(Stack)
  • 队列(Queue)
  • 链表(Linked List)
  • 树(Tree)
  • 图(Graph)
  • 堆(Heap)
  • 散列表(Hash)

第二章 算法

1.算法的五个重要特征:

  • 有穷性
  • 确切性
  • 输入
  • 输出
  • 可行性

2.算法是程序的灵魂

数据结构+算法=程序

程序=算法+数据结构+程序设计方法+语言环境

3.表示算法的方法

  • 流程图
  • N-S流程图
  • 计算机语言

4.时间复杂度和空间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n的平方)<O(n3)<O(2的n次方)<O(n!)<O(n的n次方)

内置模块库timeit,用来检测和比较python代码运行时间。

class timeit.Timer(stmt='pass',setup='pass',timer=<timer function>)
  • Timer:测量小段代码执行速度的类
  • stmt:要测试的代码语句(statment)
  • setup:运行代码时需要的设置
  • timer:定时器函数,与平台有关

第三章 Python内置的几种数据结构

1.列表

2.元组

3.字典

第四章 线性表

1.线性表

两个基本特征:

  • 集合中必存在唯一的“第一元素”和唯一的“最后元素”。
  • 除最后元素之外,均有唯一的后继;除第一元素之外,均有唯一的前驱。

结构特点:

  • 均匀性:同一线性表的各数据元素必须有相同的类型和长度。
  • 有序性:各元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的,即存在唯一的“第一个”和“最后一个”数据元素,除了第一个和最后一个外,其他元素前面只有一个数据元素直接前驱,后面只有一个直接后继。

基本操作:

2.顺序表

以数组形式保存。

主要操作功能:

  • 计算顺序表的长度
  • 清空操作
  • 判断线性表是否为空
  • 判断顺序表是否为满
  • 附加操作
  • 插入操作
  • 删除操作
  • 获取单元
  • 按值查找

3.链表

通过“链”建立起数据元素之间的次序关系。主要有单链表、循环链表、双向链表、双向循环链表。

文章来源:https://blog.csdn.net/2301_80618119/article/details/135754855
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。