Page 3 of 9 FirstFirst 12345 ... LastLast
Results 21 to 30 of 82

Thread: Horror of horrors! Linked lists in C

  1. #21
    Join Date
    Sep 2007
    Location
    Oklahoma, USA
    Beans
    2,378
    Distro
    Xubuntu 16.04 Xenial Xerus

    Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by dwhitney67 View Post
    This is beyond the scope of the OP's exercise. Even so, merely storing addresses in a file won't help once power is restored, since the application may operate using a different range of virtual memory.
    When I mention writing to permanent storage, the addresses involved were not RAM addresses but actually disk addresses. That was the implementation in which I learned how to manipulate doubly linked lists; it was a text editor written in assembly language and later ported into C. The data portion of each node was a text buffer. Using a linked list allowed for insertion of new text in the middle of a buffer, by splitting it and inserting a new node, and the Prev and Next pointers were actual disk addresses, not RAM.

    This was on a mainframe system some 10 years before PCs came into existence; things were rather primitive in those days!

    For tutorial purposes, the OP's assignment is to be done entirely in RAM and requires use of "the current" node as the reference point, so the code has to be able to handle insertion at either end of the list, or in the middle.

    I wouldn't give such an assignment with double linkage until after a full introduction to string handling and single linkage, but I didn't set up the lesson plan...
    --
    Jim Kyle in Oklahoma, USA
    Linux Counter #259718
    Howto mark thread: https://wiki.ubuntu.com/UnansweredPo.../SolvedThreads

  2. #22
    Join Date
    May 2006
    Beans
    1,790

    Re: Horror of horrors! Linked lists in C

    All this text about linked lists makes me ponder that there surely must be one or two good tutorials on youtube where someone shows these things graphically.

  3. #23
    Join Date
    May 2008
    Location
    UK
    Beans
    1,451
    Distro
    Ubuntu 8.04 Hardy Heron

    Re: Horror of horrors! Linked lists in C

    Tony - Happy to try to help.
    Unless otherwise stated - all code posted by me is untested. Remember to Mark the Thread as Solved.
    Ubuntu user number # 24044 Projects : TimeWarp - on the fly Backups

  4. #24
    Join Date
    Jun 2007
    Location
    Maryland, US
    Beans
    6,288
    Distro
    Kubuntu

    Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by Arndt View Post
    All this text about linked lists makes me ponder that there surely must be one or two good tutorials on youtube where someone shows these things graphically.
    I always try to picture a collection of train cars that are attached to each other.
    Attached Images Attached Images

  5. #25
    Join Date
    Jun 2011
    Beans
    67
    Distro
    Ubuntu 11.10 Oneiric Ocelot

    Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by JKyleOKC View Post
    Your verification routine can be made much simpler by using another library function, "instr()." This searches a string for presence of a substring.
    What is this instr() function? It doesn't seem standard, I don't seem to have it on my system, and I cannot find any documentation on it.

    To the OP, if you did want to use a technique similar to the one JKyleOKC described, then you can use the strchr, strrchr, or strstr functions, in case you, like me, don't have this 'instr' library function.

  6. #26
    Join Date
    Sep 2007
    Location
    Oklahoma, USA
    Beans
    2,378
    Distro
    Xubuntu 16.04 Xenial Xerus

    Re: Horror of horrors! Linked lists in C

    My memory obviously failed me on the function's name; I suspect I was thinking of strchr or more likely, strstr. It's been a few years since I did serious C programming...
    --
    Jim Kyle in Oklahoma, USA
    Linux Counter #259718
    Howto mark thread: https://wiki.ubuntu.com/UnansweredPo.../SolvedThreads

  7. #27
    Join Date
    Mar 2011
    Location
    South Dakota
    Beans
    1,129
    Distro
    Ubuntu 13.10 Saucy Salamander

    Arrow Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by dwhitney67 View Post
    Anyhow, I have not had the time to read this entire thread, so I'm still unsure if the OP wants to insert at the front of the list or at the end, or perhaps somewhere in the "middle" so as to maintain a sorted list.

    If at the beginning, then only one pointer to the head node is required. If inserting at the end, then a tail pointer is needed.

    This is clearly something I need to think about more and take steps to diagram exactly the algorithm I think will solve my problem. Sorry I went mia for a bit there. I began to see myself getting stalled and just spinning my wheels. I was stiting there staring at the code and the the more I did the more confuse I became. I needed to step away from it for a moment. I'm sure glad I did because now I have all this great feedback in these posts and my mind is fired up again. I'm making a separate diagram right now that I will attach to this post before pushing the submit button.

    In a nutshell, I wanted to insert to the end of the list but not the end end of the list - the second to the end while maintaining the last thing in the list as NULL. Perhaps my terminology is skewed when describing it like that. I was just thinking about the situation where you get a few of them in a list. At that point you couldn't say the "end" of the list because that would leave it without NULL at that end. It would have to be between the NULL at the end and the last item before inserting.

    I haven't taken time to seriously consider how my linkages and the type of list I chose to go after ties into the search function. I know I wanted to use a function call to the search function in my print function to make it (the print function) simpler. I have tossed some ideas around regarding a search algorithm though.

    One thing that seems to pop up is to assign some sore of unique id based on the content of one of the string (the "Name" string perhaps). Then, when I think about that, I come to a conslusion that's probably redundant, inneficient, and prone to error (if not begging to break the program with it).

    Then, and I like this idea, I think of sorting directly on the data. If I have a NULL at both ends, I can start at either end simulteosly and go both directions at the same time. One direction corresponds to the first character in every string (string in every node) and the other corresponds to the second. Then, when both sorts reach the opposite end of where they started, they switch directions and one is on character 3 and the other on character 4, etc. Back and forth they go, ripping through the data and sorting it. Each one stops when they reach the end of the shortest string or second to the end of the shortes string, respectively? No, better that they have a way to determine when enough is enough and just stop then.

    Now I have to be very careful, because there is a time limit; but, if the results of that sort were to be placed in a table... Well you could have the sort run after every insert then update the table with the new results, then search on the table. This is way, way more than I can accomplish in the next 3 days. If there is some small part of that idea I could implement though - OOO'WIE!! the awsomeness that program would exude! Just smokin' hot!


    Quote Originally Posted by JKyleOKC View Post
    When I mention writing to permanent storage, the addresses involved were not RAM addresses but actually disk addresses. That was the implementation in which I learned how to manipulate doubly linked lists; it was a text editor written in assembly language and later ported into C. The data portion of each node was a text buffer. Using a linked list allowed for insertion of new text in the middle of a buffer, by splitting it and inserting a new node, and the Prev and Next pointers were actual disk addresses, not RAM.

    This was on a mainframe system some 10 years before PCs came into existence; things were rather primitive in those days!

    For tutorial purposes, the OP's assignment is to be done entirely in RAM and requires use of "the current" node as the reference point, so the code has to be able to handle insertion at either end of the list, or in the middle.

    I wouldn't give such an assignment with double linkage until after a full introduction to string handling and single linkage, but I didn't set up the lesson plan...

    The assignment is to be done entirely in ram. It dosn't require anywhere near the complexity I've brought into it. A singly linked list would be perfectly acceptable. I purposely beat myself like this because I think it's the best way to really learn a lot. I like taking things to the maximum of my potential and beyond, really creating a challenge. And, "awsomeness" in a program never hurt anyone

    Diagram coming:
    ----------------

    Edit:

    Diagrams attached
    Attached Images Attached Images
    Last edited by ClientAlive; February 22nd, 2012 at 08:27 AM.
    “ The best method for accelerating a computer is the one that boosts it by 9.8 m/s2. ”
    - Anonymous

  8. #28
    Join Date
    Jul 2007
    Location
    Poland
    Beans
    4,499
    Distro
    Ubuntu 14.04 Trusty Tahr

    Re: Horror of horrors! Linked lists in C

    sorting can be done right off the bat, at the insertion time.
    you simply start at the entry pointer, check the node located there to evaluate the relation between the node and new data. If condition is not met, you go to next node, check, ... and when you find proper place you rip the plugs between the 2 nodes where your new one is to be located, insert the node and replug everything. If you do that, you have a guarantee that your list is always sorted.

    You simply have to consider if it's more advantageous to insert data in dummy mode and spend more time to seek through the unsorted structure (or sort it at once when it's big which also takes time) or to waste some cpu cycles at insertion time to find proper place for new nodes in exchange for luxury of predictability which saves time in the long run.
    Programming is all about such compromises, there is no such thing as a free lunch and it's your responsibility to pick the right structure for the task at hand, knowing advantages and disadvantages of available solutions.

  9. #29
    Join Date
    Feb 2009
    Beans
    542
    Distro
    Kubuntu

    Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by ClientAlive View Post
    In a nutshell, I wanted to insert to the end of the list but not the end end of the list - the second to the end while maintaining the last thing in the list as NULL.
    NULL is not the last item in a linked list. It's a value we give to the next item pointer for the last item to tell ourselves "there is no next item".

    Remember that the next item pointer isn't the next item itself: it's an address that *points* (thus the term "pointer") to the next item. NULL is a special address reserved by the operating system and the compiler to mean "nowhere". So when the next item pointer is NULL, that means "the next item is nowhere, it doesn't exist".

  10. #30
    Join Date
    Mar 2011
    Location
    South Dakota
    Beans
    1,129
    Distro
    Ubuntu 13.10 Saucy Salamander

    Arrow Re: Horror of horrors! Linked lists in C

    This thing is acting very, very strangely. It has some kind of bug that I can't seem to find and I'm eating up hours trying to find it. It seems it's taking anything that happens to be a selection from the menu (or, I guess, a case in my switch statement) and applying it as a selection. I attached a screenshot that shows this a little.

    I select a for [A]dd an entry and am prompted with both of the printf lines in a row with no regard for the newline that's in the code for them. It just races past the first fgets, appartently, and prints the next line asking for the phone number. You enter somthing and press enter and just get a newline. You enter something again and press enter and it repeats (printing the request for both name and number - thought they are two separate printf lines in the code). If you happen to enter pp (maybe just p) it enters case 'p': and you see the prinf in that block of code printed to the screen.

    I'm afraid I'll end up wasting what precious little time I have left on this crap. I'm still looking but I haven't seen anything that might be causing it. It reminds me of the thing I described before with my menu function. Where adding a newline to one of the printf in it had no effect on the output. Yes it's inside the parenthesis.

    Code:
    /*
    Objective: Create a doubly linked list. Use a design in which it is the
    current node that is used to create a new node or to delete. Prev and Next
    are there for navigation and searching.
    
    Tip: 
    
    Status: <Content censored>
    
    Next steps: 
    */
    
    #include <ctype.h> //for tolower(), among other things?
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h> //for strcopy
    
    struct Node
    {
    	char Name[32];
    	char Phone[18];
    	struct Node *Prev;
    	struct Node *Next;
    };
    
    struct Node *Curr = NULL;
    
    void Menu(); //Done
    //char ValidSelection(char S); //Done
    void Insert(char N[], char P[]); //Done
    //Delete();
    //Search();
    void Print(char Selection); //Done
    
    int main(void)
    {
    	Menu();
    	char Selection = ' ';
    
    	while(Selection != 'Q' || Selection != 'q')
    	{
    		scanf("%c", &Selection);
    		//ValidSelection(Selection);
    
    		switch(tolower(Selection))
    		{
    			case 'a':
    			{
    				//insert
    
    				char Name[32];
    				char Phone[18];
    
    				printf("Enter name...  \n");
    				fgets(Name, sizeof(Name), stdin);
    				printf("Enter phone number...  \n");
    				fgets(Name, sizeof(Name), stdin);
    
    				Insert(Name, Phone);
    
    				break;
    			}
    
    			case 'd':
    			{
    				//delete
    				break;
    			}
    
    			case 's':
    			{
    				//search
    				break;
    			}
    
    			case 'p':
    			{
    				//print
    
    				int SubSelection = 0; //initialize to zero?
    
    				printf("Would you like to: Print [A]ll or Print [E]ntry ?\n");
    				SubSelection = getchar();
    				//ValidSelection(Selection);
    				Print(Selection);
    
    				break;
    			}
    		} //end switch
    	} //end while
    
    return 0;
    } //end main
    
    void Menu()
    {
    	//display menu to user
    
    	printf("Please select one of the following...\n\n");
    	printf("[A]dd an entry\n");
    	printf("[D]elete an entry\n");
    	printf("[S]earch for an entry\n");
    	printf("[P]rint entries\n");
    	printf("[Q]uit\n");
    	printf("\n");
    } //end function
    
    //char ValidSelection(char S)
    //{	//accept user's selection - include validation
    
    //	const char ValidSelection[13] = {'E', 'e', 'A', 'a', 'D', 'd', 'S', 's', 'P', 'p', 'Q', 'q', '\0'};
    //	int i;
    
    //	if(isalpha(S))
    //	{
    //		while(ValidSelection[i] != '\0')
    //		
    
    //			if(S == ValidSelection[i])
    //			{
    //			S = S;
    //			}
    
    //			else
    //			{
    //				printf("Invalid selection. Please enter your selection again...\n");
    //				printf("\n");
    //			}
    
    //			++i;
    //		}
    //	}
    
    //	else
    //	{
    //		printf("Invalid Selection. Please enter your selection again...\n");
    //		printf("\n");
    //	}
    
    //	return S;
    //} //end function
    
    void Insert(char N[], char P[])
    {
    	//create a new node with data entered by user
    
    	struct Node *Temp;
    	Temp = (struct Node *)malloc(sizeof(struct Node));
    
    	if(Temp != NULL)
    	{
    		strcopy(Temp->Name, *N);
    		strcopy(Temp->Phone, *P);
    
    		if(Curr == NULL)
    		{
    			Curr = Temp; //insert to curr - first entry
    			Curr->Prev = NULL; //make this the beginning of the list
    			Curr->Next = NULL; //make this the end of the list
    		}
    
    		else
    		{
    			Curr->Next = Temp;
    			Temp->Prev = Curr;
    			Curr = Temp;
    			Curr->Next = NULL;
    		}
    	}
    } //end function
    
    //Delete()
    //{
    	//removwe an existing struct instance
    //} //end function
    
    //Search()
    //{
    	//search for a specific, existing instance and print the entire instance
    //} //end function
    
    void Print(char Selection)
    {
    	struct Node *Pointer = Curr;
    
    	if(Selection == 'A' || Selection == 'a') //user entered [A[ll)
    	{
    		//Print entire list
    
    		while(Pointer != NULL)
    		{
    			printf("%s", Pointer->Name);
    			printf("%d", *Pointer->Phone);
    		}
    	}
    
    	else if(Selection == 'E' || Selection == 'e')//user entered [E]ntry
    	{
    		//code to print a single entry - use search function call
    	}
    
    	else
    	{
    		printf("Invalid entry\n");
    		printf("Please enter your selection again...\n");
    	}
    } //end function
    ---------------------

    Edit:

    Ta hell with it!

    At every turn this stinkin thing bites me. Can't pass an array into the sob, acts completely bizare for no appartent reason that I can see. I completely started over on in another file, trying to get somwhere with this absolute horror of a program. I'm wasting my time with this little garbage crap and not even get to focus on the linked list at all.
    Attached Images Attached Images
    Last edited by ClientAlive; February 22nd, 2012 at 12:32 PM.
    “ The best method for accelerating a computer is the one that boosts it by 9.8 m/s2. ”
    - Anonymous

Page 3 of 9 FirstFirst 12345 ... LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •