数据结构概述、指针与内存

数据结构的定义

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

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

　　算法 = 对存储数据的操作

衡量算法的标准：

• 　　　　时间复杂度：大概程序要执行的次数，而非执行的时间
• 　　　　空间复杂度：算法执行过程中大概所占用的最大内存
• 　　　　难易程度
• 　　　　健壮性

内存的基本概念：

　　1.内存是用来存储数据的设备。它的存储速度介于寄存器和硬盘之间。

　　2.内存是CPU唯一可以访问的大容量的存储设备，所有硬盘中的程序和数据必须调入内存之后方可被CPU执行。注：CPU不能直接处理硬盘中的数据！

　　3.内存的问题是软件开发中最核心的问题之一！如：内存的分配、释放，内存什么时候分配、什么时候释放？由谁来分配、释放？分配在什么地方？访问权限如何？

　　4.内存是多字节组成的线性一维存储空间。

　　5.内存的基本和划分单位是字节。

　　6.每个字节含有8位，每一位存放1个0或1个1。

　　7.字节和编号一一对应。每个字节都有一个唯一确定的编号，一个编号对应一个字节，这个编号也叫字节。

　　8.一个系统所能管理的内存空间的大小取决于参与编号的二进制位数。 如：DOS系统20位寻址方案，可控制2^20B即1MB的内存。

软件运行与内存关系（垃圾数据）

　　内存是在操作系统的统一管理下使用的！

　　1.软件在运行前需要向操作系统申请存储空间， 在内存空闲空间足够时，操作系统将分配一段内存空间并将外存中软件拷贝一份存入该内存空间中，并启动该软件的运行！

　　2.在软件运行期间，该软件所占内存空间不再分配给其他软件

　　3.当软件运行完毕后，操作系统将回收该内存空间（注：操作系统并不清空该内存空间中遗留下来的数据），以便再次分配给其他软件使用。 综上所诉，一个软件所分配到的空间极可能存在着以前其他软件使用过后的残留数据，这些数据称之为垃圾数据。所以通常情况下我们为一个变量、数组，分配好存储空间之后都要对该内存空间初始化！

指针的定义

　　指针即地址，地址是内存单元的编号，范围是0~2^8-1的非负整数，不可重复，但所存内容可以重复。 指针变量就是存放内存单元地址的变量，不能存放内存单元内容。

 1 #include<stdio.h>
 2 int main(){
 3     int *p; //p是个变量的名字，int*表示该P变量只能存储int类型变量的值,而不能存char或其他类型变量的值
 4     int i = 10;
 5     int j;
 6     //p = &j; //由于j没有赋值，所以p不会接收不确定单元的地址，p会被内存填充为一个垃圾数字
 7     p = &i;  //把i的地址给指针变量p
 8     j = *p;  //由于指针p接收了变量i的地址，*p表示把i变量地址的值取出来，再赋值给j
 9     
10     printf("i = %d,j = %d,*p = %d",i,j,*p);  //都输出10
11     return 0;
12 }

硬件被操作系统控制，编译器请求操作系统分配内存给变量，当程序运行完，内存会被回收 ，但数据变成了垃圾数据，并没有被清除。

如何通过被调函数修改主调函数中普通变量的值？

　　1.实参为相关变量的地址

　　2.形参为以该变量的类型为类型的指针变量

　　3.在被调函数中通过 *形参变量名的方式，就可以修改主函数变量的值

 1 #include<stdio.h>
 2 void f(int *p){
 3     *p = 100;
 4 }
 5 int main(){
 6     int i = 9;
 7     f(&i);
 8     printf("%d",i);//输出100,而不是9
 9     return 0;
10 }