Занятие 9. Pascal abc.net: Контейнерные классы

Авторadmin / Опубликовано

Рассматривается работа с контейнерными классами в abc.net

Назад
К оглавлению
Далее

Стек / Stack

  • Push(x: T);
  • Pop: T;
  • Peek: T;
  • Clear;
  • property Count: integer;

Очередь / Queue

  • Enqueue(x: T);
  • Dequeue: T;
  • Peek: T;
  • Clear;
  • property Count: integer;

Список / List

  • Contains(x: T): boolean;
  • IndexOf(x: T): integer;
  • LastIndexOf(x: T): integer;
  • Find(pred: T -> boolean): T;
  • FindIndex(pred: T -> boolean): integer;
  • FindAll(pred: T -> boolean): List;
  • ForEach(act: T -> ());
  • TrueForAll(pred: T -> boolean): boolean;
  • Reverse;
  • Reverse(from,count: integer);
  • Sort;
  • Clear;
  • Add(x: T);
  • AddRange(seq: sequence of T);
  • Remove(x: T): boolean;
  • RemoveAll(pred: T -> boolean): integer;
  • RemoveAt(ind: integer);
  • RemoveRange(ind,count: integer);
  • Insert(ind: integer; x: T);
  • InsertRange(ind: integer; seq: sequence of T);
  • property Count: integer;
  • property Capacity: integer;

Словари / Dictionary

Dictionary, SortedDictionary, SortedList

  • Add(k: Key; v: Value);
  • Remove(k: Key): boolean;
  • ContainsKey(k: Key): boolean;
  • ContainsValue(v: Value): boolean;
  • TryGetValue(k: Key; var v: Value): boolean;
  • Clear;
  • property Count: integer;

Пример 1:

begin
  var graph := Dict(('Rostov',Dict(KV('Moscow',1000),KV('Bataisk',10))),
                ('Moscow',Dict(KV('Rostov',1000))),
                ('Bataisk',Dict(KV('Rostov',10))) 
               );
  graph.Println(NewLine);
  graph['Rostov']['Moscow'] := 1100;
  graph['Moscow']['Rostov'] := 1100;
  Println;
  graph.Println(NewLine);
end.

Пример 2:

begin
  var q := ReadLines('a1.pas').Select(s->s.Matches('\w+')).SelectMany(x->x)
           .Select(x->x.Value);
  var d := new Dictionary<string,integer>;
  foreach var x in q do
    if d.ContainsKey(x) then
      d[x] := d[x] + 1
    else d[x] := 1;  
  d.OrderByDescending(x->x.Value).Take(10).Print(NewLine);  
end.

Данный пример может быть решен более коротким способом, используя d.Get, которая возвращает либо значение, соответствующее ключу, либо 0 если ключа нет:

begin
  var q := ReadLines('FreqFile.pas').Select(s->s.Matches('\w+')).SelectMany(x->x)
             .Select(x->x.Value);
  var d := new Dictionary<string,integer>;
  foreach var x in q do
    d[x] := d.Get(x) + 1;
  d.OrderByDescending(x->x.Value).Take(10).Print(NewLine);  
end.

Результат:

(x,9)
(d,4)
(var,3)
(q,2)
(Select,2)
(s,2)
(Value,2)
(begin,1)
(ReadLines,1)
(FreqFile,1)

Источником строк может быть файл, находящийся в интернете:

begin
  var w := new System.Net.WebClient();
  var ss := w.DownloadString('http://vojnaimir.ru/files/book1.txt');
 
  var q := ss.MatchValues('\w+');
  var d := new Dictionary<string,integer>;
  foreach var x in q do
    d[x] := d.Get(x) + 1;
  d.OrderByDescending(x->x.Value).Take(20).Print(NewLine);  
end.

Результат:

(и,10137)
(в,4863)
(не,4221)
(что,3652)
(на,3200)
(с,3025)
(он,3017)
(как,1913)
(его,1876)
(к,1778)
(то,1606)
(я,1354)
(она,1195)
(сказал,1145)
(было,1137)
(это,1030)
(за,961)
(так,952)
(но,949)
(ее,897)

Если необходимо взять только собственные имена, то следует использовать фильтр: слово с большой буквы и длины не менее 4:

var q := ss.MatchValues('\w+').Where(s->s[1].IsUpper and (s.Length>3));

HashSet, SortedSet

  • Add(x: T): boolean;
  • Remove(x: T): boolean;
  • Contains(x: T): boolean;

LinkedListNode

  • property Next: LinkedListNode read;
  • property Prev: LinkedListNode read;
  • property Value: T read write;

LinkedList

  • Contains(x: T): boolean;
  • Find(x: T): LinkedListNode;
  • FindLast(x: T): LinkedListNode;
  • AddFirst(x: T);
  • AddLast(x: T);
  • AddAfter(n: LinkedListNode; x: T);
  • AddBefore(n: LinkedListNode; x: T);
  • Clear;
  • Remove(LinkedListNode);
  • RemoveFirst;
  • RemoveLast;
  • property Count: integer;
  • property First: LinkedListNode;
  • property Last: LinkedListNode;

Решение задач

Пример: Задана строка с арифметическим выражением. Определить правильность расстановки скобок ( может встречаться (), [], {}).

Решение:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

begin
  var ss: string;
 {ss := '{vbsdf[fsdfdff]aa';}
 ss := '{df{ff{df}aa';
  var st := new stack<char>;
  var res := true;
 
  for var i := 1 to ss.Length do
  begin
    case ss[i] of
      '(': st.Push(ss[i]);
      ')':
        if (st.Count = 0) or (st.Pop <> '(') then
        begin
          res := false;
          break;
        end;
 
      '[': st.Push(ss[i]);
      ']':
        if (st.Count = 0) or (st.Pop <> '[') then
        begin
          res := false;
          break;
        end;
      '{': st.Push(ss[i]);
      '}':
        if (st.Count = 0) or (st.Pop <> '{') then
        begin
          res := false;
          break;
        end;
     end;
  end;
  if st.Count <> 0 then res:=false;
  if res = true then println('ok') else println('NOT RIGHT');
end.
Пример: Дана корректная запись арифметического выражения в форме обратной польской записи. Вычислить выражение, используя стек. (ОПН — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций)
7 2 3 * - эквивалентно 7-2*3
1 2 + 4 × 3 + эквивалентно (1 + 2) х 4 + 3

Выполнение:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

begin
var st:=new stack <integer>;
var ss:='2 3 + 5 7 + /';
var s:=ss.ToWords;
foreach var x in s do
begin
case x[1] of
'0'..'9':st.push(x.ToInteger);
'+': st.push(st.pop+st.pop);
'*':st.push(st.pop*st.pop);
'-':st.push(st.pop-st.pop);
'/':st.push(st.pop div st.pop);
end;
 
end;
println(st.pop);
assert(st.count=0);
end.