啥也别说了

看C++和算法,眼泪哗哗的。。。
 
 

常用链接

  • 我的随笔
  • 我的评论
  • 我参与的随笔

留言簿(4)

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  • algorithm(14) (rss)
  • pku/acm(59) (rss)
  • 数字图像(1) (rss)

随笔档案

  • 2010年5月 (1)
  • 2010年3月 (5)
  • 2009年3月 (1)
  • 2008年12月 (1)
  • 2008年11月 (66)

搜索

  •  

最新评论

  • 1. re: ACM 2325 Persistent Number 大数相除
  • 大数相除部分,貌似100/20的结果是错的。
  • --Raise
  • 2. re: 字典树原理(转)
  • 一看就是c++外行写的代码,
  • --ddd
  • 3. re: ACM 1664 放苹果
  • 赞。。新手 看了豁然开朗。.。谢谢了
  • --mokuku
  • 4. re: 字典树原理(转)
  • 代码风格不是很好
  • --ygqwna
  • 5. re: 字典树原理(转)[未登录]
  • 只有new,没有delete,必然内存泄露
  • --123

阅读排行榜

  • 1. 字典树原理(转)(7989)
  • 2. STL 堆排序使用和体会(转)(2089)
  • 3. ACM 2325 Persistent Number 大数相除(1849)
  • 4. 二叉树实例(1737)
  • 5. 大概了解cin,cin.getline,cin.clear,cin.ignore,cin.get()的用法(1626)

评论排行榜

  • 1. 字典树原理(转)(7)
  • 2. ACM 1730 Perfect Pth Powers(3)
  • 3. ACM 1929 Calories from Fat(2)
  • 4. ACM 2316 SPIN(2)
  • 5. ACM 2325 Persistent Number 大数相除(2)

Powered by: 博客园
模板提供:沪江博客
C++博客 | 首页 | 发新随笔 | 发新文章 | 联系 | 聚合 | 管理

2010年5月29日

STL 堆排序使用和体会(转)
STL堆排序其实就是创建一个二叉树,下面是几个常用函数的使用方法和代表的意思
#include
#include
#include
#include
using namespace std;

(1)创建一个数组,并添加数据
    vector v_Arry;
    v_Arry.push_back(5);
    v_Arry.push_back(6);
    v_Arry.push_back(4);
    v_Arry.push_back(8);
    v_Arry.push_back(2);
    v_Arry.push_back(3);
    v_Arry.push_back(7);
    v_Arry.push_back(1);
    v_Arry.push_back(9);
    v_Arry.push_back(10);
    v_Arry.push_back(55);

(2)make_heap(v_Arry.begin(), v_Arry.end(), less()) //建堆(其实就是建二叉树),根节点是最大值,其每一个节点都小于或等于其父节点;使用greater()则相反,根节点是最小值,其每一个节点都大于或等于其父节点

(3)此时可以输出查看一下建好的堆是不是一个标准的二叉树
我的输出结果是:55,10,7,9,6,3,4,1,8,5,2
变成二叉树就是如下:
<!--[if !vml]--><!--[endif]--> <!--[if !vml]--><!--[endif]-->

 

结果不是唯一单一定要满足父节点和子节点的大小关系。
(4)pop_heap(v_Arry.begin(), v_Arry.end());//把根节点移到末尾,并没有删除
     v_Arry.pop_back();//删除该节点
    此时输出结果:10,9,7,8,6,3,4,1,2,5
二叉树如下:

 

(5)v_Arry.push_back(55); //只是添加数据放到子节点
    push_heap(v_Arry.begin(), v_Arry.end());//往二叉树中插入数据,满足子节点小于等于父节点
此时输出结果:55,10,7,8,9,3,4,1,2,5,6
二叉树如下:

 

(6)sort_heap(v_Arry.begin(), v_Arry.end());//对二叉树所有节点进行排序
此时输出结果:1,2,3,4,5,6,7,8,9,10,55

(7)find ( v_Arry.begin(), v_Arry.end(), value );// 从begin到end查找value,若找不到,返回end

原文地址:http://blog.zol.com.cn/1356/article_1355249.html
posted @ 2010-05-29 07:37 hunter 阅读(2089) | 评论 (0) | 编辑 收藏
 

