博文
明晰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],eax 这里，我们为了简单并没有释放内存，那么该怎么去释放呢？是delete p么？澳，错了，应该是delete []p，这是为了告诉编译器：我删除的是一个数组，VC6就会根据相应的Cookie信息去进行释放内存的......
用空间换时间---对处理大量数据问题的一点思考(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 500unsigned long UglyNumber(int n){ unsigned long lib[MAX] = {1,};//用来存储丑陋数表 unsigned long i, num; int k = 1; for (i=2; k<MAX; n++) { &n......
手机拼音输入法头文件和主函数(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中逆序查找#号，直到找到#号或遇到buf的第一个元素为止。 若找到#号，则把#号之后的合法字符（数字）复制到value； 若未找到#号，则把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. 汉字选择状态： 进入本状态，如果所选的拼音组合包含对应汉字。则可以选择汉字。否则回到状态1，并且此时不输出任何汉字。每页最多有10个汉......
求围圈问题的详细算法和程序集锦(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; //插入 }} 有些算法把a[0]设置为临时数据......
我所理解的归并排序算法(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); }}template <class T>void MergeSort(T a[]......
我所理解的堆排序算法(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]; a[i] = x;}
template <class T>T DeleteMin(T a[], int le......
我所理解的快速排序算法(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) &nb......
求素数表的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 N = 2000000; //被分析的数的最大值，若执行Sushu_3()，N不能超过1000000 &nb......