Solved

splitting a linked list

Posted on 2004-04-18
41
432 Views
Last Modified: 2013-12-14
That is what I want to do:
linked list:
2->4->3->18->15->7->9->NULL

the number is track number
a pointer called q_head points to 2
a pointer called q_tail points to 9

I wanna do SCAN disk algorithum...
If the track number, say, 14, split the linked list into two:
the request order would be 15->18->9->7->4->3->2
so I decide split the original link list to two:
1. higher track number order and sorted it i.e 15->18->NULL
2. lower track number order and sorted it i.e 2->3->4->7->9->NULL. then reverse it and combine to the 1 makes the request order....

I haven't sorted it..

typedef struct disk_rec disk;

struct disk_rec {
      int            proc;
      int            track;
      disk            *next;
      ReadOrWrite      type;
};
...
...
static      disk      *disk_q_head, *disk_q_tail;
...
get request and put in into the linked list...

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
    disk *target, *low_queue, *high_queue, *ptlow;
    int disk_head = 14;

    target = disk_q_head;
    low_queue =  (disk *) malloc(sizeof(disk));
    low_queue->proc = 0;    /dummy node/
    low_queue->track = 0;
    low_queue->type = 0;
    high_queue =  (disk *) malloc(sizeof(disk));
    high_queue->proc = 0;
    high_queue->track = 0;
    high_queue->type = 0;
    ptlow = low_queue;
    while (target != NULL)
    {
      if (target->track < disk_head)
      {
        low_queue->next = target;
        low_queue = low_queue->next;
       }
      if(target->track > disk_head)
      {
       high_queue->next = target;
       high_queue = high_queue->next;
       }
       target = target->next;
     }
     while(ptlow != NULL)
     {
       high_queue->next = ptlow;
       high_queue = high_queue->next;
       ptlow = ptlow->next;
      }
 }

I don't think it is working and I have no idea about the sorting...do I need another two list to do insertion sort.?

Thanks in advance.
0
Comment
Question by:redsar
  • 20
  • 15
  • 6
41 Comments
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Ok.
So what you want to do is:
from the current track position,take all higher track positions till end of platter and sort the,
Take all smaller track positions than the current pos.,sort them descending and attach them to the first sorted list.
0
 

Author Comment

by:redsar
Comment Utility
yes...
0
 

Author Comment

by:redsar
Comment Utility
but i'm not sure whether it works or how to do the sorting
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Also,what you could consider is keeping the list sorted by changing your insert routine.

Then,form a new list by deleting nodes having larger track numbers than the current position by deleting these nodes from the original list and inserting them in the new list.

Now,the original list has the nodes less than the current position in ascending order.

If you use doubly linked list,you could traverse the list in reverse order,insering each node into the other list.

Or sort the LL in reverse order and insert the head of this list to the tail of the other.
0
 

Author Comment

by:redsar
Comment Utility
btu did I create the two linked list properly and combine them? I don;t want the dummy node...
i think i get the idea, but technically, I can't make that run properly.thanks a lot...
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
You are allocating memory only for the header node for low_queue and high_queue.

if (target->track < disk_head)
     {
       low_queue->next = target;
       low_queue = low_queue->next;
      }

the first time this is executed,low_queue is an allocated node so its ok.
>low_queue = low_queue->next;
now,low_queue points to the node in the target node.
next time around:

>low_queue->next = target;

This modifies the target list since you are not allocating memory for nodes in low_queue.

the same goes for high_queue as well
0
 

Author Comment

by:redsar
Comment Utility
sorry, can't really get the point...
but i guess i need to allocate memory for the target..
may be i should so something like

if (target->track < disk_head)
     {
         target = (disk *)malloc(sizeof(disk));
       low_queue->next = target;
       low_queue = low_queue->next;
      }

0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
See,target points to your initial list.

You are constructing the other two lists:low_queue and high_queue.

What you could do is:

