《嵌入式数据结构与算法》由会员分享，可在线阅读，更多相关《嵌入式数据结构与算法（77页珍藏版）》请在金锄头文库上搜索。
1、嵌入式工程师培训嵌入式工程师培训嵌入式工程师培训嵌入式工程师培训嵌入式电子工程师2 2 2 2大纲大纲大纲大纲大纲大纲大纲大纲概述 线性表 栈和队列 树与图 查找与排序3概述4 4 4 4 著名计算机科学家沃思(Nikiklaus Wirth )提出: 程序 = 数据结构 + 算法。 数据结构：描述数据的类型和组织形式 算法：描述对数据的操作步骤 数据结构与算法：大多时候用的是旧知识 新思想概述概述概述概述概述概述概述概述5 5 5 5 数据结构 指的是计算机内部数据的组织形式和存储方 法，或者说是相互之间存在一种或多种特定关 系的数据元素的集合。 线性结构：主要包括顺序表、链表、栈、队列 等
2、，最简单的如数组。 树结构：人工智能中的“博弈树”，商业智能中 的“决策树”，多媒体技术中的“哈夫曼树”等。 图结构：各元素之间具有复杂对应关系的数据 结构，如神经网络系统，贝叶斯网络等。概述概述概述概述概述概述概述概述6 6 6 6 算法 是对特定问题求解步骤的一种描述或求 解问题的策略，它是指令的有限序列。 特征： 有穷性:执行指令的时间和次数是有限的 确定性:每一指令有确切的含义，无二义 可行性:每一操作都可以通过已经实现的基 本运算，执行有限次来实现 输入:0个或多个输入 输出:能产生1个或多个输出概述概述概述概述概述概述概述概述7线性表8 8 8 8 顺序表 用一组连续地址的内存单元
3、来存储整张 数据表信息，这种存储结构下的线性表 就叫做顺序表。 特征： 有唯一一个表名标识该顺序表 占据一块连续的内存单元 数据顺序存放，元素之间有先后关系线性表线性表线性表线性表线性表线性表线性表线性表9 9 9 9 顺序表 学生信息表，如图:线性表线性表线性表线性表线性表线性表线性表线性表10101010 顺序表 静态顺序表：容量固定，方法如定义一 个数组的方法类似。 初始化如下：线性表线性表线性表线性表线性表线性表线性表线性表11111111 顺序表 动态顺序表：容量可以动态追加，定义采用 malloc()，追加采用realloc()。 void *realloc(void *mem_a
4、ddress, unsigned int newsize); 功能：先按照newsize指定的大小分配空间，将原有数 据从头到尾拷贝到新分配的内存区域，而后释放原来 mem_address所指内存区域，同时返回新分配的内存区 域的首地址。即重新分配存储器块的地址。 返回值：如果重新分配成功则返回指向被分配内存的指 针，否则返回空指针NULL。 线性表线性表线性表线性表线性表线性表线性表线性表12121212线性表线性表线性表线性表线性表线性表线性表线性表13131313 顺序表 多维数组 可以理解成，不同的维数就是不同的构造类型，占 用不同的内存空间，即，内存偏移量不同，如： 一维数组：(ai
5、)，i个元素，一条线性 表,*(a+i)； 二维数组：(aij)，i行j列，共i*j个元素，一 张行列矩阵二维线性表,*(*a+i)； 三维数组：(aijk)，共i*j*k个元素，一个 立方容器，即i张矩阵二维表组成,*(*(*a)+i); 四维数组：(aijkm)，共i*j*k*m个元素， 可以认为是i个立方容器组成,*(*(*(*a)+i);线性表线性表线性表线性表线性表线性表线性表线性表14141414 顺序表 不管是二维还是三维还是多维数组，都可以定 义一个一维指针来指向 因为多维数组是顺序存储结构，所以最终会退 化成一维指针指向，并通过*(p+i)来遍历数组 其实即使你定义多维指针来
6、指向时，她还是会 退化成一维的 为了体现多维特点也可以定义成 int(*p).=str ，但元素访问时变得 很麻烦，要一级一级取地址直至取到内容为止线性表线性表线性表线性表线性表线性表线性表线性表15151515 顺序表 但也有另一个用 处，就是可以像 数组名一样通过 下标进行数据访 问，所以在程序 设计中可以根据 用户自己的实际 需求进行定义线性表线性表线性表线性表线性表线性表线性表线性表二维数组：int str23*(p+i)*(*(p)+i)pijint(*p)3=strint *p=str三维数组：int str234*(p+i)*(*(*(p)+i)pijkint(*p)34=str
7、int *p=str16161616 顺序表 由此我们可以看到: 静态顺序表不便于升级和维护。 动态顺序表插入或删除成员时是低效的，且 不适合用于复杂的数据结构中。 链表 链表作为动态内存管理的一种经典方式，利用 这种管理方式可以用在很多复杂的数据结构 中，算得上是一种常用基本数据结构。线性表线性表线性表线性表线性表线性表线性表线性表17171717 链表 单向循环链表 它的特点是表中最后一个结点的指针域指向 头结点，整个链表形成一个环。 由此，从表中任一结点出发均可找到表中其 他结点。线性表线性表线性表线性表线性表线性表线性表线性表18181818 链表 单向循环链表线性表线性表线性表线性表
8、线性表线性表线性表线性表19191919 链表 双向循环链表 以上讨论的链表都只能从某个结点出发，顺 着指针往一个方向寻查其它结点，为了克服 这种单向性的缺点，于是又加入了一个指针 域，用于索引另一个向方上的结点。 结点数据结构：线性表线性表线性表线性表线性表线性表线性表线性表20202020 链表 双向循环链表线性表线性表线性表线性表线性表线性表线性表线性表21212121 链表 在双向链表中间插入一个结点线性表线性表线性表线性表线性表线性表线性表线性表22222222 链表 在双向链表表头插入一个结点线性表线性表线性表线性表线性表线性表线性表线性表23232323 链表 在双向链表表尾插入
9、一个结点与在表头插入类 似 其实对于循环双向链表来说，可以没有头尾结 点概念的。 在双向链表中删除一个结点线性表线性表线性表线性表线性表线性表线性表线性表24242424 链表 共享链表 基于单双向链表，将指针域和数据域进行分 开管理，这是linux内核常见的一种链表形 式。 链表的操作形式多种多样，共享链表可以将 这些操作独立出来实现共享，从而可以提高 代码的重用性和健状性。 到此可以看到链表原来可以这样灵活的运 用，这也是开源给大家带来的幸福。线性表线性表线性表线性表线性表线性表线性表线性表25252525 链表 共享链表 操作分类： 初始化链表第一个节点 将新节点添加到链表头或尾 删除一
10、个节点 替换一个节点 将一个节点移动到链表头或尾 将一个节点移动到另一个节点的前或后面 判断一个链表是否为空或只有一个节点线性表线性表线性表线性表线性表线性表线性表线性表26262626 链表 共享链表 数据结构的实现： 通过结构体中的成员，求成员地址相对于结构 体的偏移量。 通过结构体中的成员地址，求取该成员所在结 构体的首地址。线性表线性表线性表线性表线性表线性表线性表线性表27272727线性表线性表线性表线性表线性表线性表线性表线性表28282828 栈 限定仅在表尾进行插入或删除操作的线 性表。 栈顶：表尾端 栈底：表头端 应用：数制转换，行编辑程序，树的遍 历等。 凡是对数据的处理
11、具有“后进先出”的特点，都 可以用栈这种数据结构来操作 这种LIFO的数据特征可以用下图形象表示：栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列29292929 栈栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列30303030 队列 限定只允许在表的一端插入，另一端删 除，具有先进先出特点的线性表。 队尾：允许插入的一端 队头：允计删除的一端 应用：凡是对数据的处理具有“先进先出”的特 点，都可以用队列这种数据结构来操作。 无论栈还是队列，都具有缓存数据的作 用，只是跟据实际存取需要，来选择那 种线性结构。栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和
12、队列栈和队列31313131 队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4 a a a an n n n 队队 列列 示示 意意 图图队 头队 头队 尾队 尾先 进 先先 进 先先 进 先先 进 先 出出出出FIFOFIFOFIFOFIFO32323232 队列 循环队列：栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列33333333 队列 循环队列 队尾插入信息并移动指针： rear=(rear+1)%MAX 队头取走信息并移动指针：
13、 front=(front+1)%MAX 绶冲区有信息：rear与front不相等，有可 能大于或小于 绶冲区无信息：rear = front 队满条件： (rear+1)%MAX=front(rear=0 3. di=伪随机数序列，称伪随机探测再散列。查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序60606060 哈希表 冲突处理 再散列法：Hi=RHi(key), i=1,2,k RHi均是不 同的散列函数，即在同义词产生地址冲突时计算另 一个散列函数地址，直到冲突不再发生，这种方法 不易产生“聚集”，但增加了计算时间。 链地址法：又叫拉链法，他将产生冲突
14、的元素链成 一条链表，它是一种哈希表与遍历或二分查找等其 它检索方法相结合的一种方法。 建立一个公共溢出区 查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序61616161 哈希表查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序62626262 选择法排序 从第一个元素开始作为起始值，与起始值比较 找出剩下未比较过的最值与起始值交换，即选 出一个最值出来。 步骤： 首先假设第一个元素“i”是最值。 从第二个元素下标“j”开始一个个取出与“i”进行比较 是否交换。 内循环一次则找出一个最值与“i”进行交换，否则不 变 外循环“i”所指向的值就是上一轮的最值，“i”加一后 进入下一轮比较。查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序63636363 选择法排序 选择排序处理过程：查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序查找与排序64646464 插入法排序 通过数据移动，留出合适位置插入顺序 合适的值，而无须数据交换。 步骤： 从第二个元素“i”开始绶存准备用于比较，并留出一 个空位。 将空位前的元素“j”
