多線程編程指南

當前流行的Windows操作系統能同時運行幾個程序(獨立運行的程序又稱之為進程)，對于同一個程序，它又可以分成若干個獨立的執行流，我們稱之為線程，線程提供了多任務處理的能力。用進程和線程的觀點來研究軟件是當今普遍采用的方法，進程和線程的概念的出現，對提高軟件的并行性有著重要的意義。現在的大型應用軟件無一不是多線程多任務處理，單線程的軟件是不可想象的。因此掌握多線程多任務設計方法對每個程序員都是必需要掌握的。本實例針對多線程技術在應用中經常遇到的問題，如線程間的通信、同步等，分別進行探討，并利用多線程技術進行線程之間的通信，實現了數字的簡單排序。  

一、 多線程編程指南實現方法

1、理解線程

要講解線程，不得不說一下進程，進程是應用程序的執行實例，每個進程是由私有的虛擬地址空間、代碼、數據和其它系統資源組成。進程在運行時創建的資源隨著進程的終止而死亡。線程的基本思想很簡單，它是一個獨立的執行流，是進程內部的一個獨立的執行單元，相當于一個子程序，它對應于Visual C++中的CwinThread類對象。單獨一個執行程序運行時，缺省地包含的一個主線程，主線程以函數地址的形式出現，提供程序的啟動點，如main（）或WinMain（）函數等。當主線程終止時，進程也隨之終止。根據實際需要，應用程序可以分解成許多獨立執行的線程，每個線程并行的運行在同一進程中。

一個進程中的所有線程都在該進程的虛擬地址空間中，使用該進程的全局變量和系統資源。操作系統給每個線程分配不同的CPU時間片，在某一個時刻，CPU只執行一個時間片內的線程，多個時間片中的相應線程在CPU內輪流執行，由于每個時間片時間很短，所以對用戶來說，仿佛各個線程在計算機中是并行處理的。操作系統是根據線程的優先級來安排CPU的時間，優先級高的線程優先運行，優先級低的線程則繼續等待。

線程被分為兩種：用戶界面線程和工作線程（又稱為后臺線程）。用戶界面線程通常用來處理用戶的輸入并響應各種事件和消息，其實，應用程序的主執行線程CWinAPP對象就是一個用戶界面線程，當應用程序啟動時自動創建和啟動，同樣它的終止也意味著該程序的結束，進程終止。工作線程用來執行程序的后臺處理任務，比如計算、調度、對串口的讀寫操作等，它和用戶界面線程的區別是它不用從CWinThread類派生來創建，對它來說最重要的是如何實現工作線程任務的運行控制函數。工作線程和用戶界面線程啟動時要調用同一個函數的不同版本；最后需要讀者明白的是，一個進程中的所有線程共享它們父進程的變量，但同時每個線程可以擁有自己的變量。 

二、多線程編程指南線程的管理和操作

1、線程的啟動

創建一個用戶界面線程，首先要從類CwinThread產生一個派生類，同時必須使用DECLARE_DYNCREATE和IMPLEMENT_DYNCREATE來聲明和實現這個CwinThread派生類。第二步是根據需要重載該派生類的一些成員函數如：ExitInstance（）、InitInstance（）、OnIdle（）、PreTranslateMessage（）等函數。最后調用AfxBeginThread()函數的一個版本：CWinThread* AfxBeginThread( CRuntimeClass* pThreadClass, int nPriority = THREAD_PRIORITY_NORMAL, UINT nStackSize = 0, DWORD dwCreateFlags = 0, LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL ) 啟動該用戶界面線程，其中第一個參數為指向定義的用戶界面線程類指針變量，第二個參數為線程的優先級，第三個參數為線程所對應的堆棧大小，第四個參數為線程創建時的附加標志，缺省為正常狀態，如為CREATE_SUSPENDED則線程啟動后為掛起狀態。