2010年3月11日

运用计数排序进行基数排序
基数排序是首先按最低有效位数字进行排序,以解决卡片排序问题。
重复对所有的d位数字都进行排序,仅需要d遍就可以将一堆卡片进行排序。
这里又运用了基数排序的方法,所以总的时间复杂度为O(n*d)。
#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的元素个数
    for (i=1;i<=9;i++)
       c[i]
=c[i]+c[i-1];
    
//c[i]包含小于等于i的元素个数
    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
<<"输入个数及位数"<<endl;
    cin
>>num>>d;
    
int* a = new int[num];
    
int* b = new int[num];
    cout
<<"排序前:"<<endl;
    
for(int i=0;i<num;i++)
    
{
        cin
>>a[i];
    }

        
    RadixSort(a,b,d,num);

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


    delete [] a;
    delete [] b;
}

posted @ 2010-03-11 11:08 hunter 阅读(508) | 评论 (0) | 编辑 收藏
 

2010年3月10日

sizeof用法(转)

C语言中判断数据类型长度符
用法
      sizeof(类型说明符,数组名或表达式);
或
      sizeof 变量名

1. 定义:
sizeof是C/C++中的一个操作符(operator)是也,简单的说其作用就是返回一个对象或者类型所占的内存字节数。
MSDN上的解释为:
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.
其返回值类型为size_t,在头文件stddef.h中定义。这是一个依赖于编译系统的值,一般定义为
typedef unsigned int size_t;
世上编译器林林总总,但作为一个规范,它们都会保证char、signed char和unsigned
char的sizeof值为1,毕竟char是我们编程能用的最小数据类型。
2. 语法:
sizeof有三种语法形式,如下:
1) sizeof( object ); // sizeof( 对象 );
2) sizeof( type_name ); // sizeof( 类型 );
3) sizeof object; // sizeof 对象;
所以,
int i;
sizeof( i );  // ok
sizeof i;     // ok
sizeof( int ); // ok
sizeof int;    // error
既然写法3可以用写法1代替,为求形式统一以及减少我们大脑的负担,第3种写法,忘掉它吧!实际上,sizeof计算对象的大小也是转换成对对象类型的计算,也就是说,同种类型的不同对象其sizeof值都是一致的。这里,对象可以进一步延伸至表达式,即sizeof可以对一个表达式求值,编译器根据表达式的最终结果类型来确定大小,一般不会对表达式进行计算。如:
sizeof( 2 );          // 2的类型为int,所以等价于 sizeof( int );
sizeof( 2 + 3.14 );   // 3.14的类型为double,2也会被提升成double类型,所以等价于 sizef(double)

