栈 Stack逻辑特性后进先出LIFO分类顺序栈数组实现、链栈单链表实现操作入栈、出栈、取栈顶元素、判空特点插入和删除只在同一端栈顶进行操作push 入栈头插新节点变成新 toppop 出栈删头top 往后移动后进先出 LIFO只保存一个 top栈顶指针2. 队列 Queue逻辑特性先进先出FIFO分类顺序队列、循环队列、链队列操作入队、出队、取队头、判空特点一端入队队尾另一端出队队头操作enQueue 入队尾插用 rear 直接挂新节点deQueue 出队删头删空队列时rear 要置 NULL先进先出 FIFO3. 双向链表双链表类型线性结构节点特点每个节点保存数据 前驱地址 后继地址特点可以正向、反向遍历删除节点不需要额外遍历寻找前驱双向链表头节点创建代码示例双向链表头插与单向链表思路相近但是需要同时维护next前和prev后两条指针。往前、往后两个方向箭头都要修改双向链表的整体操作都与单向链表的逻辑相近只有增删节点时需要修改相邻节点的next与prev两个方向指针4. 二叉链表类型非线性树形结构二叉树的链式存储节点特点每个节点保存数据 左孩子指针 右孩子指针遍历方式前序、中序、后序、层序遍历1.定义—递归式的定义树是n(n≥0)个结点的有限集合:当n0时称为空树;当n0时满足:有且仅有一个根结点(Root);**其余结点可分为m(m ≥0)个互不相交的有限集合T,T2…Tm每个集合本身也是一棵树称为根的子树2.结点的特点1.每个结点最多有两个子树;2.左、右子树有顺序不可互换;3.即使某结点仅有一个子树也必须明确是左子树还是右子树。访问节点顺序前序遍历 根 – 左 – 右中序遍历 左 – 根 – 右后序遍历 左 – 右 – 根层序遍历需要通过队列链表实现通过排序反推树形结构前序 中序能唯一确定二叉树。原因前序提供根节点中序利用根节点切分左右子树逻辑唯一后序 中序能唯一确定二叉树。原因后序提供根节点中序利用根节点切分左右子树逻辑唯一前序 后序不能唯一确定二叉树。原因只能确定根节点但无法划分哪些节点属于左子树哪些属于右子树创建二叉树前序遍历代码前序中序后序代码逻辑一样写法相同调整输出时间即可看到效果三种排序输出的结果5. 哈希表基本思想:记录存储位置”与关键字(要处理的数据相关的一个值)之间的对应关系组成一个数组数组每个位置挂载一条单链表作用利用哈希函数计算下标用链表处理哈希冲突特点查找速度快链表用来存放哈希值相同的元素操作插入、查找、删除、销毁哈希冲突不同关键字经过同一个哈希函数计算后得到相同哈希地址下标此时常见解决方法有1.通过开发地址法2.链地址法哈希链表创建单向链表代码示例哈希链表打印函数桶数组在栈由函数结束自动回收桶数组与在堆区空间开辟相比内存小且不能动态分配哈希链表寻找值注意由于是数组所以需要传递数组的地址二级指针哈希表修改指定的值哈希表删除指定的值哈希表销毁