陋居

淡薄名利,修身养性

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  31 Posts :: 1 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2013年2月19日 #

C语言中对于下面的两种情况,是否相同呢?

char a[] = "abcdefg";---------------1

char *p = "abcdefg";-----------------2

在谈到这些区别时,应该先谈一下计算机中对变量是如何存储的。从编译原理中我们知道,对于所有的变量他都会影射到一个符号表中。为了简化,这里给出一种最简单的便于理解的符号表:

a

0xffaa

p

0xffcc

表1 一个简单的符号表示例

以上表格中a代表一个变量,0xffaa则为变量a的内容的存储地址;p代表另一个变量,0xffcc为变量p的内容的存储地址。对于数组型的变量和指针型的变量,其地址代表的含义不同。

对于数组a:

这个0xffaa地址就是其存放数组内容的首地址了。对于a[i]的引用步骤如下:

步骤一、取出i的值,将他与0xffaa相加;

步骤二、取出为(0xffaa+i)中的内容。

对于指针p:

这个0xffcc地址就是中存放的不是字符串的内容,而是一个地址,这个地址才是字符串的首地址,对p[i]或者用指针表示*(p+i)的应用步骤如下:

步骤一、取出0xffcc地址中的内容,例如为0xffdf;

步骤二、取出地址0xffdf中的内容。

数组和指针的对比如下图:

下面是在VC6.0下作的一个试验,通过这个试验大家可以看到,虽然同过[]和通过*引用都一样,但在内部处理的方法是不一样的。

#include "stdafx.h"

#include "stdio.h"

int main(int argc, char* argv[])

{

     int a[3]={1,2,3};

     int *p =a;

     printf("a:%d,&a:%d,a[0]:%d,*a:%d,p:%d,&p:%d,*p:%d,p[0]:%d",a,&a,

a[0],*a,p,&p,*p,p[0]);

     return 0;

}

输出结果:

a:1310580,&a:1310580,a[0]:1,*a:1,p:1310580,&p:1310576,*p:1,p[0]:1。

由上面的分析可知,如果在一个文件中定义了一个数组int maychar[100],那么下面的声明就是完全错误的。

extern int *maychar;

这样的话,在引用时他就会按照指针的方法来引用数组。正确的声明应该是exter int maychar[];这里数组的大小并不重要。下面将指针与数组的区别用表格的形式列出如下:

指针

数组

保存数据的地址

保存数据

间接访问数据

直接访问

通常用于动态数据结构

通常用于存储固定数目数据类型相同的元素

相关操作malloc(),free()等

隐式分配和删除

同常指向匿名数据

自身即为数据名

表2 指针与数组的区别

还要提醒一点的就是:

char a[] = "abcdefg";---------------数组内容能修改(字符数组)

char *p = "abcdefg";-----------------内容不能修改(字符串常量)

在ANSI C中,初始化指针是所创建的字符串时常量,被定义为只读,如果试图通过指针修改这个字符串的值,程序就会出现为定义的行为。

posted @ 2013-02-19 13:33 eircQ 阅读(189) | 评论 (0)编辑 收藏

2012年1月20日 #


      可以说2012是转折的一年。

      我也开始思考自己。
      公司在转型,我也在转变。
      
      2012年的目标:
      一.控制自己。
  做自己对自己持续受益的事情。
  
  二.不断地学习。学习前人的经验,避免前人的错误。
      看书(学习技能,学习历史),观察周围的人,思考。

      三.认识自己。努力去做好自己。建设自己的原则。(每天思考)
      
      四.更加激情地去热爱生活,去融入到生活,工作中。真诚对待每一个人。



posted @ 2012-01-20 01:38 eircQ 阅读(1489) | 评论 (1)编辑 收藏

2011年6月17日 #

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法对算法本身的速度要求很高。

  而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将给出详细的说明。

  对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。

  我将按照算法的复杂度,从简单到难来分析算法。

  第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。

  第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。

  第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。

  第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。


  现在,让我们开始吧:
  
一、简单排序算法
由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。

1.冒泡法:
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:
#include <iostream.h>

void BubbleSort(int* pData,int Count)
{
  int iTemp;
  for(int i=1;i<Count;i++)
  {
    for(int j=Count-1;j>=i;j--)
    {
      if(pData[j]<pData[j-1])
      {
        iTemp = pData[j-1];
        pData[j-1] = pData[j];
        pData[j] = iTemp;
      }
    }
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  BubbleSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}

倒序(最糟情况)
第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次

其他:
第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次

上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意,我们给出O方法的定义:

  若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没学好数学呀,对于编程数学是非常重要的!!!)

现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时, 交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样 的原因,我们通常都是通过循环次数来对比算法。


2.交换法:
交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
  int iTemp;
  for(int i=0;i<Count-1;i++)
  {
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<pData[i])
      {
        iTemp = pData[i];
        pData[i] = pData[j];
        pData[j] = iTemp;
      }
    }
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  ExchangeSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次

其他:
第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次

从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。

3.选择法:
现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)
这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中选择最小的与第二个交换,这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
  int iTemp;
  int iPos;
  for(int i=0;i<Count-1;i++)
  {
    iTemp = pData[i];
    iPos = i;
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<iTemp)
      {
        iTemp = pData[j];
        iPos = j;
      }
    }
    pData[iPos] = pData[i];
    pData[i] = iTemp;
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  SelectSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数:6次
交换次数:2次

其他:
第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数:6次
交换次数:3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n
所以我们有f(n)=O(n)。
所以,在数据较乱的时候,可以减少一定的交换次数。


