香蕉久久av一区二区三区,久久精品无码专区免费东京热,久久九九亚洲精品

快速排序算法

#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 幽夢還鄉閱讀(379) | 評論 (0) | 編輯收藏

修正后的堆排序算法

  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

posted @ 2010-06-01 22:53 幽夢還鄉閱讀(301) | 評論 (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*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;
}

posted @ 2010-06-01 00:37 幽夢還鄉閱讀(468) | 評論 (0) | 編輯收藏

Java和C++中的泛型比較

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 幽夢還鄉閱讀(675) | 評論 (0) | 編輯收藏

一些簡單排序

  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

posted @ 2010-05-27 22:16 幽夢還鄉閱讀(255) | 評論 (0) | 編輯收藏

作為初學者的一些心得(持續更新)

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 幽夢還鄉閱讀(267) | 評論 (0) | 編輯收藏

簡單工具類

//使用寬字符集，重寫了一些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 幽夢還鄉閱讀(1492) | 評論 (0) | 編輯收藏

字符串大小寫轉換

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 幽夢還鄉閱讀(574) | 評論 (0) | 編輯收藏

今天是生蛋節，我準備一個人過

很安靜的屋子很安靜的世界

posted @ 2009-12-25 11:50 幽夢還鄉閱讀(174) | 評論 (0) | 編輯收藏

今天新開的博客

特此慶祝，以后這里就是記錄我自學c++點點滴滴的地方

posted @ 2009-12-23 22:53 幽夢還鄉閱讀(294) | 評論 (1) | 編輯收藏

狂奔的蝸牛

常用鏈接

留言簿

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