最新要闻
- 全球讯息:职工医保报销比例2022_职工医保报销比例
- 全球观点:OpenAI CEO谈GPT4:人类迄今开发的最伟大技术 有点害怕了
- 即时:曹曦月方否认带货3个月成交278元:拿证据说话
- 国内外多名大胃王意外死亡 有人胖到320斤有人开播前突然昏迷:专家科普
- 环球微头条丨男子整形后称没法靠颜值吃饭了:丢了工作
- 《暗黑4》公测性能实测:RTX 4090显卡流畅跑8K
- 世界要闻:李彦宏谈文心一言:市场反馈符合预期 股价波动没必要解释
- 焦点滚动:挺能藏啊!男子电动滑板车藏84个SSD入境被海关查获
- 天天微头条丨卡佩罗:那不勒斯和国米将晋级 迈尼昂和奥纳纳是米兰双雄的关键
- 每日观点:曹姓明星收20万带货3月成交278元 被判退还13.9万:要量力而行
- 13代酷睿躺赢了 4nm锐龙7000跳票:此前规格被砍2刀
- 环球观热点:《流浪地球2》门框机器人科幻十足 设计师详解:还能晾衣服能甩干
- 东北首条海下/跨海地铁!大连地铁5号线正式运营
- 动态焦点:暴雪:《暗黑》系列能成功多亏了韩国玩家热情和爱戴
- 全球观点:朱雀二号遥一运载火箭发射失利:已查明飞行故障 通过归零评审
- 全球热头条丨《雷霆沙赞2》豆瓣开分6.5:加朵女神加分、剧情被批幼稚低级
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
世界最资讯丨数据结构-绪论
- 本文参考于2024年的王道考研计算机的复习指导。- 仅供学习交流,如侵权,即删。- 本系列地址:https://www.cnblogs.com/kohler21/category/2289027.html
目录- 第一章 绪论
- 数据结构的基本概念
- 基本概念和术语
- 数据结构三要素
- 1.数据的逻辑结构
- 2.数据的存储结构
- 3.数据的运算
- 算法和算法评价
- 算法的基本概念
- 算法效率的度量
- 数据结构的基本概念
第一章 绪论
数据结构的基本概念
基本概念和术语
1.数据
数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
2.数据元素
(资料图片)
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。
3.数据对象
数据对象是具有相同性质的数据元素的集合,是数据的一个子集。例如,整数数据对象是集合N={0,±1,±2,···}。
4.数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1)原子类型。其值不可再分的数据类型。
2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
3)抽象数据类型。抽象数据组织及与之相关的操作。
5.数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中,数据元素都不是孤立存在的,它们之间存在某种关系,这种数据元素相互之间的关系称为结构(Structure)。
数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。
数据的逻辑结构和存储结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构。
数据结构三要素
1.数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构,线性表是典型的线性结构;集合、树和图是典型的非线性结构。数据的逻辑结构分类如图所示。
集合。结构中的数据元素之间除“同属一个集合”外,别无其他关系,如下图所示。
线性结构。结构中的数据元素之间只存在一对一的关系,如下图所示。
树形结构。结构中的数据元素之间存在一对多的关系,如下图所示。
图状结构或网状结构。结构中的数据元素之间存在多对多的关系,如下图所示。
2.数据的存储结构
存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构,它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。
1)顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取,每个元素占用最少的存储空间:缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
2)链式存储。不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象,能充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,且只能实现顺序存取。
3)索引存储。在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是(关键字,地址)。其优点是检索速度快;缺点是附加的索引表额外占用存储空间。另外,增加和删除数据时也要修改索引表,因而会花费较多的时间。
4)散列存储。根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。其优点是检索、增加和删除结点的操作都很快;缺点是若散列函数不好,则可能出现元素存储单元的冲突,而解决冲突会增加时间和空间开销。
3.数据的运算
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
算法和算法评价
算法的基本概念
算法(Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。此外,一个算法还具有下列5个重要特性:
1)有穷性。一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。
2)确定性。算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出。
3)可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4)输入。一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
5)输出。一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。
通常,设计一个“好”的算法应考虑达到以下目标:
1)正确性。算法应能够正确地解决求解问题。
2) 可读性。算法版具有良好的可读性,以指助人们理解。
3)健壮性。输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。
4)高效率与低存储量需求。效率是指算法执行的时间,存储量需求是指算法执行过程中所需要的最大存储空间,这两者都与问题的规模有关。
算法效率的度量
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
1.时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级。算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级,因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度®。因此,算法的时间复杂度记为:T(n)=O(f(n))。
式中,O的含义是T(n)的数量级,其严格的数学定义是:若T(n)和f(n)是定义在正整数集合上的两个函数,则存在正常数C和no,使得当n≥no时,都满足0≤T(n)≤Cf(n)。
算法的时间复杂度不仅依赖于问题的规模n,也取决于待输入数据的性质(如输入数据元素的初始状态)。例如,在数组A[0...n—1]中,查找给定值k的算法大致如下:
(1)i=n-1;(2)while(i>=0&&(A[i]!=k));(3)i--;(4)return i;
该算法中语句3(基本运算)的频度不仅与问题规模n有关,而且与输入实例中A的各元素的取值及k的取值有关:
①若A中没有与k相等的元素,则语句3的频度f(n)=n。
②若A的最后一个元素等于k,则语句3的频度f(n)是常数0。最坏时间复杂度是指在最坏情况下,算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下,算法的期望运行时间。
最好时间复杂度是指在最好情况下,算法的时间复杂度。
一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。
在分析一个程序的时间复杂性时,有以下两条规则:
a)加法规则
T(n)=Ti(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
b)乘法规则
T(n) = T1(n)xT2(n) = O((n))xO(g(n))=O(f(n)xg(n))
按数量级递增排列,常见的时间复杂度有:
常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2),立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
2.空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。记为
S(n)=O(g(n))
一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需的辅助空间为常量,即O(1)。
关键词:
热文:数据安全始终是一个不可忽视的问题
世界最资讯丨数据结构-绪论
全球讯息:职工医保报销比例2022_职工医保报销比例
全球观点:OpenAI CEO谈GPT4:人类迄今开发的最伟大技术 有点害怕了
即时:曹曦月方否认带货3个月成交278元:拿证据说话
希尔排序、快速排序、KMP算法
环球热推荐:008爬虫之短短20行代码下载周杰伦所有歌曲
一次 Hyperf 注解失效问题分析
全球看热讯:Qt+百度AI文字识别OCR小工具
国内外多名大胃王意外死亡 有人胖到320斤有人开播前突然昏迷:专家科普
热点在线丨2023省选16天
著名的Breach黑客论坛管理员被捕
环球微头条丨男子整形后称没法靠颜值吃饭了:丢了工作
《暗黑4》公测性能实测:RTX 4090显卡流畅跑8K
世界短讯!SSL/TLS协议运行机制的概述
最新资讯:重学c#系列—— explicit、implicit与operator[三十四]
世界要闻:李彦宏谈文心一言:市场反馈符合预期 股价波动没必要解释
焦点滚动:挺能藏啊!男子电动滑板车藏84个SSD入境被海关查获
【天天快播报】webpack原理(2):ES6 module在Webpack中如何Tree-shaking构建
CTF show 信息收集篇
Quicker 快速开发,控制脚本关闭(示例,鼠标连点器)
天天微头条丨卡佩罗:那不勒斯和国米将晋级 迈尼昂和奥纳纳是米兰双雄的关键
每日观点:曹姓明星收20万带货3月成交278元 被判退还13.9万:要量力而行
13代酷睿躺赢了 4nm锐龙7000跳票:此前规格被砍2刀
已知球面经纬度求方位角和反方位角(awk一行代码实现)
环球观热点:《流浪地球2》门框机器人科幻十足 设计师详解:还能晾衣服能甩干
东北首条海下/跨海地铁!大连地铁5号线正式运营
世界热讯:Linux学习笔记
报道:插件化架构设计(2):插件化从设计到实践该考量的问题汇总
【天天新要闻】Vins 前端中高效的去畸变的方式解析
动态焦点:暴雪:《暗黑》系列能成功多亏了韩国玩家热情和爱戴
全球观点:朱雀二号遥一运载火箭发射失利:已查明飞行故障 通过归零评审
全球热头条丨《雷霆沙赞2》豆瓣开分6.5:加朵女神加分、剧情被批幼稚低级
【全球独家】万字血书Vue—Vue的核心概念
张兰被曝国外欠债9.8亿,海外家庭信托被追债,拼命带货疑为还债
Ocelot使用与设置路由Routing
环球速递!arthas排查线上问题真是太好用了!
肯德基全家桶被曝吃出生的炸鸡!店家回应是锅出现故障
世界快播:C++ class struct
环球视点!Windows OpenGL ES 图像 GPUImageLookupFilter
世界观速讯丨8万元会成爆款吗?宝骏悦也实车曝光:像吉姆尼、能跑303公里
每日热文:印度男子因新娘高三成绩不好要求退婚 还要退5千彩礼:网友看笑
世界观焦点:CSS学习笔记
热门看点:女生被拍同学勇敢对峙让男子删除 想保护好自己的朋友:网友称赞勇敢
1.5mm!iPhone 15 Pro Max将打破最薄边框纪录:CAD外观渲染图曝光 更帅了
全球微头条丨没有科技与狠活 :依能天然苏打水2.3元发车 无糖无气0卡
03月18日09时福建漳州疫情数据 阳了以后为什么会腰疼?应该怎么办?
当前要闻:为什么文件删除了但磁盘空间没有释放?
微博图床被废,自己动手丰衣足食。
【聚看点】Source Generator初探
4、AOP
天天亮点!汽车降价潮蔓延!成都豪撒1亿购车补贴 汽车流通协会称武汉汽车降价不公平
【天天热闻】俞敏洪称下辈子宁愿当没钱的流浪汉:自己周围的企业家都在没日没夜的干活
比亚迪出海再下一城!乌兹比克斯坦三车齐发:宋PLUS 22万起售
世界聚焦:调查显示民众预期英国央行将继续加息
【全球速看料】差距有多大?一图看懂蔚来、小鹏、理想汽车2022年第四季度财报:老大变了
每日速读!水晶球档杆绝无仅有!韩系豪华电动车捷尼赛思GV60上市:28.58万起
世界速讯:你对Linux窗口管理程序Tmux了解吗
【全球聚看点】还买什么汉兰达!全新大七座SUV福特锐界L开售:22.98万历史新低
【世界速看料】超市6500元招聘引学生排队投简历 负责人:已收到五十多份
世界看点:南宁市2023年事业单位统一考试简章发布 337个岗位共招1764人
【当前独家】读Java性能权威指南(第2版)笔记20_垃圾回收G
何小鹏:王凤英一周工作七天、让大家很卷
何小鹏谈竞争对手降价:油车一定会反击、小鹏将降低25%生产成本
springboot跨域问题解决方案
天天亮点!听闻索尼PS5 Pro主机明年发售后:老玩家们集体不干了
环球通讯!日本女大胃王菅原初代患肠癌病逝:曾10分钟吞399碗荞麦面
全球热点评!美国一核电站承认150万升核污染水泄漏:已隐瞒数月
导演郭帆都看不下去!众筹1亿的《流浪地球2》周边 为啥要偷工减料?
说句话就能做表格、PPT!微软把GPT-4塞进办公套件 我慌了
每日热门:喉结左侧有个硬疙瘩_左侧睾丸里有个小疙瘩是什么
AIGC的下一站是什么?
速读:vue2前端导出带背景色表格 xlsx xlsx-style
环球新资讯:Attention与SelfAttention
五角大楼官员表示:太阳系中可能存在外星母舰探测地球
环球消息!每日机构分析:3月17日
fiddler:The system proxy was changed.Click to reenable capturing
iPhone 15 Pro Max屏幕边框窄爆:将打破小米13纪录
99元 联想YOGA新款M5无线鼠标上架:鹅卵石设计
张裕葡小萄赤霞珠甜红葡萄酒2支到手39.9元:酒香浓郁
世界热讯:手机百度文库的下载券怎么用啊 为什么(百度文库不能用下载券)
网红店半天妖烤鱼被曝垃圾桶捞回食材上桌!合肥市监局:全市门店停业
天天微头条丨赛博2077支持DLSS3 iGame RTX 40显卡实战:性能2倍提升
河南三月飞雪 突降大雪竟与人工增雨有关
中金所就30年期国债期货合约征求意见
世界观速讯丨铭瑄发布旗舰级MGG RTX 4080、4070 Ti:丧心病狂5风扇、9热管
【焦点热闻】AMD份额涨不动了 专家称Intel的麻烦已结束:CPU竞争力更强
每日视点!山东一公司疑设卑劣人员从业跟踪岗:你去哪我就发函到哪
微头条丨铲屎官注意!研究表明养宠物或影响睡眠
热点评!你买过大船货吗?男子电动滑板车藏84个SSD入境被海关查获
全球新消息丨如何在Docker下部署nacos并注册Java服务
每日讯息!记录--vue中封装一个右键菜单组件(复制粘贴即可使用)
【新要闻】一汽奔腾销量惨淡,靠预售23.58万起的奔腾M9有望逆转吗?
天天快资讯:车主注意:新一轮国内油价降了!加满一箱油将少花4元
焦点要闻:全球最大集装箱船将在宁波舟山港开启首航:比航母还长
今日热讯:接二连三胜!长三乙火箭成功发射高分十三号02星
环球快资讯:《三体》动画播放量破5亿!豆瓣评分暴跌至3.9 差评率高达86%
票房已突破45亿!《满江红》宣布密钥再次延期
全球热门:“315”曝光:带货直播间水军泛滥,该如何应对?
天天观速讯丨债市日报:3月17日