C++区联合程序开发

清风

C++是一种十分优秀的语言，它的好处我就不在这里多说了。为了帮助大家更好的应用这们语言。C++区正在尝试联合编写程序。
如果大家有志于将来通过C++找工作，或者已经在工作中应用着这种语言，希望有更多提高。不妨参加我们的活动。一般从参加工作开始，每个人都要经过这样一个过程。先学习公司已有的程序，作最简单的修补。随着知识的积累可以改一些更重要的程序，甚至可以独立写一个feature。水平进一步提高，可以主持开发一个component。最后水平达到公司最高的时候可以成为公司的框架师。负责维护或重新开发整套系统。不是每一个人都能走到这一步。不过在这里，我们希望给大家一个互相学习的机会。给在不同阶段的网友一个在自己基础上进一步提高的机会。
我们这个活动几个月前开始搞，暑假阶段停了几个月。现在希望能继续坚持下去。编程环境选的是VC6.0
由于大家的起点可能不同，我们尽量从简单的开始。最先开始的是一个算法演示的小程序。这个程序还在不断的改进中。独立实现一个算法需要不少VC++/MFC的知识。大家如果觉得这部份知识不够的话可以在VC++区学习，或者先写只用C++的算法实现部份。就像我前面说的，从修修补补开始，逐渐能够实现一个单独的算法，在到能够设计更复杂的框架。
这里编程由于没有时间限制，希望大家尽量把自己的程序写到自己认为最满意的程度。先学的什么知识技巧尽量用上。这也是提高自己水平的必经之路。
希望大家想出更多更好的题目。同时欢迎各高手指点，或帮助设计框架。如果题目不在这个帖子的第一页，我们会把题目的链接放在这里。

■■■■■■

现在正在作的是一个算法演示的程序。源程序如下(更新：09/23)





附件: 只有本站会员才能下载或查看附件，请您 登录 或 注册

夜神君

程序代码：

#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <fstream>
using namespace std;
class Timer
{ clock_t start_time;
public:
Timer(){start_time=clock();}
void elaspe()
/*计算时间*/
{
clock_t end_time=clock();
cout<<"It takes "<<(double)(end_time-start_time)/(double)CLK_TCK<<"seconds\n";
}
/*时间归零*/
void reset(){start_time=clock();}
};
#define maxSortNum 4 /*定义排序算法的个数（种类）*/
class CCompositor
{ int *a;
public:
CCompositor(){a=NULL;}
~CCompositor(){delete []a;}
void FileMenu();
void Initional(int i);
void GetFile(ifstream&is,int size);
void doCompose(int n);
void sort_1();
void sort_2();
void sort_3();
void sort_4();
};
typedef void (CCompositor::*sort)();
sort g_x[] = {CCompositor::sort_1, CCompositor::sort_2, CCompositor::sort_3, CCompositor::sort_4};
struct SortStruct
{ int m_iIndex; //索引
char* m_pChoice; //文件类型
char* m_pFile; //文件路径
int m_iInfoSize; //文件大小
};
SortStruct sortArr[]={
1, " 1. 数据长度20个， 顺序\n", "order20.txt", 20,
2, " 2. 数据长度200个， 顺序\n", "order200.txt", 200,
3, " 3. 数据长度2000个， 顺序\n", "order2000.txt", 2000,
4, " 4. 数据长度20个， 逆序\n", "unOrder20.txt", 20,
5, " 5. 数据长度200个， 逆序\n", "unOrder200.txt", 200,
6, " 6. 数据长度2000个， 逆序\n", "unOrder2000.txt", 2000,
7, " 7. 数据长度20个， 随机\n", "noOrder20.txt", 20,
8, " 8. 数据长度200个， 随机\n", "noOrder200.txt", 200,
9, " 9. 数据长度2000个， 随机\n", "noOrder2000.txt", 2000,
10," 10.数据长度20个， 部分排序\n","partlyOrder20.txt", 20,
11," 11.数据长度200个， 部分排序\n","partlyOrder200.txt", 200,
12," 12.数据长度200个， 部分排序\n","partlyOrder2000.txt", 2000,
};
void CCompositor::sort_1()
{ //增加代码，完成你的算法
}
void CCompositor::sort_2()
{ //增加代码，完成你的算法
}
void CCompositor::sort_3()
{ //增加代码，完成你的算法
}
void CCompositor::sort_4()
{ //增加代码，完成你的算法
}
void CCompositor::GetFile(ifstream&is,int size)
{ //if(!is)exit(1);
delete a;a=NULL;
a=new int[size];
for(int i=0;i<size;i++)
is>>a[i];
}
void CCompositor::FileMenu()
/*列出所有不同类型的数据*/
{ cout<<" 算法比较数据文件目录\n";
cout<<" ——————————————"<<endl;
for (int i=0;i<sizeof(sortArr)/sizeof(SortStruct);i++)
{
cout<<sortArr[i].m_pChoice;
}
cout<<"请选择...";
} void CCompositor::Initional(int i)
/*根据不同的文件数据进行数据加载*/
{ ifstream is;
is.open(sortArr[i-1].m_pFile);
GetFile(is,sortArr[i-1].m_iInfoSize);
is.close();
}
int _tmain(int argc, _TCHAR* argv[])
{ CCompositor compose;
compose.FileMenu();
int choice;cin>>choice;
compose.Initional(choice);
Timer time;
for(int j=0;j<sizeof(g_x)/4;j++)
{
g_x[j];
time.elaspe();
time.reset();
}
return 0;
}


