Only the paranoid survive

[zz]windows service install

xiaoiiiyao — Sat, 27 Jun 2009 15:50:00 GMT

首先，我们要给windows service添加Installer。右键点击设计视图，选择Add Installer，VS将会为我们添加ProjectInstaller.cs，并在ProjectInstaller中添加组件serviceInstaller1和serviceProcessInstaller1，现在我们来修改他们的属性来控制Service的安装和启动选项。在ProjectInstaller得设计视图中选中serviceProcessInstaller1，将它得Account属性选为LocalSystem，这样以这个帐号服务启动。如果你希望系统启动时自动启动服务得话，将serviceInstaller1的StartType的属性选为Automatic，如果手动启动的话，选为manaul。
其次，要安装service，我们要用到IntallUtil.exe这个程序，这个程序位于C：\WINDOWS\Microsoft.NET\Framework\v2.0.50727.点击开始菜单，选择“运行”，在运行对话框中输入cmd，进入到命令行窗口，输入cd ：\WINDOWS\Microsoft.NET\Framework\v2.0.50727，进入到这个目录，然后输入installutil F:\project\考试系统\项目代码\Service\GradeService\GradeService\bin\Debug\GradeService.exe， installutil后边的内容就是我们的工程生成的可执行程序的路径，可以根据你自己的实际情况进行修改。

如果你给ServiceInstaller1的StartType设为Automatic的话，安装完服务，服务已经运行起来了，如果StartType是Manual的话，你需要手动启动。现在我们进入“服务”，要打开“服务”，请单击“开始”，指向“设置”，然后单击“控制面板”。依次单击“性能和维护”、“管理工具”，然后双击“服务”。在里边你应该能够看到我们制作的Service GradeService。在这里边，我们可以启动，关闭服务，还可以设置服务的启动类型。然后，我们看看服务有没有正确的写入日志，我们需要进入到事件查看器，要打开“事件查看器”，请单击“开始”，指向“设置”，然后单击“控制面板”。单击“性能和维护”，单击“管理工具”，然后双击“事件查看器”。如下图所示，我们的消息已经成功的写到了系统日志里了，下图。

文章出处：http://www.diybl.com/course/4_webprogram/asp.net/asp_netshl/2008414/110334_5.html

[zz]windows service 之调试过程

xiaoiiiyao — Sat, 27 Jun 2009 15:50:00 GMT

http://www.cnblogs.com/slh-blogs/archive/2009/05/14/1456517.html

最近第一次用C#写了一个windows service ,其实实现的内容比较简单。就是启动remoting 连接，但是调试相对初次写windws service 的我来说，比较烦。没有经验，而且没办法像调试其他windows 程序一样设置断点，无法看到运行过程。经过查看一些相关资料后，有了一点点调试的心得。特此留笔，以待今后使用。

相关源码：

static void Main()
        {
            ServiceBase[] ServicesToRun;

            // 同一进程中可以运行多个用户服务。若要将
            // 另一个服务添加到此进程中，请更改下行以
            // 创建另一个服务对象。例如，
            //
            //   ServicesToRun = new ServiceBase[] {new Service1(), new MySecondUserService()};
            //
            ServicesToRun = new ServiceBase[] { new TeamWorldService() };

            ServiceBase.Run(ServicesToRun);
            //TeamWorldService obj = new TeamWorldService();
            //obj.OnStart();
        }

TeamWorldService :

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Diagnostics;
using System.ServiceProcess;
using System.Text;
using System.IO;
using Tribal.TeamWorld.API;
using Tribal.BaseClasses;
using Tribal.TeamWorld.Remoting;
using Tribal.TeamWorld.Implementation;

namespace Tribal.TeamWorld.Service
{
    partial class TeamWorldService : ServiceBase
    {
        private RemotingInterface _remotingInterface = null;
        private MainController _mainController = null;
        public TeamWorldService()
        {
            InitializeComponent();//

        }

        protected override  void OnStart(string[] args)
        {
            this.AddTextLine("Starting server  ( " + DateTime.Now.ToString() + " )");

            try
            {
                this.AddTextLine("Initializing MainController ");
                this._mainController = MainController.GetInstance();
            }
            catch (Exception ex)
            {
                this.PrintExceptions(ex);
            }

            if (this._mainController != null)
            {
                this.AddTextLine("Connecting userinterface to LogController ");
            }

            try
            {
                this.AddTextLine("Starting MainController");
                this._mainController.Start();
            }
            catch (Exception exc)
            {
                this.PrintExceptions(exc);
            }

            try
            {
                this.AddTextLine("Starting .NET RemotingInterface");
                this._remotingInterface = new RemotingInterface();
                this._remotingInterface.StartServing();
            }
            catch (Exception exc)
            {
                this.PrintExceptions(exc);
            }
        }

        protected override void OnStop()
        {

            this._remotingInterface.StopServing();
            this._mainController.Stop();
            this.AddTextLine("End .NET RemotingInterface");

        }

        private void PrintExceptions(Exception exc)
        {
            Exception current = exc;
            while (current != null)
            {
                this.AddTextLine(current.Message);
                this.AddTextLine(current.StackTrace);

                current = current.InnerException;
            }
        }

        private void AddTextLine(string line)
        {
            try
            {
                FileStream fs = new FileStream(@"C:\TeamWorldServiceLog.txt", FileMode.OpenOrCreate, FileAccess.Write);

                StreamWriter m_streamWriter = new StreamWriter(fs);

                m_streamWriter.BaseStream.Seek(0, SeekOrigin.End);

                m_streamWriter.WriteLine(line+ "\r\n");

                m_streamWriter.Flush();

                m_streamWriter.Close();

                fs.Close();
            }
            catch (Exception ex)
            {

            }
        }
    }
}

方法1：写日志
        是最传统的调试windows service方法，也是大家在调试service 比较管用的方式，但是，调试起来还是不太明朗。你要在你认为可能出现错误的地方全部添加写日志的方法。我上面的代码就采用了AddTextLine 函数实现的这种方法。

方法2：附加进程
        附加进程的方法可以像调试正常的widows程序一样，设置断点进行单步调试。但是，我必须在安装启动服务后，才可以进行附加此服务进程，可在附加的同时OnStart 函数已经执行完毕，所以对Onstart 无法调试。但是我可以通过设置启动服务延时来加载调试。
        步骤如下：
                     1，设置启动服务延时，

private System.Timers.Timer timerDelay;

        protected override void OnStart(string[] args)
        {
            try
            {

                ///delay start the SynData 30seconds
                timerDelay = new System.Timers.Timer(30000);
                timerDelay.Elapsed += new System.Timers.ElapsedEventHandler(timerDelay_Elapsed);
                timerDelay.Start();
            }
            catch (Exception ex)
            {
                this.PrintExceptions(ex);
            }
        }

        void timerDelay_Elapsed(object sender, System.Timers.ElapsedEventArgs e)
        {
            timerDelay.Enabled = false;
            timerDelay.Close();
            //你要加的代码
            //.To do..
        }

                      注意：正常服务的启动时间为30秒左右，当服务启动时间超过30秒会报错！，所以不要在OnStart中做过多的操作，也可以用这种延时的方法启动服务，以防在启动服务时超时。
                     2、首先要对服务进行安装，然后启动服务。
                     3、打开vs2005 调试—>附加到进程，选择你的服务进程（如果找不到可以勾选显示所有用户的进程），就可以了。

方法3：
      我认为是这次调试对我帮助最大。
      在Main 函数中,注释掉原有自动生成的代码，注意红字部分是要根据自己的服务名字来手工添加的
             // ServiceBase[] ServicesToRun;

            // 同一进程中可以运行多个用户服务。若要将
            // 另一个服务添加到此进程中，请更改下行以
            // 创建另一个服务对象。例如，
            //
            //   ServicesToRun = new ServiceBase[] {new Service1(), new MySecondUserService()};
            //
            //ServicesToRun = new ServiceBase[] { new TeamWorldService() };

            //ServiceBase.Run(ServicesToRun);
            //******************************************
            TeamWorldService obj = new TeamWorldService();
            obj.OnStart();
            //******************************************
      然后把 protected override  void OnStart(string[] args) 改为 public void OnStart()。
      ，设置你的断点，按 F5 运行就可以调试了。

以上是自己这次调试widows service 后，得到的一些方法。以待今后继续积累。

[zz]提示文字根据焦点自动消失的输入框javascript