對于工作線程來說，啟動一個線程，首先需要編寫一個希望與應用程序的其余部分并行運行的函數如Fun1()，接著定義一個指向CwinThread對象的指針變量*pThread,調用AfxBeginThread(Fun1,param,priority)函數，返回值賦給pThread變量的同時一并啟動該線程來執行上面的Fun1（）函數，其中Fun1是線程要運行的函數的名字，也既是上面所說的控制函數的名字，param是準備傳送給線程函數Fun1的任意32位值，priority則是定義該線程的優先級別，它是預定義的常數，讀者可參考MSDN。

2、線程的優先級

以下的CwinThread類的成員函數用于線程優先級的操作：

int GetThreadPriority（）；

BOOL SetThradPriority（）(int nPriority)；

上述的二個函數分別用來獲取和設置線程的優先級，這里的優先級，是相對于該線程所處的優先權層次而言的，處于同一優先權層次的線程，優先級高的線程先運行；處于不同優先權層次上的線程，誰的優先權層次高，誰先運行。至于優先級設置所需的常數，自己參考MSDN就可以了，要注意的是要想設置線程的優先級，這個線程在創建時必須具有THREAD_SET_INFORMATION訪問權限。對于線程的優先權層次的設置，CwinThread類沒有提供相應的函數，但是可以通過Win32 SDK函數GetPriorityClass（）和SetPriorityClass（）來實現。

3、線程的懸掛和恢復

CWinThread類中包含了應用程序懸掛和恢復它所創建的線程的函數，其中SuspendThread（）用來懸掛線程，暫停線程的執行；ResumeThread（）用來恢復線程的執行。如果你對一個線程連續若干次執行SuspendThread（），則需要連續執行相應次的ResumeThread（）來恢復線程的運行。

4、結束線程

終止線程有三種途徑，線程可以在自身內部調用AfxEndThread()來終止自身的運行；可以在線程的外部調用BOOL TerminateThread( HANDLE hThread, DWORD dwExitCode )來強行終止一個線程的運行，然后調用CloseHandle（）函數釋放線程所占用的堆棧；第三種方法是改變全局變量，使線程的執行函數返回，則該線程終止。下面以第三種方法為例，給出部分代碼：

////////////////////////////////////////////////////////////////

//////CtestView message handlers

/////Set to True to end thread

Bool bend=FALSE;//定義的全局變量，用于控制線程的運行；

//The Thread Function；

UINT ThreadFunction(LPVOID pParam)//線程函數

{

while(!bend)

{

Beep(100,100);

Sleep(1000);

}

return 0;

}

/////////////////////////////////////////////////////////////

CwinThread *pThread;

HWND hWnd;

Void CtestView::OninitialUpdate()

{ 

hWnd=GetSafeHwnd();

pThread=AfxBeginThread(ThradFunction,hWnd);//啟動線程

pThread->m_bAutoDelete=FALSE;//線程為手動刪除

Cview::OnInitialUpdate();

}

////////////////////////////////////////////////////////////////

Void CtestView::OnDestroy()

{

bend=TRUE;//改變變量，線程結束

WaitForSingleObject(pThread->m_hThread,INFINITE);//等待線程結束

delete pThread;//刪除線程

Cview::OnDestroy();

} 

三、多線程編程指南線程之間的通信

通常情況下，一個次級線程要為主線程完成某種特定類型的任務，這就隱含著表示在主線程和次級線程之間需要建立一個通信的通道。一般情況下，有下面的幾種方法實現這種通信任務：使用全局變量（上一節的例子其實使用的就是這種方法）、使用事件對象、使用消息。這里我們主要介紹后兩種方法。

1、利用用戶定義的消息通信

在Windows程序設計中，應用程序的每一個線程都擁有自己的消息隊列，甚至工作線程也不例外，這樣一來，就使得線程之間利用消息來傳遞信息就變的非常簡單。首先用戶要定義一個用戶消息，如下所示：#define WM_USERMSG WMUSER+100；在需要的時候，在一個線程中調用：：PostMessage((HWND)param,WM_USERMSG,0,0)或CwinThread::PostThradMessage（）來向另外一個線程發送這個消息，上述函數的四個參數分別是消息將要發送到的目的窗口的句柄、要發送的消息標志符、消息的參數WPARAM和LPARAM。下面的代碼是對上節代碼的修改，修改后的結果是在線程結束時顯示一個對話框，提示線程結束：