if (target->track < disk_head)
     {
       low_queue->next =(disk *)malloc(sizeof(disk));
//allocate a new node and make low_queue->next point to it.

//set the field values in the new allocated node.since low_queue->next points to the node,low_queue->next->proc points to its proc field
       low_queue->next->proc=target->proc;


>if (target->track < disk_head)
>    {
>        target = (disk *)malloc(sizeof(disk));
>      low_queue->next = target;
>      low_queue = low_queue->next;
>     }

Here what you would be doing is allocating a new node and making target point to it.After this you wouldnt be able to traverse the original list as the reference you had of that list was target and you now made it point to a new node.

       low_queue->next->track=target->track;
       low_queue->next->type=target->type;

//set the next pointer for this node to NULL.
       low_queue->next->next=NULL;

      }
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
I dont know what happened to the formatting of my prev post:

Here it is again:

See,target points to your initial list.

You are constructing the other two lists:low_queue and high_queue.

What you could do is:

if (target->track < disk_head)
    {
      low_queue->next =(disk *)malloc(sizeof(disk));
//allocate a new node and make low_queue->next point to it.

//set the field values in the new allocated node.since low_queue->next points to the node,low_queue->next->proc points to its proc field
      low_queue->next->proc=target->proc;
      low_queue->next->track=target->track;
      low_queue->next->type=target->type;

//set the next pointer for this node to NULL.
      low_queue->next->next=NULL;

     }

>if (target->track < disk_head)
>    {
>        target = (disk *)malloc(sizeof(disk));
>      low_queue->next = target;
>      low_queue = low_queue->next;
>     }

Here what you would be doing is allocating a new node and making target point to it.After this you wouldnt be able to traverse the original list as the reference you had of that list was target and you now made it point to a new node.
0
 

Author Comment

by:redsar
Comment Utility
thanks....I hope that's ok...

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
 disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
    if ( target->track < diskhead){
    low_q_tail->next = (disk *)malloc(sizaeof(disk));
    low_q_tail->next->proc = target->proc;
    low_q_tail->next->track = target->track;
    low_q_tail->next->type = target->type;
    low_q_tail->next->next =NULL;
    low_q_tail = low_q_tail->next;
   }
   if (target->track >diskhead){
   //the same procedure as low_q_tail;
   }
  //sort both link list, reverse the low_q
   //then attach
   low_q_head = low_q_head->next //point to the first node
   while(low_q_head != NULL)
   {
      high_q_tail->next =(disk *)malloc(sizeof(disk));
      high_q_tail->proc =  low_q_head->proc;
     ...
     ..
     high_q_tail = high_q_tail->next;  
     low_q_head = low_q_head ->next;
}
}


0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
This wont work as you have eliminated the dummy node and i didnt take care of that.
Initially low_q_tail is NULL and we use low_q_tail->next which hasnt been allocated.

Try this:

void
scan_schedule(int current_time, int *delay, int *nextproc)
{
disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
disk *low_h,*high_h; //points to the header of the lists.
int flag=0;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
   if( target->track < diskhead){
   low_q_tail = (disk *)malloc(sizeof(disk));
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
   low_q_tail->proc = target->proc;
   low_q_tail->track = target->track;
   low_q_tail->type = target->type;
   low_q_tail->next =NULL;
   low_q_tail = low_q_tail->next;
  }
   if(target->track>diskhead){
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
 //the same procedure as low_q_tail;
  }
 flag=0;
while(low_q_head != NULL)
  {
     high_q_tail=(disk *)malloc(sizeof(disk));
     if(flag==0)
    {
      high_h=low_q_tail;flag=1;
    }
     high_q_tail->proc =  low_q_head->proc;
    ...
    ..
    high_q_tail = high_q_tail->next;  
    low_q_head = low_q_head ->next;
}
}


I thought you might've needed the dummy node for header info. but the above code should work.

0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
You need low_h and high_h to refer to the list from the start coz you advance low_q_tail everytime you insert a new node so low_q_tail points to the last node.

0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Also,in your code,

>low_q_head = low_q_head->next //point to the first node

What does this statement do.Is this to jump over the dummy node?
If this is the case,you dont need it any more,just use low_h.

To attach the second list at the end of the first one,just do:

high_q_tail->next=low_h;

high_q_tail points to the last node in this list.Initially its next pointer is NULL.
Just make its NEXT pointer point to the first node of the low_q list.

Thats all.You dont need to attach node by node.

0
 

Author Comment

by:redsar
Comment Utility
thanks for your help,
I got another  idea, why don't simply pick the next element to serve in the disk_q, like this:
34>6->19->32->78->NULL
disk head = 10
the disk head moves up initially

