Костюк лекция 8

1. ОСНОВЫ ПРОГРАММИРОВАНИЯ

Лекция 8
Символьные строки и таблицы
1

2. Символы и символьные строки

Символьная переменная - тип char.
Пример описания:
var c1, c2: char;
Действия:
- присваивание, например:
c1:=’a’; c2:=’+’;
- сравнение операциями: >, <, =, <>, <=, >=,
сравниваются их коды, как целые числа.
Функция ord(c1) вычисляет код c1.
Коды задаются таблицей кодирования
(например, ASCII, символ – 1 байт, код – от 0 до 255).
2

3. Таблица ASCII (CP866)

00 10 20 30 40 50 60 70 80 90 A0 B0 C0 D0 E0 F0
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
!
"
#
$
%
&
’
(
)
*
+
,
.
/
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
‘
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Щ
Ъ
Ы
Ь
Э
Ю
Я
а
б
в
г
д
е
ж
з
и
й
к
л
м
н
о
п
░
▒
▓
│
┤
╡
╢
╖
╕
╣
║
╗
╝
╜
╛
┐
└
┴
┬
├
─
┼
╞
╟
╚
╔
╩
╦
╠
═
╬
╧
╨
╤
╥
╙
╘
╒
╓
╫
╪
┘
┌
█
▄
▌
▐
▀
р
с
т
у
ф
х
ц
ч
ш
щ
ъ
ы
ь
э
ю
я
Ё
ё
Є
є
Ї
ї
Ў
ў
º
∙
√
№
¤
■
3

4. Символьные строки – особые массивы

Описание (пример):
var s1, s2: string[20];
здесь 20 – максимальная длина, фактическая – от 0 до
20.
Действия:
- присваивание, например:
s1:=’abcd’; s2:=s1;
- сложение (конкатенация, склеивание), например:
s2:=s1+’efg’;
- доступ к символу внутри строки, как к элементу
массива, например:
с1:=s1[1];
- функция length вычисляет фактическую длину
строки
- сравнение операциями: >, <, =, <>, <=, >=
4

5.

Сравнение двух строк символов производится в
лексикографическом порядке:
1) вначале сравниваются между собой первые
символы обеих строк, затем вторые и т.д.;
2) сравнение продолжается до первого
несовпадения двух сравниваемых символов,
большей считается та строка, код очередного
символа у которой больше;
3) если первая строка полностью совпадает с
началом более длинной второй строки, то первая
строка считается меньшей.
5

6. Примеры сравнения двух строк

’ABC’ < ’BBC’,
’ABC’ < ’ABCD’,
’ABC’ < ’abc’
’ABC’ < ’ABD’
’ДОМ’ < ’ДЫМ’
’ДОМ’ < ’Дом’
’ДОМ’ < ’ДОМИК’
’Abc’ < ’abc’
6

7. Множество из K объектов – символьных строк

Описание (пример):
var D: array[1..1000]of string[20];
Универсум – множество всех возможных строк
длиной до 20 символов, их количество:
1 + 256 + 2562 + 2563 + . . . + 25620 =
= (25621 – 1)/(256 – 1) ≈ 1,467 ∙ 1048.
Алгоритмы для множеств из символьных строк
тождественны соответствующим алгоритмам
для множеств из чисел, так как строки можно
упорядочивать и сравнивать, как целые числа.
7

8. Множество из K объектов – символьных строк

var
z: string[20]; {макс. длина такая же, }
{как для элементов массива D}
Алгоритм сортировки вставками для строк:
for i:=1 to K-1 do begin
j:=i; z:=D[j+1];
while(j>0)and(D[j]>z) do begin
D[j+1]:=D[j]; j:=j-1
end;
D[j+1]:=z;
end;
8

9. Сравнение двух строк с перекодировкой

Таблица перекодировки для отождествления заглавных
и строчных букв:
const T:array[0..255]of byte=
( 0, 1, 2, . . . ,
65,66,67, ... ,90, ...,95,96,65,66,67, ...);
{’A’ ’B’ ’C’
’Z’
’_’ ’’’ ’a’ ’b’ ’c’
}
код буквы ’A’ должен совпадать с кодом буквы ’a’ и т.д.
Сравнение двух символьных переменных c1 и c2:
сравниваются их преобразованные коды:
T[ord(c1)] и T[ord(c2)].
Подобным способом можно перейти от одной
таблицы кодирования к другой таблице.
9

10.

const T:array[0..255]of byte = ( 0,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,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
80,81,82,83,84,85,86,87, 88,89,90,91,92,93,94,95,
96,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90,123,124,125,126,127,
128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
133,133,242,243,244,245,246,247,248,249,250,251,252,253,254,255);
10

11. Сравнение двух строк с перекодировкой

