We are reading a book and we have to store every character of this book with it's count.
like : "This is to test" out should be: T4 H1 I2 S3 O1 E1
What will be the most appropriate data structure here and why? and what would be the logic here.
Asked
Active
Viewed 690 times
0
-
1let's have your opinion first... what structures are you familiar with? what fits best? – Nim Jul 11 '11 at 16:26
-
I am not sure but Tree DS will suit it. – Vikram Ranabhatt Jul 11 '11 at 16:31
-
Should this q have a 'homework' tag? – Steve Townsend Jul 11 '11 at 16:31
-
@Chris_vr, edit the question, add your thinking in, and you will most likely learn more - don't simply shift your homework question to someone else...A tree could work, but so could any of the other structures that are available, you need to think what characteristics do you need of the data structure (for your requirement) and what are the characteristics of the structures you are familiar with and match the most suitable one. – Nim Jul 11 '11 at 16:35
4 Answers
3
An array of ints would do fine here. Create an array, each index is a letter of the alphabet (you'll probably want to store upper and lower case separately for perf reasons when scanning the book). As you scan, increment the int at the array location for that letter. When you're done, print them all out.
gbjbaanb
- 51,617
- 12
- 104
- 148
1
Based on your description, you only need a simple hash of characters to their count. This is because you only have a limited set of characters that can occur in a book (even counting punctuation, accents and special characters). So a hash with a few hundred entries will suffice.
manku
- 1,268
- 10
- 9
-
1Hashing is monstrously overcomplex for this problem imo. Speed versus simple char-indexed array of counts will be horrible. – Steve Townsend Jul 11 '11 at 16:29
-
fair enough - its overcomplex, but the speed will most definitely not be horribly worse. They are both effectively O(1). – manku Jul 12 '11 at 08:13
-
hashset access is much more complex than array access, O(1) notwithstanding. Just walk the code. – Steve Townsend Jul 12 '11 at 12:46
1
The appropriate data structure would be a std::vector (or, if you want something built-in, an array). If you're using C++0x, std::array would work nicely as well.
The logic is pretty simple -- read a character, (apparently convert to upper case), and increment the count for that item in the array/vector.
Jerry Coffin
- 476,176
- 80
- 629
- 1,111
1
The choice of selecting a data structure not only depends on what kind of data you want to store inside the data structure but more importantly on what kind of operations you want to perform on the data.
Have a look at this excellent chart which helps to decide when to use which STL container.
Ofcourse, In your case an std::array(C+0x) or std::vector, seems to be a good choice.
