久久精品人人做人人爽电影蜜月 ,亚洲国产精品综合久久网络,国内精品久久久久影院亚洲

�q�用计数排序�q�行基数排序

hunter — Thu, 11 Mar 2010 03:08:00 GMT

基数排序是首先按最低有效位数字�q�行排序�Q�以解决卡片排序问题�?br>重复�Ҏ(gu��)��有的d位数字都�q�行排序�Q�仅需要d遍就可以��一堆卡片进行排序�?br>�q�里又运用了基数排序的方法，所以�ȝ��旉��复杂度�ؓ(f��)O(n*d)�?br>

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cmath>
using namespace std;

void CountSort(int a[], int b[],int num,int d)   //计数排序
{
    int* c = new int[10];
    int index;
    for (int i=0;i<=9;i++)
       c[i]=0;
    int size = num;
    for (int j=0;j<size;j++)
    {
        index=a[j]%(int)pow(10.0,d)/(int)pow(10.0,d-1);
        c[index]++;
    }
    //c[i]包含�{�于i的元素个�?/span>
    for (i=1;i<=9;i++)
       c[i]=c[i]+c[i-1];
    //c[i]包含��于�{�于i的元素个�?/span>
    for (j=size-1;j>=0;j--)
    {
        index=a[j]%(int)pow(10.0,d)/(int)pow(10.0,d-1);
        b[c[index]-1]=a[j];
        c[index]--;
    }

    for (j=0;j<size;j++)    //更新一�ơ排序后的a数组
    {
        a[j]=b[j];
    }
        delete [] c;
}

void RadixSort(int a[],int b[],int d,int num)   //基数排序
{
    for(int i=1;i<=d;i++)
        CountSort(a,b,num,i);
}

void main()
{
    int num,d;
    cout<<"输入个数�?qi��ng)位�?/span>"<<endl;
    cin>>num>>d;
    int* a = new int[num];
    int* b = new int[num];
    cout<<"排序前：(x��)"<<endl;
    for(int i=0;i<num;i++)
    {
        cin>>a[i];
    }

    RadixSort(a,b,d,num);

    cout<<"排序后：(x��)"<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<b[j]<<endl;
    }

    delete [] a;
    delete [] b;
}

hunter 2010-03-11 11:08 发表评论

hunter — Wed, 10 Mar 2010 15:36:00 GMT

C语言中判断数据类型长度符
用法
      sizeof(�c�d��说明�W�，数组名或表达�?;
�?br>      sizeof 变量�?br>
1. 定义�Q?br>sizeof是C/C++中的一个操作符�Q�operator�Q�是也，��单的说其作用��是�q�回一个对象或者类型所占的内存字节数�?br>MSDN上的解释为：(x��)
The sizeof keyword gives the amount of storage, in bytes, associated with a variable or a type (including aggregate types). This keyword returns a value of type size_t.
其返回值类型�ؓ(f��)size_t�Q�在头文件stddef.h中定义。这是一个依赖于�~�译�pȝ��的��|��一般定义�ؓ(f��)
typedef unsigned int size_t;
世上�~�译器林林��L��，但作��Z��个规范，它们都会(x��)保证char、signed char和unsigned
char的sizeof��gؓ(f��)1�Q�毕竟char是我们编�E�能用的最��数据类型�?br>2. 语法�Q?br>sizeof有三�U�语法�Ş式，如下�Q?br>1) sizeof( object ); // sizeof( 对象 );
2) sizeof( type_name ); // sizeof( �c�d�� );
3) sizeof object; // sizeof 对象;
所以，
int i;
sizeof( i );  // ok
sizeof i;     // ok
sizeof( int ); // ok
sizeof int;    // error
既然写法3可以用写�?代替�Q��ؓ(f��)求�Ş式统一以及(qi��ng)减少我们大脑的负担，�W?�U�写法，忘掉它吧�Q�实际上�Q�sizeof计算对象的大��也是�{换成对对象类型的计算�Q�也��是��_(d��)��同种�c�d��的不同对象其sizeof值都是一致的。这里，对象可以�q�一步�g伸至表达式，即sizeof可以对一个表辑ּ�求��|��~�译器根据表辑ּ�的最�l�结果类型来��定大小�Q�一般不�?x��)对表达式进行计��。如�Q?br>sizeof( 2 );          // 2的类型�ؓ(f��)int�Q�所以等价于 sizeof( int );
sizeof( 2 + 3.14 );   // 3.14的类型�ؓ(f��)double�Q?也会(x��)被提升成double�c�d��Q�所以等价于 sizef(double)

