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
#include
#include
/* 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 /* 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 /* 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!
