• C

I wanna simualate the SCAN disk algorithm
17->23->3->18->50->6->NULL;
i wanna pick 23 when executed first time: 17->3->18->50->6->NULL;
then 50 :17->3->18->6->NULL
then there are no more in that direction and go to 99:
then change the direction to 18: 17->3->6->NULL..ans so on...
typedef struct disk_rec disk;

struct disk_rec {
int            proc;
int            track;
disk            *next;
};
...

disk *x, *target, *curr;
x = curr = target = disk_q_head;
int foundtarget = 0;
while(x != NULL && x->track > diskhead)
{
if (foundtarget == 0)
{
target = x;
foundtarget = 1;
break;

}
if (foundtarget == 1)
{
if(target->track > x->track)
target = x;
else
break;
}
x = x->next;
}
while(curr->next != target)
curr = curr->next;
curr->next = target->next;
free(target);
When the target is the max and need to go to disk end, how can I know it , and what's with the above code....can't work it out...
thanks for help
###### Who is Participating?

Commented:
I still say that keeping the list sorted always by modifying your insert function would be a better option.

Then,you have 2 options:

Keeping the list ordered shouldnt be a problem.
Delete nodes larger than current position and insert into another list.
Sort the remaining nodes in descending order and insert onto the other list.

Using doubly linked list,sorting in reverse order would be simpler.

0

Commented:
>When the target is the max and need to go to disk end, how can I know it
Iterate through the list and if there is no entry > diskhead, you need to do to the end of the list

>what's with the above code....can't work it out...
pls elaborate
0

Commented:
while(x != NULL && x->track > diskhead)    ...... this loop will break as soon as you encounter a value less than diskhead ... probably this is not what you want ... keep loop condition to be while ( x!= NULL) and inside the loop if x->track < diskhead then continue !!!
{
if (foundtarget == 0)
{
target = x;
foundtarget = 1;
break;

}
if (foundtarget == 1)
{
if(target->track > x->track)
target = x;
else
break;
}
x = x->next;
}
The method you are using is O(n^2) .... you traverse the entire list every time !!! The idea of splitting the list into sorted order was superior ... it will take only O(nlogn) time
0

Commented:
Here,you are scanning the entire list everytime a request is to be selected.
If you have the list sorted,traverse till the track number becomes greater than the current position,then delete all subsequent nodes from the original list.This(deletion) can be done in O(1) time.

Form a list of the deleted nodes.This can also be done in O(1) time as you just have to point to the start of the deleted nodes.

Reverse the list and attach to the first list.
0

Commented:
>If you have the list sorted,traverse till the track number becomes greater than the current
>position,then delete all subsequent nodes from the original list.This(deletion) can be done in O(1)
>time.
1. Sorting implies minimum O(n^2)
2. Deletion of one node is O(1) ... since you can have O(n) node to delete, deletion will be O(n)

>Form a list of the deleted nodes.This can also be done in O(1) time as you just have to point to
>the start of the deleted nodes.
>Reverse the list and attach to the first list.
Reversing is again O(n)
0

Commented:
You dont have to delete all nodes one by one.

Just set the next pointer of the last node that has track number less than current position to NULL.

Setting a pointer takes O(1) time.
0

Commented:
>1. Sorting implies minimum O(n^2)

1. Sorting implies minimum O(nlog(n))
0

Commented:
and how about freeing the memory ?
0

Commented:
>and how about freeing the memory ?

We dont need to free memory right now coz we will be inserting them back into the list after reversing them.

For e.g.
if this is the original list:
Current poistion:10
17->23->3->18->50->6->NULL;
Sorted would be:(i say dont sort it when u need it,keep it sorted as u insert nodes)

3->6->17->18->23->50->NULL;

Traverse till u have track numbers less than 10:
set the next pointer of the last such node to NULL and save the address of the next node in another variable.
So,now you have two lists:
3->6->NULL
and
17->18->23->50->NULL;

Now reverse the first list and attach to the end of the second.

Since,we will be attaching the deleted nodes again into the list,we dont need to free the mem. allocated to them.
0

Commented:
>We dont need to free memory right now coz we will be inserting them back into the list after reversing them
then why add the overhead of "deleting" ... or was it just a misnomer
0

Commented:
I guess my english is getting worse by the day. :~)

What i meant by deleting was to remove a number of nodes from one list and make them into another list.

I guess splitting would've been a better word.

0

Author Commented:
thanks for the help...I'm totally lost, but anyway thanks a lot.
I get yours idea, but I just can't extend it into code....
0

Commented:
C'mon redsar,thats not fair.You are not supposed to accept an answer until your prolem is solved.

If its the code you cant understand,i'll try again.

Give us a chance.

I request sunny on the OP's behalf to unaccept the answers of this question as well as the other question:

http://oldlook.experts-exchange.com:8080/Programming/Programming_Languages/C/Q_20957942.html
0

Commented:
ankur,

I would be happy to open both the questions if redsar shows some interest.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.