1`CIS142 ===== on your disk, turn in: cpp file [for the source code, the include file (name files the same), testbed exe files hard copy of all source codes [including the testtemp] hard copy of the output do preconditions and postconditions also include template criteria 4/2/98 -------- INTRODUCTION TO THE COURSE -------------------------------------------------- reuse code - improve productivity and improve interity abstration - procedural data [look at the big picture, don't worry about the details from the start....do the details later] coupleing....making you use something like STUDENT as a structure data type for a function - send in 3 ints, and make the function as GENERIC as possible. [coupleing is using a COMPLEX function - avoid this] put one task in a function at a TIME - don't do multiple operations in one function its best to work from the TOP-DOWN [down-up doesn't usually provide a good picture] object oriented programmng requires these components {we'll see these in mod4]: OOP requires: P - Polymorphism I - Inheritance E - Encapsulation [introducment in mod1 through mod4] (class structure) why -> abstration -> bind data definition and operations for data of that type objects and data will be studied....objects CAN'T be seperated from their "characteristics" we're changing from PROCEEDURAL C++ to OBJECT-ORIENTED C++. we're doing templates to begin with - template can handle ANY data type, but we're looking to receive ANYTHING. do insertion sort as first function [comment out float lines] - this from program 1 insertion sort is TRIVIAL by 261... :) [it's an n^2 algorithm] learn more sorting algorhithms in 261! 4/3/98 --------- homework: read text related to insertion sort topics: programmer productivity (and integrity) / (control) -> tools -> reuse abstraction -> procedural -> data - ADT OOP this will be on the first test: in control, we're going to have some access privlidges: public - completely availabe - can read and write private - not available - can't see it or write it protected - module 4 [sub-classes] friend private almost uses "user groups" - like friends -- exceptions to the rule - overrides tools for productivity: code generators [programs to generate code] libraries of code reusing code: copy and pasting include files test question ------------------- which method is easier? - the include file, or the direct posting to your cpp file? include the file using include "include.cpp" - it takes up less room [in the text] PLUS....if someone across your network has updated a source file, and it's a better file - when the business recompiles their programs, they always get the newest version of your file. [if someone else updated the file] make sure you only do one function, and you don't "couple" items together abstration: procedural code : [what we've been doing all along] also on test: data - ADT - ABSTRACT DATA TYPE - data definition and operations defined for data of that type. Desirable Characteristic: 1) incapsulation - binding of definition and operations. in c++, this is a CLASS STRUCTURE. 2) information hiding - control - details are hidden. [keeping details from our client]. access provided - public, private, protected, friend 4/6/98 --------- topic for today: templates....why and how? you can reuse these...copy to maintain the signature and reuse it. when you have more then one function with the same name (different types), like we did in cis141, it's called function overloading. signature file contains: a return type, a function name, and a parameter's list. we have a swapem for integers. what if we change a and b to be floats? - you will get temporary values, and it'll make new temporary values of the other type. for a template: template class is your KEYWORD. theType is USER-DEFINED. 3 components of function signatures ========================= return type function name parameters list 4/7/98 ===== ASSIGNMENT DUE 4/13. [first program] Topics - Templates (why? how?) function signature function overloading template criteria LAB - do a binary search template going over the cheating policy "buddies" [find a buddy in class to keep in check with] on your disk, turn in: cpp file [for the source code, the include file (name files the same), testbed exe files hard copy of all source codes [including the testtemp] hard copy of the output do preconditions and postconditions also include template criteria [what does the user have to supply to make this work?] preconditions of a binary search - array must be sorted in order. postconditions of a binary search - will return an value of the array usually where your target value will be located. 4/8/98 you need something to tell the compiler the function is not yet complete - template - this causes compiler to not convert to object code until the function KNOWS what type of code is being sent. ABSTRACT DATA TYPES ==================== (ADT) OOP - Data Active POP - Function Oriented, Data Passive Definition: Binding of a new definition with the operations efined for data of that type. (Defining a new data type with operations) (you'll probably never use a struct again after this point in time - you can't really do operations with structs. A "student" from here on would PROBABLY be a class. You'll understand why as we move through this quarter. when you "bind" something together, it's called ENCAPSULATION. Implementation--Classes in C++ 1. Attributes (data definition): data members 2. Capabilities (operations): methods 3. Access Privlidges (control mechanism): private - nobody but objects like me can mess with my data members. public - it's not a critical data member. protected - applies to sub-classes. friend - can change or modify the private data - exceptions to the rule. Class structure binds together the data members and methods. The "unit" created at declaration is known as an object. data member - is the attributes of a class. [as opposed to a "field name" which was an attiribute of a struct]. methods will be very much like functions you write in 141. everything that class needs to do is called a method. [and will be defined as a spectrum]. 4/9/98 ====== ADT's Concept [Encapsulation, Information Handleing] Implementation Classes in C++ Data Members Methods Access - {public, private, friend, protected} as an ADT, you have two parts: data members (both here going to be of type INT) methods (constructor) a method will be sum () and print () so.... data members: [usually private] int a int b methods constructor sum () return a() - [read only access] print () return b() - [read only access] data members are PRIVATE. methods are PUBLIC. do a class then do {, }, and a ; class aThing { }; --notes...if you leave out the ;, you get an error about 2 pages down that makes you have NO CLUE you left out a semicolen. rules to remember: 1. all classes have a min of 1 method - the constructor - and this must have the same name as the CLASS. The constructor initializes everything you'll use in this class, so that it will not contain any random garbage. You should also comment to the reader which values you're initializing it to. 2. default constructor: the constructor that works with no parameters. a default constructor usually looks like this: AThing(); but it also looks like: AThing (int=0, int=0); the default constructor can work universally, but if you use a default, you CAN NOT use any additional constructors. If you're specifying [not using a default], you can use more constructors. now...in doing actual definitions Method Definitions Syntax Returntype className :: methodname (optional parameter list) A and B , of course, are part of the class "AThing" - therefore, they're incapsulated in the class. if we're to use: AThing X; - that means we've got X, which includes A and B as 0 - their default values. AThing G(2,3) - that means we've got G, which includes A and B as 2 and 3, their defined values. X and G are now OBJECTS [or instances] of class AThing. 4/10/98 ====== ADTs continued ; classes in C++ review: class AThing { private: int a; int b; public AThing (int=0, int=0) } AThing :: AThing() [default - sets to 0] { a=0; b=0; } AThing :: AThing(int N1, int N2) [user inserts amounts] { a=0; [or 15 or whatever] b=0; [or 10 or whatever] } const methods - ALWAYS label your public data parts const ; because that way we're SURE they won't be altered. (your private data members). 4/13/98 ====== classes in c++: -> data members -> method -> constructor / default -> overload mathematic / relational ops ** any internal types can be directly outputed (such as int, float, et cetera). OUR created types [such as aType] can not be directly outputed. We will learn this eventually. there is a default assignment operator [as used for ints...ie, w=x+y] , and we're going to use it for now. eventually, we'll be writing our own. on the left hand side [of a=x+y], left side is OBJECT, right side is parameter. now we're dealing with something like X.+(y); AThing operator - tells compiler you're overriding it's standard definition for the operator you're overwriting. AThing AThing :: operator + (const AThing& rhs) //rhs = right hand side { AThing answer; //if you had no CONSTRUCTOR - this line //would BOMB! return (answer); } 4/15/98 ====== if left hand side is not an object of our type, it can not be a class method!!!! w=x+3 w=3+x AThing operator ___ = this overloads standard operations AThing AThing :: operator + (const int& rhs) const obvious tell tell that this is a class method. [class name an resolution operator says i belong to someone!] -- resolution operator: :: if you can write a function as a METHOD, do so. methods can easily be converted to friends. [syntaxiadly] say.... AThing AThing :: operator - (const AThing& rhs)const vs AThing operator + (const int& lhs, const AThing& rhs) i've got the possibilities of relational anomolies - greater than has been define by default. but...what if i added a greater then? say we've got : AThing x (5,2) AThing y (6,2) X < y X > y X = y return (a < rhs.a && b < rhs.b) is 5 < 6 ? is 2 < 2 ? 4/15/98 ====== left hand object must be an object of my our class. information hiding and ??? are desirable characteristics of ADT. what's the purpose of the header file? to communicate with those that may want to use objects of our type. [it's not restricted to just objects] Project Organization (Development Environment) H - user interface .CPP - details to be hidden when development is completel .IDE - binds all associated files with application. Contains crucial update information about all files in the project, last revision date, et cetera. MyClass.H (Class Declaration) MyClass.CPP (class definition) | | | (#include) | (compile) | | Myprogram.Cpp (user of class) MyClass.obj (class object code) | | | (compile) | | | Myprogram.obj (link) | | | | | | <-linking-> | ------------------------------------------------------------- | (based on prj (project) file myprogram.exe 4/17/98 ====== a compiler directive is NOT source code - it is a direct command to the compiler. the <#include> is a compiler directive. It does not get converted to object code. other compiler directives: #ifndef - if not defined, #define it. #ifndef ATHING #define ATHING if it's not defined, define it here. . . . . #endif the name you choose [such as ATHING], it can't be the same term as another compiler reserve word or user defined word on the system. this is used mainly to prevent compiling two different definitions for "AThing" or for whatever. this is more or less a protective envolope. To Create A Project: ============== 1) go to the project pull-down menu 2) select new project. 3) the actual running program and the project name must be the same. In this particular instance, the filename will be myprog.ide 4) select easywin - for now. [this is the target type] 5) platform and target model - go with standards. 6) there are two IMPORTANT things to make a note of... click advanced options..... there is a check for rc and def. we're going to click both of those files off {for now}. they're like a config.sys file on you system boot. :) TCWIN45 HAS A BUG - it must be exited using the OK BUTTON. if you save using ENTER, it will NOT SAVE YOUR DATA. 7) click ok on that.... 8) get your project tree.... 9) RIGHT CLICK myprog.exe - click ADD NODE 10) add your myclass.cpp to the tree- MAKE SURE THEY ARE ON THE SAME LEVEL. 11) go ahead and double click the main filename - it'll link and run. 4/21/98 ====== projects in C++ -- and doing complex number classes, +2!! complex # class is worth TWO POINTS. We're also introducing MOD2 today. Purpose of a header file - tells anyone who wishes to use this what they need to know about the functions and classes. while you develop, you MUST include the CPP after you get into a project, get the file into the .H setup client.cpp - our testbed -- it will also include the .h file. DON'T FORGET!!!!!!!!!!!!!! ================= #ifndef ATHING #define ATHING ---MOD2--- 3 storage classes -we'll be asked to talk about them and go over advantages and disadvantages concerning these: 3 storage classes: What is their scope and lifetime? 1. Automatic 2. Static: - "static int Z" space is given on the stack; can only be initialized ONE time. does not change. 3. Dynamic with a stack....the LAST thing put on is the FIRST thing taken off. 4/22/98 ====== 3 storage classes in C++ --- Automatic variables (or objects) Scope: Limited to the file or function in which the variable is declared. Example, if x is declared in f, then that x is onloy accessaiblew from within the function f. lifetime: Space is allocated for function local variables when the function is invoked, and the space for those local automatic variables is de-allocated at functiont ermination. Usually the space for automatric variables is allocated on the system data stack. Static Variables (or objects) Scope: Same as was the case for automatic variables. Lifetime: The duration of the program execution. This differs from automatic variables in that the space allocated for such a variable does not "disappear" from one invocation of the function to the next. IN essence , these varaibles provide us with a form of "value persistence" form one call to the next. Without having statis variables available, there is a temptation to make such variables global (so that their values could persist) when in fact we only needed a variable with local scope. Static variables solve this problem. Dynamic variables (or objects) Scope: These are accessable as long as we maintain a pointer to them. Lifetime: From the time we explicitly use "new" to to allocate space for them, to the time that we issue a "delete" command to release that space. We, the programmer, are in control of the lifetime! We take on the "responsibility" of managing that space through the use of pointers. A lot of flexiblity and power, but the programmer carries the additional work of some memory management. ...a static variable will not be de-allocated at the end of a function.... Notes on DYNAMIC STORAGE............ Keywords: new delete null we might use null to say "there's nothing there yet" - sort of like "-1" in arrays. instead of using int p; -- use int* p, -- you're saying this int will hold a pointer which refrences an ADDRESS [in memory], which in turn hits up a memory location. also....float* p will refrence a location in memory of a FLOAT. HOWEVER........all of these memory sizes in memory will be 4 bytes [to hold another memory location]. in our windows system, 4 bytes are being held in our system for a pointer. 4 bytes...is 32 bits. that's 2 to the 10th....kilobytes 2 to the 20th...megabytes. 2 to the 30th....gigabytes 2 to the 31st....2,000,000,000 2 to the 32ne....4,000,000,000 **bits used - directly relate to the amount of memory available** [homework +1 due friday] -- handout included to setup a variable: p=new int; then, you say *p = 10; - to write to p. there is a major differnece between: p=10; *p=10; free function -- free?? we're really talking a method....verses a function. all functions are free -- all methods are attached! there is no difference between a function and a free function a friend function has special access privlidges to the private data members 4/23/98 ====== dynamic variables - -new -delete -null possible errors: -dangling reference -garbage. dangling reference - de-referencing a pointer after it has been returned to the heap after it has been returne to the heap through a heap through a delete statement. Notice - this won't give you a compiler error or any problem. garbage - loosing an address prior to deallocation - commion result of an assignment statement (in error) [when the programmer looses an address in the heap prior to returning it via a delete statement ; usually the result of an assignment statement.] int* p; (4 byte memory address in the stack) p=new int(5); delete p; [p stores an address] then..... r=new int; *r=20 cout << *p you don't want to do something like p=20; that will overwrite whatever data is at "memory location 20" 4/27/98 ===== dynamic variables: new delete //function calls ================== null ================== dangling reference -- watch out!! garbage 4/28/98 ====== Linked ADT - concept, and implementation Hexadecimal Number system [homework +1 due friday] -- handout included turn in... decemal binary hex 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F sample: A 3 D 9 0 F B 7 1010 0011 1101 1001 0000 1111 1011 0111 pointer: a variable that holds an address in memory. 4/29/98 ===== LIST ADT - a list is a collection of homogeneous items. In order to have a list ADT, you must know the following items: Data ==== Collection Beginning and End Points of the data. Traversal - anything you have to go all the way through the list in order to accomplish - includes printing / searching. Add/Remove to list.....and access directly to the Ith (whatever cell you want). Linked List vs Arrays.... array... advantage - work for implementer is simplified disadvantage - space is not properly utilized, we don't manage memory precisely. linked list: in book class - we'll need pointers - each data piece has to have a "hook" to get us to the next guy. you have to add a data member to link it into the implementation. a few costs - watch the coding [which is in the extra cell], and the overhead of additional pointers which must be added. this is best for the dynamic lists...which grow and shrink, but especially for the largest types of data. in program: class SRlist; //forward reference -- means you're not going to actually define this as of yet. "just hang on, I'll tell you about this later". void add (Student *); //since we're asking for a student pointer, the possibility of failing is rather impossible. if duplicates are ok - add can't fail. you might address rather duplicates, et cetera could fail? consider that while making a list. for SRLIST, SRLIST must be a friend because you need access to the private data member "first", or second, so forth... for Student, SRLIST needs to be a friend (ostream) so you can have access to the NEXT data field, to link to the next guy. 4/30/98 ====== Continuing Linked Lists.......... List ADT Implementation Array LL we'll be asked to talk about the list adt and the implementation. These are two seperate things. in mod 3 - we'll be working with CLASS templates friend only applies to ONLY the class and its methods. You can't have a "friend of a friend", ok? :) In order to make it one, it must be stated esplicidly. what question do you ask to determine if the method needs to be a friend? - does it need access? does printing one student need access to "first" -- no. :) say... public: Student (string="0"; float; int=0) - not valid. Put the "=0's" first. the only things that come in on a parameter list comes from "the end user" - the outside world. When adding a new guy to the old list.....add the LOOSE one first....because he can't corrupt the list (since he's not part of it yet). 1. next guy's next = first's next 2. set first = new guy dont' forget the safety net...make sure you don't get a null! 5/1/98 ===== program notes: mylist = 5500 5500 = jay green jay green's next = 5000 john smith's next = null steps!! ====== new guy's next to the old guy's next reset first to the new guy 5/3/98 ===== objectives - physical and logical views linked list - implementation -- remove from front -- add to rear -- remove from rear multiple logical views of data can be stored in a logical list. for every logical "lookup" or view we want to represent, all we have to do is add a pointer. a first subject might point to animals...you basically just add another "next data view" your add and delete can handle both lists at the same time (in our program) definition: (define a multiple logical view) - you are maintaining multiple logical views of the data in one physical implementation. Linked lists allow you to do it by adding a pointer for every logical list you wish to maintain. 5/5/98 ===== Entire list search -- printing, counting, how many meet specified criteria? a. Initialize walker to first in list while (walker != NULL) { process each node update walker } Example - count nodes in list int count=0; ListNode* walker; walker=first; while (walker !=first); {//assertion: walker is "pointing to" a valid address. count ++ is smith in my list? -- do you need to search everyone? NO. printing all employee paychecks ....you DO need to see everyone. definition: assertion - what do I know to be true at this moment b. Initialize walker to first in null while (walker != NULL) {test condition process only nodes meeting criteria) update walker} Example How many students have a gpa >= 3.0 ? int count=0; ListNode* walker; walker=first; while (walker != NULL) { if ((*walker).gpa >= 3.0 count ++; walker = (*walker).next; } cout << this list has << count << A & B student. descriminators - adding efficency -- additional code which "works better" : 2. Early exit possible -- Is Smith in the list? Is there a student with a gpa of 4.0 ? int found = 0; //initialize boolean to false et cetera... you've gotta say (walker != NULL && ! found) - because if he's not there... you've got a problem. **MAKE SURE YOU'RE NOT LOOKING AT A NULL POINTER!!** [that's a GPF!] 1. ran out of list 2. target was found 3. passed a place he should be (*walker).next can be replaced by walker -> next if it is in order by GPA....what about virtual lists (additional lookups?) if you get a GPF - it's most likely de-referencing a null pointer. while (walker != NULL && ! found) -- early exit in an UNORDERED list while (walker != NULL) -- works generically. ave access to the NEXT data field, to link to the next guy. 4/30/98 ====== Continuing Linked Lwrn`j<Uz: Y=?ggiPy{;=EPR  -/h Y [ t   f  g * , ; =   { ;=kk+-Rmz !7Jm1<t  OOQ!pwTTFs VX+EG1BTeq8::BDfnv "$GIWZ\\^`dfQ6<>Akm5 7 9 !!!f!!!!!!!!!!!!""""")"3"<"U"X"Z"Z""""""""""###(#*#s#########$4$6$$$$G%%%%%&&V&x&z&&&&&'&'('*','.'C'F'H'J'L'U']''''''''((8(:((((((6)8)A)C)y){)))))))*C*E*V*X*h*x*z***************++_+a++++',),=,x,,---u------..+.H.T.`... /)/+/4/////000-0/0?0O0Q0w0z0}00000011x1111111 2Q2223:3X333*4a4z4445X5Z5c5k5k5m5555555P6r6t6666 7"7>7Q7a7q7s7s7u7w77777781838B8D8888888 9"9"9$9-95979U9W9y9{9&:(:0;2;Q;S;;;=====>>??????@@*@0@9@@@B@@@@BADADAAAAAAA?BABaBcBBBBBBBClCnCnCCCCCCCCCCCCCHD~DDDDEEEE!E#E9E@EJERETEfE|EEEEE/FoFFFFGmGmGGGGGGGHH"H.H5HAHCHnHHHHHHHHHHH II&IIIRITI]IeIIIIIIII JJJ!J-J9JFJRJ_JkJwJJJJJJJJJJJKKKKKLKNKWK^KKKKKKKLLLLLLL M M MMEMMMMMQNN O8O:OGOIOOOO;PRPTPTPPPP1QYQ[QQQQQQQRRR1R:R@RBRRRRRRR{S}SSSTT'T0TzT|TTTT1UjUlUlUUUUUUUUU VVV0VIVKVeVgVpVxVVVVVVVVVW-W?WVWXWWWWWJXVXXXXXYY^YYYYYYYYZ9ZPZbZgZiZZZZZZ[[[[[\[[[[[ \'\:\c\u\w\\\\\\]]];]@]r]t]]]^ ^"^Q^`^b^^^^__$_9_9_Y_[_____"`$`&`l```b^^^^__$_9_  Arial!!!!!!!""""")"3"<"U"X"Z"