02142 数据结构导论
2023-10-13 11:37:42 1 举报AI智能生成
02142 数据结构导论
作者其他创作
大纲/内容
存储数据元素
数据元素之间的关联方式
包含两个部分:
存储，处理的对象
顺序存储结构
链式存储结构
索引存储结构
散列存储结构
逻辑结构对应的存储结构（物理结构）
数据
也叫字段或域，不可分割最小标识单元
数据项
为数据的基本单位，由数据项组成
_解释_
任意两个节点之间都没有邻接关系，组织形式松散
集合：
结点按逻辑关系以此排列形成一条“链”，结点之间一个一个依次相邻接
线性结构：
具有分支、层次特性，形态向自然界的树，上层的结点可以与下层多个结点相邻接
树形结构：
任何两个结点都可以相邻接
图结构：
逻辑结构
数据元素
术语
常数阶: O(1)
例如：二分查找法
对数阶：O（log2n）
线性阶：O(n)
常见的多项式阶：O（n^2）、O（n^3）
例如：O（n^2） 冒泡算法
多项式阶：O(n^c)
C>1的正常数
常见的指数阶有O（2^n)
该算法时间复杂度不可估算
指数阶：O(C^n)
类型
T(n)=O(f(n))
时间复杂度
程序代码所占的空间
输入数据所占用的空间
辅助变量所占用的空间
算法执行期间所需要的存储空间
S(n)=O(g(n))
空间复杂度
满足具体的问题需要
正确性
便于阅读、理解、交流、调试、修改、扩充
易读性
容错机制
健壮性
时间性能与空间性能效率
时空性
评价因素
算法
概论
第一章
逻辑结构相邻，物理存储位置也相邻
称为顺序表：一般使用数组来表示
插入
删除
查找
基本运算
最坏的情况下，时间复杂度O(n)
创建
单链表
循环链表
双向链表
对称结构
访问前驱和后继结点时间复杂度O（1）
头结点的prior 指向最后一个结点 ，最后一个结点的next指向头结点
从任意个结点出发都能够扫描整个链表
描述
设p指向待删结点
设p指向结点后面
双向循环链表
链接存储结构
顺序表与单链表算法性能对比
线性表
第二章
特性：后进先出
Push
进栈
Pop
出栈
栈
特性：先进先出
链队列
队列
三元表示法
稀疏矩阵
值相同的元素或零元素
分布有规律
对称矩阵
矩阵的压缩存储
数组
栈、队列和数组
第三章
简述
存储机构
遍历
二叉树
树和森林
哈夫曼树
树和二叉树
第四章
图
第五章
第六章
排序
第七章
02142 数据结构导论
0 条评论
回复 删除
下一页
