数据结构学习☞入门(一)算法数据结构

编程如果只是一个为了解决生活温饱的工具，那你可以完全忽略数据结构，算法，你的目标很容易实现；但如果你是热爱编程，把它当做对生活的追求，想在这一行走的更远，更久，那么在你的学习规划中，她们便是必不可少的一种语言；

算法，数据结构，程序设计方法，语言工具4个方面是一个程序设计人员所应该拥有的，算法是灵魂，数据结构是加工，对象语言是工具;由此可见算法和数据结构的重要性，不管我们选择Java，c语言还是JavaScript，她们都只是一种语言工具；核心和灵魂依旧在算法和数据结构

在学习算法之前，应该先学会数据结构；没有数据结构的支撑，算法有点艰辛；数据结构又分C语言版本的Java版本的；在学数据结构之前我们应该对这两个语言其中一门有所了解；

算法

算法是解决“做什么”和“怎么做”的问题；在我们日常的操作语句中体现的淋淋尽致，如果我们不了解算法也就谈不上程序设计；掌握了算法就是掌握了程序设计的灵魂

如果让你写一个1+2+3+4+...+100的结构程序，你会怎么写呢？ 思考三秒钟很多人第一时间想到的是第一种算法，很少有人会去想第二种；

我们来比较一下这两种算法，方法一随着n的增大，语句执行的次数成线性增加；方法二是不管n有多大，语句总是只执行一次；都可行，但很明显方法二的算法优于方法一；

为什么呢？

为了更好的区分她们的差别我们引入算法的时间复杂度即算法的时间的度量；（即O()）；

记T(n)是语句执行次数的函数；随着n的增加，T(n)增长最慢的算法我们称为最优算法；即算法时间复杂度小；

方法一的时间复杂度为O(n)，方法二的时间复杂度为O(1)

好的算法应该具备时间效率和存储量低的特点；正如我们日常生活一样的，我们总希望花最少的钱，用最短的时间办大事；算法也有一样的思想；最少的存储空间，最少的时间，办同样的好事；

在算法的入门级别中有没有感觉到算法的神奇?

任何事物没有好坏之分，只有适不适合；算法也不例外

2.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项？

一种使用递归实现，递归能够使程序的结构更加清晰，更简洁，更容易让人理解，减少度代码的时间；递归使用的是选择结构；

一种使用迭代，迭代使用的是循环结构；

乍一看我们会觉得使用递归效果更佳。可是我们忽略了大量的调用递归会建立函数的副本，消耗大量的时间和内存；而迭代则不需要反复调用函数和占用额外的内存；

判断一个算法好不好，我们只通过少量的数据不能做出准确判断，因此根据需求情况选择不同的代码实现方式；

算法的强大不止于此，强大而有趣味的算法等着我们去挑战；

算法的特性：

• 有穷性：算法应该包含有限的操作步骤
• 确定性：算法中的每一个步骤应该是确定的
• 有零或多个输入：执行算法的时候需要从外界取得必要的信息
• 有一个或多个输出：算法的目的是为了求解，“解”就是输出
• 有效性：每个步骤应该是有效的，并得到确定的结果

好的算法应该是：速度快，存储空间少

数据结构

深入学习之前先了解数据结构一组概念 数据: 描述客观事物的符号；能输入到计算机中，能被计算机程序处理；比如声音，图像，视频...

数据元素：是组成数据的有一定意义的基本单位；也被称为记录；（比如学生，老师

数据项：一个数据元素可以有若干个数据项组成；是数据项不可分割的最小单位；（比如学生的姓名，学号,性别...

数据对象：数据元素具有相同数量和类型的数据项；（比如学生有姓名，学号，性别等相同的数据项

数据结构：相互之间存在一种或者多种特定关系的数据元素集合；

数据结构按照视点不同可分为：逻辑结构和物理结构

逻辑结构

逻辑结构：数据对象中数据元素之间的关系

• 集合结构：数据元素除了同属于一个集合之外，她们没有任何关系
• 线性结构：数据元素之间一对一关系
• 树形结构：数据元素之间存在一对一或一对多的层级关系
• 图形结构：数据元素是多对多的关系


物理结构

物理结构(存储结构)：数据的逻辑结构在计算机中的存储形式

• 集合结构：数据元素除了同属于一个集合之外，她们没有任何关系
• 顺序结构：把数据元素存放在地址连续的存储单元里；(数组)
• 链式结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

逻辑结构是面向问题的，物理结构是面向计算机的；我们应该注重的就是物理结构，将数据及其逻辑关系存储到计算机内存中去线性,树形,图形,链式是数据结构的重点和难点

题外话

指针，地址，指针变量是什么？

地址是指向该变量单元；地址形象化地称为指针；指针变量的值是地址；所有说指针是一个地址，指针变量是存放地址的变量；

在设计一个较大的程序时，往往把它分成若干个程序模块。每个模块包括一个或者多个函数，每个函数实现一个功能；函数是一个功能，每个函数用来实现一个特定的功能，函数的名字应该反映其代表的功能；利用函数，减少重复编写的程序段的工作量；(例如：C语言中main()函数) 在实际应用中我们用函数来实现模块化程序设计

结构体：C语言允许用户自己建立有不同类型的数据组成的组合型的数据结构，称为结构体;

结构体类型：包含不同类型的成员；

结构体指针，就是指向结构体变量的指针；

链表是什么？ 链表是一种数据结构，必须利用指针变量来实现；数据结构包括（number结构类型，Object类型，Array类型等等）；链表是根据需要开辟内存单元，链表有一个头指针，存放一个地址，该地址指向一个元素（每个链表都有一个头指针，必不可少）；链表中的每一个元素称为节点；节点包含两个部分，用户需要的实际数据，下一个节点的地址(next);链表中的地址是不连续的；要找某一元素，必须先找到上一个元素，根据他提供的下一个元素地址才能找到下一个元素；

形参不占内存中的存储单元；如果函数不需要返回值则不需要return语句