也可以对一个函数调用求值,其结果是函数返回类型的大小,函数并不会被调用,我们来看一个完整的例子:
char foo()
{
printf("foo() has been called.\n");
return 'a';
}
int main()
{
size_t sz = sizeof( foo() ); // foo() 的返回值类型为char,所以sz = sizeof(char ),foo()并不会被调用
printf("sizeof( foo() ) = %d\n", sz);
}
C99标准规定,函数、不能确定类型的表达式以及位域(bit-field)成员不能被计算sizeof值,即下面这些写法都是错误的:
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的常量性
sizeof的计算发生在编译时刻,所以它可以被当作常量表达式使用,如:
char ary[ sizeof( int ) * 10 ]; // ok
最新的C99标准规定sizeof也可以在运行时刻进行计算,如下面的程序在Dev-C++中可以正确执行:
int n;
n = 10; // n动态赋值
char ary[n]; // C99也支持数组的动态定义
printf("%d\n", sizeof(ary)); // ok. 输出10
但在没有完全实现C99标准的编译器中就行不通了,上面的代码在VC6中就通不过编译。所以我们最好还是认为sizeof是在编译期执行的,这样不会带来错误,让程序的可移植性强些。
4. 基本数据类型的sizeof
这里的基本数据类型指short、int、long、float、double这样的简单内置数据类型,由于它们都是和系统相关的,所以在不同的系统下取值可能不同,这务必引起我们的注意,尽量不要在这方面给自己程序的移植造成麻烦。
一般的,在32位编译环境中,sizeof(int)的取值为4。
5. 指针变量的sizeof
学过数据结构的你应该知道指针是一个很重要的概念,它记录了另一个对象的地址。既然是来存放地址的,那么它当然等于计算机内部地址总线的宽度。所以在32位计算机中,一个指针变量的返回值必定是4(注意结果是以字节为单位),可以预计,在将来的64位系统中指针变量的sizeof结果为8。
char* pc = "abc";
int* pi;
string* ps;
char** ppc = &pc;
void (*pf)();// 函数指针
sizeof( pc ); // 结果为4
sizeof( pi ); // 结果为4
sizeof( ps ); // 结果为4
sizeof( ppc ); // 结果为4
sizeof( pf );// 结果为4
指针变量的sizeof值与指针所指的对象没有任何关系,正是由于所有的指针变量所占内存大小相等,所以MFC消息处理函数使用两个参数WPARAM、LPARAM就能传递各种复杂的消息结构(使用指向结构体的指针)。
6. 数组的sizeof
数组的sizeof值等于数组所占用的内存字节数,如:
char a1[] = "abc";
int a2[3];
sizeof( a1 ); // 结果为4,字符 末尾还存在一个NULL终止符
sizeof( a2 ); // 结果为3*4=12(依赖于int)
一些朋友刚开始时把sizeof当作了求数组元素的个数,现在,你应该知道这是不对的,那么应该怎么求数组元素的个数呢Easy,通常有下面两种写法:
int c1 = sizeof( a1 ) / sizeof( char ); // 总长度/单个元素的长度
int c2 = sizeof( a1 ) / sizeof( a1[0] ); // 总长度/第一个元素的长度
写到这里,提一问,下面的c3,c4值应该是多少呢
void foo3(char a3[3])
{
int c3 = sizeof( a3 ); // c3 ==
}
void foo4(char a4[])
{
int c4 = sizeof( a4 ); // c4 ==
}
也许当你试图回答c4的值时已经意识到c3答错了,是的,c3!=3。这里函数参数a3已不再是数组类型,而是蜕变成指针,相当于char* a3,为什么仔细想想就不难明白,我们调用函数foo1时,程序会在栈上分配一个大小为3的数组吗不会!数组是“传址”的,调用者只需将实参的地址传递过去,所以a3自然为指针类型(char*),c3的值也就为4。
7. 结构体的sizeof
这是初学者问得最多的一个问题,所以这里有必要多费点笔墨。让我们先看一个结构体:
struct S1
{
char c;
int i;
};
问sizeof(s1)等于多少聪明的你开始思考了,char占1个字节,int占4个字节,那么加起来就应该是5。是这样吗你在你机器上试过了吗也许你是对的,但很可能你是错的!VC6中按默认设置得到的结果为8。
Why为什么受伤的总是我
请不要沮丧,我们来好好琢磨一下sizeof的定义——sizeof的结果等于对象或者类型所占的内存字节数,好吧,那就让我们来看看S1的内存分配情况:
S1 s1 = { 'a', 0xFFFFFFFF };
定义上面的变量后,加上断点,运行程序,观察s1所在的内存,你发现了什么
以我的VC6.0为例,s1的地址为0x0012FF78,其数据内容如下:
0012FF78: 61 CC CC CC FF FF FF FF
发现了什么怎么中间夹杂了3个字节的CC看看MSDN上的说明:
When applied to a structure type or variable, sizeof returns the actual size, which may include padding bytes inserted for alignment.
原来如此,这就是传说中的字节对齐啊!一个重要的话题出现了。
为什么需要字节对齐计算机组成原理教导我们这样有助于加快计算机的取数速度,否则就得多花指令周期了。为此,编译器默认会对结构体进行处理(实际上其它地方的数据变量也是如此),让宽度为2的基本数据类型(short等)都位于能被2整除的地址上,让宽度为4的基本数据类型(int等)都位于能被4整除的地址上,以此类推。这样,两个数中间就可能需要加入填充字节,所以整个结构体的sizeof值就增长了。
让我们交换一下S1中char与int的位置:
struct S2
{
int i;
char c;
};
看看sizeof(S2)的结果为多少,怎么还是8再看看内存,原来成员c后面仍然有3个填充字节,这又是为什么啊别着急,下面总结规律。
字节对齐的细节和编译器实现相关,但一般而言,满足三个准则:
1) 结构体变量的首地址能够被其最宽基本类型成员的大小所整除;
2) 结构体每个成员相对于结构体首地址的偏移量(offset)都是成员大小的整数倍,如有需要编译器会在成员之间加上填充字节(internal adding);
3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍,如有需要编译器会在最末一个成员之后加上填充字节(trailing padding)。
对于上面的准则,有几点需要说明:
1) 前面不是说结构体成员的地址是其大小的整数倍,怎么又说到偏移量了呢因为有了第1点存在,所以我们就可以只考虑成员的偏移量,这样思考起来简单。想想为什么。
结构体某个成员相对于结构体首地址的偏移量可以通过宏offsetof()来获得,这个宏也在stddef.h中定义,如下:
   #define offsetof(s,m) (size_t)&(((s *)0)->m)
