Additional Linked List Problems (Try to Solve yourself)
[Solve the Problems]
Page 474 (chapter 9) à Questions: 6,7,8,9,10,17*
[Read] Double linked list:
page 487-489
[Read] Spare matrices: page
501-504
[Solve the Problems]
A) Exercise 9.5 (page 508):
6,7,8,24,25,26
B) Page 512: 19*, 20*, 21
17. In the ‘josephus problem’,
a group of soldiers is surrounded by the enemy and 1 soldier is to be selected
to ride for help. The soldiers are arranged in circle. When the count reaches
n, that soldier is removed. And count starts again from next soldier. This
process continues until 1 remains. Write a program to implement this selection
strategy.
19. In a multi-user
environment, jobs with various memory requirements are submitted to the
computer system, and the OS allocates a portion of memory to each job using
some memory management scheme. One popular scheme maintains a circular doubly
linked list of free memory blocks. When a memory request is received, this list
is searched to locate the first available block that is large enough to satisfy
the request. An appropriate portion of the block is allocated to the job, and
any remaining portion remains on the free list.
Write and test a function to
implement this first-fit memory management scheme. Assume that memory blocks
are represented as ‘structs’ that contain the start address of available block
and its size, together with the links necessary to maintain a circular doubly
linked list. The function should return the address of the allocated block or
an allocation that the request cannot be satisfied.
20. Another common
memory-management strategy is the best-fit scheme, in which the free list is
scanned and the memory block that best fits the request is allocated. This
block is either the first block whose size is equal to the request or the block
whose size least exceeds the request. Write the function to use the best-fit
scheme.