UINT ThreadFunction(LPVOID pParam)

{

while(!bend)

{

Beep(100,100);

Sleep(1000);

}

：：PostMessage(hWnd,WM_USERMSG,0,0)；

return 0;

}

////////WM_USERMSG消息的響應函數為OnThreadended(WPARAM wParam,

LPARAM lParam)

LONG CTestView::OnThreadended(WPARAM wParam,LPARAM lParam)

{

AfxMessageBox("Thread ended.");

Retrun 0;

}

上面的例子是工作者線程向用戶界面線程發送消息，對于工作者線程，如果它的設計模式也是消息驅動的，那么調用者可以向它發送初始化、退出、執行某種特定的處理等消息，讓它在后臺完成。在控制函數中可以直接使用：：GetMessage()這個SDK函數進行消息分檢和處理，自己實現一個消息循環。GetMessage()函數在判斷該線程的消息隊列為空時，線程將系統分配給它的時間片讓給其它線程，不無效的占用CPU的時間，如果消息隊列不為空，就獲取這個消息，判斷這個消息的內容并進行相應的處理。

2、用事件對象實現通信

在線程之間傳遞信號進行通信比較復雜的方法是使用事件對象，用MFC的Cevent類的對象來表示。事件對象處于兩種狀態之一：有信號和無信號，線程可以監視處于有信號狀態的事件，以便在適當的時候執行對事件的操作。上述例子代碼修改如下： 

////////////////////////////////////////////////////////////////////

Cevent threadStart ,threadEnd;

UINT ThreadFunction(LPVOID pParam)

{

：：WaitForSingleObject(threadStart.m_hObject,INFINITE);

AfxMessageBox("Thread start.");

while(!bend)

{

Beep(100,100);

Sleep(1000);

Int result=::WaitforSingleObject(threadEnd.m_hObject,0);

//等待threadEnd事件有信號，無信號時線程在這里懸停

If(result==Wait_OBJECT_0)

Bend=TRUE;

}

：：PostMessage(hWnd,WM_USERMSG,0,0)；

return 0;

}

/////////////////////////////////////////////////////////////

Void CtestView::OninitialUpdate()

{ 

hWnd=GetSafeHwnd();

threadStart.SetEvent();//threadStart事件有信號

pThread=AfxBeginThread(ThreadFunction,hWnd);//啟動線程

pThread->m_bAutoDelete=FALSE;

Cview::OnInitialUpdate();

}

////////////////////////////////////////////////////////////////

Void CtestView::OnDestroy()

{

threadEnd.SetEvent();

WaitForSingleObject(pThread->m_hThread,INFINITE);

delete pThread;

Cview::OnDestroy();

}

運行這個程序，當關閉程序時，才顯示提示框，顯示"Thread ended"。 

四、多線程編程指南線程之間的同步

前面我們講過，各個線程可以訪問進程中的公共變量，所以使用多線程的過程中需要注意的問題是如何防止兩個或兩個以上的線程同時訪問同一個數據，以免破壞數據的完整性。保證各個線程可以在一起適當的協調工作稱為線程之間的同步。前面一節介紹的事件對象實際上就是一種同步形式。Visual C++中使用同步類來解決操作系統的并行性而引起的數據不安全的問題，MFC支持的七個多線程的同步類可以分成兩大類：同步對象（CsyncObject、Csemaphore、Cmutex、CcriticalSection和Cevent）和同步訪問對象（CmultiLock和CsingleLock）。本節主要介紹臨界區（critical section）、互斥（mutexe）、信號量（semaphore），這些同步對象使各個線程協調工作，程序運行起來更安全。

1、多線程編程指南臨界區

