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