Динамические структуры данных

1. Программирование на языке высокого уровня

Богатов Р.Н.
Программирование
на языке высокого уровня
Лекция 12.
Динамические структуры данных
Кафедра АСОИУ ОмГТУ, 2013

2. Списки

• Односвязный (однонаправленный) список
• Двусвязный (двунаправленный) список
• Кольцевой список

3. Стек. Очередь. Дек

• Стек (англ. stack — стопка) — структура данных с методом
доступа к элементам «последним пришёл — первым
вышел» (англ. LIFO, Last In — First Out).
• Очередь (англ. queue) — структура данных с методом
доступа к элементам «первым пришёл — первым вышел»
(англ. FIFO, First In — First Out).
• Дек (англ. deque = double ended queue — двусвязная очередь,
«очередь с двумя концами») — структура данных, в которой
элементы можно добавлять и удалять как в начало, так и в
конец.

4. List. Stack. Queue

// n – количество элементов массива а
// выбрать из a элементы, которые делятся на 11
List<int> b = new List<int>();
b.Add(x);
for (int i = 0; i < n; i++)
b.Insert(i, x);
if (a[i] % 11 == 0 && !b.Contains(a[i]))
b.Remove(x);
b.Add(a[i]);
b.RemoveAt(i);
using
for
(intSystem.Collections;
i = 0; i < b.Count; i++)
= b.Min();
textBox1.Text += b[i] + "\r\n";
= b.Max();
...
= b.Sum();
Stack s = new Stack();
= b.Average();
s.Push(x);
x = (int)s.Pop();
= b.IndexOf(x);
while (s.Count > 0) ...
= b.LastIndexOf(x);
if (s.Contains(x)) ...
= b.Contains(x);
...
b.Reverse();
Queue q = new Queue();
b.Sort();
q.Enque(x);
x = (int)q.Dequeue();
while (q.Count > 0) ...
if (q.Contains(x)) ...

5. Деревья

Дерево (в теории графов) — связный ациклический граф

6. Игра в животные

7. Дерево игры в животные

Хищное?
Хищное?
Лев
Живёт в
лесу?
Слон
Медведь
Умеет
летать?
Живёт в
воде?
Выбирается
на сушу?
Крокодил
Акула
Длинная
шея?
Голубь
Лев
Живёт в
воде?
Жираф
Кит
Слон

8. Код игры в животные

public partial class Form1 : Form
{
// кнопка "Да"
class
Vopros
//
кнопка
"Добавить"
private
void
Form1_Load(object sender, EventArgs e)
if (x.yes != null)
{
Vopros
yes = new Vopros();
{
{
public
text;
Vopros
no =string
new
Vopros();
Nachalo
= new
Vopros();
x = x.yes;
...
public
Vopros =yes,
no;
no.text
= x.text;
Nachalo.text
"хищное";
textBox1.Text = x.text + "?";
Nachalo = new Vopros {
}
yes.text
= textBox2.Text;
Vopros
z = new Vopros();
}
text = "хищное",
Vopros
Nachalo;
// первый вопрос
z.text
= "лев";
else
yes = new Vopros { text = "лев" },
Vopros
x;
//
текущий вопрос
x.text
= textBox3.Text;
Nachalo.yes
= z;
{
no = new Vopros { text = "слон" }
...
x.no z= =no;
new Vopros();
MessageBox.Show("Ура! Я угадал!");
};
x.yesz.text
= yes;= "слон";
button4_Click(sender, e); // ...
начать заново
Nachalo.no = z;
}
button4_Click(sender,
// начать заново
// кнопка e);
"Нет"
if (x.no != null)
x = Nachalo;
//
кнопка
{ "Начать заново"
}
x = Nachalo;x = x.no;
textBox1.Text
= x.text + "?";
textBox1.Text
= x.text + "?";
groupBox1.Hide();
}
else
{
label2.Text = "Чем оно отличается от '" + x.text + "'?";
groupBox1.Show();
}