Лабораторная работа 14. Динамические структуры данных: стек, очередь и дерево

2011-2012 учебный год

Краткая теория

К сегодняшнему занятию Вами изучены следующие элементы управления

1. Edit
2. Label
3. Button
4. RadioButton
5. CheckBox
6. SpinEdit (на вкладке Misc)
7. FloatSpinEdit (на вкладке Misc)
8. ListBox (на вкладке Standard)
9. Memo (на вкладке Standard)
10. GroupRadioButton (на вкладке Standard)
11. ShowMessage, MessageBox
12. StringGrid (на вкладке Additional)
13. Image (на вкладке Additional)
14. Shape (на вкладке Additional)
15. TTabControl (на вкладке Common Controls)

Об отметках

Основные упражнения не отмечены никакими специальными знаками, их выполнения достаточно для удовлетворительной оценки. Дополнительные упражнения отмечены "звездочками", их выполнение необходимо для получения повышенной оценки.

- "5" - в отчете выполнены все основные упражнения, дополнительно выполнены упражнения с одной и двумя "звездочками".
- "4" - в отчете выполнены все основные упражнения, дополнительно выполнены упражнения с одной "звездочкой".
- "3" - в отчете выполнены все основные упражнения.

Упражнения

1. Стек. В программе по нажатию кнопки должен добавляться элемент в стек, а по нажатию другой кнопки - извлекаться из стека.
2. Требования к выполнению. Для визуализации процессов извлечения и добавления использовать компоненты TShape.
3. Пример интерфейса

1. Пример программы
  1. // Глобальные константы.
  2. const
  3. NO_EXIST = 'Элемент не существует!';
  4. DEEP_STACK = 'Глубина стека ограничена: ';
  5. N_MAX = 7;
  6. RANGE : array [1..N_MAX] of string = ('Каждый',
  7. 'Охотник',
  8. 'Желает',
  9. 'Знать',
  10. 'Где',
  11. 'Сидит',
  12. 'Фазан');
  13. // Глобальные типы.
  14. type
  15. p_my_stack = ^t_my_stack;
  16. t_my_stack = record
  17. next : p_my_stack;
  18. s : string;
  19. end;
  20. // Глобальные переменные.
  21. var
  22. p_head : p_my_stack;
  23. p : p_my_stack;
  24. n : 1..N_MAX;
  25. procedure TForm1.FormCreate(Sender: TObject);
  26. begin
  27. n := 0;
  28. p_head := nil;
  29. Shape1.Visible := False;
  30. Shape2.Visible := False;
  31. Shape3.Visible := False;
  32. Shape4.Visible := False;
  33. Shape5.Visible := False;
  34. Shape6.Visible := False;
  35. Shape7.Visible := False;
  36. end;
  37. procedure TForm1.FormDestroy(Sender: TObject);
  38. var
  39. p : p_my_stack;
  40. begin
  41. if p_head <> nil then
  42. p := p_head;
  43. end;
  44. procedure TForm1.Button1Click(Sender: TObject);
  45. begin
  46. if n < N_MAX then begin
  47. Inc(n);
  48. Label3.Caption := IntToStr(n);
  49. New(p);
  50. p^.next := p_head; // новый указывает на "бывшую" верхушку стека
  51. p^.s := RANGE[n];
  52. p_head := p; // вершиной стека становится новый элемент
  53. ListBox1.Items.Add(IntTOStr(n) + '. ' + p^.s);
  54. case n of
  55. 1 : begin
  56. Shape1.Visible := True;
  57. end;
  58. 2 : begin
  59. Shape2.Visible := True;
  60. end;
  61. 3 : begin
  62. Shape3.Visible := True;
  63. end;
  64. 4 : begin
  65. Shape4.Visible := True;
  66. end;
  67. 5 : begin
  68. Shape5.Visible := True;
  69. end;
  70. 6 : begin
  71. Shape6.Visible := True;
  72. end;
  73. 7 : begin
  74. Shape7.Visible := True;
  75. end;
  76. end;
  77. end
  78. else ShowMessage(DEEP_STACK + IntToStr(N_MAX));
  79. end;
  80. procedure TForm1.Button2Click(Sender: TObject);
  81. begin
  82. case n of
  83. 1 : begin
  84. Shape1.Visible := False;
  85. end;
  86. 2 : begin
  87. Shape2.Visible := False;
  88. end;
  89. 3 : begin
  90. Shape3.Visible := False;
  91. end;
  92. 4 : begin
  93. Shape4.Visible := False;
  94. end;
  95. 5 : begin
  96. Shape5.Visible := False;
  97. end;
  98. 6 : begin
  99. Shape6.Visible := False;
  100. end;
  101. 7 : begin
  102. Shape7.Visible := False;
  103. end;
  104. end;
  105. if p_head <> nil then begin
  106. Dec(n);
  107. p := p_head;
  108. p_head := p_head^.next;
  109. end
  110. else ShowMessage(NO_EXIST);
  111. Label3.Caption := IntToStr(n);
  112. end;
