inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 4 Strings Structs Review Arrays Arrays are almost identical to pointers char string and char string are nearly identical declarations They differ in subtle ways incrementing declaration of filled arrays Key Difference an array variable is a CONSTANT pointer to the first element ar i ar i 2005 06 23 Andy Carle A Carle Summer 2005 UCB CS 61C L4 Structs 1 A Carle Summer 2005 UCB CS 61C L4 Structs 2 Review Arrays and Pointers Review Common C Errors Array size n want to access from 0 to n 1 There is a difference between assignment and equality a b is assignment a b is an equality test Array Indexing Versions Pointer Indexing Version define ARSIZE 10 int ar ARSIZE int i 0 sum 0 define ARSIZE 10 int ar ARSIZE int p ar q ar 10 int sum 0 while i ARSIZE sum ar i while p q sum p or while i ARSIZE sum ar i C allows 1 past end of array CS 61C L4 Structs 3 A Carle Summer 2005 UCB This is one of the most common errors for beginning C programmers Precedence Rules int a 1 2 3 4 a 1 CS 61C L4 Structs 4 Topic Outline C Strings 1 3 Strings A string in C is just an array of characters Handles char string abc Structs How do you tell how long a string is Heap Allocation Intro Last character is followed by a 0 byte null terminator int strlen char s int n 0 while s n 0 n 0 return n Linked List Example CS 61C L4 Structs 5 A Carle Summer 2005 UCB A Carle Summer 2005 UCB CS 61C L4 Structs 6 A Carle Summer 2005 UCB C Strings Headaches 2 3 C String Standard Functions 3 3 One common mistake is to forget to allocate an extra byte for the null terminator int strlen char string More generally C requires the programmer to manage memory manually unlike Java or C int strcmp char str1 char str2 compute the length of string When creating a long string by concatenating several smaller strings the programmer must insure there is enough space to store the full string return 0 if str1 and str2 are identical how is this different from str1 str2 What if you don t know ahead of time how big your string will be char strcpy char dst char src copy the contents of string src to the memory at dst and return dst The caller must ensure that dst has enough memory to hold the data to be copied String constants are immutable char f abc f 0 char f abc f 0 illegal Because section of mem where abc lives is immutable Works Because in declaration c copies abc into space allocated for f A Carle Summer 2005 UCB CS 61C L4 Structs 7 A Carle Summer 2005 UCB CS 61C L4 Structs 8 Pointers to pointers 1 4 review Pointers to pointers 2 4 review Sometimes you want to have a procedure increment a variable Solved by passing in a pointer to our subroutine What gets printed Now what gets printed void AddOne int x x x 1 void AddOne int p p p 1 y 5 int y 5 AddOne y printf y d n y y 6 int y 5 AddOne y printf y d n y A Carle Summer 2005 UCB CS 61C L4 Structs 9 A Carle Summer 2005 UCB CS 61C L4 Structs 10 Pointers to pointers 3 4 Pointers to pointers 4 4 But what if what you want changed is a pointer Solution Pass a pointer to a pointer called a handle declared as h What gets printed Now what gets printed void IncrementPtr int p p 1 p int A 3 50 60 70 int q A IncrementPtr q printf q d n q CS 61C L4 Structs 11 void IncrementPtr int h q 60 h h 1 q Aq q 50 Aq 50 60 70 A Carle Summer 2005 UCB int A 3 50 60 70 int q A IncrementPtr q printf q d n q CS 61C L4 Structs 12 50 60 70 A Carle Summer 2005 UCB C structures Overview 1 3 C structures Pointers to them 2 3 A struct is a data structure composed of simpler data types The C arrow operator dereferences and extracts a structure field with a single operator Like a class in Java C but without methods or inheritance Don t get hung up on this comparison struct point int x int y void PrintPoint struct point p printf d d p x p y CS 61C L4 Structs 13 A Carle Summer 2005 UCB How big are structs 3 3 Recall C operator sizeof which gives size in bytes of type or variable The following are equivalent struct point p printf x is d n p x printf x is d n p x CS 61C L4 Structs 14 A Carle Summer 2005 UCB Dynamic Memory Allocation 1 4 C has operator sizeof which gives size in bytes of type or variable Assume size of objects can be misleading is bad style so use sizeof type How big is sizeof p struct p char x int y Many years ago an int was 16 bits and programs assumed it was 2 bytes 5 bytes 8 bytes Compiler may word align integer y CS 61C L4 Structs 15 A Carle Summer 2005 UCB CS 61C L4 Structs 16 A Carle Summer 2005 UCB Dynamic Memory Allocation 2 4 Dynamic Memory Allocation 3 4 To allocate room for something new to point to use malloc with the help of a typecast and sizeof Once malloc is called the memory location might contain anything so don t use it until you ve set its value ptr int malloc sizeof int Now ptr points to a space somewhere in memory of size sizeof int in bytes int simply tells the compiler what will go into that space called a typecast malloc is almost never used for 1 var After dynamically allocating space we must dynamically free it free ptr Use this command to clean up OS keeps track of size to free ptr int malloc n sizeof int This allocates an array of n integers CS 61C L4 Structs 17 A Carle Summer 2005 UCB CS 61C L4 Structs 18 A Carle Summer 2005 UCB Dynamic Memory Allocation 4 4 Binky Pointer Video thanks to NP SU Malloc does not always succeed System could be out of memory An error occurred during the memory request Operating system just doesn t like you today Always check the pointer you get back to make sure it is not NULL int p if p int malloc 10 sizeof int NULL do something to recover CS 61C L4 Structs 19 A Carle Summer 2005 UCB Linked List Example A Carle Summer 2005 UCB CS 61C L4 Structs 20 Linked List Example Let s look at an example of using structures pointers malloc and free to implement a linked list of strings struct Node …
View Full Document
Unlocking...