数据、数据元素、数据项和数据对象数据Data是信息的载体是客观事物的符号表示是所有能输入计算机中并被计算机程 序处理的符号的总称。如数学计算中用到的整数和实数等数值类型文本编辑中用到的字符串 多媒体程序处理的图形、图像、声音及动画等非数值类型它们通过特殊编码定义后的数据。数据元素Data Element是数据的基本单位在计算机中通常作为一个整体进行考虑和处 理。在有些情况下数据元素也称为元素、记录、结点等。数据元素用于完整地描述一个对象 如前一节示例中的一名学生记录树中棋盘的一个格局状态以及图中的一个顶点等。数据项Data Item是组成数据元素的、有独立含义的、不可分割的最小单位。例如学 生基本信息表中的学号、姓名、性别等都是数据项。数据对象Data Object是性质相同的数据元素的集合是数据的一个子集。例如整数 数据对象是集合N {0, ±1, ±2, …}字母字符数据对象是集合C {‘A’, ‘B’, … ,‘Z’, ‘a’, ‘b’, …, ‘z’} 学生基本信息表也可以是一个数据对象。由此可以看出不论数据元素集合是无限集如整数 集或是有限集如字母字符集还是由多个数据项组成的复合数据元素如学生基本表 的集合只要集合内元素的性质均相同都可称之为一个数据对象。人话翻译数据没有加工过的原始符号。表里那些 2023001、张三、男 就是数据是信息的原材料。数据项最小的、不可再分的单位相当于表格里的一列一个字段比如 学号 姓名 。数据元素由若干数据项组成的一个个体相当于表格里的一行比如某一名学生的完整记录。数据对象性质相同的数据元素的集合相当于整张表比如全体学生记录。数据是 字数据项是 列数据元素是 行数据对象是 整张表。例·学生信息表地址学号姓名性别籍贯专业0114李田所男下北泽厨师501145田所浩二男下北泽厨师10011451李荣男下北泽厨师150114514德川男东京厨师概念人话理解在 学生信息表 里的位置例子数据没加工的原始符号信息的原材料单元格里的内容114、李田所、男数据项不可再分的最小字段一列地址、姓名、性别、专业数据元素一个完整个体整体处理一行一条学生记录0 114 李田所 男 下北泽 厨师数据对象性质相同的数据元素的集合整张表全体学生记录数据结构结构本质上是一种组织关系它揭示了元素间的相互联系和排列顺序。数据结构Data Structure是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包含逻辑结构存储结构数据结构的三要素逻辑结构、存储结构、数据运算数据的逻辑结构是从逻辑关系上描述数据它与数据的存储无关是独立于计算机的。数据的逻辑结构的两要素数据元素关系数据的逻辑结构可分为集合结构、线性结构、树形结构、图形结构前驱与后继前驱直接前驱在逻辑上排在前面紧邻的那个结点。后继直接后继在逻辑上排在后面紧邻的那个结点。集合结构数据元素关系是否属于同一集合线性结构数据元素关系一对一结构特点①有且只有一个开始结点无前驱②有且只有一个终端结点无后继③其余每个结点有且只有一个[前驱]和[后继]例 a-b-c-d-e 有且只有一个开始结点aa无前驱 有且只有一个终端结点ee无后继 其余每个结点有且只有一个前驱、后继 但a-b-c-d-b-e 其中b存在两个后继c、d 不满足线性结构特性属于非线性结构树结构数据元素关系一对多特点①存在唯一根结点且根结点无前驱②除根节点外其余结点有且仅有一个前驱父节点③结点存在0个或多个后继子结点④不准出现回路、环相关名词根结点最顶层无前驱。​父结点某个结点的直接前驱。​子结点某个结点的直接后继。​叶子结点没有孩子后继的结点。​子树一个结点和它所有后代构成的部分。图结构数据元素关系多对多特点①结点可以0个、1个或多个前驱②结点可以0个、1个或多个后继③允许存在回路环​ ④没有唯一的根结点没有严格的父子关系逻辑结构元素间关系一句话典型代表集合结构无关系只是 放一起集合 Set、班级花名册线性结构一对一一条线串起来数组、链表、栈、队列树形结构一对多像族谱有根有分支二叉树、文件夹目录图形结构多对多像网四通八达社交网络、地图路径集合结构·花名册 线性结构·队列树形结构·族谱 图形结构·电路图基本数据结构存储结构数据对象在计算机中的存储表示称为数据的存储结构也称为物理结构。存储结构是 逻辑结构的存储映像顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的通常 借助程序设计语言的数组类型来描述。链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中而链式存储结构无须占用一整块存储空间。但为了表示结点之间的关系需要给每个结点附加指针字段用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述存储结构关键思想逻辑相邻与物理位置查找特点典型代表顺序挨着放逻辑相邻 物理相邻按下标直接算地址随机访问快数组链式指针串物理可任意散开要顺着指针一个一个找链表索引建目录数据区 一张索引表先查索引表再跳过去定位数据库索引、书目录散列函数算地址由关键字直接定位格子平均一步到位冲突时处理HashMap、字典算法的定义和特性算法解决某类问题而规定的一个有限长的操作序列特性输入一个算法有0个或多个输入 参考scanf或Scanner输出一个算法有一个或多个输出 如打印Hello,World确定性对于每种情况下所应执行的操作不会产生二义性使执行者和阅读者能明确含义和执行有穷性一个算法必须总是在执行有穷步后结束且每一步都必须在有穷时间内完成while(1)死循环不满足有穷性可行性算法中的每条指令都是可执行的项目内容定义算法是对解决问题的一系列明确、有序操作步骤的描述是有限条指令的集合按照指令执行可以在有限步骤内得到问题的解。有穷性一个算法必须总是在执行有限步之后结束每一步都在有限时间完成不能无限循环。确定性算法中每一条指令含义明确相同输入一定得到相同输出不存在二义性。可行性算法中的每一步操作都可以实现能通过基本运算完成。输入0 个或多个输入取自指定对象集合。输出至少 1 个输出是算法计算得到的结果。算法优劣评价标准评价标准说明时间复杂度算法运行需要的时间。主要看语句执行次数关注随输入规模 n 增大时时间增长趋势越低越好。空间复杂度算法执行占用的内存空间。看临时变量所占存储额外空间越少越好。正确性算法对合法输入能够得到正确结果这是最基础要求。可读性代码逻辑清晰、便于人阅读理解、调试和维护。健壮性鲁棒性遇到非法输入、异常情况时算法不会崩溃能恰当处理。时间复杂度问题规模指问题输入数据量的大小是衡量输入多少的一个量一般用 n 表示。如求 n 个数的和这里数字的个数n就是问题规模数组有n个元素n就是规模。算法的时间、空间开销通常会随着n的变化而改变。语句频度又叫语句的执行次数。指算法里某一条语句在整个算法运行过程中总共被重复执行次数。算法的时间复杂度一般的算法中基本语句重复执行次数是问题规模n的某个函数,算法的时间量度记为其表示随着问题规模n的增大算法执行时间的增长率和的增长率相同称为算法的渐进时间复杂度简称时间复杂度时间复杂度计算定理加法定理多顺序代码块如果一段程序由前后顺序执行的 A、B 两部分组成则复杂度乘法定理A 循环里面套 B 循环则时间复杂度取最高次幂规则定理若则时间复杂度例1·顺序代码加法规则int i,sum0; for(i1;in;i) sumi; // T₁(n)nO(n) for(i1;in;i) for(j1;jn;j) sum; // T₂(n)n²O(n²)总时间复杂度例2·双层嵌套循环乘法规则int i,j; for(i1;in;i) //外层O(n) for(j1;ji;j) //内层最多i次 printf(hi); i 1,j1,hi循环1次 i 2,j2,hi循环2次 i 3,j3,hi循环3次 ... hi执行的语句频度123...n n·(n1)/2时间复杂度例3·三层循环乘法int i,j,k; for(i1;in;i) //T(n) O(n) for(j1;jn;j) //T(n) O(n) for(k1;kn;k) //T(n) O(n) printf(a);时间复杂度例4·log 对数复杂度int i1; while(i n){ i * 2; }循环次数时间复杂度例5·nlog nint i,j; for(i1;in;i){ //外层n次 j1; while(jn){ //内层logn次 j *2; } }时间复杂度例6·常数复杂度 O (1)int a,b; scanf(%d%d,a,b); int cab; printf(%d,c);//仅执行1次时间复杂度例7·带 if 分支取最坏情况int i; if(n100){ for(i1;in;i) printf(x); //执行n次 }else{ for(i1;in*n;i) printf(x);//执行n²次 }时间复杂度例8·多项式化简已知则