例如,想要获得S2中c的偏移量,方法为
size_t pos = offsetof(S2, c);// pos等于4
2) 基本类型是指前面提到的像char、short、int、float、double这样的内置数据类型,这里所说的“数据宽度”就是指其sizeof的大小。由于结构体的成员可以是复合类型,比如另外一个结构体,所以在寻找最宽基本类型成员时,应当包括复合类型成员的子成员,而不是把复合成员看成是一个整体。但在确定复合类型成员的偏移位置时则是将复合类型作为整体看待。
这里叙述起来有点拗口,思考起来也有点挠头,还是让我们看看例子吧(具体数值仍以VC6为例,以后不再说明):
struct S3
{
char c1;
S1 s;
char c2;
};
S1的最宽简单成员的类型为int,S3在考虑最宽简单类型成员时是将S1“打散”看的,所以S3的最宽简单类型为int,这样,通过S3定义的变量,其存储空间首地址需要被4整除,整个sizeof(S3)的值也应该被4整除。
c1的偏移量为0,s的偏移量呢这时s是一个整体,它作为结构体变量也满足前面三个准则,所以其大小为8,偏移量为4,c1与s之间便需要3个填充字节,而c2与s之间就不需要了,所以c2的偏移量为12,算上c2的大小为13,13是不能被4整除的,这样末尾还得补上3个填充字节。最后得到sizeof(S3)的值为16。
通过上面的叙述,我们可以得到一个公式:
结构体的大小等于最后一个成员的偏移量加上其大小再加上末尾的填充字节数目,即:
sizeof( struct ) = offsetof( last item ) + sizeof( last item ) + sizeof( trailing padding )
到这里,朋友们应该对结构体的sizeof有了一个全新的认识,但不要高兴得太早,有一个影响sizeof的重要参量还未被提及,那便是编译器的pack指令。它是用来调整结构体对齐方式的,不同编译器名称和用法略有不同,VC6中通过#pragma pack实现,也可以直接修改/Zp编译开关。#pragma pack的基本用法为:#pragma pack( n ),n为字节对齐数,其取值为1、2、4、8、16,默认是8,如果这个值比结构体成员的sizeof值小,那么
该成员的偏移量应该以此值为准,即是说,结构体成员的偏移量应该取二者的最小值,
公式如下:
offsetof( item ) = min( n, sizeof( item ) )
再看示例:
#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))的值为2,所以i的偏移量为2,加上sizeof(i)等于6,能够被2整除,所以整个S1的大小为6。
同样,对于sizeof(S3),s的偏移量为2,c2的偏移量为8,加上sizeof(c2)等于9,不能被2整除,添加一个填充字节,所以sizeof(S3)等于10。

