数据结构学习笔记(郝斌老师)

《数据结构学习笔记(郝斌老师)》由会员分享，可在线阅读，更多相关《数据结构学习笔记(郝斌老师)（88页珍藏版）》请在金锄头文库上搜索。

1、学算法， 不要想着自己能够完完整整的自己编一个算法， 也不要觉得自己想不出来就备 受打击。 只要能看懂别人写的算法，然后反复地自己敲，反反复复地出错，然后再敲，最后实现 能够把这个程序敲出来就行了。 看懂主要分三步：1 看懂主函数的流程；2 明确每一个子函数的功能；3 试数，就是自 己往里面代数。 总搞不懂， 看不懂地算法， 就把它背会， 然后反复想， 期待能够搞定 （基本很少， 但有） 。 数据结构研究的就是个体的存储和个体与个体之间关系的存储问题存储问题， 算法研究的是对数据的 操作问题操作问题，并且不同的存储结构会影响算法的使用，举个简单的例子，要想实现一个功能， 你首先需要把数据拿出来

2、，对于数组来说用 for 循环就可以实现，但对于链表就不可以了， 所 以 说 算 法 依 附 于 存 储 数 据 的 结 构 ， 结 构 不 同 算 法 必 定 会 有 差 异 (控制线用来控制 cpu 对于内存条，是只读还是只写，还是可读或可写) 两个指针变量之间只可以相减，不可以相加，相乘或相除，因为这样的运算无意义 对于单个指针可以进行加法或者减法运算（自增，自减） “指向同一块连续空间的不同存储单元”这个要求存在，是因为不同类型的指针变量，相 减无意义，例如，一个保存的是整型的地址，另一个保存的是实型的地址，相减干啥？ 指针就是地址，计算机里的地址值就是编号，所以可以说指针就是编号。

3、Double 类型变量占 8 个字节，一个字节占 8 位，意思是，一个字节可以存放 8 个 0 或 者 8 个 1。 一个字节用一个地址表示（一个字节一个编号），那么 double 类型变量因为占 8 个字 节，那么就会有 8 个地址，那么指针中究竟存放的是这 8 个字节中的哪个地址呢？ 解： 对于变量来说，要用它的第一个字节的地址来表示整个变量的地址。在计算机中的地 址总线中用 32 根线（即 32 位）来存储变量在内存中所占首字节的地址，意思是用四个字节 来存储某变量首字节的地址。 所有的指针变量占四个字节所有的指针变量占四个字节， 这意味着， 一个指针变量无论它指向的变量占多大的字节，

4、它永远只占四个字节。 所以，指针中究竟存放的是这 8 个字节中的第一个字节的地址。 据此，做下面这个题 问两次输出的 q 相差多少？ 答：因为每个 double 类型变量占 8 个字节，一个字节用一个地址来表示，用一个变量中的 首地址（即第一个字节的地址）来表示变量的地址。意味着两个 double 类型变量之间有 8 个地址值，所以两个地址值应该相差 8； 运行结果：第一个数据+8 等于第二个数据。（16 进制） 指针与一维数组指针与一维数组 # include int main(void) int a5; /a 是数组名5 是数组元素的个数 元素就是变量a0- a4 /int a34; /3

5、 行 4 列 a00是第一个元素 aij第 i+1 行 j+1 列 int b5; /a = b;/error a 是常量 printf(“%#Xn“, printf(“%#Xn“, a); return 0; /* 在 Vc+6.0 中的输出结果是: - 0X12FF6C 0X12FF6C Press any key to continue - 总结： 一维数组名 一维数组名是个指针常量，常量意味着，其值不可以被改变 它存放的是一维数组第一个元素的地址 */ 指针变量，变量，这两种变量的“变”，一定要好好理解，它的变化范围是什么，变化 对象是什么，一定要搞清楚。 指针变量也是变量， 它与变量

6、的区别在于其存放的东西不一样， 这就意味着变化的对象 不一样；以及变化的范围不同。 指针变量存放的是地址值 （为什么要经常用字母 p 来表示一个指针变量， 就是因为它里 面存放的是地址值，是位置信息，英文单词 position 的首字母为 p），地址值是变量在定义 时计算机赋给变量的一个计算机识别的标识，它的值是计算机编好的一系列的编号。所以， 指针变量的变化范围就是那些所有的地址值编号，一般来说就是以 16 进制表示的从 0 开始 的一系列的数。 指针的变量值是人赋予的那些数据，其变化范围就是数学上所定义的那个范围。 语法程序举例语法程序举例 1： # include int main(vo

7、id) int * p; /p 是变量的名字, int * 表示 p 变量存放的是 int 类型变量的地址 int i = 3; p = /OK /p = i; /error，因为类型不一致，p 只能存放 int 类型变量的地址，不能存放 int 类 型变量的值 /p = 55; /error 原因同上 return 0; 程序举例程序举例 2 # include int main(void) int * p; /p 是变量的名字, int * 表示 p 变量存放的是 int 类型变量的地址 /int * p; 不表示定义了一个名字叫做*p 的变量 / int * p; 应该这样理解: p 是

8、变量名, p 变量的数据类型是 int *类型 /所谓 int * 类型 实际就是存放 int 变量地址的类型 int i = 3; int j; p = /* 这句话写完就意味着： 1. p 保存了 i 的地址, 因此 p 指向 i 2. p 不是 i，i 也不是 p，更准确的说： 修改 p 的值不影响 i 的值，修改 i 的值也不会影响 p 的值 3. 如果一个指针变量指向了某个普通变量, 则 *指针变量就完全等同于普通变量 例子: 如果 p 是个指针变量，并且 p 存放了普通变量 i 的地址 则 p 指向了普通变量 i *p就完全等同于i 或者说:在所有出现*p 的地方都可以替换成 i

9、在所有出现 i 的地方都可以替换成*p *p 就是以 p 的内容为地址的变量 */ j = *p;/等价于 j = i; printf(“i = %d, j = %dn“, i, j); return 0; 程序举例程序举例 3 3 互换两个数字 # include void huhuan_1(int , int); void huhuan_2(int *, int *); void huhuan_3(int *, int *); int main(void) int a = 3; int b = 5; huhuan_3( /huhuan_2(*p, *q); 是错误的, huhuan_1(a

