Dynamic, -
Pascal C++.
, , .
PNode TNode.
PNode TNode Pascal
:
type
PNode = ^TNode;
TNode = record
Data: integer;
Next: PNode;
Prev: PNode;
end;
++:
struct TNode
{
int Data;
TNode* Next;
TNode* Prev;
};
typedef TNode* PNode;
Dynamic1Dynamic2,
(Dynamic3Dynamic28) TNode -
Data Next (. Dynamic1);
(Dynamic29Dynamic80) TNode (.
Dynamic29).
-
, ( )
( ) .
, , -
, 1.
-
nil ( Pascal).
Dynamic1. P 1 TNode, Data (
) Next ( PNode TNode).
Next .
Data , P 2 .
Dynamic2◦. P 1 TNode. Next
, , , -
, , Next nil ( ,
). Data
, ( )
.
Dynamic3Dynamic13 (stack)
- TNode (. Dynamic2).
Next nil. (top)
.
( nil). -
Data.
Dynamic3◦. D P 1 . -
D P 2
.
Dynamic4. N (> 0) N . , -
( ),
.
Dynamic5◦. P 1 .
|
|
|
() D, P 2
.
, P 2= nil. -
, .
Dynamic6. P 1 , -
.
118
. . . Programming Taskbook 4.6
. .
, .
Dynamic7. P 1 ( , P 1= nil).
. -
N ( 0).
, -
.
Dynamic8◦. P 1 P 2 . -
(
,
) . -
.
Dynamic9◦. P 1 P 2 . -
,
(
, ). -
,
.
( ,
nil).
.
Dynamic10◦. P 1 . -
,
, (
, ;
). -
( nil).
.
Dynamic11◦. P 1 ( , P 1= nil).
N (> 0) N . TStack
Top PNode ( )
Push(S, D), S
D (S TStack, D
). Push
(
) .
Dynamic12◦. P 1 ,
. TStack (. Dynamic11), -
Pop(S) , S ()
, ,
(S TStack).
Pop -
|
|
|
. (
,
nil).
Dynamic13. P 1 . TStack (.
Dynamic11), StackIsEmpty(S)
( TRUE, S , FALSE ) Peek(S)
( S,
). S -
TStack. , Pop
Dynamic12, (
, ) -
. StackIsEmpty
, ,
.
Dynamic14Dynamic28 (queue) -
- TNode (. Dynamic2).
Next nil. (-
, head) , (, tail)
.
, ,
.
nil. ,
Data.
Dynamic14. 10 . ,
(
, ), P 1 P 2
.
120
. . . Programming Taskbook 4.6
Dynamic15. 10 . : -
(1, 3,..., 9),
(2, 4,..., 10); -
.
, .
Dynamic16. 10 . : -
,
(
). ,
( ;
nil).
Dynamic17. D P 1 P 2
( , P 1= P 2= nil).
D
.
Dynamic18. D P 1 P 2 ,
. D
() .
.
,
.
Dynamic19. N (> 0) P 1 P 2 -
. N
( N ,
). (
nil). -
, .
Dynamic20. P 1 P 2 . -
,
, (
,
). (
|
|
|
nil). -
, .
Dynamic21. ; P 1 P 2,
P 3 P 4( ,
nil). (
)
.
.
Dynamic22. N (> 0) ;
P 1 P 2, P 3 P 4. N -
.
N ,
. ,
( nil).
.
Dynamic23. ; -
P 1 P 2, P 3 P 4.
, -
( ,
). -
, (
nil). -
.
Dynamic24. ; -
P 1 P 2, P 3 P 4.
. , -
( ).
.
.
Dynamic25◦. ; -
P 1 P 2, P 3 P 4.
( ).
. -
.
, Data .
Dynamic26. P 1 P 2 (
, P 1 = P 2 = nil). N (> 0)
N . TQueue Head Tail
PNode ( )
Enqueue(Q, D), Q
122
. . . Programming Taskbook 4.6
D (Q TQueue, D -
). Enqueue
.
Dynamic27. P 1 P 2 ,
. TQueue (. Dynamic26),
Dequeue(Q) ,
() , -
, (Q -
TQueue). Dequeue
.
(
|
|
|
, nil).
Dynamic28. P 1 P 2 .
TQueue (. Dynamic26), QueueIsEmpty(Q)
, TRUE, Q , FALSE
(Q TQueue).
, Dequeue
Dynamic27, -
( , )
. QueueIsEmpty
.
Dynamic29. P 2 TNode, Data (
) Prev Next ( PNode TNode).
Prev Next -
. Data
, P 1 P 3
.
Dynamic30◦. P 1 -
TNode, Next. -
Prev TNode, ()
,
( Next), (
Prev). Prev nil. -
.
Dynamic31Dynamic69 (doubly
linked list) - TNode,
, (. Dynamic30).
Next Prev
nil.
,
: (first),
(last) (current).
nil. ,
Data.
Dynamic31. P 0
. N , -
P 1 P 2 .
Dynamic32. D 1 D 2 P 0 -
.
D 1, D 2.
.
Dynamic33. D P 0 -
.
D .
Dynamic34. D P 0 -
.
D .
Dynamic35. P 1 P 2 -
, .
(
) -
.
Dynamic36. P 1 P 2 -
, .
(
)
.
124
. . . Programming Taskbook 4.6
Dynamic37. P 1 -
. (-
)
.
Dynamic38. P 1 -
. (
-
)
|
|
|
.
Dynamic39. P 1 -
. (-
)
.
Dynamic40. P 1 -
. (-
) -
.
Dynamic41. P 0 -
. :
, , ,
( ; -
nil).
, .
Dynamic42. P 1 , -
. -
. , -
.
Dynamic43. P 1 -
.
(
, nil). -
, .
Dynamic44. P 0
. -
.
, Data -
.
Dynamic45. P 0
. -
.
, Data -
.
Dynamic46. K (> 0) P 0
. K
( K , -
).
.
, Data .
Dynamic47. K (> 0) P 0
. K
( K , -
).
.
, Data .
Dynamic48. P X P Y -
( P X
P Y, ).
-
. ,
Data .
Dynamic49◦. P 1 -
. , -
( )
. -
, Data .
Dynamic50. P 1 -
. , -
( )
126
. . . Programming Taskbook 4.6
. -
, Data .
Dynamic51. -
: P 1 P 2
, P 0 . ,
( )
,
.
.
Dynamic52. -
: P 1 P 2
, P 0 . ,
( )
,
.
.
Dynamic53. P X P Y -
; P X
P Y, . , -
( ),
( ). -
.
, nil.
.
Dynamic54. P X P Y -
; P X
P Y, . , -
( ),
( ). -
.
, nil.
.
Dynamic55◦. P 1 -
. , Next
, Prev -
. ,
.
Dynamic56. P 1 P 2 -
, . -
(. Dynamic55), -
,
. P 3 P 4
( P 3 -
, P 4 ).
.
Dynamic57. K (> 0) P 1 P 2
.
K (
)
.
(. Dynamic55),
, K. -
.
Dynamic58. K (> 0) P 1 P 2
.
K (
) -
. -
(. Dynamic55),
, K.
.
Dynamic59◦. P 1, P 2 P 3 , -
( ,
P 1= P 2= P 3= nil). N (> 0) N .
TList First, Last Current PNode ( -
, )
InsertLast(L, D), -
D L (L TList,
D ).
. -
( )
, .
128
. . . Programming Taskbook 4.6
Dynamic60. P 1, P 2 P 3 , -
( ,
P 1= P 2= P 3= nil). N (> 0) N . -
TList (. Dynamic59), InsertFirst(L, D),
D L (L
TList, D -
). .
(-
)
, .
Dynamic61. , , -
P 1, P 2 P 3.
. TList (. Dynamic59), -
InsertBefore(L, D), D
L (L
TList, D ).
.
,
.
Dynamic62. , , -
P 1, P 2 P 3. -
. TList (. Dynamic59),
InsertAfter(L, D), D -
L (L
TList, D ). -
.
,
.
Dynamic63◦. , ,
P 1, P 2 P 3. TList (. -
Dynamic59), ToFirst(L) (
L), ToNext(L) ( L -
, ), SetData(L, D) (
L D ) IsLast(L)
( TRUE, L -
, FALSE ). L TList;
ToFirst ToNext . -
-
, ,
.
Dynamic64. , , -
P 1, P 2 P 3. TList
(. Dynamic59), ToLast(L) (
L), ToPrev(L) ( L -
, ) GetData(L)
( L), IsFirst(L) -
( TRUE, L
, FALSE ). L
TList; ToLast ToPrev .
-
, .
.
Dynamic65. P 1, P 2 P 3 , -
, -
. TList (. Dynamic59),
DeleteCurrent(L) , L
(L
TList).
, , .
, .
. ,
( -
nil).
Dynamic66. P 1, P 2 P 3 ,
. TList (. -
Dynamic59), SplitList(L 1, L 2),
L 1 L 2 (
, L 1 , -
). TList;
, . -
130
. . . Programming Taskbook 4.6
.
-
.
,
.
Dynamic67. ,
. TList (.
Dynamic59), AddList(L 1, L 2),
L 1 ( ) L 2;
L 1 . L 2
.
TList . -
.
, .
Dynamic68. ,
. TList (.
Dynamic59), InsertList(L 1, L 2),
L 1( ) L 2
; L 1 . -
L 2 . -
TList .
-
.
, -
.
Dynamic69. ,
( ).
TList (. Dynamic59), MoveCurrent(L 1, L 2),
L 1 L 2(
L 2 -
; L 1 ,
, ).
TList . -
.
,
.
