bg287

csc210 Final Project Instructions

Posted in csc210 by bnmng on 2011 04/22

Write a C++ program to create an array of linked lists. The program will store variables as they come from a file in a hash table (to be explained later). The program will also keep track of the number of accesses to each variable.

You will need to modify the node class to hold two data fields, a string and a count field. The program will use an array of linked lists to store variables in memory. The program will use an array of linked lists to store variables in memory. You will go to each array position by using a hash function to select the array element.

Declare the array with the following constant
const int PRIME=5;
Do not create a separate class for the array of bags; use the existing bag class only.

You will select each array position by hashing. After selecting the appropriate index, search the linked list to see if the string or variable is present. If it is, then update the count field by adding 1. If it is not present, then create a new node (storing it at the head of the list) and store the string, setting its count file to 1 ( since there has been an occurrence). You will need head_insert, either as a member function or a utility to add the values to the list.

Hashing involves adding the ASCII codes for each value and then using remainder division to select the array index. The hash table insures even distribution of the variables for fast access. Note that the data will not be sorted.

The output of the program will be a printout of each linked list, starting at index zero. Print the variables plus the count of each.

The algorithm will be discussed in more detail in class. You will need a search yielding a pointer to update the count field when a variable is present. Further specifications will be given if needed.

INPUT: File containing strings representing variables.

OUTPUT: As described above.

TO HAND IN:

Hardcopy of the C++ Code.
Hardcopy of the output
Your recording device

SPECIFICATIONS for the HASH FUNCTION:
output type: int
input type: a string or cstring
algorithm: sum the ASCII code for the string and return the sum modulo the size of the array. Ignore overflow when doing the sum.

Data for program 4

educe
line
educe
primrose
depart
line
thwart
line
grand
cellular
line
educe
depart
manage
depart
headline
empire
torch
headline
line
myth
deposit
balance
cellular
educe
distance

SPECIFICATIONS for PROGRAM

For the node class, add the following:

Private member
string word
two functions, a transformer and observer for the new private member
modify the constructor for the new data member

For the bag class
Public:
The “Big Four”, constructor, copy constructor, destructor, overloaded =.

bool search_list
// tells the client wheather a specific value is in the list. Calls a function search.

void head_insert
//should be a member function rather than a utility.

void add_to_count
//access the “current” pointer (in the private section)
//to update the count field of the node if the search is successful

friend ostream operator << (ostream &, const bag & mylist)
//prints a linked list.
//Overloaded operator to print both the data and the count field for each node.

Protected:
node * search1_list
//Called by the public function search_list.
//Sets the private memebr current to the node to be updated
//or is NULL if the value is not there.

Private:
node * head_ptr;
node * current;
//add to the bag class. This pinter will be used in the search
//and again used to update the node if the data is already present.

In The Main Program

The main should have an EOF loop and a two-way decision to decide whether
to update the count field or add a new node to the head of the list.

Print the list in the main after the EOF loop. (the output will not be sorted)

The call to the output operator is as follows:
out4<<hashtable[i]//out4 is an ofstream object

Suggestion: code the program at first with a single, linked list, then add the hash table.

csc 210 2011 04 20

Posted in csc210 by bnmng on 2011 04/20

Random notes about Program 4:
Hash function will see a string coming in. Doesn’t know anything about a class.
Sample Test given out today. Program 4 interfaces with an array of classes.

Final on the 4th at 5:00. One on exceptions, one on recursion.

Today: HW 9, sample test & inclass ex for recursion.

csc210 2011 04 18 Notes

Posted in csc210 by bnmng on 2011 04/18

Tonight: Homework 8 then Chapter 18.
Recursion. Finish what we need to cover for the semester.
Simple Types
Arrays
Linked List

HW 9 is due Wed the 20th.
Lab Mon 25th
Final May 4th.
Wed the 27th and May 2 free.

Probably can adapt Program 2 for Program 4.

csc210 20110413 Notes

Posted in csc210 by bnmng on 2011 04/13

Homework Monday and Wednesday, Lab 25th. Week 15 free.

Final, earliest possible Wed the 4th, during class time.
Program due during final exam.

Free class Wed 27, Monday May 2nd.

Read 18.2 – 18.6
Skip 18.3

Today, Test 3
Exceptions
Recursion

Program: A simple linked list. You can modify Program 2’s linked list.

The node will look like this:

Name Field: These will be the names for our variables.
Count FIeld
Link Field

If it’s there, update the count. If not, add it.

The decision of whether or not to add a node should be in the main.

