# 01 линейные структуры данных

• Published on
16-Nov-2014

• View
5.920

1

Embed Size (px)

DESCRIPTION

" "

Transcript

• 1. 1 01.12.2008, 08.12.2008 -, 261

2.

• Pascal (Delphi)

3.

• + = ( )

4.

• , , , ,

5.

• ,
• type student = record
• name : string;
• class : integer;
• marks : array[1..10] of integer;
• end;

6.

• var
• s : student;
• s.name := Vasya;
• writeln(s.name);

7. Pascal

• =
• ( new ) ( delete )
• pstudent = ^student

8.

• ()
• type
• pnode = ^node;
• node = record
• data : integer;
• next : pnode;
• end;
• first

9.

• ( find )
• ( remove )

10. 11.

• var
• p : pnode;
• begin
• new(p);
• p^.data := x;
• p^.next := first;
• first := p;
• end;

12.

• function find(x : integer) : boolean;
• var
• wp : pnode;
• begin
• wp := first;
• while (wp nil) do begin
• if (wp^.data = x) then begin
• result := true;
• exit;
• end;
• wp := wp^.next;
• end;
• result := false;
• end;

13.

14.

• ,

15. ()

• procedure remove(x : integer);
• var
• cur, prev, tmp : pnode;
• begin
• if (first = nil) then begin
• exit;
• end;
• if (first^.data = x) then begin
• tmp := first;
• first := first^.next;
• delete(tmp);
• exit;
• end;

16. ()

• prev := first;
• cur := first^.next;
• while (cur nil) do begin
• if (cur^.data = x) then begin
• prev^.next := cur^.next;
• delete(cur);
• exit;
• end;
• cur := cur^.next;
• prev := prev^.next;
• end;
• end;

17.

• find O(n)
• remove O(n)

18.

• ,
• type
• pnode = ^node;
• node = record
• data : integer;
• next,prev: pnode;
• end;

19.

• ( find )
• ( remove )

20.

• var
• p : pnode;
• begin
• new(p);
• p^.data := x;
• p^.next := first;
• if (first nil) then begin
• first^.prev := p;
• end;
• first := p;
• end;

21.

• ,
• function find(x : integer) : boolean;
• var
• wp : pnode;
• begin
• wp := first;
• while (wp nil) do begin
• if (wp^.data = x) then begin
• result := true;
• exit;
• end;
• wp := wp^.next;
• end;
• end;

22. 23.

• ,
• ,

24. ()

• procedure remove(x : integer);
• var
• cur, prev, next : pnode;
• begin
• if (first = nil) then begin
• exit;
• end;
• end;

25. ()

• cur := first;
• while (cur nil) do begin
• if (cur^.data = x) then begin
• prev := cur^.prev;
• next := cur^.next;
• // 4 :
• //
• exit;
• end;
• cur := cur^.next;
• end;

26. (1, 2)

• if (prev=nil) and (next=nil) then begin
• //
• first := nil;
• delete(cur);
• end;
• if (prev nil) and (next = nil) then
• begin
• //
• prev^.next := nil;
• delete(cur);
• end;

27. (3, 4)

• if (prev = nil) and (nextnil) then
• begin
• //
• first := next;
• delete(cur);
• end;
• if (prevnil) and (nextnil) then begin
• //
• prev^.next := next;
• next^.prev := prev;
• delete(cur);
• end;

28. ?

• ( sentinel elements ) , ,

29.

• type
• pnode = ^node;
• node = record
• data : integer;
• next, prev : pnode;
• isSentinel : boolean;
• end;

30. 31.

• var
• p : pnode;
• begin
• new(p);
• p^.data := x;
• p^.next := first;
• first^.prev := p;
• first := p;
• end;

32.

• function find(x : integer) : boolean;
• var
• wp : pnode;
• begin
• wp := first;
• while (wp nil) do begin
• if ( ( not( wp^.isSentinel ) ) and
• (wp^.data = x) ) then begin
• result := true;
• exit;
• end;
• wp := wp^.next;
• end;
• result := false;
• end;

33.

• procedure remove(x : integer);
• var
• cur, prev, next : pnode;
• begin
• cur := first;
• while (cur nil) do begin
• if ( ( not( cur^.isSentinel ) ) and
• (cur^.data = x) ) then begin
• cur^.prev^.next := cur^.next;
• cur^.next^.prev := cur^.prev;
• delete(cur);
• exit;
• end;
• cur := cur^.next;
• end;
• end;

! 34.

• find O(n)
• remove O(n)

35.

• Stack
• LIFO (Last In First Out)

36.

• push(x)
• pop()
• isEmpty()

37.

• stack,
• top,

38.

• procedure push(x : integer);
• begin
• inc(top);
• stack[top] := x;
• end;
• function isEmpty() : boolean;
• begin
• result :=( top = 0 ) ;
• end;

39.

• function pop() : integer;
• begin
• if (isEmpty()) then begin
• //
• //
• exit;
• end;
• result := stack[top];
• dec(top);
• end;

40.

• Queue
• FIFO (First In First Out)

41.

• remove
• isEmpty

42.

• queue,
• tail ,
• ,

43.

• begin
• queue[tail] := x;
• inc(tail);
• end;
• function isEmpty() : boolean;
• begin
• result :=( head = tail ) ;
• end;

44.

• function remove() : boolean;
• begin
• if (isEmpty()) then begin
• //
• //
• exit;
• end;
• end;

45.

• Dequeue = double-ended queue

46.

• removeLeft
• removeRight
• isEmpty

47.

• ,
• left
• right
• ,
• dequeue: array[-10..10] of longint;

48.

• function isEmpty() : boolean;
• begin
• result := left > right;
• end;
• begin
• inc(right);
• dequeue[right] := x;
• end;

49.

• begin
• dec(left);
• dequeue[left] := x;
• end;

50.

• function removeLeft() : boolean;
• begin
• if (isEmpty()) then begin
• //
• //
• exit;
• end;
• result := dequeue[left];
• inc(left);
• end;

51.

• function removeRight() : boolean;
• begin
• if (isEmpty()) then begin
• //
• //
• exit;
• end;
• result := dequeue[right];
• dec(right);
• end;

52.

• , ,

53.

• ( 100 , 50 )
• !

54.

• memory : array[1..MAXMEM] of node;
• MAXMEM
• free
• memory
• -1 nil

55. 56.

• var
• p : integer;
• begin
• p := free;
• inc(free);
• memory[p].data := x;
• memory[p].next := first;
• first := p;
• end;

57.

• function find(x : integer) : boolean;
• var
• wp : integer ;
• begin
• wp := first;
• while ( wp -1 ) do begin
• if (memory[wp].data = x) then begin
• result := true;
• exit;
• end;
• wp := memory[wp].next;
• end;
• result := false;
• end;

58. ()

• procedure remove(x : integer);
• var
• cur, prev, tmp : integer;
• begin
• if ( first = -1 ) then begin
• exit;
• end;
• if (memory[first].data = x) then begin
• tmp := first;
• first := memory[first].next;
• exit;
• end;

59. ()

• prev := first;
• cur := memory[first].next;
• while (cur -1) do begin
• if (memory[cur].data = x) then begin
• memory[prev].next := memory[cur].next;
• exit;
• end;
• cur := memory[cur].next;
• prev := memory[prev].next;
• end;
• end;

60.

61.

• ( new, delete ),
• ,
• ,