16.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Thursday 2006.11.2 (Week 8)
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/16.txt)

Chapter 7: Pointers (continued)

Sorting by pointer swap
Array of positions

Last time: array of pointers to string literals

char *suit[4] = { "Hearts", "Diamonds", "Clubs", "Spades" };

we can swap suit[i], suit[j] by 
	char *temp = suit[i];
	suit[i] = suit[j];
	suit[j] = temp;

However, if we declared it as

char m[4][9] = { "Hearts", "Diamonds", "Clubs", "Spades" };

then we can't just swap m[i], m[j] by
	char temp[9] = m[i]; /* This is wrong!! you can't do this */
	m[i] = m[j];         /* This is also wrong */
	m[j] = temp;         /* This is wrong, too */
because
1. m[i] is not a constant array and cannot be used as an initializer
2. m[i] has no L-value! it is the expression (m + i)
	(remember, it's m (a constant) + sizeof(char)*i => it's an R-value!)
3. m[j] has no L-value either

Instead, in this case we would have to make a "deep copy"
when we swap m[i] and m[j] (i.e., swap two rows):

int k; /* need to copy each column */
for (k = 0; k < 9; k++) {
	char temp = m[i][k];
	m[i][k] = m[i][j];
	m[i][j] = temp;
}


Alternative: 
 make an array of pointers to the rows.

char m[4][9] = { "Hearts", "Diamonds", "Clubs", "Spades" };
typedef char RowType[9]; /* RowType is a 9-char array */
RowType *p[4] = { m, m+1, m+2, m+3 };
/* p is a 4-element array of pointers to rows */
/* This way, 
 p[0] contains address of m[0], 
 p[1] contains address of m[1], ...
 */
int main() {
        int i;
        for (i=0; i< 4; i++) {
                printf("p[%d] = %p, &m[%d] = %p\n", i, p[i], i, &m[i]);
        }
}

you will see p[i] is exactly the same as &m[i]! (your answer may vary)
(result are from cs25.cs.nthu.edu.tw)
% ./a.out
p[0] = 20954, &m[0] = 20954
p[1] = 2095d, &m[1] = 2095d
p[2] = 20966, &m[2] = 20966
p[3] = 2096f, &m[3] = 2096f

Then, we can swap p[i], p[j] instead.

	RowType *temp = p[i];
	p[i] = p[j];
	p[j] = temp;

You are not moving m[i] and m[j] themselves, 
but p[i], p[j] are switched.
(much faster than switching m[i][0]...m[i][8]  and  m[j][0]...m[j][8]!!)

Book example: deck of cards
Representation: 2-dimensional array, 4 rows (of suits)  by 13 columns (of faces)

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

/* declare inside main() */
const char *suit[4] = { "Hearts", "Diamonds", "Clubs", "Spades" };
	/* array of pointers to constant strings */

const char *face[13] = { "Ace", "Deuce", "Three", "Four", "Five", "Six",
	"Seven", "Eight", "Nine", "Ten", "Jack", "Queen", "King" };
	/* array of pointers to contant strings */

int deck[4][13] = { 0 };
	/* 0 means the card [i][j] is not in the deck.
	  1--52 would be the position of the card in the deck. */

We could have declared
int deck[4][13] = { 
	/* all of the Hearts ??*/
	{ 29  /* the position of Ace */,
	  33  /* the position of Deuce */,
	  7   /* the position of Three */, 
	  .... 
	},
	/* all of the Diamonds ??*/
	{ 15   /* the position of Ace */,
	  44   /* the position of Deuce */,
	  ...
	 },
	 /* all of Clubs ??*/
	 { ... },
	 /* all of Spades ??*/
	 { ... }
};

But this program does not statically initialize the positions of
the cards; instead, it uses random number generators to determine
which card should be next.

1	void shuffle( int wDeck[][13]) {
2		int row, column, pos;
3		for (pos = 1; pos <= 52; pos++) {
			/* go through the positions of the card in the deck */
4			do {
5				row = rand() % 4;
6				column = rand() % 13;
7			} while (wDeck[row][column]); /* [row][column] already has a position */
			/* we found a card not yet assigned a position */
8			wDeck[row][column] = pos; /* assign the new position to this card */
9		}
10	}

To print ("deal") the cards one at a time, 
void deal(int wDeck[][13], const char *wFace[], const char *wSuit[]) {
	int pos, row, column;
	for (pos = 1; pos <= 52; pos++) {
		/* check each row */
		for (row = 0; row < 4; row++) {
			for (column = 0; column < 13; column++) {
				if (pos == wDeck[row][column]) {
					printf("%d: %s of %s\n", pos, wFace[column], wSuit[row]);
					/* found it -- we can skip */
					break;
				}
			}
		}
	}
}

But this is not very efficient!
One way is to encode the row/column in one integer:

cardNum = row * 13 + column;

Declare another array: 
int shuffledDeck[52];

after line 8:
	shuffledDeck[pos-1] = row * 13 + column;

then, deal() would look like
	for (pos = 0; pos < 52; pos++) {
		int row = shuffledDeck[pos] / 13;
		int column = shuffledDeck[pos] % 13;
		printf("%d: %s of %s\n", pos+1, wFace[column], wSuit[row]);
	}
=>  This is much faster!