狂奔的蜗牛

通过计算机成就人生

C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks

2010年6月5日 #

#include <stdio.h>


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

{

int i = p-1;

int x = a[r-1];

for (int j=p; j<r; 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<size;i++)

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

    return 0;

}

posted @ 2010-06-05 16:59 幽梦还乡 阅读(145) | 评论 (0)编辑 收藏

2010年6月1日 #

  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*+ 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 

posted @ 2010-06-01 22:53 幽梦还乡 阅读(105) | 评论 (0)编辑 收藏

#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*+ 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;
}

posted @ 2010-06-01 00:37 幽梦还乡 阅读(214) | 评论 (0)编辑 收藏

2010年5月31日 #

Java中的泛型和C++中的泛型,也就是C++中的模板类和模板函数等等,有着本质的不同.
GJ (Generic Java)是对 Java 语言的一种扩展,是一种带有参数化类型的 Java 语言。用 GJ 编写的程序看起来和普通的 Java 程序基本相同,只不过多了一些参数化的类型同时少了一些类型转换。实际上,这些 GJ 程序也是首先被转化成一般的不带泛型的 Java 程序后再进行处理的,编译器自动完成了从 Generic Java 到普通 Java 的翻译。 
GJ 程序的语法在表面上与 C++ 中的模板非常类似,但是二者之间有着本质的区别。 

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

其 次,在 C++ 模板中,编译器使用提供的类型参数来扩充模板,因此,为 List<A> 生成的 C++ 代码不同于为 List<B> 生成的代码,List<A> 和 List<B> 实际上是两个不同的类。而 Java 中的泛型则以不同的方式实现,编译器仅仅对这些类型参数进行擦除和替换。类型 ArrayList<Integer> 和 ArrayList<String> 的对象共享相同的类,并且只存在一个 ArrayList 类。
posted @ 2010-05-31 15:23 幽梦还乡 阅读(307) | 评论 (0)编辑 收藏

2010年5月27日 #

  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[] = { 35794821 };
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 

posted @ 2010-05-27 22:16 幽梦还乡 阅读(73) | 评论 (0)编辑 收藏

2010年3月3日 #

1.当你include了其他namespace的头文件之后,记得也要相应的引入namespace,否则会出现奇怪的错误!


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

   语法: [函数<要转换的类型>(被转换的变量)]  例如: long l = static_cast<long>(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 关键字 :只声明不定义,也就是不分配存储空间,应该是这个样子的吧?
posted @ 2010-03-03 22:16 幽梦还乡 阅读(83) | 评论 (0)编辑 收藏

2010年1月10日 #


//使用宽字符集,重写了一些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_ */
posted @ 2010-01-10 20:33 幽梦还乡 阅读(1120) | 评论 (0)编辑 收藏

2010年1月9日 #

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
posted @ 2010-01-09 23:20 幽梦还乡 阅读(469) | 评论 (0)编辑 收藏

2009年12月25日 #

很安静的屋子很安静的世界
posted @ 2009-12-25 11:50 幽梦还乡 阅读(82) | 评论 (0)编辑 收藏

2009年12月23日 #

特此庆祝,以后这里就是记录我自学c++点点滴滴的地方
posted @ 2009-12-23 22:53 幽梦还乡 阅读(75) | 评论 (1)编辑 收藏

仅列出标题