现在,朋友们可以轻松的出一口气了,:)
还有一点要注意,“空结构体”(不含数据成员)的大小不为0,而是1。试想一个“不占空间”的变量如何被取地址、两个不同的“空结构体”变量又如何得以区分呢于是,“空结构体”变量也得被存储,这样编译器也就只能为其分配一个字节的空间用于占位了。如下:
struct S5 { };
sizeof( S5 ); // 结果为1
8. 含位域结构体的sizeof
前面已经说过,位域成员不能单独被取sizeof值,我们这里要讨论的是含有位域的结构体的sizeof,只是考虑到其特殊性而将其专门列了出来。
C99规定int、unsigned int和bool可以作为位域类型,但编译器几乎都对此作了扩展,允许其它类型类型的存在。使用位域的主要目的是压缩存储,其大致规则为:
1) 如果相邻位域字段的类型相同,且其位宽之和小于类型的sizeof大小,则后面的字段将紧邻前一个字段存储,直到不能容纳为止;
2) 如果相邻位域字段的类型相同,但其位宽之和大于类型的sizeof大小,则后面的字段将从新的存储单元开始,其偏移量为其类型大小的整数倍;
3) 如果相邻的位域字段的类型不同,则各编译器的具体实现有差异,VC6采取不压缩方式,Dev-C++采取压缩方式;
4) 如果位域字段之间穿插着非位域字段,则不进行压缩;
5) 整个结构体的总大小为最宽基本类型成员大小的整数倍。
还是让我们来看看例子。
示例1:
struct BF1
{
char f1 : 3;
char f2 : 4;
char f3 : 5;
};
其内存布局为:
|_f1__|__f2__|_|____f3___|____|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
0 3 7 8 1316
位域类型为char,第1个字节仅能容纳下f1和f2,所以f2被压缩到第1个字节中,而f3只
能从下一个字节开始。因此sizeof(BF1)的结果为2。
示例2:
struct BF2
{
char f1 : 3;
short f2 : 4;
char f3 : 5;
};
由于相邻位域类型不同,在VC6中其sizeof为6,在Dev-C++中为2。
示例3:
struct BF3
{
char f1 : 3;
char f2;
char f3 : 5;
};
非位域字段穿插在其中,不会产生压缩,在VC6和Dev-C++中得到的大小均为3。
9. 联合体的sizeof
结构体在内存组织上是顺序式的,联合体则是重叠式,各成员共享一段内存,所以整个联合体的sizeof也就是每个成员sizeof的最大值。结构体的成员也可以是复合类型,这里,复合类型成员是被作为整体考虑的。
所以,下面例子中,U的sizeof值等于sizeof(s)。
union U
{
int i;
char c;
S1 s;
};


转自:http://blog.sina.com.cn/s/blog_5af743940100ctd9.html

posted @ 2010-03-10 23:36 hunter 阅读(457) | 评论 (0) | 编辑 收藏
 
计数排序
时间复杂度为O(n).
计数排序的基本思想就是对每一个输入元素X,确定出小于X的元素个数。
有了这一信息就可以把X直接放到它在最终输出数组中的位置上。
例如,如果有17个元素小于X,则X就属于第18个输出位置。
在计数排序算法的代码中,我们假定输入是个数组A[0...n-1],length[A]=n。另外还需要两个数组:存放排序结果的B[0...n-1],以及提供临时存储区的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的元素个数
    for (i=1;i<=k;i++)
       c[i]
=c[i]+c[i-1];
    
//c[i]包含小于等于i的元素个数
    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
<<"输入最大整数及输入个数"<<endl;
    cin
>>max;
    cin
>>num;
    
int* a = new int[num];
    
int* b = new int[num];
    cout
<<"排序前:"<<endl;
    
for(int i=0;i<num;i++)
    
{
        cin
>>a[i];
        
if (a[i]>max)
            i
--;
    }

        
    CountSort(a,b,max,num);

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


    delete [] a;
    delete [] b;
}

posted @ 2010-03-10 23:29 hunter 阅读(324) | 评论 (0) | 编辑 收藏
 

2010年3月9日

快速排序及二分查找
经典的快速排序和二分查找
#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)               //小于卫兵的值进行对换
        {
            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;     //若不加一可能存在无限循环的结果
    }

    
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
<<"排序前:"<<endl;
    
for(int i=0;i<num;i++)
        cin
>>a[i];
    QuickSort(a,
0,num-1);
    cout
<<"排序后:"<<endl;
    
for (int j=0;j<num;j++)
    
{
        cout
<<a[j]<<endl;
    }

    cout
<<"输入要查找的数"<<endl;
    
int x;
    cin
>>x;
    
int result=BinarySearch(a,0,num-1,x);
    
if (result>=0)
        cout
