数据结构资料 - 1 - 教材：《数据结构》 严蔚敏 吴伟民 清华大学出版社

《数据结构算法实现及解析》 高一凡 西安电子科技大学出版社 第一部分 数据结构概述 一、定义（研究是数据结构的存储和数据的操作的） 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。 数据结构 = 个体的存储（从某个角度而言，可忽略） + 个体与个体之间关系的存储（核心） 算法 = 对存储数据的操作 二、算法 解题的方法和步骤 衡量算法的标准 1.时间复杂度 大概程序要执行的次数，而非执行的时间 2.空间复杂度 算法执行过程中大概所占用的最大内存 3.难易程度（即可读性） 4.健壮性 三、数据结构的地位 数据结构是软件中最核心的内容 程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言 第二部分 预备知识 一、指针 数据结构资料 - 2 - 指针的重要性：指针是C语言的灵魂

定义 地址：内存单元的编号 从零开始的非负整数 范围：0--FFFFFFFF（即0--4G-1） 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（只能进行减运算） 分类： 1.基本类型的指针 2.指针和一维数组的关系 二、结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求 什么叫结构体 结构体是用户根据实际需要自己定义的数据类型 如何使用结构体 两种方式： struct Student st = {1000, "zhangsan", 20} struct Student * pst = &st; 1.st.sid 2.pst->sid pst所指向的结构体变量中的sid这个成员 数据结构资料 - 3 - 注意事项

结构体变量不能加减乘除，但可以相互赋值 普通结构体变量和结构体指针变量作为函数传参问题 三、动态内存的分配和释放 假设动态构造一个int型的一位数组 int len； int * pArr = (int *)malloc (sizeof(int) * len); ①本语句分配了两块内存，一块内存是动态分配的，总共len个字节；另一块是静态分配的，是pArr变量本身所占的内存，总共4个字节。 ②malloc只有一个int型的形参，表示要求系统分配的字节数 ③malloc函数的功能是请求系统分配len个字节的内存空间，如果分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL ④malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此，malloc函数前面必须加强制类型转换（数据类型 *），表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。 ⑤free（* pArr） 表示把pArr所指向的内存给释放掉 pArr本身的内存是静态的，不能有程序员手动释放，只能在pArr变量所在的函数运行终止时有系统自动释放 ⑥跨函数使用内存 静态内存不可以跨函数使用： 静态内存在函数执行期间可以被其它函数使用 静态内存在函数执行完毕之后就不能在被其它函数使用 数据结构资料 - 4 - 动态内存可以跨函数使用

动态内存在函数执行完毕之后仍然可以被其它函数使用 第三部分 模块一：线性结构 [把所有的结点用一条直线穿起来] 一、连续存储[数组] 1.什么叫做数组 元素类型相同，大小相等 2.数组的优缺点（相对于链表） 优点：存取速度快 缺点：实现必须知道数组的长度 需要大块连续的内存块 插入和删除元素很慢 空间通常是有限制的 二、离散存储[链表] 1.定义 N个结点离散分配 彼此通过指针相连 每个结点只有一个前驱结点，每个结点只有一个后续结点 首结点没有前驱结点，尾结点没有后续结点 专业术语： 首结点：第一个存放有效数据的结点 尾结点：最有一个存放有效数据的结点 头结点：头结点的数据类型和首结点的类型是一样的 首结点之前的结点 头结点并不存放有效数据 数据结构资料 - 5 - 加头结点的目的是为了方便对链表的操作

头指针：指向头结点的指针变量 尾指针：指向尾结点的指针变量 确定一个链表需要几个参数： （如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参数） 一个参数，即头指针，因为我们通过头指针可以推算出链表的其它所有的信息 2.分类 单链表 双链表：每一个结点有两个指针域

循环链表：能通过任何一个结点找到其它所有的结点 非循环链表 3.算法 遍历 / 查找 / 清空 / 销毁 / 求长度 / 排序 / 删除结点 / 插入结点 插入结点：(伪算法) ① r = p->pNext; p->pNext = q; q->pNext = r; ② q->pNext = p->pNext; p->pNext = q;(这两行代码不能倒过来) 删除结点：（伪算法） r = p->pNext; p->pNext = p->pNext->pNext; free(r); 狭义的算法是与数据的存储方式密切相关 广义的算法是与数据的存储方式无关 泛型： 利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的 数据结构资料 - 6 - 同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和

图），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以对它执行相同的操作 4.链表的优缺点（相对于数组） 优点：空间没有限制 插入和删除元素很快 缺点：存取的速度很慢 三、线性结构的两种常见应用之一 栈 1.定义：一种可以实现“先进后出”的存储结构 栈类似于箱子 2.分类 静态栈：以数组为内核 动态栈：以链表为内核 3.算法 出栈 / 入栈 4.应用 函数调用 / 中断 / 表达式求值 /内存分配 / 缓冲处理 / 迷宫 四、线性结构的两种常见应用之一 队列 1.定义：一种可以实现“先进先出”的存储结构 队列类似于排队买票 2.分类 链式队列 ---- 用链表实现 静态队列 ---- 用数组实现 静态队列通常都必须是循环队列 数据结构资料 - 7 - 循环队列的讲解：

①静态队列为什么必须是循环队列 普通队列的参数front和rear只增不减，导致内存浪费 ②循环队列需要几个参数来确定 需要两个参数：front / rear ③循环队列各个参数的含义 两个参数在不同的场合有不同的含义 ①队列初始化 front 和 rear 的值都为零 ②队列非空 front 代表的是队列的第一个元素 rear 代表的是队列的最后一个有效元素的下一个元素 ③队列空 front 和rear 的值相等，但不一定是零 ④循环队列入队伪算法讲解(在尾部入队) 第一步：将值存入rear所指向的位置 第二步：rear = (rear + 1)%数组的长度 ⑤循环队列出队伪算法讲解（在头部出队） front = (front +1)%数组的长度 ⑥如何判断循环队列为空 如果front 与rear的值相等，则该队列一定为空 ⑦如何判断循环队列为满 第一种方法：多增加一个标识参数，即数组的长度 （常用）第二种方法：少用一个元素，如果front == (rear + 1)%数组的长度，则数据结构资料 - 8 - 循环队列已满

3.算法 出队 / 入队 4.应用 所有和时间有关的操作都有队列的影子 五、专题：递归（使用栈实现的） 1、定义:一个函数自己直接或间接调用自己 2、函数的调用 当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事： a、将所有的实际参数、返回地址等信息传递给被调函数保存 b、为被调函数的局部变量（包括形参）分配存储空间 c、将控制转移到被调函数的入口 从被调函数返回主调函数之前，系统也要完成三件事： a、保存被调函数返回结果 b、释放被调函数所占的存储空间 c、依照被调函数保存的返回地址将控制转移到调用函数 当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都在栈顶位置。 A函数调用A函数与A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已。