4.插入法:
插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
  int iTemp;
  int iPos;
  for(int i=1;i<Count;i++)
  {
    iTemp = pData[i];
    iPos = i-1;
    while((iPos>=0) && (iTemp<pData[iPos]))
    {
      pData[iPos+1] = pData[iPos];
      iPos--;
    }
    pData[iPos+1] = iTemp;
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  InsertSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}

倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数:6次
交换次数:3次

其他:
第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数:4次
交换次数:2次

上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,因为其循环次数虽然并不固定,我们仍可以使用O方 法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单排序的不同,交换次数仍然 可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们 需要三次‘=’,而这里显然多了一些,所以我们浪费了时间。

最终,我个人认为,在简单排序算法中,选择法是最好的。


二、高级排序算法:
高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(最容易的方法——递归)。

1.快速排序:
#include <iostream.h>

void run(int* pData,int left,int right)
{
  int i,j;
  int middle,iTemp;
  i = left;
  j = right;
  middle = pData[(left+right)/2]; //求中间值
  do{
    while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
      i++;     
    while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
      j--;
    if(i<=j)//找到了一对值
    {
      //交换
      iTemp = pData[i];
      pData[i] = pData[j];
      pData[j] = iTemp;
      i++;
      j--;
    }
  }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)

  //当左边部分有值(left<j),递归左半边
  if(left<j)
    run(pData,left,j);
  //当右边部分有值(right>i),递归右半边
  if(right>i)
    run(pData,i,right);
}

void QuickSort(int* pData,int Count)
{
  run(pData,0,Count-1);
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  QuickSort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}

这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况
1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。
2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。
第一层递归,循环n次,第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大??呵呵,你完全不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。
如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢
于快速排序(因为要重组堆)。

三、其他排序
1.双向冒泡:
通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。
代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。
反正我认为这是一段有趣的代码,值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
  int iTemp;
  int left = 1;
  int right =Count -1;
  int t;
  do
  {
    //正向的部分
    for(int i=right;i>=left;i--)
    {
      if(pData[i]<pData[i-1])
      {
        iTemp = pData[i];
        pData[i] = pData[i-1];
        pData[i-1] = iTemp;
        t = i;
      }
    }
    left = t+1;

    //反向的部分
    for(i=left;i<right+1;i++)
    {
      if(pData[i]<pData[i-1])
      {
        iTemp = pData[i];
        pData[i] = pData[i-1];
        pData[i-1] = iTemp;
        t = i;
      }
    }
    right = t-1;
  }while(left<=right);
}

void main()
{
  int data[] = {10,9,8,7,6,5,4};
  Bubble2Sort(data,7);
  for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}


2.SHELL排序
这个排序非常复杂,看了程序就知道了。
首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。
工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
  int step[4];
  step[0] = 9;
  step[1] = 5;
  step[2] = 3;
  step[3] = 1;

  int iTemp;
  int k,s,w;
  for(int i=0;i<4;i++)
  {
    k = step[i];
    s = -k;
    for(int j=k;j<Count;j++)
    {
      iTemp = pData[j];
      w = j-k;//求上step个元素的下标
      if(s ==0)
      {
        s = -k;
        s++;
        pData[s] = iTemp;
      }
      while((iTemp<pData[w]) && (w>=0) && (w<=Count))
      {
        pData[w+k] = pData[w];
        w = w-k;
      }
      pData[w+k] = iTemp;
    }
  }
}

void main()
{
  int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
  ShellSort(data,12);
  for (int i=0;i<12;i++)
    cout<<data[i]<<" ";
  cout<<"\n";
}
呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并“超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。

最后,希望大家愉快的编程。有什么意见,给我提吧!
posted @ 2011-06-17 08:09 eircQ 阅读(214) | 评论 (0)编辑 收藏

