易语言算法入门必读篇.doc

易算法初步之一_线性表本系列讲座仅供初学编程且能熟练掌握易语言者学习。本讲座只讲一些基本的编程算法和对应概念。如果愿以学，每篇都需细细研读，彻底搞懂。写讲座很费时间。本人没有太多的业余时间。关键是水平实在有限，文笔实在是自犬，打字速度巨慢，所以讲座将不定期推出。当然，动力还是来自易友的支持和本人对易语言的感谢之情。算法需从头学起，先讲线性表吧。线性表的概念线性表作为最基本的数据结构，在编程中运用很广泛。线性表上的运算是比较简单和常用的，在研究线性表上的运算前，还是先讲讲线性表的有关概念。何谓线性表？ 现实生活中线性表的例子很多。如，英文字母表（A-Z）是线性表，其中每个字母就是一个数据元素（也称结点）。易语言中的一维数组也是线性表。每个数据成员就是结点。可以发现这些结点的之间的特点就像是用一根线一把珍珠串在一起成为一根珍珠链。任何一个珍珠最多和两个珍珠相连。线性表（Linear List) 是由n（n0)个数据元素（结点）a1，a2，.,an组成的有序序列。其中数据元素的个数n定义为表的长度。当n0时称为空表。常常将非空线性表（n0）记做：（a1,a2,.,an)(排版局限就这样表示吧）。线性表的逻辑结构前面以讲过，现在用专业的语句给大家描述一下。线性表的逻辑特征，就是其结点的邻接关系。a1称为开始结点，它没有直接前趋（“直接前趋”，是指与它相邻且在它前面的结点。）而仅有一个直接后继，“直接后继”，是指与他相邻且在它后面的结点）;an称为终端结点，它没有直接后继，而只有一个直接前趋。其余的内部结点ai（2=in-1)（a后面的字母都是小下标，没办法表示时用括号括住，_），有一个直接前趋a（i-1），和直接后继a（i+1）。明白了线性表的逻辑结构后，编程时的很多问题与此类似时，就可以抽象为线性表。在用线性表上的运算方法进行运算。在易语言中线性表的存储方式就是用一维数组。所以，我们把一维数组称为线性表。以后线性表上的运算，都是通过一维数组完成。线性表的其它存储结构在易语言中不易实现，不再我们现在的研究范围。关于结点 线性表是由一个个结点组成，结点间的邻接关系就构成线性表的逻辑结构。其内容我们以讲过。结点是什么呢？结点是数据的载体，它可以是简单的变量类型，更多时候是复杂的自定义数据类型的变量。线性表的运算。易语言以提供了一维数组的运算方法。我们现在研究他们到底是怎么实现的。理由就是，很多时候结点是很复杂的自定义数据类型的变量，这时的一维数组就无法用易语言提供的运算命令进行计算，这时就需要我们自己来写。线性表上的运算是最简单的，也是每个想学算法的人首先和必需掌握的。下节我们在讲吧易语言算法入门（2） 插入运算讲完线性表的有关概念，我们以一维数组为例来研究线性表上的基本运算。1.插入运算线性表的插入运算是指在线性表的第i（1=i=n）个位置上，插入一个新结点x，使线性表的长度为n+1。在易语言中，一维数组上插入一个数据可以直接调用 “无返回值 插入成员 （欲插入成员的数组变量，欲插入的位置，欲插入的成员数据）”系统命令。我们来研究它使怎么实现的。原理：原理很简单，当向一维数组的第i个位置插入一个数据时，第i个位置及它以后的数据依次都向后移动，将第i个位置腾出来后，把所要插入的数据写入该位置。算法：1.首先增加数组的长度。在易语言中可以用“加入成员”和“重定义数组”两种方法。前者可能更快些。2.移动数据。不破坏数据，当然是从数组的最后位置向前移动了。可设一个位置变量p指向最后位置。data 是定义的一维数组，长度为n。datap,就是我们插入数组尾部的空数据。 datap=datap-1 把数组的倒数第二个数据移到尾部。然后pp-1 ，p指向数组的倒数第二个数据， datap=datap-1 把数组的倒数第三个数据移到数组的倒数第二个位置上，.依次移动，最后把数组的第i个位置上的数据移到i+1的位置上。3.把需要插入的数据插入到datai。ok子程序：插入数据返回值类型：逻辑型参数：欲插入数组 数据类型：整数型 ，参数：欲插入数据 数据类型：整数型参数：插入位置 数据类型：整数型局部变量：p 数据类型：整数型如果真 (插入位置 1 或 插入位置 取数组成员数 (欲插入数组) 返回 (假)如果真结束加入成员 (欲插入数组, 欲插入数据)p 取数组成员数 (欲插入数组)判断循环首 (p 插入位置) 欲插入数组 p 欲插入数组 p 1 p p 1判断循环尾 ()欲插入数组 插入位置 欲插入数据返回 (真)是不是很简单，但这些都是我们以后研究复杂算法的基础。下节讲线性表上的删除运算。别忘了顶，你们的支持是我最大的动力！这个是上传的 e 格式文件 点击查看例1易语言算法入门（3） 删除运算上节讲了往数组中插入一个数据的方法，这是我这个“易语言算法入门”教程所讲的第一个算法，以后将陆续讲解线性表（顺序存储结构）与非线性表（顺序存储结构）上的各种基本运算方法。在易语言中，描述线性表上的运算方法时，我们是以一维数组举例的。一维数组中数据（结点）在逻辑上是顺序相连的，并且它们在计算机中内存中也是顺序存储的，我们一般称顺序存储的线性表为顺序表。注意，顺序表是从存储方式上来描述表结构的；线性表则是从逻辑上描述表结构的。表结构从逻辑上可分为线性表和非线性表。线性表和非线性表都可以用两种方式存储，即顺序存储（如数组），和链式存储。表的链式存储方式需要指针，在易语言中无法描述，不是我讨论的范畴。我们讨论的范围是顺序存储的线性表和非线性表上的运算。这样的运算还是很丰富的，在易语言中都可以实现。在易语言中顺序表是建立在一维数组基础上的表结构。本教程所讲的运算均是顺序表上的运算。本节讲述顺序表上的删除运算：原理： 删除运算也是通过移动结点来完成的。删除i结点时，我们只要把i后面的结点依次向前移动。在一维数组中把欲删除的位置后面的数据依次前移，把最后位置的数组成员删除，便完成了此运算。只有删除最后位置上的数据时不需要移动数据，直接删除该成员。用以下代码来完成此运算。子程序：删除数据返回值类型：逻辑型参数：欲操作数组 数据类型：整数型 ，参数：删除位置 数据类型：整数型局部变量：p 数据类型：整数型局部变量：i 数据类型：整数型如果真 (删除位置 1 或 删除位置 取数组成员数 (欲操作数组) 返回 (假)如果真结束p 删除位置变量循环首 (删除位置, 取数组成员数 (欲操作数组) 1, 1, i) 欲操作数组 p 欲操作数组 p 1 p p 1变量循环尾 ()删除成员 (欲操作数组, 取数组成员数 (欲操作数组), 1)返回 (真)源代码及演示例程这个是上传的 e 格式文件 点击查看例2下节讲查找运算。易语言算法入门（4） 查找运算顺序表上的查找运算有很多种。如顺序查找法、二分法、分块查找法等。我们先来介绍顺序查找法，顺序查找法，就是在表中顺序对比结点和欲查找数据的值，相同则返回相应的位置值。其过程，就是对表的顺序扫描。这是一种方法简单，但效率不高的查找方式。以下是运算代码：子程序：查找数据返回值类型：逻辑型参数：欲操作数组 数据类型：整数型 ，参数：欲查找数据 数据类型：整数型参数：查找位置 数据类型：整数型 局部变量：i 数据类型：整数型计次循环首 (取数组成员数 (欲操作数组), i) 如果真 (欲操作数组 i 欲查找数据) 查找位置 i 返回 (真) 如果真结束计次循环尾 ()返回 (假)二分查找以前讨论过，这里不讲了。其它查找均较为复杂，以后在讲。从下节起，讲几个排序算法。这个是上传的 e 格式文件 点击查看例3易语言算法入门（5） 排序算法（一）从本节开始我们我们慢慢增加算法的难度。我们讲的算法都是编程中一些常用的算法，都是一些有共性的东西。这些东西学会了，编程水平自然会上一个层次。本节讲排序运算。首先讲插入排序法。插入排序的基本思想是：每次把一个待排序的结点，按其关键字的大小插入到前面已排序好结点中，直到全部结点插入完毕。1.直接插入排序法 两个重要概念。有序区：是指顺序表中已排序好的部分。无序区：即表中未进行排序的区域。例如，一维数组2，5，6，2，9，5，47 有序区的范围是：【1，3】（从1到3结点），无序区是：【4，7】（从4到7结点）。对于任何一个结点为n（n1)的顺序表,其初始有序区的范围是【1，1】无序区的范围是【2，n】。大家能否理解呢？（道理很简单，一个结点自然是有序的。）插入排序的基本思想就是不断增大有序区，减小无序。直到无序区消失。直接插入排序的原理： 每次将无序区的第一个结点插入到有序区中。例，无序数组8，5，6，4，3，9，4，其初始有序区【1，1】,无序区【2，7】，第一次插入运算，将无序区第一个结点“5”查到前面的有序区中。运算后数组为5,8,6,4,3,9,4,有序区为【1，2】无序区为【3，7】。第二次插入运算，将无序区的第一个结点“6”插入到前面的有序区中，运算后的数组为5,6,8,4,3,9,4,其有序区为【1，3】，无序区减小成【4，7】。如此重复，经过6次插入运算，有序区成为【1，7】，无序区消失。此数组成为有序数组。程序代码：子程序：直接插入排序参数：欲操作数组 数据类型：整数型 ，局部变量：结点个数 数据类型：整数型 /:数组的长度局部变量：无序区首 数据类型：整数型 /:指向无序区第一个结点的指针。局部变量：插入点 数据类型：整数型 /:将无序区第一个结点插入到有序区中的位置 局部变量：暂存容器 数据类型：整数型 /:暂时存放无序区第一个结点的数据，局部变量：移动点 数据类型：整数型 /:移动数据时的控制变量结点个数 取数组成员数 (欲操作数组)如果真 (结点个数 1) 返回 ()如果真结束变量循环首 (2, 结点个数, 1, 无序区首) /:需要进行n-1次插入运算。 计次循环首 (无序区首 1, 插入点) /:在有序区中寻找插入位置。 如果真 (欲操作数组 无序区首 欲操作数组 插入点) /:此为升序排序的插入条件。 跳出循环 () /:找到了插入位置。 如果真结束 计次循环尾 () 暂存容器 欲操作数组 无序区首 变量循环首 (无序区首, 插入点 1, -1, 移动点) /:前面讲的插入运算 欲操作数组 移动点 欲操作数组 移动点 1 变量循环尾 () 欲操作数组 插入点 暂存容器变量循环尾 ()本段代码用到了前面讲的查找算法和插入算法。掌握一些基本算法，可以提高编程能力。 这个是上传的 e 格式文件 点击查看例4练习：去掉数组中重复的数据，即数组中没有重复的数据。易语言算法入门（5） 排序算法（二）帖子被锁，开新帖讨论上节未讲完的内容。直接插入排序法的代码在执行过程中，大部分时间是消耗在查找插入点位置和移动结点上。结点的移动是必须的，此类算法是无法减少移动次数的，除非是用新的算法。而每次都从无序区首（即表的第一个结点）开始寻找插入点的过程是完全没有必要的，可以用我们讲过的二分查找法优化此过程。二分查找法我和老鸟都讲过，此处不再重复。以下是实现代码，c语言算法书上是没有的，是俺活学活用的即兴之做。子程序：二分直接插入排序参数：欲操作数组 数据类型：整数型 ，局部变量：结点个数 数据类型：整数型局部变量：无序区首 数据类型：整数型局部变量：插入点 数据类型：整数型局部变量：暂存容器 数据类型：整数型局部变量：移动点 数据类型：整数型局部变量：首位置 数据类型：整数型局部变量：末位置 数据类型：整数型局部变量：中间位置 数据类型：整数型结点个数 取数组成员数 (欲操作数组)如果真 (结点个数 1) 返回 ()如果真结束变量循环首 (2, 结点个数, 1, 无序区首) 首位置 1 末位置 无序区首 1 判断循环首 (首位置 末位置) 中间位置 取整 (首位置 末位置) 2) 如果 (欲操作数组 无序区首 欲操作数组 中间位置) 插入点 中间位置 末位置 中间位置 1 否则 如果 (欲操作数组 无序区首 欲操作数组 中间位置) 首位置 中间位置 1 否则 插入点 中间位置 跳出循环 () 如果结束 如果结束 判断循环尾 () 如果真 (插入点 0) 暂存容器 欲操作数组 无序区首 变量循环首 (无序区首, 插入点 1, -1, 移动点) 欲操作数组 移动点 欲操作数组 移动点 1 变量循环尾 () 欲操作数组 插入点 暂存容器 插入点 0 如果真结束变量循环尾 ()这个是上传的 e 格式文件 点击查看例5易语言算法入门（5） 排序算法（三）上节对直接插入排序进行了优化，我们暂且把优化算法称为二分直接插入排序，这种算法仅仅事对寻找插入点的过程做了优化。如果我们能找到另一中方法，可同为减少寻找插入点的次数和移动结点的次数，就可显著的提高排序的运算速度。本节介绍的希尔排序算法是直接插入排序法的一种变种，它能有效的减少这两个方面的运算量，从而显著的提高排序操作的运算速度。原理： 先取一个小于结点数的整数k作为分组单位，把表上的所有相距k的结点逻辑上看成一组。在个组内进行直接插入排序；减小k的取值，把表上的所有相距k的结点逻辑上看成一组。在个组内进行直接插入排序；重复以上步骤；最后一次k取1，即对整个表做直接插入排序。其中k称为增量，增量的取值集合称为增量表。例，无序数组4,5,8,2,6,8,9,2,4,5,1,6,1,5,4,2 增量表我们取成“5，3，1”（k的取值集合）1.当k5为，表上的逻辑分组情况为：【1，6，11。16】【2，7，12】【3，8，13】【4，9。14】【5，10，15】（【 】内均是数组的下标值）。k5为的组内进行直接插入排序过程为：第一组：数组成员分别为“4”，“8”，“1”，“2”。排序后的数组1,5,8,2,6,2,9,2,4,5,4,6,1,5,4,8 第二组：数组成员分别为“5”，“9”，“6”。 排序后的数组1,5,8,2,6,2,6,2,4,5,4,9,1,5,4,8 第三组：数组成员分别为“8”，“2”，“1”。 排序后的数组1,5,1,2,6,2,6,2,4,5,4,9,8,5,4,8 第四组：数组成员分别为“2”，“4”，“5”。 排序后的数组1,5,1,2,6,2,6,2,4,5,4,9,8,5,4,8 第五组：数组成员分别为“6”，“5”，“4”。 排序后的数组1,5,1,2,4,2,6,2,4,5,4,9,8,5,6,8 此趟运算后数组为1,5,1,2,4,2,6,2,4,5,4,9,8,5,6,82.当k3为，表上的逻辑分组情况为：【1，4，7，10，13，16】【2，5，8，11，14】【3，6，9，12，15】（【 】内均是数组的下标值）。k3为的组内进行直接插入排序过程为：第一组：数组成员分别为“1”，“2”，“6”，“5”，“8”，“8” 排序后的数组1,5,1,2,4,2,5,2,4,6,4,9,8,5,6,8 第二组：数组成员分别为“5”，“4”，“2”，“4”，“6”。 排序后的数组1,2,1,2,4,2,5,4,4,6,5,9,8,6,6,8 第三组：数组成员分别为“1”，“2”，“4”，“9”，“6”。 排序后的数组1,2,1,2,6,2,6,2,4,5,4,6,8,5,9,8 此趟运算后数组为1,2,1,2,6,2,6,2,4,5,4,6,8,5,9,8 3.当k1为，表上的逻辑分组情况为：【1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16】（【 】内均是数组的下标值）。即整个表分为一个组，此时对整个表做直接插入表排序，可以发现此趟运算时结点移动是非常少的。此趟运算后数组为有序数组。通过以上详细的运算过程描述，我们可以发现：当k值很大时，组很小，查找和移动量都很小，随着k值增大，组虽然增大，查找运算量增大了，但最耗时间的移动结点运算量却在减小。总的排序运算耗时是显著的减小，效率成倍提高。希尔排序法的整体性能与增量表的取值有密切的关系。最佳的增量表取值组合，在数学上还没有证明出来。我们一般取一些奇数、质数，但不要