没有合适的资源?快使用搜索试试~ 我知道了~
数据结构知识点总结.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 162 浏览量
2022-07-11
20:24:57
上传
评论
收藏 205KB PDF 举报
温馨提示
试读
8页
数据结构知识点概括 第一章 概 论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。 ·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。 ·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构: ·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型 ADT: ·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程,以
资源推荐
资源详情
资源评论
数据结构知识点概括
第一章 概 论
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。
数据结构的定义:
·逻辑结构:从逻辑结构上描述数据,独立于计算机。·线性结构:一对一关系。
·线性结构:多对多关系。
·存储结构:是逻辑结构用计算机语言的实现。·顺序存储结构:如数组。
·链式存储结构:如链表。
·索引存储结构:·稠密索引:每个结点都有索引项。
·稀疏索引:每组结点都有索引项。
·散列存储结构:如散列表。
·数据运算。
·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。
·常用的有:检索、插入、删除、更新、排序。
数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。
·结构类型:由用户借助于描述机制定义,是导出类型。
抽象数据类型
ADT
:·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。
算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。
评价算法的好坏的因素:·算法是正确的;
·执行算法的时间;
·执行算法的存储空间(主要是辅助存储空间);
·算法易于理解、编码、调试。
时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模
n
的函数。
渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。
评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为:常数阶
O
(
1
)、对数阶
O
(
log2n
)、线性阶
O
(
n
)、线性对数阶
O
(
nlog2n
)、
平方阶
O
(
n^2
)、立方阶
O
(
n^3
)、……
k
次方阶
O
(
n^k
)、指数阶
O
(
2^n
)。
空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模
n
的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。
第二章 线性表
线性表是由
n
≥
0
个数据元素组成的有限序列。
n=0
是空表;非空表,只能有一个开始结点,有且只能有一个终端结点。
线性表上定义的基本运算:
·构造空表:
Initlist
(
L
)
·求表长:
Listlength
(
L
)
·取结点:
GetNode
(
L
,
i
)
·查找:
LocateNode
(
L
,
x
)
·插入:
InsertList
(
L
,
x
,
i
)
·删除:
Delete
(
L
,
i
)
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和
逻辑结构中各结点相邻关系是一致的。地址计算:
LOCa
(
i
)
=LOCa
(
1
)
+
(
i-1
)
*d
;(首地址为
1
)
在顺序表中实现的基本运算:
·插入:平均移动结点次数为
n/2
;平均时间复杂度均为
O
(
n
)。
·删除:平均移动结点次数为(
n-1
)
/2
;平均时间复杂度均为
O
(
n
)。
线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个
结点值的同时,还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。
一个单链表由头指针的名字来命名。
单链表运算:
·建立单链表·头插法:
s->next=head
;
head=s
;生成的顺序与输入顺序相反。平均时间复杂度均为
O
(
n
)。
·尾插法:
head=rear=null
;
if
(
head=null
)
head=s
;
else r->next=s
;
r=s
; 平均时间复杂度均为
O
(
n
)
·加头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。
·查找·按序号:与查找位置有关,平均时间复杂度均为
O
(
n
)。
·按值:与输入实例有关,平均时间复杂度均为
O
(
n
)。
·插入运算:
p=GetNode
(
L
,
i-1
);
s->next=p->next
;
p->next=s
;平均时间复杂度均为
O
(
n
)
·删除运算:
p=GetNode
(
L
,
i-1
);
r=p->next
;
p->next=r->next
;
free
(
r
);平均时间复杂度均为
O
(
n
)
单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或
尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是
O
(
1
),不用
遍历整个链表。
双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域
prior
,形成两条不同方
向的链。由头指针
head
惟一确定。
双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为
O
(
1
)。
顺序表和链表的比较: ·基于空间:
·顺序表的存储空间是静态分配,存储密度为
1
;适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配,存储密度<
1
;适于线性表长度变化大时采用。
·基于时间:
·顺序表是随机存储结构,当线性表的操作主要是查找时,宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。
资源评论
是空空呀
- 粉丝: 167
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功