Chapter 5. Arrays and Pointers

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// One-dimensional array and Pointer 

#include <iostream>
using namespace std;

int a[] = { 0, 1, 2, 3, 4 };

int main()
{
  int i, *p;
  
  for( i=0; i<=4; i++) cout << a[i] << "   ";
  cout << endl;
  
  for( p= &a[0]; p<=&a[4]; p++) cout << *p << "   ";
  cout << endl;
  
  for( p= &a[0], i=0; i<=4; i++) cout << p[i] << "   ";
  cout << endl;
  
  for(p=a,i=0; p+i<=a+4; i++) cout << *(p+i) << "   ";
  cout << endl;
  
  for(p=a+4; p>=a; p--) cout << *p << "   ";
  cout << endl;
  
  for(p=a+4,i=0; i<=4; i++) cout << p[-i] << "   ";
  cout << endl;
  
  for(p=a+4; p>=a; p--) cout << a[p-a] << "   ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// Two-dimensional array and Pointers 

#include <iostream>
using namespace std;

int a[3][3] = {
  { 1, 2, 3 },
  { 4, 5, 6 },
  { 7, 8, 9 }
};

int *pa[3] = { a[0], a[1], a[2] };	// Array of Pointers
int *p = a[0];

int main() {
  int i;
  for( i=0; i<3; i++ )
    cout << a[i][2-i] << " " << *a[i] << " " << *(*(a+i)+i) << endl;
    cout << endl;
  for( i=0; i<3; i++)
    cout << *pa[i] << " " << p[i] << endl;
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// Abstract Data Type - Extendible Array

#include "extendible_array.h"

int main() {
  Iarray a(3);
  for(int i=0; i<3; i++) 
    a[i] = i;
  a.print();
  cout << "size of a is " << a.size() << endl;
  a.resize(5);
  a.print();
  a[3] = 3; a[4] = 4;
  // a[5] = 5;    error! 	
  a.print();
  a.resize(2);
  a.print();
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// Abstract Data Type - Extendible Array
// Filename: extendible_array.h

#include <iostream>
using namespace std;

class Iarray {
  int *a, len;
public:
  Iarray(int length);
  ~Iarray();
  int& operator[](int n);
  int size();
  void resize(int length);
  void print();
};

Iarray::Iarray(int length) {
  len = length;
  a = new int[len];
  for(int i=0; i<len; i++) a[i] = 0;
}

Iarray::~Iarray() {
  delete [] a;
}

int& Iarray::operator[](int i) {
  if( 0>i || i>=len) {
    cout << "Error: " << i << " subscript is out of bounds.\n";
    exit(-1);
  }
    return a[i];
}

int Iarray::size() {
  return len;
}

void Iarray::resize(int length) {
  if(len == length) return;
  int newlen = length, i;
  int *newa = new int[newlen];
  int min = (newlen < len) ? newlen : len;
  for(i=0; i<min; i++) newa[i] = a[i]; 
  for(i=min; i<newlen; i++) newa[i] = 0;
  delete [] a;
  a = newa;
  len = newlen;
}

void Iarray::print() {
  for(int i=0; i<len; i++)
    cout << a[i] << " ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// Eight queens puzzle

#include <iostream>
using namespace std;

int x[9];
void Print(int n) {
  static int solution = 0;
  cout << "\nsolution = " << ++solution << endl;
  for(int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++)
      if (x[i] == j) cout << " Q";
      else cout << " .";
    cout << '\t' << x[i] << endl;
  }
}

bool Check(int k, int i) {
  for (int j=1; j < k; j++)
    if ((x[j] == i)  // Two in the same column
	      || (abs(x[j]-i) == abs(j-k))) // or in the same diagonal
      return(false);
  return(true);
}


void Queens(int k, int n) {
  for (int i=1; i<=n; i++) {
    if (Check(k, i)) {
      x[k] = i;
      if (k==n) Print(n); 
      else Queens(k+1, n);
    }
  }
}

int main() {
  Queens(1,8);
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// N queens puzzle
// Check by changing the value of N in the source code

#include <iostream>
using namespace std;

#define N 9
int a[N], b[2 * N - 1], c[2 * N - 1], x[N];

void found(void) {
  int i, j;
  static int solution = 0;
  cout << "\nsolution = " << ++solution << endl;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++)
      if (x[i] == j) cout << " Q";
      else           cout << " .";
    cout << endl;
  }
}

void seek(int i) {
  int j;
  for (j = 0; j < N; j++)
    if (a[j] && b[i + j] && c[i - j + N - 1]) {
      x[i] = j;
      if (i < N - 1) {
        a[j] = b[i + j] = c[i - j + N - 1] = 0;
        seek(i + 1);
        a[j] = b[i + j] = c[i - j + N - 1] = 1;
      } 
      else found();
   }
}

int main() {
  int i;
  for (i=0; i<N; i++)     a[i] = 1;
  for (i=0; i<2*N-1; i++) b[i] = 1;
  for (i=0; i<2*N-1; i++) c[i] = 1;
  seek(0);
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 5: Array & Pointer

// Magic square if the sums of the numbers in each row, each column, and both main diagonals are the same.

#define SIZE 160     // Consider a memory for increasing the size. 

#include <iostream>
#include <iomanip>
using namespace std;

int m[SIZE][SIZE];

void odd_n(int n);
void even_n(int n);
void check(int n);
void display(int n);
void swap(int i1, int j1, int i2, int j2);

int main() {
  int n;
  cout << "\nInput the number 3-" << SIZE << ": ";
  cin >> n;
  if(n>2 && n<=SIZE) {
    if(n%2) odd_n(n);
    else even_n(n);
    check(n);
  }
}

void odd_n(int n) {
  int i, j, num=1, nn=n*3/2;
  
  for(i=0; i < n; i++)
    for(j=0; j < n; j++)
      m[(i*2-j+n)%n][(j-i+nn)%n] = num++;
}

void even_n(int n) {
  int i, j, bound=n-1, num=1;
  int mid=n/2, nn=n*n+1, swch = mid;
  int block1=(n-2)/4, block2=bound-block1;
  int inside1=n/4, inside2=bound-inside1;

  for(i=0; i<n; i++)
    for(j=0; j<n; j++) {
      if(i >= inside1 && i <= inside2 && j >= inside1 && j <= inside2)
        m[i][j]=num;
      else 
        if((i > block1 && i < block2) || (j > block1 && j < block2))
          m[i][j]=nn-num;
        else 
          m[i][j]=num;
      num++;
  }
  if(!(n%4)) return;

  swch=mid;
  for(i=0; i<mid; i++) {
    if(i==block1 || i==block2) {
      swch=0; continue;
    }
    swap(i, block2, bound-i, block2);
    swap(block1, i, block1, bound-i);
    swap(block2, i, block2, bound-i);
    swap(swch, i, swch, bound-i);
  }
  for(i=block1+1; i < block2; i++) {
    swap(i, block1, i, block2);
    swap(block1, i, block2, i);
  }
  swap(mid, block1, mid, block2);
  swap(block1, swch, block2, swch);
}

void swap(int i1, int j1, int i2, int j2) {
  int t;
  t=m[i1][j1];
  m[i1][j1]=m[i2][j2];
  m[i2][j2]=t;
}

void check(int n)
{
  int i, j;
  unsigned long sum, srow, scol, sd1=0, sd2=0;

  sum=(unsigned long)n*(n*n+1)/2;
  cout << "SUM = " << sum << endl;
  for(i=0; i < n; i++) {
    sd1 += m[i][i];
    sd2 += m[i][n-i-1];
    srow = scol = 0;
    for(j=0; j < n; j++) {
      srow += m[i][j];
      scol += m[j][i];
    }
    if((srow!=sum) || (scol!=sum)) return;
  }

  if((sd1!=sum) || (sd2!=sum)) return;
  cout << "\n- O.K. -\n\n";
  display(n);
}

void display(int n) {
  for(int i=0; i<n; i++) {
    cout << setw(2) << i+1 << ")] ";
    for(int j=0; j<n; j++)
      cout <<setw(4) << m[i][j];
    cout << endl;
  }
}