數組中逆序對

題目： 在數組中的兩個數字，如果前面的一個數字大于後面的數字，則這兩個數字為一個逆序對。輸入一個數組，求這個數組的逆序對個數。例如：給定數組{5,8,3,1} ，則有<5,3>、<5,1>、<8,3>、<8,1>、<3,1> 這5個逆序對。

問題分析：我采用兩種方法來解決這個問題：

        1）考慮到二叉搜尋樹中每個節點X，它的左子樹所有關鍵字的值小于節點X的值，而右子樹的所有關鍵字的值大于節點X的值，根據這種特點設計一種資料結構存儲每一節點，資料結構如下所示：

                                   struct treeNode{

                                    int value;

                                    searchTree left;

                                    searchTree right;

                                    int rightChildNum;     //用于記錄節點的右子樹有多少個孩子

                                  };

程式讀取數組的元素，建構節點并插入節點，在建立二叉搜尋樹過程中，改變結構體的rightChildNum成員的值來計算數組的逆序對。具體參考程式。

        2）運用歸并排序方法解決這個問題，思路在《劍指offer》有詳細說明。這裡不再多說。

代碼：1）的方法

#include <stdio.h>
#include <stdlib.h>

struct treeNode;
typedef struct treeNode *searchTree;
struct treeNode{
	int value;
	searchTree left;
	searchTree right;
	int rightChildNum;
};

static int inverseCount=0;   //用于統計逆序對的個數

searchTree
insert(int X, searchTree T){    //插入一個節點時改變結構體中rightChildNum成員值
	if(T==NULL){
		T = malloc(sizeof(struct treeNode));
		if(T == NULL){
			printf("Out of space!\n");
			exit(1);
		}else{
			T->value = X;
			T->rightChildNum = 1;
			T->left = T->right = NULL;
		}
	}else if(X < T->value){
		inverseCount += T->rightChildNum;  //節點T及左孩子的個數為插入X節點時的逆序對數
		T->left = insert(X,T->left);
	}else if(X > T->value){
		T->rightChildNum++;              //增加節點T的左孩子個數
		T->right = insert(X,T->right);
	}

	return T;
}

searchTree 
createArrayNode(int array[],int N){
	int i;
	searchTree T=NULL;
	for(i=0; i<N; i++){
		T=insert(array[i],T);	
	}

	return T;
}

void
printTree(searchTree T){
	if(T!=NULL){
		printTree(T->left);	
		printf("%d:%d\t",T->value,T->rightChildNum);
		printTree(T->right);	
	}
}

void 
removeTree(searchTree T){
	if(T != NULL){
		removeTree(T->left);	
		removeTree(T->right);
		if(T->left==NULL && T->right==NULL)
			free(T);
	}
}

int 
main(int argc,char **argv){
	searchTree T;
//	int array[6]={7,5,8,6,4,9};
//	int array[4]={7,5,6,4};
//	int array[7]={7,9,2,4,6,8,13};
    int array[]={7,5,8,6,4,9,14,21,1,52,49,2,56,27,128,65,47,23,57,98,10,17,72};
	T=createArrayNode(array,23);
	printTree(T);
	printf("\n");
	printf("Inverse Count is: %d\n",inverseCount);
	removeTree(T);
	return 0;
}
           

      2）歸并排序的代碼：

頭檔案："fatal.h"

#include <stdio.h>
#include <stdlib.h>

#define		Error(str)        FatalError(str)
#define		FatalError(str)	  fprintf(stderr,"%s\n",str),exit(1)
           

#include "fatal.h"

typedef int ElementType;

int
Merge( ElementType A[], ElementType tmpArray[], int lPos, int rPos, int rightEnd ){
	int leftEnd, numElements, tmPos;
	int i, count = 0;

	leftEnd = rPos-1;
	tmPos = rightEnd;
	numElements = rightEnd-lPos+1;

	while( lPos <= leftEnd && rPos <= rightEnd )
		if( A[leftEnd] > A[rightEnd] ){
			tmpArray[tmPos--] = A[leftEnd--];
			count += rightEnd - rPos + 1;
		}else
			tmpArray[tmPos--] = A[rightEnd--];

	while( lPos <= leftEnd )
			tmpArray[tmPos--] = A[leftEnd--];
	while( rPos <= rightEnd )
			tmpArray[tmPos--] = A[rightEnd--];

	for( i=0; i < numElements; i++, lPos++ )
		A[lPos] = tmpArray[lPos];

	return count;
}

int
MSort( ElementType A[], ElementType tmpArray[], int left, int right ){
	int Center;
	int count, leftCount, rightCount;

	if( left >= right )
		return 0;	
	
	Center = ( left + right ) / 2;
	leftCount = MSort( A, tmpArray, left, Center );
	rightCount = MSort( A, tmpArray, Center + 1, right );
	count = Merge( A, tmpArray, left, Center + 1, right );

	return count + leftCount + rightCount;
}

int
Mergesort( ElementType A[], int n ){
	ElementType *tmpArray;
	int count;

	tmpArray = malloc( n*sizeof(ElementType) );
	if( tmpArray != NULL ){
		count = MSort( A, tmpArray, 0, n-1 );
		free( tmpArray );
	}else
		FatalError( "No space for tmp array!!!" );

	return count;
}


int 
main(){
	int count;
//	ElementType arr[]={23,1,5,75,23,9,24,16,92,4};
	ElementType arr[]={7,5,6,4,2};

	count = Mergesort(arr,5);

	printf("inverse numbers is: %d\n",count);
	return 0;
}
           

參考文獻：

《資料結構與算法分析-c語言描述》（美）Mark Allen Weiss

希望大家能夠多多交流！