臨界區是保證在某一個時間只有一個線程可以訪問數據的方法。使用它的過程中，需要給各個線程提供一個共享的臨界區對象，無論哪個線程占有臨界區對象，都可以訪問受到保護的數據，這時候其它的線程需要等待，直到該線程釋放臨界區對象為止，臨界區被釋放后，另外的線程可以強占這個臨界區，以便訪問共享的數據。臨界區對應著一個CcriticalSection對象，當線程需要訪問保護數據時，調用臨界區對象的Lock()成員函數；當對保護數據的操作完成之后，調用臨界區對象的Unlock()成員函數釋放對臨界區對象的擁有權，以使另一個線程可以奪取臨界區對象并訪問受保護的數據。同時啟動兩個線程，它們對應的函數分別為WriteThread()和ReadThread()，用以對公共數組組array[]操作，下面的代碼說明了如何使用臨界區對象：

#include "afxmt.h"

int array[10],destarray[10];

CCriticalSection Section;

UINT WriteThread(LPVOID param)

{

Section.Lock();

for(int x=0;x<10;x++)

array[x]=x;

Section.Unlock();

}

UINT ReadThread(LPVOID param)

{

Section.Lock();

For(int x=0;x<10;x++)

Destarray[x]=array[x];

Section.Unlock();

}

上述代碼運行的結果應該是Destarray數組中的元素分別為1-9，而不是雜亂無章的數，如果不使用同步，則不是這個結果，有興趣的讀者可以實驗一下。

2、多線程編程指南互斥

互斥與臨界區很相似，但是使用時相對復雜一些，它不僅可以在同一應用程序的線程間實現同步，還可以在不同的進程間實現同步，從而實現資源的安全共享。互斥與Cmutex類的對象相對應，使用互斥對象時，必須創建一個CSingleLock或CMultiLock對象，用于實際的訪問控制，因為這里的例子只處理單個互斥，所以我們可以使用CSingleLock對象，該對象的Lock()函數用于占有互斥，Unlock()用于釋放互斥。實現代碼如下：

#include "afxmt.h"

int array[10],destarray[10];

CMutex Section;

UINT WriteThread(LPVOID param)

{

CsingleLock singlelock;

singlelock (&Section);

singlelock.Lock();

for(int x=0;x<10;x++)

array[x]=x;

singlelock.Unlock();

}

UINT ReadThread(LPVOID param)

{

CsingleLock singlelock;

singlelock (&Section);

singlelock.Lock();

For(int x=0;x<10;x++)

Destarray[x]=array[x];

singlelock.Unlock();

}

3、多線程編程指南信號量

信號量的用法和互斥的用法很相似，不同的是它可以同一時刻允許多個線程訪問同一個資源，創建一個信號量需要用Csemaphore類聲明一個對象，一旦創建了一個信號量對象，就可以用它來對資源的訪問技術。要實現計數處理，先創建一個CsingleLock或CmltiLock對象，然后用該對象的Lock()函數減少這個信號量的計數值，Unlock()反之。下面的代碼分別啟動三個線程，執行時同時顯示二個消息框，然后10秒后第三個消息框才得以顯示。

/////////////////////////////////////////////////////////////////////////

Csemaphore *semaphore;

Semaphore=new Csemaphore(2,2);

HWND hWnd=GetSafeHwnd();

AfxBeginThread(threadProc1,hWnd);

AfxBeginThread(threadProc2,hWnd);

AfxBeginThread(threadProc3,hWnd);

UINT ThreadProc1(LPVOID param)

{

CsingleLock singelLock(semaphore);

singleLock.Lock();

Sleep(10000);

::MessageBox((HWND)param,"Thread1 had access","Thread1",MB_OK);

return 0;

}

UINT ThreadProc2(LPVOID param)

{

CSingleLock singelLock(semaphore);

singleLock.Lock();

Sleep(10000);

::MessageBox((HWND)param,"Thread2 had access","Thread2",MB_OK);

return 0;

}

UINT ThreadProc3(LPVOID param)

{

CsingleLock singelLock(semaphore);

singleLock.Lock();

Sleep(10000);

::MessageBox((HWND)param,"Thread3 had access","Thread3",MB_OK);

return 0;

}

二、 多線程編程指南編程步驟

