Printable View
Hi,
Could anyone suggest the best data structure that can be used in C to represent a book? i.e. an alphabet is contained in a paragraph, a paragraph is contained in a page and a page is in a book.
I mean if the user says, given a page and given a paragraph, how many 'a's are there in it, we'll be able to find the answer.
It would be great if someone could comment on time/space complexity w.r.t C.
Appreciate your guidance.
Thanks,
Angshu
> Could anyone suggest the best data structure that can be used in C to represent a book?
Only you can decide "best", based on your requirements - what are you expected to do with the data once you've stored in inside some data structure.
> I mean if the user says, given a page and given a paragraph,
Perhaps an array of paragraphs then?
Do something, try it out and see for yourself.
> It would be great if someone could comment on time/space complexity w.r.t C.
time/space complexity is independent of any computer language.
If you want a literal translation of the book the I would expect:
Book: contains an array of pages;
Page: an Array of Paragraphs
Paragraphs: an Array of strings. (with each array representing a line.)
Need not say what kind of fragmentary headache this kind of -programming/operations upon the structure- will cause.
Good luck.
Rather than using a 4- or 5-dimensional array, I would use dynamic memory allocation. You'll save a lot of memory that way.
As implied by some of the other posts, a single struct does not do well for describing a book.
I would probably have a struct that describes a book and contains a pointer to a linked list of page structures. Each page structure would contain a pointer to a linked list of paragraph structures. Each paragraph then has pointers to the text for that paragraph, either as a linked list of line structures or as a single chunk of data.
To find a particular paragraph on a particular page in a given book, you'd walk the linked list of pages to find the right page, and then you'd walk that page's linked list of paragraphs to find the right paragraph, then you'd do the operation (in your example, counting the 'a's in the text) on the text for that paragraph (or on the lines contained in the paragraph.)
If books are potentially large, you don't want to waste system resources by allocating separate char arrays for each line of text. Using indexes into the text along with a length of the line/paragraph will permit you to either store the entire text as a single large allocation or not have to store the entire book in memory. As you gain experience with data structures, you'll find that these things come naturally.
Don't forget that some a-hole like me will be interested in finding the number of a's in the second paragraph of the fourth page of chapter 6.