Data Structures

Chapter 2: Arrays

2-1
Abstract Data Type and C++
Class
• Four components in a C++ Class
– class name
– data members: the data that makes up the class
– member functions: the set of operations that may
be applied to the objects of class
– levels of program access:
• private: accessible within the same class
• protected: accessible within the same class and derived
classes
2-2
• public: accessible anywhere
Rectangle.h –Definition of Rectangle Class
// in the header file Rectangle.h
#ifndef RECTANGLE_H /* preprocessor
directive, “if not defined” */
#define RECTANGLE_H
class Rectangle // class name: Rectangle
{
public:
// 4 member functions
Rectangle(); // constructor
~Rectangle(); // destructor
int GetHeight();
int GetWidth();
private: height
// 4 data members
int xLow, yLow, height, width; (x, y) width
// (xLow, yLow) is the bottom left corner
};
#endif
2-3
Rectangle.cpp – Operation Implementation
// in the source file Rectangle.cpp
#include <Rectangle.h>

int Rectangle::GetHeight() {return height;}

int Rectangle::GetWidth() {return width;}

• ADT: Abstract Data Type

– Rectangle.h: Object representation
(or Class Definition)
– Rectangle.cpp: Operation implementation
2-4
Constructor(1)
• Constructor ( 建構子 ): the name of the function is
identical to its class name, to initialize the data
members
Rectangle::Rectangle(int x, int y, int h,
int w)
{
xLow = x; yLow = y;
height = h; width = w;
}
int main()
{
Rectangle r(1,3,6,6); // call constructor
Rectangle *s=new Rectangle(0,0,3,4);
return 0;
} 2-5
Constructor(2)
• Another way of Constructor initialization:
Rectangl::Rectangle(int x = 0, int y = 0,
int h = 0, int w = 0)
: xLow(x), yLow(y), height(h), width(w)
{ }

int main()
{
Rectangle t; // all set to 0
return 0;
}

2-6
Operator Overloading
int Rectangle::operator==(const Rectangle& s)
// overload "=="
{
if (this == &s) return 1;
else if ( (xLow == s.xLow) && (yLow == s.yLow)
&&
(height == s.height) && (width ==
s.width) )
return 1;
return 0;
}

ostream& Rectangle:: operator<<(ostream& os,

Rectangle& r) // overload “<<"
{
os << "Position is: " << r.xLow << " ";
os << r.yLow << endl;
os << "Height is: " << r.height << endl;
os << "Width is: " << r.width << endl;
return os; 2-7
}
Complete Program for Rectangle
#include <iostream>
using namespace std;

