计算机算法1大全PPT课件

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