1 ECE 15B COMPUTER ORGANIZATION Dr. Rahul Singh!Lecture 13!Strings, Lists & Stacks!May 14, 2009 Electrical and Computer Engineering University of California, Santa Barbara!Announcements!• HW #3!• Due next Friday, May 15 at 5:00 PM in HFH!• Project #2 !• Due May 29 at 5:00 PM!• Project #3!• Assigned next Thursday, May 19!• Due June 5 at 5:00 PM!• Quiz #2!• In class, next Thursday, May 21!• Covers up until todayʼs lecture (#13)!May 14, 2009!Lecture 13: Strings, Lists & Stacks!1!Electrical and Computer Engineering University of California, Santa Barbara!Review: More C Pointer Dangers!• Declaring a pointer just allocates space to hold the pointer – it does not allocate something to be pointed to!!• Local variables in C are not initialized!• they may contain anything.!• What does the following code do?!void f(){! int* x;! *x = 5;!}!May 14, 2009!2!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Review: Pointers & Allocation!• After declaring a pointer:!int *ptr;!• ptr doesnʼt actually point to anything yet. !• We can either:!• make it point to something that already exists, or!• allocate room in memory for something new that it will point to… (this lecture)!May 14, 2009!3!Lecture 13: Strings, Lists & Stacks!2 Electrical and Computer Engineering University of California, Santa Barbara!Review: Pointers & Allocation!• Pointing to something that already exists:!int *ptr, var1, var2; ! !!!var1 = 5;!ptr = &var1;!var2 = *ptr;!• var1 and var2 have room implicitly allocated for them.!May 14, 2009!4!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Review: Arrays!• Declaration!int ar[2];!• declares a 2-element integer array!int ar[] = {795, 635};!• declares and fills a 2-element integer array.!• Accessing elements!ar[num];!• returns the numth element!May 14, 2009!5!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Review: Arrays!• Arrays are (almost) identical to pointers!char *string and char string[] !• Nearly identical declarations!• They differ in very subtle ways: !• incrementing, declaration of filled arrays!• Key Concept: An array variable is a pointer to the first element.!May 14, 2009!6!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Review: Arrays!• Consequences:!• ar is a pointer!• ar[0] is the same as *ar!• ar[2] is the same as *(ar+2)!• We can use pointer arithmetic to access arrays more conveniently.!• Declared arrays are only allocated while the scope is valid!char *foo() {" char string[32]; ...;" return string;}!• above is incorrect!May 14, 2009!7!Lecture 13: Strings, Lists & Stacks!3 Electrical and Computer Engineering University of California, Santa Barbara!Arrays!• Array size n; want to access from 0 to n-1, but test for exit by comparing to address one element past the array!int a[10], *p, *q, sum = 0;! ..."p = &a[0]; q = &a[10];"while (p != q)" /* sum = sum + p*; p = p + 1; */!! sum += *p++;!• Is this legal?!• C defines that one element past end of array must be a valid address!• i.e., not cause a bus error or an address error!May 14, 2009!8!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Arrays!• Array size n; want to access from 0 to n-1, so you should use counter AND utilize a constant for declaration & incr!• Wrong!int i, a[10];!for(i = 0; i < 10; i++){ ... }!• Right !#define ARRAY_SIZE 10!int i, a[ARRAY_SIZE];!for(i = 0; i < ARRAY_SIZE; i++){ ... }!• Why? SINGLE SOURCE OF TRUTH!• Youʼre utilizing indirection !• avoiding maintaining two copies of the number 10!May 14, 2009!9!Lecture 13: Strings, Lists & Stacks!Electrical and Computer Engineering University of California, Santa Barbara!Arrays!• Pitfall: An array in C does not know its own length, and bounds are not checked!!• Consequence: !• We can accidentally access off the end of an array.!• We must pass the array and its size to a procedure which is going to traverse it.!• Segmentation faults and bus errors:!• These are VERY difficult to find, so be careful.!May 14, 2009!Lecture 13: Strings, Lists & Stacks!10!Electrical and Computer Engineering University of California, Santa Barbara!Pointers to Pointers!• But what if what you want changed is a pointer?!• What gets printed?!May 14, 2009!Lecture 13: Strings, Lists & Stacks!11!void IncrementPtr(int *p) { p = p + 1; } int A[3] = {50, 60, 70}; int *q = A; IncrementPtr(q); printf(“*q = %d\n”, *q); 50 60 70 A q4 Electrical and Computer Engineering University of California, Santa Barbara!Pointers to Pointers!• Solution! Pass a pointer to a pointer!• This is called a handle !• Declared as **h!• Now what gets printed?!May 14, 2009!Lecture 13: Strings, Lists & Stacks!12!void IncrementPtr(int **h) { *h = *h + 1; } int A[3] = {50, 60, 70}; int *q = A; IncrementPtr(&q); printf(“*q = %d\n”, *q); *q = 60 50 60 70 A q q Electrical and Computer Engineering University of California, Santa Barbara!C Strings!• A string in C is just an array of characters.!char string[] = “abc”;!• How do you tell how long a string is?!• Last character is followed by a 0 byte (null terminator) ! !!!!!May 14, 2009!Lecture 13: Strings, Lists & Stacks!13!int strlen(char s[])!{! int n = 0;! while (s[n] != 0) !! n++;! return n;!}!Electrical and Computer Engineering University of California, Santa Barbara!C Strings Headaches!• One common mistake is to forget to allocate an extra byte for the null terminator.!• More generally, C requires the programmer to manage memory manually (unlike Java or C++).!• When creating a long string by concatenating several smaller strings, the programmer must insure there is enough space to store the full string!!• What if you donʼt know ahead of time how big your string will be?!May 14, 2009!Lecture 13: Strings, Lists & Stacks!14!Electrical and Computer Engineering University of California, Santa Barbara!Copying strings!• Why not say:!void copy (char sTo[ ], char sFrom[ ]) {" sTo =