class Rectangle
{
friend ostream& operator<< (ostream&, Rectangle&);
public:
int Rectangle::operator==(const Rectangle&)
Rectangle(); // constructor
~Rectangle(); // destructor
int GetHeight(); int GetWidth();
private:
int xLow, yLow, height, width;
};
...
int main()
{
Rectangle r(1,3,6,6),t(1,3,6,6); // call constructor
if (r == t) cout << 1 << endl; // overloaded "=="
cout << r; // overloaded "<<“
2-8
return 0;
Array as ADT
• Array Objects:
– A set of pairs <index, value> where for each value of
index ( 索引 ) there is a corresponding value.
– Index set is a finite ordered set of one or more dimensions.
For example, {0,…,n1} for one dimension, {(0,0), (0,1),
(0,2),(1,0),(1,1),…,(3,2)…} for two dimensions.
class GeneralArray{
public:
GeneralArray(int j, RangeList list, float initValue =
defaultValue);
// create a linear (1D) array of size j
float Retrieve(index i);
// return the value of index i
void Store(index i, float x);
// change the value of index i to x
}
2-9
1-dimentional Array in C/C++
// array declaration ( 陣列宣告 )
int a[10]; // no intialization
float f[7];

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

int a[]={10,11,12}; // array size:3

// a[0]=10, a[1]=11, a[2]=12
bool b[] = {true, false, true};
char c[] = {'B', 'C', ‘\0', ‘\n'};
char d[] = “BED"; // 4 bytes

2-10
Programming skills
int a[100];
for (i = 0; i < 100; a[i++] = 0);

Better:Constants defined by identifiers

#define NUMELTS 100

int a[NUMELTS];
for (i = 0; i < NUMELTS; a[i++] = 0);

2-11
Representation of Arrays
• Representation of one dimensional array
α α+ α+ α+ α+ α+ α+ α+ α+ α+ α+10α+1
1 2 3 4 5 6 7 8 9 1
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[1
1]

• Multidimensional arrays can be implemented

by one dimensional array via either row major
order or column major order.
2-12
Two Dimensional (2D) Arrays
2-dimensional array:
int [ ][ ]a = new int[3][4]; // in C++
int a[3][4]; // in C/C++
It can be shown as a table:
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

2-13
Row-major Order (from 2D to 1D)
• int a[3][4]; // row-major order
• logical structure physical structure
0 1 2 3
a[0][0]
0 a[0][1]
1 a[0][2]
2 a[0][3]
a[1][0]
A[2][1] a[1][1]
a[1][2]
a[1][3]
Mapping function: a[2][0]
Address of a[i][j]= **
2-14
where one integer occupies 4 bytes.
Memory Mapping of Row-major Order
 : the start address of array a
– refer to a[0], a[0][0], a[0][0][0], etc.
 : the memory size for storing each element
– char: 1 byte, =1
– int: 4 bytes, =4
• 2D to 1D
– int (char) a[u1][u2]
– a[i][j] =  + (iu2 + j)  
• 3D to 1D
– int (char) a[u1][u2][u3]
– a[i][j][k] =  + (i  u2  u3 + j  u3 + k)   2-15
Column-Major Order
a b c d
e f g h
i j k l
• Convert 2D into 1D by collecting elements first by
columns, from left to right..
• Within a column, elements are collected from top to
bottom.
• We get y = {a, e, i, b, f, j, c, g, k, d, h, l}

col 0 col 1 col 2 … col i

2-16
Memory Mapping of Column-major Order
 : the start address of array a
– refer to a[0], a[0][0], a[0][0][0], etc.
 : the memory size for storing each element
– char: 1 byte, =1
– int: 4 bytes, =4
• 2D to 1D
– int (char) a[u1][u2]
– a[i][j] =  + (i+ j u1 )  
• 3D to 1D
– int (char) a[u1][u2][u3]
– a[i][j][k] =  + (i + j  u1 + k u1  u2 )   2-17
Sets in Pascal
var x, x1, x2: set of 1..10;
x = [1, 2, 3, 5, 9, 10]

A set is represented by a bit string.

e.g. 1110100011 1: in the set
0: not in the set

e.g. x1 = [2, 4, 6, 8] 0101010100

x2 = [1, 2, 5, 9] 1100100010

• union 聯集 :
x1  x2 = **
x1 + x2 = [1, 2, 4, 5, 6, 8, 9] **
2-18
x1 = [2, 4, 6, 8]
0101010100
Intersection 交集 :
x2 = [1, 2, 5, 9]
x1  x2 = 1100100010 **
x1 * x2 = [2] **

difference 差集 :
x1 – x2 = **
x1 – x2 = [4, 6, 8] **

contain 包含 :
x1  x2 
x1  x2  **
a in x1 

• The size of a set is limited. 2-19

Polynomial ( 多項式 )
f(x) = x8  10x5 + 3x3 + 1.5
• 4 terms: x8,  10x5, 3x3, 1.5
• Coefficients( 係數 ): 1,  10, 3, 1.5
• Nonnegative integer exponents( 指數 , 冪 ):
8, 5, 3, 0

2-20
Polynomial Addition
f(x) = x8  10x5 + 3x3 + 1.5
g(x) = 3x3 + 2x  4

f(x) = x8  10x5 + 3x3 + 1.5

g(x) = 3x3 + 2x  4
f(x) + g(x) = x8  10x5 + 6x3 + 2x  2.5

• a(x) + b(x) = (ai+bi)xi

2-21
Polynomial Representation (1)
#define MaxDegree 100
class Polynomial{
private:
int degree; // degree ≤ MaxDegree
float coef [MaxDegree + 1];
};
f(x) = x8  10x5 + 3x3 + 1.5

0 1 2 3 4 5 6 7 8 9 10 11 12 …
1.5 0 0 3 0 -10 0 0 1 0 0 0 0 0...
2-22
Polynomial Representation (2)
class Polynomial{
private:
int degree;
float *coef;
public:
Polynomial::Polynomial(int d) {
degree = d;
coef = new float [degree+1];
}
};
f(x) = x8  10x5 + 3x3 + 1.5
0 1 2 3 4 5 6 7 8 9 10 11 12 …
1.5 0 0 3 0 -10 0 0 1 0 0 0 0 0...
2-23
Polynomial Representation (3)
• Add the following two polynomials:
a(x) = 2x1000 + 1
# of elements
b(x) = x + 10x + 3x + 1
4 3 2

0 1 2 0 1 2 3 4
a_coef 2 2 1 b_coef 4 1 10 3 1

a_exp 1000 0 b_exp 4 3 2 0

0 1 2 3 4 5
c_coef 5 2 1 10 3 2

c_exp 1000 4 3 2 0
2-24
Sparse Matrices ( 稀疏矩陣 )
• Most elements of the matrix are of zero

000000 Row 0 5  6 matrix (5 by

000304 Row 1 6)
Row 2 5 rows
000570 Row 3 6 columns
000000 Row 4 30 elements
0 0 2 Column
600 4
6 nonzero elements
2-25
Matrices

15 0 0 22 0  15
0 11 3 0 0 0 
  27 3 4 
 6 82  2  0 0 0 6 0 0 
   
 109  64 11  0 0 0 0 0 0 
   91
 12 8 9 0 0 0 0 0 
 48  
27 47   0 0 28 0 0 0 
Dense matrix 53 Sparse matrix

2-26
Matrix Transpose in a 2-D Array
 1 2 3  1 4 7 10
 4 5 6  2 5 8 11
A=   B=  
 7 8 9  3 6 9 12 34
 
10 11 12 43

for (i = 0; i < rows; i++ )

for (j = 0; j < columns; j++ )
B[j][i] = A[i][j];
Time Complexity: O(rows  columns)
2-27
Sparse Matrix Representation
• Use triples ( 三元組 ): (row, column,
value) 0 0 0 0 0 0
– (1,3,3), (1, 5, 4), (2,3,5), (2,4,7), 0 0 0 3 0 4
(4,2,2), (4,3,6) 0 0 0 5 7 0
• To perform matrix operations, such 0 0 0 0 0 0
0 0 2 6 0 0
as transpose, we have to know the
number of rows, number of
columns, and number of nonzero
elements.
2-28
Linear List Representation of Matrix
000000 row 1 1 2 2 4 4
000304 column 3 5 3 4 2 3
000570 value 3 4 5 7 2 6
000000
002600

2-29
Linear List for a Matrix
• Class SparseMatrix
– Array smArray of triples of type MatrixTerm
• int row, col, value // for a triple (row, col, value)
– int rows, // number of rows in this matrix
cols, // number of columns in this matrix
terms, // number of nonzero elements in this matrix
capacity; // size of smArray
• Size of smArray generally not predictable at time
of initialization
– Start with some default capacity/size (say 10)
– Increase capacity as needed
2-30
C++ Class for Sparse Matrix
class SparseMatrix; // forward declaration
class MatrixTerm {
friend class SparseMatrix
private:
int row, col, value;
};
class SparseMatrix {
...
private:
int Rows, Cols, Terms;
MatrixTerm smArray[MaxTerms];
}
2-31
Matrix Transpose
• Intuitive way:
for (each row i)
take element (i, j, value) and store it in (j, i, value) of
the transpose
row 1 1 2 2 4 4 3 5 3 4 2 3
column 3 5 3 4 2 3 1 1 2 2 4 4
value 3 4 5 7 2 6 3 4 5 7 2 6
• More efficient way:
for (all elements in column j)
place element (i, j, value) in position (j, i, value)
2-32
Efficient Way for Matrix
Transpose 0 0 0 0 0
000000
000304 00000
00002
M 000570 MT
000000 03506
00700
002600
04000
row 1 1 2 2 4 4 2 3 3 3 4 5
column 3 5 3 4 2 3 4 1 2 4 2 1
value 3 4 5 7 2 6 2 3 5 6 7 4 2-33
Transposing a Matrix
SparseMatrix SparseMatrix::Transpose()
// return the transpose of a (*this)
{
SparseMatrix b;
b.Rows = Cols; // rows in b = columns in a
b.Cols = Rows; // columns in b = rows in a
b.Terms = Terms; // terms in b = terms in a
if (Terms > 0) // nonzero matrix
{
int CurrentB = 0;
for (int c = 0; c < Cols; c++) // transpose by columns
for (int i = 0; i < Terms; i++)
// find elements in column c
if (smArray[i].col == c) {
b.smArray[CurrentB].row = c;
b.smArray[CurrentB].col = smArray[i].row;
b.smArray[CurrentB].value =
smArray[i].value;
CurrentB++;
}
} // end of if (Terms > 0)
return b;
} // end of transpose
2-34
Time Complexity
• Time Complexity:
O(terms  columns)
=O(rows  columns  columns)
• A better transpose function
– It first computes the number of nonzero elements
in each columns of matrix A before transposing to
matrix B. Then it determines the starting address
of each row for matrix B. Finally, it moves each
nonzero element from A to B.
2-35
Faster Matrix Transpose

000000 0 0 0 0 0 Step 1: #nonzero in row i of transpose

000304 00000 = #nonzero in column i of
000570 00002 original matrix
000000 03506 = [0, 0, 1, 3, 1, 1]
002600 00700
Step 2: Start of row i of transpose
04000
= size sum of rows 0,1,2, i-1 of
row 1 1 2 2 4 4 transpose

column 3 5 3 4 2 3 = [0, 0, 0, 1, 4, 5]
value 3 4 5 7 2 6 Step 3: Move elements, left to right,
from original list to transpose list
2-36
000000 00000
00000
Faster Matrix Transpose 000304
000570 00002
000000 03506
row 1 1 2 2 4 4 002600 00700
04000
column 3 5 3 4 2 3 rowStart =
value 3 4 5 7 2 6 [0, 0, 0, 1, 4, 5]

- 3 - - - - - 3 - - - 5 - 3 3 - - 5
- 1 - - - - - 1 - - - 1 - 1 2 - - 1
- 3 - - - - - 3 - - - 4 - 3 5 - - 4
rowStart = rowStart = rowStart =
[0, 0, 0, 2, 4, 5] [0, 0, 0, 2, 4, 6] [0, 0, 0, 3, 4, 6]

2-37
Time Complexity
Step 1: #nonzero in each row
O(terms)
Step2: Start address of each row
O(columns)
Step 3: Data movement
O(terms)
• Total time complexity:
O(terms + columns)= O(rows columns)

2-38
Matrix Multiplication
• Given A and B, where A is m  n and B is n  p,
the product matrix D = A  B has dimension m 
p.
• Let dij =D[i][j]
n 1
d ij  aik bkj
k 0

where 0 ≤ i ≤ m-1 and 0 ≤ j ≤ p -1.

2-39
Matrix Multiplication Example (1)
000000 000
000304 020
000
A56= 0 0 0 5 7 0 B63=
030
000000
047
002600
010
0 0 0
0 13 0
D53= A  B = 0 43 49
0 0 0
0 18 0 2-40
Matrix Multiplication Example (2)
A56 = B63=
row 1 1 2 2 4 4 row 1 3 4 4 5
column 3 5 3 4 2 3 column 1 1 1 2 1
value 3 4 5 7 2 6 value 2 3 4 7 1
D53= A  B =
row 1 2 2 4
column 1 1 2 1
value 13 43 49 18
2-41
String in C/C++
char c[] = {'B', 'C', 'D', '\0'};
char d[] = “BED"; // 4 bytes
• In C/C++, a string is represented as a character
array
0 1 2 3 4
B E D \0
• Internal representation
0 1 2 3 4
66 69 68 0 2-42
String in C
• General string operations include comparison
( 比較 ), string concatenation( 連接 ), copy,
insertion, string matching( 匹配 , 比對 ), printing
• Function in C: #include <string.h>
– strcat, strncat
– strcmp, strncmp
– strcpy, strncpy, strlen
– strchr, strtok, strstr, …
• #include <cstring> // in C++ for string.h
2-43
String Matching Problem
• Given a text string T of length n and a
pattern string P of length m, the exact string
matching problem is to find all occurrences
of P in T.
• Example: T=“AGCTTGCTA”
P=“GCT”
• Applications:
– Searching keywords in a file (Text Editor)
– Searching engines (Google)
– Database searching (GenBank)
2-44
KMP Algorithm for String Matching
• KMP algorithm
– Proposed by Knuth, Morris and Pratt
– Time complexity: O(m+n)

• More string matching algorithms (with source

codes):
http://www-igm.univ-mlv.fr/~lecroq/string/

2-45