xiaoiiiyao — Fri, 26 Jun 2009 13:38:00 GMT

http://www.cnblogs.com/zfanswer/archive/2009/04/23/1441938.html

输入框html代码

<input id="searchKey" type="text" name="q" value="" tips="请输入关键字"/><br />

js脚本语言,完成功能:
a.页面加载完毕输入框中显示提示文字,可在上边的输入框属性tips中自定义
b.鼠标点击输入框,输入框获得焦点时,提示文字自动消失
c.鼠标焦点离开输入框,提示文字根据情况显示
        网上好多实例代码是鼠标一离开就显示提示文字,输入框中用户的输入也会消失-----不合理
        有的保存了用户输入,离开时还是会显示提示文字,再获得焦点是显示用户的输入,也不太符合习惯
   经本人修改:
        判断输入框中如果有用户输入,则焦点离开时输入不会被提示文字取代,并且再次获得焦点时,光标自动位于文字的最后方,这也是经常使用的一个小技巧,提高用户体验.
d.这样就可以和一个button完美组合成一个输入框了,检索服务等等...

<script language="javascript" type="text/javascript">
//输入框内水印
window.onload = function(){
    var o=document.getElementById("searchKey");
    o.setAttribute("valueCache",o.value);
    o.onblur = function(){
        if(o.value=="")
        {
            o.valueCache="";
            o.value=o.tips;
        }
        else
            o.valueCache=o.value;
    }
    o.onfocus = function(){
        o.value=o.valueCache; 
        //光标始终在文字最后
      var e = event.srcElement;
        var r =e.createTextRange();
        r.moveStart('character',e.value.length);
        r.collapse(true);
        r.select();
    }
    o.onblur();
}

<script>

[zz]未能加载文件或程序集“Microsoft.Office.Interop.Excel"

xiaoiiiyao — Wed, 24 Jun 2009 19:21:00 GMT

未能加载文件或程序集“Microsoft.Office.Interop.Excel, Version=11.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c”或它的某一个依赖项。系统找不到指定的文件。

部署时遇到了这个问题。

目前已经解决。

服务器上没有安装Office

提出以后，管理员安装了Office2003（注意安装以后要重启电脑）

按照网上找到的一些方法，

安装：
vstor.exe

下载地址：
http://www.microsoft.com/downloads/details.aspx?FamilyId=8315654B-A5AE-4108-B7FC-186402563F2B&displaylang=zh-cn#filelist

然后下载安装：
O2003PIA.EXE
http://www.microsoft.com/downloads/details.aspx?FamilyId=3C9A983A-AC14-4125-8BA0-D36D67E0F4AD&displaylang=en

之后还是没有解决

然后

在服务器上开始-程序-管理工具-Microsoft .NET Framework 2.0 配置-管理程序集缓存-将程序集添加到程序集缓存。选中那些dll即可。

然而不幸的是还是没有解决。

最后重启IIS 问题解决了。

具体怎么解决的就是以上两个方法之一或两者都必须做到。

我认为一个很重要的问题是

在C:\WINDOWS\assembly目录下面必须要有项目的引用。

未能加载文件或程序集“Microsoft.Office.Interop.Excel, Version=11.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c”或它的某一个依赖项。系统找不到指定的文件。

其中的原理是

计算机上缺少了项目引用的Office类文件Interop.Excel.dll

vstor.exe和O2003PIA.EXE是office可重用开发XXX的安装程序。

写的不太清楚，反正就是这样子了

[zz]定义局部变量时，字符串不能超过8000的方法

xiaoiiiyao — Wed, 24 Jun 2009 14:04:00 GMT

http://www.cnblogs.com/xnxylf/archive/2008/11/14/1333211.html

经常有人提到,用动态生成SQL语句的方法处理数据时,处理语句超长,无法处理的问题

/*-- 数据测试环境 --*/
if exists (select * from dbo.sysobjects where id = object_id(N'[tb]') and OBJECTPROPERTY(id, N'IsUserTable') = 1)
drop table [tb]
GO

create table tb(单位名称 varchar(10),日期 datetime,销售额 int)
insert into tb
select 'A单位','2001-01-01',100
union all select 'B单位','2001-01-02',101
union all select 'C单位','2001-01-03',102
union all select 'D单位','2001-01-04',103
union all select 'E单位','2001-01-05',104
union all select 'F单位','2001-01-06',105
union all select 'G单位','2001-01-07',106
union all select 'H单位','2001-01-08',107
union all select 'I单位','2001-01-09',108
union all select 'J单位','2001-01-11',109

/*-- 要求结果
日期       A单位 B单位 C单位 D单位 E单位 F单位 G单位 H单位 I单位 J单位
---------- ----- ----- ----- ----- ----- ----- ---- ---- ---- ------
2001-01-01 100   0     0     0     0     0     0     0     0     0
2001-01-02 0     101   0     0     0     0     0     0     0     0
2001-01-03 0     0     102   0     0     0     0     0     0     0
2001-01-04 0     0     0     103   0     0     0     0     0     0
2001-01-05 0     0     0     0     104   0     0     0     0     0
2001-01-06 0     0     0     0     0     105   0     0     0     0
2001-01-07 0     0     0     0     0     0     106   0     0     0
2001-01-08 0     0     0     0     0     0     0     107   0     0
2001-01-09 0     0     0     0     0     0     0     0     108   0
2001-01-11 0     0     0     0     0     0     0     0     0     109
--*/

/*-- 常规处理方法*/

declare @sql varchar(8000)
set @sql='select 日期=convert(varchar(10),日期,120)'
select @sql=@sql+',['+单位名称
+']=sum(case 单位名称 when '''+单位名称+''' then 销售额 else 0 end)'
from(select distinct 单位名称 from tb) a
exec(@sql+' from tb group by convert(varchar(10),日期,120)')

/*-- 问题: 如果单位很多,这时,@SQL的值就会被截断,从而出错.*/

/*--下面给出种解决办法:--*/

--/*-- 方法1. 多个变量处理

--定义变量,估计需要多少个变量才能保存完所有数据
declare @sql0 varchar(8000),@sql1 varchar(8000)
--,@sqln varchar(8000)

--生成数据处理临时表
select id=identity(int,0,1),groupid=0
,值=',['+单位名称 +']=sum(case 单位名称 when '''
+单位名称+''' then 销售额 else 0 end)'
into #temp from(select distinct 单位名称 from tb) a

--分组临时表,判断慨最多多少个单位可以组合成一个不超过8000的字符串,这里取假设为5个
update #temp set groupid=id/5  --5为每组的单位个数

--生成SQL语句处理字符串
  --初始化
select @sql0=''
,@sql1=''
--
-- ,@sqln

  --得到处理字符串
select @sql0=@sql0+值 from #temp where groupid=0  --第一个变量
select @sql1=@sql1+值 from #temp where groupid=1  --第二个变量
--select @sqln=@sqln+值 from #temp where groupid=n  --第n个变量

--查询
exec('select 日期=convert(varchar(10),日期,120)'
+@sql0+@sql1
-- +@sqln
+' from tb group by convert(varchar(10),日期,120)
')

--删除临时表
drop table #temp

/*
优点:比较灵活,数据量大时只需要增加变量就行了.不用改动其他部分
缺点:要自行估计处理的数据,估计不足就会出错
*/
--*/

--/*-- 方法2. 多个变量处理,综合了方法1, 解决了方法1中需要人为判断的问题,自动根据要处理的数据量进行变量定义

declare @sqlhead varchar(8000),@sqlend varchar(8000)
,@sql1 varchar(8000),@sql2 varchar(8000),@sql3 varchar(8000),@sql4 varchar(8000)
,@i int,@ic varchar(20)

--生成数据处理临时表
select id=identity(int,0,1),gid=0
,a=',['+单位名称 +']=sum(case 单位名称 when '''
+单位名称+''' then 销售额 else 0 end)'
into # from(select distinct 单位名称 from tb) a

--判断需要多少个变量来处理
select @i=max(len(a)) from #
print @i
set @i=7800/@i

--分组临时表
update # set gid=id/@i
select @i=max(gid) from #

--生成数据处理语句
select @sqlhead='''select 日期=convert(varchar(10),日期,120)'''
,@sqlend=''' from tb group by convert(varchar(10),日期,120)'''
,@sql1='',@sql2='select ',@sql3='',@sql4=''

while @i>=0
select @ic=cast(@i as varchar),@i=@i-1
  ,@sql1='@'+@ic+' varchar(8000),'+@sql1
  ,@sql2=@sql2+'@'+@ic+'='''','
  ,@sql3='select @'+@ic+'=@'+@ic+'+a from # where gid='+@ic
   +char(13)+@sql3
  ,@sql4=@sql4+',@'+@ic