10、, b);也是 错误的 printf(“a = %d, b = %dn“, a, b); return 0; /不能完成互换功能 void huhuan_1(int a, int b) int t; t = a; a = b; b = t; return; /*主函数的 a 和 b 与该被调函数的 a,b 占不同的内存空间， 所以在被调函数中对 a 和 b 进行交换并不会修改主函数中 a 和 b 的值。函数 huhuan_1(int a, int b)的形参为 整形，这意味着只只是将主函数中的是将主函数中的 a a 和和 b b 的值发送给函数的值发送给函数 huhuan_1huhuan_1，

11、让它可以使用这，让它可以使用这 个变量的值个变量的值，然后进行为了实现某个功能的操作然后进行为了实现某个功能的操作，其操作结果不会影响主函数中 a 和 b 的值。*/ /*全局变量的生存期是全局变量的生存期是 伴随着整个程序的执行的伴随着整个程序的执行的 局部变量的生存期是局部变量的生存期是 伴随着其所在函数的执行的伴随着其所在函数的执行的 所以， 函数 huhuan_1 互换完毕后， 结束该函数， 然后返回主函数， 继续执行 printf() 语句，所以 a 和 b 的值没有被互换*/ /不能完成互换功能 void huhuan_2(int * p, int * q) int * t;/如果

12、要互换 p 和 q 的值，则 t 必须是 int *,不能是 int,否则会出 错 t = p; p = q; q = t; /可以完成互换功能 void huhuan_3(int * p, int * q) int t; /如果要互换*p和*q的值, 则t必须定义成int,不能定义成int *, 否 则语法出错 t = *p;/p 是 int *,*p 是 int *p = *q; *q = t; 指针常见错误：指针常见错误： （这个程序跑起来， 语法上不会报错， 但是， 系统会自动终止程序，因为这样的错误太弱智了，系统还是可以识别出来的，如果一个程序 能够躲避操作系统的控制，在内存中捣一些

13、鬼，这些程序就是病毒程序） （这个 程序时会报错的，因为，*q 所存储的事整型数据，而 p 存放的是整型地址，类型不一致所 以编译的时候就会报错。） （这个程序在语法上并没有问题，但是,操作系统只允许程序操作已经开辟了的内存空间，操作系统只允许程序操作已经开辟了的内存空间， 开辟了的存储空间就属于该程序的天地，不允许程序对未开辟的不属于这个程序的天地进开辟了的存储空间就属于该程序的天地，不允许程序对未开辟的不属于这个程序的天地进 行操作，例如读写操作，或者说其他操作。行操作，例如读写操作，或者说其他操作。操作系统会检验出这个程序存在超越权限的代 码，所以程序跑起来时会被操作系统报错，然后被终止

14、。例如，具体来说就是具体来说就是，int *q，就 为 q 变量开辟了一块存储单元， 这一块存储空间就属于这个程序的天地， 可以对其进行操作， 例如进行同类型变量的赋值等操作、p=q、，但是，printf(“%dn”,*q)，因为 q 变量存储的是变量存储的是 一个不属于该程序天地的一块存储单元的地址一个不属于该程序天地的一块存储单元的地址，*p 就是对这这块区域进行取值运算，就属就是对这这块区域进行取值运算，就属 于对不属于这个程序天地的进行读的操作，这样的操作是不被操作系统允许的，于对不属于这个程序天地的进行读的操作，这样的操作是不被操作系统允许的，） 指针最复杂的地方在于指针最复杂的地方

15、在于：1.内存泄漏内存泄漏（内存越用越少内存越用越少，内存用光之后就会调用虚拟内存内存用光之后就会调用虚拟内存，如如 果虚拟内存也用光了果虚拟内存也用光了，机子就死机了机子就死机了）；2.野指针野指针（不直到指针确切地指向或者说保存了谁不直到指针确切地指向或者说保存了谁 的地址。）的地址。） （本质上来说这两个问题就是，你怎么确定当前这一块存储单元，有多少个指针变量（本质上来说这两个问题就是，你怎么确定当前这一块存储单元，有多少个指针变量 保存了这块单元的地址，因为一块存储空间在一个大型的程序中会有好多个指针指向它，保存了这块单元的地址，因为一块存储空间在一个大型的程序中会有好多个指针指向它，

16、 如果一次都不释放就会导致内存泄漏，一不小心如果一次都不释放就会导致内存泄漏，一不小心 free 多了，程序就会挂掉。）多了，程序就会挂掉。） 当前学当前学 c 语言的指针语言的指针，最关键的就在于讲动态内存最关键的就在于讲动态内存，为将来学为将来学 java,c#,c+准备准备，对于一对于一 块动态的内存空间，用完之后就需要进行释放，释放就是通过函数块动态的内存空间，用完之后就需要进行释放，释放就是通过函数 free(p)；进行释放，；进行释放，p 是指向该内存的一个指针变量。是指向该内存的一个指针变量。 （这个图中有三个指针变量指向了一块动态的内存空间， 这在一个大型的程序中很常见， 那 么，这个时候如果再写一个 free(q)，整个程序就会挂掉。同一个空间被释放两次，程序会挂 掉。） 要想在自定义函数中改变主函数中变量的值， 就需要把变量的地址值作为实