计算机科学论坛--对数据排序查找实例

// ArithmeticDlg.cpp : implementation file
//
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string>
#include <iostream>

#include "stdafx.h"
#include "Arithmetic.h"
#include "ArithmeticDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
CAboutDlg();

// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA

// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL

// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CArithmeticDlg dialog

CArithmeticDlg::CArithmeticDlg(CWnd* pParent /*=NULL*/)
: CDialog(CArithmeticDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CArithmeticDlg)
m_fdata = _T("");
m_data = _T("");
m_data2 = _T("");
m_find = _T("");
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CArithmeticDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CArithmeticDlg)
DDX_Control(pDX, IDC_BUTTON_MAKE, m_bmake);
DDX_Control(pDX, IDC_BUTTON_CLEARIN, m_clearin);
DDX_Control(pDX, IDC_BUTTON_SORT, m_bsort);
DDX_Control(pDX, IDC_BUTTON_FIND, m_bfind);
DDX_Control(pDX, IDC_BUTTON_CLEAR, m_clear);
DDX_Text(pDX, IDC_EDIT_FIND, m_fdata);
DDX_Text(pDX, IDC_EDIT_DATA, m_data);
DDX_Text(pDX, IDC_EDIT_DATA2, m_data2);
DDX_Text(pDX, IDC_EDIT_DATA3, m_find);
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CArithmeticDlg, CDialog)
//{{AFX_MSG_MAP(CArithmeticDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON_FIND, OnButtonFind)
ON_BN_CLICKED(IDC_BUTTON_SORT, OnButtonSort)
ON_BN_CLICKED(IDC_BUTTON_CLEARIN, OnButtonClear)
ON_BN_CLICKED(IDC_BUTTON_MAKE, OnButtonCreat)
ON_BN_CLICKED(IDC_BUTTON_CLEAR, OnButtonClearAll)
ON_WM_CTLCOLOR()
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CArithmeticDlg message handlers

BOOL CArithmeticDlg::OnInitDialog()
{
CDialog::OnInitDialog();

// Add "About..." menu item to system menu.

// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
  CString strAboutMenu;
  strAboutMenu.LoadString(IDS_ABOUTBOX);
  if (!strAboutMenu.IsEmpty())
  {
   pSysMenu->AppendMenu(MF_SEPARATOR);
   pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
  }
}

// Set the icon for this dialog.  The framework does this automatically
//  when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE);   // Set big icon
SetIcon(m_hIcon, FALSE);  // Set small icon

// TODO: Add extra initialization here

((CBitmapButton *)GetDlgItem(IDC_BUTTON_MAKE))->LoadBitmaps(
  IDB_BITMAP1,
  IDB_BITMAP2,
  IDB_BITMAP2,
  IDB_BITMAP1);
((CBitmapButton *)GetDlgItem(IDC_BUTTON_MAKE))->Invalidate(true);
    ((CBitmapButton *)GetDlgItem(IDC_BUTTON_MAKE))->SizeToContent();

return TRUE; // return TRUE unless you set the focus to a control
}

void CArithmeticDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
  CAboutDlg dlgAbout;
  dlgAbout.DoModal();
}
else
{
  CDialog::OnSysCommand(nID, lParam);
}
}

// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.

void CArithmeticDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting

SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

  // Center icon in client rectangle
  int cxIcon = GetSystemMetrics(SM_CXICON);
  int cyIcon = GetSystemMetrics(SM_CYICON);
  CRect rect;
  GetClientRect(&rect);
  int x = (rect.Width() - cxIcon + 1) / 2;
  int y = (rect.Height() - cyIcon + 1) / 2;

  // Draw the icon
  dc.DrawIcon(x, y, m_hIcon);
}
else
{
  CDialog::OnPaint();
}
}

// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CArithmeticDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}

CSortData::CSortData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CSortData::~CSortData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}

CSortData::CSortData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}

CSortData& CSortData::operator =(CSortData & SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return * this;
}

bool CSortData::operator <(CSortData & data)
{
return m_iIndex < data.m_iIndex;
}

bool CSortData::operator >(CSortData & data)
{
return m_iIndex > data.m_iIndex;
}

template<class T>
void run(T* pData,int left,int right)
{
int i,j;
T middle,iTemp;
i = left;
j = right;

middle = pData[(left+right)/2];
do{
  while((pData[i]<middle) && (i<right))//快速排序
   i++;
  while((pData[j]>middle) && (j>left))
   j--;
  if(i<=j)
  {
   iTemp = pData[i];
   pData[i] = pData[j];
   pData[j] = iTemp;
   i++;
   j--;
  }
}while(i<=j);

if(left<j)
  run(pData,left,j);
if(right>i)
  run(pData,i,right);
}

template<class T>
void QuickSort(T * pData,int Count)
{
run(pData,0,Count-1);
}

void CArithmeticDlg::OnButtonCreat()
{
// TODO: Add your control notification handler code here
int m=0,j=10;
srand( (unsigned)time( NULL ) );
sprintf( buffer,"原始数据：\r\n");
for(int ii = 0;   ii < 100;ii++ )
{
  float mm=rand()/13;
  data[ii] = CSortData(mm,"");//生成100个随机数
  if(ii%10 == 0)
  {
   j += sprintf( buffer+j,"\r\n%d ~ %d -->  ",ii+1,ii+10);
  }
  j  += sprintf( buffer+j,"%d ", data[ii].m_iIndex );
}

m_data = buffer;

UpdateData(FALSE);
}

