本期继续学习数据结构与算法知识
也可以细分为以下四种基本类型:
集合结构:集合结构里面的元素关系是孤立的,仅同属于相同的集合。
线性结构:数据元素之间存在着一对一的线性关系。除第一个和最后一个元素外,每个元素只有一个前驱和一个后继数据元素。
树结构:数据元素之间存在这一对多的层次关系。除根结点外,每个数据元素只有一个前驱数据元素,可有0个或若干个后继数 据元素。
图结构:数据元素之间存在着多对多的任意关系。每个元素可有0个或若干个前驱数据元素和0个或若干个后继数据元素。
4.数据的存储(物理)结构
定义:物理结构是指数据的逻辑结构在计算机中的存储形式。存储结构有两种:
顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。
算法:
1.定义:算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
2.算法的五个重要特性:
(1)有穷性:一个算法包含有限个操作步骤。一个算法在执行若干个步骤之后应该能够结束,而且每一步骤都在有限时间内完成。
(2)确定性:算法中的每一步骤必须有确切的含义,不能产生二义性。
(3)可行性:算法中的每一步骤都应该是能有效地执行,并得到确定的结果。
(4)输入:一个算法可以有零个或多个输入。
(5)输出:一个算法有一个或多个输出。没有输出的算法是毫无意义的。
3.算法设计的要求:
算法设计的好坏关乎程序执行效率,算法的设计必须满足下列四个要求:
(1)正确性:正确性是指算法达到了测试要求。
(3)可读性:指人对算法的理解,可读性高便于交流,有利于算法的调试和修改
(3)健壮性:对于非法输入的数据,算法能给出相应的响应,阻止不可预料的后果的产生
(4)效率与低存储量需求:效率指算法的执行时间,执行时间短的算法效率高。存储量需求是指算法执行过程中所需的最大存储空间,存储量需求越小的算法效率越高。
4.算法的分析:
(1)算法效率的度量:算法执行时间是其对应的程序在计算机上运行所消耗的时间。程序在计算机上运行所需时间与下列因素有关:
1)算法本身选用的策略
2)书写程序的语言
3)编译产生的代码质量
4)机器执行指令的速度
5)问题的规模
其中算法本身选用的策略是算法好坏的根本,书写程序的语言和编译产生的代码质量要看具体的软件支持。
(2)算法的时间复杂度:
可以用算法中语句的执行次数来度量一个算法的效率。
(3)算法的空间复杂度: