C语言数据结构第一篇（绪论）

柔情只为你懂 2022-12-12 13:58 176阅读 0赞

今天开始学习C语言的数据结构，每天会在这个平台记录自己的学习，相当于学习笔记吧！一是可以作为督促自己每天坚持学习，二是可以见证自己成长的历程，当然，最大的愿望就是希望这些笔记对你们也有用，可以给你们一些帮助！！！  
**一、为什么要学数据结构？**  
程序设计=数据结构+算法  
因为数据结构可以让编程能力有质的飞跃，不仅仅局限于编写一些简单的问题，不用绞尽脑汁调用现成的东西，然而还不懂到底是什么意思！数据结构很难，我相信我可以坚持学下去嘿嘿！

**二、关于数据结构的一些基本概念**  
**数据**：所有能输入到计算机中并被计算机程序处理的符号的总称。  
**数据元素**：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。  
**数据对象**：性质相同的数据元素的集合，是数据的一个子集。  
**数据结构**：相互之间存在一种或多种特定关系的数据元素的集合。

**三、数据结构的形式定义**：  
数据结构是一个二元组：Data\_Structure = (D,S)  
D表示数据元素（有限集），S表示数据元素之间的关系。

**四、数据结构包含逻辑结构和物理结构**  
**逻辑结构：**  
逻辑结构主要有4中：分别是**集合结构**、**线性结构**、**树形结构**和**图状结构**（也称网状结构）。  
**集合结构**：各元素之间除了同属一个集合外没有其他的关系。  
**线性结构**：结构的数据元素之间存在一对一的关系。  
**树形结构**：结构的数据元素之间存在一对多的关系。（如家谱或族谱通常是树形结构）  
**网状结构**：结构的数据元素之间存在多对多的关系。（如各个城市之间的交通路线关系）

**物理结构：**  
物理结构（又称存储结构）主要有2中，分别是**顺序存储结构**和**链式存储结构**。  
**顺序存储结构**：如a1到an按照一定的顺序存储,a1到an一次排放。这种存储方式的特点就是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，假设地址相邻的两个元素相差两个字节，若a1的存储位置已知，则an的存储位置为：  
an=a1+2(n-1)  
![在这里插入图片描述][20201007190726690.png_pic_center]  
**链式存储结构**：  
它的特点就是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。  
这种存储方式每一个元素有数据域和指针域，指针域的作用是指向下一个数据的数据域。就像我们在医院排号时，我们所拿的号就相当于指针域，当医生叫到你手上的号的前一个号时，你就会高度紧张，这种方式你不用一直站在那里排队，可以自由的活动，只要注意医生喊号即可，从这里可以看出，链式存储结构比顺序存储结构更灵活。

**五、算法**  
**算法的5个重要特性：**  
（1）**有穷性**。一个算法必须在执行有限步后结束，且每一步都能在又穷的时间内完成。  
（2）**正确性**。每一条算法不能产生二义性，对于相同的输入必须有相同的输出。  
（3）**可行性**。算法中描述的操作都能通过已经实现的基本运算执行有限次来实现。  
（4）**输入和输出**。一个算法可以有0个或多个输入，一个算法必须有一个或多个输出。  
**算法设计的要求：**  
（1）**正确性**。正确性包括4个方面。算法程序没有语法错误；算法程序对于合法输入都能产生满足要求的输出；算法程序对非法输入能产生满足规格的说明，来提醒用户他输入错了；算法程序对于故意刁难的测试输入都有满足要求的输出结果。  
（2）**可读性**。算法方面人们阅读和交流。  
（3）**健壮性**。对非法输入算法也能做出反应或进行处理，不会产生莫名其妙的输出结果。  
（4）**高效率和低存储需求**。算法的执行时间尽量短，存储需求尽量小，执行时间短的算法效率高。

**六、算法效率的度量**  
有**事前分析估算法**（在计算机程序编写前，依照统计方法对算法进行估算）和**事后统计方法**（在程序编写完成后，对算法的效率进行估算）  
显然。用事后统计方法更好！  
关于算法效率的评价有时间复杂度和空间复杂度两个衡量标准。由于现在计算机的性能都比较好，所以一般考虑时间复杂度。关于这时间复杂度和空间复杂度的计算方法，比较复杂。明天针对这两个问题专门出一片博客。今天到此为止吧！晚安！

[20201007190726690.png_pic_center]: /images/20221123/6fab8d206e694bf9b4907e013e393426.png