数据结构与算法知识总结资源-CSDN文库

数据结构

需积分: 5 47 浏览量 2023-05-10 09:59:07 上传评论 1 收藏 4.03MB PDF 举报

资源推荐

资源详情

资源评论

数据结构与算法

嵌入式

2021-12-31

作者:九月

邮箱:3154643536@qq.com

目录 
前言 ................................................................................................................................................................ 1 
数据结构简介 ......................................................................................................................................... 8 
逻辑结构和物理结构 ........................................................................................................................... 8 
1.逻辑结构 .................................................................................................................................... 8 
1.1.集合结构 ....................................................................................................................... 8 
1.2.线性结构 ....................................................................................................................... 8 
1.3.树性结构 ....................................................................................................................... 8 
1.4.图性结构 ....................................................................................................................... 9 
2.物理结构 .................................................................................................................................... 9 
2.1.顺序存储结构 ............................................................................................................. 9 
2.2.链式存储结构 ............................................................................................................. 9 
算法概述 .................................................................................................................................................. 9 
1 算法的特性 ................................................................................................................................. 9 
2 算法设计的要求 ...................................................................................................................... 10 
3 算法时间复杂度 ...................................................................................................................... 10 
3.1.算法时间复杂度定义 .............................................................................................. 10 
3.2.时间复杂度的计算 .................................................................................................. 10 
3.3.最坏情况和平均情况的时间复杂度 .................................................................. 11 
4 算法空间复杂度 ...................................................................................................................... 11 
线性表 ..................................................................................................................................................... 11 
1.线性表的顺序存储结构 ....................................................................................................... 12 
1.1.获取元素操作 ........................................................................................................... 12 
1.2.插入操作 ..................................................................................................................... 12 
1.3.删除指定值操作 ....................................................................................................... 14 
1.4.清空操作 ..................................................................................................................... 14 
1.5.线性表顺序存储的优缺点..................................................................................... 14 
2.线性表的链式存储结构 ....................................................................................................... 15 

2.1.单链表的插入操作示例 ......................................................................................... 16 
2.2.单链表的删除操作示例 ......................................................................................... 18 
2.3.单链表的优缺点 ....................................................................................................... 19 
3.链表的几种形式 ..................................................................................................................... 19 
3.1.静态链表 ..................................................................................................................... 20 
3.2.循环链表 ..................................................................................................................... 23 
3.1.双向链表 ..................................................................................................................... 23 
栈和队列 ................................................................................................................................................ 26 
1.栈的介绍 .................................................................................................................................. 27 
1.1.顺序栈的结构设计 .................................................................................................. 27 
1.2.顺序栈的插入操作 .................................................................................................. 27 
1.3.顺序栈的出栈操作 .................................................................................................. 28 
1.4.双顺序栈共享空间的设计..................................................................................... 28 
1.5.链式栈的设计 ........................................................................................................... 30 
1.6.链式栈的入栈设计 .................................................................................................. 31 
1.7.链式栈的出栈设计 .................................................................................................. 32 
1.8.栈的作用 ..................................................................................................................... 32 
2.队列的介绍 .............................................................................................................................. 41 
3.队列的程序设计示例 ........................................................................................................... 41 
3.1.入队操作示例 ........................................................................................................... 42 
3.2.出队操作示例 ........................................................................................................... 42 
4.循环队列 .................................................................................................................................. 43 
4.1 循环队列入队操作 ................................................................................................... 43 
4.2 循环队列出队操作 ................................................................................................... 43 
KMP 模式匹配算法 ............................................................................................................................... 43 
1.next 数组的推导 ................................................................................................................... 44 
2.以 next 数组进行 KMP 匹配推导算法程序..................................................................... 45 
3.KMP 改进算法的 nextval 数组推导 ................................................................................. 46 

树 .............................................................................................................................................................. 47 
1.树的一些名词含义 ................................................................................................................ 48 
2.树结构和线性结构的区别 .................................................................................................. 48 
3.树结构的存储方式 ................................................................................................................ 48 
3.1.双亲表示法 ................................................................................................................ 48 
3.2.孩子表示法 ................................................................................................................ 49 
3.3.孩子兄弟表示法 ....................................................................................................... 49 
二叉树 ..................................................................................................................................................... 50 
1.二叉树的特点 ......................................................................................................................... 50 
1.1.特殊二叉树特点 ....................................................................................................... 51 
2.二叉树的性质 ......................................................................................................................... 52 
3.二叉树的存储结构 ................................................................................................................ 53 
4.二叉树的遍历 ......................................................................................................................... 53 
4.1.前序遍历 ..................................................................................................................... 53 
4.2.中序遍历 ..................................................................................................................... 54 
4.3.后序遍历 ..................................................................................................................... 55 
4.4.顺序遍历 ..................................................................................................................... 57 
5.二叉树的建立 ......................................................................................................................... 57 
6.二叉树的结点插入 ................................................................................................................ 59 
7.二叉树的结点删除 ................................................................................................................ 60 
8.递归计算二叉树的高度，结点数和叶子结点数 ......................................................... 63 
哈夫曼树 ................................................................................................................................................ 64 
1.如何构建一颗哈夫曼树 ....................................................................................................... 65 
2.程序实现示例 ......................................................................................................................... 66 
2.1.结构定义示例 ........................................................................................................... 66 
2.2.初始化结点示例 ....................................................................................................... 67 
2.3.哈夫曼树构建示例 .................................................................................................. 67 
平衡二叉树(AVL 树) ........................................................................................................................ 68 