不知道这个有用没

效率比较可以用模板的。

参与的数据也应该是多种

未来的回忆

应该差不多，我把它改成MFC下的，另外算效率的时候我再加上单步演示的算出各种算法各交换多少次。

木子

三个基本排序，这段时间没什么长进，别的还不行。
高效排序明天吧。

1. //end 是超尾
   
2. 
   
3. /*插入排序
   
4. 最好时间复杂度O(n)，最坏时间复杂度O(n^2)，随机序列的复杂度接近后者。*/
   
5. 
   
6. template <class T>
   
7. void insertionsort(T *begin, T *end)
   
8. {
   
9. T *p, *q;
   
10. T tmp;
    
11. for(p=begin+1; p!=end; p++)
    
12. {
    
13. tmp = *p;
    
14. for(q=p; q!=begin && tmp<*(q-1); q--)
    
15. *q = *(q-1);
    
16. *q = tmp;
    
17. }
    
18. }
    
19. /*选择排序
    
20. 最好最坏复杂度都是O(n^2),优点是移动次数较少*/
    
21. 
    
22. template <class T>
    
23. void selectionsort(T *begin, T *end)
    
24. {
    
25. T *p, *q, *least;
    
26. for(p=begin; p!=end-1; p++)
    
27. {
    
28. for(q=p+1,least=p; q!=end; q++)
    
29. if(*q < *least)
    
30. least = q;
    
31. if(p != least)
    
32. swap(*p, *least);
    
33. }
    
34. }
    
35. 
    
36. /*冒泡排序
    
37. 时间复杂度是O(n^2),缺点是移动次数较多，认为是三种基本排序中最差的。*/
    
38. 
    
39. template <class T>
    
40. void bubblesort(T *begin, T *end)
    
41. {
    
42. T *p, *q;
    
43. end--;
    
44. for(p=begin; p!=end; p++)
    
45. for(q=end; q>p; q--)
    
46. if(*q < *(q-1))
    
47. swap(*q, *(q-1));
    
48. }

复制代码

新郎

1. template <class T>
   
2. inline void movedown(T *data, int first, int last)
   
3. {
   
4. int largest = 2*first + 1;
   
5. while(largest <= last)
   
6. {
   
7. if(largest<last && data[largest]<data[largest+1])
   
8. largest++;
   
9. if(data[first] < data[largest])
   
10. {
    
11. swap(data[first], data[largest]);
    
12. first = largest;
    
13. largest = largest*2 + 1;
    
14. }
    
15. else
    
16. break;
    
17. }
    
18. }
    
19. 
    
20. template <class T>
    
21. void heapsort(T *begin, T *end)
    
22. {
    
23. int size = end - begin;
    
24. for(int i=size/2-1; i>=0; i--)
    
25. movedown(begin, i, size-1);
    
26. for(int j=size-1; j>0; j--)
    
27. {
    
28. swap(*begin, *(begin+j));
    
29. movedown(begin, 0, j-1);
    
30. }
    
31. }

复制代码

秋风扫落叶

以下是引用myajax95在2006-9-25 13:52:36的发言：
应该差不多，我把它改成MFC下的，另外算效率的时候我再加上单步演示的算出各种算法各交换多少次。
有没有MFC的变量类型说明, 我一直没分清.

况天佑

myajax：你的那个首页有点问题，比如我双击以后进入hannuo，然后点首页返回，再点一下其他地方，然后再点hannuo就会发现，hannuo上没有焦点。

黒設會

我的关于性能测试的想法

先定义一个基类Action，定义比较，移动的方法，同时有记录的变量。

