A suggestion on data structures in C

This is a discussion on A suggestion on data structures in C within the C Programming forums, part of the General Programming Boards category; Hi, Could anyone suggest the best data structure that can be used in C to represent a book? i.e. an ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    141

    A suggestion on data structures in C

    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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    > 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.

  3. #3
    WDT
    WDT is offline
    Tha 1 Sick RAT
    Join Date
    Dec 2003
    Posts
    271
    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.
    A hundred Elephants can knock down the walls of a fortress... One diseased rat can kill everyone inside

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Rather than using a 4- or 5-dimensional array, I would use dynamic memory allocation. You'll save a lot of memory that way.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Sr. Software Engineer filker0's Avatar
    Join Date
    Sep 2005
    Location
    West Virginia
    Posts
    235
    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.
    Insert obnoxious but pithy remark here

  6. #6
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. i need advice about data structures
    By sawer in forum C Programming
    Replies: 2
    Last Post: 04-22-2006, 04:40 AM
  2. Replies: 2
    Last Post: 02-28-2006, 02:01 PM
  3. Any Good Data Structures Books?
    By YevGenius in forum C++ Programming
    Replies: 3
    Last Post: 05-26-2004, 08:49 AM
  4. array of structures, data from file
    By nomi in forum C Programming
    Replies: 5
    Last Post: 01-11-2004, 01:42 PM
  5. Array Data Structures
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 03-27-2002, 06:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21