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