disk *x, *target;
x = target = diskhead;
int foundtarget = 0
while (x !=NULL)
{
   if ( x->track > diskhead)
{
  if ( foundtarget == 0)
  {
      target = x;
      foundtarget = 1;
      break;
   }
  if (foundtarget == 1)
  {
    if (target ->track > x->track)
       traget = x;
    else
      break;
   }
}
   x = x->next;  
}
free(target);
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Sorry.I couldnt get your point in your last post.

And if free(target) is meant to remove the node from the Queue list,you need to reassign the pointers as well otherwise u'd have a broken list.

For e.g.:

Original List:
34>6->19->32->78->NULL

You want to delete 19.free(19) just frees the memory allocated for the node 19.
But 6's next pointer still points to the location where 19 was allocated.you need to assign 6's next pointer to 19's next pointer before freeing it.



0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Sorry.I couldnt get your point in your last post.

And if free(target) is meant to remove the node from the Queue list,you need to reassign the pointers as well otherwise u'd have a broken list.

For e.g.:

Original List:
34>6->19->32->78->NULL

You want to delete 19.free(19) just frees the memory allocated for the node 19.
But 6's next pointer still points to the location where 19 was allocated.you need to assign 19's next pointer to 6's next pointer before freeing it.



0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
The second post is correct.
>you need to assign 19's next pointer to 6's next pointer before freeing it.
0
 

Author Comment

