《计算机算法PPT大全.ppt》由会员分享，可在线阅读，更多相关《计算机算法PPT大全.ppt（11页珍藏版）》请在三一文库上搜索。
1、算法深入学习实录,第3章走在算法的路上之分析简单的数据结构,技术支持：,目 录,第3章 走在算法的路上之分析简单的数据结构,3.1 学习编程的注意事项 （1）在学习知识之前要有足够的理解，也就是说盖房打地基之前要先有一个大概的了解、规划。 （2）做什么事情都有捷径可寻，但是有时候，在学习编程的过程中走捷径并不是一件很好的事情。,第3章 走在算法的路上之分析简单的数据结构,3.2 喜欢单挑线性表 3.2.1 线性表的特性 线性表是一个线性结构，它是一个含有n0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且仅
2、有一个前驱和一个后继节点。通常可以把一个线性表表示成一个线性序列：k1，k2，kn，其中k1是开始节点，kn是终端节点。 1. 线性结构的特征 在编程领域中，线性结构具有如下两个基本特征。 （1）集合中必存在唯一的一个“第一元素”和唯一的一个“最后元素”； （2）除最后一个元素之外，均有唯一的后继(后件)和唯一的前驱(前件)； 由n(n0)个数据元素(节点)a1，a2，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表，我们通常将非空的线性表(n0)记作： (a1，a2，an) 数据元素ai(1in)没有特殊含义，大家不必去“剖根问底”的研究它，它只是一个抽象的符号，其具体
3、含义在不同的情况下可以不同。 2. 线性表的基本操作过程 线性表虽然只是一对一的单挑，但是其操作功能非常强大，具备了很多操作技能。 3. 线性表的结构特点 均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度； 有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。,第3章 走在算法的路上之分析简单的数据结构,3.2.2 顺序表操作 在现实应用中，有两种实现线性表数据元素存储功能的方法，分别是顺
4、序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法，此方式的主要操作功能如下所示。 （1）计算顺序表的长度 （2）清空操作 （3）判断线性表是否为空 （4）判断顺序表是否为满 （5）附加操作 （6）插入操作 （7）删除操作 （8）获取表元 （9）按值进行查找,第3章 走在算法的路上之分析简单的数据结构,3.2.3 链表操作 链比顺序表要复杂一点，对于同一个数据，它可以和不相邻的数据发生关系。例如农民通常将收获的水果卖给商贩，商贩将收购的水果卖给加工厂。这是一条水果加工产业链，可以得出商贩是农民的财神、加工厂是商贩的财神这一论调。在那一年的某一天，老实的农民发现利润较低，于是拉着自己
5、的水果不远万里的亲自卖给了加工厂。这样农民伯伯获得了更大的利润，而商贩也不能怎么着，这个产业链还得继续下去。 由此可见，链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无需移动元素就而提高了运行效率。链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。,第3章 走在算法的路上之分析简单的数据结构,3.3 守规矩的先进先出的队列 3.3.1 队列基础 队列和栈一样，只允许在断点处插入和删除元素，循环队的入队算法如下所示。 （1）tail=tail+1； （2）如果tail
6、=n+1，则tail=1； （3）如果head=tai，即尾指针与头指针重合，则表示元素已装满队列，会施行上溢出错处理；否则Q(tail)=X，结束整个过程，其中X表示新入出元素。 3.3.2 链队列和循环队列 使用C语言定义链队列的格式如下所示。 typedef struct QNode ElemTypedata; struct QNode*next; QNode, *QueuePtr; typedef struct QueuePtr front; /* 队头指针，指向头元素 */ QueuePtr rear;/* 队尾指针，指向队尾元素 */ LinkQueue;,第3章 走在算法的路上之
7、分析简单的数据结构,3.3.3 队列的基本操作 （1）初始化队列Q的目的是创建一个队列 （2）入队的目的是将一个新元素添加到队尾，相当于到队列最后排队等候。 （3）出队的目的是取出队头的元素，并同时删除该元素，使后一个元素成为队头。 （4）获取队列第1个元素，即将队头的元素取出，不删除该元素，队头仍然是该元素。 （5）判断队列Q是否为空 3.3.4 队列的链式存储 当使用链式存储结构表示队列时，需要设置队头指针和队尾指针，这样做的好处是可以设置队头指的针和队尾的指针。在入队时需要执行如下三条语句。 s-next=NULL; rear-next=s; rear=s; 在C语言中，实现队列链式存储
8、结构类型的代码如下所示。 type struct linklist /链式队列的节点结构 Elemtype Entry;/队列的数据元素类型 struct linklist *next;/指向后继节点的指针 LINKLIST; typedef struct queue/链式队列 LINKLIST *front;/队头指针 LINKLIST *rear;/队尾指针 QUEUE;,第3章 走在算法的路上之分析简单的数据结构,3.4 后进先出的栈 3.4.1 什么是栈 栈允许在同一端进行插入和删除操作，允许进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。栈底是固定的，而栈
9、顶浮动的；如果栈中元素个数为零则被称为空栈。插入操作一般被称为进栈（PUSH），删除操作一般被称为退栈（POP）。 在栈中有两种基本操作，分别是入栈和出栈。 （1）入栈（Push） 将数据保存到栈顶。在进行入栈操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。入栈（Push）操作的算法如下： 如果TOP，则给出溢出信息，作出错处理。在进栈前首先检查栈是否已满，如果满则溢出；不满则进入下一步骤； 设置TOP=TOP+1，使栈指针加，指向进栈地址； S(TOP)=X，结束操作，X为新进栈的元素。 （2）出栈（Pop） 将栈顶的数据弹出，然后修改栈顶指针，使其指向栈
10、中的下一个元素。出栈（Pop）操作的算法如下： 如果TOP0，则输出下溢信息，并实现出错处理。在退栈之前先检查是否已为空栈，如果是空则下溢信息，如果不空则进入下一步骤； X=S(TOP)，退栈后的元素赋给X； TOP=TOP-1，结束操作，栈指针减，指向栈顶。,第3章 走在算法的路上之分析简单的数据结构,3.4.2 栈的基本操作 1. 顺序栈 顺序栈是栈的顺序存储结构的简称，它是一个运算受限的顺序表。假设S是SeqStack类型的指针变量，如果栈底位置在向量的低端，则S-data0是栈底元素。 2. 链栈 链栈是指栈的链式存储结构，是没有附加头节点的、运算受限的单链表，栈顶指针是链表的头指针。,谢谢您的支持 ！,2012年5月20日,技术支持：,