也可以对一个函数调用求��|��其结果是函数�q�回�c�d��的大��，函数�q�不�?x��)被调用�Q�我们来看一个完整的例子�Q?br>char foo()
{
printf("foo() has been called.\n");
return 'a';
}
int main()
{
size_t sz = sizeof( foo() ); // foo() 的返回值类型�ؓ(f��)char�Q�所以sz = sizeof(char )�Q�foo()�q�不�?x��)被调�?br>printf("sizeof( foo() ) = %d\n", sz);
}
C99标准规定�Q�函数、不能确定类型的表达式以�?qi��ng)位域（bit-field�Q�成员不能被计算sizeof��|��即下面这些写法都是错误的�Q?br>sizeof( foo );// error
void foo2() { }
sizeof( foo2() );// error
struct S
{
       unsigned int f1 : 1;
       unsigned int f2 : 5;
       unsigned int f3 : 12;
};
sizeof( S.f1 );// error
3. sizeof的常量�?br>sizeof的计��发生在�~�译时刻�Q�所以它可以被当作常量表辑ּ�使用�Q�如�Q?br>char ary[ sizeof( int ) * 10 ]; // ok
最新的C99标准规定sizeof也可以在�q�行时刻�q�行计算�Q�如下面的程序在Dev-C++中可以正��执行：(x��)
int n;
n = 10; // n动态赋�?br>char ary[n]; // C99也支持数�l�的动态定�?br>printf("%d\n", sizeof(ary)); // ok. 输出10
但在没有完全实现C99标准的编译器中就行不通了�Q�上面的代码在VC6中就通不�q�编译。所以我们最好还是认为sizeof是在�~�译期执行的�Q�这样不�?x��)带来错误，让程序的可移植性强些�?br>4. 基本数据�c�d��的sizeof
�q�里的基本数据类型指short、int、long、float、double�q�样的简单内�|�数据类型，�׃��它们都是和系�l�相关的�Q�所以在不同的系�l�下取值可能不同，�q�务必引��h��们的注意�Q�尽量不要在�q�方面给自己�E�序的移植造成�ȝ��?br>一般的�Q�在32位编译环境中�Q�sizeof(int)的取��gؓ(f��)4�?br>5. 指针变量的sizeof
学过数据�l�构的你应该知道指针是一个很重要的概念，它记录了另一个对象的地址。既然是来存攑֜�址的，那么它当然等于计��机内部地址�ȝ��的宽度。所以在32位计��机中，一个指针变量的�q�回值必定是4�Q�注意结果是以字节�ؓ(f��)单位�Q�，可以预计�Q�在��来�?4位系�l�中指针变量的sizeof�l�果�?�?br>char* pc = "abc";
int* pi;
string* ps;
char** ppc = &pc;
void (*pf)();// 函数指针
sizeof( pc ); // �l�果�?
sizeof( pi ); // �l�果�?
sizeof( ps ); // �l�果�?
sizeof( ppc ); // �l�果�?
sizeof( pf );// �l�果�?
指针变量的sizeof��g��指针所指的对象没有��M��关系�Q�正是由于所有的指针变量所占内存大��相�{�，所以MFC消息处理函数使用两个参数WPARAM、LPARAM��p��传递各�U�复杂的消息�l�构�Q��用指向结构体的指针）�?br>6. 数组的sizeof
数组的sizeof值等于数�l�所占用的内存字节数�Q�如�Q?br>char a1[] = "abc";
int a2[3];
sizeof( a1 ); // �l�果�?�Q�字�W?末尾�q�存在一个NULL�l�止�W?br>sizeof( a2 ); // �l�果�?*4=12�Q�依赖于int�Q?br>一些朋友刚开始时把sizeof当作了求数组元素的个敎ͼ�现在�Q�你应该知道�q�是不对的，那么应该怎么求数�l�元素的个数呢Easy�Q�通常有下面两�U�写法：(x��)
int c1 = sizeof( a1 ) / sizeof( char ); // 总长�?单个元素的长�?br>int c2 = sizeof( a1 ) / sizeof( a1[0] ); // 总长�?�W�一个元素的长度
写到�q�里�Q�提一问，下面的c3�Q�c4值应该是多少�?br>void foo3(char a3[3])
{
int c3 = sizeof( a3 ); // c3 ==
}
void foo4(char a4[])
{
int c4 = sizeof( a4 ); // c4 ==
}
也许当你试图回答c4的值时已经意识到c3�{�错了，是的�Q�c3!=3。这里函数参数a3已不再是数组�c�d��Q�而是蜕变成指针，相当于char* a3�Q��ؓ(f��)什么仔�l�想惛_��不难明白�Q�我们调用函数foo1�Ӟ��E�序�?x��)在栈上分配一个大��ؓ(f��)3的数�l�吗不会(x��)�Q�数�l�是“传址”的，调用者只需��实参的地址传递过去，所以a3自然为指针类型（char*�Q�，c3的��g��׃ؓ(f��)4�?br>7. �l�构体的sizeof
�q�是初学者问得最多的一个问题，所以这里有必要多费点笔墨。让我们先看一个结构体�Q?br>struct S1
{
char c;
int i;
};
问sizeof(s1)�{�于多少聪明的你开始思考了�Q�char�?个字节，int�?个字节，那么加�v来就应该�?。是�q�样吗你在你机器上试�q�了吗也�怽�是对的，但很可能你是错的�Q�VC6中按默认讄��得到的结果�ؓ(f��)8�?br>Why��Z��么受伤的��L��?br>请不要沮丧，我们来好好琢��一下sizeof的定义——sizeof的结果等于对象或者类型所占的内存字节敎ͼ�好吧�Q�那��p��我们来看看S1的内存分配情况：(x��)
S1 s1 = { 'a', 0xFFFFFFFF };
定义上面的变量后�Q�加上断点，�q�行�E�序�Q�观察s1所在的内存�Q�你发现了什�?br>以我的VC6.0��Z��Q�s1的地址�?x0012FF78�Q�其数据内容如下�Q?br>0012FF78: 61 CC CC CC FF FF FF FF
发现了什么怎么中间�Ҏ(gu��)��?个字节的CC看看MSDN上的说明�Q?br>When applied to a structure type or variable, sizeof returns the actual size, which may include padding bytes inserted for alignment.
原来如此�Q�这��是传说中的字节寚w��啊！一个重要的话题出现了�?br>��Z��么需要字节对齐计��机�l�成原理教导我们�q�样有助于加快计��机的取数速度�Q�否则就得多花指令周期了。�ؓ(f��)此，�~�译器默认会(x��)对结构体�q�行处理�Q�实际上其它地方的数据变量也是如此）�Q�让宽度�?的基本数据类型（short�{�）都位于能�?整除的地址上，让宽度�ؓ(f��)4的基本数据类型（int�{�）都位于能�?整除的地址上，以此�c�L��。这��P��两个��C��间就可能需要加入填充字节，所以整个结构体的sizeof值就增长了�?br>让我们交换一下S1中char与int的位�|�：(x��)
struct S2
{
int i;
char c;
};
看看sizeof(S2)的结果�ؓ(f��)多少�Q�怎么�q�是8再看看内存，原来成员c后面仍然�?个填充字节，�q�又是�ؓ(f��)什么啊别着急，下面�ȝ��规律�?br>字节寚w��的细节和�~�译器实现相养I��但一般而言�Q�满��三个准则：(x��)
1) �l�构体变量的首地址能够被其最宽基本类型成员的大小所整除�Q?br>2) �l�构体每个成员相对于�l�构体首地址的偏�U�量�Q�offset�Q�都是成员大��的整数倍，如有需要编译器�?x��)在成员之间加上填充字节�Q�internal adding�Q�；
3) �l�构体的��d��ؓ(f��)�l�构体最宽基本类型成员大��的整数倍，如有需要编译器�?x��)在最末一个成员之后加上填充字节（trailing padding�Q��?br>对于上面的准则，有几炚w��要说明：(x��)
1) 前面不是说结构体成员的地址是其大小的整数倍，怎么又说到偏�U�量了呢因�ؓ(f��)有了�W?点存在，所以我们就可以只考虑成员的偏�U�量�Q�这��h��考�v来简单。想想�ؓ(f��)什么�?br>�l�构体某个成员相对于�l�构体首地址的偏�U�量可以通过宏offsetof()来获得，�q�个宏也在stddef.h中定义，如下�Q?br>   #define offsetof(s,m) (size_t)&(((s *)0)->m)
例如�Q�想要获得S2中c的偏�U�量�Q�方法�ؓ(f��)
size_t pos = offsetof(S2, c);// pos�{�于4
2) 基本�c�d��是指前面提到的像char、short、int、float、double�q�样的内�|�数据类型，�q�里所说的“数据宽度”��是指其sizeof的大��。由于结构体的成员可以是复合�c�d��Q�比如另外一个结构体�Q�所以在��L��最宽基本类型成员时�Q�应当包括复合类型成员的子成员，而不是把复合成员看成是一个整体。但在确定复合类型成员的偏移位置时则是将复合�c�d��作�ؓ(f��)整体看待�?br>�q�里叙述��h��有点拗口�Q�思考�v来也有点挠头�Q�还是让我们看看例子吧（具体数��g��以VC6��Z��Q�以后不再说明）�Q?br>struct S3
{
char c1;
S1 s;
char c2;
};
S1的最宽简单成员的�c�d��为int�Q�S3在考虑最宽简单类型成员时是将S1“打散”看的�Q�所以S3的最宽简单类型�ؓ(f��)int�Q�这��P��通过S3定义的变量，其存储空间首地址需要被4整除�Q�整个sizeof(S3)的��g��应该�?整除�?br>c1的偏�U�量�?�Q�s的偏�U�量呢这时s是一个整体，它作为结构体变量也满��_��面三个准则，所以其大小�?�Q�偏�U�量�?�Q�c1与s之间侉K��?个填充字节，而c2与s之间��׃��需要了�Q�所以c2的偏�U�量�?2�Q�算上c2的大��ؓ(f��)13�Q?3是不能被4整除的，�q�样末尾�q�得补上3个填充字节。最后得到sizeof(S3)的��gؓ(f��)16�?br>通过上面的叙�q�ͼ�我们可以得到一个公式：(x��)
�l�构体的大小�{�于最后一个成员的偏移量加上其大小再加上末��填充字节数目�Q�即�Q?br>sizeof( struct ) = offsetof( last item ) + sizeof( last item ) + sizeof( trailing padding )
到这里，朋友们应该对�l�构体的sizeof有了一个全新的认识�Q�但不要高兴得太早，有一个媄响sizeof的重要参量还未被提及(qi��ng)�Q�那便是�~�译器的pack指��o(h��)。它是用来调整结构体寚w��方式的，不同�~�译器名�U�和用法略有不同�Q�VC6中通过#pragma pack实现�Q�也可以直接修改/Zp�~�译开兟�?pragma pack的基本用法�ؓ(f��)�Q?pragma pack( n )�Q�n为字节对齐数�Q�其取��gؓ(f��)1�?�?�?�?6�Q�默认是8�Q�如果这个值比�l�构体成员的sizeof值小�Q�那�?br>该成员的偏移量应该以此��gؓ(f��)准，��x��_(d��)��l�构体成员的偏移量应该取二者的最��|��
公式如下�Q?br>offsetof( item ) = min( n, sizeof( item ) )
再看�C�Z��Q?br>#pragma pack(push)   // ��当前pack讄��压栈保存
#pragma pack(2) // 必须在结构体定义之前使用
struct S1
{
char c;
int i;
};
struct S3
{
char c1;
S1 s;
char c2;
};
#pragma pack(pop) // 恢复先前的pack讄��
计算sizeof(S1)�Ӟ��min(2, sizeof(i))的��gؓ(f��)2�Q�所以i的偏�U�量�?�Q�加上sizeof(i)�{�于6�Q�能够被2整除�Q�所以整个S1的大��ؓ(f��)6�?br>同样�Q�对于sizeof(S3)�Q�s的偏�U�量�?�Q�c2的偏�U�量�?�Q�加上sizeof(c2)�{�于9�Q�不能被2整除�Q�添加一个填充字节，所以sizeof(S3)�{�于10�?br>
现在�Q�朋友们可以��L��的出一口气了，:)
�q�有一点要注意�Q?#8220;�I�结构体”�Q�不含数据成员）的大��不�?�Q�而是1。试想一�?#8220;不占�I�间”的变量如何被取地址、两个不同的“�I�结构体”变量又如何得以区分呢于是�Q?#8220;�I�结构体”变量也得被存储，�q�样�~�译器也��只能�ؓ(f��)其分配一个字节的�I�间用于占位了。如下：(x��)
struct S5 { };
sizeof( S5 ); // �l�果�?
8. 含位域结构体的sizeof
前面已经说过�Q�位域成员不能单独被取sizeof��|��我们�q�里要讨论的是含有位域的�l�构体的sizeof�Q�只是考虑到其�Ҏ(gu��)��性而将其专门列了出来�?br>C99规定int、unsigned int和bool可以作�ؓ(f��)位域�c�d��Q�但�~�译器几乎都�Ҏ(gu��)��作了扩展�Q�允许其它类型类型的存在。��用位域的主要目的是压�~�存储，其大致规则�ؓ(f��)�Q?br>1) 如果盔R��位域字段的类型相同，且其位宽之和��于�c�d��的sizeof大小�Q�则后面的字�D�将紧邻前一个字�D�存储，直到不能容纳为止�Q?br>2) 如果盔R��位域字段的类型相同，但其位宽之和大于�c�d��的sizeof大小�Q�则后面的字�D�将从新的存储单元开始，其偏�U�量为其�c�d��大小的整数倍；
3) 如果盔R��的位域字�D늚��c�d��不同�Q�则各编译器的具体实现有差异�Q�VC6采取不压�~�方式，Dev-C++采取压羃方式�Q?br>4) 如果位域字段之间�I�插着非位域字�D�，则不�q�行压羃�Q?br>5) 整个�l�构体的��d��ؓ(f��)最宽基本类型成员大��的整数倍�?br>�q�是让我们来看看例子�?br>�C�Z��1�Q?br>struct BF1
{
char f1 : 3;
char f2 : 4;
char f3 : 5;
};
其内存布局为：(x��)
|_f1__|__f2__|_|____f3___|____|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
0 3 7 8 1316
位域�c�d��为char�Q�第1个字节仅能容�U�下f1和f2�Q�所以f2被压�~�到�W?个字节中�Q�而f3�?br>能从下一个字节开始。因此sizeof(BF1)的结果�ؓ(f��)2�?br>�C�Z��2�Q?br>struct BF2
{
char f1 : 3;
short f2 : 4;
char f3 : 5;
};
�׃��盔R��位域�c�d��不同�Q�在VC6中其sizeof�?�Q�在Dev-C++中�ؓ(f��)2�?br>�C�Z��3�Q?br>struct BF3
{
char f1 : 3;
char f2;
char f3 : 5;
};
非位域字�D늩�插在其中�Q�不�?x��)��生压�~�，在VC6和Dev-C++中得到的大小均�ؓ(f��)3�?br>9. 联合体的sizeof
�l�构体在内存�l�织上是��序式的�Q�联合体则是重叠式，各成员共享一�D�内存，所以整个联合体的sizeof也就是每个成员sizeof的最大倹{��结构体的成员也可以是复合类型，�q�里�Q�复合类型成员是被作为整体考虑的�?br>所以，下面例子中，U的sizeof值等于sizeof(s)�?br>union U
{
int i;
char c;
S1 s;
};

转自�Q?a >http://blog.sina.com.cn/s/blog_5af743940100ctd9.html

hunter 2010-03-10 23:36 发表评论

计数排序

hunter — Wed, 10 Mar 2010 15:29:00 GMT

旉��复杂度�ؓ(f��)O(n).
计数排序的基本思想��是�Ҏ(gu��)��一个输入元素X�Q�确定出��于X的元素个数�?br>有了�q�一信息��可以把X直接攑ֈ�它在最�l�输出数�l�中的位�|�上�?br>例如�Q�如果有17个元素小于X�Q�则X��属于第18个输��Z��|��?br>在计数排序算法的代码中，我们假定输入是个数组A[0...n-1]�Q�length[A]=n。另外还需要两个数�l�：(x��)存放排序�l�果的B[0...n-1]�Q�以�?qi��ng)提供�?f��)时存储区的C[0...k].

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

