Laboratory work number 3. "RING LISTS"

Objective: to investigate and study ring lists on the example of basic procedures.


The task of the work: to master the skills of writing programs for the study of basic procedures of list structures in the PASCAL programming language.


Operating procedure :

• 
  study the description of the laboratory work;

• 
  according to the task given by the teacher, to develop an algorithm for the program for solving the problem;

• 
  write a program in PASCAL;

• 
  debug the program;

• 
  to solve a task;

• 
  issue a report.

Brief theory

The fact that the lists are described in previous work. We looked at unidirectional lists, now we’ll look at ring lists.





As you can see in the figure, the list closes into a kind of “ring”: by following the links, you can move from the last element of the list to the title element. Because of this, lists of this kind are called ring lists .

To loop the list, you must assign the pointer to the last element to the beginning of the list (Ptr (p) = lst).

Ptr (p) - the pointer of the last element;

Lst is the index of the beginning of the list.

Algorithm

Operations with ring lists:

Insert an item in the ring list

To do this, you must perform the following steps:





a) Create an empty element pointed to by pointer q

q = getnode

b) Insert x into the information field of the created element

info (q) = x

c) Associate element X with element B

ptr (q) = ptr (p) - this means that the pointer

the created element is assigned the value of the pointer element p.

d) Associate element A with element X

ptr (p) = q - this means that following the element

And there will be an element pointed to by the pointer q.

Finally:





The insertion process has been illustrated in detail in a previous paper.

Remove item from ring list

Remove from the list the element that follows the element with the working pointer p.





To do this, you must perform the following steps:

a) Enter the pointer q, which will point to the element to be deleted.

q = ptr (p)

b) Put behind item A item B

ptr (p) = ptr (q)

c) Remember the information contained in the info field of the item to be deleted.

k = info (q)

d) Delete the item with the q pointer.

Freenode (q)

Finally:

Tasks

Options:

1) It is given the ring list containing 20 surnames of players of a football team. Split players into 2 groups of 10 people. In the second group falls every 12th person.


2) There are 2 ring lists containing the names of the athletes of 2 fencing teams. Make a draw. In the first team, every n-th player is selected, and in the second - every m-th player.


3) The task of Josephus.


4) There are 2 ring lists containing the names of the lottery participants and the names of the prizes. Win N people (every K-th). The number to recalculate prizes is t.


5) There are 2 lists containing the names of the students and the number of examination tickets. The number of recalculations for tickets - E, for students - K. Determine the numbers of tickets pulled out by students.


6) Given a list containing the list of goods. From the elements of the 1st list (products manufactured by SONY) create a new list.


7) Given 2 lists containing the names of the students of 2 groups. Transfer L students from the 1st group to the second. Conversion number -K.


8) Given 2 lists containing the list of goods produced by Concern BOSH and FILIPS. Create a list of products produced both by one and another company.


9) There are 2 lists containing the names of the players of the main team and the reserve. Make K replacements.


10) There are 2 lists containing the names of the soldiers of the 1st and 2nd platoons. During the attack of M, the man from the 1st platoon died. To replenish the soldiers of the 2nd platoon.


11) Given 2 lists containing the list of products and the names of buyers. Every Nth buyer buys Mth product. Display a shopping list.


12) There are 2 lists containing the names of products manufactured by SONY and SHARP. Create a list of products competing with each other products.