Очень прошу помогите с прогой....С++

pomogite
5/30/2010, 1:44:33 PM
Дана целочисленная матрица размера n X m, в которой имеются ровно два одинаковых элемента. Найти индексы этих элементов.
DELETED
5/30/2010, 9:39:34 PM
CODE
#include <stdio.h>

///////////////////////////////////////////////////////////////
// Dirty binary tree
//
template <typename T> class CNode {
public:
CNode () {
 m_IsAccepted = false;
 m_pRight = 0;
 m_pLeft = 0;
};

CNode ( CNode* pRoot, T Value ) {
 m_IsAccepted = false;
 m_pRight = 0;
 m_pLeft = 0;
 m_Value = Value;
 if ( pRoot ) {
  m_IsAccepted = Insert ( pRoot, this );
 };
};

~CNode() {
 if ( m_IsAccepted ) {
  if ( m_pRight ) {
   delete m_pRight;
  };

  if ( m_pLeft ) {
   delete m_pLeft;
  };
 };
};

T* GetValue () {
 return &m_Value;
};

bool IsAccepted() const {
 return m_IsAccepted;
};

bool operator == (const CNode& rValue) {
 return this->m_Value == rValue.m_Value;
};

bool operator > (const CNode& rValue) {
 return this->m_Value > rValue.m_Value;
};

bool operator < (const CNode& rValue) {
 return this->m_Value > rValue.m_Value;
};

CNode& operator = ( CNode& rValue ) {
 if ( this != &rValue ) {
  m_pLeft  = rValue.m_pLeft;
  m_pRight = rValue.m_pRight;
  m_Value  = rValue.m_Value;
  m_IsAccepted  = rValue.m_IsAccepted;
 };
 return *this;
};

static bool Insert ( CNode* pRoot, CNode* pChild ) {
 if ( pRoot && pChild ) {
  if ( pChild->m_IsAccepted ) {
   return false;
  };
  if ( !pRoot->m_IsAccepted ) {
   pChild->m_IsAccepted = true;
   *pRoot = *pChild;
   delete pChild;
   return true;
  };
  if ( *pRoot == *pChild ) {
   *pChild = *pRoot;
   return false;
  } else if ( *pChild > *pRoot ) {
   if ( pRoot->m_pRight ) {
    return Insert ( pRoot->m_pRight, pChild );
   } else {
    pRoot->m_pRight = pChild;
    return true;
   };
  } else {
   if ( pRoot->m_pLeft ) {
    return Insert ( pRoot->m_pLeft, pChild );
   } else {
    pRoot->m_pLeft = pChild;
    return true;
   };
  };
 } else {
  return false;
 };
};

private:
CNode* m_pRight, *m_pLeft;
T m_Value;
bool m_IsAccepted;
};

///////////////////////////////////////////////////////////////
// Matrix item template
//
template <typename T> class CMatrixItem {
public:
CMatrixItem () {
};

CMatrixItem ( int x, int y, T Value ) {
 m_x  = x;
 m_y  = y;
 m_Value = Value;
};

CMatrixItem ( CMatrixItem& rValue ) {
 memset ( this, &rValue, sizeof(this) );
};

CMatrixItem& operator = ( CMatrixItem& rValue ) {
 if ( this != &rValue ) {
  m_x  = rValue.m_x;
  m_y  = rValue.m_y;
  m_Value = rValue.m_Value;
 };
 return *this;
};

bool operator == (const CMatrixItem& rValue) {
 return m_Value == rValue.m_Value;
};

bool operator > (const CMatrixItem& rValue) {
 return m_Value > rValue.m_Value;
};

bool operator < (const CMatrixItem& rValue) {
 return m_Value < rValue.m_Value;
};

public:
operator T() {
 return m_Value;
};

int GetX() const {
 return m_x;
};

int GetY() const {
 return m_y;
};

private:
int m_x;
int m_y;
T m_Value;
};


//////////////////////////////////////////////////////////////
//
template <> CMatrixItem<char*>::CMatrixItem ( int x, int y, char* Value ) {
m_x  = x;
m_y  = y;

// Store hash instead of full string
if ( Value ) {
 unsigned int b    = 0x0005C6B7;
 unsigned int a    = 0x0000F8C9;
 unsigned int hash = 0;

 while ( *Value ) {
  hash = hash * a + *Value;
  a *= b;
  Value++;
 };

 m_Value = (char*)(hash & 0x7FFFFFFF);
} else {
 m_Value = 0;
};
};


///////////////////////////////////////////////////////////////
// Build dirty binary tree and filter equal values
//  pMatrix - flattened two-dimensional array
//  width - matrix width
//  height - matrix height
template<typename T> CNode<CMatrixItem<T>>* GetTree ( T* pMatrix, int width, int height ) {
if ( CNode<CMatrixItem<T>>* pTree = new CNode<CMatrixItem<T>>() ) {
 for ( int x = 0; x < width; x++ ) {
  for ( int y = 0; y < height; y++ ) {
   CNode<CMatrixItem<T>>* pNode = new CNode<CMatrixItem<T>> ( pTree, CMatrixItem<T>(x,y, pMatrix[x+y*width] ) );
   if ( pNode && !pNode->IsAccepted() ) {
    printf ( "%d:%d seems to be equal to %d:%d\n", x, y, pNode->GetValue()->GetX(), pNode->GetValue()->GetY() );
    delete pNode;
   };
  };
 };
 return pTree;
};

return 0;
}

///////////////////////////////////////////////////////////////
//
int main(int argc, char* argv[]) {
int arr[5][5] = { { 22, 12, 13, 14, 15 },  
     { 22, 22, 23, 00, 25 },
     { 31, 31, 33, 00, 35 },
     { 41, 42, 43, 00, 11 },
     { 51, 52, 53, 54, 11 } };

printf ( "Дублирование в целочисленной матрице:\n" );

if ( CNode<CMatrixItem<int>>* pTree = GetTree ( &arr[0][0], 5, 5 ) ) {
 // Here we're with our binary tree

 // ... DoSomething();

 // Clean-up
 delete pTree;
};


printf ( "\n\nДублирование в матрице, содержащей строки:\n" );
char* chararr[3][3] = { { "Один", "Ноль", "Три" },  
      { "Четыре", "Пять", "Ноль" },
      { "Семь", "Восемь", "Девять" } };

if ( CNode<CMatrixItem<char*>>* pTree = GetTree ( &chararr[0][0], 3, 3 ) ) {
 // Here we're with our binary tree

 // ... DoSomething();

 // Clean-up
 delete pTree;
};

return 0;
}