1、 啟動Visual C++6.0，生成一個32位的控制臺程序，將該程序命名為"sequence"

2、 輸入要排續的數字，聲明四個子線程；

3、 輸入代碼，編譯運行程序。

三、 多線程編程指南程序代碼

//////////////////////////////////////////////////////////////////////////////////////

// sequence.cpp : Defines the entry point for the console application.

/*

主要用到的WINAPI線程控制函數，有關詳細說明請查看MSDN；

線程建立函數：

HANDLE CreateThread(

LPSECURITY_ATTRIBUTES lpThreadAttributes, // 安全屬性結構指針，可為NULL；

DWORD dwStackSize, // 線程棧大小，若為0表示使用默認值； 

LPTHREAD_START_ROUTINE lpStartAddress, // 指向線程函數的指針；

LPVOID lpParameter, // 傳遞給線程函數的參數，可以保存一個指針值； 

DWORD dwCreationFlags, // 線程建立是的初始標記，運行或掛起； 

LPDWORD lpThreadId // 指向接收線程號的DWORD變量； 

);

對臨界資源控制的多線程控制的信號函數：

HANDLE CreateEvent(

LPSECURITY_ATTRIBUTES lpEventAttributes, // 安全屬性結構指針，可為NULL；

BOOL bManualReset, // 手動清除信號標記，TRUE在WaitForSingleObject后必須手動//調用RetEvent清除信號。若為 FALSE則在WaitForSingleObject

//后，系統自動清除事件信號；

BOOL bInitialState, // 初始狀態，TRUE有信號，FALSE無信號；

LPCTSTR lpName // 信號量的名稱，字符數不可多于MAX_PATH；

//如果遇到同名的其他信號量函數就會失敗，如果遇

//到同類信號同名也要注意變化；

);

HANDLE CreateMutex(

LPSECURITY_ATTRIBUTES lpMutexAttributes, // 安全屬性結構指針，可為NULL

BOOL bInitialOwner, // 當前建立互斥量是否占有該互斥量TRUE表示占有，

//這樣其他線程就不能獲得此互斥量也就無法進入由

//該互斥量控制的臨界區。FALSE表示不占有該互斥量 

LPCTSTR lpName // 信號量的名稱，字符數不可多于MAX_PATH如果

//遇到同名的其他信號量函數就會失敗，

//如果遇到同類信號同名也要注意變化；

);

//初始化臨界區信號，使用前必須先初始化

VOID InitializeCriticalSection(

LPCRITICAL_SECTION lpCriticalSection // 臨界區變量指針

);

//阻塞函數

//如果等待的信號量不可用，那么線程就會掛起，直到信號可用

//線程才會被喚醒，該函數會自動修改信號，如Event，線程被喚醒之后

//Event信號會變得無信號，Mutex、Semaphore等也會變。

DWORD WaitForSingleObject(

HANDLE hHandle, // 等待對象的句柄

DWORD dwMilliseconds // 等待毫秒數，INFINITE表示無限等待

);

//如果要等待多個信號可以使用WaitForMutipleObject函數

*/

#include "stdafx.h"

#include "stdlib.h"

#include "memory.h"

HANDLE evtTerminate; //事件信號,標記是否所有子線程都執行完

/*

下面使用了三種控制方法，你可以注釋其中兩種，使用其中一種。

注意修改時要連帶修改臨界區PrintResult里的相應控制語句

*/

HANDLE evtPrint; //事件信號,標記事件是否已發生

//CRITICAL_SECTION csPrint; //臨界區

//HANDLE mtxPrint; //互斥信號,如有信號表明已經有線程進入臨界區并擁有此信號

static long ThreadCompleted = 0; 

/*用來標記四個子線程中已完成線程的個數,當一個子線程完成時就對ThreadCompleted進行加一操作, 要使用InterlockedIncrement(long* lpAddend)和InterlockedDecrement(long* lpAddend)進行加減操作*/

//下面的結構是用于傳送排序的數據給各個排序子線程

struct MySafeArray

{

long* data;

int iLength;

};

//打印每一個線程的排序結果

