数据结构学习，详解数据结构与算法知识(二)

本期继续学习数据结构与算法知识

也可以细分为以下四种基本类型：

集合结构：集合结构里面的元素关系是孤立的，仅同属于相同的集合。

线性结构：数据元素之间存在着一对一的线性关系。除第一个和最后一个元素外，每个元素只有一个前驱和一个后继数据元素。

树结构：数据元素之间存在这一对多的层次关系。除根结点外，每个数据元素只有一个前驱数据元素，可有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)算法的空间复杂度：