博文
明晰C++内存分配的五种方法的区别(转帖)(2006-11-21 14:17:00)
摘要：在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。
自由存储区，就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。
全局/静态存储区，全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量又分为初始化的和未初始化的，在C++里面没有这个区分了，他们共同占用同一块内存区。
常量存储区，这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改（当然，你要通过非正当手段也可以修改，而且方法很多，在《const的思考》一文中，我给出了6种方法）
明确区分堆与栈
在bbs上，堆与栈的区分问题，似乎是一个永恒的话题，由此可见，初学者对此往往是混淆不清的，所以我决定拿他第一个开刀。
首先，我们举一个例子：
void f() { int* p=new int[5]; }
这条短短的一句话就包含了堆与栈，看到new，我们首先就应该想到，我们分配了一块堆内存，那么指针p呢？他分配的是一块栈内存，所以这句话的意思就是：在栈内存中存放了一个指向一块堆内存的指针p。在程序会先确定在堆中分配内存的大小，然后调用operator new分配内存，然后返回这块内存的首地址，放入栈中，他在VC6下的汇编代码如下：
00401028 push 14h
0040102A call operator new (00401060)
0040102F add esp,4
00401032 mov dword ptr [ebp-8],eax
00401035 mov eax,dword ptr [ebp-8]
00401038 mov dword ptr [ebp-4],e......
用空间换时间---对处理大量数据问题的一点思考(2006-11-11 16:36:00)
摘要：题目来自http://acm.pku.edu.cn/JudgeOnline/problem?id=1338，我做了一点小改动。
丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。
给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。
函数接口：unsigned long UglyNumber(int n);
输入输出示例：
n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15；
解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。
本文分析一些建立丑陋数表的方法。
方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。
最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。
代码如下：
#define MAX 500
unsigned long UglyNumber(int n)
{
unsigned long lib[MAX] = {1,};//用来存储丑陋数表
unsigned long i, num;
int k = 1;
for (......
手机拼音输入法头文件和主函数(2006-10-21 20:04:00)
摘要：//*
Name: 手机拼音输入系统头文件
Copyright:
Author:
Date: 20-10-06 07:23
Description:手机拼音输入系统头文件
*/
#define SIZE 500
struct Node{
char data[10];
struct Node *next;
};
typedef struct Node SPELL;
typedef SPELL *LNode;
char *storage[SIZE];
//////////////////////////////////////////////////////////////////////////////////
/*
函数声明：void ReadFile(const char fileName[]);
函数功能：从指定的文件中把所有汉语拼音及对应汉字读入一个指针数组*storage[]（全局变量），
数组的每个元素指向文件中的一行。
输入变量： const char fileName[]，指定的文件名，其中存储了汉字库
输出变量：*storage[]，全局变量，每个元素指向一个包含某拼音组合及其对应汉字的字符串
返回值： 无
*/
void ReadFile(const char fileName[]);
///////////////////////////////////////////////////////////////////////////////
/*
函数声明：void ReadValue(char value[]);
函数功能：读取用户输入的字符串buf，并对其进行适当的转换。
转换规则：先找到结束键'1'，删除结束键之后的字符。
若无结束键'1'，value[i] = '\0';；并结束程序;
然后在buf中逆序查找#号，直......
手机的汉语拼音输入法(2006-10-21 19:58:00)
摘要：系统功能：
手机的汉语拼音输入法很'聪明'，只要用数字键组合，就能够自动找到能组成拼音的字母组合.从2开始分别代表2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz"
键盘布局如图示
+-------+-------+-------+
|1 OK |2 abc |3 def |
+-------+-------+-------+
|4 ghi |5 jkl |6 mno |
+-------+-------+-------+
|7 pqrs |8 tuv |9 wxyz |
+-------+-------+-------+
|#<prep>|0<back>|*<next>|
+-------+-------+-------+
拼音规则：输入时手机有3个状态：
1. 拼音状态： 只接受2至9，和结束键1。按下1则进入状态2，如果候选拼音组合唯一则自动进入状态3（此时拼音不必拼完）；如果无匹配的拼音组合，则一直忽略直到遇到#取消当前拼音。若用户输入非法字符，则自动屏蔽非法字符，只读取合法字符。若只输入结束键1，表示用户选择离开。
2. 选择拼音状态 ： 根据用户输入的数字组合，在屏幕上列出满足条件的拼音组合，每页最多有10个组合，按字母顺序标号由0到9。接受0-9任何一个键则选择对应组合进入状态3。忽略选择不存在组合的位置的数字。接受*则下翻一页。如果已经到达最后一页则忽略*号。接受#则取消当前拼音，并回到状态1。
3. 汉字选择状态： 进入本......
求围圈问题的详细算法和程序集锦(2006-06-24 21:57:00)
摘要：这是以前发在"c语言之家"的一篇文章,今天把它收集到一起来.
17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号。
这个题目的解法很多，我原来就总结了5种，但都不如用数组队列来的简明。
算法如下：
/*求围圈问题的详细算法和程序*/
/*17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a[17]={0};
int front=0, rear=16; //因为数据较小，可令队头元素也占一个实用（有数据域）的空间
int i, count=0; //计数器
for (i = 0;i < 17;i++)
a[i] = i + 1; /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
while ((front%17) != (rear%17))//当队列元素还有一个，注意这里不需要队列为空，而是留一个元素
{
if(++count < 3)//若元素非3的倍数，......
我所理解的插入排序算法(2006-06-20 23:21:00)
摘要：插入排序是一种简单的排序方法，因为的实现比较简单，所以在数据量较少时应用很广泛。插入排序根据其插入的不同方式，可以分为直接插入排序，折半插入排序，2-路插入排序，表插入排序和希尔排序。在这里我将一一写出各种插入排序的算法代码。
直接插入排序
template <class T>
void InsertSort(T a[], int len)
{
int i, j;
T temp;
for (i=1; i<len; i++)
{
temp = a[i];
for (j=i-1; j>=0 && a[j]>temp; j--)//元素后移
a[j+1] = a[j];
a[j+1] = temp; //插入
}<......
我所理解的归并排序算法(2006-06-15 23:24:00)
摘要：归并排序算法以O（nlogn）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。它可以用递归的形式实现，形式简洁易懂。但是需要注意的是当用递归形式时，如果数据较多，则开销很大，实用性很差，所以我们一般采用非递归的形式。我这里两种形式都给出。
不管是递归还是非递归，归并排序算法中基本的操作是合并两个已经排序的数组。
递归形式：
template <class T>
void MSort(T a[], int left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
MSort(a, left, center);
MSort(a, center+1, right);
Merge(a, left, center, right, right-left+1);
}
}
temp......
我所理解的堆排序算法(2006-06-14 10:10:00)
摘要：我所理解的堆排序算法
堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，
这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。
堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，
另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然
如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的
是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。
二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组
中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在
i/2上。
堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，
然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组
的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，
再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，
新得到的数组就是排序后的数组。
template <class T>
void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆，注意保证新二叉堆不越界
{
int i;
for (i=len; i/2>0 && a[i/2]>x; i/=2)
a[i] = a[i/2];
&n......
我所理解的快速排序算法(2006-06-14 10:09:00)
摘要：我所理解的快速排序算法
快速排序是在实践中最快的已知排序算法，它的平均运行时间是O（NlogN）。该算法
之所以特别快，主要是由于非常精练和高度优化的内部循环。在队列中寻找合适的枢点元素，
并按枢点元素划分序列，是快速排序算法的关键。
为简单起见，我这里数组的第一个元素作为枢点元素，重新排列数组，使得枢点元素
之前的元素都小于枢点元素，而枢点元素之后的元素都大于或等于枢点元素。
在这里我提供算法的两种实现：
第一种：
template <class T>
int Parttion(T a[], int low, int high)
{
T x = a[low];
while (low < high)
{
while (low < high && a[high] >= x)
high--;
a[low] = a[high];
while (low < high && a[low] < x)
......
求素数表的3种方法(2006-06-08 09:36:00)
摘要：/*
题目描述：求出N内的所有素数，把他们存储到数组sushu[MAX] 中，并返回素数的个数。
算法描述：在下面的程序中我分别使用了常规方法和新方法求素数表，结果新方法所用时间远小于常规方法。
新方法的思路其实不新，只是利用了一个小技巧：一个正整数如果不能被所有不大于它的平方根的素数整除，则它一定是素数。我在判断正整数i是否为素数时，不是让它去整除每一个不大于它的平方根的正整数，而是让它去整除已经得到的素数表中的素数（此时素数表中的素数比i要小），这样就大大地减少了运算量。
注意：另外还有一种类似桶式排序的方法，是把所要分析的正整数作为布尔数组p[N]的下标，
先给布尔数组p[N]赋初值为true。从i=2开始分析，若p[i]==true，则i的所有倍数j=n*i均为非素数，将以j为下标的元素p[j]==false；直到i==N/2结束分析。
遍历布尔数组p[N]，若若p[i]==true，则表示i为素数，将其存入素数表。
这种方法速度也很快，但它需要设置一个长度为N的布尔数组p[N]，当N很大时，会占用过多内存空间，导致程序不能执行。
*/
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
long Sushu_1(long a[], long n);
long Sushu_2(long a[], long n);
long Sushu_3(long a[], long n);
int main()
{
const long MAX = 150000; //预计素数总的个数
const long......