void PrintResult(long* Array, int iLength, const char* HeadStr = "sort");

//排序函數

unsigned long __stdcall BubbleSort(void* theArray); //冒泡排序

unsigned long __stdcall SelectSort(void* theArray); //選擇排序

unsigned long __stdcall HeapSort(void* theArray); //堆排序

unsigned long __stdcall InsertSort(void* theArray); //插入排序

/*以上四個函數的聲明必須適合作為一個線程函數的必要條件才可以使用CreateThread

建立一個線程。

（1）調用方法必須是__stdcall，即函數參數壓棧順序由右到左，而且由函數本身負責

棧的恢復, C和C++默認是__cdecl, 所以要顯式聲明是__stdcall

（2）返回值必須是unsigned long

（3）參數必須是一個32位值，如一個指針值或long類型

(4) 如果函數是類成員函數，必須聲明為static函數，在CreateThread時函數指針有特殊的寫法。如下(函數是類CThreadTest的成員函數中)：

static unsigned long _stdcall MyThreadFun(void* pParam);

handleRet = CreateThread(NULL, 0, &CThreadTestDlg::MyThreadFun, NULL, 0, &ThreadID);

之所以要聲明為static是由于，該函數必須要獨立于對象實例來使用，即使沒有聲明實例也可以使用。*/

int QuickSort(long* Array, int iLow, int iHigh); //快速排序

int main(int argc, char* argv[])

{

long data[] = {123,34,546,754,34,74,3,56};

int iDataLen = 8;

//為了對各個子線程分別對原始數據進行排序和保存排序結果

//分別分配內存對data數組的數據進行復制

long *data1, *data2, *data3, *data4, *data5;

MySafeArray StructData1, StructData2, StructData3, StructData4;

data1 = new long[iDataLen];

memcpy(data1, data, iDataLen << 2); //把data中的數據復制到data1中

//內存復制 memcpy(目標內存指針, 源內存指針, 復制字節數), 因為long的長度

//為4字節,所以復制的字節數為iDataLen << 2, 即等于iDataLen*4

StructData1.data = data1;

StructData1.iLength = iDataLen;

data2 = new long[iDataLen];

memcpy(data2, data, iDataLen << 2);

StructData2.data = data2;

StructData2.iLength = iDataLen;

data3 = new long[iDataLen];

memcpy(data3, data, iDataLen << 2);

StructData3.data = data3;

StructData3.iLength = iDataLen;

data4 = new long[iDataLen];

memcpy(data4, data, iDataLen << 2);

StructData4.data = data4;

StructData4.iLength = iDataLen;

data5 = new long[iDataLen];

memcpy(data5, data, iDataLen << 2);

unsigned long TID1, TID2, TID3, TID4; 

//對信號量進行初始化

evtTerminate = CreateEvent(NULL, FALSE, FALSE, "Terminate");

evtPrint = CreateEvent(NULL, FALSE, TRUE, "PrintResult");

//分別建立各個子線程

CreateThread(NULL, 0, &BubbleSort, &StructData1, NULL, &TID1);

CreateThread(NULL, 0, &SelectSort, &StructData2, NULL, &TID2);

CreateThread(NULL, 0, &HeapSort, &StructData3, NULL, &TID3);

CreateThread(NULL, 0, &InsertSort, &StructData4, NULL, &TID4);

//在主線程中執行行快速排序，其他排序在子線程中執行 

QuickSort(data5, 0, iDataLen - 1);

PrintResult(data5, iDataLen, "Quick Sort");

WaitForSingleObject(evtTerminate, INFINITE); //等待所有的子線程結束

//所有的子線程結束后，主線程才可以結束

delete[] data1;

delete[] data2;

delete[] data3;

delete[] data4;

CloseHandle(evtPrint);

return 0;

}

/*

冒泡排序思想(升序，降序同理，后面的算法一樣都是升序):從頭到尾對數據進行兩兩比較進行交換,小的放前大的放后。這樣一次下來，最大的元素就會被交換的最后，然后下一次 

循環就不用對最后一個元素進行比較交換了，所以呢每一次比較交換的次數都比上一次循環的次數少一，這樣N次之后數據就變得升序排列了*/

