 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》线性表的顺序存储【讲解】 |
|
线性表的顺序存储结构
1.线形表介绍 把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称顺序表。 假设顺序表的每个元素需占用l个存储单元，并以第一个元素所占的存储地址作为元素的存储位置，则顺序表中第i+1个元素的存储位置LOC( ai+1)和第i个元素的存储位置LOC(ai )之间满足下列关系： LOC(ai+1)=LOC(ai)+l 顺序表的第i个元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l 在顺序表中，每个元素ai的存储地址是该元素在表中的位置i的线性函数。只要知道基地址和每个元素的大小，就可在相同时间内求出任一元素的存储地址。在这种存储方式下，容易实现表中元素的定位。而且，要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。 2.顺序表上实现的基本操作 [注意：以下所提到的“第i个位置”是逻辑位置，对应的物理位置为“i 减1”，即逻辑位置从1开始，物理位置从0开始] 以下主要讨论顺序表的插入和删除两种典型运算算法和时间复杂度。 1、 插入 在顺序表中，元素的物理顺序必须和元素的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的元素，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新元素x。仅当插入位置i=n+1时，才无须移动元素，直接将x插入表的末尾。 在表的第i(1≦i≦)n+1个位置上，插入一个新元素使长度为n的顺序表 (a1，…a i-1，ai，…，an) 变成长度为n+1的顺序表 (a1，…a i-1，x，ai，…，an) 分析算法的复杂度： 这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移操作上，该操作的执行次数（即移动元素的次数）是n-i+1。由此可看出，所需移动元素的次数不仅依赖于表的长度n，而且还与插入位置i有关： <1> 当i=n+1时，由于循环变量的终值大于初值，元素后移操作将不进行，只是相当于在表的末尾增加了一个元素，这是最好情况，其时间复杂度O（1）。 <2> 当i=1时，元素后移操作将循环执行n次，需移动表中所有元素，这是最坏情况，其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。 在长度为n的顺序表中第i个位置上插入一个元素，令Eis(n)表示移动元素的期望值（即移动的平均次数），则在第i个位置上插入一个元素的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入元素的机会是均等的，则 p1=p2=p3=…=pn+1=1/(n+1) 因此，在等概率插入的情况下 也就是说，在顺序表上做插入运算，平均要移动表上一半元素。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 2、删除 顺序表的删除运算是指将表的第i(1≦i≦n)个元素删除，使长度为n的顺序表： (a1，…a i-1，ai，a i+1…，an) 变成长度为n-1的顺序表，删除点之后的元素都要左移一位，如删除第i个元素之后顺序表中元素变为 (a1，…a i-1，a i+1，…，an) 当要删除元素的位置i不在表长范围（即i＜1或i＞n）时，为非法位置，不能做正常的删除操作。 分析算法的复杂度： 该算法的时间分析与插入算法相似，元素的移动次数也是由表长n和位置i决定。 <1> 若i=n，则由于循环变量的初值大于终值，前移操作将不执行，无需移动元素，这种情况下算法的时间复杂度为O(1)。 <2> 若i=1，则前移操作将循环执行n-1次，需移动表中除开始元素外的所有元素，这种情况下算法的时间复杂度为O(n)。 删除算法的平均性能分析与插入算法相似。在长度为n的顺序表中删除一个元素，令Ede(n)表示所需移动元素的平均次数，删除表中第i个元素的移动次数为n-i，故 式中，pi表示删除表中第i个元素的概率。在等概率的假设下， p1=p2=p3=…=pn=1/n 由此可得 即在顺序表上做删除运算，平均要移动表中约一半的元素，平均时间复杂度也是O(n)。 3.学习建议及练习任务 栈的实现原理也是基于连续地址的顺序存储结构的，学习者在理解线性表的顺序存储结构后，可以尝试实现一个类似于栈的算法，在这里暂且称为表栈，要求如下： 1.定义表栈空间，要求表栈的栈底为表栈空间的起始地址（这一点与栈相反）。 2.拥有入表栈、出表栈操作（自定义）。 3.元素操作规则是先入后出，即最后放进表栈的元素出表栈的时候最先出表栈。 4.表栈溢出提示。 5.将表栈中的元素实时显示到屏幕。 [07/09/21] |