C++博客-狂奔的蜗牛

快速排序算法

幽梦还乡 — Sat, 05 Jun 2010 08:59:00 GMT

#include

int partition(int* a, int p, int r)

{

int i = p-1;

int x = a[r-1];

for (int j=p; j

if (a[j-1] <= x) {

i++;

int temp;

temp = a[j-1];

a[j -1] = a[i-1];

a[i-1] = temp;

}

int temp;

temp = a[i];

a[i] = a[r-1];

a[r-1] = temp;

return i+1;

}

void quick_sort(int* a, int p,int r)

{

if (p < r) {

int q = partition(a, p, r);

quick_sort(a, p, q-1);

quick_sort(a, q+1, r);

}

int main()

{

int a[] = {2,8,5,4,7,9,11,1};

int size = sizeof a / sizeof a[0];

quick_sort(a, 1, size);

printf(" The final result is :");

for(int i=0;i

printf("[%d] ",a[i]);

return 0;

}

幽梦还乡 2010-06-05 16:59 发表评论

修正后的堆排序算法

幽梦还乡 — Tue, 01 Jun 2010 14:53:00 GMT

  1 #include <iostream>
  2 using namespace std;
  3
  4 class suanfa {
  5 public:
  6     int tempsize;
  7     suanfa(int heapsize);
  8     /*将a[i]为根节点的子树生成最大堆!*/
  9     void heapify(int* a, int i);
10     /*获取父节点,在这里没用*/
11     int parent(int i);
12     /*获取左子树,数组序号*/
13     int left(int i);
14     /*获取右子树,数组序号*/
15     int right(int i);
16     /*交换2个值*/
17     void swap(int *a ,int i, int j);
18     /*暂时先不用--日后再用*/
19     void max_heapify(int* a, int heapsize);
20     /*堆排序*/
21     void  heapify_sort(int* a, int size);
22     ~suanfa();
23 };
24 suanfa::suanfa(int heapsize){
25     tempsize = heapsize;
26 }
27 int suanfa::left(int i){
28     return 2*i + 1;
29 }
30 int suanfa::right(int i){
31     return 2*i+2;
32 }
33 int suanfa::parent(int i){
34     return i/2;
35 }
36
37 suanfa::~suanfa(){
38     //delete [] a;
39     //m_array = NULL;
40     cout << "我被析构了" << endl;
41 }
42 void suanfa::heapify(int* a, int i){
43     int l = left(i);
44     int r = right(i);
45     int largest = 0;//以a[i]为根节点的子树的最大值的数组下标
46     int size = tempsize;//heapsize 这里=数组的大小
47     /**获取该子树最大下标*/
48     if (l > size -1) {
49         l = size -1;
50     }
51     if(r > size -1){
52         r = size -1;
53     }
54     if (l <= size - 1  && a[l] > a[i]) {
55         largest = l;
56     }else {
57         largest = r;
58     }
59     if (r <= size - 1 && a[r] > a[largest]) {
60         largest = r;
61     }
62     /*如果根节点不是改子数组最大值,则进行交换*/
63     if (a[i] < a[largest]) {
64         swap(a, i, largest);
65         heapify(a, largest);
66     }
67
68
69 }
70 void suanfa::swap(int* a, int i, int j){
71     int key = a[i];
72     a[i] = a[j];
73     a[j] = key;
74 }
75 void suanfa::max_heapify(int* a, int heapsize){
76     //j->(heapsize-1)/2的子数组是最大堆.
77     for(int j = (heapsize - 1) / 2; j >=0; --j)
78     {
79         heapify(a,j);
80     }
81 }
82 void suanfa::heapify_sort(int* a, int size){
83     max_heapify(a, size);
84     for (int i = size -1; i>0; i--) {
85         swap(a, 0, i);
86         tempsize --;
87         max_heapify(a, tempsize);
88     }
89 }
90 int main () {
91
92     //int a[] = {16,4,10,14};
93     int a[10000];
94     for (int i=0; i<10000; i++) {
95         a[i] = i;
96     }
97     int size = sizeof a / sizeof a[0];
98     suanfa sf(size);
99     //sf.heapify_sort(a, size);
100     //sf.heapify(a, 2);
101     sf.max_heapify(a, size);
102     for (int i=0; i<size; i++) {
103         cout << a[i] << " ";
104     }
105     cout << endl;
106     return 0;
107 }
108

幽梦还乡 2010-06-01 22:53 发表评论

堆排序以及优先级队列 -- 第一步最大堆

幽梦还乡 — Mon, 31 May 2010 16:37:00 GMT

#include <iostream>
using namespace std;

class suanfa {
public:
    /*将a[i]为根节点的子树生成最大堆!*/
    void heapify(int* a, int i);
    /*获取父节点,在这里没用*/
    int parent(int i);
    /*获取左子树,数组序号*/
    int left(int i);
    /*获取右子树,数组序号*/
    int right(int i);
    /*交换2个值*/
    void swap(int *a ,int i, int j);
    /*暂时先不用--日后再用*/
    void max_heapify(int* a, int heapsize);
    ~suanfa();
};
int suanfa::left(int i){
    return 2*i + 1;
}
int suanfa::right(int i){
    return 2*i+2;
}
int suanfa::parent(int i){
    return i/2;
}

suanfa::~suanfa(){
    //delete [] a;
    //m_array = NULL;
    cout << "我被析构了" << endl;
}
void suanfa::heapify(int* a, int i){
    int l = left(i);
    int r = right(i);
    int largest = 0;//以a[i]为根节点的子树的最大值的数组下标
    int size = 10;//heapsize 这里=数组的大小
    /**获取该子树最大下标*/
    if (l <= size - 1  && a[l] > a[i]) {
        largest = l;
    }else {
        largest = r;
    }
    if (r <= size - 1 && a[r] > a[largest]) {
        largest = r;
    }
    /*如果根节点不是改子数组最大值,则进行交换*/
    if (a[i] < a[largest]) {
        swap(a, i, largest);
        heapify(a, largest);
    }


}
void suanfa::swap(int* a, int i, int j){
    int key = a[i];
    a[i] = a[j];
    a[j] = key;
}
void suanfa::max_heapify(int* a, int heapsize){
    //j->(heapsize-1)/2的子数组是最大堆.
    for(int j = (heapsize - 1) / 2; j >=0; --j)
    {
        heapify(a,j);
    }
}
int main () {
    suanfa sf;
    int a[] = {16,4,10,14,7,9,3,2,8,1};
    int size = sizeof a / sizeof a[0];
    for(int j = (size - 1) / 2; j >=0; --j)
    {
        sf.heapify(a,j);
    }
    for (int i=0; i<size; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

幽梦还乡 2010-06-01 00:37 发表评论

Java和C++中的泛型比较

幽梦还乡 — Mon, 31 May 2010 07:23:00 GMT

Java中的泛型和C++中的泛型,也就是C++中的模板类和模板函数等等,有着本质的不同.

GJ （Generic Java）是对 Java 语言的一种扩展，是一种带有参数化类型的 Java 语言。用 GJ 编写的程序看起来和普通的 Java 程序基本相同，只不过多了一些参数化的类型同时少了一些类型转换。实际上，这些 GJ 程序也是首先被转化成一般的不带泛型的 Java 程序后再进行处理的，编译器自动完成了从 Generic Java 到普通 Java 的翻译。

GJ 程序的语法在表面上与 C++ 中的模板非常类似，但是二者之间有着本质的区别。

首先，Java 语言中的泛型不能接受基本类型作为类型参数――它只能接受引用类型。这意味着可以定义 List，但是不可以定义 List。

其次，在 C++ 模板中，编译器使用提供的类型参数来扩充模板，因此，为 List 生成的 C++ 代码不同于为 List 生成的代码，List 和 List 实际上是两个不同的类。而 Java 中的泛型则以不同的方式实现，编译器仅仅对这些类型参数进行擦除和替换。类型 ArrayList 和 ArrayList 的对象共享相同的类，并且只存在一个 ArrayList 类。

幽梦还乡 2010-05-31 15:23 发表评论

一些简单排序

幽梦还乡 — Thu, 27 May 2010 14:16:00 GMT

  1 //============================================================================
  2 // Name        : suanfa.cpp
  3 // Author      : dream
  4 // Version     :
  5 // Copyright   : powered by YeQiangWei
  6 // Description : Hello World in C++, Ansi-style
  7 //============================================================================
  8
  9 #include <iostream>
10 using namespace std;
11 /*默认都安升序排列*/
12 class Algorithm {
13 public:
14     /*分治法*/
15     void merge_sort(int* a, int p, int r);
16     void merge(int* a, int p, int q, int r);
17     /**选择排序*/
18     void select_sort(int* a, int length);
19     /*插入排序*/
20     void insert_sort(int* a, int length);
21     /*冒泡排序*/
22     void bubble_sort(int* a, int length);
23 };
24 void Algorithm::bubble_sort(int* a, int length) {
25     for (int i = 1; i < length; i++) {
26         for (int j = 0; j <= i; j++) {
27             if (a[i] < a[j]) {
28                 int key = a[j];
29                 a[j] = a[i];
30                 a[i] = key;
31             }
32         }
33
34     }
35 }
36 void Algorithm::insert_sort(int* a, int length) {
37     cout << length << endl;
38     for (int i = 1; i < length; i++) {
39         int j = i - 1;
40         int key = a[i];
41         while (j >= 0 && key < a[j]) {
42             a[j + 1] = a[j];
43             j--;
44         }
45         a[j + 1] = key;
46     }
47 }
48 void Algorithm::merge(int* a, int p, int q, int r) {
49     int n1 = q - p + 1;
50     int n2 = r - q;
51     int* L = new int[n1 + 1];
52     int* R = new int[n2 + 1];
53     for (int m = 0; m < n1; m++) {
54         L[m] = a[p + m];
55     }
56     for (int n = 0; n < n2; n++) {
57         R[n] = a[q + n + 1];
58     }
59     int i = 0;
60     int j = 0;
61     for (int k = p; k <= r; k++) {
62         if (L[i] <= R[j]) {
63             a[k] = L[i];
64             i++;
65         } else {
66             a[k] = R[j];
67             j++;
68         }
69     }
70 }
71
72 void Algorithm::merge_sort(int* a, int p, int r) {
73
74     int q = 0;
75     //cout << "这里其实还是执行了的" << q << endl;
76     if (p < r) {
77         q = (p + r) / 2;
78         merge_sort(a, p, q);
79         merge_sort(a, q + 1, r);
80         merge(a, p, q, r);
81     }
82 }
83
84 void Algorithm::select_sort(int* a, int length) {
85     if (NULL == a)
86         return;
87     cout << length << endl;
88     for (int i = 0; i < length; i++) {
89         for (int j = i; j < length; j++) {
90             if (a[i] > a[j]) {
91                 cout << "a[]=" << a[i] << endl;
92                 int key = a[i];
93                 a[i] = a[j];
94                 a[j] = key;
95             }
96         }
97     }
98 }
99
100 int main() {
101     int a[] = { 3, 5, 7, 9, 4, 8, 2, 1 };
102     int length = sizeof(a) / sizeof(a[0]);
103     Algorithm al;
104     al.bubble_sort(a, length);
105     for (size_t i = 0; i < (sizeof(a) / sizeof(a[0])); i++) {
106         cout << a[i] << " ";
107     }
108     return 0;
109 }
110
111
112

幽梦还乡 2010-05-27 22:16 发表评论

作为初学者的一些心得(持续更新)

幽梦还乡 — Wed, 03 Mar 2010 14:16:00 GMT
1.当你include了其他namespace的头文件之后,记得也要相应的引入namespace,否则会出现奇怪的错误!

2. c++的显示类型转换 :

   语法: [函数<要转换的类型>(被转换的变量)] 例如: long l = static_cast(i);//将i转换成long型

    1>. static_cast: 静态类型转换."良性"和"适度良性"转换, 包括不用强制转换,例如自动类型转换.
     2>. const_cast: 常量类型转换: 对"const"和"volatile"进行转换,即把被转换变量转换成const.

3. 如果你想捕获全部异常方法：
      try{
          //这里是可能抛出异常的代码
          }catch（...）{//这里处理异常}

4.陷阱：
当在编写的代码中遇到异常的时候，非常重要的一点是，读者应该问一下，“如果异常发生，程序占用的资源被正确清理了么？” 大多数情况下不必担心，但是如果在一个对象的构造函数执行过程当中抛出异常，那么这个对象的析构函数就不会被调用，因此，编写构造函数的时候，程序员必须特别的仔细。

5.疑问:
uintptr_t vs size_t 二者究竟有什么区别?我用nginx测试过,2种类型都行得通.区别究竟是什么?

6. extern 关键字 :只声明不定义,也就是不分配存储空间,应该是这个样子的吧?

幽梦还乡 2010-03-03 22:16 发表评论

简单工具类

幽梦还乡 — Sun, 10 Jan 2010 12:33:00 GMT

//使用宽字符集，重写了一些string类里面有所欠缺的方法，都是为了忽略大小写而做的。
/*
* Utils.h
*
*  Created on: 2010-1-9
*      Author: dream
*/

#ifndef UTILS_H_
#define UTILS_H_
#include <iostream>
#include <fstream>
#include <string>
#include <cstddef>
/**
*常用工具类
*/
class StringUtil: char_traits<wchar_t> {

public:
    /**
     *将字符串转换成小写
     */
    static const string toLowerCase(string& s) {
        string lower(s);
        for (size_t i = 0; i < s.length(); ++i) {
            lower[i] = tolower(lower[i]);
        }
        return lower;
    }

    /**
     * 将字符串转换成大写
     */
    static const string toUpperCase(string& s) {
        string upper(s);
        for (size_t i = 0; i < s.length(); ++i) {
            upper[i] = toupper(upper[i]);
        }
        return upper;
    }
    /*以下将对一些string类的方法重载，以提供忽略大小写的方法*/
    ///////////////////////////////////////////////////////////////////////

    static const bool eq(wchar_t c1st, wchar_t c2nd) {
        return towupper(c1st) == towupper(c2nd);
    }
    static const bool ne(wchar_t c1st, wchar_t c2nd) {
        return towupper(c1st) == towupper(c2nd);
    }
    static const bool lt(wchar_t c1st, wchar_t c2nd) {
        return towupper(c1st) < towupper(c2nd);
    }

    /**
     *str1 > str2 返回 1
     *str1 < str2 返回 -1
     *str1 = str2 返回 0
     */
    static const int compare(const wchar_t* str1, const wchar_t* str2, size_t n) {
        for (size_t i = 0; i < n; i++) {
            if (str1 == 0) {
                return -1;
            } else if (str2 == 0) {
                return 1;
            } else if (towlower(*str1) < towlower(*str2)) {
                return -1;
            } else if (towlower(*str1) > towlower(*str2)) {
                return 1;
            }
            assert(towlower(*str1) == towlower(*str2));
            ++str1;
            ++str2;

        }
        return 0;
    }

    /**
     * 忽略大小写查找指定字符串，返回的是16进制的值
     *
     * 因为gcc默认使用char或者string类型，所以出入第一个参数的时候需要进行强制类型转换
     *
     * @Param wchar_t* s1 : 待查找的字符串
     * @Param size_t n: 从第N位开始查找
     * @Param wchar_t c:被查找的对象
     */
    static const wchar_t* find(const wchar_t* s1, size_t n, wchar_t c) {
        while (n-- > 0) {
            if (towupper(*s1) == towupper(c))
                return s1;
            else
                ++s1;
        }
        return 0;
    }
};
#endif /* UTILS_H_ */

幽梦还乡 2010-01-10 20:33 发表评论

字符串大小写转换

幽梦还乡 — Sat, 09 Jan 2010 15:20:00 GMT
c++中的string中没有进行大小写字符串转换的功能：

要自己实现其实很简单，方法如下：

1 static const string toLowerCase(string& s) { 2 string lower(s); 3 for (size_t i = 0; i < s.length(); ++i) { 4 lower[i] = tolower(lower[i]); 5 } 6 return lower; 7 } 8 9 static const string toUpperCase(string& s) { 10 string upper(s); 11 for (size_t i = 0; i < s.length(); ++i) { 12 upper[i] = toupper(upper[i]); 13 } 14 return upper; 15 } 16

幽梦还乡 2010-01-09 23:20 发表评论

今天是生蛋节，我准备一个人过

幽梦还乡 — Fri, 25 Dec 2009 03:50:00 GMT
很安静的屋子很安静的世界

幽梦还乡 2009-12-25 11:50 发表评论

今天新开的博客

幽梦还乡 — Wed, 23 Dec 2009 14:53:00 GMT
特此庆祝，以后这里就是记录我自学c++点点滴滴的地方

幽梦还乡 2009-12-23 22:53 发表评论

C++博客-狂奔的蜗牛

快速排序算法

修正后的堆排序算法

堆排序以及优先级队列 -- 第一步 最大堆

Java和C++中的泛型比较

一些简单排序

作为初学者的一些心得(持续更新)

简单工具类

字符串大小写转换

今天是生蛋节，我准备一个人过

今天新开的博客

堆排序以及优先级队列 -- 第一步最大堆