Lab number 2. "LIST OF DATA STRUCTURES"

Objective: to investigate and study the list data structures. The task of the work: to master the skills of writing programs for the study of list structures in the programming language PASCAL. 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 So far, we have considered only static program objects. This term refers to objects that are generated immediately before the execution of the program, exist during the entire time of its execution and the size of the values ​​of which do not change during the execution of the program. Since static objects are generated before the execution of the program and the size of their values ​​can be distinguished at the stage of translation of the source text of the program in the language of the machine. However, the use of only static objects in programming can cause certain difficulties, especially from the point of view of obtaining an efficient machine program, and such efficiency can be extremely important in solving a number of problems. The fact is that sometimes we do not know in advance not only the size of the value of a program object, but even whether this object will exist or not. Such software objects that already appear during program execution are called dynamic objects. In the PASCAL language for working with dynamic objects, a special data type is provided - the so-called reference type. The value of this type is a reference to a program object, through which the object is directly accessed. In machine language, such a link is just represented by indicating the place in the memory of the corresponding object. In this case, to describe actions on dynamic objects, each such object in the program is assigned a static variable of reference type — in terms of these reference variables, and actions on the corresponding dynamic objects are described. So, dynamic data structures have two features: 1. The number of elements in the structure is not definable in advance; 2. Elements of a dynamic structure do not have a rigid linear order. They can be scattered in memory. In order to link the elements of a dynamic structure among themselves, the structure of the element in addition to the information field includes fields of pointers (links with other elements of the structure). p1, p2 - pointers containing the addresses of the elements with which the element is associated. The most common dynamic structures are linked lists . From the point of view of logical representation distinguish linear and nonlinear lists. In linear lists, links are strictly ordered. The previous item pointer gives the address of the next item or vice versa. Linear lists are simply linked and doubly linked lists. To nonlinear - multiply linked lists. A list item is generally a combination of a record field (information field) and one or more pointers. Linear unidirectional lists By simply-connected lists, we mean an ordered sequence of elements, each of which has 2 fields: the info info field and the ptr pointer field. The peculiarity of the pointer is that it gives only the address of the subsequent element of the list. For unidirectional lists, the index field of the last item in the list is empty nil. Lst is the index of the beginning of the list. He presents the list as a whole. Sometimes the list may be empty, i.e. There are no items in this list. In this case, lst = nil.

Algorithm

Operations with single-linked lists.

1. 
   Insert an element at the beginning of a single-linked list.

Insert at the beginning of this list an item whose information field contains the variable D. To do this, you must perform the following steps:

a) Create an empty element pointed to by the pointer p.





b) Assign the value D to the information field of the created element.





c) Associate a new item with a list.


Ptr (p) = lst (lst - no longer indicates the beginning of the list)


d) Move the lst pointer to the top of the list.


Finally:

Removing an element from the beginning of a single-linked list

Delete the 1st item in the list, but remember the information contained in the info field of this item.





To do this, you must perform the following steps:

a) Enter the pointer p, which will point to the item to be deleted.

P = lst

b) Store the info field of the element referenced by p into some variable (x).

X = info (P)

c) Move the lst pointer to the new beginning of the list.

lst = ptr (P)

d) Delete the item pointed to by p.

Freenode (p)

Finally:

Insert item into list

Paste into this list before the element pointed to by pointer p, an element with information field x.





To do this, you must perform the following steps:

a) Create an empty element pointed to by the pointer q.

Q = getnode

b) Enter x into the information field of the created item.

Info (Q) = x

c) Associate element x with element B.

Ptr (Q) = Ptr (P) - this means that the pointer of the created element is assigned the value of the pointer of the element p.

d) Associate element A with element x.

Ptr (p) = Q - this means that the next element A will be the element pointed to by the pointer Q.

Finally:

Removing an item from a single-linked 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 item to be deleted.

Q = ptr (p)

b) Put item B behind item A.

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 pointer Q.

Freenode (q)

Finally:

Tasks

Options:

1. Write a program for moving the element to n positions.

2. Create a copy of the list.

3. Add an item to the top of the list.

4. Glue the two lists.

5. Remove the nth item from the list.

6. Insert an item after the nth item in the list.

7. Create a list containing elements common to the two lists.

8. Sort the items in the list in ascending order.

9. Delete every second list item.

10. Delete every third item in the list.

11. Sort the list items in descending order.

12. Clear the list.