by:redsar
Comment Utility
thanks....
I think I'm lost...
this is my code so far..
void
scan_schedule(int current_time, int *delay, int *nextproc)
{
   disk *x, *target, *curr, *diskend;
   x = curr = target = disk_q_head;
   int foundtarget = 0;
   int diskhead = curr_track;
   /* There are no requests left and nothing for the disk to do */
   if(x == NULL) {
               idle = 1;
               last_busy = current_time;
               *nextproc = -1;
               return;
      }
      /* How long has the disk been idle? */
      if(idle == 1) {
                  time_waiting += (current_time-last_busy);
      }
      idle = 0;

   /*keep testing if there are requests in the queue */
   while(x != NULL  && curr_direction == 1){
         /* find a node that has a higher tracks in the current direction */
         if (x->track > diskhead){
               /* If the algorithm has not found any target yet. */
               if (foundtarget == 0){
                     target = x;
                     foundtarget = 1;
                     break;
           }

            /* If the algorithm has found target then compare the track number */
                  if (foundtarget == 1){
                        if(target->track > x->track)
                           target = x;
                        else
                           break;
                   }
       }
      x = x->next;
   }

   if (foundtarget == 1){
         /* remove the process form linked list */
         while(curr->next != target)
                         curr = curr->next;
         curr->next = target->next;

         /* is the data in the cache ? */
            if ((in_cache = is_in_cache(target->track))) {
                  if (target->type == Read)
                        num_cache_hits++;
            } else {
                  add_to_cache(target->track);
                  if (target->type == Read)
                        num_cache_misses++;
            }
            /* decide if we have to move the disk head */
                  /* note that we are not doing write-behind caching */
                  if ((target->type == Write) || !in_cache)
                        mustmove = abs(curr_track-target->track);
                  num_tracks += mustmove;
                  if(mustmove > 0) {
                        num_seeks++;
                        *delay = mustmove*track_cost + start_cost;
                        curr_track = target->track;
                  } else
                        *delay = 0;
                  /* (Getting data from the cache or the current track takes "no time") */
                  *nextproc = target->proc;
            free(target);
}
            /*
            * if the algorithm did not find any requests have higher track number in the current direction
            * seek to disk end and then change the direction
            */
         diskend = (disk *)malloc(sizeof(disk));
         if(diskend == NULL) {
                  fprintf(stderr, "Ran out of memory.\n");
                  exit(1);
            }
            diskend->proc = 0
            diskend->track = 99;
            diskend->type = 0;

         if (foundtarget == 0){
              curr_track = diskend->track;
              curr_direction  = 0
              free(diskend);
   }
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Repeating my comment in your other thread,

Keeping the list sorted would be a better and much efficient option.
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 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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

Author Comment

by:redsar
Comment Utility
I guess, there may be more and more requests keep coming in...so even if I sorted the linked list, and i can only process one request at a time...I don;t know how to explain...
If I scanning the entire list evertime...I can handle the coming requests properly, because i pick the element in the current link list...
foe example
Initially, the requests are
3->4->34->23->21->NULL;
disk head = 5
execute the scan_schedule
pick 21 then more requests come in
3->4->34->23->20->80->NULL;
pick 20 when exe another time
then 23...34...80...

If I sorted the origianlly linked list...
1. 3->4->NULL
2. 21->23->34->NULL
combine
21->23->34->4->3->NULL
I would serve the request in this order no matter the more requests coming in...so I just ignore the coming requests even if they are closer to the current disk head...

sorry for the english...I'm not sure wether I'm on the right track...
0
 

Author Comment

by:redsar
Comment Utility
hi, i don't quite understand some part of the code
void
scan_schedule(int current_time, int *delay, int *nextproc)
{
disk *target, *low_q_head, low_q_tail, *high_q_head, *high_q_tail;
disk *low_h,*high_h; //points to the header of the lists.
int flag=0;
..

target = disk_q_head;

low_q_head = low_q_tail = NULL;
high_q_head = high_q_tail = NULL;

while(target != NULL){
   if( target->track < diskhead){
   low_q_tail = (disk *)malloc(sizeof(disk));
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;
   }
   low_q_tail->proc = target->proc;
   low_q_tail->track = target->track;
   low_q_tail->type = target->type;
   low_q_tail->next =NULL;
   low_q_tail = low_q_tail->next;
  }
   if(target->track>diskhead){
   if(flag==0)
   {
     low_h=low_q_tail;flag=1;  //IS that high_h = high_q_tail; flag =1;
   }
 //the same procedure as low_q_tail;  
  }
 flag=0; //why?
while(low_q_head != NULL)
  {
     high_q_tail=(disk *)malloc(sizeof(disk));
     if(flag==0)
    {
      high_h=low_q_tail;flag=1; //why  pount low_q_tail to high_h???
    }
     high_q_tail->proc =  low_q_head->proc;
    ...
    ..
    high_q_tail = high_q_tail->next;  
    low_q_head = low_q_head ->next;
}  //missing target = target->next???
}
thanks for your help again
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 50 total points
Comment Utility
Do you have the code for splitting, sorting and merging right ? If yes then accomodating new requests should be easy

if ( new_request > diskhead )
{
          insert in a position such that request_in_list < new_request < next_request_in_list
                                  OR
          request_in_list < new_request > next_request_in_list  (between highest request so far and 99)
}

else if ( new_request < diskhead )
{
          insert in a list s.t. request_in_list < new_request < next_request_in_list
                                 OR
           end of list
}
else if ( new_request == diskhead )
{
           service right now !!!
}
0
 

Author Comment

by:redsar
Comment Utility
i don;t think all the splitting, sorting working all right...
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
post your most recent code and the problems you are having with it
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Have you tried executing your code?
0
 

Author Comment

by:redsar
Comment Utility
void
scan_schedule(int current_time, int *delay, int *nextproc)
{
      disk *x, *target, *curr, *diskend;
      int foundtarget = 0;
      int diskhead = curr_track;
    int      mustmove = 0;
      int      in_cache = FALSE;
    x = curr = target = disk_q_head;

      /* There are no requests left and nothing for the disk to do */
      if(x == NULL) {
            idle = 1;
            last_busy = current_time;
            *nextproc = -1;
            return;
      }
      /* How long has the disk been idle? */
      if(idle == 1) {
            time_waiting += (current_time-last_busy);
      }
      idle = 0;

   /*find the next requsts that has higher track number*/
   while(x != NULL  && curr_direction == 1){
         if (x->track > diskhead){
               /* If the algorithm has not found any target yet. */
               if (foundtarget == 0){
                     target = x;
                     foundtarget = 1;
               }

            /* If the algorithm has found target then compare the track number */
                  if (foundtarget == 1){
                        if(target->track > x->track)
                           target = x;
                        else
                           break;
                   }
       }
      x = x->next;
   }
   if (foundtarget == 1){
   while( x !=NULL && curr_direction == 0){
         if ( x->track < diskhead){
               target  = x;
               foundtarget =1;
         }
        if (foundtarget == 1){
              if(target->track < x->track)
                    target = x;
          }
                   x= x->next;
     }
         /* remove the process form linked list */
         while(curr->next != target)
                         curr = curr->next;
         curr->next = target->next;

         /* is the data in the cache ? */
            if ((in_cache = is_in_cache(target->track))) {
                  if (target->type == Read)
                        num_cache_hits++;
            } else {
                  add_to_cache(target->track);
                  if (target->type == Read)
                        num_cache_misses++;
            }
            /* decide if we have to move the disk head */
        /* note that we are not doing write-behind caching */
                  if ((target->type == Write) || !in_cache)
                        mustmove = abs(curr_track-target->track);
                  num_tracks += mustmove;
                  if(mustmove > 0) {
                        num_seeks++;
                        *delay = mustmove*track_cost + start_cost;
                        curr_track = target->track;
                  } else
                        *delay = 0;
                  /* (Getting data from the cache or the current track takes "no time") */
                  *nextproc = target->proc;
            free(target);
  }

            /*
            * if the algorithm did not find any requests have higher track number in the current direction
            * seek to disk end and then change the direction
            */
         diskend = (disk *)malloc(sizeof(disk));
         if(diskend == NULL) {
                  fprintf(stderr, "Ran out of memory.\n");
                  exit(1);
            }
            diskend->proc = 0;
            diskend->track = 99;
            diskend->type = 0;

         if (foundtarget == 0 && curr_direction == 1){
              curr_track = diskend->track;
              curr_direction  = 0;
              free(diskend);
           }
        /* if no requests on the left side then change the direction to up again */
         if (foundtarget == 0 && curr_direction == 0){
                   curr_track = diskend->track;
                   curr_direction  = 1;
                   free(diskend);
           }

}  /* scan_schedule() */
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
post your most recent code ******and the problems you are having with it******

Makes my task a bit easier if you do not mind :o)
0
 
