Solved

Linked List Creation

Posted on 1999-01-21
11
536 Views
Last Modified: 2006-11-17
The following struct is for part numbers, I'm trying to create a program that will read part numbers from an input file and place them dynamically in a linked list.

struct part{                    
      char partNo[6];
      int onHand = 0;
      struct part *_next;
      };

My problem at this point is understanding how the list can be held together.  Below are other functions that I have:

part * getPart(char pNew)
      {
            part *p;
            p = (part) malloc(sizeof(part));

            if(p == NULL){
                  printf("Memory failure in getPart");
            } else {
                  p->partNo = pNew;
                  p->_next = NULL;
              }
                  return p;
      }

      int insertPart(part **list, char pValue)
      {
            part *p, *pNew;
            pNew = getPart(pValue);

            if(pNew == NULL){
                  printf("Error in insertPart");
                  return 0;
            }

                  else if(*list == NULL  || (*list)->partNo >= newValue){
                  pNew->_next = *list;
                  *list = pNew;
            }

                  else {
                        q = *list;

                        while(q->_next != NULL && q->_next->partNo <= pValue){
                              q = q->_next;
                              pNew->_next = q->_next;
                              q->_next = pNew;
                  }  //end while
            } // end if
      }  //  end insertPart

Here are example part numbers from an input file:
D JNE294 18
D MBI953 20
D NWI373 2
D MEO674 7

The codes O and D willbe used to distinguish between orders and deliveries.  If D for delivery, then the linked list is to be searched to locate the proper insertion point.  If O for order, then the list is checked to see if the part number is present in inventory....  
0
Comment
Question by:John500
11 Comments
 

Author Comment

by:John500
ID: 1258285
Edited text of question
0
 

Author Comment

by:John500
ID: 1258286
Edited text of question
0
 
LVL 10

Accepted Solution

by:
viktornet earned 100 total points
ID: 1258287
There are some mistakes in your code... To better understand Linked Lists, try to read this article...

http://www.inversereality.org/tutorials/c++/linkedlists.html

There is also a file to be downloaded with full source code...

Hope this helps...

-Viktor
--Ivanov
0
 
LVL 16

Expert Comment

by:imladris
ID: 1258288
OK, there's a couple of problems that I can see. Let's first review the concept. A dynamically linked list is a series of objects (the part structure in your case) that are linked together with pointers starting at some anchor. The anchor would be a pointer variable that points to the first object in the list. Each object in the list points to the next one. So to find any object in the list you look at the first one (by getting its "address" from the anchor) and that is not the one you are looking for, you get the next one (by getting its "address" from the next pointer in the current object).

So, with all that in mind, you have a getPart function which creates a new part (maybe it should have been makePart).
insertPart is attempting to insert a part into a linked list. The anchor for the list is passed in as part **list.
insertPart has three main clauses. The first one cuts out if you can't get a new part. That's good.
The second clause seems to dealing with the case of an empty list (*list==NULL). I'm not clear on what the second clause ((*list)->partNo >= newValue) is attempting to accomplish.
In the body for this clause the list pointer should be set to point to the first object. Something like:

*list=pNew;

while you have, you should NOT write the other line (pNew->_next=*list;). This sets the part to point at the beginning of the list (itself). It should just be left at NULL to indicate this is the end.

I can explain the third clause as well if you want...

0
 
LVL 10

Expert Comment

by:viktornet
ID: 1258289
This should be as follows...

part *getPart(char pNew[6])
   {
   part *p;
   p = (part *) malloc(sizeof(part));

   if(p == NULL) {
     printf("Memory failure in getPart");
     exit(1);
   }
   else {
     strcpy(p->partNo, pNew);
     p->_next = NULL;
    }
   return p;
   }

or something like that.. Check out the website I gave you.. it is a good tutorials with images that show you how everything works, and stuff...

-Viktor
--Ivanov
0
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 1

Expert Comment

by:FuzzyLogic
ID: 1258290
Hi John500.
It seems while I was writing my answer, some other comments where given, so I may repeat what imladris wrote; but NM.


Some remarks about your program:

1. I would use typedef to define a char[6] type:
  typedef char tPartNumber[6];
so it will be clearer when you passes part-number pointers.
Remember that you must memcpy() part-numbers, or you're just passing the pointers.

2. malloc - you should have (part *) casting.

3. The "getPart" and "inserPart" functions should get "char *" or PartNumber type.

4. If "getPart" fails, "insertPart" gives the error message again.

5. The while statement (in "insertPart"): Only the first line (q = q->next;), should be in the while block.
The other two lines just insert "p" into the linked list.

6. For comparison, use strcmp() or your own function.

There may be other errors, since I did not tried to compile your program...


Now some explainations about your function(s), and how to write the other functions:

"getPart" allocates a new part (with a specified PartNumber).

However, "insetPart" does all the real work...
After you have a new object, there are two general cases when you want to insert it into a linked list:
1. Inserting the object as the first in the list. This may happan when the list was previously empty, or it really should be the first one (ie, the smallest key).
This is what happans in the second if. (BTW, you can put "return" and forget about the else).
2. However, you might want to put the new object somewhere else in the list. So first of all, you should search the object in the list that you want to link the new object after it. This is the (corrected) while statement. It searches the list, till the apropriate item or the end (what comes first).
And now, for the linkage. It is very simple, just the other two lines which should be out of the while statement.


Other function needed (or at least I think so):

A good function to add will be "PrintAllParts", which will pass all over the list, from the beginning to the end, and print all the records (part-numbers).

Now you need a "searchPart" function.
It is easier than the "insertPart" function, just look near the while statement.
You have to search the list from the beginning if the PartNumber (the key) is matching. I don't think you'll have any problem.

More difficult function you might want, is "removePart".
In this function, you should pay attention to special cases, when the part is the first or the last in the list.
If the item is in the middle of the list, you just have to search it, and "take it out", by fixing the previous item _next field, and freeing the allocated memory (if needed).


Hope you got the idea of linked lists.

Fuzzy
0
 
LVL 10

Expert Comment

by:viktornet
ID: 1258291
here is another way it might be better....

part *getPart(char pNew[6])
        {
        part *p;
        p = (part *) malloc(sizeof(part));
        if(p == NULL) {
          printf("Memory failure in getPart");
          return NULL;
        }
        strcpy(p->partNo, pNew);
        p->_next = NULL;
        return p;
        }

then when you use the function you can do this..

if ((MyPart = getPart(MyNum)) == NULL) exit(1); //or return 1; or whatever....

-Viktor
--Ivanov
0
 

Author Comment

by:John500
ID: 1258292
Thanks to all,

Viktornet,

I'll close the question out but is it possible to get feedback on this as I clean it up?  If so, by email?

John

0
 
LVL 10

Expert Comment

by:viktornet
ID: 1258293
yeah, of course... if u wanna e0mail me, my e-mail address is in my profile...
0
 

Author Comment

by:John500
ID: 1258294
At this point I'm having trouble taking it from the main program.  I have code to add which allows the user to pick the input file.  I'll add it.  Once this is done, I need help, say from you, stepping through the program to see what's ok and what's needed yet.  Right now I have little mistakes everywhere that are overwhelming me.  How about it?
0
 
LVL 10

Expert Comment

by:viktornet
ID: 1258295
no problem... Read the article, try to edit your program and fix it , and let me know how thing are going...
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now