1. template <class T>
   
2. class Action
   
3. {
   
4. public:
   
5. pair<int,int> result;
   
6. 
   
7. Action() { result.first = 0; result.second = 0; }
   
8. 
   
9. bool lessthan(T &a, T &b)
   
10. {
    
11. result.first++;
    
12. return a < b;
    
13. }
    
14. 
    
15. void move(T &dest, T &source)
    
16. {
    
17. dest = source;
    
18. result.second++;
    
19. }
    
20. 
    
21. void Swap(T &a, T &b)
    
22. {
    
23. swap(a, b);
    
24. result.second += 3;
    
25. }
    
26. };

复制代码

然后每种排序定义为一个由Action派生的类型，其中的比较，移动用基类的方法，如

1. template <class T>
   
2. class InsertionSort : public Action<T>
   
3. {
   
4. void insertionsort(T *begin, T *end)
   
5. {
   
6. T *p, *q;
   
7. T tmp;
   
8. for(p=begin+1; p!=end; p++)
   
9. {
   
10. move(tmp, *p); //--
    
11. for(q=p; q!=begin && lessthan(tmp, *(q-1)); q--) //--
    
12. move(*q, *(q-1)); //--
    
13. move(*q, tmp); //--
    
14. }
    
15. }
    
16. public:
    
17. 
    
18. pair<int,int> operator()(T *begin, T *end)
    
19. {
    
20. Action<T>::result.first = 0;
    
21. Action<T>::result.second = 0;
    
22. insertionsort(begin, end);
    
23. return Action<T>::result;
    
24. }
    
25. 
    
26. };

复制代码

1. template <class T>
   
2. class HeapSort : public Action<T>
   
3. {
   
4. void movedown(T *data, int first, int last)
   
5. {
   
6. int largest = 2*first + 1;
   
7. while(largest <= last)
   
8. {
   
9. if( largest<last && lessthan(data[largest],data[largest+1]) ) //--
   
10. largest++;
    
11. if( lessthan(data[first], data[largest]) ) //--
    
12. {
    
13. Swap(data[first], data[largest]); //--
    
14. first = largest;
    
15. largest = largest*2 + 1;
    
16. }
    
17. else
    
18. break;
    
19. }
    
20. }
    
21. void heapsort(T *begin, T *end)
    
22. {
    
23. int size = end - begin;
    
24. for(int i=size/2-1; i>=0; i--)
    
25. movedown(begin, i, size-1);
    
26. for(int j=size-1; j>0; j--)
    
27. {
    
28. Swap(*begin, *(begin+j)); //--
    
29. movedown(begin, 0, j-1);
    
30. }
    
31. }
    
32. public:
    
33. pair<int,int> operator()(T *begin, T *end)
    
34. {
    
35. Action<T>::result.first = 0;
    
36. Action<T>::result.second = 0;
    
37. heapsort(begin, end);
    
38. return Action<T>::result;
    
39. }
    
40. };

复制代码

我又加了一个函数，这个也许没有必要。

1. template <class T, class U>
   
2. pair<int,int> Test(T *begin, T *end, U func)
   
3. {
   
4. return func(begin, end);
   
5. }

复制代码

测试的主函数，

1. int main()
   
2. {
   
3. const int N = 1000;
   
4. int ar[N], br[N];
   
5. 
   
6. for(int i=0; i<N; i++)
   
7. ar[i] = br[i] = Random::get().random();
   
8. 
   
9. for(int i=0; i<N; i++)
   
10. cout<<ar[i]<<' ';
    
11. cout<<endl;
    
12. 
    
13. pair<int, int> performance = Test(ar, ar+N, HeapSort<int>());
    
14. for(int i=0; i<N; i++)
    
15. cout<<ar[i]<<' ';
    
16. cout<<endl;
    
17. cout<<"\nheapsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;
    
18. 
    
19. performance = Test(br, br+N, InsertionSort<int>());
    
20. for(int i=0; i<N; i++)
    
21. cout<<ar[i]<<' ';
    
22. cout<<endl;
    
23. cout<<"\ninsertionsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;
    
24. cin.get();
    
25. return 0;
    
26. }

复制代码

在 dev cpp编译通过，vc6不知道怎么样。

若叶花吹雪

woodhead可以试着尽量不用T*
这样，很多时候就必须是数组了
比如容器什么的（一些STL容器），就不能用了

还是学着泛型编程上的那样做吧，一般化些。

PS：虽然我也是才开始看这本书，呵呵，不过觉得它上面说的很有道理