我打开了封印多年的数据结构C语言笔记——绪论

数据结构与算法极速入门系列其他文章

数据结构与算法极速入门系列（更新ing）

什么是数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素集合。
数据结构：关心数据元素之间的相互关系与组织方式、运算及规则，不涉及数据元素的具体内容。

为什么学习数据结构

《数据结构》是计算机软件专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件，是编好程序的基础。

计算机解决问题的一般过程

当今计算机应用的特点：

所处理的数据量大且具有一定的关系

对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

举个简单的例子

表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构。

数据类型

数据结构从逻辑上可以分为四种结构：

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
线性结构：结构中的数据元素之间存在着一对一的线性关系。
树形结构：结构中的数据元素之间存在着一对多的层次关系。
图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

什么是算法

高德纳(Donald Ervin Knuth)——经典巨著《计算机程序设计的艺术》的年轻作者。

引用大佬的话：

“A finite set of rules which gives a sequence of operations for solving a specific type of problem.”

算法是规则的有限集合，是为解决特定问题而规定的一系列操作。

算法、语言、程序的关系

Niklaus E. Wirth给出的公式：算法+数据结构=程序，说明数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。算法是程序的灵魂。
算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。

一个好的算法一般应该具有的基本特征

正确性(Correctness)
可读性(Readability)：可供理解的难易程度
易读性(Legibility)：便于阅读的难易程度
高效性(Efficiency)——最优性(Optimality)

设计实现算法过程的一般步骤

找出与求解有关的数据元素之间的关系（建立结构关系）。
确定在某一数据对象上所施加的运算。
考虑数据元素的存储表示。
选择描述算法的语言。
设计实现求解的算法，并用程序语言加以描述。

算法性能评价

算法执行时间

一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
语句频度
语句频度是指该语句在一个算法中重复执行的次数。

算法的时间复杂度

T(n)=O(f(n)) 表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

常量阶：O(1)
线性阶：O(n)
平方阶：O(n2)
立方阶：O(n3)
指数阶：O(2n)
对数阶：O(log2n)
二维阶：O(nlog2n)

复杂度频率表

上一张图大家直观感受

例如：下列程序段：

       for (i=1;  i< n;  i++)  
           for (j=i; j<= n;  j++) x++;`

有一个二重循环，语句x++的执行频度为:
n+(n-1)+(n-2)+…+3+2+1 =n(n+1)/2
而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。

void mult(int a[], int b[], int c[] ) {
  // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积
   for (i=1; i<=n; ++i)
      for (j=1; j<=n; ++j) {
         c[i,j] = 0;
         for (k=1; k<=n; ++k)
            c[i,j] += a[i,k]*b[k,j];
      } //for
} //mult

时间复杂度: O(n3)

最坏时间复杂度

void bubble(int a[], int length) /*整数数组a递增排序*/
{int i=0,j,t; /*t作两两比较的临时变量*/
 int change;
 do{chang=false;
      for(j=1; j<length-1; j++)
          if (a[j] > a[j+1]) /* 交换位置 */
             {t = a[j];
              a[j] = a[j+1];
              a[j+1] = t;
              change=true;}
       i=i+1;
      } while (i<length && change==true);}

考虑程序在最坏情况下的运行情况

时间复杂度: O(n2)

#数据结构##小白编程入门##大一新生学习方向##C/C++##算法#