function scomp(var s1,s2:string):integer;
var i,r,n1,n2:integer;
begin n1:=length(s1); n2:=length(s2);
r:=0; i:=1;
while (i<=n1)and(i<=n2)and
(T[ord(s1[i])]=T[ord(s2[i])]) do i:=i+1;
if (i<=n1)and(i<=n2) then begin
if T[ord(s1[i])]<T[ord(s2[i])] then r:=-1
else r:=1
end
else if (i<=n1) then r:=1
{s1>s2}
else if (i<=n2) then r:=-1; {s1<s2}
scomp:=r
end;
Трудоемкость: O(min(n1,n2))
11

12. Массив строк: упорядочение с учетом перекодировки

Описание:
var D: array[1..1000]of string[20];
z: string[20];
Алгоритм сортировки вставками с перекодировкой:
for i:=1 to n-1 do begin
j:=i; z:=D[j+1];
while (j>0)and(scomp(D[j],z)=1) do begin
D[j+1]:=D[j]; j:=j-1;
end;
D[j+1]:=z;
end;
12

13. Контекстный поиск в символьном массиве S длиной n по образцу-строке d длиной m

Результат: i – начало образца d в
S (первое совпадение).
m:=length(d); p:=0; i:=1;
while (p=0)and(i<=n-m+1) do
if (d[1]<>S[i]) then i:=i+1
else begin
j:=1;
while(j<m)and(d[j+1]=S[i+j])do j:=j+1;
if j=m then p:=1 else i:=i+1
end;
if p=0 then i:=0;
Трудоемкость: O(m·n)
13

14. Контекстный поиск в символьном массиве S длиной n по образцу-строке d длиной m с перекодировкой. Поиск всех совпадений

m:=length(d); p:=0; i:=1;
while i<=n-m+1 do begin
if T[ord(d[1])]=T[ord(S[i])] then begin
j:=1;
while (j<m)and
(T[ord(d[j+1])]=T[ord(S[i+j])]do j:=j+1;
if j=m then writeln(i);
end;
i:=i+1
end;
Трудоемкость: O(m·n)
14

15. Поиск слов в символьном массиве.

Признак распознавания слова:
p=0, если слово еще не началось (или были
только разделители)
p=1, если слово началось
p=2, если слово закончилось и распознано
Таблица для проверки разделителей:
Y[ord(c)]=1, если символ c - буква
Y[ord(c)]=0, если символ c - не буква
(разделитель)
15

16. Таблица для проверки букв и разделителей

const Y:array[0..255]of byte =
(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,
0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,
0,0,0);
16

17. Поиск слова d в символьном массиве S длиной n.

m:=length(d); p:=0; j:=1;
while (p<2)and(j<=n) do begin
c:=S[j];
if p=0 then begin
if Y[ord(c)]=1 then {начало слова}
begin d1:=c; p:=1; i:=j end
end
else begin
if Y[ord(c)]=1 then d1:=d1+c {слово продолжается}
else if scomp(d,d1)=0 then p:=2
{слово закончилось и совпало с образцом}
else p:=0 {слово закончилось но не совпало с образцом}
end;
j:=j+1
end;
if p=0 then i:=0
else if (p=1)and(scomp(d,d1)<>0) then i:=0;
17
Трудоемкость: O(n))

18. Распознавание группы слов в символьном массиве S длиной n

p:=0; j:=0;
while j<=n do begin
j:=j+1;
if j<=n then c:=S[j] else c:=' ';
if p=0 then begin
if Y[ord(c)]=1 then begin d1:=c; p:=1; i:=j end
end
else begin
if Y[ord(c)]=1 then d1:=d1+c
else begin
{слово выделено, поиск совпадения}
q:=1; p:=0;
while q<=k do {D - массив слов длиной k}
if scomp(d1,D[q])=0 then begin
writeln(D[q],’ ’,i); q:=k+1
end
else q:=q+1
end
end
end;
Трудоемкость: O(n·k))
18

19. Распознавание упорядоченной группы слов в символьном массиве S длиной n

p:=0; j:=0;
while j<=n do begin
j:=j+1;
if j<=n then c:=S[j] else c:=’ ’;
if p=0 then begin
if Y[ord(c)]=1 then begin d1:=c; p:=1; i:=j end
end
else begin
if Y[ord(c)]=1 then d1:=d1+c
else begin p:=0; {слово выделено, поиск совпадения}
b:=1; e:=k;
while b<=e do begin {D – упорядоченный массив слов длиной k}
q:=(b+e)div 2; r:=scomp(d1,D[q]);
if r<0 then b:=q+1
else if r>0 then e:=q-1
else begin writeln(D[q],’ ’,i); b:=e+1 end
end
end
end
19
end;
{Трудоемкость: O(n·log k))}