2011年5月17日 #

  用VS2005调试一个程序,出现“没有找到MFC80D.DLL……”的提示使程序不能运行,删掉Debug文件夹重新编译问题依旧,上网查了一下,有说是vs路径的原因,有说是vs没装好的原因。
  在“启动调试F5”的工具图标右侧有一栏“解决方案配置”,无意中将其中的“Debug”改为“Release”,F5通过,运行正常,项目目录下生成“Release”文件夹,Debug方式生成的“Debug"文件夹是无用的。原因如下:
 

  DEBUG和RELEASE 版本差异及调试相关问题:
  I.         内存分配问题

  1.          变量未初始化。下面的程序在debug中运行的很好。

      thing * search(thing * something)
        BOOL found;
        for(int i = 0; i < whatever.GetSize(); i++)
          {
          if(whatever[i]->field == something->field)
             { /* found it */
              found = TRUE;
              break;
             } /* found it */
           }
    if(found)
             return whatever[i];
    else
             return NULL;
  而在release中却不行,因为debug中会自动给变量初始化found=FALSE,而在release版中则不会。所以尽可能的给变量、类或结构初始化。

  2.            数据溢出的问题 
        如:char buffer[10];
             int counter;
       lstrcpy(buffer, "abcdefghik");

  在debug版中buffer的NULL覆盖了counter的高位,但是除非counter>16M,什么问题也没有。但是在release版中,counter可能被放在寄存器中,这样NULL就覆盖了buffer下面的空间,可能就是函数的返回地址,这将导致ACCESS ERROR。
  3.         DEBUG版和RELEASE版的内存分配方式是不同的。如果你在DEBUG版中申请   ele 为 6*sizeof(DWORD)=24bytes,实际上分配给你的是32bytes(debug版以32bytes为单位分配),而在release版,分配给你的就是24bytes(release版以8bytes为单位),所以在debug版中如果你写ele[6],可能不会有什么问题,而在release版中,就有ACCESS VIOLATE。

  II.      ASSERT和VERIFY

  1.         ASSERT在Release版本中是不会被编译的。

  ASSERT宏是这样定义的

        #ifdef _DEBUG
        #define ASSERT(x) if( (x) == 0) report_assert_failure()
        #else
        #define ASSERT(x)
        #endif
        实际上复杂一些,但无关紧要。假如你在这些语句中加了程序中必须要有的代码
  比如

  ASSERT(pNewObj = new CMyClass);

  pNewObj->MyFunction();

  这种时候Release版本中的pNewObj不会分配到空间

  所以执行到下一个语句的时候程序会报该程序执行了非法操作的错误。这时可以用VERIFY :

        #ifdef _DEBUG
        #define VERIFY(x) if( (x) == 0) report_assert_failure()
 
 
  #else

        #define VERIFY(x) (x)
        #endif
  这样的话,代码在release版中就可以执行了。

  III.   参数问题:

  自定义消息的处理函数,必须定义如下:

  afx_msg LRESULT OnMyMessage(WPARAM, LPARAM);

  返回值必须是HRESULT型,否则Debug会过,而Release出错

  IV.  内存分配

  保证数据创建和清除的统一性:如果一个DLL提供一个能够创建数据的函数,那么这个DLL同时应该提供一个函数销毁这些数据。数据的创建和清除应该在同一个层次上。

  V.     DLL的灾难

  人们将不同版本DLL混合造成的不一致性形象的称为 “动态连接库的地狱“(DLL Hell) ,甚至微软自己也这么说(http://msdn.microsoft.com/library/techart/dlldanger1.htm)。

       如果你的程序使用你自己的DLL时请注意:

  1.       不能将debug和release版的DLL混合在一起使用。debug都是debug版,release版都是release版。

  解决办法是将debug和release的程序分别放在主程序的debug和release目录下


  2.         千万不要以为静态连接库会解决问题,那只会使情况更糟糕。

  VI.  RELEASE板中的调试:

  1.         将ASSERT() 改为 VERIFY() 。找出定义在"#ifdef _DEBUG"中的代码,如果在RELEASE版本中需要这些代码请将他们移到定义外。查找TRACE(...)中代码,因为这些代码在RELEASE中也不被编译。请认真检查那些在RELEASE中需要的代码是否并没有被便宜。

  2.         变量的初始化所带来的不同,在不同的系统,或是在DEBUG/RELEASE版本间都存在这样的差异,所以请对变量进行初始化。

  3.         是否在编译时已经有了警告?请将警告级别设置为3或4,然后保证在编译时没有警告出现.

  VII.   将Project Settings" 中 "C++/C " 项目下优化选项改为Disbale(Debug)。编译器的优化可能导致许多意想不到的错误,请参考http://www.pgh.net/~newcomer/debug_release.htm

  1.         此外对RELEASE版本的软件也可以进行调试,请做如下改动:

  在"Project Settings" 中 "C++/C " 项目下设置 "category" 为 "General" 并且将"Debug Info"设置为 "Program Database"。

  在 "Link"项目下选中"Generate Debug Info"检查框。

  "Rebuild All"

  如此做法会产生的一些限制:

  无法获得在MFC DLL中的变量的值。

  必须对该软件所使用的所有DLL工程都进行改动。

  另:

  MS BUG:MS的一份技术文档中表明,在VC5中对于DLL的"Maximize Speed"优化选项并未被完全支持,因此这将会引起内存错误并导致程序崩溃。

  2.         www.sysinternals.com有一个程序DebugView,用来捕捉OutputDebugString的输出,运行起来后(估计是自设为system debugger)就可以观看所有程序的OutputDebugString的输出。此后,你可以脱离VC来运行你的程序并观看调试信息。

  3.         有一个叫Gimpel Lint的静态代码检查工具,据说比较好用。http://www.gimpel.com 不过要化$的。

参考文献:

1)         http://www.cygnus-software.com/papers/release_debugging.html

2)        http://www.pgh.net/~newcomer/debug_release.htm

posted @ 2011-05-17 09:31 eircQ 阅读(314) | 评论 (0)编辑 收藏

2010年12月2日 #

期:2004-07-30]来源:CSDN  作者:[字体:  ]

--------------- 
什么是 Hash 
Hash 的重要特性 
Hash 函数的实现 
主要的 Hash 算法 
Hash 算法的安全问题 
Hash 算法的应用 
结 论 
---------------


Hash,一般翻译做“散列”,也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。

数学表述为:h = H(M) ,其中H( )--单向散列函数,M--任意长度明文,h--固定长度散列值。

 

在信息安全领域中应用的Hash算法,还需要满足其他关键特性:

第一当然是单向性(one-way),从预映射,能够简单迅速的得到散列值,而在计算上不可能构造一个预映射,使其散列结果等于某个特定的散列值,即构造相应的M=H-1(h)不可行。这样,散列值就能在统计上唯一的表征输入值,因此,密码学上的 Hash 又被称为"消息摘要(message digest)",就是要求能方便的将"消息"进行"摘要",但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。

第二是抗冲突性(collision-resistant),即在统计上无法产生2个散列值相同的预映射。给定M,计算上无法找到M',满足H(M)=H(M') ,此谓弱抗冲突性;计算上也难以寻找一对任意的M和M',使满足H(M)=H(M') ,此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)",在一个10人的团体中,你能找到和你生日相同的人的概率是2.4%,而在同一团体中,有2人生日相同的概率是11.7%。类似的,当预映射的空间很大的情况下,算法必须有足够的强度来保证不能轻易找到"相同生日"的人。

