ImageVerifierCode 换一换
格式:PPT , 页数:54 ,大小:744.50KB ,
资源ID:379641      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-379641.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(Chapter 2 Arrays and Structures.ppt)为本站会员(registerpick115)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

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.),

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1