20. Формирование словаря D из символьного массива S длиной n

p:=0; j:=0; k:=0;
while j<=n do begin
j:=j+1;
if j<=n then c:=S[j] else c:=' ';
if p=0 then begin
if Y[ord(c)]=1 then begin d1:=c; p:=1; i:=j end
end
else begin
if Y[ord(c)]=1 then d1:=d1+c
else begin
{слово выделено, поиск совпадения}
q:=1; p:=0;
while q<=k do {D - массив слов длиной k}
if scomp(d1,D[q])=0 then q:=k+2
else q:=q+1;
if q=k+1 then begin {добавление в массив D еще одного слова}
k:=k+1; D[k]:=d1
end
end
end
20
end;
Трудоемкость: O(n·k))

21. Информационные таблицы

Таблица – набор объектов одинаковой структуры
Структура объекта – набор разнотипных полей, каждое принадлежит какомулибо типу (целому, вещественному, строковому)
Представление в программе:
1) набор массивов, для каждого поля – отдельный массив;
2) массив или список записей, для каждого объекта – своя запись.
Пример. Структура объекта – 3 поля: A (целый тип), B (строковый тип),
C (целый тип).
1. Набор массивов:
var A, C: array[1..1000]of integer;
B: array[1..1000]of string[20];
i-я запись в таблице: (A[i], B[i], C[i])
2. Массив записей:
var T: array[1..1000]of record
A:integer; B: string[20]; C:integer
end;
i-я запись в таблице: (T[i].A, T[i].B, T[i].C)
21

22. Спортивное двоеборье

Результаты соревнований спортсменов по двум видам
в таблице:
Фамилия
Результат по 1-му виду
Результат по 2-му виду
F
R1
R2
Вычисление общего места в двоеборье по минимуму суммы
мест в двух видах:
Фамилия
Результат
по 1-му
виду
Результат
по 2-му
виду
F
R1
R2
Место по Место по
1-му виду 2-му виду
M1
M2
Сумма
мест
Общее
место в
двоеборье
MS
M2
22

23. Спортивное двоеборье

____________________________________________________
place(R1,M1,n);
{вычисление мест M1 по по 1-му виду}
place(R2,M2,n);
{вычисление мест M2 по по 2-му виду}
for i:=1 to n do
{вычисление суммы мест M0}
MS[i]:=M1[i]+M2[i];
place(MS,M0,n); {вычисление мест M0 по по обоим видам}
____________________________________________________
procedure place(var R,M:array of real;n:integer);
var i,ib,j:integer;
begin
{косвенная сортировка}
ssort(R,In,n);
{по возрастанию (убыванию)}
ib:=1;
for i:=1 to n do
if (i=n)or(R[In[i]]<>R[In[i+1]]) then begin
for j:=ib to i do M[In[j]]:=(ib+i)/2;
ib:=i+1
end
end;
23

24. Соединение отдельных таблиц результатов по двум видам в общую таблицу

Результаты соревнований спортсменов по двум видам
представлены в двух таблицах:
Фамилия
Результат по 1-му виду
Фамилия
Результат по 2-му виду
F1
R01
F2
R02
Общая таблица:
Фамилия
Результат по 1-му виду
Результат по 2-му виду
F
R1
R2
24

25. Соединение отдельных таблиц результатов в общую таблицу

sort2(F1,R01,n1); {упорядочение 1-й входной таблицы}
sort2(F2,R02,n2); {упорядочение 2-й входной таблицы}
{Пересечение множеств строк из 1-й и 2-й таблиц по фамилиям:}
i1:=1; i2:=1; n:=0;
while (i1<=n1)and(i2<=n2) do
if F1[i1]<F2[i2] then i1:=i1+1
else if F1[i1]>F2[i2] then i2:=i2+1
else begin
n:=n+1;
F[n]:=F1[i1];R1[n]:=R01[i1];R2[n]:=R02[i2];
i2:=i2+1; i1:=i1+1
end;
25

26. Вычисление средних оценок

Оценки по предмету, у одного ученика могут быть несколько
текущих оценок:
Фамилия
Оценка
F
R
Средние оценки учеников:
Фамилия
Средняя оценка
Количество текущих оценок
FS
RS
KS
26

27. Вычисление средних оценок

sort2(F,R,n); {упорядочение входной таблицы}
{Выделение групп записей с одинаковыми фамилиями и
вычисление для них среднего значения:}
S:=0; k:=0; m:=0;
for i:=1 to n do
begin S:=S+R[i]; k:=k+1;
if (i=n)or(F[i]<>F[i+1]) then begin
m:=m+1;
FS[m]:=F[i]; KS[m]:=k; RS[m]:=S/k;
S:=0; k:=0
end
end;
27