第三是映射分布均匀性和差分分布均匀性,散列结果中,为 0 的 bit 和为 1 的 bit ,其总数应该大致相等;输入中一个 bit 的变化,散列结果中将有一半以上的 bit 改变,这又叫做"雪崩效应(avalanche effect)";要实现使散列结果中出现 1bit 的变化,则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息,尽量均匀的反映到输出的每一个 bit 上去;输出中的每一个 bit,都是输入中尽可能多 bit 的信息一起作用的结果。

 

Damgard 和 Merkle 定义了所谓“压缩函数(compression function)”,就是将一个固定长度输入,变换成较短的固定长度的输出,这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复“压缩”输入的分组和前一次压缩处理的结果的过程,直到整个消息都被压缩完毕,最后的输出作为整个消息的散列值。尽管还缺乏严格的证明,但绝大多数业界的研究者都同意,如果压缩函数是安全的,那么以上述形式散列任意长度的消息也将是安全的。这就是所谓 Damgard/Merkle 结构:

在下图中,任意长度的消息被分拆成符合压缩函数输入要求的分组,最后一个分组可能需要在末尾添上特定的填充字节,这些分组将被顺序处理,除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外,当前分组将和前一个分组的压缩函数输出一起被作为这一次压缩的输入,而其输出又将被作为下一个分组压缩函数输入的一部分,直到最后一个压缩函数的输出,将被作为整个消息散列的结果。

 

 

MD5 和 SHA1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的。

1) MD4 
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。它的安全性不像RSA那样基于数学假设,尽管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻击了它3轮变换中的 2 轮,证明了它并不像期望的那样安全,但它的整个算法并没有真正被破解过,Rivest 也很快进行了改进。

下面是一些MD4散列结果的例子:

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0 
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24 
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d 
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b 
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9 
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4 
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536


2) MD5 
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。它较MD4所做的改进是:

1) 加入了第四轮 
2) 每一步都有唯一的加法常数; 
3) 第二轮中的G函数从((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 变为 ((X ∧ Z) ∨ (Y ∧ ~Z))以减小其对称性; 
4) 每一步都加入了前一步的结果,以加快"雪崩效应"; 
5) 改变了第2轮和第3轮中访问输入子分组的顺序,减小了形式的相似程度; 
6) 近似优化了每轮的循环左移位移量,以期加快"雪崩效应",各轮的循环左移都不同。 
尽管MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好。

消息首先被拆成若干个512位的分组,其中最后512位一个分组是“消息尾+填充字节(100…0)+64 位消息长度”,以确保对于不同长度的消息,该分组不相同。64位消息长度的限制导致了MD5安全的输入长度必须小于264bit,因为大于64位的长度信息将被忽略。而4个32位寄存器字初始化为A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210,它们将始终参与运算并形成最终的散列结果。

接着各个512位消息分组以16个32位字的形式进入算法的主循环,512位消息分组的个数据决定了循环的次数。主循环有4轮,每轮分别用到了非线性函数

F(X, Y, Z) = (X ∧ Y) ∨ (~X ∧ Z) 
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ~Z) 
H(X, Y, Z) =X ⊕ Y ⊕ Z 
I(X, Y, Z) = X ⊕ (Y ∨ ~Z) 
这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作:将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果与第4个相加,再加上32位字和一个32位字的加法常数,并将所得之值循环左移若干位,最后将所得结果加上a、b、c、d之一,并回送至ABCD,由此完成一次循环。

所用的加法常数由这样一张表T[i]来定义,其中i为1…64,T[i]是i的正弦绝对值之4294967296次方的整数部分,这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性性。

当所有512位分组都运算完毕后,ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子:

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e 
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661 
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72 
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0 
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b 
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f 
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a 
参考相应RFC文档可以得到MD4、MD5算法的详细描述和算法的C源代码。

3) SHA1 及其他 
SHA1是由NIST NSA设计为同DSA一起使用的,访问http://www.itl.nist.gov/fipspubs可以得到它的详细规范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。因为它将产生160bit的散列值,因此它有5个参与运算的32位寄存器字,消息分组和填充方式与MD5相同,主循环也同样是4轮,但每轮进行20次操作,非线性运算、移位和加法运算也与MD5类似,但非线性函数、加法常数和循环左移操作的设计有一些区别,可以参考上面提到的规范来了解这些细节。下面是一些SHA1散列结果的例子:

SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d 
SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1 
其他一些知名的Hash算法还有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的这些都属于"纯"Hash算法。还有另2类Hash算法,一类就是基于对称分组算法的单向散列算法,典型的例子是基于DES的所谓Davies-Meyer算法,另外还有经IDEA改进的Davies-Meyer算法,它们两者目前都被认为是安全的算法。另一类是基于模运算/离散对数的,也就是基于公开密钥算法的,但因为其运算开销太大,而缺乏很好的应用前景。

 

没有通过分析和差分攻击考验的算法,大多都已经夭折在实验室里了,因此,如果目前流行的Hash算法能完全符合密码学意义上的单向性和抗冲突性,就保证了只有穷举,才是破坏Hash运算安全特性的唯一方法。为了对抗弱抗冲突性,我们可能要穷举个数和散列值空间长度一样大的输入,即尝试2^128或2^160个不同的输入,目前一台高档个人电脑可能需要10^25年才能完成这一艰巨的工作,即使是最高端的并行系统,这也不是在几千年里的干得完的事。而因为"生日攻击"有效的降低了需要穷举的空间,将其降低为大约1.2*2^64或1.2*2^80,所以,强抗冲突性是决定Hash算法安全性的关键。

