Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Need help getting started (http://www.go4expert.com/forums/help-getting-started-t3509/)

Nichie 21Mar2007 09:24

Need help getting started
Hello, I would like to seek some help on a programming assignment I am doing. I have been programming for roughly a year or so. When I made it to my Data Structure class I feel like I've hit a wall. The class moves very fast and it's really hard for me to catch up since I am still trying to understand a lot of the key concepts from my previous classes. I would really appreciate it if somebody could point me towards the right direction and give me tip and advices overall. Also, by no means am I asking for someone to do the assignment, but rather, give me some ideas on how I should tackle the problem.


In this assignment I am to construct a "dictionary ADT" in which key values are mapped to associated data items. The program is designed to count the numbers of occurrences of every word in a large text file. A WordCount ADT will keep track of word/count pairs, and supports the following operations:

- void increment (string key); - this method search for the word "key" -- if it finds the word, it increments the count associated with that word, and if it doesn't find the word, it must insert the word into our data structure and initialize the count for that word to 1.

- void print () - This method prints out all the word/count pairs that are stored in the data structure.

Also, I must implement the WordCount ADT in three different ways:

1. A simple linked list: All new insertions should be made at the front of the list, and nodes never change position in the list.

2. A linked list with the "move-to-front" heuristic: Like implementation 1, but every time a word is accessed in the increment() method it is moved to the very beginning of the linked list.

3. A Binary Search Tree: A simple binary search tree implementation, where you don't worry about keeping the tree balanced at all. Just insert items where they belong in your tree.

In particular, I need to make a clean interface that is common to all implementations, and the program should be written to use the interface. Should be able to switch out the three different implementations just by changing one line in the main program.
I really need help on getting started on this program since I have never done anything like this before. Should I be using a template? What does it mean to be able to switch out the three implementations by changing a line in the main program? What's the best way to do the implementation?

Please forgive my total newbness, I must apologize in advance since I will be asking a lot of noob questions. But I must understand these and I really would appreciate your help.


DaWei 21Mar2007 09:37

Re: Need help getting started
A list is nothing but a degenerate form of a tree. That is, it's just a totally unbalanced tree with the root at one end. The nodes are the same: data and two pointers. In a doubly-linked list one pointer points to the previous entry and the other points to the next entry. In a tree, one points to the left child and one points to the right child. In a map, there are essentially two items of data in a key:value relationship. The pointers are just part of the organizational structure. Read about the STL map container to get some ideas.

If you design an object to represent one node and another object to represent a collection of nodes, then you change the operation of your program merely by choosing which collection object to instantiate. The node object has methods to handle its own data and to provide information about that data to the outside; the collection object has methods to handle the manipulations of the nodes in the collection. It gets its information from the nodes, via the node methods.

I suggest that you design a list, a map, and a tree. Then look them over. You'll be surprised at what pops out as common to the three, and that the things you need to do are highly similar. Design an interface based on that commonality, and that gets the job done in a sensible way.

A better subject line, from the viewpoint of people searching for help, would have been "Need help with data structures, trees, lists".

All times are GMT +5.5. The time now is 02:07.