Theory of data structures and processing algorithms

Introduction 10

part 1.
introduction to the theory of data structures and algorithms for their processing 12

1.Types of data 13

1.1 Integer type - INTEGER 14

1.2 Real type - REAL 15

1.3 Boolean type - BOOLEAN 16

1.4 Character Type - CHAR 16

1.5 Pointer type - POINTER 17

1.6 Standard user types 18

1.6.1 Listed 18

1.6.2 Range or interval 19

2. Static and semi-static data structures 20

2.1 Levels of data presentation 21

2.2 Classification of data structures 22

2.3 Static data structures 23

2.3.1 Vectors 23

2.3.2 Arrays 24

2.3.3 Records 24

2.3.4 Tables 27

2.4 Semi-static data structures 28

2.4.1 Stacks 29

2.4.2 Queue 31

2.4.3 Dec 39

3. Dynamic data structures 41

3.1 Linked Lists 42

3.1.1 Singly Lists 42

3.1.2 Ring-related list 43

3.1.3 The doubly linked list 44

3.1.4 Ring doubly linked list 45

3.2 Implementing Stacks Using Simply-Connected Lists 46

3.3 Organization of Getnode, Freenode operations and disposal of released elements 49

3.3.1 GetNode 49 operation

3.3.2 FreeNode 50 Operation

3.3.3 Disposal of freed items on multiply linked lists 50

3.4 A simply-connected list, as an independent data structure 51

3.4.1 Inserting and Retrieving Items from a List 53

3.4.2 Examples of typical operations on lists 54

3.4.3 Header elements in lists 57

3.5 Nonlinear related structures 58

4. Recursive data structures 62

4.1 Trees 62

4.1.1 Representation of trees 64

4.2 Binary trees 64

4.2.1 Reduction of m-ary tree to binary 66

4.2.2 Basic tree operations 68

4.2.3 Algorithm for creating a binary search tree 69

4.2.4 Passage of binary trees 71

5. Search 74

5.1 Sequential Search 74

5.2.Index search 77

5.3. Sequential Search Efficiency 79

5.4. Efficiency of indexed sequential search 79

5.5 Search Optimization Methods 80

5.5.1 Reordering the lookup table by swapping a found item to the top of the list 81

5.5.2. Transposition method 82

5.5.3. Optimal Search Tree 84

5.6 Binary search (halving method) 86

5.7. Search for binary tree 88

5.8 Search with insert (with inclusion) 89

5.9 Search with deletion 91

6. Sorting 95

6.1. Sort by direct inclusion 96

6.2 Sorting by direct selection 99

6.3. Sort using direct exchange (bubble sort) 100

6.4. Improved sorting methods 102

6.4.1. Quick Sort 102

6.4.2 Shell Sorting (Sorting in Diminishing Pitch) 104

7. KEY CONVERSION (INSTALLATION) 108

7.1. Selecting a conversion function 108

7.2. Algorithm 110

part 2.
Workshop on structures and data processing algorithms in computer 114

methodical guide to laboratory work 115

Organizational and methodical instructions 115

Laboratory work number 1. "Semi-structured data structures" 117

Brief theory 117

Algorithm 119

Assignments 121

Lab number 2. "LIST OF DATA STRUCTURES" 122

Brief theory 122

Linear unidirectional lists 124

Algorithm 125

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

Inserting item into list 127

Removing an item from a single-linked list 127

Quests 128

Lab number 3. "RING LISTS" 130

Brief theory 130

Algorithm 131

Insert an item in the ring list 131

Removing an item from the ring list 132

Tasks 133

Lab number 4. "MODEL OF MASS SERVICE" 135

Brief theory 135

Algorithm 137

The procedure for adding an item to the top of the list. 137

The removal procedure from the top of the list. 137

The procedure for adding an item to the list. 137

Uninstall procedure 138

Quests 138

Laboratory work number 5. "BINARY TREES (basic procedures)" 140

Brief theory 140

Algorithm 143

The procedure for creating a binary tree 143

Tree Traversal Procedures 145

Binary Tree Search Procedure 146

The procedure for including an element in the tree 147

Procedure for removing an item from a binary tree 148

Tasks 150

Laboratory work number 6. "SORTING BY DIRECT INCLUSION METHOD" 153

Brief theory 153

Algorithm 155

Quests 156

Laboratory work number 7. "SORTING BY DIRECT SELECTION METHOD" 158

Brief theory 158

Algorithm 162

Quests 163

Lab number 8. "SORTING BY DIRECT EXCHANGE" 165

Brief theory 165

Algorithm 167

Bubble Method Algorithm 167

Algorithm method Quiksort 167

Quests 168

Lab number 9. "SORTING BY TREE" 170

Brief theory 170

Algorithm 172

Creating a binary search tree: 173

Traversing the tree from left - to the right 174

Tasks 174

Laboratory work number 10. "RESEARCH OF METHODS OF LINEAR AND BINARY SEARCH" 177

Brief theory 177

Algorithm 178

Linear search 178

Search by division in half (binary search). 180

Quests 182

Laboratory work №11. "RESEARCH OF METHODS OF SEARCH OPTIMIZATION" 184

Brief theory 184

Algorithm 186

Reordering by swapping to the top of the list 186

Transposition method 187

Quests 188

Laboratory work No. 12. "SEARCH BY WOOD WITH INCLUSION" 191

Brief theory 191

Algorithm 192

Tasks 194

Laboratory work number 13. "SEARCH BY TREE WITH EXCEPTION" 196

Brief theory 196

Algorithm 197

Tasks 200

TESTS FOR LABORATORY WORKS 202

Methodical guide to coursework
work 217

1 Requirements for coursework 217

2. A tentative list of coursework 218

3. An example of performing a course work 219

3.1 Statement of the Problem 219

3.2 Brief Theory 219

3.3 Research Method 223

3.4 study results 223

3.5 Test Case 225

3.6 Conclusions 226

3.7 Description of the procedures used in the program 226

Conclusion 238

Literature 240

attachment.
Tests with answers 241