2. Очередь. В программе по нажатию кнопки должен добавляться элемент в очередь, а по нажатию другой кнопки - извлекаться из очереди.
3. Требования к выполнению. Для визуализации процессов извлечения и добавления использовать компоненты TShape.
4. Пример интерфейса

1. Пример программы
  1. // Глобальные константы.
  2. const
  3. NO_EXIST = 'Элемент не существует!';
  4. LEN_CHAIN = 'Длина очереди ограничена: ';
  5. N_MAX = 7;
  6. RANGE : array [1..N_MAX] of string = ('Как',
  7. 'Однажды',
  8. 'Жак',
  9. 'Звонарь',
  10. 'Городской',
  11. 'Сломал',
  12. 'Фонарь');
  13. // Глобальные типы.
  14. type
  15. p_my_chain = ^t_my_chain;
  16. t_my_chain = record
  17. next : p_my_chain;
  18. s : string;
  19. end;
  20. // Глобальные переменные.
  21. var
  22. p_head : p_my_chain;
  23. p : p_my_chain;
  24. p_last : p_my_chain;
  25. n : 0..N_MAX;
  26. procedure TForm1.FormCreate(Sender: TObject);
  27. begin
  28. n := 0;
  29. p_head := nil;
  30. p := nil;
  31. p_last := nil;
  32. Shape1.Visible := False;
  33. Shape2.Visible := False;
  34. Shape3.Visible := False;
  35. Shape4.Visible := False;
  36. Shape5.Visible := False;
  37. Shape6.Visible := False;
  38. Shape7.Visible := False;
  39. end;
  40. procedure TForm1.FormDestroy(Sender: TObject);
  41. var
  42. p : p_my_chain;
  43. prev : p_my_chain;
  44. begin
  45. if p_head <> nil then
  46. p := p_head;
  47. end;
  48. procedure TForm1.Button1Click(Sender: TObject);
  49. begin
  50. if n < N_MAX then begin
  51. Inc(n);
  52. Label3.Caption := IntToStr(n);
  53. if p_last = nil then begin // если очередь пуста
  54. New(p);
  55. p_last := p;
  56. p_head := p_last;
  57. p^.next := nil; // за новым очередником никто не стоит
  58. // - Кто крайний? - P - крайний!
  59. end
  60. else begin
  61. New(p);
  62. p^.next := nil; // за новым крайним никого нет
  63. p_last^.next := p; // "бывший" крайний указывает на нового крайнего
  64. p_last := p; // указатель на крайнего смещается к новому
  65. end;
  66. p^.s := RANGE[n];
  67. ListBox1.Items.Add(IntTOStr(n) + '. ' + p^.s);
  68. case n of
  69. 1 : begin
  70. Shape1.Visible := True;
  71. end;
  72. 2 : begin
  73. Shape2.Visible := True;
  74. end;
  75. 3 : begin
  76. Shape3.Visible := True;
  77. end;
  78. 4 : begin
  79. Shape4.Visible := True;
  80. end;
  81. 5 : begin
  82. Shape5.Visible := True;
  83. end;
  84. 6 : begin
  85. Shape6.Visible := True;
  86. end;
  87. 7 : begin
  88. Shape7.Visible := True;
  89. end;
  90. end;
  91. end
  92. else ShowMessage(LEN_CHAIN + IntToStr(N_MAX));
  93. end;
  94. procedure TForm1.Button2Click(Sender: TObject);
  95. begin
  96. if n > 0 then Dec(n);
  97. case (N_MAX - n) of
  98. 1 : begin
  99. Shape1.Visible := False;
  100. end;
  101. 2 : begin
  102. Shape2.Visible := False;
  103. end;
  104. 3 : begin
  105. Shape3.Visible := False;
  106. end;
  107. 4 : begin
  108. Shape4.Visible := False;
  109. end;
  110. 5 : begin
  111. Shape5.Visible := False;
  112. end;
  113. 6 : begin
  114. Shape6.Visible := False;
  115. end;
  116. 7 : begin
  117. Shape7.Visible := False;
  118. end;
  119. end;
  120. if p_head <> nil then begin
  121. // Dec(n);
  122. p := p_head;
  123. p_head := p_head^.next;
  124. Dispose(p);
  125. end
  126. else ShowMessage(NO_EXIST);
  127. Label3.Caption := IntToStr(n);
  128. end;