LVL 9

Assisted Solution

by:ankuratvb
ankuratvb earned 350 total points
Comment Utility
>if(flag==0)
>  {
>    low_h=low_q_tail;flag=1;  //IS that high_h = high_q_tail; flag =1;
>  }

Yes.

>flag=0; //why?
>while(low_q_head != NULL)
> {
>    high_q_tail=(disk *)malloc(sizeof(disk));
>    if(flag==0)
>   {
>     high_h=low_q_tail;flag=1; //why  pount low_q_tail to high_h???
>   }

I guess i misplaced the high_q code down here
Now,since its in the same loop,you'll need 2 flags.

do:
int flag1=0;//along with flag's declaration.

>if(flag1==0)
>  {
>    low_h=low_q_tail;flag1=1;  //IS that high_h = high_q_tail; flag =1;
>  }

in the first while loop.

To attach the low_q to the high_q.
SInce high_q_tail points to the last node of the high list,simply do:
high_q_tail->next=low_h;

Here i am assuming that low_h points to the first node in the low list after reversing it.


0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
Redsar,

If the problem is not solved as yet, I can reopen the question and we can continue discussion

sunnycoder
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
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_20958636.html
0
 

Author Comment

by:redsar
Comment Utility
Thanks guys, basically the thing is i don't really understand the project...I can't implement what I want...I got segmentation fault when running...and the project package consist of many files, i can't post all the related file here, so it's hard to explain what the problems are...I wanna learn...how can I post all the realted files to u guys and post my code to see what's going wrong?
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Put it up on a site,there are lots of free web hosting sites going around.

You can try www.freewebs.com

0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Are the source files large enough that they cant be posted here?
0
 

Author Comment

by:redsar
Comment Utility
how can i attach the source files here?
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
you cannot attach the files here .... post them in some other site which gives you free web space e.g. geocities or freewebs and post the link here
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
I meant copy the code from your source file and paste it here. in a post.

The website idea is much better.

0
 

Author Comment

by:redsar
Comment Utility
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
Redsar,

that is quite a bit of code .. I may have sometime during the weekend

1. point out what functions you need help with (just the name will suffice) and what help (what is not working)
2. Do you want me to reopen this question ?

sunnycoder
0
 

Author Comment

by:redsar
Comment Utility
Thanks, I just need to implement three types disk scheduling, what i have done is in my code. I understand the disk scheduling, but the projects seems working for multiprocess in one time...my code obviously not working...

I guess I'll give points to u guys , cos u guys help a lot.
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Hi redsar,

>that is quite a bit of code.
Seriously. :~))

