CS115 Study Guide - Final Guide: Substring, Data Definition Language, Association List

830 views10 pages
Published on 2 Feb 2013
Course
Professor
Computer Science 115 – SOS Final Exam Review
!
1!
Tutor: Jumana Bahrainwala (jzbahrai@uwaterloo.ca)
Coordinator: Erin Vanderstoep (evanders@uwaterloo.ca)
STRUCTURES
A structure bundles data in a package together
Serves as a useful way to refer to data you define
Defining a structure is the first step (they usually do this for you)
Gives three useful functions
Note: The contract should have the name of the structure rather than
“structure”
To define a structure:
(define-struct sname (field1 field2.....))
Doing this gives you three functions:
make-sname ;constructor
sname-field1, sname-field2.... ;selectors
sname? ;type predicate
o Basically this is saying that you have created a structure called "sname" that
has properties defined in f1....fn
Structure Template
(define (function-name a-struct)
... (structure-f1 a-struct)...
... (structure-f2 a-struct)...
...
... (structure-fn a-struct)...)
A Data Definition: is a comment specifying the types of data
;;a posn in a structure (make-posn xcoord ycoord), where
;;xcoord is a number
;;ycoord is a number
Structure Definitions: show what each item represents
(define-struct contact (name email_address))
;; A contact is a structure (make-contact n e) where
;; n is a non
empty string representing a person's name and
;; e is a non
empty string representing a person's email address.
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 10 pages and 3 million more documents.

Already have an account? Log in
Computer Science 115 – SOS Final Exam Review
!
2!
LISTS
Formal Definition
A list is either:
empty or
(cons f r), where f is a value and r is a list
Examples of Lists in Scheme:
=> (cons ‘a (cons ‘b (cons ‘c (cons ‘d empty))))
=> empty
=> (list ‘a ‘b ‘c ‘c)
List Template
(define (mylist alist)
(cond
[(empty? alist)...]
[(cons? alist) ...]))
Difference between Structures and Lists:
Structures are easier to select data
Lists are better for recursion
INTRODUCTION TO RECURSION
Base Case: The starting and ending point of the function. The first thing that
the function checks in an “if” case. Function stops recursing when the base
case is true.
Recursive Part: Only if your base case fails. Ask “What do you want to change
if your base case fails?” Keep doing this until your base case passes.
A general recursive template
(define (my-recurse int) Defining Base Case
(cond
[(base-case? int) ...]
[else ...... (my-recurse ......)]))
Store/Alter the variable Re-apply function on the changed variable
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 10 pages and 3 million more documents.

Already have an account? Log in
Computer Science 115 – SOS Final Exam Review
!
3!
Problem 1
Give the structure templates for the following structures. Then, define a
function that consumes a list of CD structures and produces the total price,
using the template for CD.
(define-struct movie (title producer))
(define-struct CD (artist title price))
Solution
(define (my-movie-fn a-movie)
...(movie-title a-movie)...
...(movie-producer a-movie)...)
(define (my-CD-fn a-CD)
...(CD-artist a-CD)...
...(CD-title a-CD)...
...(CD-price a-CD)...)
(define (total-price aloCD)
(cond
[(empty? aloCD) 0]
[else (+ (CD-price (first aloCD)) (total-price (rest aloCD)))]))
___________________________________________________________________________
:: why did we choose this particular base case? We want the function to stop
once we have added up ALL the prices. So we need to keep going until the
list is empty. When it is empty, we aren't adding any price, so just add 0 to
our price total.
:: Or you can think about it another way. If we had an empty list in there, there
would be no prices to add, and our total price is zero.
LIST OF LISTS
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 10 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Grade+

Unlimited access to all notes and study guides.

Grade+All Inclusive
$10 USD/m
You will be charged $120 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.