select @sql1='declare '+left(@sql1,len(@sql1)-1)+char(13)
,@sql2=left(@sql2,len(@sql2)-1)+char(13)
,@sql3=left(@sql3,len(@sql3)-1)
,@sql4=substring(@sql4,2,8000)

--执行
exec( @sql1+@sql2+@sql3+'
exec('+@sqlhead+'+'+@sql4+'+'+@sqlend+')'
)

--删除临时表
drop table #
--*/

方法2中,关键要做修改的是下面两句,其他基本上不用做改变:

--生成数据处理临时表,修改a=后面的内容为相应的处理语句
select id=identity(int,0,1),gid=0
,a=',['+code+']=sum(case b.c_code when '''
+code+''' then b.value else 0 end)'
into # from #Class

--生成数据处理语句,将@sqlhead,@sqlend赋值为相应的处理语句头和尾
select @sqlhead='''select a.id,a.name,a.code'''
,@sqlend=''' from #Depart a,#Value b where a.Code=b.d_Code group by a.id,a.code,a.name'''
,@sql1='',@sql2='select ',@sql3='',@sql4=''

[zz]检索 COM 类工厂中 CLSID 为 {00024500-0000-0000-C000-000000000046} 的组件时失败，原因是出现以下错误: 80070005。

xiaoiiiyao — Tue, 23 Jun 2009 15:51:00 GMT

http://topic.csdn.net/u/20070628/16/17b8b13e-8728-4403-bf14-9e814fd9142f.html

配置DCOM

具体配置方法如下:

1:在服务器上安装office的Excel软件.

2:在"开始"->"运行"中输入dcomcnfg.exe启动"组件服务"

3:依次双击"组件服务"->"计算机"->"我的电脑"->"DCOM配置"

4:在"DCOM配置"中找到"Microsoft Excel 应用程序",在它上面点击右键,然后点击"属性",弹出"Microsoft Excel 应用程序属性"对话框

5:点击"标识"标签,选择"交互式用户"

6:点击"安全"标签,在"启动和激活权限"上点击"自定义",然后点击对应的"编辑"按钮,在弹出的"安全性"对话框中填加一个"NETWORK SERVICE"用户(注意要选择本计算机名),并给它赋予"本地启动"和"本地激活"权限.

7:依然是"安全"标签,在"访问权限"上点击"自定义",然后点击"编辑",在弹出的"安全性"对话框中也填加一个"NETWORK SERVICE"用户,然后赋予"本地访问"权限.

注：在XP系统中还要添"加机器名/ASPNET"用户的上述权限。
在window 2003 server中，如果还出现8000401a错误，在标示里面选择“下列用户”，填写登录计算机的并拥有对Excel本地操作权限的用户。或者在标示里面选择“启用用户”

[Data Structure]二叉搜索树的节点删除（Binary Search Trees）(zz)

xiaoiiiyao — Mon, 22 Dec 2008 18:31:00 GMT

转自：http://hi.baidu.com/sangwf/blog/item/e9b4211f26c2e3c8a6866967.html

上次在《线性搜索的优化》中提到一个程序中的二叉树节点删除出现了BUG，一直没有去解决，虽然没有什么大碍，但心里中觉得有点不爽，还是要解决掉。于是翻了一下数据结构课本，把关于二叉搜索树的东西又看了一遍，自己也写了个删除节点的函数，测试了几下没有出现问题，估计没BUG了吧。今天就想总结一下。

首先，我们要明确二叉搜索树的概念。其定义是：它是一个二叉树，可能为空。如果不为空，则满足以下属性：

     1）每个元素都有一个键值，并且没有重复。
     2）左子树中的元素键值都小于根节点的键值。
     3）右子树中的元素键值都大于根节点的键值。
     4）左右子树也满足二叉搜索树的定义。

通过这个定义我们就明白了什么是二叉搜索树。对它的搜索和插入都比较容易，搜索就是二分搜索法，插入就是首先搜索树，将搜索中止的节点作为父节点，把待插入的节点作为它的儿子，也比较容易理解。最麻烦的就是删除节点，因为情况比较多，需要所有情况都考虑清楚。

在我看来，写一个小程序和写一个大软件没多大区别，都要按照软件工程的步骤来做。可行性分析和需求分析就不说了，首先要对这个删除功能进行设计，那就要把所有情况都列举出来。我是不赞同一边写代码一边考虑情况的，那样容易遗漏情况。那我们就来分析一下所存在的情况。

    待删除的节点按照儿子的个数可以分为三种：
    1）没有儿子，即为叶节点。直接把父节点的对应儿子指针设为NULL，删除儿子节点就OK了。
    2）只有一个儿子。那么把父节点的相应儿子指针指向儿子的独生子，删除儿子节点也OK了。
    3）有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删节点的位置。左儿子的最大元素其实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的节点。那就是最大的了（很好证明）。
    初略的一看，你可能觉得要递归了，删除了左子树的最大元素不是还要调整吗？其实你可以看到，这个元素是没有右子树的（左子树有没有无所谓），我们只要将最大元素的父节点指向最大元素的左儿子就可以了。最后，清理掉待删除的儿子节点。

还有其他情况么？没有了。但要注意一点问题，那就是待删除的节点可能没有父亲，也就是可能本身就是根节点。那就要改变根节点指针了。这样在编程时，是首先按照有无父节点分成两种情况呢？还是按照儿子个数分为三种情况然后在处理没有父亲的特殊情况呢？我个人选择第二种，代码量会小一点（两个儿子的情况处理代码较多）。代码如下：

    void delete_node(tree_node_ptr * pptr,int value) {
         tree_node_ptr tree = *pptr;
         tree_node_ptr parent = NULL, child = NULL;
         while (tree) {
              if (value == tree->value) {
               child = tree;
               break;
              }
              if (value < tree->value) {
                   parent = tree;
                   tree = tree->left;
              } else {
                   parent = tree;
                   tree = tree->right;
              }
         }
     if (!child) { //未找到
          return ;
     }

//叶节点
if (child->left==NULL&&child->right == NULL) {
  if (parent == NULL) { //根节点
   *pptr = NULL;
  } else if (parent->left == child) {
   parent->left = NULL;
  } else {
   parent->right = NULL;
  }

} else

//只有一个孩子
if (!(child->left&&child->right)) {
  if (child->left) {
   if (parent == NULL) {
    *pptr = child->left;
   } else {
    parent = child->left;
   }

  } else {
   if (parent == NULL) {
    *pptr = child->right;
   } else {
    parent = child->right;
   }
  }
} else

//有两个孩子
{
  //寻找左子树的最大元素
  tree_node_ptr pMax = child->left;
  tree_node_ptr pMaxParent = NULL;
  while (pMax->right) {
   pMaxParent = pMax;
   pMax = pMax->right;
  }

  if (pMax == child->left) {
   pMax->right = child->right;

  } else {
   pMaxParent->right = pMax->left;
   pMax->left = child->left;
   pMax->right = child->right;
  }
  if (parent == NULL) {
   *pptr = pMax;
  } else if(parent->left == child) {
   parent->left = pMax;
  } else {
   parent->right = pMax;
  }

}

delete child;
}

也谈内存对齐（zz）

xiaoiiiyao — Wed, 12 Nov 2008 10:00:00 GMT

也谈内存对齐 - [技术前沿]

Tag：语言探索

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
 http://bigwhite.blogbus.com/logs/1347304.html

在最近的项目中，我们涉及到了“内存对齐”技术。对于大部分程序员来说，“内存对齐”对他们来说都应该是“透明的”。“内存对齐”应该是编译器的“管辖范围”。编译器为程序中的每个“数据单元”安排在适当的位置上。但是C语言的一个特点就是太灵活，太强大，它允许你干预“内存对齐”。如果你想了解更加底层的秘密，“内存对齐”对你就不应该再透明了。

一、内存对齐的原因
大部分的参考资料都是如是说的：
1、平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
2、性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。

