快乐不是因为拥有的多而是因为计较的少

2008年10月的内容

堆排序算法总结
技术文档

堆排序算法总结

2008-10-27 最后修改:2009-08-19 07:25 11931浏览 1评论 简洁版

1、 堆排序定义
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
注意:
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

阅读更多...

几种内部排序算法总结--c++版
技术文档

几种内部排序算法总结–c++版

2008-10-26 最后修改:2009-08-19 07:25 213893浏览 0评论 简洁版

1 #include <iostream>
2 using namespace std;
3
4 /*/////////////////////////////////////////////////////////////////////////
5 以下为快速排序
6 /////////////////////////////////////////////////////////////////////////*/
7 /*
8 冒泡排序
9 算法:
10 核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找到这两个项目后
11 交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
12 时间复杂度n*n  (n-1)*n/2
13 */
14 void BubbleSortData(int SortData[], int Length)
15 {
16 int tmpData =0;
17 bool swapFlag =true;
18
19 for (int i=Length-1; i>0 && swapFlag; i--)
20 {
21 swapFlag =false;
22 for(int j=0; j<i; j++)
23 {
24 if ( SortData[j] > SortData[j+1])
25 {
26 tmpData =SortData[j];
27 SortData[j] =SortData[j+1];
28 SortData[j+1] =tmpData;
29 swapFlag =true;
30 }
31 }
32 }
33
34 return;
35 }
36 /*

阅读更多...

网桥,路由器,交换机的功能区别
技术文档

网桥,路由器,交换机的功能区别

2008-10-23 2008-10-23 5107浏览 0评论 简洁版

首先在局域网里面,大量主机之间的通信都是通过arp广播来决定目的主机的地址的,为了减小在共享环境中的介质争用(也就是冲突),网桥产生了,它的作用是将广播域划分为一个一个小的冲突域,这样便增大了可用的带宽,但是广播域还是没有变。从这里可以看出,网桥不涉及逻辑地址,所以它工作在第二层(数据链路层),并且端口很少(注意与后面的交换机区别),最后是网桥常常是基于软件的,因此可以处理上层事务。

看到了网桥的作用,于是人们将其发展为多端口设备,并且整合了集线器的功能,发明了交换机,交换机也是工作在第二层,由于具有多个端口,所以也叫做多口桥。交换机除了具有桥接(也就是隔绝冲突)和转发数据报之外,还具有其他高级特性:比如说 vlan(虚拟局域网),port trunking(连路聚合),spanning tree(生成树),等等特性,高端的交换机还具有路由功能,具体的路由功能将在后面介绍。交换机是一种专用的网络设备,它是基于硬件的,所以具有比基于软件的网桥更高的数据转发能力。

阅读更多...

NS2简介
技术文档

NS2简介

2008-10-23 2008-10-23 12525浏览 1评论 简洁版

NS是一种针对网络技术的源代码公开的、免费的软件模拟平台,研究人员使用它可以很容易的进行网络技术的开发,而且发展到今天,它所包含的模块已经非常丰富,几乎涉及到了网络技术的所有方面。所以,NS成了目前学术界广泛使用的一种网络模拟软件。在每年国内外发表的有关网络技术的学术论文中,利用NS给出模拟结果的文章最多,通过这种方法得出的研究结果也是被学术界所普遍认可的,此外,NS也可作为一种辅助教学的工具,已被广泛应用在了网络技术的教学方面。因此,目前在学术界和教育界,有大量的人正在使用或试图使用NS。

然而,对初学者来说,NS是非常难于掌握的,一般人从学习NS到上手至少需要半年多时间。原因是多方面的:一方面,NS内容庞杂,随软件所提供的手册更新不够快,初学者阅读起来非常困难;另一方面,使用NS还要掌握其它很多必备的相关知识以及相关工具,这会使初学者感到无从入手;有的使用者可能还不了解网络模拟的过程或是对NS软件的机制缺乏理解,这也影响了对NS的掌握。另外,不论在国外还是国内,还没有一本书能集中回答和解决这些问题,这也是NS难于被掌握的一个重要原因。

阅读更多...

NS2完整的流程简介
技术文档

NS2完整的流程简介

2008-10-23 2008-10-23 7299浏览 0评论 简洁版

1、建立脚本文件(只给出两个关键点的代码)
配置模拟属性:
set val(chan)  Channel/WirelessChannel   ;# 信道类型
set val(prop) Propagation/TwoRayGround   ;# 传播模型
set val(netif)   Phy/WirelessPhy         ;# 物理层
set val(mac)     Mac/802_11              ;# MAC类型
set val(ifq)     Queue/DropTail/PriQueue ;#
set val(ll)      LL                      ;# 链路层
set val(ant)     Antenna/OmniAntenna     ;# 天线类型
set val(ifqlen)   50                     ;# ifq中最大包数
set val(nn)       30                     ;# 移动节点个数
set val(rp)       AODV                   ;# 路由协议
set opt(cp)      "CBR"                   ;# 数据流类型
set opt(sc)      "scen"                  ;# 场景文件

配置移动节点:
# 构造节点
$ns_ node-config -adhocRouting $val(rp) \
-llType $val(ll) \
-macType $val(mac) \
-ifqType $val(ifq) \
-ifqLen $val(ifqlen) \
-antType $val(ant) \
-propType $val(prop) \
-phyType $val(netif) \
-channelType $val(chan) \
-topoInstance $topo \
-agentTrace ON \
-routerTrace OFF \
-macTrace ON \
-movementTrace OFF

阅读更多...

搜索算法小结
技术文档

搜索算法小结

2008-10-23 最后修改:2009-08-19 07:25 4450浏览 0评论 简洁版

搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分和所有的可能情况,从而求出问题的解的一种方法。
常用的搜索算法有:
一.回溯法
回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作为其控制结构,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。

二.深度优先搜索和广度优先搜索
深度搜索与广度搜索的控制结构和产生系统很相似,唯一的

阅读更多...

遥远的炊烟
经典珍藏

遥远的炊烟

2008-10-22 2008-10-22 2580浏览 0评论 简洁版

文:鲁先圣
在城市生活得久了,常常想起乡村里的炊烟。炊烟下宁静的土屋,果实累累的枣树石榴树和悠闲的鸡鸭羊群。更常常想起炊烟里的母亲。
只要在乡村生活过,有谁不怀念村庄上空那袅袅升起的炊烟?袅袅的炊烟,在房屋的脊梁上盘旋,在树梢的鸟巢旁飘荡,在胡同的拐角里踱步,最后都凝聚成片片朦胧的烟霞。那温暖的烟霞里,有母亲的呼唤,有奶奶的目光,也有父亲洪钟般的声音。
对炊烟的记忆,是一个人心灵深处的情节,是一个人大浪淘沙之后的顿悟,是人生归于平静的从容。
有多久没有看到过炊烟了?城市里没有炊烟,城市里用的是煤气液化气,即使有了些许的炊烟,也是有害的气体,是不会让人留恋的。况且,城市里的人们,也没有时间留意炊烟,大家都匆匆忙忙,谁会有时间在意稍纵即逝的炊烟?炊烟只属于宁静的乡村,只属于浑厚的黄土地。
只有当停下了人生的脚步的时候,只有当心灵归于一份淡雅和安静的时候,那袅袅的炊烟才会从久远的记忆中升起来,瞬间就弥漫了你整个的心灵。

阅读更多...