数据结构学习笔记.pdf

《数据结构学习笔记.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、相信很多人和我一样在数据结构学习的道路上走了很多弯路，虽然我的计算机水平有限，但是，我任然希望能够帮助到大家，让大家少走弯路。这是我根据郝斌老师的《数据结构自学教程》复习数据结构这门课程所做的笔记，一共有78集，郝斌老师的课讲得很好，建议大家听一听。这里面的代码都是能够运行通过的，如果有什么疑问，可以与我联系，相互学习。QQ:672553963此外，提醒大家在学习的过程中不要相信谁谁谁说什么很深奥很难之类的话，任何东西，再难也是人想出来的，只要你有耐心，什么知识都是能够学会的。任何一个大牛也是从菜鸟开始的！数据结构概述预备知识模块一：线性结构连续存储：数组离散存储：链表线性结构的两种应用

2、之一：栈线性结构的两种应用之二：队列模块二：非线性结构树图模块三：查找和排序查找：折半查找排序：冒泡排序插入排序选择排序快速排序归并排序数据结构的概念：我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中。以及在此基础上为实现某个功能而执行的相应操作，这个相应的操作也叫算法。衡量算法的标准：1.时间复杂度2.空间复杂度3.难易程度4.健壮性数据结构的特点：数据结构是软件设计中最核心的课程预备知识：指针inti=10;int*p=&i;//等价于int*p;p=&i;1.如果一个指针变量(p)存放了某个普通变量(i)的地址，那我们就可以说“p指

3、向i”，但是p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值；2.*p等价于i，或者说*p可以与i在任何地方互换；3.如果一个指针变量指向了某个普通变量，则*指针变量完全等价于该普通变量注意：1.指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址；2.普通表达式前不能加*3.常量和表达式前不能加&。内存内存的基本概念1.内存是用来存储数据的设备。它的存储速度介于寄存器和硬盘之间；2.内存是CPU唯一可以直接访问的大容量存储设备。所有硬盘中的程序和数据必须调入内存之后方可被CPU执行。3.内存的问题是软件开发中最核心的问题。如：内存的分配、内

4、存的释放。什么时候分配内存、什么时候释放内存、由谁来分配、由谁来释放、分配在什么地方、访问权限如何；4.内存是多字节组成的线性一维存储空间；5.内存的基本单位是字节；6.每个字节含有8位。每一位存放1个0或1；7.字节和编号是一一对应的。每个字节都有唯一的确定编号，一个编号对应一个字节，这个编号也叫地址；8.一个系统所能管理的内存空间的大小取决于参与编号的二进制位数。内存是在操作系统的统一管理下使用的。1.软件在运行时需要向操作系统申请存储空间，在内存空闲足够时，操作系统将分配一段内存空间并将外存中软件拷贝一份存入该内存空间中，并启动该软件的运行；2.在软件运行期间，该软件所占内存不再分

5、配给其它软件；3.当软件运行完毕后，操作系统将回收该内存空间，以便再次分配给其它软件使用。（注：操作系统不会清空内存空间中遗留下来的数据，只是回收其操作权限）如何通过被调函数修改主调函数中普通变量的值？1.主调函数的实参为相关变量的地址2.被调函数的形参为以该变量的类型为类型的指针变量3.在被调函数中通过“*形参变量名”的方式就可以修改主调函数中普通变量的值。#includevoidf1(inti){i=99;}voidf2(int*p){*p=99;}voidf3(int**q){*q=(int*)0xffffffff;}intmain(){inti=9;f1(i);/

6、/局部变量的值不变printf(“i=%d”,i);f2(&i);//形参为i的地址printf(“i=%d”,i);int*p=&i;//对内存地址的操作，是不安全的printf(“p=%p”,p);f3(&p);printf(“p=%p”,p);}指针和数组1指针和一维数组数组名：一维数组名是个指针常量；它的值不能被修改；一维数组名指向的是数组的第一个元素。2下标和指针的关系a[i]<<==>>*(a+i)结构体为什么会出现结构体？为了表示一些复杂的数据，而普通的基本类型无法满足要求。什么叫结构体？结构体是用户根据实际需求自己定义的一种数据类型。如何使用结构体？//定

7、义结构体实际上就是定义一种新的数据类型structStudent{intsid;charname[200];intage;};//分号不能省略使用结构体定义变量时，与类的使用有一定的差异structStudentstu={1000,”zhangsan”,20};printf(“&d%s%d”,stu.sid,stu.name,stu.age);stu.sid=99;//stu.name=”lisi”//这样使用是不对的strcp