Структури от данни — учебник, проверен код и покритие на конспекта

М. Тодорова, Структури от данни и програмиране на C++, Сиела, София, 2011 — № 2 в официалната библиография на СУ. Това е същият автор и заглавие, а не допълнителна книга със сходна тематика.

Използваме дигитализацията на предоставения скан: 318 PDF страници, текст, копируем код и векторни схеми. „Ориг.“ означава отпечатания номер в книгата; „нов PDF“ е позицията в четеца на тази конкретна версия. Диапазонът включва и продължението на оригинална страница, ако е пренесено на следващ PDF лист. Номерата не важат за суровия скан.

Отвори дигитализирания учебник · Свали PDF · Свали проверения код, тестовете и описанието на поправките

Таблица за всичките 20 теми · Проверки и поправки · Ред за четене · Официален конспект

Кои теми покрива учебникът

СУ 2 — покритие на конспекта; кратки ориентировъчни заглавия, официалната формулировка остава в конспекта
ТемаСтепен на покритиеПолезни части и точни странициКакво остава извън обхвата
I.1. ООПЧастично — приложение на ООПКлас, интерфейс, конструктори, копиране и унищожаване: ориг. 32–41 / нов PDF 29–38; наследяване при стек/опашка: ориг. 90–95 / нов PDF 85–90; разнородни списъци и виртуални функции: ориг. 132–137 / нов PDF 126–132.Не заменя СУ 1, 3 и 4. Не развива систематично проектните шаблони; шаблон на C++ клас не е design pattern.
I.2. Структури от данни: низ, множество, масивСъществено, но частично§1.1–1.3: ориг. 9–19 / нов PDF 9–18; сложност: ориг. 19–25 / нов PDF 17–22; множества: ориг. 104–108 / нов PDF 99–103; търсене в масив: ориг. 300–303 / нов PDF 282–286.Масивът и множеството имат пряка опора. Низовете са предпоставени/използвани, без пълно изложение на всички операции; разделът за низове изисква други източници.
I.3. Линейни списъци, стек, опашка, сортирани списъциОсновна опораСтек: ориг. 30–55 / нов PDF 27–52; опашка: ориг. 55–77 / нов PDF 51–73; едносвързан списък: ориг. 78–89 / нов PDF 73–84; сортирани списъци: ориг. 95–99 / нов PDF 89–94; циклични/двусвързани: ориг. 113–131 / нов PDF 107–126.Показаните в разработката рекурсивни length/contains са авторско допълнение, не цитирани листинги. Книгата често реализира списъчните операции итеративно; връзката с рекурсията е подкрепена и от СУ 9.
I.4. Дървета, графи, обхождания, покриващо дърво, сложностОсновна опора с уточнени границиКоренови дървета: ориг. 157–163 / нов PDF 151–156; двоични: ориг. 164–185 / нов PDF 156–177; BST и балансиране: ориг. 186–215 / нов PDF 177–206; графи/представяне: ориг. 224–238 / нов PDF 213–227; BFS/DFS: ориг. 239–243 / нов PDF 228–232; пътища: ориг. 244–249 / нов PDF 232–237.Конструирането на покриващо дърво чрез родителите е авторски извод от обхожданията. За минимално покриващо дърво се запазва допълнителният MIT източник. Оценките зависят от реализацията.
I.5. Функционално програмиранеЧастично — функции от по-висок редaccumulate, map, filter: ориг. 108–112 / нов PDF 102–107; върху дървета: ориг. 175–177 / нов PDF 167–170.Това са C++ реализации. Не заместват Haskell, модела на заместване и ленивото оценяване; основни остават СУ 6 и СУ 9.
I.6. Бази от данни, СУБД, релационни и NoSQL системиСамо помощен фонB-дървета: ориг. 215–224 / нов PDF 205–214; хеширане: ориг. 303–317 / нов PDF 285–299.Полезни за идеята за индекс, но не покриват моделите, архитектурата и свойствата на СУБД. Не е основание за сверяване на цялата тема.
I.7. SQLНе покрива—Няма систематично изложение на SQL; използвай литературата за бази данни.
I.8. XML, DTD/XSD, HTML, DOMСамо общ фон за дърветаЙерархични структури: ориг. 157–185 / нов PDF 151–177.Дърветата помагат за интуицията, но XML/DOM и техните стандарти не са предмет на учебника.
I.9. Пространство на състоянията и търсенеЧастично — неинформирано търсенеBFS/DFS: ориг. 239–243 / нов PDF 228–232; намиране и възстановяване на пътища: ориг. 244–249 / нов PDF 232–237.Няма достатъчна опора за евристики, hill climbing, greedy и A*. Запазва се официалният учебник по ИИ (СУ 8).
II.1. ER модел — основни елементиНе покрива—Не разглежда ER същности, връзки и атрибути.
II.2. Проектиране на ER модели и ограниченияНе покрива—Класовете/указателите в C++ не са ER ограничения.
II.3. Слаби множества същностиНе покрива—Няма ER идентифициращи връзки и частични ключове.
II.4. Релационен модел и преобразуване от ERНе покрива—Записът struct не е изложение на релационната схема или ER преобразуването.
II.5. Функционални зависимостиНе покрива—Функция в C++ не означава функционална зависимост между атрибути.
II.6. Декомпозиция, BCNF и 3NFНе покрива—Няма теория на нормализацията и декомпозициите.
II.7. Многозначни зависимости и 4NFНе покрива—Няма изложение на многозначни зависимости.
II.8. Релационна алгебраСамо помощен фонМножества: ориг. 104–108 / нов PDF 99–103.Операциите с множества са само предварително знание; не покриват проекция, съединяване и релационни изрази.
II.9. Алгебра върху мултимножестваНе покрива—Списъкът с повторения сам по себе си не дава семантиката на релационните операции върху мултимножества.
II.10. Разширени релационни операцииСамо помощен фонАлгоритми за сортиране: ориг. 266–299 / нов PDF 253–282.Сортирането на масиви не покрива групиране, агрегиране и външни съединявания.
II.11. Ограничения в релационния моделНе покрива—Инвариантите на C++ структури не заместват ключови/референтни ограничения и релационния им запис.