二、对齐规则
每个特定平台上的编译器都有自己的默认“对齐系数”(也叫对齐模数)。程序员可以通过预编译命令#pragma pack(n)，n=1,2,4,8,16来改变这一系数，其中的n就是你要指定的“对齐系数”。

规则：
1、数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中，比较小的那个进行。
2、结构(或联合)的整体对齐规则：在数据成员完成各自对齐之后，结构(或联合)本身也要进行对齐，对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行。
3、结合1、2颗推断：当#pragma pack的n值等于或超过所有数据成员长度的时候，这个n值的大小将不产生任何效果。

三、试验
我们通过一系列例子的详细说明来证明这个规则吧!
我试验用的编译器包括GCC 3.4.2和VC6.0的C编译器，平台为Windows XP + Sp2。

我们将用典型的struct对齐来说明。首先我们定义一个struct：
#pragma pack(n) /* n = 1, 2, 4, 8, 16 */
struct test_t {
int a;
char b;
short c;
char d;
};
#pragma pack(n)
首先我们首先确认在试验平台上的各个类型的size，经验证两个编译器的输出均为：
sizeof(char) = 1
sizeof(short) = 2
sizeof(int) = 4

我们的试验过程如下：通过#pragma pack(n)改变“对齐系数”，然后察看sizeof(struct test_t)的值。

1、1字节对齐(#pragma pack(1))
输出结果：sizeof(struct test_t) = 8 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(1)
struct test_t {
int a;  /* 长度4 < 1 按1对齐；起始offset=0 0%1=0；存放位置区间[0,3] */
char b;  /* 长度1 = 1 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 > 1 按1对齐；起始offset=5 5%1=0；存放位置区间[5,6] */
char d;  /* 长度1 = 1 按1对齐；起始offset=7 7%1=0；存放位置区间[7] */
};
#pragma pack()
成员总大小=8

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 1) = 1
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 8 /* 8%1=0 */ [注1]

