CS23
int f(int a[], int l) { int i; int m; for (m = 0, i = 0; i < l; i++) if (a[i] < a[m]) m = i; return a[m]; }
Pre-condition: a is an int array with l elements.
Post-condition: f() returns the smallest value in a.
Invariant: a[m]
is the smallest value in a[0]
through
a[i - 1]
.
Sketch: Modular programming uses a control abstraction and is a top-down style. Very difficult to achieve meaningful data hiding.
Object-oriented programming is a bottom-up approach that uses data abstraction: data has strictly defined operations which can be performed and data can only be modified through this narrow interface. The implementation is completely hidden.
Sketch: recursion certainly uses more memory than an iterative solution (for the stack frames). It is time efficient for some things (raising an integer to a power, binary search) and very time inefficient for other things (Fibonacci sequence, Towers of Hanoi).
struct listItem { listItem* next; int value; }; typedef listItem* list;
Write a function which takes as arguments two ascending sorted linked lists and merges them to create a single ascending sorted linked list. The two original lists should no longer exist after this operation. Here is the function prototype:
list* SortedMerge(list& a, list& b);
Note that the return type is a small typo.
// a and b are reference parameters so that we can empty them out. list SortedMerge(list& a, list&b) { list merged; // Points to beginning of merged list. list temp; // Points to end of merged list. // Get the merged list started. if (a == NULL && b == NULL) // Nothing to do. return NULL; // b has smallest value. else if (a != NULL && b != NULL && b->value < a->value || a == NULL) { merged = b; b = b->next; } else // a has smallest value. { merged = a; a = a->next; } temp = merged; temp->next = NULL; while (a != NULL && b!= NULL) // Compare first item of each list. { if (a->value < b->value) { temp->next = a; a = a->next; } else { temp->next = b; b = b->next; } temp = temp->next; temp->next = NULL; } if (a != NULL) // Append remainder of a to merged list. { temp->next = a; a = NULL; // a is now empty. } else // Append remainder of b and empty. { temp->next = b; b = NULL; } return merged; }
class Stack { int *s; int len; int top; public: Stack(int length); ~Stack(); void Push(int val); int Pop(void); inline int Empty(void) { return top == 0; } inline int Full(void) { return top == len; } }; Stack::Stack(int length) { assert (length > 0); s = new int[length]; assert (s != NULL); len = length; top = 0; } Stack::~Stack() { delete [] s; s = NULL; } void Stack::Push(int val) { assert (!Full()); s[top++] = val; } int Stack::Pop(void) { assert (!Empty()); return s[--top]; }