Chapter 2 Arrays and Structures.ppt
《Chapter 2 Arrays and Structures.ppt》由会员分享,可在线阅读,更多相关《Chapter 2 Arrays and Structures.ppt(54页珍藏版)》请在麦多课文档分享上搜索。
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,/
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CHAPTER2ARRAYSANDSTRUCTURESPPT