2、2字节对齐(#pragma pack(2))
输出结果：sizeof(struct test_t) = 10 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(2)
struct test_t {
int a;  /* 长度4 > 2 按2对齐；起始offset=0 0%2=0；存放位置区间[0,3] */
char b;  /* 长度1 < 2 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 = 2 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;  /* 长度1 < 2 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 2) = 2
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 10 /* 10%2=0 */

3、4字节对齐(#pragma pack(4))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(4)
struct test_t {
int a;  /* 长度4 = 4 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;  /* 长度1 < 4 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 4 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;  /* 长度1 < 4 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 4) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

4、8字节对齐(#pragma pack(8))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(8)
struct test_t {
int a;  /* 长度4 < 8 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;  /* 长度1 < 8 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 8 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;  /* 长度1 < 8 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 8) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

5、16字节对齐(#pragma pack(16))
输出结果：sizeof(struct test_t) = 12 [两个编译器输出一致]
分析过程：
1) 成员数据对齐
#pragma pack(16)
struct test_t {
int a;  /* 长度4 < 16 按4对齐；起始offset=0 0%4=0；存放位置区间[0,3] */
char b;  /* 长度1 < 16 按1对齐；起始offset=4 4%1=0；存放位置区间[4] */
short c; /* 长度2 < 16 按2对齐；起始offset=6 6%2=0；存放位置区间[6,7] */
char d;  /* 长度1 < 16 按1对齐；起始offset=8 8%1=0；存放位置区间[8] */
};
#pragma pack()
成员总大小=9

2) 整体对齐
整体对齐系数 = min((max(int,short,char), 16) = 4
整体大小(size)=$(成员总大小) 按 $(整体对齐系数) 圆整 = 12 /* 12%4=0 */

四、结论
8字节和16字节对齐试验证明了“规则”的第3点：“当#pragma pack的n值等于或超过所有数据成员长度的时候，这个n值的大小将不产生任何效果”。另外内存对齐是个很复杂的东西，上面所说的在有些时候也可能不正确。呵呵^_^

[注1]
什么是“圆整”？
举例说明：如上面的8字节对齐中的“整体对齐”，整体大小=9 按 4 圆整 = 12
圆整的过程：从9开始每次加一，看是否能被4整除，这里9，10，11均不能被4整除，到12时可以，则圆整结束。

[Algorithm]堆排序(zz)

xiaoiiiyao — Mon, 10 Nov 2008 14:22:00 GMT

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、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

1 /*
2 堆排序
3 (1)用大根堆排序的基本思想
4 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
5 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，
6 由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
7 ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
8 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
9 由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys，
10 同样要将R[1..n-2]调整为堆。
11 ……
12 直到无序区只有一个元素为止。
13 (2)大根堆排序算法的基本操作：
14 ① 初始化操作：将R[1..n]构造为初始堆；
15 ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
16 注意：
17 ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
18 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。
19 堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，
20 且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
21 */
22
23 //生成大根堆
24 void HeapAdjust(int SortData[],int StartIndex, int Length)
25 {
26     while(2*StartIndex+1 < Length)
27     {
28         int MinChildrenIndex = 2*StartIndex+1 ;
29         if(2*StartIndex+2 < Length )
30         {
31             //比较左子树和右子树，记录最大值的Index
32             if(SortData[2*StartIndex+1]<SortData[2*StartIndex+2])
33             {
34                 MinChildrenIndex = 2*StartIndex+2;
35             }
36         }
37         if(SortData[StartIndex] < SortData[MinChildrenIndex])
38         {
39             //交换i与MinChildrenIndex的数据
40             int tmpData =SortData[StartIndex];
41             SortData[StartIndex] =SortData[MinChildrenIndex];
42             SortData[MinChildrenIndex] =tmpData;
43             //堆被破坏，需要重新调整
44             StartIndex = MinChildrenIndex ;
45         }
46         else
47         {
48             //比较左右孩子均大则堆未破坏，不再需要调整
49             break;
50         }
51     }
52
53     return;
54 }
55
56 //堆排序
57 void HeapSortData(int SortData[], int Length)
58 {
59     int i=0;
60
61     //将Hr[0,Lenght-1]建成大根堆
62     for (i=Length/2-1; i>=0; i--)
63     {
64         HeapAdjust(SortData, i, Length);
65     }
66
67     for (i=Length-1; i>0; i--)
68     {
69         //与最后一个记录交换
70         int tmpData =SortData[0];
71         SortData[0] =SortData[i];
72         SortData[i] =tmpData;
73         //将H.r[0..i]重新调整为大根堆
74         HeapAdjust(SortData, 0, i);
75     }
76
77     return;
78 }

[Algorithm]分数变小数

xiaoiiiyao — Sun, 09 Nov 2008 22:55:00 GMT

1.分数变小数
    写出一个程序，接受一个以N/D的形式输入的分数，其中N为分子，D为分母，输出它的小数形式。如果它的小数形式存在循环节，要将其用括号括起来。例如：1/3=.00000...表示为.(3)，又如41/333=.123123123...表示为.(123)。
一些转化的例子：
1/3=.(3)
22/5=4.4
1/7=.(142857)
3/8=.375
45/46=.803(571428)
    用上面的分数和11/59来测试你的程序。
运行举例：
ENTER N，D：17
1/7=.(142857)
本题中，0<=N<=65535，0<=D<=65535，设运算结果小数点后最多保留100位。
(1)解题思路
    本题可以模仿手算除法的形式，重复地进行求商和余数的运算，直到余数为0或出现循环节为止。
(2)参考程序
Const Max=100;                      (小数点后最大位数)
Var Left,Digit:Array[0..Max]of Word; (记录每次的余数和商)
    n,d:Word;
    q,Top:Word;                       (q为循环字节的位置)
Procedure Init;
Begin
    Write('ENTER N,D:');
    Readln(n,d);
End;
Procedure Cacl;               (计算)
Var i:Word;
Begin
    Digit[0]:=n Div d;
    Left[0]:=n Mod d;
    Top:=0;
    q:=0;                      (初始化商和余数)
    While Left[Top]<> 0 Do      (余数不为0则循环)
        Begin
            Inc(Top);
            Digit[Top]:=(Left[Top-1]*10)Div d;
            Left[Top]:=(Left[Top-1]*10)Mod d;
            For i:=0 To Top-1 Do
            If Left[Top]=Left[i] Then
                Begin
                    q:=i+1;
                    Exit;             (如果出现循环节则退出)
                End;
        End;
End;

Procedure Print;
Var i:Word;
Begin
    Write(n,'\',d,'=');
    If(Digit[0]<>0 Then Write(Digit[0]);
    If Top>0 Then Write('.');
    For(i:=1 To Top Do
        Begin
            If i=q Then Write('(');
            Write(Digit[i]);
        End;
    If q>0 Then Write(')');
    Writein;
End;
Begin
    Init;                {读入数据}
    Cacl;                {计算}
    Print;;              {打印结果}
End.
(3)运行结果
ENTER N，D：11 59
11/59=.(1864406779661016949152542372881355932203389830508474576271)

附：改写后的C源程序如下：
#include<stdio.h>
#define Max 100           /*小数点后最大位数*/
int Left[Max];
int Digit[Max];              /*记录每次的余数和商*/
int n,d,q,Top;               /*q为循环字节的位置*/

void Init(void)
{
　 printf("ENTER N,D:");
　 scanf("%d %d",&n,&d);
}

void Cacl(void)       /*计算*/
{
　 int i=0,j=1;
　 Digit[0]=n/d;           /*求商*/
　 Left[0]=n%d;            /*求余数*/
　 Top=0;
　 q=0;              /*初始化商和余数*/
　 while(Left[Top]!=0&&j==1&&Top<100)
　 {
　　  Top++;　　　　　　　　　　　/*取下一个数组元素*/
　　  Digit[Top]=(Left[Top-1]*10)/d;　　　/*求商*/
　　  Left[Top]=(int)(Left[Top-1]*10)%d;　/*求余数*/

  　　for(i=0;i<Top-1;i++)
  　　{
  　　　 if(Left[Top]==Left[i])　　　　/*如果出现循环节则退出*/
  　　　 {
  　　　　  q=i+1;
  　　　　  j=0;
  　　　　  break;
  　　　 }

　　}
　 }
}

void Print(void)　　　　　　　　　　　/*输出计算结果*/
{
　 int i;
　 printf("n/d= ");
　 if(Digit[0]!=0) printf("%d",Digit[0]);
　 if(Top>0) printf(".");
　 for(i=1;i<=Top;i++)
　 {
　　 if(i==q) printf("(");
　　printf("%d",Digit[i]);
　 }
　 if(q>0) printf(")");
}

void main(void)
{
　 Init();　　　　　　/*读入数据*/
　 Cacl(); /*计算*/
　 Print(); /*打印结果*/
}

[Algorithm]由遍历结果求二叉树

xiaoiiiyao — Sun, 09 Nov 2008 11:29:00 GMT

已知前序是ABCDEFG 中序是CBEDAFG 求二叉树

首先从取前序第1个字母(A) 按此字母把中序分成两段 (CBED) (AFG)
A做根 (CBED)做左子树 (FG)右子树
再按长度把前序后面的部分分成(BCDE) (FG)

问题就转换成
已知前序是BCDE 中序是CBED 求二叉树
和
已经前序是FG 中序是FG 求二叉树

看出来了没有,递归求解的.
下面的步骤省略分析.
前序中序 : 根左子树分解右子树分解
BCDE CBED : B (C) (C) (ED) (DE)
C C : C
DE　 ED : D (E) (E)
E E : E

FG FG : F (G) (G)
G G : G
得出的二叉树就是
A
/ \
B F
/ \ \
C D G
/
E

同理可算，一直后序遍历和中序遍历求二叉树。

/*
*已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中；试编写算法建立该二叉树的二叉链表
*
*下面给出用C语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组preod[ ]与inod[ ]中，并假设二叉树各结点的数据值均不相同。
*/

/*n为二叉树的结点个数，root为二叉树根结点的存储地址*/
void ReBiTree(char preod[],char inod[],int n,BiTree root)
{
    if (n≤0)   root=NULL;
    else PreInOd(preod,inod,1,n,1,n,&root);
}

void PreInOd(char preod[],char inod[],int i,int j, int k, int h,BiTree *t）
{
    BiTree* t=(BiTNode*)malloc(sizeof(BiTNode));
    *t->data=preod[i];
    int m=k;
    while(inod[m]!=preod[i]) m++;

    if (m==k) *t->lchild=NULL;
    else PreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild);

    if (m==h) *t->rchild=NULL;
    else PreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild);
}

[Algorithm]一道算法笔试题（zz）

xiaoiiiyao — Fri, 07 Nov 2008 15:18:00 GMT

淘宝网校园招聘笔试题

【题目】

n 是一个整数，对它进行如下循环操作：若 n 是奇数，将 n 增加一或减少一；若 n 是偶数，将它减小一半。求最短的步骤把 n 变成 1。 （题目来源：淘宝网 2008 校园招聘笔试题; TopLanguage论坛有讨论）

【解答一】

我们的讨论将针对 n 的二进制表示。总的操作次数就是除法次数和加（减）法次数的和，而除法次数是固定的，除了一种情况，那就是通过加法增加了一个位长，但这种情况最多出现一次，因为一旦“溢出”，低位部分全部变成了“0”，接下来就不会涉及加（减）法了。现在来看：

（1） 如果低位是“01”，那么减一能消掉一个“1”，但加一则不行，而且加一对高位也不会起“辅助”作用，比如 “11101”，虽然加一能变成 “11110”，接下来通过加一能消掉一大片“1”，但是这同样可以通过先减一变为 “11100”，然后加一消掉一大片“1” 来实现，不会比前种方法差；

（2） 如果低位是“011”，那么加/减一都消掉一个“1”，但是减一不会对高位起“辅助”作用，而加一有可能对高位起“辅助”作用从而达到更优的解。比如 “11011”，加一变为 “11100”，再加一可变为 “100000”，两次加法就够了；要是先减一的话，变为 “11010”，同样是剩三个“1”，但要多次加减操作才能消掉它们。当然，这里 “011” 指的是前面还有“1”，所以加一后并不“溢出”，故没有增加除法次数。但你或许会说，到时候“1”都被推到高位后，有可能要溢出。然而仔细想想，到时候若真需要对它进行溢出，那么肯定是剩有连续三个以上（含三个）“1”，而这样“溢出”虽增加了一次除法，但减法却减少了一次以上，更加有利；否则，比如特例 3，即“11”，自然是先减一再折半更优。所以溢不溢出到时还是由你说了算，溢出有利就溢出，否则就不溢出，现在先不管三七二十一，将“1”推向高位，让更多的“1”挤在一起再说。

（3） 如果低位有多于两个的连续“1”，显然加一比减一能消去更多的“1”，并且可能对高位产生“辅助”作用，优上加优。

//=====================================================================//

经过以上讨论，可以概括出如下算法：

REPEAT_UNTIL n = 1

IF n <= 3 THEN 直接处理

ELSE

IF n mod 4 = 1 即低位为“01” THEN n := n - 1

ELSE_IF n mod 4 = 3 即低位多于一个连续的“1” THEN n := n + 1

ELSE n := n / 2 END_IF

END_IF

END_REPEAT

//=====================================================================//

【解答二】

事实上，我们可以用更“数学”的方法得到以上结果。

设 f(n) 表示 n 变为 1 所需的最少操作次数，很容易得出状态转移方程

为了将动态规划算法优化为贪心算法，需要获取更多信息，从而剪去状态转移方程中的 min 函数。

可以考虑以下不等式：

(IEQ1)

证：利用数学归纳法。显然 k=1,2 时成立。所以仅需证明 f(2k+2) <= f(2k+3)，即

                1 + f(k+1) <= 2 + min{ f(k+1), f(k+2) }，仅需证明 f(k+1) <= 1 + f(k+2)。
                若 k=2t，即需证明 f(2t+1) <= 1 + f(2t+2)，即 2 + min{ f(t), f(t+1) } <= 2 + f(t+1)，显然成立；
                若 k=2t+1，即需证明 f(2t+2) <= 1 + f(2t+3)，仅需证明 f( 2(t+1) ) <= f( 2(t+1)+1 )，而

k-(t+1) = t > 0，故 (t+1) < k，由归纳假设即知不等式成立。

(IEQ2)

证：同样利用数学归纳法。显然 k=1,2 时成立。所以仅需证明 f(2k+3) >= f(2k+4)，即

2 + min{ f(k+1), f(k+2) } >= 1 + f(k+2)，仅需证明 1 + f(k+1) >= f(k+2)。
若 k=2t，即需证明 1 + f(2t+1) >= f(2t+2)，仅需证明 f(2t+1) >= f(2t+2)，而显然

t<=k，由归纳假设，不等式成立；

若 k=2t+1，即需证明 1 + f(2t+2) >= f(2t+3)，即 2 + f(t+1) >= 2 + min{ f(t+1), f(t+2) }，这是显然的。

有了 (IEQ1) (IEQ2) 两个不等式，事情就很好办了：

马上得到了我们 [解答一] 中辛苦探索出的又不容易将正确性的论据严格说清楚的贪心算法。

【数据与验证】

有了算法，我们可以编写程序获取一些数据，从而对问题有更直观的认识。

由于动态规划算法是最容易想到也最“显然”的，所以将以此为标准算法产生参考数据，来验证我们的简明算法的正确性。程序如下：

   1:  #include <iostream>

   2:  using namespace std;

3:

   4:  #define MAX_RANGE 9999999

   5:  unsigned tab[ MAX_RANGE + 1 ] = { 0, 0, 1, 2 };

6:

   7:  int main(){

   8:      unsigned num, count, tmp;

   9:      bool coincidental = true;

10:

  11:      for(num=4; num < MAX_RANGE; num++){

  12:          // 利用动态规划求得参考数据

  13:          if( num & 1 )

  14:              tab[num] = 2 + min( tab[ num/2 ], tab[ num/2 + 1 ] );

  15:          else

  16:              tab[num] = 1 + tab[ num>>1 ];

17:

  18:          // 施行操作并统计操作次数

  19:          for(tmp=num,count=0; tmp > 3; tmp>>=1,count++){

  20:              switch( tmp & 3 ){

  21:              case 1:

  22:                  tmp--, count++;

  23:                  break;

  24:              case 3:

  25:                  tmp++, count++;

  26:                  break;

  27:              }

  28:          }

  29:          count += ( tmp == 2 ? 1 : 2 );

30:

  31:          // 输出不符合参考数据的操作次数

  32:          if( count != tab[num] ){

  33:              coincidental = false;

  34:              cout<<num<<": "<<count<<"\t";

  35:          }

  36:      }

37:

  38:      if( coincidental )

  39:          cout<<endl<<endl<<"所有答案都是正确的。"<<endl<<endl;

  40:      else

  41:          cout<<endl<<endl<<"以上答案不准确。"<<endl<<endl;

42:

  43:      cout<<endl<<"前 100 个数的最优次数如下表："<<endl<<endl;

  44:      for(num=1; num < 101; num++){

  45:          cout<<num<<": "<<tab[num]<<"\t";

  46:          if( num % 5 == 0 )

  47:              cout<<endl;

  48:      }

49:

  50:      return 0;

  51:  }

//=========================================================//

        运行结果如下：

        所有答案都是正确的。

        前 100 个数的最优次数如下表：

        1: 0      2: 1      3: 2      4: 2      5: 3
        6: 3      7: 4      8: 3      9: 4      10: 4
        11: 5    12: 4    13: 5    14: 5    15: 5
        16: 4    17: 5    18: 5    19: 6    20: 5
        21: 6    22: 6    23: 6    24: 5    25: 6
        26: 6    27: 7    28: 6    29: 7    30: 6
        31: 6    32: 5    33: 6    34: 6    35: 7
        36: 6    37: 7    38: 7    39: 7    40: 6
        41: 7    42: 7    43: 8    44: 7    45: 8
        46: 7    47: 7    48: 6    49: 7    50: 7
        51: 8    52: 7    53: 8    54: 8    55: 8
        56: 7    57: 8    58: 8    59: 8    60: 7
        61: 8    62: 7    63: 7    64: 6    65: 7
        66: 7    67: 8    68: 7    69: 8    70: 8
        71: 8    72: 7    73: 8    74: 8    75: 9
        76: 8    77: 9    78: 8    79: 8    80: 7
        81: 8    82: 8    83: 9    84: 8    85: 9
        86: 9    87: 9    88: 8    89: 9    90: 9
        91: 9    92: 8    93: 9    94: 8    95: 8
        96: 7    97: 8    98: 8    99: 9    100: 8

//=========================================================//

【返璞归真】

一个算法，并不是越玄乎越高深越好，而是越朴素越简单越直观越容易理解越好。所以，接下来我们要引出一个所有人（包括没有算法感的人）都能理解的算法。由于这个算法的直观性，所以我不打算多费口舌，而是直接给出一个示例图，大家看了就明白了。

如果看懂了这个图，你就明白我们的算法时间复杂度为 O(logn)。至于空间复杂度，如果题目不要求你求出具体操作步骤，而只要你告诉他最少需要多少步，那么仅需两个额外空间，故空间复杂度为 O(1)；如果要求出具体操作步骤呢？也简单，记录上图中这样的序列，反推回去，即可，这样时间/空间复杂度皆为 O(logn)。

大道至简。完。

注：此算法部分受这篇文章的启发。

[C#] 浅谈C#托管程序中的资源释放问题(ZZ)

xiaoiiiyao — Mon, 03 Nov 2008 11:19:00 GMT

终于开始动手写这篇文章了，有个网友催了我好几次，今天终于可以静下心来完成它。

便于对文章的开展，需要先明确两个概念。

第一个就是很多人用.Net写程序，会谈到托管这个概念。那么.Net所指的资源托管到底是什么意思，是相对于所有资源，还是只限于某一方面资源？很多人对此不是很了解，其实.Net所指的托管只是针对内存这一个方面，并不是对于所有的资源；因此对于Stream，数据库的连接，GDI+的相关对象，还有Com对象等等，这些资源并不是受到.Net管理而统称为非托管资源。而对于内存的释放和回收，系统提供了GC-Garbage Collector，而至于其他资源则需要手动进行释放。

那么第二个概念就是什么是垃圾，通过我以前的文章，会了解到.Net类型分为两大类，一个就是值类型，另一个就是引用类型。前者是分配在栈上，并不需要GC回收；后者是分配在堆上，因此它的内存释放和回收需要通过GC来完成。GC的全称为“Garbage Collector”,顾名思义就是垃圾回收器，那么只有被称为垃圾的对象才能被GC回收。也就是说，一个引用类型对象所占用的内存需要被GC回收，需要先成为垃圾。那么.Net如何判定一个引用类型对象是垃圾呢，.Net的判断很简单，只要判定此对象或者其包含的子对象没有任何引用是有效的，那么系统就认为它是垃圾。

明确了这两个基本概念，接下来说说GC的运作方式以及其的功能。内存的释放和回收需要伴随着程序的运行，因此系统为GC安排了独立的线程。那么GC的工作大致是，查询内存中对象是否成为垃圾，然后对垃圾进行释放和回收。那么对于GC对于内存回收采取了一定的优先算法进行轮循回收内存资源。其次，对于内存中的垃圾分为两种，一种是需要调用对象的析构函数，另一种是不需要调用的。GC对于前者的回收需要通过两步完成，第一步是调用对象的析构函数，第二步是回收内存，但是要注意这两步不是在GC一次轮循完成，即需要两次轮循；相对于后者，则只是回收内存而已。

很明显得知，对于某个具体的资源，无法确切知道，对象析构函数什么时候被调用，以及GC什么时候会去释放和回收它所占用的内存。那么对于从C、C++之类语言转换过来的程序员来说，这里需要转变观念。

那么对于程序资源来说，我们应该做些什么，以及如何去做，才能使程序效率最高，同时占用资源能尽快的释放。前面也说了，资源分为两种，托管的内存资源，这是不需要我们操心的，系统已经为我们进行管理了；那么对于非托管的资源，这里再重申一下，就是Stream，数据库的连接，GDI+的相关对象，还有Com对象等等这些资源，需要我们手动去释放。

如何去释放，应该把这些操作放到哪里比较好呢。.Net提供了三种方法，也是最常见的三种，大致如下：

1． 析构函数；

2． 继承IDisposable接口，实现Dispose方法；

3． 提供Close方法。

经过前面的介绍，可以知道析构函数只能被GC来调用的，那么无法确定它什么时候被调用，因此用它作为资源的释放并不是很合理，因为资源释放不及时；但是为了防止资源泄漏，毕竟它会被GC调用，因此析构函数可以作为一个补救方法。而Close与Dispose这两种方法的区别在于，调用完了对象的Close方法后，此对象有可能被重新进行使用；而Dispose方法来说，此对象所占有的资源需要被标记为无用了，也就是此对象被销毁了，不能再被使用。例如，常见SqlConnection这个类，当调用完Close方法后，可以通过Open重新打开数据库连接，当彻底不用这个对象了就可以调用Dispose方法来标记此对象无用，等待GC回收。明白了这两种方法的意思后，大家在往自己的类中添加的接口时候，不要歪曲了这两者意思。

接下来说说这三个函数的调用时机，我用几个试验结果来进行说明，可能会使大家的印象更深。

首先是这三种方法的实现，大致如下：

/// <summary>

/// The class to show three disposal function

/// </summary>

public class DisposeClass:IDisposable

{

public void Close()

{

Debug.WriteLine( "Close called!" );

}

~DisposeClass()

{

Debug.WriteLine( "Destructor called!" );

}

#region IDisposable Members

public void Dispose()

{

// TODO: Add DisposeClass.Dispose implementation

Debug.WriteLine( "Dispose called!" );

}

#endregion

}

对于Close来说不属于真正意义上的释放，除了注意它需要显示被调用外，我在此对它不多说了。而对于析构函数而言，不是在对象离开作用域后立刻被执行，只有在关闭进程或者调用GC.Collect方法的时候才被调用，参看如下的代码运行结果。

private void Create()

{

DisposeClass myClass = new DisposeClass();

}

private void CallGC()

{

GC.Collect();

}

// Show destructor

Create();

Debug.WriteLine( "After created!" );

CallGC();

运行的结果为：

After created!

Destructor called!

显然在出了Create函数外，myClass对象的析构函数没有被立刻调用，而是等显示调用GC.Collect才被调用。

对于Dispose来说，也需要显示的调用，但是对于继承了IDisposable的类型对象可以使用using这个关键字，这样对象的Dispose方法在出了using范围后会被自动调用。例如：

using( DisposeClass myClass = new DisposeClass() )

{

//other operation here

}

如上运行的结果如下：

Dispose called!

那么对于如上DisposeClass类型的Dispose实现来说，事实上GC还需要调用对象的析构函数，按照前面的GC流程来说，GC对于需要调用析构函数的对象来说，至少经过两个步骤，即首先调用对象的析构函数，其次回收内存。也就是说，按照上面所写的Dispose函数，虽说被执行了，但是GC还是需要执行析构函数，那么一个完整的Dispose函数，应该通过调用GC.SuppressFinalize(this )来告诉GC，让它不用再调用对象的析构函数中。那么改写后的DisposeClass如下：

/// <summary>

/// The class to show three disposal function

/// </summary>

public class DisposeClass:IDisposable

{

public void Close()

{

Debug.WriteLine( "Close called!" );

}

~DisposeClass()

{

Debug.WriteLine( "Destructor called!" );

}

#region IDisposable Members

public void Dispose()

{

// TODO: Add DisposeClass.Dispose implementation

Debug.WriteLine( "Dispose called!" );

GC.SuppressFinalize( this );

}

#endregion

}

通过如下的代码进行测试。

private void Run()

{

using( DisposeClass myClass = new DisposeClass() )

{

//other operation here

}

private void CallGC()

{

GC.Collect();

}

// Show destructor

Run();

Debug.WriteLine( "After Run!" );

CallGC();

运行的结果如下：

Dispose called!

After Run!

显然对象的析构函数没有被调用。通过如上的实验以及文字说明，大家会得到如下的一个对比表格。

	析构函数	Dispose方法	Close方法
意义	销毁对象	销毁对象	关闭对象资源
调用方式	不能被显示调用，会被GC调用	需要显示调用或者通过using语句	需要显示调用
调用时机	不确定	确定，在显示调用或者离开using程序块	确定，在显示调用时

那么在定义一个类型的时候，是否一定要给出这三个函数地实现呢。

我的建议大致如下。

1． 提供析构函数，避免资源未被释放，主要是指非内存资源；

2． 对于Dispose和Close方法来说，需要看所定义的类型所使用的资源（参看前面所说），而决定是否去定义这两个函数；

3． 在实现Dispose方法的时候，一定要加上“GC.SuppressFinalize( this )”语句，避免再让GC调用对象的析构函数。

C#程序所使用的内存是受托管的，但不意味着滥用，好地编程习惯有利于提高代码的质量以及程序的运行效率。

[C++]C++的四种cast操作符的区别--类型转换(ZZ)

xiaoiiiyao — Sun, 02 Nov 2008 00:12:00 GMT

C++的四种cast操作符的区别
发信站: 水木社区 (Thu Jan 26 21:15:16 2006), 站内

声明 by NetMD：
并非我的原创，来自互联网，且是两篇帖子的合集，个人觉得这样才比较完备

----------------------------------------------------------------------

Q:什么是C风格转换？什么是static_cast, dynamic_cast 以及 reinterpret_cast？区别是什么？为什么要注意？

A:转换的含义是通过改变一个变量的类型为别的类型从而改变该变量的表示方式。为了类型转换一个简单对象为另一个对象你会使用传统的类型转换操作符。比如，为了转换一个类型为doubole的浮点数的指针到整型：
代码:
int i;
double d;

i = (int) d;
或者：

i = int (d);

对于具有标准定义转换的简单类型而言工作的很好。然而，这样的转换符也能不分皂白的应用于类（class）和类的指针。ANSI-C++标准定义了四个新的转换符：'reinterpret_cast', 'static_cast', 'dynamic_cast' 和 'const_cast'，目的在于控制类(class)之间的类型转换。
代码:
reinterpret_cast<new_type>(expression)
dynamic_cast<new_type>(expression)
static_cast<new_type>(expression)
const_cast<new_type>(expression)

1 reinterpret_cast

'reinterpret_cast'转换一个指针为其它类型的指针。它也允许从一个指针转换为整数类型。反之亦然。（译注：是指针具体的地址值作为整数值？）
这个操作符能够在非相关的类型之间转换。操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换。

如果情况是从一个指针到整型的拷贝，内容的解释是系统相关的，所以任何的实现都不是方便的。一个转换到足够大的整型能够包含它的指针是能够转换回有效的指针的。

代码:
class A {};
class B {};

A * a = new A;
B * b = reinterpret_cast<B *>(a);
'reinterpret_cast'就像传统的类型转换一样对待所有指针的类型转换。

2 static_cast

'static_cast'允许执行任意的隐式转换和相反转换动作。（即使它是不允许隐式的）

应用到类的指针上，意思是说它允许子类类型的指针转换为父类类型的指针（这是一个有效的隐式转换），同时，也能够执行相反动作：转换父类为它的子类。

在这最后例子里，被转换的父类没有被检查是否与目的类型相一致。
代码：
class Base {};
class Derived : public Base {};

Base *a = new Base;
Derived *b = static_cast<Derived *>(a);
'static_cast'除了操作类型指针，也能用于执行类型定义的显式的转换，以及基础类型之间的标准转换:

代码:
double d = 3.14159265;
int i = static_cast<int>(d);

3 dynamic_cast

'dynamic_cast'只用于对象的指针和引用。当用于多态类型时，它允许任意的隐式类型转换以及相反过程。不过，与static_cast不同，在后一种情况里（注：即隐式转换的相反过程），dynamic_cast会检查操作是否有效。也就是说，它会检查转换是否会返回一个被请求的有效的完整对象。
检测在运行时进行。如果被转换的指针不是一个被请求的有效完整的对象指针，返回值为NULL.
代码：
class Base { virtual dummy() {} };
class Derived : public Base {};

Base* b1 = new Derived;
Base* b2 = new Base;

Derived* d1 = dynamic_cast<Derived *>(b1); // succeeds
Derived* d2 = dynamic_cast<Derived *>(b2); // fails: returns 'NULL'

如果一个引用类型执行了类型转换并且这个转换是不可能的，一个bad_cast的异常类型被抛出：
代码:
class Base { virtual dummy() {} };
class Derived : public Base { };

Base* b1 = new Derived;
Base* b2 = new Base;

Derived d1 = dynamic_cast<Derived &*>(b1); // succeeds
Derived d2 = dynamic_cast<Derived &*>(b2); // fails: exception thrown

4 const_cast

这个转换类型操纵传递对象的const属性，或者是设置或者是移除：
代码:
class C {};

const C *a = new C;

C *b = const_cast<C *>(a);
其它三种操作符是不能修改一个对象的常量性的。
注意：'const_cast'也能改变一个类型的volatile qualifier。

--------------------------------------------------------------------

C++的4种类型转换

   一、C 风格（C-style）强制转型如下：

   (T) expression // cast expression to be of type T
   函数风格（Function-style）强制转型使用这样的语法：
   T(expression) // cast expression to be of type T
   这两种形式之间没有本质上的不同，它纯粹就是一个把括号放在哪的问题。我把这两种形式称为旧风格（old-style）的强制转型。

   二、 C++的四种强制转型形式：

　　C++ 同时提供了四种新的强制转型形式（通常称为新风格的或 C++ 风格的强制转型）：
　　const_cast(expression)
　　dynamic_cast(expression)
　　reinterpret_cast(expression)
　　static_cast(expression)

　　每一种适用于特定的目的：

　　·dynamic_cast 主要用于执行“安全的向下转型（safe downcasting）”，也就是说，要确定一个对象是否是一个继承体系中的一个特定类型。它是唯一不能用旧风格语法执行的强制转型，也是唯一可能有重大运行时代价的强制转型。

   ·static_cast 可以被用于强制隐型转换（例如，non-const 对象转型为 const 对象，int 转型为 double，等等），它还可以用于很多这样的转换的反向转换（例如，void* 指针转型为有类型指针，基类指针转型为派生类指针），但是它不能将一个 const 对象转型为 non-const 对象（只有 const_cast 能做到），它最接近于C-style的转换。

　　·const_cast 一般用于强制消除对象的常量性。它是唯一能做到这一点的 C++ 风格的强制转型。

　　·reinterpret_cast 是特意用于底层的强制转型，导致实现依赖（implementation-dependent）（就是说，不可移植）的结果，例如，将一个指针转型为一个整数。这样的强制转型在底层代码以外应该极为罕见。
　　
　　旧风格的强制转型依然合法，但是新的形式更可取。首先，在代码中它们更容易识别（无论是人还是像 grep 这样的工具都是如此），这样就简化了在代码中寻找类型系统被破坏的地方的过程。第二，更精确地指定每一个强制转型的目的，使得编译器诊断使用错误成为可能。例如，如果你试图使用一个 const_cast 以外的新风格强制转型来消除常量性，你的代码将无法编译。

==
== dynamic_cast .vs. static_cast
==

class B { ... };
class D : public B { ... };

void f(B* pb)
{
   D* pd1 = dynamic_cast<D*>(pb);
   D* pd2 = static_cast<D*>(pb);
}

If pb really points to an object of type D, then pd1 and pd2 will get the same value. They will also get the same value if pb == 0.

If pb points to an object of type B and not to the complete D class, then dynamic_cast will know enough to return zero. However, static_cast relies on the programmer’s assertion that pb points to an object of type D and simply returns a pointer to that supposed D object.

   即dynamic_cast可用于继承体系中的向下转型，即将基类指针转换为派生类指针，比static_cast更严格更安全。dynamic_cast在执行效率上比static_cast要差一些,但static_cast在更宽上范围内可以完成映射,这种不加限制的映射伴随着不安全性.static_cast覆盖的变换类型除类层次的静态导航以外,还包括无映射变换,窄化变换(这种变换会导致对象切片,丢失信息),用VOID*的强制变换,隐式类型变换等...

==
== static_cast .vs. reinterpret_cast
==

   reinterpret_cast是为了映射到一个完全不同类型的意思,这个关键词在我们需要把类型映射回原有类型时用到它.我们映射到的类型仅仅是为了故弄玄虚和其他目的,这是所有映射中最危险的.(这句话是C++编程思想中的原话)

   static_cast 和 reinterpret_cast 操作符修改了操作数类型. 它们不是互逆的; static_cast 在编译时使用类型信息执行转换, 在转换执行必要的检测(诸如指针越界计算, 类型检查). 其操作数相对是安全的. 另一方面, reinterpret_cast 仅仅是重新解释了给出的对象的比特模型而没有进行二进制转换, 例子如下:

   int n=9; double d=static_cast < double > (n);

   上面的例子中, 我们将一个变量从 int 转换到 double. 这些类型的二进制表达式是不同的. 要将整数 9 转换到双精度整数 9, static_cast 需要正确地为双精度整数 d 补足比特位. 其结果为 9.0. 而reinterpret_cast 的行为却不同:

   int n=9;
   double d=reinterpret_cast<double & > (n);

   这次, 结果有所不同. 在进行计算以后, d 包含无用值. 这是因为 reinterpret_cast 仅仅是复制 n 的比特位到 d, 没有进行必要的分析.

转载：http://welfare.cnblogs.com/articles/336091.html

[Algorithm]反转一个字节和判断32位整数二进制中1的个数的算法(zz)

xiaoiiiyao — Sat, 01 Nov 2008 16:22:00 GMT

反转一个字节和判断32位整数二进制中1的个数的算法

unsigned char reverse8( unsigned char c )
{
    c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
    c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
    c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
    return c;
}

unsigned long func(unsigned long x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL);
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL);
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL);
    return x;
}

先看问题1: 反转一个字节。
它的算法是这样的: 首先是2位2位为一组，交换前一半和后一半。再4位4位为一组，交换前一半和后一半。再8位为一组，交换前一半和后一半

。
可能还有点说不清楚。我举个例子。
将1 2 3 4 5 6 7 8 反转。
(1)2个2个为一组，交换前一半和后一半, 变成。
  2 1 4 3 6 5 8 7
(2)4个4个为一组，交换前一半和后一半，变成
  4 3 2 1 8 7 6 5
(3)再8个为一组，交换前一半和后一半, 变成
  8 7 6 5 4 3 2 1
反转成功。
这样的算法本来很是简单，很容易用数学归纳法证明其正确。这函数，巧妙就巧妙在作了并行计算，分组，它一次就计算完了。

先看第一个语句。c = ( c & 0x55) << 1 | ( c & 0xAA ) >> 1;
0x55其实就是01010101, 0xAA就是10101010
假设 c=abcdefgh
c & 0x55 = 0b0d0f0h,    c & 0xAA = a0c0e0g0
跟着，前者左移一位, b0d0f0h0, 后者右移一位, 0a0c0e0g, 再一个|运算，就两位两位交换了位置。
想象一下，你有一个长纸条，分成一格一格，每格写一个字，假如你将纸条每隔一格剪一个小洞，滑一格，覆盖在原来的纸条上，你就会看到两个两个字交换了位置。
(注: |运算可以换成+运算，想一想为什么)

第二个语句。 c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
0x33 = 00110011, 0xCC=11001100。

第三个语句。c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
0x0f = 00001111, 0xF0=11110000.

这两个语句的作用也是分组，将一半位变成0，移位滑动，跟着再组合，就分组交换了位置。
不防想象两个小纸条剪洞叠加。

这方法应该可以推广。
理解了问题1，也就很容易理解问题2了.

问题2: 判断32位整数二进制中1的个数。
和问题1一样，也是采用了分组并行计算。

基本方法是: 2位2位为一组，相加，看看有几个1。再4位4位为一组，相加，看看有几个1......
还是说的不太明白。接着分析。

为了简单说明，先看看8位的情形。相应地，函数里面的语句变成。
x = (x & 0x55) + ((x >> 1) & 0x55);   (1)
x = (x & 0x33) + ((x >> 2) & 0x33);   (2)
x = (x & 0x0f) + ((x >> 4) & 0x0f);   (3)
return x;

假设x=abcdefgh. 0x55=01010101
x & 0x55 = 0b0d0f0h.  (x>>1) & 0x55 = 0a0c0e0g。相加。就可以知道2位2位一组1的个数。

比如x=11111111
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=10101010。你2位2位地看，10=2, 就是2 2 2 2, 就是说各组都是2个1。
比如x=00101001
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=00010101。你2位2位地看，就是0 1 1 1, 前1组只有0个1，后面的组都是1个1。

好啦。再来看。0x33=00110011。
x=abcdefgh.
x=(x & 0x33)+((x >> 2)&0x33); 相当于, 00ab00ef + 00cd00gh。
因为语句(1)之后。ab指示了头两位有多少个1，cd指示了下两位有多少个1。相加00ab+00cd就指示前4位有多少个1。这样就是4位4位为一组。注意这样的分组，组与组之间永远都不会产生进位的。正因为不会产生进位，才可以分开来看。

好啦。下面的过程都是一样的，不再多说。
8位，16位，32位都一样。

转自：http://blog.chinaunix.net/u2/66039/showart_526398.html