2. Дерево. Создать программу визуализирующую добавление элементов в динамическую структуру данных - дерево - с помощью компонента TShape. Доработать пример программы до второго уровня дерева с учетом того, что корень, root - нулевой уровень.
3. Требования к выполнению. Для визуализации построения дерева использовать компоненты TShape.
4. Пример интерфейса

1. Пример программы
  1. // Глобальные типы.
  2. type
  3. p_my_tree = ^t_my_tree;
  4. t_my_tree = record
  5. left : p_my_tree;
  6. right : p_my_tree;
  7. s : string;
  8. end;
  9. // Глобальные константы.
  10. const
  11. NO_EXIST = 'Элемент не существует!';
  12. NUM_NODES = 'Узлы дерева ограничены: ';
  13. N_MAX = 7;
  14. RANGE : array [1..N_MAX] of string = ('Как',
  15. 'Однажды',
  16. 'Жак',
  17. 'Звонарь',
  18. 'Городской',
  19. 'Сломал',
  20. 'Фонарь');
  21. // Глобальные переменные.
  22. var
  23. p_left : p_my_tree;
  24. p_root : p_my_tree;
  25. p_right : p_my_tree;
  26. p : p_my_tree;
  27. n : 0..N_MAX;
  28. implementation
  29. { TForm1 }
  30. procedure TForm1.FormCreate(Sender: TObject);
  31. begin
  32. n := 0;
  33. p_left := nil;
  34. p_root := nil;
  35. p_right := nil;
  36. Shape1.Visible := False;
  37. Shape2.Visible := False;
  38. Shape3.Visible := False;
  39. Shape4.Visible := False;
  40. Shape5.Visible := False;
  41. Shape6.Visible := False;
  42. Shape7.Visible := False;
  43. end;
  44. procedure TForm1.FormDestroy(Sender: TObject);
  45. var
  46. p : p_my_tree;
  47. begin
  48. if p_root <> nil then
  49. p := p_root;
  50. end;
  51. // Добавить слева.
  52. procedure TForm1.Button1Click(Sender: TObject);
  53. begin
  54. if n < N_MAX then begin
  55. Inc(n, 2);
  56. if p_root = nil then begin
  57. New(p);
  58. p_root := p;
  59. p^.left := nil;
  60. p^.right := nil;
  61. n := 1;
  62. p^.s := RANGE[n];
  63. Shape1.Visible := True;
  64. end
  65. else begin
  66. New(p);
  67. if p_root^.left = nil then n := 2;
  68. p_root^.left := p;
  69. p^.left := nil;
  70. p^.right := nil;
  71. p^.s := RANGE[n];
  72. end;
  73. case n of
  74. 1 : begin
  75. Shape1.Visible := True;
  76. end;
  77. 2 : begin
  78. Shape2.Visible := True;
  79. end;
  80. 4 : begin
  81. Shape4.Visible := True;
  82. end;
  83. 6 : begin
  84. Shape6.Visible := True;
  85. end;
  86. end;
  87. ListBox1.Items.Add(IntTOStr(n) + '. ' + p^.s);
  88. end
  89. else ShowMessage(NUM_NODES + IntToStr(N_MAX));
  90. end;
  91. // Добавить справа.
  92. procedure TForm1.Button2Click(Sender: TObject);
  93. begin
  94. if n < N_MAX then begin
  95. Inc(n, 2);
  96. if p_root = nil then begin
  97. New(p);
  98. p_root := p;
  99. p^.left := nil;
  100. p^.right := nil;
  101. n := 1;
  102. p^.s := RANGE[n];
  103. Shape1.Visible := True;
  104. end
  105. else begin
  106. New(p);
  107. if p_root^.right = nil then n := 3;
  108. p_root^.right := p;
  109. p^.left := nil;
  110. p^.right := nil;
  111. p^.s := RANGE[n];
  112. p^.s := RANGE[n];
  113. end;
  114. case n of
  115. 1 : begin
  116. Shape1.Visible := True;
  117. end;
  118. 3 : begin
  119. Shape3.Visible := True;
  120. end;
  121. 5 : begin
  122. Shape5.Visible := True;
  123. end;
  124. 7 : begin
  125. Shape7.Visible := True;
  126. end;
  127. end;
  128. ListBox1.Items.Add(IntTOStr(n) + '. ' + p^.s);
  129. end
  130. else ShowMessage(NUM_NODES + IntToStr(N_MAX));
  131. end;

Домашнее задание

1. Домашний стек. В задаче "Стек" выводить адреса элементов в компонент TMemo.
2. Требования к выполнению. Для визуализации процессов извлечения и добавления использовать компоненты TShape.
3. Домашнее дерево. В задаче "Дерево" выводить адреса элементов в компонент TMemo.
4. Требования к выполнению. Для визуализации построения дерева использовать компоненты TDrawGrid.

Page updated

Google Sites

Report abuse