void CountSort(int a[], int b[],int k,int num)
{
    int* c = new int[k+1];
    for (int i=0;i<=k;i++)
       c[i]=0;
    int size = num;
    for (int j=0;j<size;j++)
       c[a[j]]++;
    //c[i]包含�{�于i的元素个�?/span>
    for (i=1;i<=k;i++)
       c[i]=c[i]+c[i-1];
    //c[i]包含��于�{�于i的元素个�?/span>
    for (j=size-1;j>=0;j--)
    {
        b[c[a[j]]-1]=a[j];
        c[a[j]]--;
    }

        delete [] c;
}
void main()
{
    int num,max;
    cout<<"输入最大整数及(qi��ng)输入个数"<<endl;
    cin>>max;
    cin>>num;
    int* a = new int[num];
    int* b = new int[num];
    cout<<"排序前：(x��)"<<endl;
    for(int i=0;i<num;i++)
    {
        cin>>a[i];
        if (a[i]>max)
            i--;
    }

    CountSort(a,b,max,num);

    cout<<"排序后：(x��)"<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<b[j]<<endl;
    }

    delete [] a;
    delete [] b;
}

hunter 2010-03-10 23:29 发表评论

快速排序及(qi��ng)二分查找

hunter — Tue, 09 Mar 2010 14:05:00 GMT

