当前位置: 首页 > news >正文

第一章

数据结构(Data Structure)--研究数据的特性及数据之间存在的关系
一:什么是数据结构
数据结构:用计算机解决一个具体的问题时,需要以下几个步骤---首先从具体问题种抽象出一个适当的数学模型,然后设计一个能解此数学模型的算法(Algorithm),最后编出程序,进行测试,并调整程序直至得到最终解答。(Insert插入,Delete删除,Modify修改)
在数据结构中,数据之间的关系主要有两种,它们分别是线性关系和非线性关系,其中非线性关系又可以分为树型关系和图关系。
*-数据结构是指数据之间的相互形式,即数据的组织形式,数据结构分为逻辑结构和存储结构。逻辑结构是指数据元素之间的逻辑关系:存储结构是指数据元素及其关系在计算机内的表示。

二:数据(Data)
人们利用文字符号,数字符号及其他规定的符号对现实世界的事物及其活动所做的描述;在计算机科学中,数据的含义非常广泛,一切能输入计算机钟并且能被计算机程序处理的信息(文字,表格,声音,图像等等)都成为数据。
*-数据是对客观事物的符号表示
-数据项(数据元素)是指具有独立含义的最小识别单位(数据中不可分割的最小单位)。数据项又称 项/字段。
三:数据元素(Data Element) 最小单位是二进制数的一位(bit)
一般情况下,一个结点含有若干个字段(也叫数据项)。
四:数据对象(Data Object)
也称为数据元素类(Data Element Class),具有相同性质的数据元素集合,某个具体问题中,数据元素都具有相同的性质(元素值不一定相等),属于同一数据对象(数据元素类),数据元素是数据元素类的一个实例。
五:数据结构(Data Structure)可记 D,R(D是数据元素的有限集合,R是D上的关系)
1.集合结构:数据元素之间的关系-属于同一个集合。集合是元素关系极为松散的一种结构。
2.线性结构:数据元素之间存在着一对一的关系。
3.树形结构:数据元素之间存在着一对多的关系。
4.图形结构:数据元素之间存在着多对多的关系。图形结构也称作网状结构
六:逻辑结构(Logical Construction)
结点和结点之间的逻辑关系称为数据的逻辑关系。
七:存储结构(Storage Construction)
数据及数据之间的关系在计算机中的存储表示称为数据的存储结构。
1.顺序存储方法-将逻辑上相邻的结点存储在物理位置上想论的存储单元中,结点间的逻辑关系有存储单元的邻接关系体现。 顺序存储结构(Sequential Storage Structure)主要应用于线性数据结构
2.链接存储方法-不要求逻辑上的相邻的结点在物理位置上也相邻,结点间的逻辑关系由附加的指针字段表示。 链式存储结构(Linked Storage Structuer)通常借助于程序语言的指针类型描述
3.索引存储方法-在存储结点信息的同时,建立附加的索引表。索引表由若干索引项组成,每个结点在索引表中都有一个索引项,称为稠密索引(Dense Index);若一组结点在索引表中只对应一个索引项,称为稀疏索引(Spara Index)。索引项的一般形式(关键字,地址)-关键字唯一标识一个结点的数据项。稠密索引中索引项的地址指示结点所在的存储位置;稀疏索引中索引项的地址指示一组结点的起始存储位置。
4.散列存储方法-根据结点的关键字直接计算出该结点的存储地址。
八:数据处理(Data Processing)
是指对数据进行查找,插入,删除,合并,排序,统计及简单计算等操作的过程。
九:抽象数据类型(Abstract Data Type,ADT)
由一种数据模型和在该数据模型上的一组操作组成。抽象数据类型包括定义和实现两个方面,其中定义是独立于现实的。抽象数据类型的定义仅取决于它的逻辑特性,而与其在计算机内部的实现无关。(输入与输出定义)
ADT=(D,S,P)--D是数据对象;S是D上的关系集;P是加在D上的一组操作。当定义抽象数据类型时,可以使用一下格式
ADT 抽象数据类型名{
_____数据对象:<数据对象的定义>
_____数据关系:<数据关系的定义>
_____基本操作:<基本操作的定义>
}
数据对象和数据关系的定义用伪码来描述,基本操作的定义格式为:
基本操作名(参数表)
基本条件:<初始条件描述>
操作结果:<操作结果描述>
十:算法
1.完整算法: 正确性;确定性;有穷性;有效性;可终止性
2.算法是执行特定计算的有穷过程(可以没有输入,但要有输出)5个特点:动态有穷;确定性;输入;输出;可行性【每条指令都充分基本,原则上由人仅用笔和纸在有限的时间内也能完成】
算法和程序是通用的
3.算法设计要求
正确性;可读性;健壮性;效率与存储量需求
4.算法分析
主要是指判断算法的优劣,判断算法的好坏从两个方面考虑:从时间角度;从空间角度上衡量算法。一般算法分析从时间角度考虑的比较多,也不能只以时间或空间衡量简单化,要根据实际情况综合考虑。
度量一个程序的执行时间:(1)事后统计方法。(2)事前分析估算的方法
5.算法描述的分析:
将算法的求解问题输入称为问题的规模,用整数n表示。
每个步骤中可能有若干条语句,而频度就是指每条语句的执行次数,一个算法的时间复杂度是指算法的时间耗费。当问题的规模n取趋向无穷大时,我们把四家复杂度的数量阶称为算法的渐进时间复杂度。
一般称为 算法的时间复杂度,记做"O"(Order)他有着严格的数字定义:
T(n)和f(n)在定义是正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常熟C和n0,使得当n>=n0时满足0<=T(n)<=C
f(n)
空间复杂度(Space Complexity)类似于时间复杂度,该算法耗费的存储空间,也是问题规模n的函数一般指渐进空间复杂度。记作:S(n)=O(f(n))其中n是问题的规模(大小)

