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

  • Published on
    16-Nov-2014

  • View
    5.920

  • Download
    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.

  • ( add )
  • ( find )
  • ( remove )

10. 11.

  • procedure add(x : longint);
  • 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.

  • add O(1)
  • find O(n)
  • remove O(n)

18.

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

19.

  • ( add )
  • ( find )
  • ( remove )

20.

  • procedure add(x : longint);
  • 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.

  • procedure add(x : longint);
  • 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.

  • add O(1)
  • 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.

  • add
  • remove
  • isEmpty

42.

  • queue,
  • head ,
  • tail ,
  • ,

43.

  • procedure add(x : integer);
  • 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;
  • result := queue[head];
  • inc(head);
  • end;

45.

  • Dequeue = double-ended queue

46.

  • addLeft
  • removeLeft
  • addRight
  • removeRight
  • isEmpty

47.

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

48.

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

49.

  • procedure addLeft(x : integer);
  • 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.

  • procedure add(x : longint);
  • 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 ),
  • ,
  • ,

62. ! ? ? [email_address]

Recommended

View more >