<<"目标位置为:"<<result+1<<endl;
    
else
        cout
<<"目标不在数组中"<<endl;
}

posted @ 2010-03-09 22:05 hunter 阅读(693) | 评论 (0) | 编辑 收藏
 

2010年3月7日

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

#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
<<"排序后结果为"<<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);           //堆排序
    show(input,num);
}
posted @ 2010-03-07 22:08 hunter 阅读(261) | 评论 (0) | 编辑 收藏
 

2009年3月8日

BMP文件结构
1. BMP文件组成

  BMP文件由文件头、位图信息头、颜色信息和图形数据四部分组成。文件头主要包含文件的大小、文件类型、图像数据偏离文件头的长度等信息;位图信息头包含图象的尺寸信息、图像用几个比特数值来表示一个像素、图像是否压缩、图像所用的颜色数等信息。颜色信息包含图像所用到的颜色表,显示图像时需用到这个颜色表来生成调色板,但如果图像为真彩色,既图像的每个像素用24个比特来表示,文件中就没有这一块信息,也就不需要操作调色板。文件中的数据块表示图像的相应的像素值,需要注意的是:图像的像素值在文件中的存放顺序为从左到右,从下到上,也就是说,在BMP文件中首先存放的是图像的最后一行像素,最后才存储图像的第一行像素,但对与同一行的像素,则是按照先左边后右边的的顺序存储的;另外一个需要读者朋友关注的细节是:文件存储图像的每一行像素值时,如果存储该行像素值所占的字节数为4的倍数,则正常存储,否则,需要在后端补0,凑足4的倍数。

  2. BMP文件头

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

typedef struct tagBITMAPFILEHEADER
{
WORD bfType; // 位图文件的类型,必须为“BM”
DWORD bfSize; // 位图文件的大小,以字节为单位
WORD bfReserved1; // 位图文件保留字,必须为0
WORD bfReserved2; // 位图文件保留字,必须为0
DWORD bfOffBits; // 位图数据的起始位置,以相对于位图文件头的偏移量表示,以字节为单位
} BITMAPFILEHEADER;该结构占据14个字节。

  3. 位图信息头

  BMP位图信息头数据用于说明位图的尺寸等信息。其结构如下:

typedef struct tagBITMAPINFOHEADER{
DWORD biSize; // 本结构所占用字节数
LONG biWidth; // 位图的宽度,以像素为单位
LONG biHeight; // 位图的高度,以像素为单位
WORD biPlanes; // 目标设备的平面数不清,必须为1
WORD biBitCount// 每个像素所需的位数,必须是1(双色), 4(16色),8(256色)或24(真彩色)之一
DWORD biCompression; // 位图压缩类型,必须是 0(不压缩),1(BI_RLE8压缩类型)或2(BI_RLE4压缩类型)之一
DWORD biSizeImage; // 位图的大小,以字节为单位
LONG biXPelsPerMeter; // 位图水平分辨率,每米像素数
LONG biYPelsPerMeter; // 位图垂直分辨率,每米像素数
DWORD biClrUsed;// 位图实际使用的颜色表中的颜色数
DWORD biClrImportant;// 位图显示过程中重要的颜色数
} BITMAPINFOHEADER;该结构占据40个字节。

  注意:对于BMP文件格式,在处理单色图像和真彩色图像的时候,无论图象数据多么庞大,都不对图象数据进行任何压缩处理,一般情况下,如果位图采用压缩格式,那么16色图像采用RLE4压缩算法,256色图像采用RLE8压缩算法。

  4. 颜色表

  颜色表用于说明位图中的颜色,它有若干个表项,每一个表项是一个RGBQUAD类型的结构,定义一种颜色。RGBQUAD结构的定义如下:

typedef struct tagRGBQUAD {
BYTErgbBlue;// 蓝色的亮度(值范围为0-255)
BYTErgbGreen; // 绿色的亮度(值范围为0-255)
BYTErgbRed; // 红色的亮度(值范围为0-255)
BYTErgbReserved;// 保留,必须为0
} RGBQUAD;

  颜色表中RGBQUAD结构数据的个数由BITMAPINFOHEADER 中的biBitCount项来确定,当biBitCount=1,4,8时,分别有2,16,256个颜色表项,当biBitCount=24时,图像为真彩色,图像中每个像素的颜色用三个字节表示,分别对应R、G、B值,图像文件没有颜色表项。位图信息头和颜色表组成位图信息,BITMAPINFO结构定义如下:

