没有合适的资源?快使用搜索试试~ 我知道了~
数据结构基础知识要点.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 173 浏览量
2021-10-10
19:40:13
上传
评论
收藏 248KB DOCX 举报
温馨提示
试读
17页
数据结构基础知识要点.docx
资源推荐
资源详情
资源评论
第一章 数据结构
.定义
数据结构是电脑存储、组织数据的方式。数据结构是抽象数据类型的物理实现。
数据结构包括如下几个方面:
数据元素之间的逻辑关系即数据的逻辑结构。
数据元素及其关系在电脑存储器中的存储方式,即数据的存储结构,也称为数据的物理
结构。
施加在该数据上的操作即数据的运算。
逻辑结构类型
集合结构。交通工具的集合,动物的集合
线性结构。一对一,综合素质测评产生的学生排名
树形结构。一对多,单位的组织结构图,族谱
图形结构。多对多,生产流程、施工计划、网络建设图等
存储结构类型
顺序存储方法。数组
链式存储方法。链表
索引存储方法
散列存储方法
算法
通常把具体存储结构上的操作实现步骤或过程称为算法。
语言里通常表现为解决问题的步骤
程序 算法〔加工数据〕 数据结构〔数据的存储和组织〕
算法的五个特征
有穷性在有穷步之后结束。
确定性无二义性。
可行性可通过基本运算有限次执行来实现。
有输入:可有零个或多个。
有输出至少有一个输出。
算法分析
时间复杂度:〔算法的工作量大小〕通常把算法中包含基本运算次数的多少称为算法的
时间复杂度也就是说一个算法的时间复杂度是指该算法的基本运算次数。
算法中基本运算次数 是问题规模 的某个函数 记作:
空间复杂度:
实现算法所需的存储单元多少
第二章线性表
线性表的基本概念
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性
表的长度用 表示。
线性结构的基本特征为
集合中必存在唯一的一个“第一元素”;
集合中必存在唯一的一个“最后元素”;
除最后一个元素之外,均有唯一的后继后件;
除第一个元素之外,均有唯一的前驱前件。
定义顺序表
线性表逻辑结构
顺序表存储结构
!"##$%&'()*+,,定义存放顺序表元素的数组
-!./+,,!./ 为存放线性表的实际长度
0123-+,,顺序表类型
顺序表上的运算及其实现
建立顺序表 #3-
创建一个空的顺序表,要完成线性表所需空间的分配和其他初始化设置。
求线性表的长度 3-3./
输出线性表 4-3-
在线性表中的指定位置插入一个元素 5 !"
根据键值查找指定元素 6- !"7)"
获取指定位置的元素信息 8 !"
9删除指定位置的元素 4! !"
:释放线性表 4;3-
线性表的链式存储——单链表〔## 域和指针域 <〕
由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素即数据元素之间是一对一
的逻辑关系所以当进行链式存储时一种最简单也最常用的方法是
在每个结点中除包含有数据域外只设置一个指针域用以指向其后继结点这样构成的
链接表称为线性单向链接表简称单链表;
9单链表的定义
3-=3- 类型的定义如下
3);,>定义单链表结点类型>,
!"##+
3);><+,>指向后继结点>,
03-=3-+
:顺序表上的运算及其实现
、创建单链表 3-=3->#3-+
、初始化单链表 ?;-5-3-3-=3->!-+
、释放单链表 ?;-4;3-3-=3->!-+
、获取单链表中元素的数量 -3-3./3-=3->!-+
、输出单链表中的所有数据 ?;-4-3-3-=3->!-+
、获取单链表中指定位置的元素 -8 !"3-=3->!--!; !"> !"+
9、根据键值查找指定元素 -6- !"7)"3-=3->!-/#>=/ !"> !"+
:、采用头插法向单链表中插入一个元素
-5 !"@A#3-=3->!- !"" !"+
B、采用尾插法向单链表中插入一个元素
-5 !"@6;;3-=3->!- !"" !"+
、向单链表中的指定位置插入一个元素
5 !"@3;3-=3->!--!; !"" !"+
、删除指定位置的元素
-4! !"3-=3->!--!; !"> !"+
B线性表的链式存储——双链表〔## 域指针域 <和 前驱〕
对于双链表采用类似于单链表的类型定义其 43-=3- 类型的定义如下
4);,>定义双链表结点类型>,
!"##+
4);>-;+,>指向前驱结点>,
4);><+,>指向后继结点>,
043-=3-
在双链表中 所指的结点之后插入一个> 结点。
其操作语句描述为
CD<CD<+,>将 插入到 之后>,
CD<CD-;+
CD-;+
CD<+
归纳起来删除双链表 3 中> 结点的后续结点。其操作语句描述为
CD<2CD<+
2CD<CD-;+
循环链表
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是
空而是指向表头结点整个链表形成一个环。由此从表中任一结点出发均可找到链表中其
他结点。带头结点的单向循环链表和双向循环链表如下列图
剩余16页未读,继续阅读
资源评论
学习使人快乐张
- 粉丝: 14
- 资源: 6万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功