To help you a little bit(this isnt the exact program you want),
I wrote my own program for SCAN based on the same structure defn as yours.

Here it is.Its quite simple and i've documented it as well.

//SCAN Schedule Implementation
#include<stdio.h>
#include<alloc.h>
struct node
{
      int proc;
      int track;
      struct node *next;
      int type;
}*p;
//p is the global reference to start of list
void scan_schedule(struct node *,int);
void store(struct node *,int,int,int);//param.(start of list,proc,track,type)
void disp(struct node *);
void del(struct node *,int);//param.(start of list,node number)
void main()
{
      int curr_track=30;
      p=NULL;
      store(p,1,70,1);
      store(p,1,60,1);
      store(p,1,50,1);
      store(p,1,40,1);
      store(p,1,30,1);
      store(p,1,20,1);
      store(p,1,10,1);
      scan_schedule(p,curr_track);
}
void store(struct node *q,int pr,int tr,int ty)
{
      if(q==NULL)
      {
            p=malloc(sizeof(struct node));
            p->proc=pr;
            p->track=tr;
            p->type=ty;
            p->next=NULL;
      }
      else
      {
            while(q->next!=NULL)
            {
                  q=q->next;
            }
            q->next=malloc(sizeof(struct node));
            q->next->proc=pr;
            q->next->track=tr;
            q->next->type=ty;
            q->next->next=NULL;
      }
}

void disp(struct node *q)
{
      printf("\nValues:");
      while(q!=NULL)
      {
            printf("\n%d %d %d ",q->proc,q->track,q->type);
            q=q->next;
      }
      getch();
}

void del(struct node *q,int n)
{
      int c=1;
      struct node *temp;
      if(n==1)
      {
            if(p==NULL)
            {
                  printf("Error");getch();return;
            }
            else
            p=p->next;
      }
      else
      {
            while(c<n-1)
            {
                  if(q->next==NULL)
                  {
                        printf("Error");getch();return;
                  }
                  q=q->next;c++;
            }
            if(q->next==NULL)
            {
                  printf("Error");getch();return;
            }
            q->next=q->next->next;
      }
}

void scan_schedule(struct node *q,int curr_track)
{
      int nc,deln;
      int start=0;//define start of platter
      int end=100;//define end of platter
      struct node *target;
      //node to store the target node which is to be serviced

      while(p!=NULL)//keep looping till there are nodes in the list
      {
            //this do loop services all nodes higher than current pos
            do
            {
                  target=NULL;
                  //target set to NULL to avoid changes to existing nodes
                  //since i use target to point to nodes in the list
                  //if i dont remove the reference,all serviced nodes
                  //would get track number=end
                  target->track=end;
                  //set target's track number to end of platter
                  nc=1;//counts node number starting from 1
                  while(q!=NULL)
                  {
                        if(q->track >= curr_track && q->track <= target->track)
                        {
                              target=q;deln=nc;//select target,set node number to be deleted
                        }
                        q=q->next;nc++;
                  }
                  if(target->track!=end)
                  {
                        curr_track=target->track;printf("\nService:%d",curr_track);
                        del(p,deln);//delete serviced node
                        q=p;//set q to point to start of list
                  }
            }
            while(target->track!=end);

            q=p;nc=1;
            //this do loop works backward servicing all nodes
            //less than current position
            do
            {
                  target=NULL;
                  target->track=start;
                  nc=1;
                  while(q!=NULL)
                  {
                        if(q->track <= curr_track && q->track >= target->track)
                        {
                              target=q;deln=nc;
                        }
                        q=q->next;nc++;
                  }
                  if(target->track!=start)
                  {
                        curr_track=target->track;printf("\nService:%d",curr_track);
                        del(p,deln);
                        q=p;
                  }
            }
            while(target->track!=start);
      }
}

The logic is what you wanted,keep scanning from one end to the other till you have nodes in the list,and always pick up the node that is closest to the current position in the direction that we are scanning.


Difference to your problem:

I delete nodes according to node number not according to node address.

HTH atleast a little bit.
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org (http://seleniumhq.org) Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.

771 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

14 Experts available now in Live!

Get 1:1 Help Now