void CArithmeticDlg::OnButtonSort()//排序
{
// TODO: Add your control notification handler code here
// UpdateData(TRUE);

int jj=10;
QuickSort(data,100);
sprintf( bufferbak,"排序数据：\r\n");
for(int k = 0; k<100; k++ )
{
  if(k%10 == 0)
  {
   jj += sprintf( bufferbak+jj,"\r\n%d ~ %d -->  ",k+1,k+10);
  }
  jj  += sprintf( bufferbak+jj,"%d ", data[k].m_iIndex );
}
m_data2 = bufferbak;
UpdateData(FALSE);
}

void CArithmeticDlg::OnButtonFind()//查找
{
// TODO: Add your control notification handler code here
UpdateData(TRUE);//取屏幕输入数据
char findbuffer[2000];
char fbuffer[2000];
memset(findbuffer,0,2000);
memset(fbuffer,0,2000);
if(m_fdata.IsEmpty()){return;}//判空
if(m_data2.IsEmpty()){return;}//判空
finddata = atoi(m_fdata);
int low = 0,high = 100,mid,q=0,p=10;//折半查找
sprintf( fbuffer,"折半查找：\r\n");
while(low<=high)
{
  mid = (low + high)/2;
  q++;
  if(finddata==data[mid].m_iIndex)
  {
   sprintf( findbuffer,"第 %d 次查找数据成功：%d 为排序数组中第 %d 个数据。" ,q,finddata,mid+1);
   break;
  }
  else if(finddata<data[mid].m_iIndex)
  {
   high = mid-1;
   p += sprintf( fbuffer+p,"\r\n第 %d 次查找： \r\n\r\n查找数据:%d < mid:%d \r\n",q,finddata,data[mid].m_iIndex);
  }
  else
  {
   low = mid+1;
   p += sprintf( fbuffer+p,"\r\n第 %d 次查找： \r\n\r\n查找数据:%d > mid:%d \r\n",q,finddata,data[mid].m_iIndex);
  }
}
if(findbuffer[0]==0x00) sprintf( findbuffer,"查找失败！排序数组中无此数据，请重新输入。");

/* for(int i=101; finddata != data[i].m_iIndex; --i);//顺序查找
if(i<0 || i>100)
{
sprintf( findbuffer,"排序数组中无此数据,请重新输入");
}
else
{
sprintf( findbuffer,"所查找数据：%d 为第 %d个数据。" ,finddata,i+1);
}
*/
m_find = fbuffer;
m_fdata = findbuffer;
UpdateData(FALSE);
}

void CArithmeticDlg::OnButtonClear()
{
// TODO: Add your control notification handler code here
m_fdata.Empty();
UpdateData(FALSE);
}
void CArithmeticDlg::OnButtonClearAll()
{
// TODO: Add your control notification handler code here
m_data.Empty();//清屏
m_data2.Empty();
m_find.Empty();
m_fdata.Empty();
UpdateData(FALSE);
}

HBRUSH CArithmeticDlg::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor)
{
HBRUSH hbr = CDialog::OnCtlColor(pDC, pWnd, nCtlColor);

// TODO: Change any attributes of the DC here
// pDC->SetBkColor(0xff0000);
// pDC->SetTextColor(0x00ff00);
// TODO: Return a different brush if the default is not desired
return hbr;
}

// ArithmeticDlg.h : header file
//

#if !defined(AFX_ARITHMETICDLG_H__61F8DA19_6F91_4A14_AA15_5A5C8EABF28B__INCLUDED_)
#define AFX_ARITHMETICDLG_H__61F8DA19_6F91_4A14_AA15_5A5C8EABF28B__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

/////////////////////////////////////////////////////////////////////////////
// CArithmeticDlg dialog
class CSortData
{
public:
CSortData(int Index,char* strData);
CSortData();
virtual ~CSortData();

int m_iIndex;
int GetDataSize(){return m_iDataSize;};
const char* GetData(){return m_strDatamember;};
CSortData& operator = (CSortData &SrcData);
bool operator < (CSortData & data);
bool operator > (CSortData & data);

private:
char* m_strDatamember;
int m_iDataSize;
};

class CArithmeticDlg : public CDialog
{
// Construction
public:
CArithmeticDlg(CWnd* pParent = NULL); // standard constructor
public:
int sortdata[1000];
int finddata;
CSortData data[1000];
char buffer[1000];
char bufferbak[1000];
// Dialog Data
//{{AFX_DATA(CArithmeticDlg)
enum { IDD = IDD_ARITHMETIC_DIALOG };
CBitmapButton m_bmake;
CBitmapButton m_clearin;
CBitmapButton m_bsort;
CBitmapButton m_bfind;
CBitmapButton m_clear;
CString m_fdata;
CString m_data;
CString m_data2;
CString m_find;
//}}AFX_DATA

// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CArithmeticDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL

// Implementation
protected:
HICON m_hIcon;

// Generated message map functions
//{{AFX_MSG(CArithmeticDlg)
virtual BOOL OnInitDialog();
afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
afx_msg void OnButtonFind();
afx_msg void OnButtonSort();
afx_msg void OnButtonClear();
afx_msg void OnButtonCreat();
afx_msg void OnButtonClearAll();
afx_msg HBRUSH OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor);
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};

//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_ARITHMETICDLG_H__61F8DA19_6F91_4A14_AA15_5A5C8EABF28B__INCLUDED_)


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.750ms