单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。

利用单向链表结构绘制聚类谱系图的算法

本文介绍了一种利用聚类分析结果绘制聚类谱系图的新方法。利用单向链表结构可以方便地把杂乱无章的聚类信息排列起来绘成谱系图。文中给出了详细的算法和相应的ＦＯＲＴＲＡＮ程序。

微视频在单向链表教学中的开发与设计

将微视频融入以案例为基础的C语言教学中,特别是在单向链表的教学中,有着良好的教学效果。笔者讲解了如何将单向链表的建立、插入和删除三种操作利用微视频开发并设计。

单向链表在高速缓存中的应用

在中国石油油气管道SCADA系统的实时库软件中,在数据转发缓存中采用了单向链表,在模拟发送的情况下,达到了每秒写入130万以上数据块的极高性能,满足了系统的高性能处理需求。

基于单向哈希链表树的轻量蜂窝IP切换认证协议

对蜂窝IP网络的安全性尤其是快速切换安全性进行研究,提出了一种新的轻量蜂窝IP切换认证协议。该协议利用单向哈希链表树,实现蜂窝IP网络通信实体间的安全注册和切换认证。分析表明,该协议与蜂窝IP协议相结合,将为无线通信中数据交互及快速切换提供有效的安全保证。

基于单向指针链表的快速搜索算法的实现

本文通过对单向指针链表数据的存贮和快速搜索的研究，结合一些成熟的搜索算法，在VC和TC语言中实现了基于单向指针链表的快速搜索算法，并给出了算法相关的具体原理和实现代码。本算法摈弃了单向指针链表数据的逐点循序搜索算法的缺点，加快了搜索速度。进一步发挥了单向指针链表数据的优势。

基于单向并行多链表的流管理

高速条件下数据访存是流管理的瓶颈,传统表项操作"读-处理-写"模式效率仅为36%,读写转换和读写延时是制约效率的重要因素。针对这个问题,提出了连续读写法处理表项,通过合并读写时延和复用读写转换的方式使表项操作效率超过90%;并在此基础上提出了单向并行多链表法。通过多个链表的交替操作,使连续读写法应用于处理不活动超时流。理论分析和实验表明,单向并行多链表法能够适用于OC-768(40Gbps)链路下管理千万条表项明显优于辅助存储法和双向链表法的OC-192(10Gbps)下百万条表项的管理能力。

一种处理交点退化现象的高效多边形裁剪算法

针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象,提出了一种能够处理交点退化现象的高效多边形裁剪算法.该算法利用单向链表实现多边形的存储,同时基于单调链的平面扫描法求解多边形间的交点,减少了多边形顶点的遍历次数和求交次数;对于重点和重边现象,通过交点关联的线段间的方向关系判别交点的进出性;最后更新多边形顶点序列,获取裁剪结果.实验结果表明,该算法能够完成对含内环多边形的裁剪,在交点退化情况下也能获得准确的裁剪结果.且该算法裁剪效率较Greiner-Hormann算法大幅提高,具有很高的执行效率和实用性.

嵌入式系统实时中值滤波的高效实现

为了满足嵌入式系统实时数字滤波的需要,针对抗脉冲干扰能力较好的中值数字滤波,提出一种存储量小、运算速度快的高效算法。该算法利用循环存储结构,在存储实时新数据的同时,自动剔除最老的旧数据,释放其所占用的存储资源,避免为新到来的数据申请存储资源。利用排序链表存储中值滤波的原始数据,避免了其他中值滤波算法在排序时必需的数据移动或交换,使中值滤波算法中的排序计算量降低到O(N)级,提高了算法效率。实测对比表明,提出的中值滤波算法的存储器使用量至多是传统中值滤波算法的37%,运算速度至少是Matlab函数库medfilt1()给定算法的2倍。

筛选法求素数

介绍了用链表、数组和指针、集合与可视化语言提供的动态数组,其中前两种方法用C语言作了详细介绍,第一和第四种方法可突破空间的限制。

利用多种方法求解数据结构算法问题的评析

2009年计算机专业硕士研究生考试同以往有所改变,数据结构作为一门重要的专业课在考试中占有较高的地位。对于改革后的第一次考试,算法问题在试卷中体现的较为灵活与新颖,其基本目的就是考察学生在不断总结与理解的过程中寻求一个又好又快的算法。本文以09年硕士研究生考试的算法综合题为例,利用多种方法求解并进行综合比较,最终得出既优秀又快捷的算法。

微型GPS接收机的设计

阐述了以Jupiter OEM板为核心的GPS接收机的软硬件设计,采用芯片SP2339实现了串口的硬件扩展,使用以ST7920为核心控制芯片的128*64液晶屏显示接收到的数据,在嵌入式程序中使用单向链表完成数据的存储处理,设计完成的GPS接收机能够快速定位、测量野外站点坐标。

线性数据结构的Visual Basic描述与实现

通过给出一种基于VisualBasic编程的线性数据结构实现范例熏研究与探讨利用数组和自定义数据类型描述链表、栈和队列等线性数据结构的构造方法。

三维激光扫描下建筑内墙微小缝隙识别模型

为降低建筑内墙微小缝隙识别模型时的点位误差,提出一种三维激光扫描下建筑内墙微小缝隙识别模型方法。基于三维激光扫描技术,采用激光扫描仪以及电子全站仪这两种仪器采集建筑内墙微小缝隙三维数据。对建筑内墙微小缝隙三维数据实施预处理,使数据能够分层按照垂直方向存储。通过Geomagic studio软件构建建筑内墙微小缝隙识别模型,具体构建过程包括三个阶段:第一个阶段是点阶段、第二个阶段是多边形阶段、第三个阶段是曲面阶段。实验结果证明,该方法的点位误差小于原有方法,仅为7.7 mm,且整体耗时较少,平均为190.4 ms,输出的信噪比较高,平均为149.6 dB,具有一定应用价值。