在NIST新的 Advanced Encryption Standard (AES)中,使用了长度为128、192、256bit 的密钥,因此相应的设计了 SHA256、SHA384、SHA512,它们将提供更好的安全性。

 

Hash算法在信息安全方面的应用主要体现在以下的3个方面:

1) 文件校验 
我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性,使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。它常被用在下面的2种情况下:

第一是文件传送后的校验,将得到的目标文件计算 md5 checksum,与源文件的md5 checksum 比对,由两者 md5 checksum 的一致性,可以从统计上保证2个文件的每一个码元也是完全相同的。这可以检验文件传输过程中是否出现错误,更重要的是可以保证文件在传输过程中未被恶意篡改。一个很典型的应用是ftp服务,用户可以用来保证多次断点续传,特别是从镜像站点下载的文件的正确性。

更出色的解决方法是所谓的代码签名,文件的提供者在提供文件的同时,提供对文件Hash值用自己的代码签名密钥进行数字签名的值,及自己的代码签名证书。文件的接受者不仅能验证文件的完整性,还可以依据自己对证书签发者和证书拥有者的信任程度,决定是否接受该文件。浏览器在下载运行插件和java小程序时,使用的就是这样的模式。

第二是用作保存二进制文件系统的数字指纹,以便检测文件系统是否未经允许的被修改。不少系统管理/系统安全软件都提供这一文件系统完整性评估的功能,在系统初始安装完毕后,建立对文件系统的基础校验和数据库,因为散列校验和的长度很小,它们可以方便的被存放在容量很小的存储介质上。此后,可以定期或根据需要,再次计算文件系统的校验和,一旦发现与原来保存的值有不匹配,说明该文件已经被非法修改,或者是被病毒感染,或者被木马程序替代。TripWire就提供了一个此类应用的典型例子。

更完美的方法是使用"MAC"。"MAC" 是一个与Hash密切相关的名词,即信息鉴权码(Message Authority Code)。它是与密钥相关的Hash值,必须拥有该密钥才能检验该Hash值。文件系统的数字指纹也许会被保存在不可信任的介质上,只对拥有该密钥者提供可鉴别性。并且在文件的数字指纹有可能需要被修改的情况下,只有密钥的拥有者可以计算出新的散列值,而企图破坏文件完整性者却不能得逞。

2) 数字签名 
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。

在这种签名协议中,双方必须事先协商好双方都支持的Hash函数和签名算法。

签名方先对该数据文件进行计算其散列值,然后再对很短的散列值结果--如Md5是16个字节,SHA1是20字节,用非对称算法进行数字签名操作。对方在验证签名时,也是先对该数据文件进行计算其散列值,然后再用非对称算法验证数字签名。

对 Hash 值,又称"数字摘要"进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点:

首先,数据文件本身可以同它的散列值分开保存,签名验证也可以脱离数据文件本身的存在而进行。

再者,有些情况下签名密钥可能与解密密钥是同一个,也就是说,如果对一个数据文件签名,与对其进行非对称的解密操作是相同的操作,这是相当危险的,恶意的破坏者可能将一个试图骗你将其解密的文件,充当一个要求你签名的文件发送给你。因此,在对任何数据文件进行数字签名时,只有对其Hash值进行签名才是安全的。

3) 鉴权协议 
如下的鉴权协议又被称作"挑战--认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。

需要鉴权的一方,向将被鉴权的一方发送随机串(“挑战”),被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后,返还鉴权方,鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较(“认证”),如相同,则可在统计上认为对方拥有该口令字,即通过鉴权。

POP3协议中就有这一应用的典型例子:

S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us> 
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb 
S: +OK maildrop has 1 message (369 octets) 
在上面的一段POP3协议会话中,双方都共享的对称密钥(鉴权口令字)是tanstaaf,服务器发出的挑战是<1896.697170952@dbc.mtview.ca.us>,客户端对挑战的应答是MD5("<1896.697170952@dbc.mtview.ca.us>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb,这个正确的应答使其通过了认证。

 

散列算法长期以来一直在计算机科学中大量应用,随着现代密码学的发展,单向散列函数已经成为信息安全领域中一个重要的结构模块,我们有理由深入研究其设计理论和应用方法。

posted @ 2010-12-02 23:08 eircQ 阅读(405) | 评论 (0)编辑 收藏

原文 http://www.cnblogs.com/finallyliuyu/archive/2010/10/11/1848130.html

一、C++中不能使用random()函数

==================================================================================

本文由青松原创并依GPL-V2及其后续版本发放,转载请注明出处且应包含本行声明。

C++中常用rand()函数生成随机数,但严格意义上来讲生成的只是伪随机数(pseudo-random integral number)。生成随机数时需要我们指定一个种子,如果在程序内循环,那么下一次生成随机数时调用上一次的结果作为种子。但如果分两次执行程序,那么由 于种子相同,生成的“随机数”也是相同的。

在工程应用时,我们一般将系统当前时间(Unix时间)作为种子,这样生成的随机数更接近于实际意义上的随机数。给一下例程如下:

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
    double random(double,double);
    srand(unsigned(time(0)));
    for(int icnt = 0; icnt != 10; ++icnt)
        cout << "No." << icnt+1 << ": " << int(random(0,10))<< endl;
    return 0;
}

