前言：

       今天我们正式开始一个新的专栏——初阶数据结构（C语言实现），本专栏后续持续更新时间复杂度空间复杂度、顺序表、链表、栈和队列、二叉树、排序等算法的相关知识，欢迎大家互相学习，可以私信互相讨论哦！

一、基本概念和术语

1、数据（Data）

       （1）是所有能输入计算机且能被计算机程序处理的各种符号的集合；

       （2）是对客观事物的符号表示；

       （3）信息的载体；

       （4）能够被计算机识别、存储和加工；

       （5）数据的含义广泛，包括：①数值型数据——整数、实数等；②非数值型数据——文字、图像、声音等。

2、数据元素（data element）

      （1）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；（例如：学生表中一个学生的信息为一个数据元素）

       （2）也称为元素。或称为记录、结点或顶点；

       （3）一个数据元素可由若干个数据项组成。（例如：学生表中一个学生信息为一个数据元素，而学生信息中的每一项（如姓名、年龄等）为一个数据项）

3、数据项

       （1）构成数据元素的不可分割的最小单位；

       （2）数据、数据元素、数据项三者之间的关系：数据 > 数据元素 > 数据项（如：学生表 > 学生信息 > 学号、姓名等）

4、数据对象（data obiect）

       （1）数据对象

               ①是性质相同的数据元素的集合，是数据的一个子集；

               例如：整数数据对象是集合 N = {0，1，-1, 2，-2……}

（2）数据元素与数据对象

               ①数据元素——组成数据的基本单位，与数据的关系：是集合的个体；

               ②数据对象——性质相同的数据元素的集合，与数据的关系是：集合的子集。

二、什么是数据结构

1、数据结构（data structure）

      （1）数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

       （2）数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构

       （3）或者说，数据结构是带结构的数据元素的集合。

       （4）数据结构的形式定义为：数据结构是一个二元组

               Data Structure = （D，R）

       其中：D是数据元素的有限集，S是D上关系的有限集。

2、数据结构包括以下三个方面的内容：

       （1）结构定义中的“关系”描述的是数据元素之间的逻辑关系，也称为逻辑结构。

       （2）数据结构在计算机中的表示（又称映像），称为数据的物理结构或存储结构。（它包含数据元素的表示和关系的表示）

      （3）数据的运算和实现，即对数据元素可以实施的操作以及这些操作在相应的存储结构上的实现。

3、数据结构的两个层次

       （1）逻辑结构

               ①描述数据元素之间的逻辑关系；

               ②与数据的存储无关，独立于计算机；

               ③是从具体问题抽象出来的数学模型。

（2）存储结构（物理结构）

               ①数据元素及其关系在计算机存储器中的结构（存储方式）

               ②是数据结构在计算机中的表示

（3）逻辑结构与存储结构的关系：

               ①存储结构是逻辑关系的映像与元素的映像；

               ②逻辑结构是数据结构的抽象，存储结构是数据结构的实现；

               ③两者综合起来建立了数据元素之间的结构关系

4、逻辑结构的种类

划分方法一：

1）线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后趋。（例如：线性表、栈、队列、串）

2）非线性结构：一个结点可能有多个直接前趋和直接后趋。（例如：树、图）

划分方式二 —— 四类基本逻辑结构

       （1）集合结构：结构中的数据元素之间除了同属一个集合的关系外，无任何其它关系。

       （2）线性结构：结构中的数据元素之间存在一对一的线性关系。

       （3）树形结构：结构中的数据元素之间存在着一对多的层次关系。

       （4）图状结构或网状结构：结构中的数据元素之间存在多对多的任意关系。

5、存储结构的种类

四种基本的存储结构：

       （1）顺序存储结构：

         ①用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。

         ②C语言中用数组来实现顺序存储结构，例如：

（2）链式存储结构：

               ①用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针表示。

               ②C语言中指针来实现链式存储结构，例如：

（3）索引存储结构

（4）散列存储结构

总结：数据结构 —— 就是在内存中管理数据。

三、什么是算法

1、算法（algorithm）的定义：

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中指令表示一个或多个操作。

       简而言之：算法就是一系列的计算步骤，用来输入数据转化成输出结果。

2、算法的描述：

       （1）自然语言：中文、英文等

       （2）流程图：传统流程图、NS流程图

       （3）伪代码：类语言——类C语言

       （4）程序语言：C语言

3、算法特性：

算法特性：一个算法必须具备以下五个重要特性

       （1）有穷性：一个算法必须总是在执行又穷步之后结束，且每一步都在又穷时间内完成。

       （2）确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

       （3）可行性：算法是可行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

       （4）输入：一个算法有零个或多个输入。

       （5）输出：一个算法有一个或多个输出。

4、算法设计的要求

（1）正确性（correctness）：算法满足问题要求，能正确解决问题；

       算法转化为程序后要注意：

       ①程序中不含语法错误；

       ②程序对于几组输入数据能够得出满足要求的结果；

       ③程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据都能得出满足要求的结果

       ④程序对于一切合法的输入数据都能得出满足要求的结果。

               通常以第三层意义上的正确性作为衡量一个算法是否合格的标准。

（2）可读性（readability）：

             ①算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解

             ②另一方面，晦涩难读的算法易于隐藏较多错误而难以调试

（3）健壮性（robustness）：

               ①指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。

               ②处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

（4）高效性（efficency）：要求花费尽量少的时间和尽量低的存储要求。

5、算法与程序

      （1）算法：就是一系列的计算步骤，用来将输入数据转化成输出结果，一个问题可以有多种算法。

       （2）程序：就是用某种程序语言对算法的具体实现。

程序 = 数据结构 + 算法

               ①数据结构通过算法实现操作

               ②算法根据数据结构设计程序

四、数据结构和算法的重要性

1、数据结构是计算机软件相关专业的专业基础课

2、在教学计划中的地位：核心、承上启下的课程

3、考研：必考专业；

4、找工作面试，笔试的重点考核内容

总结：类似与练武的“内功”！

五、如何学好数据结构和算法

1、死磕代码：不要光想，要多多上机练习。

2、注意画图和思考：数据结构是复杂的，所以我们要多动手画图，多思考帮助我们理解。

数据结构的一些基础概念和术语我们就学完了，下一次我们开始正式讲解时间复杂度空间复杂度。

如果有错误，可以私信，互相讨论哦！！！