Created byDrago Percic
12 views1 downloads
Implementacija i upravljanje jednostruko spregnutim listama
Grade 10Computer Science1 days
★★★★★
5.0 (1 rating)Linked ListsC ProgrammingMemory ManagementPointersData StructuresAlgorithm EfficiencyDynamic Allocation
📝
Inquiry Framework
Question Framework
Driving Question
The overarching question that guides the entire project.Kako možemo dizajnirati i implementirati fleksibilan sistem za upravljanje dinamičkim podacima (poput pametne liste pesama ili sistema za upravljanje zadacima) koji prevazilazi ograničenja statičke memorije, a pritom osigurava bezbednost i integritet svakog elementa pri svakoj izmeni?Essential Questions
Supporting questions that break down major concepts.- Kako se jednostruko spregnuta lista razlikuje od statičkog niza u pogledu upravljanja memorijom i fleksibilnosti?
- Na koji način 'pokazivači' (ili reference) omogućavaju povezivanje elemenata koji nisu fizički susedi u memoriji?
- Koji su kritični koraci (i kojim redosledom se moraju izvršiti) da bi se novi čvor bezbedno umetnuo na specifičnu poziciju bez gubitka ostatka liste?
- Zašto je 'curenje memorije' ili 'izgubljeni pokazivač' (dangling pointer) rizik prilikom brisanja elemenata iz liste i kako to možemo sprečiti?
- Kako iteracija kroz listu (ispis) demonstrira linearan pristup podacima i koje su prednosti i mane ovakvog pristupa u odnosu na direktan pristup?
- U kojim realnim aplikacijama (poput muzičkih plejera ili 'undo' funkcija) je struktura liste efikasnija od klasičnog niza?
Standards & Learning Goals
Learning Goals
By the end of this project, students will be able to:- Učenici će moći da objasne strukturu čvora jednostruko spregnute liste i ulogu pokazivača u povezivanju dinamičkih podataka.
- Učenici će uspešno implementirati algoritme za dodavanje elemenata na početak, kraj i proizvoljno mesto u listi bez gubitka integriteta podataka.
- Učenici će razviti funkciju za brisanje elemenata sa specifične pozicije uz pravilno upravljanje memorijom (sprečavanje curenja memorije).
- Učenici će analizirati i uporediti efikasnost (vremensku i prostornu složenost) operacija nad listama u odnosu na statičke nizove.
- Učenici će kreirati funkcionalni prototip aplikacije (npr. muzička lista ili task menadžer) koji koristi povezane liste za dinamičko upravljanje podacima.
Program nastave i učenja za gimnaziju (Srbija)
2.RI.2.2.3.
Primary
Učenik dizajnira i implementira algoritme koristeći dinamičke strukture podataka (liste, stekovi, redovi).Reason: Ovaj standard direktno pokriva osnovnu temu projekta - implementaciju i manipulaciju jednostruko spregnutim listama.
2.RI.2.2.4.
Primary
Učenik upravlja memorijom koristeći pokazivače i dinamičku alokaciju memorije u odabranom programskom jeziku.Reason: Rad sa listama je nemoguć bez razumevanja pokazivača i dinamičke alokacije, što je ključni deo ovog standarda.
2.RI.2.2.1.
Secondary
Učenik analizira efikasnost algoritama i bira odgovarajuće strukture podataka za rešavanje konkretnih problema.Reason: Projekat podstiče učenike da porede liste sa nizovima, što doprinosi razvoju veština analize algoritamske efikasnosti.
CSTA K-12 Computer Science Standards
CSTA 3A-AP-14
Supporting
Construct programs that use collections of data, such as lists, to represent real-world phenomena.Reason: Ovaj međunarodni standard podržava primenu listi u modelovanju realnih sistema poput muzičkih plejera, što je centralni deo Driving Question-a.
Entry Events
Events that will be used to introduce the project to studentsThe Human Data Stream Challenge
Students participate in a physical simulation where they represent 'nodes' holding pieces of a secret code. To add a new student into the middle of the 'line' without moving anyone else's physical position, they must creatively use strings (pointers) to redirect the flow, highlighting the efficiency of linked lists over arrays.📚
Portfolio Activities
Portfolio Activities
These activities progressively build towards your learning goals, with each submission contributing to the student's final portfolio.Activity 1
Nacrt Čvora: Temelji u C-u (Konstrukcija Čvora)
Pre nego što pređu na izgradnju cele liste, učenici moraju razumeti anatomiju jednog „Čvora” (Node) u jeziku C. U ovoj aktivnosti, učenici definišu strukturu (struct) koja sadrži podatak (npr. ceo broj) i pokazivač na sledeći element istog tipa. Vežbaće dinamičku alokaciju memorije na „heap-u” koristeći funkciju malloc i naučiće kako da pristupe poljima strukture preko pokazivača.Steps
Here is some basic scaffolding to help students complete the activity.1. Definisati strukturu 'Cvor' koja sadrži celobrojnu promenljivu 'podatak' i samoreferencirajući pokazivač 'sledeci' (struct Cvor* sledeci).
2. U 'main' funkciji, koristeći funkciju 'malloc' i operator 'sizeof', dinamički alokovati memoriju za dva čvora (npr. glava i drugi_cvor). Obavezno uključiti zaglavlje <stdlib.h>.
3. Ručno dodeliti vrednosti podacima i povezati čvorove tako što će pokazivač 'sledeci' prvog čvora dobiti adresu drugog čvora, dok će 'sledeci' drugog čvora postati NULL.
4. Nacrtati memorijsku mapu (dijagram) koja ilustruje stack (gde su pokazivači) i heap (gde su stvarni podaci), prikazujući kako pokazivači „pokazuju” na memorijske adrese.
Final Product
What students will submit as the final product of the activityIzvorni fajl u programskom jeziku C (.c) koji sadrži definiciju strukture 'Cvor', upotrebu funkcije 'malloc' za kreiranje dva čvora i njihovo ručno povezivanje, uz priloženu skicu (dijagram) memorije.Alignment
How this activity aligns with the learning objectives & standardsAktivnost je direktno usklađena sa standardom 2.RI.2.2.4: „Učenik upravlja memorijom koristeći pokazivače i dinamičku alokaciju memorije u odabranom programskom jeziku”. Fokus je na C sintaksi i funkciji malloc.Activity 2
Lančana reakcija: Širenje liste (Dodavanje na početak i kraj)
Učenici će implementirati dve osnovne operacije za rad sa listom: dodavanje elementa na sam početak (glava - Head) i na sam kraj (rep - Tail). Ova vežba je ključna za razumevanje kako se pokazivači preusmeravaju i kako se vrši iteracija (prolazak) kroz listu kako bi se pronašao poslednji element koji pokazuje na NULL.Steps
Here is some basic scaffolding to help students complete the activity.1. Napisati funkciju 'dodajNaPocetak': kreirati novi čvor pomoću 'malloc', dodeliti mu vrednost, usmeriti njegov pokazivač 'sledeci' na trenutnu glavu liste, a zatim ažurirati glavu liste da pokazuje na novi čvor.
2. Napisati funkciju 'dodajNaKraj': obraditi scenario prazne liste (gde novi čvor postaje glava), a za popunjenu listu koristiti 'while' petlju da se dođe do poslednjeg čvora (onog koji pokazuje na NULL) i povezati ga sa novim čvorom.
3. Implementirati funkciju 'prikaziListu' koja koristi pomoćni pokazivač za prolazak kroz celu listu od početka do kraja, ispisujući vrednost svakog čvora u konzoli.
4. U 'main' funkciji testirati kod dodavanjem najmanje pet različitih brojeva (kombinovanjem obe funkcije) i pozvati ispis kako bi se vizuelno potvrdio ispravan redosled elemenata.
Final Product
What students will submit as the final product of the activityBiblioteka koda (izvorni fajl .c) koja sadrži definisane funkcije 'dodajNaPocetak', 'dodajNaKraj' i 'prikaziListu', uz dokaz o uspešnom testiranju (ispis u konzoli).Alignment
How this activity aligns with the learning objectives & standardsAktivnost je direktno usklađena sa standardom 2.RI.2.2.3: „Učenik dizajnira i implementira algoritme koristeći dinamičke strukture podataka (liste, stekovi, redovi)”. Fokus je na logici proširivanja liste sa oba kraja i razumevanju mehanizma pokazivača pri promeni strukture.Activity 3
Hirurška preciznost: Umetanje na željeno mesto
Umetanje u sredinu liste je poput „secanja” fizičkog lanca da bi se dodala nova karika. Učenici će naučiti kako da navigiraju kroz listu do pozicije „n-1”, povežu novi čvor sa čvorom koji je trenutno na poziciji „n”, a zatim preusmere pokazivač sa pozicije „n-1” na novi čvor. Poseban akcenat je na rukovanju graničnim slučajevima, kao što su umetanje na početak (indeks 0) ili pokušaj umetanja na poziciju koja ne postoji.Steps
Here is some basic scaffolding to help students complete the activity.1. Kreirati funkciju koja kao argumente prima pokazivač na glavu liste, podatak koji se unosi i ceo broj „pozicija” na koju se element smešta.
2. Implementirati petlju (for ili while) koja se zaustavlja tačno jedan korak pre željene pozicije kako bi se zadržala referenca na „prethodni” čvor.
3. Izvršiti ključnu operaciju povezivanja: prvo usmeriti pokazivač „sledeci” novog čvora na čvor koji trenutno sledi, a tek onda usmeriti pokazivač prethodnog čvora na novi čvor.
4. Dodati proveru grešaka i validaciju: ispisati odgovarajuću poruku ako je korisnik uneo negativnu poziciju ili poziciju koja je veća od trenutnog broja elemenata u listi.
Final Product
What students will submit as the final product of the activityAžurirani izvorni kod (.c fajl) koji sadrži funkciju „dodajNaPoziciju” i tabelu ručnog praćenja koda (trace table) koja prikazuje promene vrednosti pokazivača u svakom koraku iteracije.Alignment
How this activity aligns with the learning objectives & standardsAktivnost je direktno usklađena sa standardom 2.RI.2.2.3: „Učenik dizajnira i implementira algoritme koristeći dinamičke strukture podataka”. Fokus je na složenoj manipulaciji pokazivačima na specifičnoj poziciji, što zahteva precizan logički redosled kako bi se očuvao integritet ostatka liste.Activity 4
Ekipa za čišćenje: Brisanje sa pozicije i oslobađanje memorije
U ovoj aktivnosti učenici će implementirati logiku za uklanjanje člana liste sa specifične pozicije. Glavni izazov je pravilno „premošćavanje“ čvora koji se uklanja: učenici moraju da preusmere pokazivač prethodnog čvora na čvor koji sledi nakon onog koji se briše, a zatim da eksplicitno oslobode memoriju koju je zauzimao obrisani čvor. Ovo je ključna veština za pisanje stabilnih i efikasnih programa koji ne troše nepotrebno resurse sistema.Steps
Here is some basic scaffolding to help students complete the activity.1. Pronaći čvor koji se nalazi na poziciji 'pozicija - 1' (čvor neposredno pre onog koji treba da bude obrisan) prolaskom kroz listu pomoću petlje.
2. Kreirati pomoćni (privremeni) pokazivač koji će čuvati adresu čvora koji se briše, kako bismo zadržali referencu na taj deo memorije pre nego što ga „otkačimo” iz lanca.
3. Izvršiti preusmeravanje: postaviti pokazivač 'sledeci' prethodnog čvora da pokazuje direktno na čvor koji se nalazi iza onog koji brišemo (čime ga faktički izbacujemo iz niza).
4. Upotrebiti funkciju 'free()' nad privremenim pokazivačem kako bi se zauzeta memorija na heap-u vratila operativnom sistemu, čime se sprečava curenje memorije.
Final Product
What students will submit as the final product of the activityAžuriran izvorni kod (.c fajl) koji sadrži funkcionalnu proceduru „obrisiSaPozicije“ i kratak tekstualni ili vizuelni dokaz (npr. screenshot ili komentar u kodu) da je memorija pravilno oslobođena korišćenjem funkcije free().Alignment
How this activity aligns with the learning objectives & standardsAktivnost je direktno usklađena sa standardima 2.RI.2.2.4 (Upravljanje memorijom koristeći pokazivače i dinamičku alokaciju) i 2.RI.2.2.3 (Dizajniranje i implementacija algoritama koristeći dinamičke strukture). Fokus je na razumevanju životnog ciklusa podataka u memoriji i sprečavanju „curenja memorije“ (memory leak).Activity 5
Digitalna Melodija: Dinamička lista pesama (Finalni projekat)
U ovoj završnoj aktivnosti, učenici će primeniti svoje znanje o jednostruko spregnutim listama na realan scenario: kreiranje „Dinamičke muzičke liste” ili „Menadžera zadataka”. Učenici će integrisati sve prethodno razvijene funkcije (dodavanje, brisanje, ispis) u jednu interaktivnu aplikaciju kojom se upravlja putem korisničkog menija. Pored programiranja, fokus je na kritičkom razmišljanju i poređenju efikasnosti liste u odnosu na statičke nizove u kontekstu čestih izmena podataka.Steps
Here is some basic scaffolding to help students complete the activity.1. Izmeniti strukturu 'Cvor' tako da polje za podatak umesto celog broja (int) čuva naziv pesme (npr. char naziv[50] ili string).
2. U 'main' funkciji implementirati 'switch-case' strukturu koja omogućava korisniku da interaktivno bira operacije (npr. 1 za dodavanje na početak, 2 za brisanje sa pozicije, 3 za ispis liste, 0 za izlaz).
3. Testirati aplikaciju kroz konkretan scenario: dodati 3 pesme, obrisati pesmu sa sredine liste, a zatim dodati novu pesmu na početak, proveravajući ispravnost ispisa nakon svake operacije.
4. Napisati analizu od približno 200 reči u kojoj se objašnjava zašto je povezana lista bolji izbor za muzički plejer (gde se pesme stalno dodaju i brišu) u odnosu na običan niz fiksne dužine.
Final Product
What students will submit as the final product of the activityFunkcionalna konzolna aplikacija sa interaktivnim menijem (Dodaj pesmu, Obriši pesmu, Prikaži listu) i kratka pisana analiza (esej) sa uporednom tabelom vremenske složenosti operacija za liste i nizove.Alignment
How this activity aligns with the learning objectives & standardsAktivnost je direktno usklađena sa standardom 2.RI.2.2.1: „Učenik analizira efikasnost algoritama i bira odgovarajuće strukture podataka za rešavanje konkretnih problema”. Takođe podržava CSTA 3A-AP-14 standard kroz primenu kolekcija podataka za predstavljanje fenomena iz stvarnog sveta.🏆
Rubric & Reflection
Portfolio Rubric
Grading criteria for assessing the overall project portfolioRubrika za procenu portfolija: Jednostruko spregnute liste u C-u
Category 1
Tehnička implementacija i memorijska arhitektura
Ovaj domen ocenjuje tehničku preciznost u pisanju C koda i razumevanje fizičke organizacije podataka u memoriji.Criterion 1
Struktura podataka i upravljanje memorijom (2.RI.2.2.4)
Ocenjuje sposobnost učenika da ispravno definiše 'Cvor', koristi dinamičku alokaciju memorije (malloc/free) i vizuelno predstavi stanje memorije (stack i heap).
Exemplary
4 PointsUčenik besprekorno definiše strukturu čvora, koristi malloc/free bez grešaka, i kreira precizan memorijski dijagram koji jasno razdvaja stack i heap. Nema curenja memorije.
Proficient
3 PointsUčenik ispravno definiše strukturu i koristi dinamičku alokaciju, ali memorijski dijagram sadrži sitne nepreciznosti ili nedostaje jedan aspekt oslobađanja memorije.
Developing
2 PointsUčenik delimično uspešno koristi malloc, ali ima poteškoća sa sintaksom pokazivača ili dijagram ne prikazuje jasno vezu između stack-a i heap-a.
Beginning
1 PointsStruktura čvora je pogrešno definisana ili nedostaje upotreba funkcije malloc. Memorijski dijagram je nejasan ili nedostaje.
Criterion 2
Algoritmi manipulacije listom (2.RI.2.2.3)
Fokusira se na logiku povezivanja čvorova pri dodavanju na različite pozicije, osiguravajući da se 'lanac' ne prekine i da se pravilno rukuje pokazivačima.
Exemplary
4 PointsAlgoritmi su robusni, rukuju svim graničnim slučajevima (prazna lista, jedan element, nepostojeća pozicija). Kod je čitljiv i optimalno napisan.
Proficient
3 PointsFunkcije dodavanja i brisanja rade ispravno za standardne slučajeve, ali se javljaju greške pri specifičnim graničnim situacijama (npr. brisanje glave liste).
Developing
2 PointsUčenik uspešno implementira dodavanje na početak, ali greši u logici iteracije (pronalaženja pozicije) ili gubi referencu na ostatak liste.
Beginning
1 PointsAlgoritmi su nepotpuni; dodavanje ili brisanje dovodi do 'segmentation fault' grešaka ili potpunog gubitka podataka.
Category 2
Analitičko razmišljanje i praktična primena
Ovaj domen meri sposobnost učenika da primeni apstraktno znanje na realne probleme i da kritički vrednuje svoja rešenja.Criterion 1
Sinteza aplikacije i analiza efikasnosti (2.RI.2.2.1)
Ocenjuje kvalitet završne aplikacije (muzika lista) i dubinu pisane analize u kojoj se porede liste i nizovi.
Exemplary
4 PointsAplikacija je potpuno funkcionalna sa intuitivnim menijem. Analiza duboko razmatra vremensku složenost O(1) naspram O(n) i pruža ubedljive argumente za izbor strukture.
Proficient
3 PointsAplikacija radi, ali meni ima manje logičke propuste. Analiza tačno poredi liste i nizove, ali bez detaljnog osvrta na specifičnu vremensku složenost.
Developing
2 PointsAplikacija nudi osnovne funkcije, ali nedostaju provere validnosti. Analiza je površna i ne objašnjava jasno prednosti liste u dinamičkim sistemima.
Beginning
1 PointsAplikacija nije funkcionalna ili nedostaje pisana analiza. Poređenje struktura podataka je netačno.
Category 3
Komunikacija i proces rešavanja problema
Fokusira se na komunikaciju logičkog procesa kroz kod i prateću dokumentaciju, što je ključno za timski rad i debagovanje.Criterion 1
Dokumentacija i logička vizuelizacija (Trace Table)
Ocenjuje jasnoću koda, upotrebu komentara za objašnjenje pokazivačke aritmetike i preciznost Trace tabele za umetanje elemenata.
Exemplary
4 PointsKod je uzoran, komentari detaljno objašnjavaju svaki korak preusmeravanja pokazivača. Trace tabela je bez greške i prati svaku promenu adrese.
Proficient
3 PointsKod je uredan, ali komentari su šturi. Trace tabela ispravno prikazuje ključne promene, ali nedostaju međukoraci.
Developing
2 PointsKod je teško čitljiv, a komentari ne objašnjavaju logiku pokazivača. Trace tabela je nepotpuna ili sadrži logičke greške.
Beginning
1 PointsNedostaju komentari i dokumentacija. Trace tabela nije dostavljena ili je potpuno netačna.
Reflection Prompts
End-of-project reflection questions to get students to think about their learningQuestion 1
Koliko se osećaš samouvereno u korišćenju pokazivača za ručno povezivanje i preusmeravanje elemenata u memoriji bez gubitka podataka?
Scale
Required
Question 2
Prilikom implementacije funkcije za brisanje člana sa sredine liste, koji redosled koraka je ključan da bi se osigurala bezbednost podataka i integritet memorije?
Multiple choice
Required
Options
Prvo preusmeriti pokazivač prethodnog čvora, pa odmah zatim obrisati čvor bez pomoćnog pokazivača.
Kreirati pomoćni pokazivač na čvor koji se briše, preusmeriti veze oko njega, a zatim osloboditi memoriju pomoću free().
Prvo upotrebiti funkciju free() na čvoru, a zatim pokušati da povežete prethodni i sledeći čvor.
Samo preusmeriti pokazivače; funkcija malloc() sama čisti memoriju kada se program završi.
Question 3
Na osnovu tvog završnog projekta (Digitalna Melodija), objasni specifičnu situaciju u kojoj bi korišćenje običnog niza umesto povezane liste učinilo aplikaciju manje efikasnom ili težom za korišćenje. Obrazloži odgovor kroz primer dodavanja ili brisanja pesama.
Text
Required
Question 4
Koji je bio najteži logički 'čvor' (izazov) sa kojim si se suočio/la tokom kodiranja ovih operacija i koja strategija ili vizuelni prikaz (npr. crtanje memorije) ti je najviše pomogao da ga razrešiš?
Text
Optional