数据结构
2023-08-19 09:50:24 0 举报AI智能生成
数据结构就是数据的逻辑结构以及存储操作 数据结构就教会我们一件事：如何去有效的存储数据
作者其他创作
大纲/内容
线性表
概念
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列
顺序表
特性
特点：内存连续
逻辑结构：线性结构
数据结构：顺序存储
操作：增删改查
逻辑结构：线性结构
数据结构：顺序存储
操作：增删改查
链表
概念
链表是链式存储结构，用于存储逻辑关系为线性，也就是“一对一”关系的数据
特性
特点：内存不连续，通过指针连接
解决问题：解决了长度固定和插入麻烦的问题
逻辑结构：线性结构
存储类型：链式存储
操作：增删改查
解决问题：解决了长度固定和插入麻烦的问题
逻辑结构：线性结构
存储类型：链式存储
操作：增删改查
单向链表
有头链表
存放一个头节点，头节点的指针域有效，数据域无效
无头链表
每一个数据域和指针域都有效
数据结构基础知识
什么是数据结构
就是数据的逻辑结构以及存储操作
数据
数据元素
又称节点，是数据的基本单位，由若干个数据项组成
数据项
数据的最小单位，用于描述数据元素的有用信息
逻辑结构
线性关系
线性结构：一对一的关系
线性表，顺序表，链表，栈，队列
线性表，顺序表，链表，栈，队列
层次关系
树形结构：一对多关系
树：二叉树
树：二叉树
网状关系
图形结构：多对多关系
存储结构
概念：数据结构在计算机中的具体体现
顺序存储
通过数组实现：内存连续
特点：内存连续，随机存储，每个元素占用空间少
链式存储
通过指针（需要搭配结构体）实现
特点：内存不连续，通过指针连接
链表：有数据域和指针域，一个存放节点的数据一个存放结构体指针指向的下一个同类型节点的地址，需要通过结构体实现
索引存储
索引储存 = 索引表 + 数据文件
索引表用来存放数据地址
索引表用来存放数据地址
特点：可以提高查找速度，特点检索速度快，但是占用内存多，删除数据文件要及时更改索引表
散列存储
数据存储按照和关键码之间的关系进行存取，关系由自己决定，获取关键数据，通过元素的关键码方法的返回值来获取
特点：存的时候按关系存，取的时候按关系取
算法基础知识
什么是算法
算法就是解决问题的思想方法
程序 = 数据结构 + 算法
程序 = 数据结构 + 算法
算法的设计
取决于数据的逻辑结构
算法的实现
依赖于数据的存储结构
算法的特性
有穷性
算法的步骤有限
确定性
每一个步骤都有明确的含义，没有歧义
可行性
在规定时间内完成
输入输出
评价算法的好坏
正确性
易读性
健壮性
容错处理
高效性
执行效率，通过重复执行的次数来判断，也就是可以通过时间复杂度（时间处理函数）来判断
时间复杂度
语句频度：用时间规模函数表达式
时间规模函数：T(n) = O(f(n))
T(n) //时间规模函数
O //时间数量级
n //问题规模，a[100], n=100
f(n) //算法可执行语句重复执行的次数
T(n) //时间规模函数
O //时间数量级
n //问题规模，a[100], n=100
f(n) //算法可执行语句重复执行的次数
计算O的方法
(1)根据问题规模n写出表达式f(n)
(2)如果有常数项，将其置为1 //当f(n)的表达式中只有常数项的时候，例如f(n)=8 ==> O(1)
(3)只保留最高项，其他项舍去。
(4)如果最高项系数不为1，则除以最高项系数。
(2)如果有常数项，将其置为1 //当f(n)的表达式中只有常数项的时候，例如f(n)=8 ==> O(1)
(3)只保留最高项，其他项舍去。
(4)如果最高项系数不为1，则除以最高项系数。
0 条评论
下一页