unsigned long __stdcall BubbleSort(void* theArray)

{

long* Array = ((MySafeArray*)theArray)->data;

int iLength = ((MySafeArray*)theArray)->iLength;

int i, j=0;

long swap;

for (i = iLength-1; i >0; i--)

{

for(j = 0; j < i; j++)

{

if(Array[j] >Array[j+1]) //前比后大，交換

{

swap = Array[j];

Array[j] = Array[j+1];

Array[j+1] = swap;

}

}

}

PrintResult(Array, iLength, "Bubble Sort"); //向控制臺打印排序結果

InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1

if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完

//若都執行完則設置程序結束信號量

return 0;

}

/*選擇排序思想:每一次都從無序的數據中找出最小的元素，然后和前面已經有序的元素序列的后一個元素進行交換，這樣整個源序列就會分成兩部分，前面一部分是已經排好序的有序序列，后面一部分是無序的，用于選出最小的元素。循環N次之后，前面的有序序列加長到跟源序列一樣長，后面的無序部分長度變為0，排序就完成了。*/

unsigned long __stdcall SelectSort(void* theArray)

{

long* Array = ((MySafeArray*)theArray)->data;

int iLength = ((MySafeArray*)theArray)->iLength;

long lMin, lSwap;

int i, j, iMinPos;

for(i=0; i < iLength-1; i++)

{

lMin = Array[i];

iMinPos = i;

for(j=i + 1; j <= iLength-1; j++) //從無序的元素中找出最小的元素

{

if(Array[j] < lMin)

{

iMinPos = j;

lMin = Array[j];

}

}

//把選出的元素交換拼接到有序序列的最后

lSwap = Array[i];

Array[i] = Array[iMinPos];

Array[iMinPos] = lSwap;

}

PrintResult(Array, iLength, "Select Sort"); //向控制臺打印排序結果

InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1

if(ThreadCompleted == 4) SetEvent(evtTerminate);//檢查是否其他線程都已執行完

//若都執行完則設置程序結束信號量

return 0;

}

/*堆排序思想：堆：數據元素從1到N排列成一棵二叉樹，而且這棵樹的每一個子樹的根都是該樹中的元素的最小或最大的元素這樣如果一個無序數據集合是一個堆那么，根元素就是最小或最大的元素堆排序就是不斷對剩下的數據建堆，把最小或最大的元素析透出來。下面的算法，就是從最后一個元素開始，依據一個節點比父節點數值大的原則對所有元素進行調整，這樣調整一次就形成一個堆，第一個元素就是最小的元素。然后再對剩下的無序數據再進行建堆，注意這時后面的無序數據元素的序數都要改變，如第一次建堆后，第二個元素就會變成堆的第一個元素。*/

unsigned long __stdcall HeapSort(void* theArray)