double random(double start, double end)
{
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}
/* 运行结果
* No.1: 3
* No.2: 9
* No.3: 0
* No.4: 9
* No.5: 5
* No.6: 6
* No.7: 9
* No.8: 2
* No.9: 9
* No.10: 6
*/
利用这种方法能不能得到完全意义上的随机数呢?似乎9有点多哦?却没有1,4,7?!我们来做一个概率实验,生成1000万个随机数,看0-9这10个数出现的频率是不是大致相同的。程序如下:
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

int main()
{
    double random(double,double);
    int a[10] = {0};
    const int Gen_max = 10000000;
    srand(unsigned(time(0)));
   
    for(int icnt = 0; icnt != Gen_max; ++icnt)
        switch(int(random(0,10)))
        {
        case 0: a[0]++; break;
        case 1: a[1]++; break;
        case 2: a[2]++; break;
        case 3: a[3]++; break;
        case 4: a[4]++; break;
        case 5: a[5]++; break;
        case 6: a[6]++; break;
        case 7: a[7]++; break;
        case 8: a[8]++; break;
        case 9: a[9]++; break;
        default: cerr << "Error!" << endl; exit(-1);
        }
   
    for(int icnt = 0; icnt != 10; ++icnt)
        cout << icnt << ": " << setw(6) << setiosflags(ios::fixed) << setprecision(2) << double(a[icnt])/Gen_max*100 << "%" << endl;
   
    return 0;
}

double random(double start, double end)
{
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}
/* 运行结果
* 0: 10.01%
* 1:   9.99%
* 2:   9.99%
* 3:   9.99%
* 4:   9.98%
* 5: 10.01%
* 6: 10.02%
* 7: 10.01%
* 8: 10.01%
* 9:   9.99%
*/
可知用这种方法得到的随机数是满足统计规律的。

另:在Linux下利用GCC编译程序,即使我执行了1000000次运算,是否将random函数定义了inline函数似乎对程序没有任何影响,有理由相信,GCC已经为我们做了优化。但是冥冥之中我又记得要做inline优化得加O3才行...

不行,于是我们把循环次数改为10亿次,用time命令查看执行时间:
chinsung@gentoo ~/workspace/test/Debug $ time ./test
0: 10.00%
1: 10.00%
2: 10.00%
3: 10.00%
4: 10.00%
5: 10.00%
6: 10.00%
7: 10.00%
8: 10.00%
9: 10.00%

real    2m7.768s
user    2m4.405s
sys     0m0.038s
chinsung@gentoo ~/workspace/test/Debug $ time ./test
0: 10.00%
1: 10.00%
2: 10.00%
3: 10.00%
4: 10.00%
5: 10.00%
6: 10.00%
7: 10.00%
8: 10.00%
9: 10.00%

real    2m7.269s
user    2m4.077s
sys     0m0.025s

前一次为进行inline优化的情形,后一次为没有作inline优化的情形,两次结果相差不大,甚至各项指标后者还要好一些,不知是何缘由...

=================================================================================


     random函数不是ANSI C标准,不能在gcc,vc等编译器下编译通过。 可改用C++下的rand函数来实现。     1、C++标准函数库提供一随机数生成器rand,返回0-RAND_MAX之间均匀分布的伪随机整数。 RAND_MAX必须至少为32767。rand()函数不接受参数,默认以1为种子(即起始值)。 随机数生成器总是以相同的种子开始,所以形成的伪随机数列也相同,失去了随机意义。(但这样便于程序调试)
      2、C++中另一函数srand(),可以指定不同的数(无符号整数变元)为种子。但是如果种子相同,伪随机数列也相同。一个办法是让用户输入种子,但是仍然不理想。
     3、 比较理想的是用变化的数,比如时间来作为随机数生成器的种子。 time的值每时每刻都不同。所以种子不同,所以,产生的随机数也不同。
// C++随机函数(VC program)
#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;
#define MAX 100
int main(int argc, char* argv[])
{        srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面 不然要很长时间等待
   for (int i=0;i<10;i++)
   cout<<rand()%MAX<<endl;//MAX为最大值,其随机域为0~MAX-1
   return 0;
}
二、rand()的用法
     rand()不需要参数,它会返回一个从0到最大随机数的任意整数,最大随机数的大小通常是固定的一个大整数。 这样,如果你要产生0~10的10个整数,可以表达为:
  int N = rand() % 11;
     这样,N的值就是一个0~10的随机数,如果要产生1~10,则是这样:
  int N = 1 + rand() % 10;
  总结来说,可以表示为:
  a + rand() % n
     其中的a是起始值,n是整数的范围。   a + rand() % (b-a+1) 就表示 a~b之间的一个随机数若要0~1的小数,则可以先取得0~10的整数,然后均除以10即可得到随机到十分位的10个随机小数,若要得到随机到百 分位的随机小数,则需要先得到0~100的10个整数,然后均除以100,其它情况依此类推。
     通常rand()产生的随机数在每次运行的时候都是与上一次相同的,这是有意这样设计的,是为了便于程序的调试。若要产生每次不同的随机数,可以使用srand( seed )函数进行随机化,随着seed的不同,就能够产生不同的随机数。
     如大家所说,还可以包含time.h头文件,然后使用srand(time(0))来使用当前时间使随机数发生器随机化,这样就可以保证每两次运行时可以得到不同的随机数序列(只要两次运行的间隔超过1秒)。

posted @ 2010-12-02 08:42 eircQ 阅读(1084) | 评论 (0)编辑 收藏

2010年11月26日 #

文章作者:yx_th000 文章来源:Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 转载请注明,谢谢合作。
关键词:trie trie树 数据结构

    前几天学习了并查集和trie树,这里总结一下trie。
    本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本操作;至于trie树的删除单个节点实在是少见,故在此不做详解。

