C语言数据结构001——数据结构的一些基本概念

小灰灰 2023-10-06 17:59 9阅读 0赞

> 程序设计=数据结构+算法  
> 数据结构包括：数据的逻辑结构，数据的存储结构，数据的操作  
> 算法是描述求解问题方法的操作步骤集合

## 一、数据的逻辑结构：数据元素之间的相互联系方式。 ##

1）线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。  
2）树状结构：除根结点外，每个数据元素只有一个前驱数据元素，可有０个或若干个后继数据元素。  
3）图状结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]

## 二、数据的存储结构：数据元素在计算机中的存储方式。 ##

1）顺序存储结构  
把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。(数组)

2）链式存储结构  
每个结点除了存储数据元素以外还存储另外数据元素的地址。  
指针: 是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。  
使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。

## 三、数据的操作：一种数据类型允许进行的某种操作，一种数据类型数据所有的操作称为数据的操作集合。（算法设计） ##

> 程序设计=数据结构+算法

## 四、算法 ##

### 4.1、算法满足以下5个性质: ###

(1)输入性  
作为算法加工对象的量值，通常体现为算法中的一组变量。  
(2)输出性  
它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果。  
(3)有限性  
对于任意一组合法输入值，在执行有穷步骤之后一定能结束，算法中的每个步骤都能在有限时间内完成！  
(4)确定性  
对于每种情况下所应执行的操作，在算法中都有确切的规定！  
(5)可执行性  
算法中的每一步都必须足够基本，可以通过已经实现的基本操作运算有限次实现！

### 4.2、算法设计满足以下5个目标: ###

(1)正确性  
(2)可读性  
(3)健壮性  
(4)高时间效率  
(5)高空间效率  
注：算法的高时间效率和高空间效率通常是矛盾的！

### 4.3、算法的时间复杂度分析的两种方法 ###

1）事后统计方法  
2）事前分析方法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210622090559868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70