数据结构笔记.doc

|/2018/5/23数据结构概述：预备知识模块一：线性结构连续存储数组离散结构链表线性结构的两种常见应用之一 栈（堆栈）线性结构的两种常见应用之二 队列专题：递归1.1+2.+100的和2.求阶乘3.汉诺塔4.走迷宫模块二：非线性结构树图模块三：查找和排序折半查找排序：冒泡 插入 选择 快速排序 归并排序补录：Java 中容器和数据结构相关知识Iterator接口Map 哈希表严蔚敏-高一凡-黄国瑜|/2018/5/24数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。特定的数据类型:个体如何保存特定的存储结构:个体与个体的关系如何保存数据结构 = 个体的存储 + 个体关系的存储算法（狭义） = 对存储数据的操作算法：即解题的方法和步骤衡量算法的标准1. 时间复杂度重要大概程序要执行的次数，而非执行的时间2. 空间复杂度重要算法执行过程中大概所占用的最大内存3. 难易程度4. 健壮性 数据结构的地位数据结构是软件中最核心的课程。程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言|预备知识：指针结构体动态内存的分配和释放指针：指针的重要性:表示一些复杂的数据结构 快速的传送数据 使函数返回一个以上的值能否直接访问硬件 能够方便的使用数组和字符串是理解面向对象语言中引用的基础指针是 C语言的灵魂定义地址内存单元的编号从 0开始的非负整数范围 0-FFFFFFFF 【0 到 4G-1】注：无论一个变量有多大，其地址只用第一个字节的地址表示，均只占四个字节。指针指针就是地址 地址就是指针指针变量就是存放内存单元地址的变量指针本质上就是一个操作受限的非负整数分类|1、基本类型指针【略】基本概念int i=10;int *p = /等价于 int *p; p = 详解这两部操作：1）p 存放了 i的地址，所以我们说 p指向了 i2）p 和 i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值3）p 指向 i，*p 就是 i变量本身。更形象的说所有出现 *p 的地方都可以换成 i，所有出现 i的地方都可以换成*p4）int * p，不是定义了*p 的参数，而是定义了一个变量 p，为 int *类型。总结：1、如何一个指针变量(假定为 p)存放了某个普通变量(假定为 i)的地址，那我们就可以说：“p 指向了 i”， 但 p与 i是两个不同的变量，修改 p的值不影响 i的值，修改 i的值不影响 p的值.2、*p 等价于 i 或者说*p 可以与 i在任何地方互换3、如果一个指针变量指向了某个普通变量，则*指针变量 就完全等价于该普通变量注意：指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址普通变量前不能加*常量和表达式前不能加 /IIIint main(void)int i = 9; f( /Iprintf(“i = %dn”, i);指针和数组的关系指针 和 一维数组数组名一维数组名是个指针常量，它存放的是一维数组第一个元素的地址， 它的值不能被改变一维数组名指向的是数组的第一个元素下标和指针的关系ai > *(a+i)*a+3 = a0+3假设指针变量的名字为 p则 p+i的值是 p+i*(p所指向的变量所占的字节数)指针变量的运算指针变量不能相加，不能相乘，不能相除如果两指针变量属于同一数组，则可以相减指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围p+i的值是 p + i*(p所指向的变量所占的字节数)|p-i的值是 p - i*(p所指向的变量所占的字节数)p+ p+1p- p-1举例如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】两个参数存放数组首元素的指针变量存放数组元素长度的整型变量所有的指针变量只占 4个子节 用第一个字节的地址表示整个变量的地址动态内存分配和释放：程序在运行过程中可以动态的增加或减少内存分配动态构造一维数组假设动态构造一个 int型数组int *p = (int *)malloc(int len);1、malloc 只有一个 int型的形参，表示要求系统分配的字节数2、malloc 函数的功能是请求系统 len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回 NULL3、malloc 函数能且只能返回第一个字节的地址，所以我们需要把类型不一样。即所占的字节数也不确定这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此 malloc前面必须加（数据类型 *）,表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。如：int *p = (int *)malloc(50); 表示将系统分配好的 50个字节的第一个字节的地址转化为 int *型的地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这样 p就指向了第一个的四个字节，p+1 就指向了第 2个的四个字节，p+i 就指向了第 i+1个的 4个字节。p0就是第一个元素， pi就是第 i+1 个元素double *p = (double *)malloc(80); |表示将系统分配好的 80个字节的第一个字节的地址转化为 double *型的地址，更准确的说是把第一个字节的地址转化为 8个字节的地址，这样 p就指向了第一个的 8个字节，p+1 就指向了第 2个的 8个字节，p+i 就指向了第 i+1个的 8个字节。p0就是第一个元素， pi就是第 i+1个元素free（p）：动态分配的内存，必须 free()释放，系统不会自动释放。释放 p所指向的内存，而不是释放 p本身所占用的内存【重点：动态分配数组内存】int * pArr = (int *) malloc (sizeof(int) * len); (最后一个*代表了乘 分配了 4 * len个字节)|模块一：线性结构【把所有的结点用一根直线穿起来】连续存储数组1.什么叫数组元素类型离散结构链表|线性结构中两种常用应用之一 栈定义一种可以实现“先进后出”的存储结构只能从栈尾（栈顶）进和出。栈类似于箱子，局部变量都是在栈中存储的。分类静态栈【以数组为内核】动态栈【以链表为内核】算法出栈 pTop 向下移一个，pBottom 不变压栈（入栈） pTop 向上移一个，pBottom 不变应用 函数调用中断表达式求值（例如计算器的编写）|内存分配 缓冲处理 /2018/5/20线性结构中两种常用应用之二 队列定义： 一种可以实现“先进先出”的存储结构分类： 变量名：front（头部） 和 rear（尾部）链式队列-用链表实现静态队列-用数组实现注：在队首的位置删除元素，然后队首指针指向下一个元素在队尾的位置添加元素，然后队尾指针指向下一个元素 【重点】Rear 指向的是队列最后一个元素的下一个元素【重点】Front 指向的是队列的第一个元素队列算法：入队出队队列的具体应用：所有和时间及有关的操作都有队列的影子。静态队列：注：将数组的部分功能给去掉，然后再加入一些功能。静态队列通常都必须是循环队列。问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。循环队列的讲解：1. 静态队列为什么必须是循环队列