数据结构与算法概述
数据结构与算法概述
开发工具与关键技术：Visual Studio 2015 数据结构与算法概述
作者：李国旭
撰写时间：2020年4月26日
什么是“数据结构”，我们可以从最开始接触到的说起：那就是一个数据库的设计，而数据库中里面也有数据类型和长度。数据库和数据结构的相同点就是：数据库中表的关系有，一对一和多对多、一对多的关系；长度呢，就跟我们的算法的时间的复杂度有些相似，只不过它们的性质处理方面不一样而已。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成。即一个数据由那些成分数据构成，以什么方式构成，是什么结构。
目前，最关键的一个问题就是说：如何编写出有一个高效率的处理程序，就需要解决如何合理地组织数据，建立合适的数据结构，还有设计一个较好的算法；这些都是用来提高程序执行效率。对此，瑞士著名的计算机科学家尼古拉斯.沃思，他提出了“算法＋数据结构＝程序”这样的观念。
一、数据结构
（1）线性结构。结构中的数据元素之间存在着一对一的线性关系。（2）树结构。结构中的数据元素之间存在着一对一的层次关系。（3）图结构。结构中的数据元素之间存在着多对多的关系。
如下图所示：三种基本的逻辑结构
也就是说，1、线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。2、树结构：除根节点外，每个数据元素只有一个前驱数据元素，可有0个或若干个后继数据元素。3、图结构：每个数据元素可有0个或若干个前驱数据元素和0个或若干个后继数据元素。
上面的就是我们所说数据的逻辑结构，当然了最重要的还是我们的算法设计，它是取决于数据的逻辑结构；而我们的算法的实现也是取决于数据的物理存储结构，这是不可或少的一个环节。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有以下五个重要特性。
- 有穷性：一个算法应包含有限个操作步骤。即一个算法在执行若干个步骤之后应该能够结束，而且每一步都在有限时间内完成。
- 确定性：算法中的每一步都必须有确切的含义，不能产生二义性。
- 可行性：算法中的每一个步骤都应该是能有效地执行，并得到确定的结果。
- 输入：所谓输入，是指在算法执行时，从外界取得必要的数据。计算机运行程序的目的是为了进行数据处理，在大多数情况下，这些数据需要通过输入得到。有些情况下，数据已经包含在算法中，算法执行时不需要任何数据，所以一个算法可以有零个或多个输入。
- 输出：一个算法有一个或多个输出，这是算法进行数据处理后的结果。没有输出的算法是毫无意义的。
二、下面就是我们算法的时间复杂度：记作T(n)=O(f(n))
T(n)随n的增大而增大，增长得越慢，其算法的时间复杂度越低。那么一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。语句执行一次实际所需的具体时间是与机器的速度、编译程序质量、输入数据等密切相关，与算法设计的好坏无关。所以，可用算法中语句的执行次数来度量一个算法的效率。像我们平时用的for循环语句一样，循环的次数越多；所需的时间也是相应的增加。
首先定义算法中一条语句的语句频度，语句频度是指语句在一个算法中重复执行的次数。以下给出了两个n×n阶矩阵相乘算法中的各条语句以及每条语句的语句频度。例如下面的这个语句一样！（此语句转载自唐懿芳教授的文档）
语句 语句频度
for（i=0；i< n;i++） n＋1
for （j=0；j<n;j++） n2＋n
{
c[i][j]=0; n2
for (k=0;k< n; k++) n3＋n2
c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3
}
三、下面我们来了解一下数据的存储结构
（1）线性表的存储方式：它有两种存储方式一种是顺序表和链表。
顺序表的特点：就是元素按顺序存放，它的地址是连续的。
有存放当然也有插入和删除了，下面的就是顺序表的插入。
如图所示：
在3的这个位置插入一个X这个字符，那么后面的（a3、a4、a5）这三个都必须往后移一格，也就是说从最后面的那个a5开始往后开始移，给X这个字符留出足够的空间，把X存放进来。为什么呢？因为如果我们从前开始往后移，它就会把后面的元素冲掉。在这个插入的时候，还要判断一下顺序表开辟的存储空间是否已经满了，满了的话呢！那就无法插入了。同理，就好像我们在做那个项目的新增和删除、修改的时候一样，都要先判断一下数据库里面是否存在这条数据，没有就新增，修改、删除也一样是这样的操作。
这个时候我们就要注意了，在删除的时候要注意备份；删除的元素要挨个往前移一格，这样才能保证地址的连续存放的特点。那么在这里我们就要注意了，如果我们的顺序表原来就是空的，那就谈不上删除了；如果size等于0，直接返回顺序表为空
（2）线性表的链式表示和实现
然而，链表不是地址连续的空间，他的插入和删除不需要移动元素，它看到内存有空余地址就可以毫无顾忌地挤进去。
单链表的结构：单链表中构成链表的结点只有一个指向直接后继结点的指针域。
结构特点;逻辑上相邻的数据元素在物理上不一定相邻。
他们呢又有两个域，一个是数据域和指针域，那么什么又是数据域呢？它就是用来存储元素数值数据的，另一个指针域就是用来存储直接后继存储地址。而且它也不需要地址连续的单元来存储线性表。不管是插入还是删除，它们都要先定位在前一个元素。
如下图所示：插入和删除