Hash Table:
0 __
1 __->__
2 __
3 __->__
4 __
can be an array of classes or pointers. Compilers don’t

Exception Handling using Try and Catch.

Page 837 illustrates levels of throws.

Next time: Recursion.

CSC 210 20110411 Notes

Posted in csc210 by bnmng on 2011 04/11

Read 18.1 Error Handling
If you do a throw you should have a catch.

csc210 20100404 Notes

Posted in csc210 by bnmng on 2011 04/04

Test. Open Book. Sample Test handed out.
Today: Homework 7 and Sample Test 3

Note: A constant defaults to double. 3.85 is double. For float write 3.85f.

Going over sample test.

Study order of constructers & destructors with inheritance and composition.
Study virtual functions & when the base class or the derived class function is called
Rewrite a function as a template function
Rewrite a class as a template class
-Every single member function needs a template prefix

csc210 20110328 Notes

Posted in csc210 by bnmng on 2011 03/28

Test 3 on April 6th.
69okProgram due date moved to the 11th.
Lab Wednesday at 5PM.
Homework assignment handout.
Answers to prev homework handed out.
Might want to bring both books to the test.

Today:
Homework then template functions.
Template Functions
Overloading (the alternative to template functions)
Defining the functions
Instantiating.

Composition:
The part after the colon in a inheritance constructor or composition constructor is called an initializer list.

Making virtual work
Formal parameter has to be from the base class.
Need the word virtual in the base class and need to pass by reference.

There will likely be a question like Chapter 15 Exam Prep #9.

+Template classes
Ipmlemtation file with a template class should not be named .cpp because it can’t be compiled.
A good idea is using

Example myclass.h

Example tempclass.template
template
simple::simple () {
value = 0;
}
void simple::setvalue (int n) {
value=n;
}
itemtype simple::getvalie () const {
return value;
}

Example:main.cpp
include
using namespace std;
#include “myclass.h”

*** examples are not complete *****
Review: changing a simple class to a template class
Don’t use .cpp for the implementation file.
Either tyep the implementation code into the .h file, or use #include.
Within class, the specification needs .
Every single function needs a template prefix.
Cleint functions that use the class need a template prefix.
Also need nameofclass::.

-Template classes

csc210 2011 03 23 Notes

Posted in csc210 by bnmng on 2011 03/23

Lab next week.
Reading Assignment.

16.2 of Dale, and Main Savitch Chapter 6, section on Template Functions.

Today’s Agenda:
Pointers and Inheritance
Abstract and Base Classes
Template Classes from 16.1.

Composition vs Inheritance. Composition: no special syntax. Public functions are not available.

Inheritance: Special Syntax –

INheritance initializer has the name of the class after the colons; Composition has the name of the object.

Order of constructor calls: Base, Embedded, Derived. Destructors are called in opposit order.

When redefining functions in a derived class, it’s important to use ‘virtual’ in the base class to allow

Inline functions: The code is repeated throughout the main program.

Abstract Base Class: To define the functions in any derived class.
Pure virtual functions: Declare the function as virtual and assign it the value of zero.

See handout 2011 March 23 #1

Class member functions.
+ Each needs a template prefix
+ Nameofclass::

Organization of Program Code: Basically we need one big file. Cannot pre-compile cpp files. Specification file has to be .h, not .cpp because we can’t pre-compile it. Can be in separate files using an include statements. This is the same as including the entire text of one file into another.

-90

csc210 20110321 Notes

Posted in csc210 by bnmng on 2011 03/21

Lab a week from Wednesday.
Read 16.1 in Dale and read handouts.

Today: Discuss inheritance and program3
Time class
Ballsphere class

Remember all classes need constructors, transformers, observers. Classes also have destructor and iterators.

Inheritance as opposed to composition.
The pen has a ball: composition
A volyball is a ball: inheritance.

Conventional Programming: Data structures are global
OOP: Data structures are in the class.

Difference between composition constructor and inheritance constructor: composition uses the name of the instance of th eincluded class; inheritance uses the class name of hte base class.

The problem for which the keyword “virtual” is the solution usually comes up when a pointer to a base class is defined as an instance of a derived class.

Static Binding: THe formal parameter determines what’s called.
Dynamic Binding: The actual parameter determines what’s called.

CSC 210

Posted in csc210 by bnmng on 2011 03/16

Read 15 Dale to page 778
Chapter 12 Time Class

Today: Test 2
Composition line class

Review from test: Remember that destructor is called when the instance goes out of scope.

Follow

Get every new post delivered to your Inbox.