数据结构:树和二叉树

点击量:112

在数据结构中,存在着线性结构和非线性结构两种,而树型结构就是其中的一种非线性结构,最常用的有树和二叉树。树是一种以分支关系定义的层次结构,其实例广泛存在与人类的社会生活中的方方面面,比如社会组织机构中的层次关系等。在计算机领域中,树在编译程序、数据库系统中,也有着很重要的应用。

继续阅读“数据结构:树和二叉树”

数据结构:队列

点击量:75

队列是一种先进先出(FIFO, first in first out)的线性表,这一点跟栈是刚好相反的。这种数据结构只允许在表的其中一端插入元素,在另一端删除元素,就像我们日常生活中的排队一样。在队列中,最早进入队列的元素是最早离开的,进入越晚的元素离开的也越晚,不能从中间插队。

继续阅读“数据结构:队列”

数据结构:栈

点击量:92

栈是数据结构中的一种重要的线性结构,也是一种线性表,只是其操作受限。使用的过程,就像往桶里装和取物品一样,最先放进去的物品必须把后来放进去的压在上面的物品拿出去,才能取出。因此,栈是一种限定性的数据结构,其广泛应用与各类软件系统中。本文主要介绍栈的原理,并以一些应用实例来说明栈的功能。

继续阅读“数据结构:栈”

数据结构:线性表

点击量:98

数据结构中的线性表是一种线性结构的数据集合,是n个数据元素的有限序列,其存在唯一的一个被称作“第一个”的数据元素,也存在着唯一的一个被称作“最后一个”的数据元素,每个元素至多只有一个前驱和一个后继。其中,第一个元素没有前驱,最后一个元素没有后继。我们编程中最常用的一维数组(Array类)就是一种典型的线性表结构,高级一点的比如列表(List类),也是一种典型的线性表结构。这是一种最常用且最简单的数据结构。

继续阅读“数据结构:线性表”

渗漏问题算法

点击量:62

给定由随机分布的绝缘材料和金属材料构成的组合系统:金属材料占多大比例才能使组合系统成为电导体?给定一个表面有水的多孔景观(或下面有油),水将在什么条件下能够通过底部排出(或油渗透到表面)?科学家们已经定义了一个称为渗透(percolation)的抽象过程来模拟这种情况。

继续阅读“渗漏问题算法”

C语言基于MPI并行计算矩阵的乘法

点击量:138

矩阵的计算是并行计算里的一个很重要的问题。矩阵是一种网格化的数据,是一组同类型数值的集合,矩阵的出现,使得代数系统更完善,对各种实际问题的求解产生了巨大的作用。但是其庞大的计算量往往令人生畏,稍微大一点的矩阵,计算就变得非常繁琐,不仅仅是人,而且串行计算的程序,也同样会变得非常缓慢。这时我们就需要并行计算来解决这些问题了。

本文使用分治思想,利用主从节点方式,实现了一个并行计算的矩阵相乘程序,并将结果跟串行程序做了对比,计算了其加速比。

继续阅读“C语言基于MPI并行计算矩阵的乘法”

几种排序算法的实现和性能比较

点击量:123

在各种各样的排序任务中,不同的算法有着不同的效果和性能,比如稳定性、时间开销、空间开销等。本文中实现了5种排序算法:
插入排序(Insertion Sort,IS)、
自顶向下归并排序(Top-down Mergesort,TDM)、
自底向上归并排序(Bottom-up Mergesort,BUM)、
随机快速排序(Random Quicksort,RQ)和
Dijktra 3路划分快速排序(Quicksortwith Dijkstra 3-way Partition,QD3P),
并且在同一台普通计算机上,针对不同输入规模的数据进行了测试,对比了上述排序算法的时间性能。

继续阅读“几种排序算法的实现和性能比较”

组合数学实现关于购票问题的求解以及多种算法实现的性能比较

点击量:82

  】程序设计中有一类问题是购票问题,在整钱找零钱时怎样的队伍排列可以使得售票处不会出现找不开零钱的局面。本文将采用五种算法分析这道题目,并对各种算法的效率加以比较。从中可以看出组合数学理论在算法优化方面起到的显著作用。

继续阅读“组合数学实现关于购票问题的求解以及多种算法实现的性能比较”

基于字典的简单中文分词算法

点击量:303

做自然语言处理,尤其是中文自然语言处理,文本分词是必不可少的过程。其实不仅仅是中文,大多数亚洲的语言文字在计算机做处理时,都需要进行分词,甚至英文在识别短语时也要进行类似中文分词的过程。所以,我们需要一种有效的分词算法,这里我仅以中文做实例,其他语言可以参考,介绍一种简单的中文分词算法,并附上一个C#版的示例代码。

继续阅读“基于字典的简单中文分词算法”