�l�典的快速排序和二分查找

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

int Partition(int a[],int p,int r)
{
    int ran=rand()%(r-p+1)+p;       //随即选取卫兵
    swap(a[ran],a[r]);
    int x=a[r];
    int i=p-1;
    for (int j=p;j<r;j++)
    {
        if (a[j]<=x)               //��于卫兵的��D��行对�?/span>
        {
            i++;
            swap(a[i],a[j]);
        }
    }
    swap(a[i+1],a[r]);
    return i+1;
}

void QuickSort(int a[],int p,int r)
{
    int q;
    if (p<r)
    {
        q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}

int BinarySearch(int a[],int min,int max,int x)
{
    int mid;
    while (min<max)
    {
        mid=min+(max-min)/2;
        if (a[mid]>=x)
            max=mid;
        else
            min=mid+1;     //若不加一可能存在无限循环的结�?/span>
    }
    if (a[min]==x)
        return min;
    else if(a[max]==x)
        return max;
    else
        return -1;
}
void main()
{
    int num;
    cin>>num;
    int* a = new int[num];
    cout<<"排序前：(x��)"<<endl;
    for(int i=0;i<num;i++)
        cin>>a[i];
    QuickSort(a,0,num-1);
    cout<<"排序后：(x��)"<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<a[j]<<endl;
    }
    cout<<"输入要查扄��?/span>"<<endl;
    int x;
    cin>>x;
    int result=BinarySearch(a,0,num-1,x);
    if (result>=0)
        cout<<"目标位置�?"<<result+1<<endl;
    else
        cout<<"目标不在数组�?/span>"<<endl;
}