http://www.hskmm.com/?act=detail&tid=30654

相关文章:

  • 生成式AI基础设施面临网络攻击威胁:企业安全新挑战
  • 数据结构笔记
  • 实用指南:SQL Server从入门到项目实践(超值版)读书笔记 27
  • VMware ESXi 9.0.1.0 macOS Unlocker OEM BIOS 2.7 H3C 新华三 定制版
  • LGP8866 [NOIP 2022] 喵了个喵 学习笔记
  • edge每次打开不是用自己的账户,还要选择一次
  • LibreOffice Impress播放不出视频的解决方法
  • VMware ESXi 9.0.1.0 macOS Unlocker OEM BIOS 2.7 Inspur 浪潮 定制版
  • Exchange 异常关机后无法登录owa/ecp 以及ems无法连接远程服务器
  • 【GitHub每日速递 251014】Claude Code:用自然语言命令让编码快到飞起!
  • 新项目完结,Ai Agent 智能体、拖拉拽编排!
  • 硅谷大佬揭秘创业者成功法则
  • 2025年南通宠物医院最新权威推荐榜:专业诊疗与暖心服务口碑之选
  • 2025年10月学校家具定制厂家最新推荐排行榜,课桌椅,宿舍床,图书馆家具,教室家具公司推荐!
  • 2025年10月螺杆泵厂家最新推荐排行榜,单螺杆泵,双螺杆泵,三螺杆泵,高效耐用品质之选!
  • 2025年恒温恒湿系统厂家最新推荐榜单,精加工车间/厂房/美术馆/仓库/计算机房/档案室/工业/工厂车间恒温恒湿系统公司推荐
  • 2025年会议系统厂家最新推荐排行榜,专业音视频会议系统,智能会议解决方案,高清视频会议系统公司推荐!
  • RSA密钥生成基准测试深度解析
  • MaxKB 在不同场景下 RAG 引擎与向量存储的应用案例分析
  • C#数组
  • 251013
  • 简谈误差与不确定度
  • 可怕!我的Nodejs系统因为日志打印了Error 对象就崩溃了 Node.js System Crashed Because of Logging an Error
  • 前言
  • 实践
  • 数据结构字符串和图
  • 字典dict
  • 结婚证识别技术:融合计算机视觉、深度学习与自然语言处理的综合性AI能力的体现
  • 上下文丢失
  • 数据结构序列