数据结构基本认识与必要知识点准备工作

什么是数据结构?

在一些特定的、特殊的需求场景下,我们以往所学的数据类型,无法基于需求合理地组织数据,此时就需要我们直接设计一套新的数据组织形式来解决问题,也就是数据结构.

主要学习内容

1.数据结构的内容:

线性表 队列 数组 树与二叉树 图

2.算法的内容:

查找 排序

基于c语言描述的数据结构需要哪些前置知识?

函数 字符串 内存解析 数组 指针 结构体 内存分配

1.函数：

可以实现某个具体功能的代码块

增加代码的复用性

降低变成难度

函数不被调用时不会执行的

对内隐藏细节,对外暴露接口(学过Java的都知道哈,其实这也是java中的封装的特性)

我这里给大家在平时写函数实现功能的时候要问自己三个问题

(1):我们要干什么(需求)

(2):实现这个功能需要什么(参数)

(3):是否需要返回值(返回值)

2.字符串：

在c语言中是没有字符串这个数据类型的,可能在别的语言中是有的比如(Java)

在c语言中对字符串的初始化,我们可以用字符数组,字符指针

3.内存：

计算机体系结构:

辅助存储器:内存条(内存)-随机存储器RAM

主存储器:硬盘(外存)-只读存储器ROM

我们来看一下不同的数组类型在内存中所占的字节数吧

int类型在内存中占4个字节数

那char在内存就是占1个字节还有short long double 等等

4.数组：

基本定义

数组在内存中是怎么存储的

获取数组的地址

数组名我们大家都知道代表的数据数组首元素地址中的首首地址，那取数组名的地址代表什么呢，他的地址跟数组首元素的地址数据一样的，但是意义不一样，这个地址代表的数据整个数组的地址，这里大家一定要搞清楚

 sizeof关键字：获取所占的内存字节数

比如sizeof（int）占4个字节数

比如我们写函数的时候传过来的数组，我们不知道数组的长度是多少，但是我们用sizeof可以计算，sizeof（数组名）/ sizeof（数组首元素）

5.指针：

指针的定义：指针就是存放内存地址的变量

他和其他都一样，就是存的东西不一样

例如：int a;变量a就可以存整数  char a;变量a就可以存字符  double a:变量就可以存小数

           int *p;变量p就可以存int类型的地址 

什么意思呢？

比如有一个地址0x12345，我们在0x12345这个地址中存了一个int类型（整数），那变量p就可以存这个地址（0x12345代表的首地址，因为一个字节代表一个地址，int有4个字节，占4个内存的字节）

我们来看一段代码

变量p的地址和&a的地址是不是一样

接下来我们再说怎么通过地址获取里面的值

我们用到了一个*符号

他单拿出来什么意思呢？

*：间接引用操作符，用于返回指针变量的指向地址的值，通常叫做解引用指针

（简单来说就是获取一个的地址所指向的那个值（就是这个地址里面所存的值））

了解完了指针的基础的概念，我接下来给大家说一下指针的一些基础用法

(1) 普通指针：

int *p：我们声明了指针变量p，p指向一个int类型的元素，可以保存一个 int类型元素的地址（p的类型是int *）

(2) 数组指针：
int (*p) [5]：我们声明一个指针变量p,p指向一个包含5个int类型元素的数组，可以报存一个包含5个int类型元素的数组的地址（p的类型是int (*) 5）

(3) 指针数组：

int *p[5]：我们连续开辟了5个指针变量的数组，每一个数组的元素都是一个指针，并且这5个指针都指向一个int类型元素，都可以保存一个 int类型元素的地址（p 的类型是int *[5]）

(4) 函数指针：

int (*p)(int ,int)：我们声明了一个指针变量p,p指向一个包含返回值为int,形参为两个int的函数，p可以保存包含返回值为int,形参为两个int的函数的地址（p 的类型是int (*) (int,int)）

(5) 指针函数：

这个很简单就返回值为一个指针

int * bbb （）；返回一个int*类型的地址

(6) 结构体指针：

struct 结构体名字 * p：我们声明了一个指针变量p,p指向一个struct 结构体名字类型的结构体，可以保存一个struct 结构体名字类型的结构体的地址

6.结构体：

我们学过java的其实都知道Java里面有一个类，这个类其实去掉方法啥的他就相当于c语言的结构体，java的底层其实用c语言写出来的

声明：

结构体的访问：

我们来看一下代码

结构体指针与访问：

我们来看一下代码：

typedef关键字：

他的定义：typedef 数据类型 别名，简单来说，就是给数据类型重写起一个名字，比如你叫张三，给你起一个小名叫三三，三三就代表张三，只是名字改变了，作用什么的都没有改变

例如：

当然我们可以给我们直接定义的数据类型改变名字

我们来看一下代码

大家可能会问了这有什么意义呢?

我们看一下使用场景

如果我们想把int的变量全部改成double，我们需要一个个的改吗，不需要，只需要把int改成double就可以了

总结：

七：内存分配

其实java c++底层的那个new对象的代码其实都是通过c语言动态内存分配来实现的

我们学过java的其实都知道你有一个类person

person a=new person();

这句话的意思是：在栈空间开辟了声明了一个person类型的变量a的，在堆空间开辟空间存储person这个类里面的内容，其实这个底层的逻辑是在c语言写出来的，变量a属于自动内存，而new属于动态内存，如果没学过java这句话自动屏蔽

在c语言我们经常用到的一个动态内存分配的一个函数malloc()

在c语言中我们需要手动释放内存，在java中有一个特别牛的机制，他会自动回收

我们用代码演示一下：

到这里学习数据结构的前的预备内容复习完了，下面就到我们数据结构真正的开始了