link list help

ohMan · #1 03-Aug-2004, 18:24

hi

i'm really havin trouble doin this assignment in C. i've been readin many different websites and books to understand linked lists, but i still don't get it. in many examples i've seen, the lists already have set values, but in this assignment i'm suppose to allow the user to enter their own values and then sort that. i have no clue on how to do this.

here is the assignment:
Linked List in C

In a loop:
allow user to:
enter an integer
delete an integer

For each insertion/deletion, insert/delete a link
When inserting, sort in non-decreasing order
After each insertion and deletion display the list
Test your code on the following sequence of data:
insert 36
insert 46
insert 6
insert 346
insert 14
delete 46
delete 6
delete 7
delete 346

here is what i have so far:

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>

struct list {
	int         value;
	struct list *next;
};

struct list		*head, *tail;

main()
{
	head = (struct list *) malloc(sizeof(struct list));

}

after this i'm lost. can someone plzz help me? this is the first assignment i don't know what to do.

Garth Farley · #2 04-Aug-2004, 04:43

Okay, you know what to do, and roughly how to do it. You've just got to figure out the implimentation. I see you're planning on using $tail and $head pointers, but I'm gonna just describe a slightly simpler structure, a stack, which is an unsorted FILO (first in last out) singly linked list.

What functions will you want?

Well you want to add stuff to the list. We'll push elements onto the end of the list.
You want to remove items from the end, i.e. pop them off.

That's not much, eh? Right, lets get to it. You're sticking to C yes? Hokay!

You've got your struct out correctly, I'll just rename it slightly:

CPP / C++ / C Code:

typedef struct LINK {
  int         value;
  struct LINK *next;
} node, *stack_p;

Here I've defined a new type 'node' which is a link for the stack chain.
stack_p is a pointer to the top node of the stack.

Now the implimentation. First a simple check to see if the stack is empty. We will in main() declare a stack as follows:
stack_p st = NULL;

So to see if it contains any elements:

CPP / C++ / C Code:

int stack_isempty(stack_p *stack)
{
  return (*stack == NULL);
}

Next we wish to add stuff onto the end. We will do this by creating a new node, making it the new element at the top of the stack (pointed to by stack_p) and setting it's pointer to point to it's predecessor. It's a lot of fiddling with pointers, so go through it slowly.

CPP / C++ / C Code:

stack_push( int value, stack_p *stack)
{
  node *n;

  n = (node*) malloc(sizeof(node));  //create a new node
  n->value = value;                 //assign it the pushed value
  n->next = *stack;                //have the 'new top' point to the 'old top' node

  *stack = n;             //set the 'new top' node as the new top
}

Pushing, or deleting the top element of the stack & returning it's value is similar, just the above backwards really:

CPP / C++ / C Code:

int stack_pop(stack_p *stack)
{
  node *temp;    //temporarily holds the pointer to the node we're gonna delete, so we don't loose it
  int value;

  temp = *stack;     
  value = (*stack)->value;     //get the return value
  *stack = (*stack)->next;    //set the 'old top' as the 'new top'
  free(temp);                  //delete the node. Don't waste memory

  return value;
}

This is the simplest it can get. Here's somethign you can test it out with:

CPP / C++ / C Code:

int main(){
    stack_p stack = NULL;  //always set to NULL initially, or else there could be trouble!
    stack_push(7, &stack);
    stack_push(14, &stack);
    stack_push(56, &stack);

    while(!stack_isempty(&stack)){
        printf("Pushed element: %d\n", stack_pop(&stack));
    }
}//eom

Now this is the simplest linked list out there. There's no sorting or anything going on. To extend it for sorting you can iterate down the list looking to see where the element will fit properly!

Hope this helps. Good luck!
GF

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Merge sort on a linked list	Temujin_12	C++ Forum	1	06-Mar-2008 20:33
[CONTEST?]Data Structure Test	dsmith	C Programming Language	2	06-Jun-2004 15:13
help on linked lists any1?????	nick4	C Programming Language	1	17-May-2004 09:32
[include] list1.h -- Linked list class	dsmith	C Programming Language	2	04-May-2004 09:42