l        Trie原理

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

l        Trie性质

好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

2.    branch数组的下标代表字符相对于a的相对位置

3.    采用标记的方法确定是否为字符串。

4.    插入、查找的复杂度均为O(len),len为字符串长度

l        Trie的示意图

如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL





l       
Trie
Trie的优点举例

已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

1.    最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

2.    使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

3.    使 用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂 度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为 O(n*len),实际查询的复杂度只是O(len)。


解释一下 hash为什么不能将建立与查询同时执行,例如有串:911,911456输入,如果要同时执行建立与查询,过程就是查询911,没有,然后存入9、 91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能,并不知道911在输入数据中出现过。所以用 hash必须先存入所有子串,然后for循环查询。

而trie树便可 以,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时, 当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀,该思想是我在做pku上的3630中发现的,详见本文配套的“入 门练习”。

l        Trie的简单实现(插入、查询)


 1
 2#include <iostream>
 3using namespace std;
 4
 5const int branchNum = 26//声明常量 
 6int i;
 7
 8struct Trie_node
 9{
10    bool isStr; //记录此处是否构成一个串。
11    Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符
12    Trie_node():isStr(false)
13    {
14        memset(next,NULL,sizeof(next));
15    }

16}
;
17
18class Trie
19{
20public:
21    Trie();
22    void insert(const char* word);
23    bool search(char* word); 
24    void deleteTrie(Trie_node *root);
25private:
26    Trie_node* root;
27}
;
28
29Trie::Trie()
30{
31    root = new Trie_node();
32}