typedef struct tagBITMAPINFO {
BITMAPINFOHEADER bmiHeader; // 位图信息头
RGBQUAD bmiColors[1]; // 颜色表
} BITMAPINFO;

  注意:RGBQUAD数据结构中,增加了一个保留字段rgbReserved,它不代表任何颜色,必须取固定的值为“0”,同时,RGBQUAD结构中定义的颜色值中,红色、绿色和蓝色的排列顺序与一般真彩色图像文件的颜色数据排列顺序恰好相反,既:若某个位图中的一个像素点的颜色的描述为“00,00,ff,00”,则表示该点为红色,而不是蓝色。

  5. 位图数据

  位图数据记录了位图的每一个像素值或该对应像素的颜色表的索引值,图像记录顺序是在扫描行内是从左到右,扫描行之间是从下到上。这种格式我们又称为Bottom_Up位图,当然与之相对的还有Up_Down形式的位图,它的记录顺序是从上到下的,对于这种形式的位图,也不存在压缩形式。位图的一个像素值所占的字节数:当biBitCount=1时,8个像素占1个字节;当biBitCount=4时,2个像素占1个字节;当biBitCount=8时,1个像素占1个字节;当biBitCount=24时,1个像素占3个字节,此时图像为真彩色图像。当图像不是为真彩色时,图像文件中包含颜色表,位图的数据表示对应像素点在颜色表中相应的索引值,当为真彩色时,每一个像素用三个字节表示图像相应像素点彩色值,每个字节分别对应R、G、B分量的值,这时候图像文件中没有颜色表。上面我已经讲过了,Windows规定图像文件中一个扫描行所占的字节数必须是4的倍数(即以字为单位),不足的以0填充,图像文件中一个扫描行所占的字节数计算方法:

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

或者
     
     DataSizePerLine= (biWidth* biBitCount+31)/32 * 4;// 一个扫描行所占的字节数

(如果biBitCount == 8 或24)

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

或

       DataSizePerLine= (biWidth*1+3)/4*4;// 一个扫描行所占的字节数
  位图数据的大小按下式计算(不压缩情况下):

  DataSize= DataSizePerLine* biHeight。

  上述是BMP文件格式的说明,搞清楚了以上的结构,就可以正确的操作图像文件,对它进行读或写操作了。

转自http://hi.baidu.com/kennlee/blog/item/52375eca63394743f31fe7d8.html

posted @ 2009-03-08 17:06 hunter 阅读(569) | 评论 (0) | 编辑 收藏
 

2008年12月1日

ACM 2402 Palindrome Numers
     摘要: 计算第N位的形如12321的可逆数我是先把1位,2位~100位数中各含几个可逆数算出来,计入数组num,然后根据输入的N位置,算出该数有几位,并处于什么位置。依次通过取整取余得出结果。如要求出第24位,因为1位数和2位数中各含9个可逆数,所以所要求的数位于3位数中的第6个先用6对num【1】取整(三位数的个数其实就是最高和最低位从1到9,而中间只是1位数的个数加1(0)),取整后得0,而0代表第一...  阅读全文
posted @ 2008-12-01 01:28 hunter 阅读(454) | 评论 (0) | 编辑 收藏
 

2008年11月30日

ACM 2325 Persistent Number 大数相除
1000位的数字!!看来只能输入字符串了。。。

下面是某大大的代码,思路就是从2到9中找出能被N整除的数,然后打印出最小的组合

大数相那一段很值得学习!
#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++){       //大数相除
        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;
}

posted @ 2008-11-30 20:30 hunter 阅读(1849) | 评论 (2) | 编辑 收藏
 
ACM 2316 SPIN
注意输入时并不知道有几位。。。有哪位大侠知道在自己电脑上运行怎么跳出循环吗?即scanf==EOF?
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);
}


posted @ 2008-11-30 02:44 hunter 阅读(405) | 评论 (2) | 编辑 收藏
 
仅列出标题  下一页