数据结构笔记

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

1、

2、//2018/5/23数据结构概述：预备知识模块一：线性结构连续存储[数组]离散结构[链表]线性结构的两种常见应用之一栈（堆栈）线性结构的两种常见应用之二队列专题：递归1.1+2......+100的和2.求阶乘3.汉诺塔4.走迷宫模块二：非线性结构树图模块三：查找和排序折半查找排序：冒泡插入选择快速排序归并排序补录：Java中容器和数据结构相关知识Iterator接口Map哈希表严蔚敏---高一凡---黄国瑜

3、//2018/5/24数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型

4、和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。特定的数据类型:个体如何保存特定的存储结构:个体与个体的关系如何保存数据结构=个体的存储+个体关系的存储算法（狭义）=对存储数据的操作算法：即解题的方法和步骤衡量算法的标准1.时间复杂度[重要]大概程序要执行的次数，而非执行的时间2.空间复杂度[重要]算法执行过程中大概所占用的最大内存3.难易程度4.健壮性数据结构的地位数据结构是软件中最核心的课

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

6、预备知识：指针结构体动态内存的分配和释放指针：指针的重要性:表示一些复杂的数据结构快速的传送数据使函数返回一个以上的值能否直接访问硬件能够方便的使用数组和字符串是理解面向对象语言中引用的基础指针是C语言的灵魂定义地址内存单元的编号从0开始的非负整数范围0-FFFFFFFF【0到4G-1】注：无论一个变量有多大，其地址只用第一个字节的地址表示，均只占四个字节。指针指针就是地址地址就是指针指针变量就是存放内存单元地址的变量指针本质上就是一个操作受

7、限的非负整数分类

8、1、基本类型指针【略】基本概念inti=10;int*p=&i;//等价于int*p;p=&i;详解这两部操作：1）p存放了i的地址，所以我们说p指向了i2）p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值3）p指向i，*p就是i变量本身。更形象的说所有出现*p的地方都可以换成i，所有出现i的地方都可以换成*p4）int*p，不是定义了*p的参数，而是定义了一个变量p，为int*类型。总结：1、如何一个指针变量(假定为p)存放了某个普通变量(假定为i)的

9、地址，那我们就可以说：“p指向了i”，但p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值.2、*p等价于i或者说*p可以与i在任何地方互换3、如果一个指针变量指向了某个普通变量，则*指针变量就完全等价于该普通变量注意：指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址普通变量前不能加*常量和表达式前不能加&如何通过被调函数修改主调函数中普通变量的值Ⅰ实参为相关变量的地址Ⅱ形参为以该变量的类型为类型的指针变量Ⅲ在被调函数中通过*形参变量名的方式就可以修改

10、主函数相关变量的值Eg:voidf(int*p)//II{

11、*p=100;//III}intmain(void){inti=9;f(&i);//Iprintf(“i=%d”,i);}指针和数组的关系指针和一维数组数组名一维数组名是个指针常量，它存放的是一维数组第一个元素的地址，它的值不能被改变一维数组名指向的是数组的第一个元素下标和指针的关系a[i]<<==>>*(a+i)*a+3=a[0]+3假设指针变量的名字为p则p+i的值是p+i*(p所指向的变量所占的字节数)指针变量的运算指针变量不能相

12、加，不能相乘，不能相除如果两指针变量属于同一数组，则可以相减指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围p+i的值是p+i*(p所指向的变量所占的字节数)

13、p-i的值是p-i*(p所指向的变量所占的字节数)p++<==>p+1p--<==>p-1举例如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】两个参数存放数组首元素的指针变量存放数组元素长度的整型变量所有的指针变量只占4个子节用第一个字节的地址表示整个变量的地址动态内存分配和释放：[程序在运行过程中可以动态的增

14、加或减少内存分配]动态构造一维数组假设动态构造一个int型数组int*p=(int*)malloc(intlen);1、malloc只有一个int型的形参，表示要求系统分配的字节数2、malloc函数的功能是请求系统len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL3、malloc函数能且只能返回第一个字节的地址，所以我们需要把[类型不一样。即所占的字节数也不确定]这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一