hunter 2010-03-09 22:05 发表评论

hunter — Sun, 07 Mar 2010 14:08:00 GMT

《算法导论》中典型的最大堆排序

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

template<class T> void Max_Heap(T a[],int i,int size)
{
    int r = 2*i + 2;
    int l = 2*i + 1;
    int largest;
    if (l<size && a[l]>=a[i])
    {
        largest = l;
    }
    else
        largest = i;
    if (r<size && a[r] >=a[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(a[largest],a[i]);
        Max_Heap(a,largest,size);
    }
}

template<class T> void Build_Max_Heap(T a[],int size)
{
    for (int i=size/2;i>=0;i--)
    {
        Max_Heap(a,i,size);
    }
}

template<class T> void HeapSort(T a[],int size)
{
    Build_Max_Heap(a,size);
    for (int i=size-1;i>=1;i--)
    {
        swap(a[i],a[0]);       //��最大数换到数组末尾
        //show(a,size);
        size--;
        Max_Heap(a,0,size);
    }
}

template<class T> void show(T a[],int size)
{
    cout<<"排序后结果�ؓ(f��)"<<endl;
    for (int i=0;i<size;i++)
    {
        cout<<a[i]<<endl;
    }
}

int main()
{
    int num;
    cin>>num;
    char* input = new char[num];
    for (int i=0;i<num;i++)
    {
        cin>>input[i];
    }

//    Build_Max_Heap(input,num);     //建立最大堆
    HeapSort(input,num);           //堆排�?/span>
    show(input,num);
}

hunter 2010-03-07 22:08 发表评论

BMP文�g�l�构

hunter — Sun, 08 Mar 2009 09:06:00 GMT

1. BMP文�g�l�成

　　BMP文�g由文件头、位图信息头、颜色信息和囑�Ş数据四部分组成。文件头主要包含文�g的大��、文件类型、图像数据偏��L��件头的长度等信息�Q�位图信息头包含图象的尺�怿�息、图像用几个比特数值来表示一个像素、图像是否压�~�、图像所用的颜色数等信息。颜色信息包含图像所用到的颜色表�Q�显�C�图像时需用到�q�个颜色表来生成调色板，但如果图像�ؓ(f��)真彩�Ԍ��既图像的每个像素�?4个比�Ҏ(gu��)��表示�Q�文件中��没有这一块信息，也就不需要操作调色板。文件中的数据块表示囑փ�的相应的像素��|��需要注意的是：(x��)囑փ�的像素值在文�g中的存放��序��Z��左到叻I��从下��C��Q�也��是��_(d��)��在BMP文�g中首先存攄��是图像的最后一行像素，最后才存储囑փ�的第一行像素，但对与同一行的像素�Q�则是按照先左边后右边的的顺序存储的�Q�另外一个需要读者朋友关注的�l�节是：(x��)文�g存储囑փ�的每一行像素值时�Q�如果存储该行像素值所占的字节��Cؓ(f��)4的倍数�Q�则正常存储�Q�否则，需要在后端�?�Q�凑��?的倍数�?

　　2. BMP文�g�?

　　BMP文�g头数据结构含有BMP文�g的类型、文件大��和位图起始位置�{�信息。其�l�构定义如下:

typedef struct tagBITMAPFILEHEADER
{
WORD bfType; // 位图文�g的类型，必须�?#8220;BM”
DWORD bfSize; // 位图文�g的大��，以字节�ؓ(f��)单位
WORD bfReserved1; // 位图文�g保留字，必须�?
WORD bfReserved2; // 位图文�g保留字，必须�?
DWORD bfOffBits; // 位图数据的�v始位�|�，以相对于位图文�g头的偏移量表�C�，以字节�ؓ(f��)单位
} BITMAPFILEHEADER�Q�该�l�构占据14个字节�?

　　3. 位图信息�?

　　BMP位图信息头数据用于说明位囄��寸�{�信息。其�l�构如下�Q?br>
typedef struct tagBITMAPINFOHEADER{
DWORD biSize; // 本结构所占用字节�?br>LONG biWidth; // 位图的宽度，以像素�ؓ(f��)单位
LONG biHeight; // 位图的高度，以像素�ؓ(f��)单位
WORD biPlanes; // 目标讑֤�的��^面数不清�Q�必��Mؓ(f��)1
WORD biBitCount// 每个像素所需的位敎ͼ�必须�?(双色), 4(16�?�Q?(256�?�?4(真彩�?之一
DWORD biCompression; // 位图压羃�c�d��Q�必��L�� 0(不压�~?,1(BI_RLE8压羃�c�d��)�?(BI_RLE4压羃�c�d��)之一
DWORD biSizeImage; // 位图的大��，以字节�ؓ(f��)单位
LONG biXPelsPerMeter; // 位图水��^分��L率，每米像素�?br>LONG biYPelsPerMeter; // 位图垂直分��L率，每米像素�?br>DWORD biClrUsed;// 位图实际使用的颜色表中的颜色�?br>DWORD biClrImportant;// 位图昄��q�程中重要的颜色�?br>} BITMAPINFOHEADER�Q�该�l�构占据40个字节�?

　　注意�Q�对于BMP文�g格式�Q�在处理单色囑փ�和真彩色囑փ�的时候，无论图象数据多么庞大�Q�都不对图象数据�q�行��M��压羃处理�Q�一般情况下�Q�如果位��N��用压�~�格式，那么16色图像采用RLE4压羃��法�Q?56色图像采用RLE8压羃��法�?br>
　　4. 颜色�?

　　颜色表用于说明位图中的颜�Ԍ��它有若干个表��，每一个表��Ҏ(gu��)��一个RGBQUAD�c�d��的结构，定义一�U�颜艌Ӏ�RGBQUAD�l�构的定义如�?

typedef struct tagRGBQUAD {
BYTErgbBlue;// 蓝色的亮�?��D��围�ؓ(f��)0-255)
BYTErgbGreen; // �l�色的亮�?��D��围�ؓ(f��)0-255)
BYTErgbRed; // �U�色的亮�?��D��围�ؓ(f��)0-255)
BYTErgbReserved;// 保留�Q�必��Mؓ(f��)0
} RGBQUAD;

　　颜色表中RGBQUAD�l�构数据的个数由BITMAPINFOHEADER 中的biBitCount��Ҏ(gu��)��定�Q�当biBitCount=1,4,8�Ӟ��分别�?,16,256个颜色表��，当biBitCount=24�Ӟ��囑փ�为真彩色�Q�图像中每个像素的颜色用三个字节表示�Q�分别对应R、G、B��|��囑փ�文�g没有颜色表项。位图信息头和颜色表�l�成位图信息�Q�BITMAPINFO�l�构定义如下:

typedef struct tagBITMAPINFO {
BITMAPINFOHEADER bmiHeader; // 位图信息�?br>RGBQUAD bmiColors[1]; // 颜色�?br>} BITMAPINFO;

　　注意�Q�RGBQUAD数据�l�构中，增加了一个保留字�D�rgbReserved�Q�它不代表�Q何颜�Ԍ��必须取固定的��gؓ(f��)“0”�Q�同�Ӟ��RGBQUAD�l�构中定义的颜色��g��Q�红艌Ӏ�绿色和蓝色的排列顺序与一般真彩色囑փ�文�g的颜色数据排列顺序恰好相反，既：(x��)若某个位图中的一个像素点的颜色的描述�?#8220;00�Q?0�Q�ff�Q?0”�Q�则表示该点为红�Ԍ��而不是蓝艌Ӏ?br>
　　5. 位图数据

　　位图数据记录了位囄��每一个像素值或该对应像素的颜色表的索引��|��囑փ�记录��序是在扫描行内是从左到�?扫描行之间是从下��C��。这�U�格式我们又�U�Cؓ(f��)Bottom_Up位图�Q�当然与之相对的�q�有Up_Down形式的位图，它的记录��序是从上到下的�Q�对于这�U��Ş式的位图�Q�也不存在压�~��Ş式。位囄��一个像素值所占的字节敎ͼ�(x��)当biBitCount=1�Ӟ��8个像素占1个字节；当biBitCount=4�Ӟ��2个像素占1个字节；当biBitCount=8�Ӟ��1个像素占1个字节；当biBitCount=24�?1个像素占3个字节，此时囑փ�为真彩色囑փ�。当囑փ�不是为真彩色�Ӟ��囑փ�文�g中包含颜色表�Q�位囄��数据表示对应像素点在颜色表中相应的烦引��|��当�ؓ(f��)真彩色时�Q�每一个像素用三个字节表示囑փ�相应像素点彩色��|��每个字节分别对应R、G、B分量的��|��q�时候图像文件中没有颜色表。上面我已经讲过了，Windows规定囑փ�文�g中一个扫描行所占的字节数必��L��4的倍数(即以字�ؓ(f��)单位),不��的以0填充�Q�图像文件中一个扫描行所占的字节数计��方法：(x��)

DataSizePerLine= (biWidth* biBitCount+31)/8�Q?/ 一个扫描行所占的字节�?

或�?br> DataSizePerLine= (biWidth* biBitCount+31)/32 * 4�Q?/ 一个扫描行所占的字节�?/strong>

(如果biBitCount == 8 �?4)

DataSizePerLine= (biWidth* 3+3)/4*4�Q?/ 一个扫描行所占的字节�?

�?/p>
DataSizePerLine= (biWidth*1+3)/4*4�Q?/ 一个扫描行所占的字节�?
　　位图数据的大��按下式计算(不压�~�情况下)�Q?br>
　　DataSize= DataSizePerLine* biHeight�?

　　上述是BMP文�g格式的说明，搞清楚了以上的结构，��可以正��的操作囑փ�文�g�Q�对它进行读或写操作了�?br>
转自http://hi.baidu.com/kennlee/blog/item/52375eca63394743f31fe7d8.html

hunter 2009-03-08 17:06 发表评论

ACM 2402 Palindrome Numers

hunter — Sun, 30 Nov 2008 17:28:00 GMT
     摘要: 计算�W�N位的形如12321的可逆数我是先把1位，2位~100位数中各含几个可逆数��出来，计入数组num�Q�然后根据输入的N位置�Q�算��数有几位�Q��ƈ处于什么位�|�。依�ơ通过取整取余得出�l�果。如要求出第24位，因�ؓ(f��)1位数�?位数中各�?个可逆数�Q�所以所要求的数位于3位数中的�W?个先�?对num�?】取��_(d��)��三位数的个数其实��是最高和最低位�?�?�Q�而中间只�?位数的个数加1�Q?�Q�）�Q�取整后�?�Q��?代表�W�一...  阅读全文

hunter 2008-12-01 01:28 发表评论

ACM 2325 Persistent Number 大数盔R��

hunter — Sun, 30 Nov 2008 12:30:00 GMT
1000位的数字�Q�！看来只能输入字符串了。。�?br>
下面是某大大的代码，思�\��是�?�?中找��被N整除的数�Q�然后打印出最��的�l�合

大数盔R��一�D�很值得学习(f��n)�Q?br>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define  MAXCHAR 1002

void Div(char *ch1, char *ch2, char *ch3) {
    char temp[MAXCHAR];
    int i;
    memset(ch3,0,sizeof(ch3));
    int num=ch2[0]-'0';
    int len=strlen(ch1);
    int s=0;
    for(i=0;i<len;i++){       //大数盔R��
        s=s*10+ch1[i]-'0';
        ch3[i]=s/num+'0';
        s%=num;
    }
    int flag=0;
    int j=0;
    for(i=0;i<len;i++){
        if(flag==0&&ch3[i]=='0')
            continue;
        flag=1;
        temp[j]=ch3[i];
        j++;
    }
    temp[j]='\0';
    strcpy(ch3,temp);
}
bool op(char *num,int t){
    int len=strlen(num);
    int i,j,k;
    k=0;
    for(i=0;i<len;i++){
        k=k*10+num[i]-'0';
        k=k%t;
    }
    if(k==0)
        return true;
    else
        return false;
}
int main() {
    char num[MAXCHAR], s[300];
    char temp[MAXCHAR];
    char aaa[MAXCHAR];
    int i, j;
    int ans[10][2];
    while (1) {
        scanf("%s", &num);
        if(num[1]=='\0'){
            printf("1%c\n",num[0]);
            continue;
        }
        memset(ans, 0, sizeof (ans));
        if (num[0] == '-')
            break;
        for (i = 9; i >= 2; i--) {
            s[0]=i+'0';
            s[1]='\0';
            strcpy(temp, num);
            while (1) {
                if (op(temp,i) ) {
                    Div(temp,s,aaa);
                    strcpy(num,aaa);
                    ans[i][0]=1;
                    ans[i][1]++;
                    strcpy(temp,num);
                }
                else
                    break;
            }
            if(num[1]=='\0')
                break;
        }
        if(num[1]!='\0'){
            printf("There is no such number.\n");
            continue;
        }
        ans[num[0]-'0'][0]=1;
        ans[num[0]-'0'][1]++;
        for (i = 2; i < 10; i++) {
            if (ans[i][0] = 1) {
                for (j = 0; j < ans[i][1]; j++)
                    printf("%d", i);
            }
        }
        printf("\n");
    }
    return 0;
}

hunter 2008-11-30 20:30 发表评论

ACM 2316 SPIN

hunter — Sat, 29 Nov 2008 18:44:00 GMT
注意输入时�ƈ不知道有几位。。。有哪位大侠知道在自��q��(sh��)脑上�q�行怎么跛_��循环吗？即scanf==EOF�Q?br>EOF自己输入什么？

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    char input[15];char result[15];
    int len;
    scanf("%s",result);
    while (scanf("%s",input)!=EOF)
    {
        len=strlen(input);

        for (int i=0;i<len;i++)
        {
            result[i]=(result[i]-'0'+input[i]-'0')%10+'0';
        }
    }
    printf("%s",result);
}

hunter 2008-11-30 02:44 发表评论