{

long* Array = ((MySafeArray*)theArray)->data;

int iLength = ((MySafeArray*)theArray)->iLength;

int i, j, p;

long swap;

for(i=0; i {

for(j = iLength - 1; j>i; j--) //從最后倒數上去比較字節點和父節點

{

p = (j - i - 1)/2 + i; //計算父節點數組下標

//注意到樹節點序數跟數組下標不是等同的，因為建堆的元素個數逐個遞減

if(Array[j] < Array[p]) //如果父節點數值大則交換父節點和字節點

{

swap = Array[j];

Array[j] = Array[p];

Array[p] = swap;

}

}

}

PrintResult(Array, iLength, "Heap Sort"); //向控制臺打印排序結果

InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1

if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完

//若都執行完則設置程序結束信號量

return 0;

}

/*插入排序思想：把源數據序列看成兩半，前面一半是有序的，后面一半是無序的，把無序的數據從頭到尾逐個逐個的插入到前面的有序數據中，使得有序的數據的個數不斷增大，同時無序的數據個數就越來越少，最后所有元素都會變得有序。*/

unsigned long __stdcall InsertSort(void* theArray)

{

long* Array = ((MySafeArray*)theArray)->data;

int iLength = ((MySafeArray*)theArray)->iLength;

int i=1, j=0;

long temp;

for(i=1; i {

temp = Array[i]; //取出序列后面無序數據的第一個元素值

for(j=i; j>0; j--) //和前面的有序數據逐個進行比較找出合適的插入位置

{

if(Array[j - 1] >temp) //如果該元素比插入值大則后移

Array[j] = Array[j - 1];

else //如果該元素比插入值小，那么該位置的后一位就是插入元素的位置

break; 

}

Array[j] = temp;

}

PrintResult(Array, iLength, "Insert Sort"); //向控制臺打印排序結果

InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1

if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完

//若都執行完則設置程序結束信號量

return 0;

}

/*快速排序思想：快速排序是分治思想的一種應用，它先選取一個支點，然后把小于支點的元素交換到支點的前邊，把大于支點的元素交換到支點的右邊。然后再對支點左邊部分和右

邊部分進行同樣的處理，這樣若干次之后，數據就會變得有序。下面的實現使用了遞歸

建立兩個游標：iLow，iHigh；iLow指向序列的第一個元素，iHigh指向最后一個先選第一個元素作為支點，并把它的值存貯在一個輔助變量里。那么第一個位置就變為空并可以放置其他的元素。 這樣從iHigh指向的元素開始向前移動游標，iHigh查找比支點小的元素，如果找到，則把它放置到空置了的位置（現在是第一個位置），然后iHigh游標停止移動，這時iHigh指向的位置被空置，然后移動iLow游標尋找比支點大的元素放置到iHigh指向的空置的位置，如此往復直到iLow與iHigh相等。最后使用遞歸對左右兩部分進行同樣處理*/

int QuickSort(long* Array, int iLow, int iHigh)

{

if(iLow >= iHigh) return 1; //遞歸結束條件

long pivot = Array[iLow];

int iLowSaved = iLow, iHighSaved = iHigh; //保未改變的iLow，iHigh值保存起來

while (iLow < iHigh)

{

while (Array[iHigh] >= pivot && iHigh >iLow) //尋找比支點大的元素

iHigh -- ;

Array[iLow] = Array[iHigh]; //把找到的元素放置到空置的位置

while (Array[iLow] < pivot && iLow < iHigh) //尋找比支點小的元素

iLow ++ ;

Array[iHigh] = Array[iLow]; //把找到的元素放置到空置的位置

}

Array[iLow] = pivot; //把支點值放置到支點位置，這時支點位置是空置的

//對左右部分分別進行遞歸處理

QuickSort(Array, iLowSaved, iHigh-1);

QuickSort(Array, iLow+1, iHighSaved);

return 0;

}

//每一個線程都要使用這個函數進行輸出，而且只有一個顯示器，產生多個線程

//競爭對控制臺的使用權。

void PrintResult(long* Array, int iLength, const char* HeadStr)

{

WaitForSingleObject(evtPrint, INFINITE); //等待事件有信號

//EnterCriticalSection(&csPrint); //標記有線程進入臨界區

//WaitForSingleObject(mtxPrint, INFINITE); //等待互斥量空置（沒有線程擁有它）

int i;

printf("%s: ", HeadStr);

for (i=0; i {

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

Sleep(100); //延時（可以去掉）

/*只是使得多線程對臨界區訪問的問題比較容易看得到

如果你把臨界控制的語句注釋掉，輸出就會變得很凌亂，各個排序的結果會

分插間隔著輸出，如果不延時就不容易看到這種不對臨界區控制的結果

*/

}

printf("%d\n", Array[i]);

SetEvent(evtPrint); //把事件信號量恢復，變為有信號

}

四、 小結

對復雜的應用程序來說，線程的應用給應用程序提供了高效、快速、安全的數據處理能力。本實例講述了線程處理中經常遇到的問題，希望對讀者朋友有一定的幫助，起到拋磚引玉的作用。

原文地址：http://xiaocainiao.baijia.baidu.com/article/802175