Unformatted text preview:

1CMSC 212 – S07 (lect 11)Announcementsz Program #3– Available soonz Exam #1 – Thursday, March 8, 6:00 – 7:30 in Armory 0126– Makeup Exam Friday March 9, 2:00 PM – room TBA2CMSC 212 – S07 (lect 11)Graphs - Directedz In a Graph– there can be an arbitrary number of nodes– each node can have an arbitrary number of out arcsz Declarations typedef struct ARC {struct NODE *nodePtr;struct ARC *next;} Arc;typedef struct NODE {Arc *outArcs;int value;} Node;3CMSC 212 – S07 (lect 11)GraphsNullNullNullNodeArc5714key4CMSC 212 – S07 (lect 11)Adding Node To a GraphNode *AddNode(int value) {Node *new;new = (Node *) malloc(sizeof(Node));new->value = value;new->outArcs = NULL;return new;}You need to store this node into some type of structure so you don’t lose itlinked list of nodesarray of nodestree of nodesetc.5CMSC 212 – S07 (lect 11)Adding Arcs To a Graphint AddArc(Node *from, Node *to) {Arc *new, *pred, *current;pred = NULL;for (current=from->outArcs; current; current=current->next) {if (current->nodePtr == to) return 1; /* already defined this arc */pred = current;}new = (Arc *) malloc(sizeof(Arc));if (!new) return -1;new->nodePtr = to;new->next = NULL;if (!pred) {from->outArcs = new; /* first out arc for this node */} else {pred->next = new;}}6CMSC 212 – S07 (lect 11)Steps in compiling a programz Converting .c to .o files– Pre-processor– Compiler (or Translator)• Scanner/Parser• Type Checker•Optimizer• Code Generator– Assembler• Converts assembly code to machine codez Converting .o's to an executable–Linker• resolves symbols – function use and definitions– global variable declarations and use7CMSC 212 – S07 (lect 11)Pre-processorz Makes a pass over the program before the compilerz Handles– #include statements– Symbolic constants –Macros– Pre-processor Symbols– and other pre-processor directives • things that start with #8CMSC 212 – S07 (lect 11)Pre-defined Symbolsz __FILE__– the name of the source file being compiledz __LINE__– line number of the current line in the filez __DATE__– Date the file was compiledz __TIME__– Time the file was compiledz __STDC__– 1 if the compiler conforms to ANSI Cz Note: these start with two underscores and end with two underscores9CMSC 212 – S07 (lect 11)#definez #define name stuffz Symbolic constants– Primary Use– #define MAX_SIZE_TABLE 1024z Macros– #define name(parameter-list) stuff–Example:• #define SUM(a,b) a + bz Note: all caps is a convention – not required by the preprocessor– makes it easier to know something is a pre-processor definitionz Macros are a single line– Can define a "continuation" by ending line with \– #define macro1 a very long macro \– that runs onto another line10CMSC 212 – S07 (lect 11)Common Macrosz Square:– #define SQUARE(x) ((x) * (x))– foo = SQUARE(a + 1)– This is replaced to:• foo = ((a + 1) * (a + 1))z Double:– #define DOUBLE(x) ((x) + (x))– foo = 10 * DOUBLE(3)– This is replaced to:• foo = 10 * ((3) + (3))z Maximum:– #define MAX(a, b) ( (a) > (b) ? (a) : (b))– printf(“%d is the max”, MAX(5,6));– This replaces to:• printf(“%d is the max”, ((5)>(6)?(5):(6)));11CMSC 212 – S07 (lect 11)Macro Substitutionz Items are textually replaced so you must be careful!!z Consider:– #define SQUARE(x) x * x– foo = SQUARE(a + 1)– This is replaced to:• foo = a + 1 * a + 1– #define DOUBLE(x) x + x– foo = 10 * DOUBLE(3)– This is replaced to:• foo = 10 * 3 + 312CMSC 212 – S07 (lect 11)#define substitution1. Check macro invocation arguments for macros• If present, replace with macro values2. Replace macros invocations by defined macro3. Scan for any defined macros used in program• If found, repeat steps 1 & 2String literals are not scanned for macro replacement13CMSC 212 – S07 (lect 11)Macros vs. Functionsz They look similar, but macros– are textually replaced into program• can be faster than subroutines for short things– macros can not be recursive– do not check types of parameters• replaced code is type checked during compilez Example: macro being passed a type as a param#define MALLOC(n, type) \((type *) malloc( (n) * sizeof( type )))14CMSC 212 – S07 (lect 11)Other Issues with Macrosz Side Effects of Macro Parameters– Replace each use of parameter– Consider:• #define DOUBLE(x) ((x) + (x))• y = DOUBLE(++j);• y = ((++j) + (++j))z Can be hard to tell macros from functions– Solution, use all upper case for macro namesz #undef name– un-define the macro named “name”z Compiler Command Line Definition– gcc -DFOO=3– defines FOO just as though #define FOO 3 appeared in program15CMSC 212 – S07 (lect 11)Conditional Compilation z #if const-ex1– statements done iff “const-ex1” is truez #elif const-ex2– statements done iff “const-ex1” is false and “const-ex2” is truez #else– statements done iff “const-ex1” is false and “const-ex2” is falsez #endifz defined(macro-name)– one example of a constant expression– 1 if macro-name is defined, 0 if notz #error – stops the compilation at this pointz Useful if code must be different on different systemsz Tends to make code hard to read16CMSC 212 – S07 (lect 11)File Inclusionz #include "foo.h"– Works as we have seen earlierz What if foo.h includes another file– Pre-processor can handle thisz What if "foo.h" and "bar.h" each #include stuff.h– This is fine, until one program includes both foo.h and bar.hz Solution (inside stuff.h):#ifndef STUFF_H#define


View Full Document

UMD CMSC 212 - Lecture Slides

Download Lecture Slides
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Slides and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Slides 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?