START OF WEEK 4 of C <<< FILE TIMESTAMP >>> -The up to date file is in: /usr/courses/cps393/dwoit/courseNotes/ -If you are viewing your own copy, check it is up to date -If you are viewing from a link in the Course Outline, be aware it may be outdated. <<< Structures >>> -similar to NamedTuple in python -similar to using a class in Java just as group items of same type into: arrays can group items of dissimilar types into: structures struct s-name { type item1; type item2; . . . type itemN; } ; e.g., a struct to describe cars (in struct1.c) struct car { char make[40]; char model[40]; unsigned int year; float price; } ; struct car woit, chan1, chan2; //3 cars OR could declare variables in the struct definition, as in: struct car { char make[40]; char model[40]; unsigned int year; float price; } woit, chan1, chan2; //3 cars Assign woit's car: strcpy(woit.make, "Ferrari"); strcpy(woit.model, "California T"); woit.year = 2015; woit.price = 198190.00; Read in chan1's car: scanf("%s", chan1.make); //Porsche gets(chan1.model); //Carrera scanf("%u %f", &chan1.year, &chan1.price); //2013 440000 Can return a structure to a calling program: /*Source: struct6.c*/ #include struct complex { int r; int i; } ; struct complex ReadIt(void); int main(void) { struct complex X; X=ReadIt(); printf("%d + %di\n",X.r, X.i); return 0; } struct complex ReadIt(void) { struct complex temp; scanf("%d %d", &temp.r, &temp.i); return(temp); } data from temp *copied* into storage set aside for X HMWK: Rewrite the above programs using typedefs for complex numbers. Put functions WriteSum and MakeComplex, (along with anything else necessary) into a file called cmplx.c that can be compiled separately. Write a header file cmplx.h A program similar to this should then work. Compile it with cmplx.c and run it. #include "cmplx.h" void main(void) { complex X,Y; X=MakeComplex(1,2); Y=MakeComplex(3,4); WriteSum(X,Y); } <> 100 104 508 ------------------------ ... | | | | | ... ------------------------ c p struct complex { int r; int i; } c, *p; p=&c; (*p).r = 4; //Same as c.r=4; p->r = 4; //is alternate syntax 100 104 508 ------------------------ ... | 4 | | |100 | ... ------------------------ c p can pass a pointer-to-a-structure to a function instead of the structure itself -to change value of structure inside function -saves execution time/memory since structure could be huge but a ptr is usually 8 bytes (if just pass structure, a *copy* of it must be made--uses more time and memory) Note ReadIt and WriteIt print using different syntax because ReadIt has POINTER to complex, but WriteIt has complex. /*Source: struct8.c*/ #include struct complex { int r; int i; }; void ReadIt(struct complex *c); void WriteIt(struct complex p); int main(void) { struct complex A1, A2; ReadIt(&A1); WriteIt(A1); ReadIt(&A2); WriteIt(A2); return 0; } void ReadIt(struct complex *c) { printf("Enter complex: "); scanf("%d %d",&(c->r), &(c->i)); printf("Read in: %d + %di\n",c->r, c->i); //printf("Read in: %d + %di\n",(*c).r, (*c).i); } void WriteIt(struct complex c) { printf("Write it: %d + %di\n", c.r, c.i); } 100 104 ... 204 208 508 ------------------------------------------ ... | | | ... | | | | | ... ------------------------------------------ A1 A2 c /*Source: struct9.c*/ #include struct complex { int r; int i; }; void ScalarMult(int i, struct complex *p); void PrintComplex(struct complex *p); int main(void) { struct complex C={4,-2}; //struct complex C; C.r=4; C.i=-2; ScalarMult(3,&C); PrintComplex(&C); return 0; } void ScalarMult(int m, struct complex *p) { //pointer is required since mutating p p->r = p->r * m; p->i = p->i * m; } void PrintComplex(struct complex *c){ //pointer unnecessary since not mutating p //printf("%d + %di\n", c->r, c->i); printf("%d + %di\n", (*c).r, (*c).i); } HMWK: rewrite the above program using typedefs for complex. Write ConjugateComplex which turns a complex number into its conjugate (imaginary part multiplied by -1). Write a function called NegComplex turns a complex number into its negative (both imaginary and real parts multiplied by -1. <> structure named tm contains info about current time & date tm is defined in (man time.h) struct tm { int tm_sec; /*seconds, 0-60*/ int tm_min; /*minutes, 0-59*/ int tm_hour; /*hours, 0-23*/ int tm_mday; /*day of month, 1-31*/ int tm_mon; /*months since Jan, 0-11*/ int tm_year; /*years since 1900*/ int tm_wday; /*days since Sunday 0-6*/ int tm_yday; /*days since Jan 1, 0-365*/ int tm_isdst; /*daylight savings time flag*/ }; struct tm *localtime(time_t *time); //man localtime //time gets wall-clock time (precision in seconds): time_t time(time_t *time1); //man 2 time /*Source: tm1.c Purpose: to display current system time and date */ #include #include int main(void) { struct tm *systime; time_t t; t = time(NULL); systime = localtime(&t); printf("Time is %d:%d:%d\n", systime->tm_hour, systime->tm_min, systime->tm_sec); printf("Date is %d/%d/%d\n", systime->tm_mday, systime->tm_mon+1, systime->tm_year+1900); //since it is year - 1900 return 0; } For more precise time (down to nanoseconds) use clock_gettime() C has other structures to give programmer access to system information. e.g., dirent.h lets you access the linux filesystem (files, dirs, their perms, etc.) See entries.c It prints all entries in current directory div function from stdlib.h gives quotient and remainder <> struct evaluation { int tests; /*number of tests*/ int exam; /*non-0=yes, 0=no*/ int assigns; /*number of*/ int labs; /*number of*/ }; struct class { char CourseNum[10]; /*e.g., CPS590 */ char CourseName[80]; /*e.g., Intro to Operating Systems*/ struct evaluation eval; /*eval info*/ } c1, c2[10]; strcpy(c1.CourseNum, "CPS590"); c1.eval.assigns = 3; c2[0].eval.labs=6; struct7.c --Car program with new nested structure for dateBought struct7F.c --like struct7.c, but (a) reads cars from file carFile using function readCar, and (b) uses variable length array struct7FF.c --like struct7F.c, but function readCars reads all cars at once from file carFile. Simply illustrates passing more parameters to the read function. <<< Linked Lists >>> A list could be implemented any number of ways. One such way is a linked list. Generally, a linked list could be described as: ____ ______ _____ ______ ______ | -|-->|e1|-|-->|e2|-|--->|e3|-|--> .... --->|en|-| ---- ------ ------ ------ ------ List where ei is the ith element on the list. Therefore, the list a b c can be linked list: ____ ______ _____ ______ | -|-->|c |-|-->|b |-|--->|a |-| ---- ------ ------ ------ List A "null" pointer signifies end of linked list (NULL in stdlib.h) Data structure for the nodes: struct node { char ch; struct node *next; }; ------------------------------------------------------------------- from here on, may write "list" to mean "linked list" ------------------------------------------------------------------- /*Source list.c Making the list is done inefficiently here for illustration, but normally one would write a function, such as Add, so that a call such as Add(List,'a') would add an 'a' to the List */ #include #include typedef struct node NodeType; struct node { char ch; NodeType *next; //or: struct node *next; }; int main(void) { NodeType *Node, //a list node *List, //a list *ptr; //a temp var to move along a list, node by node List=NULL; // _____ // | - | The empty list, where "-" is null ptr // ----- // List Node=(NodeType *) malloc(sizeof(NodeType)); Node->ch='a'; // ____ ______ Node->next=NULL; // | -|-->|a |-| where "-" is null ptr // ---- ------ // Node printf("Node.ch: %c\n", Node->ch); //or (*Node).ch printf("Node.next: %p\n", Node->next); // ____ ______ List=Node; // | -|-->|a |-| printf("List.ch: %c\n", List->ch); // ---- ------ printf("List.next: %p\n", List->next); // List Node=(NodeType *) malloc(sizeof(NodeType)); Node->ch='b'; // ____ ______ Node->next=NULL; // | -|-->|b |-| // ---- ------ // Node Node->next=List; // ____ ______ _____ List=Node; // | -|-->|b |-|-->|a |-| // ---- ------ ------ // List /*print out list*/ printf("------------\nList is:\n------------\n "); for (ptr=List; ptr!=NULL; ) { printf(" %c ", ptr->ch); ptr=ptr->next; } printf("\n"); printf("------------\nDetail :\n------------\n"); for (ptr=List; ptr!=NULL; ) { printf("List.ch: %c\n", ptr->ch); printf("List.ch %p List.next: %p\n", &((*ptr).ch), (*ptr).next); ptr=ptr->next; } return 0; } << Adding to List >> Add(list, char) puts char on front of list /*Source add.h header file for add.c The #ifndef preprocessor directive is used so that the compiler will not see the struct definition twice (in case it is also included by another file too). Why? Later, we make search.h which also needs the struct definition. If we write a main that needs both add.h and search.h, compiler would get duplicate struct definitions which could cause an error */ #ifndef NodeTypeSeen #define NodeTypeSeen typedef struct node NodeType; struct node { char ch; NodeType *next; }; #endif void Add(NodeType **L, char c); /*Source add.c function to add a char to the front of a list */ #include #include #include "add.h" /*Note: need to pass address of L so that L can be modified. If just passed L, any changes to L inside function would be lost upon function return. e.g., calling add(List,ch) would not cause List to be changed in main after add returns */ void Add(NodeType **L, char c) { NodeType *new; new=(NodeType *) malloc(sizeof(NodeType)); //needs error checking new->ch=c; new->next=*L; *L=new; } /*Source addmain.c program to use function Add (in file add.c) to add to front of a list See ListAddAsciiArt for illustration of first 2 Adds */ #include #include "add.h" int main(void) { NodeType *Node, //a node *List, //a list *ptr; //a temp var to move along a list, node by node char ch; //char to add to front of list List=NULL; for (ch='a'; ch<'f';ch++) //add a b c d e, each to front of list Add(&List,ch); //need & so List can be changed printf("List is: "); /*print list*/ for (ptr=List; ptr!=NULL; ) { printf(" %c ", ptr->ch); ptr=ptr->next; } printf("\n"); return 0; } << Searching >> /*source: search.c Search a list to determine if given character is in list */ #include "search.h" //for NodeType definition #include //for NULL int Srch(NodeType *L, char item) { NodeType *p; for (p=L; p != NULL; p = p->next) if (p->ch == item) return 1; return 0; } Can modify addmain.c to do a search: /*Source addmainS.c compile: gcc addmainS.c add.c search.c */ #include #include #include "add.h" #include "search.h" int main(void) { NodeType *List, /*a list, like in scheme, except all char*/ *ptr; /*a temp var to move along a list, node by node*/ char ch; /*char to add to front of list*/ char item; /*char to search for*/ List=NULL; for (ch='a'; ch<'f';ch++) Add(&List,ch); printf("List is: "); for (ptr=List; ptr!=NULL; ) { printf(" %c ", ptr->ch); ptr=ptr->next; } printf("\n"); /*repeatedly search for a given item in list*/ printf("Enter char to search for (EOF to quit): "); item=getchar(); while (item!=EOF) { if ((Srch(List,item))==1) printf("found\n"); else printf("not found\n"); getchar(); //read enter key printf("Enter char to search for (EOF to quit): "); item=getchar(); } return 0; } HMWK: Write a version of Add that does not mutate (change) the list; instead, it should return a new list. The function prototype could be NodeType *Add(NodeType *L, char c); Optional HMWK: Write functions for first and rest as follows: first returns a copy of the first item on the list (error if empty list) rest returns a list that is the given list with the first item removed. (error if empty list). first should return a character and rest should return a list. HMWK: Write function InsertO which inserts a given item into a list, keeping the list in order. Write function SrchO which searches an ordered list for the given item. Note that if the item is not in the list, search can terminate as soon as it finds an item larger than the searched-for item. <<< Abstraction in C >>> -in CS, abstraction generally refers to the principle of: Hiding low-level details of implementation with higher-level interface -modularity helps accomplish this -ADT implementation provides information hiding and modularity to varying extents -user USES the ADT; programmer IMPLEMENTS the ADT e.g., strings in C -we (user) use string functions, such as strcmp, strlen -someone else (programmer) implemented the string functions/macros -ADTs in C (other than those supplied with OS): -programmer supplies -object code for functions/macros, etc. (.o files) -definitions of functions/macros, etc. (.h files) -user -writes code that #includes the programmer's .h, -compiles own code with programmer's .o file -function source code (.c) "hidden" from user USER PROGRAM CODE, using a supplied list ADT: /*Source userlistADT.c compile: gcc userlistADT.c listADT.o */ #include #include #include "listADT.h" int main(void) { List L; init(&L); add(&L,'a'); add(&L,'b'); add(&L,'c'); print(L); printf("Length is %d\n",length(L)); return 0; } PROGRAMMER CODE (list implementer): /*Source listADT.h lists are type List */ typedef struct node NodeType; struct node { char ch; NodeType *next; }; typedef struct { int length; NodeType *head; } List; void init(List *L) ; void add(List *L, char c) ; void print(List L) ; int length(List L) ; /*Source listADT.c User cannot see this file. User only gets the listADT.o file User compiles listADT.o with their main to use a list ADT */ #include #include #include "listADT.h" void init(List *L) { L->length=0; L->head=NULL; } int length(List L) { return L.length; } void add(List *L, char c) { NodeType *new; new=(NodeType *) malloc(sizeof(NodeType)); //error-check this new->ch=c; new->next=L->head; L->head=new; L->length++; } void print(List L) { int i; NodeType *p; printf("List is: "); for (i=0,p=L.head; inext) { printf(" %c ", p->ch); } putchar('\n'); } << Hiding the Implementation Details >> Above code has NOT COMPLETELY hidden list ADT implmenetation: -User can see List data structure in listADT.h -User can mess around with list directly -User NOT forced to only operate on List via provided functions e.g., user may try to -shorten list by setting some pointer to NULL -add a node between two other nodes -User might accidentally corrupt list. If programmer selling Off-The-Shelf code to a 3rd party (user), they want to COMPLETELY hide implementation details from user, so -user can't "see" the data structure itself (so can't mess around with it), -user is forced to access data structure only through the given functions. How to do this in C? Typically: -User only gets ADT.h and ADT.o (NOT ADT.c), and documentation saying how to use the ADT -User includes ADT.h in own program -User compiles own program with ADT.o -ADT.h has no ADT implementation details, only (void *) -ADT.[co] has ADT implementation details (structs etc), and casts (void *) to (ADT *) as necessary within ADT functions /*Source: main.c example of how to hide details of ADT from user by keeping struct details out of complex.h, and only in complex.c */ #include #include #include "complex.h" int main (void) { complex *m; set(&m,7,2); print(m); return 0; } //Source complex.h typedef void *complex; void set(complex **, int, int ) ; void print(complex *a) ; //Source complex.c #include #include #include "complex.h" typedef struct { int i; int j; } priv_complex; void set(complex **a, int v, int w) { priv_complex *new; new=(priv_complex *)malloc(sizeof(priv_complex)); (*new).i=v; (*new).j=w; (*a)=(complex *)new; } void print(complex *a) { printf("%d+%di\n", (*(priv_complex *)a).i, (*(priv_complex *)a).j); }