Chrisstarss

数据结构

B站学习课程：【郝斌】-数据结构入门

B站视频链接地址：https://www.bilibili.com/video/av6159200

以下是笔记：

• 第一节课：

先讲一下本次课程上所有要讲的内容，请看如下信息：

1. 数据结构概述

2. 预备知识

3. 模块一：线性结构

           连续存储[数组]

           离散存储[链表]

           线性结构的两种常见应用之一 栈

           线性结构的两种常见应用之二 队列

           专题：递归

           1. 1+2+3+4+…100的和

           2. 求介乘

           3. 汉诺塔

           4. 走迷宫

4. 模块二：非线性结构

           树

           图

5. 模块三：查找和排序

           折半查找

           排序（主要讲冒泡和快排）

                 冒泡

                 插入

                 选择

                 快速排序

                 归并排序

6. Java中容器和数据结构的相关知识

           Iterator接口

           map

           哈希表

—————————————————

• 第一节课：什么叫做数据结构

先讲数据结构概述。

配套书籍：

看书看：《数据结构》（应该是这个，老师没放图片在课上），严蔚敏、吴伟民，两本书。基本上是摘抄的，书上都是伪算法，没有具体程序。

看程序看：高一凡，把上面书里写的算法都直接用程序实现（C、C++）。【西电的】

还有一个人是黄国瑜，都是自己写的，但是没写程序。另一个人写的程序都是错的，就不说了。

数据结构概述

       定义

              我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素、删除某个元素、对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。

             （第一：个体如何存储，第二：个体和个体的关系如何存储，这两个问题解决了，数据的存储问题就解决了。实际上，特定的数据类型指的就是个体如何存储；特定的存储结构指的就是个体和个体的关系如何存储。）

              数据怎么去存，就是数据结构要研究的。存完之后要对数据进行操作，这个操作就是算法。

              数据结构 = 个体 + 个体的关系

              算法 = 对存储数据的操作

              算法可以分为狭义的算法和广义的算法，从广义上来讲，算法和存储没关系，从狭义上讲，存储数据的方式不同，所执行的算法也不一样。

              算法是依附于存储数据的，存储的方式不一样，算法也就不一样。

       算法

              （在上面的定义里写了），就是在此存储的基础上，为实现某个功能而执行的相应操作，这个操作就是算法。

第一节课完。

• 第二节课：衡量算法的标准

         算法

              算法就是解题的方法和步骤。

              衡量算法的标准（最主要是前两个）：

                     1. 时间复杂度

                              大概程序要执行的次数，而非执行的时间。（机器不一样，执行的时间也就不一样，所以不能按照实际来计算，而是要看程序执行了几次。）

                     2. 空间复杂度

                              算法执行过程中大概所占用的最大内存。

                     3. 难易程度（其他人理解起来的难易度，实际操作时更看重难易度。）

                     4. 健壮性（不要别人给一个非法的输入程序就挂了）

              搞研究最主要的是前两个，如果是应用到具体的程序里面，要编程序、实现算法的时候，第三个是最主要的。

第二节课完。

• 第三节课：数据结构的特点

           数据结构的地位

                  数据结构是软件中最核心的课程。

学完之后你发现你什么也干不了，哈哈哈哈哈哈哈哈！！！老师学了三年心都快碎了！哈哈哈哈哈哈哈哈！！！！！！！！

不要指望数据结构学完了能做个什么东西出来！~

它属于一个内部课程，虽然做不出什么，但是它会促进你对很多其他课程的学习。

           程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

           所以数据结构学的就是  数据的存储 + 数据的操作 ，和具体的语言关系不大。（学完了和没学也差别不大，哈哈！但是慢慢会显出重要性来，加油！）

           数据结构学习的难度很大，也很重要，好好学！

第三节课完。

• 第四节课：预备知识_指针_1

     ——学习数据结构有两种学习方法：

                       1. 按照书上的去学。书上都是伪算法，不是程序，也不是程序中的一段代码，学习起来难度大，但相对容易，不过不建议这样学。

                       2. 伪算法知道了，通过一种语言去把它实现，但是难度很大。建议是通过这种方法学习。

         预备知识：

                指针

                      （C语言中的指针，只是数据结构中指针的一部分，还有很大一部分没有讲。）

                结构体

                动态内存的分配和释放

【难度大不代表学不懂！加油！】

学习数据结构，享受学习编程的乐趣！！~

第四节课完。

• 第五节课：预备知识_指针_1

         预备知识：

                指针

                      指针的重要性：

                             指针是C语言的灵魂。

                      定义

                             地址

                                   内存单元的编号

                                   从0开始的非负整数

                                   范围：0-FFFFFFFF（0 - 4G-1，G是指内存的2G、4G）

——————————————————————————————

补充：

内存是CPU唯一可以访问的大容量的存储设备。内存的问题是软件开发中最核心的问题之一。】

程序运行完，为程序所分配的内存单元全都回收了。回收是指该部分内存被系统回收，不能被其他程序使用了。如果需要使用，要跟系统申请，系统再重新把某个内存单元分配给程序。回收内存单元后，里面的内容不一定会清空，可能之前的数据还存放在那里。

——————————————————————————————

                             指针：

                                    指针就是地址，地址就是指针，是一个概念

                                    指针变量是存放内存单元地址的变量

                                    指针的本质是一个操作受限的非负整数

                      指针的分类

                             1. 基本类型的指针

                             2. 指针和数组的关系

待续

                结构体

                动态内存的分配和释放