Структури от данни — учебник, проверен код и покритие на конспекта
М. Тодорова, Структури от данни и програмиране на C++, Сиела, София, 2011 — № 2 в официалната библиография на СУ. Това е същият автор и заглавие, а не допълнителна книга със сходна тематика.
Използваме дигитализацията на предоставения скан: 318 PDF страници, текст, копируем код и векторни схеми. „Ориг.“ означава отпечатания номер в книгата; „нов PDF“ е позицията в четеца на тази конкретна версия. Диапазонът включва и продължението на оригинална страница, ако е пренесено на следващ PDF лист. Номерата не важат за суровия скан.
Отвори дигитализирания учебник · Свали PDF · Свали проверения код, тестовете и описанието на поправките
Таблица за всичките 20 теми · Проверки и поправки · Ред за четене · Официален конспект
Кои теми покрива учебникът
| Тема | Степен на покритие | Полезни части и точни страници | Какво остава извън обхвата |
|---|---|---|---|
| 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 са запазени; редактираните версии са в отделния комплект.
Лек ред за подготовка
- I.2: определения и представяне → един масив → множество без повторения.
- I.3: стек → опашка → едносвързан списък → вмъкване/изтриване → сортиран списък.
- I.4: дърво с няколко възела → трите реда на обхождане → BST → граф → BFS/DFS → родителски ребра.
- I.1 и I.5: върни се към класовете и map/filter/accumulate като приложения на вече познати структури.
- I.9: пренеси BFS/DFS към състояния и действия; евристиките учи от учебника по ИИ.
За всеки откъс първо проследи един малък пример на хартия, после отвори отделния проверен листинг. Не е нужно да четеш всички програми или да запаметяваш цели C++ класове, за да изградиш изпитния отговор.