Как е проверен кодът

98 събрани листинга и допълнителните изпълними фрагменти са проверени с 88 целеви тестови програми: компилация като C++17 с Clang/LLVM-MinGW, изпълнение с AddressSanitizer и UndefinedBehaviorSanitizer. Всички 88 проверки са успешни. Проверка за течове чрез LeakSanitizer не е извършвана в Windows. Тестовете обхващат конкретни допустими входове и гранични случаи; не доказват коректност за всеки възможен вход.

Архивът съдържа src, tests, index.html с копиране на код, ПРОЧЕТИ_МЕ.txt с условията, differences.diff с промените, verification.json и възпроизводим run_tests.py. Алтернативните реализации се компилират отделно, защото някои имат еднакви имена. Граматиките, формулите и примерният изход са обозначени отделно и не са представени като компилирани програми.

Поправени са зависимости и синтаксис на шаблони, обхват на променливи, гранични случаи при празни структури, копиране на AVL баланса, конкатениране на списък със себе си, достъп пред началото на файл, ограничения на хеш-таблиците и обработване на край на входа. Част от поправките са за съвременно компилиране и сглобяване на откъсите, а други са логически поправки. Оригиналният препис и PDF са запазени; редактираните версии са в отделния комплект.

Лек ред за подготовка

  1. I.2: определения и представяне → един масив → множество без повторения.
  2. I.3: стек → опашка → едносвързан списък → вмъкване/изтриване → сортиран списък.
  3. I.4: дърво с няколко възела → трите реда на обхождане → BST → граф → BFS/DFS → родителски ребра.
  4. I.1 и I.5: върни се към класовете и map/filter/accumulate като приложения на вече познати структури.
  5. I.9: пренеси BFS/DFS към състояния и действия; евристиките учи от учебника по ИИ.

За всеки откъс първо проследи един малък пример на хартия, после отвори отделния проверен листинг. Не е нужно да четеш всички програми или да запаметяваш цели C++ класове, за да изградиш изпитния отговор.