-1

This is for a school project.

Me and my friends have been working on this specific project and have been stuck for quite a few days on this.

We have these 2 structures...

typedef struct node{
  long value;
  struct node *next;
}Node;


typedef struct list{
  Node *Node;
  struct list *next;
  struct list *prev;
}List;

The struct called node will be the linked list itself, I have to use this structure as a linked list.

The second structure called List can be pointers to nodes.

Using the first structure (and the second, if we so choose) we have to shell (insertion flavor) sort the linked list of integers.

We have tried 2 different methods, one is to brute force the sort by traversing the gap elements, determining if they need to be moved somewhere in the sorted section of the linked list, and traversing the linked list from the beginning until we find an element larger then it in the sorted section. This worked, but took too long to run (it is a data structures and algorithms course, so we have to take into account run time).

The method we want to implement involves using the second structure to point to elements spaced by gap according to shell sort, and then to sort those values in the linked list for the gap sequence.

We know how to generate the sequence, but can anyone give us some tips on implementing the algorithm?

We already have the standard linked list formed.

We figure we will need to make a list create function, and a list insert function, but after that we are lost on how to start it.

Any and all tips and comments are appreciated!!!! Thanks!

EDIT: I cannot use any arrays in this implementation, the project is about the analysis of linked-lists and comparing their use and speed to arrays.

Improve this question
11
  • 2
    If you haven't done so yet, please read the Stack Overflow question checklist. You might also want to learn what a SSCCE is. Commented Feb 28, 2014 at 7:05
  • 1
    Thanks for the input Joachim. I've read that before and I knowingly posted no code; I am not looking for someone to debug some code for me, because what I have now is simply incorrect and useless at this point. I don't want someone to just give me the answer, I want to be able to generate the algorithm myself, maybe with a little guidance from the wonderful people at stack overflow. I tried to explain what we have done, what we have tried, what doesn't work, and where we want to go. If you insist, I will edit to include some code, but IMO I dont feel like this question warrants it. Thanks! Commented Feb 28, 2014 at 7:12
  • 1
    Can't you put all the pointers to the structures in an array, then use your shell sort to sort them. once the pointers are sorted, then make a small function to link them together Commented Feb 28, 2014 at 7:17
  • 1
    to put it in simple terms you want to sort the linked list using the shell-sort right?,I am not saying ditch the linked list. once you make the linked list. traverse though the list then place all the pointers in an array, once thats done use the shell sort to sort the pointers, then link them back together in a linked list.oh just saw you edit, if you have been specifically asked not to use any sort of arrays then I guess you cant do this. Commented Feb 28, 2014 at 7:28
  • 1
    what I mean is get all the pointers to the lists. 'struct node* next', and place them in an array of type 'struct node* array[number of nodes]' then access each element through the pointer make the comparison, and swap the pointers if necessary. so once the pointers are sorted you know which node comes first,second and so on..then just link them so array[0] will be the pointer to the Head, array[1] will be the next element of head and so on. Commented Feb 28, 2014 at 7:40

1 Answer 1

Reset to default
0

I thought I'll summarize what was said in the comments

1) initially you need to place all the pointers in an array.

struct node* element_pointers[size].

If you are not sure of how many elements the struct will contain then you need to malloc the array during runtim

struct node* element_pointer = malloc(sizeof(struct node*)*number_of elements)

2) when trying to put the pointers into the array you have 2 options

You could place the pointers in the array at the time you create each of the structs, or you can traverse through the linked list and place each next pointer into the array.

If you traverse the struct its going to be a simple while loop

int i =0;
element_pointer[i++] = head; //the pointer to the Head struct//
while( Head->next != NULL){
    i++;
    element_pointer[i] = Head->next;
    head = head->next}

3) when sorting the pointers. in your shell-sort function.

do the comparisons like this

 if(element_pointer[j]->value > element_ponter[j+gap]->value)

//swap if necessary

4) the swapping function would be like this

struct node *temp = element_pointer[j]
element_pointer[j] = element_pointer[j+gap]
element_pointer[j+gap] = temp.

As jim balter mentioned you could sort a doubly linked list as well, I found this on SO Sorting doubly linked list in c which I need to study as well.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.