Thread: Linked Lists problem

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    61

    Linked Lists problem

    Hi

    So I am pretty new with C, but I know a little.. I have been here before and had great help from you guys so I thought I would try it again.

    I need to create code for a Sorted Linked List that follow these primitives;

    create: -> list
    insert: element -> list -> list
    raises DuplicateElement
    delete: element -> list -> list
    raises ElementNotFound
    find: element -> list -> Boolean
    isEmpty: list -> Boolean


    I've worked on some procedural code in class for a list search (find) that looks like this;

    List-Search(L, k)
    x <-- head[L]
    while x =/= NIL and key[x] =/= k
    do x <-- next[x]
    return x

    insert's procedural code looks like this;

    List-Insert(L, x)
    next[x] <-- head[L]
    if head[L] =/= NIL
    then prev[head[L]] <-- x
    head[L] <-- x
    prev[x] <-- NIL

    delete's procedural code came out like this;

    List-Delete(L, x)
    if prev[x] =/= NIL
    then next[prev[x]] <-- next[x]
    else head[L] <-- next[x]
    if next[x] =/= NIL
    then prev[next[x]] <-- prev[x]

    The areas I am struggling with.. is how to work with the raising of the duplicate element and the missing element, where to place them within the code, and then tying it all into one consistent stream of code.

    Also, I am probably wrong, but I figure for the last primitive of isEmpty, you would just write that if your initial search of the List returns NIL, then isEmpty is initiated.

    Feel free to ridicule me or help me, any attention is appreciated, I just think I need a little direction and I will see what I can do from there Thanks!!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Since the list is to be maintained as sorted, insert must walk the list to find the spot where the new element must go. As such, if it finds a copy of the element to be sorted, then you are done (raise the flag and stop); if not, then insert in that place (rather than at the head of the list). Similarly for delete.

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    61
    Okay, so, I think I have proper code here for creating the linked list;

    Code:
    #include<stdlib.h>
    #include<stdio.h>
    
    struct SLL {
       int val;
       struct SLL * next;
    };
    
    typedef struct SLL element;
    
    void main() {
       element * curr, * head;
       int i;
    
       head = NULL;
    
       for(i=1;i<=10;i++) {
          curr = (element *)malloc(sizeof(element));
          curr->val = i;
          curr->next  = head;
          head = curr;
       }
    
       curr = head;
    
       while(curr) {
          printf("%d\n", curr->val);
          curr = curr->next ;
       }
    }
    Now what I need to do, is.. put in a struct that will search the list for a given element, and place it in the correct spot. If the spot is filled with that exact element, duplicateEntry is flagged and we are done, if not, the element is inserted and we move onto the next element to be sorted.

    And for delete, the search is done for the given element, if found to be null, elementNotFound is flagged and we are done, otherwise we delete the current element, and move on to the next.

    Yes/No?

    Thanks tabstop.

  4. #4
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    That looks good as long as your intent is to list in decrementing order. Your logic of inserting and deleting a node looks sound.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Also you should avoid void main(). If Salem is around he will slap you!

  6. #6
    Registered User
    Join Date
    Dec 2008
    Posts
    1

    why not void main()?

    Quote Originally Posted by slingerland3g View Post
    Also you should avoid void main(). If Salem is around he will slap you!
    Interesting! on "should avoid using void main()" I want to befriend C really bad, and thus i want to know little intricacies like this.

    Thanks

  7. #7
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I would peruse through the FAQ from this site, there are some good tidbits there and should help you befriend C.



    http://faq.cprogramming.com/cgi-bin/...&id=1043284376


    FAQ's
    http://faq.cprogramming.com/cgi-bin/...arch&match=all

  8. #8
    Registered User
    Join Date
    May 2008
    Posts
    61
    what would i do in place of using void main()?

    and thank you for the compliments of the sound procedure, the hard part for me is taking it from the procedure to actual code :P that's where I am still learning, with a lot to go hehe

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by needhelpbad
    what would i do in place of using void main()?
    Use int main() and return 0 at the end of main().
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    May 2008
    Posts
    61
    okay i can do that

    now, for the functions of search and insert and so on, do i create all new structs, or do i slip the code inside? id assume each action would get its own struct, but not positive..

  11. #11
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I would recommend you create two new funcitons. One for searching the linked list and one for inserting into the linked list, say at the end of your node listing.

    Searching the linked list should not be that to much work for you. But inserting can be tricky. This all depends on where you need to insert the node.

    try something like

    Code:
    insertme->next = prior_node->next;
    prior_node->next = t;
    Granted you will have needed to allocate memory for any new node(struct) being inserted

  12. #12
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Code:
       insertme->next = prior_node->next;
       prior_node->next = insertme

  13. #13
    Registered User
    Join Date
    May 2008
    Posts
    61
    now, im sorry how newb this is right now, but the allocating memory idea sounds a bit out of my league, because im not exactly sure how or what to do to do so..

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You are already allocating memory with malloc in the code posted above.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User
    Join Date
    May 2008
    Posts
    61
    ahh my bad, guess i just wasn't paying attention to the terminology, or thinking about it clearly.

    ill post what i would think would be the insert function soon

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question On Linked Lists
    By Zildjian in forum C Programming
    Replies: 8
    Last Post: 10-23-2003, 11:57 AM
  2. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM
  3. Linked lists
    By sballew in forum C Programming
    Replies: 6
    Last Post: 10-24-2001, 08:52 PM
  4. I need some help on my linked lists app
    By valar_king in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2001, 08:36 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM