《数据结构》第1章 数据结构与算法分析概述（C语言描述）

本文主要是介绍《数据结构》第1章 数据结构与算法分析概述（C语言描述），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.1数据结构概述

1.1.1 数据结构的含义

数据结构和算法是程序设计最重要的两个内容。

简单的说，数据结构是数据的组织，存储和运算的总和。它是信息的一种组织方式，是以数据按某种组织关系起来的一批数据，其目的是为了提高算法的效率，然后用一定的存储方式存储到计算机中，并且它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

在计算机处理的大量数据中，它们都是相互关联，彼此联系的。
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作，因此，主要有三个方面的内容，数据的逻辑结构，数据的物理结构，对数据的（或算法），通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

1.1.2数据结构的基本术语

1. 数据（Data）
数据即信息的载体，是对客观事物的符号表示，指能输入到计算机中并被计算机程序处理的符号的总称。如整数，实数，字符，文字，声音，图形，图像等都是数据。

2. 数据元素（Data Element）
数据元素是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体考的对象。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时，常称为记录，结点等。数据项也称为域，字段，属性，表目，顶点。

3. 数据对象（Data Object）
数据对象是具有相同特征的数据元素的集合，是数据的一个子集。

4. 数据结构（Data Structure）
数据结构简称 DS，是数据元素组织形式，或数据元素相互之间存在一种或多种特定关系的集合。任何数据都不是彼此孤立的，通常把相关联的数据按照一定的逻辑关系组织起来，按照计算机语言的语法，语义的规定相应的存储结构或形式，并且为这些数据指定一组去处操作，这样就形成了一个数据结构。
数据结构通常有四类基本形式：集合形式，线性结构，树型结构，图形结构或网状结构。

5. 数据的逻辑结构（Logical Structure）
数据的路逻辑结构是指数据结构中数据元素之间的逻辑关系，它是从具体问题中抽象出来的数学模型。是独立于计算机存储器的（与具体的计算机无关）。

6. 数据的存储结构（PhysicalStructure）
数据的存储结构是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据存储结构的实现要用计算机语言来实现，因而是依赖于具体的计算机语言。数据存储结构有顺序和链式两种不同的方式，诉特点是要数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系。顺序存结构通常用高级编程语言中的 一维数组 来描述或实现。而链式存储结构则通常用链表来实现。

在有顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储，和散列存储。
索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时查找效率，避免盲目查找。

散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可以大大提高效率。

7. 数据类型（Data Type）
数据类型是一组具有相同性质的操作对象以及该组操作对象以及该组操作对象上的运算方法的集合。如整数类型，字符类型等。每一种数据类型都有自身特点的一组操作方法（即运算规则）。

8. 抽象数据类型（Abstract Data Type）
抽象数据类型是指一个数据模型以及在该模型上定义的一套运算规则的集合。在对抽象数据类型进行描述时，要考虑到完整性的广泛性，完整性就是要能体现所描述的抽象数据类型的全部特性，广泛性就是所定义的抽象数据类型适用的对象要广。在大型程序设计和系统软件开发中，对抽象数据类型用的较多。

1.2算法分析概述

提到算法，必须提到数据结构，我们要知道一个著名公式：

数据结构 + 算法 = 程序

我们先看看下面这张图：

图1

算法是什么？算法是一个有穷规则（或语句、指令）的有续集和。他确定了解决某一问题的一个运算序列，简单的说，就是解决某一问题的步骤描述。

1.2.1算法的特性

1）有穷性 ——算法执行的步骤（或规则）是有限的；
2）确定性 ——每个计算步骤无二义性；
3）可行性——每个计算步骤嫩巩固在有限的时间内完成；
4）输入——算法有一个或多个外部输入；
5）输出——算法有一个或多个输出；

1.2.2评价一个算法的好坏

1）消耗时间的多少；
2）消耗存储空间的多少；
3）算法的设计是否容易理解，是否容易编程实现，方便调试和维护；

1.2.3时间复杂度

时间复杂度的概念：
1）问题的规模：输入数据量的大小，用n来表示；
2）算法的时间复杂度：算法消耗时间，它是问题规模的函数 $T（n）$。

1.2.3.1语句的频度

语句的频度定义为可执行语句在算法（或程序）中重复执行的次数。若某语句执行一次的时间为$t$ ，执行次数为$f$，则该语句所耗时间的估计为$t\ast f$ 。以下面程序为例，求两个N阶方阵乘积：

void MATRIXM(A,B,C)  
{  float A[n][n],B[n][n],C[n][n];  int i,j,k;                                                 // 语句频度  for(i = 0;i < n; i++)                                      //   n+1  for(j = 0;j < n;j++)                               //  n(n+1)  {  C[i][j] = 0;                                  //   n*n  for(k = 0; k < n;k++)                        //  n*n(n+1)  C[i][j] = c[i][j]+A[i][k]*B[k][j];     //   n*n*n  }  
}  

1.2.3.2算法的时间复杂度

算法的时间复杂度定义为算法中可执行语句的频度之和，记为T(n)。T(n) 是算法所需时间的一种估计，其中n为问题的规模（或大小、体积）。如上面的例子中，问题的规模n为矩阵的阶，该算法的时间复杂度为：

$$T(n)=(n+1)+n(n+1)+n\ast n+n\ast n(n+1)+n\ast n\ast n=2\ast n\ast n\ast n+3\ast n\ast n+2\ast n+1$$

当$n$趋于无穷大时，$lim(T(n)/(n\ast n\ast n)=2$，故$T(n)$与$n\ast n\ast n$为同阶无穷大，或者说$T(n)$ 与$n\ast n\ast n$成正比、$T(n)$的量级为$n\ast n\ast n$，记为$T(n)=O(n\ast n\ast n)$;
问题规模$n$的某个函数$f(n)$,

$$T(n)=O(f(n))$$
它表示岁问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

这篇关于《数据结构》第1章 数据结构与算法分析概述（C语言描述）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---