Chapter 2 Arrays and Structures.ppt

1、Chapter 2 Arrays and Structures,Instructors: C. Y. Tang and J. S. Roger Jang,All the material are integrated from the textbook “Fundamentals of Data Structures in C“ and some supplement from the slides of Prof. Hsin-Hsi Chen (NTU).,Outline,The array as an abstract data type Structures and unions The

2、 polynomial abstract data type The sparse matrix abstract data type Representation of multidimensional arrays The string abstract data type,Outline,The array as an abstract data type Structures and unions The polynomial abstract data type The sparse matrix abstract data type Representation of multid

3、imensional arrays The string abstract data type,Arrays,Array: a set of index and valuedata structureFor each index, there is a value associated withthat index.representation (possible)implemented by using consecutive memory.,Abstract Data Type Array,Structure Array is objects : a set of pairs where

4、for each value of index there is a value from the set item.functions:Array Create (j, list) : an array of j dimensions, where list is a j-tuple whose ith element is the size of the ith dimension.Item Retrieve (A, i) : If (i index) return the item indexed by i in array A,else return error.Array Store

5、 (A, i, x) : If (i index) insert and return the new array, else return error.end Array,Implementation in C,int list5, *plist5;,Assume the memory address = 1414, list0 = 6, list2 = 8, plist3 = list = 1414printf(“%d”, list); / 1414, the variable “list” is the pointer to an intprintf(“%d”, / 6,Example:

6、 One-dimensional array accessed by address,call print1(&one0, 5),void print1(int *ptr, int rows) /* print out a one-dimensional array using a pointer */int i;printf(“Address Contentsn”);for (i=0; i rows; i+)printf(“%8u%5dn”, ptr+i, *(ptr+i);printf(“n”); ,int one = 0, 1, 2, 3, 4; Goal: print out addr

7、ess and value,Example: Array program,#define MAX_SIZE 100float sum(float , int);float inputMAX_SIZE, answer;int i;void main (void)for (i = 0; i MAX_SIZE; i+)inputi = i;answer = sum(input, MAX_SIZE);printf(“The sum is: %fn“, answer);float sum(float list, int n)int i;float tempsum = 0;for (i = 0; i n;

8、 i+)tempsum += listi;return tempsum; ,Result : The sum is: 4950.000000,Outline,The array as an abstract data type Structures and unions The polynomial abstract data type The sparse matrix abstract data type Representation of multidimensional arrays The string abstract data type,Structures (Records),

9、struct char name10; / a name that is a character arrayint age; / an integer value representing the age of the personfloat salary; / a float value representing the salary of the individual person;strcpy(person.name, “james”);person.age=10;person.salary=35000;,An alternate way of grouping data that pe

10、rmits the data to vary in type. Example:,Create structure data type,typedef struct human_being char name10;int age;float salary;ortypedef struct char name10;int age;float salary human_being;human_being person1, person2;,Example: Embed a structure within a structure,typedef struct int month;int day;i

11、nt year; date;typedef struct human_being char name10;int age;float salary;date dob;person1.dob.month = 2; person1.dob.day = 11; person1.dob.year = 1944;,Unions,Similar to struct, but only one field is active.Example: Add fields for male and female. typedef struct sex_type enum tag_field female, male

12、 sex;union int children;boolean beard; u;typedef struct human_being char name10;int age;float salary;date dob;sex_type sex_info;,human_being person1, person2; person1.sex_info.sex = male; person1.sex_info.u.beard = FALSE; person2.sex_info.sex = female; person2.sex_info.u.children = 4;,Self-Referenti

13、al Structures,One or more of its components is a pointer to itself.typedef struct list char data;list *link;list item1, item2, item3; item1.data=a; item2.data=b; item3.data=c; item1.link=item2.link=item3.link=NULL;,Construct a list with three nodes item1.link= malloc: obtain a node,Outline,The array

14、 as an abstract data type Structures and unions The polynomial abstract data type The sparse matrix abstract data type Representation of multidimensional arrays The string abstract data type,Implementation on other data types,Arrays are not only data structures in their own right, we can also use th

15、em to implement other abstract data types. Some examples of the ordered (linear) list :- Days of the week: (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday).- Values in a deck of cards: (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King)- Floors of a building: (basement, lobby, mezza

16、nine, first, second) Operations on lists : - Finding the length, n , of the list.- Reading the items from left to right (or right to left).- Retrieving the ith element from a list, 0 i n.- Replacing the ith item of a list, 0 i n.- Inserting a new item in the ith position of a list, 0 i n.- Deleting

17、an item from the ith position of a list, 0 i n.,Abstract data type Polynomial,Structure Polynomial is objects: ; a set of ordered pairs of where ai in Coefficients and ei in Exponents, ei are integers = 0 functions: for all poly, poly1, poly2 Polynomial, coef Coefficients, expon Exponents Polynomial

18、 Zero( ) := return the polynomial, p(x) = 0 Boolean IsZero(poly) := if (poly) return FALSE else return TRUE Coefficient Coef(poly, expon) := if (expon poly) return its coefficient else return Zero Exponent Lead_Exp(poly) := return the largest exponent in poly Polynomial Attach(poly,coef, expon) := i

19、f (expon poly) return error else return the polynomial poly with the term inserted Polynomial Remove(poly, expon) := if (expon poly) return the polynomial poly with the term whose exponent is expon deleted else return error Polynomial SingleMult(poly, coef, expon) := return the polynomial poly coef

20、xexpon Polynomial Add(poly1, poly2) := return the polynomial poly1 +poly2 Polynomial Mult(poly1, poly2) := return the polynomial poly1 poly2 End Polynomial,Two types of Implementation for the polynomial ADT,Type I :#define MAX_DEGREE 1001 typedef struct int degree;float coefMAX_DEGREE; polynomial;po

21、lynomial a;a.degree = na. coefi = an-i , 0 i n.,Type II : MAX_TERMS 1001 /* size of terms array */ typedef struct float coef; int expon; polynomial; polynomial termsMAX_TERMS; int avail = 0; /* recording the available space*/,advantage: easy implementation disadvantage: waste space when sparse,stora

22、ge requirements: start, finish, 2*(finish-start+1) nonparse: twice as much as Type Iwhen all the items are nonzero,PA=2x1000+1,PB=x4+10x3+3x2+1,Polynomials adding of Type I,/* d =a + b, where a, b, and d are polynomials */ d = Zero( ) while (! IsZero(a) insert any remaining terms of a or b into d,/

23、case -1: Lead_exp(a) Lead_exp(b),/ case 0: Lead_exp(a) = Lead_exp(b),/ case 1: Lead_exp(a) Lead_exp(b),Polynomials adding of Type II,void padd (int starta, int finisha, int startb, int finishb,int * startd, int *finishd) /* add A(x) and B(x) to obtain D(x) */ float coefficient; *startd = avail; whil

24、e (starta b expon */ attach(termsavail, termsstarta.coef, termsstarta.expon); starta+; avail+; /* add in remaining terms of A(x) */ for( ; starta = finisha; starta+) attach(termsavail, termsstarta.coef, termsstarta.expon);avail+; /* add in remaining terms of B(x) */ for( ; startb = finishb; startb+)

25、 attach(termsavail, termsstartb.coef, termsstartb.expon); avail+; *finishd =avail -1; ,Outline,The array as an abstract data type Structures and unions The polynomial abstract data type The sparse matrix abstract data type Representation of multidimensional arrays The string abstract data type,The s

26、parse matrix abstract data type,Matrix a Nonzero rate : 15/15 Dense !,Matrix b Nonzero rate : 8/36 Sparse !,Abstract data type Sparse_Matrix,Structure Sparse_Matrix is objects: a set of triples, , where row and column are integers and form a unique combination, and value comes from the set item. fun

27、ctions: for all a, b Sparse_Matrix, x item, i, j, max_col, max_row index Sparse_Marix Create(max_row, max_col) := return a Sparse_matrix that can hold up to max_items = max _row max_col and whose maximum row size is max_row and whose maximum column size is max_col.Sparse_Matrix Transpose(a) := retur

28、n the matrix produced by interchanging the row and column value of every triple. Sparse_Matrix Add(a, b) := if the dimensions of a and b are the same return the matrix produced by adding corresponding items, namely those with identical row and column values. else return error Sparse_Matrix Multiply(

29、a, b) := if number of columns in a equals number of rows in b return the matrix d produced by multiplying a by b according to the formula: d i j = (aikbkj) where d (i, j) is the (i,j)th element else return error.,Sparse_Matrix Create and transpose,#define MAX_TERMS 101 /* maximum number of terms +1*

30、/ typedef struct int col; int row; int value; term; term aMAX_TERMSfor each row i (or column j) take element and store it in element of the transpose.,Sparse matrix and its transpose stored as triples,Difficulty:what position to put ?,Transpose of a sparse matrix in O(columns*elements),void transpos

31、e (term a, term b) /* b is set to the transpose of a */ int n, i, j, currentb; n = a0.value; /* total number of elements */ b0.row = a0.col; /* rows in b = columns in a */ b0.col = a0.row; /*columns in b = rows in a */ b0.value = n; if (n 0) /*non zero matrix */ currentb = 1; for (i = 0; i a0.col; i

32、+) /* transpose by columns in a */ for( j = 1; j = n; j+) /* find elements from the current column */ if (aj.col = i) /* element is in current column, add it to b */ bcurrentb.row = aj.col; bcurrentb.col = aj.row; bcurrentb.value = aj.value; currentb+ ,Analysis and improvement,Discussion: compared w

33、ith 2-D array representationO(columns*elements) vs. O(columns*rows)#(elements) columns * rows, when the matrix is not sparse.O(columns*elements) O(columns*columns*rows)Problem: Scan the array “columns” times.Improvement:Determine the number of elements in each column of the original matrix. =Determi

34、ne the starting positions of each row in the transpose matrix.,Transpose of a sparse matrix in O(columns + elements),void fast_transpose(term a , term b ) /* the transpose of a is placed in b */ int row_termsMAX_COL, starting_posMAX_COL; int i, j, num_cols = a0.col, num_terms = a0.value; b0.row = nu

35、m_cols; b0.col = a0.row; b0.value = num_terms; if (num_terms 0) /*nonzero matrix*/ for (i = 0; i num_cols; i+) row_termsi = 0; for (i = 1; i = num_terms; i+) row_termsai.col+ starting_pos0 = 1; for (i =1; i num_cols; i+) starting_posi=starting_posi-1 +row_terms i-1;for (i=1; i = num_terms, i+) j = s

36、tarting_posai.col+; bj.row = ai.col; bj.col = ai.row; bj.value = ai.value; ,Sparse matrix multiplication,void mmult (term a , term b , term d ) /* multiply two sparse matrices */ int i, j, column, totalb = b.value, totald = 0; int rows_a = a0.row, cols_a = a0.col, totala = a0.value; int cols_b = b0.

37、col, int row_begin = 1, row = a1.row, sum =0; int new_bMAX_TERMS3; if (cols_a != b0.row) fprintf (stderr, “Incompatible matricesn”); exit (1); fast_transpose(b, new_b); /* set boundary condition */ atotala+1.row = rows_a; new_btotalb+1.row = cols_b; new_btotalb+1.col = 0; for (i = 1; i = totala; ) c

38、olumn = new_b1.row; for (j = 1; j = totalb+1;) /* mutiply row of a by column of b */ if (ai.row != row) storesum(d, column =new_bj.row ,else if (new_bj.row != column)storesum(d, ,storesum function,void storesum(term d , int *totald, int row, int column, int *sum) /* if *sum != 0, then it along with

39、its row and column position is stored as the *totald+1 entry in d */ if (*sum) if (*totald MAX_TERMS) d+*totald.row = row; d*totald.col = column; d*totald.value = *sum; else fprintf(stderr, ”Numbers of terms in product exceed %dn”, MAX_TERMS); exit(1); ,Analyzing the algorithm,cols_b * termsrow1 + t

40、otalb +cols_b * termsrow2 + totalb + +cols_b * termsrowrows_a + totalb = cols_b * (termsrow1 + termsrow2 + + termsrowrows_a) +rows_a * totalb = cols_b * totala + row_a * totalbO(cols_b * totala + rows_a * totalb),Compared with classic multiplication algorithm,for (i =0; i rows_a; i+) for (j=0; j col

41、s_b; j+) sum =0; for (k=0; k cols_a; k+) sum += (aik *bkj); dij =sum; ,O(rows_a * cols_a * cols_b),mmult vs. classic O(cols_b * totala + rows_a * totalb) vs. O(rows_a * cols_a * cols_b),Matrix-chain multiplication,n matrices A1, A2, , An with sizep0 p1, p1 p2, p2 p3, , pn-1 pnTo determine the multip

42、lication order such that # of scalar multiplications is minimized. To compute Ai Ai+1, we need pi-1pipi+1 scalar multiplications.e.g. n=4, A1: 3 5, A2: 5 4, A3: 4 2, A4: 2 5(A1 A2) A3) A4, # of scalar multiplications: 3 * 5 * 4 + 3 * 4 * 2 + 3 * 2 * 5 = 114(A1 (A2 A3) A4, # of scalar multiplications

43、: 3 * 5 * 2 + 5 * 4 * 2 + 3 * 2 * 5 = 100(A1 A2) (A3 A4), # of scalar multiplications: 3 * 5 * 4 + 3 * 4 * 5 + 4 * 2 * 5 = 160,Let m(i, j) denote the minimum cost for computing Ai Ai+1 AjComputation sequence :Time complexity : O(n3),Matrix-chain multiplication (cont.),Outline,The array as an abstrac

44、t data type Structures and unions The polynomial abstract data type The sparse matrix abstract data type Representation of multidimensional arrays The string abstract data type,Representation of multidimensional arrays,The internal representation of multidimensional arrays requires more complex addr

45、essing formulas. aupper0 upper1uppern-1= #(elements of a) = There are two ways to represent multidimensional arrays:row major order and column major order.(row major order stores multidimensional arrays by rows)Ex. Aupper0upper1 : upper0 rows (row0, row1, ,rowupper0-1),each row containing upper1 elementsAssume that is the address of A00 the address of Ai0 : + i *upper1 Aij : + i *upper1+j,Representation of Multidimensional Arrays (cont.),