33
34void Trie::insert(const char* word)
35{
36    Trie_node *location = root;
37    while(*word)
38    {
39        if(location->next[*word-'a'== NULL)//不存在则建立
40        {
41            Trie_node *tmp = new Trie_node();
42            location->next[*word-'a'= tmp;
43        }
    
44        location = location->next[*word-'a']; //每插入一步,相当于有一个新串经过,指针要向下移动
45        word++;
46    }

47    location->isStr = true//到达尾部,标记一个串
48}

49
50bool Trie::search(char *word)
51{
52    Trie_node *location = root;
53    while(*word && location)
54    {
55        location = location->next[*word-'a'];
56        word++;
57    }

58    return(location!=NULL && location->isStr);
59}

60
61void Trie::deleteTrie(Trie_node *root)
62{
63    for(i = 0; i < branchNum; i++)
64    {
65        if(root->next[i] != NULL)
66        {
67            deleteTrie(root->next[i]);
68        }

69    }

70    delete root;
71}

72
73void main() //简单测试
74{
75    Trie t;
76    t.insert("a");         
77    t.insert("abandon");
78    char * c = "abandoned";
79    t.insert(c);
80    t.insert("abashed");
81    if(t.search("abashed"))
82        printf("true\n");
83}

posted @ 2010-11-26 09:48 eircQ 阅读(178) | 评论 (0)编辑 收藏

2010年11月8日 #

     摘要: 使用ADO的具体方法 网上关于ADO的使用方法很多,这边我个人就整理出一个使用ADO的方法的具体步骤:1、用#import引入ADO库文件在stdafx.h文件中添加#import "c:\program files\common files\system\ado\msado15.dll"no_namespaces rename("EOF" adoEOF")  2、 数...  阅读全文
posted @ 2010-11-08 13:49 eircQ 阅读(205) | 评论 (0)编辑 收藏

2010年10月11日 #

这两天遇到一个问题,就是运行可执行文件时,出现"can not initialize data binding"错误,原因:

使用DATAGRID控件,除了注册MSDATGRD.OCX外,还需要注册一下MSSTDFMT.DLL才可以。MSSTDFMT.DLL是微软 标准数据格式对象相关动态链接库文件,引用名称为“Microsoft Data Formatting Object Library”,如果在开发程序中有数据绑定,就是通过它对数据格式化后再绑定到控件的。如果用到数据绑定控件,那么就要记得把 MSSTDFMT.DLL加到安装程序里面。

注:有的电脑注册MSDATGRD.OCX、MSSTDFMT.DLL,所以未出现此类情况。

解决方法:

方法一:

程序打包时,将MSDATGRD.OCX、MSSTDFMT.DLL都加载上去。

方法二:

开始-〉运行:

regsvr32   MSDATGRD.OCX

regsvr32   MSSTDFMT.DLL

posted @ 2010-10-11 15:55 eircQ 阅读(539) | 评论 (0)编辑 收藏

2010年9月17日 #

一、 什么是对齐,以及为什么要对齐:
1. 现代计算机中内存空间都是按照byte划分的,从理论上讲似乎对任何类型的变量的访问可以从任何地址开始,但实际情况是在访问特定变量的时候经常在特定的 内存地址访问,这就需要各类型数据按照一定的规则在空间上排列,而不是顺序的一个接一个的排放,这就是对齐。
2. 对齐的作用和原因:各个硬件平台对存储空间的处理上有很大的不同。一些平台对某些特定类型的数据只能从某些特定地址开始存取。其他平台可能没有这种情况, 但是最常见的是如果不按照适合其平台的要求对数据存放进行对齐,会在存取效率上带来损失。比如有些平台每次读都是从偶地址开始,如果一个int型(假设为 32位)如果存放在偶地址开始的地方,那么一个读周期就可以读出,而如果存放在奇地址开始的地方,就可能会需要2个读周期,并对两次读出的结果的高低 字节进行拼凑才能得到该int数据。显然在读取效率上下降很多。这也是空间和时间的博弈。
二、对齐的实现

通常,我们写程序的时候,不需要考虑对齐问题。编译器会替我们选择适合目标平台的对齐策略。当然,我们也可以通知给编译器传递预编译指令而改变对指定数据 的对齐方法。
但是,正因为我们一般不需要关心这个问题,所以因为编辑器对数据存放做了对齐,而我们不了解的话,常常会对一些问题感到迷惑。最常见的就是struct数 据结构的sizeof结果,出乎意料。为此,我们需要对对齐算法所了解。
对齐的算法:
由于各个平台和编译器的不同,现以本人使用的gcc version 3.2.2编译器(32位x86平台)为例子,来讨论编译器对struct数据结构中的各成员如何进行对齐的。
设结构体如下定义:
struct A {
    int a;
    char b;
    short c;
};
结构体A中包含了4字节长度的int一个,1字节长度的char一个和2字节长度的short型数据一个。所以A用到的空间应该是7字节。但是因为编译器 要对数据成员在空间上进行对齐。
所以使用sizeof(strcut A)值为8。
现在把该结构体调整成员变量的顺序。
struct B {
    char b;
    int a;
    short c;
};
这时候同样是总共7个字节的变量,但是sizeof(struct B)的值却是12。
下面我们使用预编译指令#pragma pack (value)来告诉编译器,使用我们指定的对齐值来取代缺省的。
#pragma pack (2) /*指定按2字节对齐*/
struct C {
    char b;
    int a;
    short c;
};
#pragma pack () /*取消指定对齐,恢复缺省对齐*/
sizeof(struct C)值是8。

修改对齐值为1:
#pragma pack (1) /*指定按1字节对齐*/
struct D {
    char b;
    int a;
    short c;
};
#pragma pack () /*取消指定对齐,恢复缺省对齐*/
sizeof(struct D)值为7。

对于char型数据,其自身对齐值为1,对于short型为2,对于int,float,double类型,其自身对齐值为4,单位字节。
这里面有四个概念值:
1)数据类型自身的对齐值:就是上面交代的基本数据类型的自身对齐值。
2)指定对齐值:#pragma pack (value)时的指定对齐值value。
3)结构体或者类的自身对齐值:其成员中自身对齐值最大的那个值。
4)数据成员、结构体和类的有效对齐值:自身对齐值和指定对齐值中较小的那个值。
有了这些值,我们就可以很方便的来讨论具体数据结构的成员和其自身的对齐方式。有效对齐值N是最终用来决定数据存放地址方式的值,最重要。有效对齐N,就 是表示“对齐在N上”,也就是说该数据的"存放起始地址%N=0".而数据结构中的数据变量都是按定义的先后顺序来排放的。第一个数据变量的起始地址就是 数据结构的起始地址。结构体的成员变量要对齐排放,结构体本身也要根据自身的有效对齐值圆整(就是结构体成员变量占用总长度需要是对结构体有效对齐值的整 数倍,结合下面例子理解)。这样就不难理解上面的几个例子的值了。
例子分析:
分析例子B;
struct B {
    char b;
    int a;
    short c;
};
假设B从地址空间0x0000开始排放。该例子中没有定义指定对齐值,在笔者环境下,该值默认为4。第一个成员变量b的自身对齐值是1,比指定或者默认指 定对齐值4小,所以其有效对齐值为1,所以其存放地址0x0000符合0x0000%1=0.第二个成员变量a,其自身对齐值为4,所以有效对齐值也为 4,所以只能存放在起始地址为0x0004到0x0007这四个连续的字节空间中,复核0x0004%4=0,且紧靠第一个变量。第三个变量c,自身对齐 值为2,所以有效对齐值也是2,可以存放在0x0008到0x0009这两个字节空间中,符合0x0008%2=0。所以从0x0000到0x0009存 放的都是B内容。再看数据结构B的自身对齐值为其变量中最大对齐值(这里是b)所以就是4,所以结构体的有效对齐值也是4。根据结构体圆整的要求, 0x0009到0x0000=10字节,(10+2)%4=0。所以0x0000A到0x000B也为结构体B所占用。故B从0x0000到0x000B 共有12个字节,sizeof(struct B)=12;

同理,分析上面例子C:
#pragma pack (2) /*指定按2字节对齐*/
struct C {
    char b;
    int a;
    short c;
};
#pragma pack () /*取消指定对齐,恢复缺省对齐*/
第一个变量b的自身对齐值为1,指定对齐值为2,所以,其有效对齐值为1,假设C从0x0000开始,那么b存放在0x0000,符合0x0000%1= 0;第二个变量,自身对齐值为4,指定对齐值为2,所以有效对齐值为2,所以顺序存放在0x0002、0x0003、0x0004、0x0005四个连续 字节中,符合0x0002%2=0。第三个变量c的自身对齐值为2,所以有效对齐值为2,顺序存放
在0x0006、0x0007中,符合0x0006%2=0。所以从0x0000到0x00007共八字节存放的是C的变量。又C的自身对齐值为4,所以 C的有效对齐值为2。又8%2=0,C只占用0x0000到0x0007的八个字节。所以sizeof(struct C)=8.

有 了以上的解释,相信你对C语言的字节对齐概念应该有了清楚的认识了吧。在网络程序中,掌握这个概念可是很重要的喔,在不同平台之间(比如在Windows 和Linux之间)传递2进制流(比如结构体),那么在这两个平台间必须要定义相同的对齐方式,不然莫名其妙的出了一些错,可是很难排查的哦^_^。
posted @ 2010-09-17 09:49 eircQ 阅读(145) | 评论 (0)编辑 收藏