Po masyvų antra pagal populiarumą duomenų struktūra yra susietas sąrašas. Susietas sąrašas yra linijinė duomenų struktūra, sudaryta iš mazgų grandinės, kurioje kiekviename mazge yra reikšmė ir žymeklis į kitą grandinės mazgą. Šiame straipsnyje pažiūrėkime, kaip įdiegti susietą sąrašą C.
Kas yra susietasis sąrašas C?
Susietas sąrašas yra linijinė duomenų struktūra. Kiekviename susietame sąraše yra dvi dalys: duomenų skyrius ir adreso skyrius, kuriame yra kito sąrašo elemento, kuris vadinamas mazgu, adresas.
Susieto sąrašo dydis nėra fiksuotas, o duomenų elementus galima pridėti bet kurioje sąrašo vietoje. Trūkumas yra tas, kad norėdami patekti į mazgą, mes turime pereiti visą kelią nuo pirmo mazgo iki reikalingo mazgo. Susietas sąrašas yra kaip masyvas, tačiau, skirtingai nei masyvas, jis nėra nuosekliai saugomas atmintyje.
Populiariausi susieto sąrašo tipai yra šie:
susietas sąrašo kodas c
Susieto sąrašo pavyzdys
Formatas: [duomenys, adresas]
Galvutė -> [3,1000] -> [43,1001] -> [21,1002]
Pavyzdyje skaičius 43 yra 1000 vietoje, o adresas yra ankstesniame mazge. Taip pateikiamas susietas sąrašas.
Pagrindinės susieto sąrašo funkcijos
C. susietame sąraše gali būti įdiegtos kelios funkcijos. Pabandykime jas suprasti programos pavyzdžio pagalba.Pirmiausia sukuriame sąrašą, jį rodome, įterpiame bet kurioje vietoje, ištriname vietą. Šis kodas parodys, kaip atlikti operacijas sąraše.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3.Įterpti pradžia n ') printf (' n 4.Įterpti pabaigoje n ') printf (' n 5.Įterpti nurodytoje vietoje n ') printf (' n 6.Delete from n pradžios ') printf (' n 7.Delete nuo pabaigos n ') printf (' n 8. Ištrinti iš nurodytos n pozicijos ') printf (' n 9. Exit n ') printf (' n ----------------- --------------------- n ') printf (' Įveskite savo pasirinkimą: t ') scanf ('% d 'ir pasirinkimas) jungiklis (pasirinkimas) {1 atvejis : sukurti () pertraukos atvejis 2: rodyti () pertraukos atvejis 3: įterpimo_ pradžia () pertraukos atvejis 4: įterpimo_pabaiga () pertraukos atvejis 5: įterpimo_pasiekimas () pertraukos atvejis 6: ištrynimo_ pradžia () pertraukos atvejis 7: ištrynimo_ baigimas () pertraukos atvejis 8: delete_pos () pertraukos 9 atvejis: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d sukurti () {struktūros mazgas * temp, * ptr temp = (struktūros mazgas *) malloc (sizeof (struktūros mazgas)) if (temp == NULL) {printf ('nAtmintis iš atminties: n') išeiti (0) } printf ('nĮveskite mazgo duomenų vertę: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} negaliojantis ekranas () {struct mazgas * ptr if (start == NULL) {printf ('nList yra tuščias: n ') return} else {ptr = pradėti spausdinti (' nSąrašo elementai yra: n '), o (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> kitas}}} void insert_begin () {struktūros mazgas * temp temp = (struktūros mazgas *) malloc (sizeof (struktūros mazgas)) if (temp == NULL) {printf ('nAtmintis iš atminties: n') grįžti} printf ('nĮveskite mazgo duomenų reikšmė: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nAtmintis iš atminties: n') grįžti} p rintf ('nĮveskite mazgo duomenų vertę: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nAtmintis iš atminties: n') return} printf ('nĮveskite naujo įterpiamo mazgo vietą: t') scanf ('% d' , & pos) printf ('nĮveskite mazgo duomenų vertę: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nNepavyko rasti: [elkitės atsargiai] n') grįžti}} temp-> next = ptr-> kitas ptr -> next = temp}} void delete_begin () {struct mazgas * ptr if (ptr == NULL) {printf ('nList is Empty: n') grįžti} else {ptr = start start = start-> next printf (' nPašalintas elementas yra:% dt ', ptr-> info) nemokamai (ptr)}} void delete_end () {struct mazgas * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') išeiti (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nPašalintas elementas yra:% dt', ptr-> info) nemokamai (ptr)} else {ptr = start while (ptr- > kitas! = NULL) {temp = ptr ptr = ptr-> kitas} temp-> kitas = NULL printf ('nPašalintas elementas yra:% dt', ptr-> informacija) nemokama (ptr)}} negaliojanti delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nSąrašas yra tuščias: n') exit (0)} else {printf ('nĮveskite trintino mazgo vietą : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nPašalintas elementas yra:% dt ', ptr-> info) nemokamai (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nPašalintas elementas yra: % dt ', ptr-> info) nemokamai (ptr)}}}Pirmoji šio kodo dalis kuria struktūrą. Susieta sąrašo struktūra sukurta taip, kad joje būtų duomenys ir adresai, kaip mums reikia. Tai daroma norint sudaryti kompiliatoriui idėją, koks turėtų būti mazgas.
struct mazgas {int info struct mazgas * kitas}Struktūroje turime duomenų kintamąjį, vadinamą info, kad laikytume duomenis, ir rodyklės kintamąjį, nurodantį adresą. Susietame sąraše galima atlikti įvairias operacijas, pvz .:
- sukurti ()
- rodyti ()
- insert_begin ()
- įterpti_pabaiga ()
- ] insert_pos ()
- delete_begin ()
- ištrinti_pabaiga ()
- delete_pos ()
Šias funkcijas vadina meniu valdoma pagrindinė funkcija. Pagrindinėje funkcijoje mes imame vartotojo indėlį atsižvelgdami į tai, kokią operaciją vartotojas nori atlikti programoje. Tada įvestis siunčiama į jungiklio dėžutę ir pagrįsta vartotojo įvestimi.
Atsižvelgiant į tai, kokia įvestis pateikiama, funkcija bus iškviesta. Toliau mes turime skirtingas funkcijas, kurias reikia išspręsti. Pažvelkime į kiekvieną iš šių funkcijų.
Sukurti funkciją
Pirma, susikurtam sąrašui sukurti yra funkcija „Sukurti“. Tai yra pagrindinis susietojo sąrašo kūrimo būdas. Leiskite mums pažvelgti į kodą.
void create () {struct mazgas * temp, * ptr printf ('nĮveskite mazgo duomenų vertę: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Rezultatas
Pirmiausia sukuriami du tokio tipo rodyklės mazgas, ptr ir temp . Vertę, kurią reikia pridėti susietame sąraše, mes paimame iš vartotojo ir saugome ją temp kintamojo informacinėje dalyje, o kito, tai yra adreso dalis, priskiriame nuliui. Yra pradžios rodyklė, turinti sąrašo pradžią. Tada mes patikriname sąrašo pradžią. Jei sąrašo pradžia yra nulinė, tada pradiniam žymekliui priskiriame temp. Priešingu atveju pereiname prie paskutinio taško, kuriame buvo pridėti duomenys.
Tam priskiriame pradinę reikšmę ptr ir traversą iki ptr-> kitas = nulinis . Tada mes paskiriame ptr-> kitas temp. adresas Panašiai pateikiamas kodas įterpti pradžioje, įterpti pabaigoje ir įterpti nurodytoje vietoje.
Ekrano funkcija
Štai rodymo funkcijos kodas.
void display () {struct mazgas * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nSąrašo elementai yra: n'), o (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> kitas}}}Rezultatas
Ekrano funkcijoje pirmiausia patikriname, ar sąrašas tuščias, ir grįžtame, jei jis tuščias. Kitoje dalyje pradinę vertę priskiriame ptr. Tada vykdome ciklą, kol ptr yra nulinis, ir atspausdiname kiekvieno mazgo duomenų elementą, kol ptr bus nulinis, nurodantis sąrašo pabaigą.
Ištrinti funkciją
Štai kodo fragmentas norint ištrinti mazgą iš susieto sąrašo.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nSąrašas yra tuščias: n') exit (0)} else {printf ('nĮveskite ištrinamas mazgas: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nPašalintas elementas yra:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> kitas printf ('nThe ištrintas elementas yra:% dt ', ptr-> info) nemokamai (ptr)}}}Rezultatas
Ištrynimo procese pirmiausia patikrinama, ar sąrašas tuščias, jei taip, jis egzistuoja. Jei ji nėra tuščia, ji prašo vartotojo ištrinti poziciją. Kai vartotojas įeina į poziciją, jis patikrina, ar ji yra pirmoji pozicija, jei taip, ji priskiria ptr pradėti ir perkelti pradžios žymeklį į kitą vietą ir ištrinti ptr. Jei pozicija nėra lygi nuliui , tada jis paleidžia ciklo ciklą nuo 0 iki pat vartotojo įvestos ir saugomos poz kintamasis. Yra „if“ teiginys, kad būtų galima nuspręsti, ar nėra įrašytos pozicijos. Jei ptr yra lygus nuliui , tada jo nėra.
Mes priskirti ptr prie temp for cikle ir ptr pereina prie kitos dalies. Po to, kai padėtis randama. Padarome temp kintamąjį, kad išlaikytume reikšmę ptr-> kitas taip praleisdamas ptr. Tada ptr ištrinamas. Panašiai tai galima padaryti ištrinant pirmą ir paskutinį elementus.
Dvigubai susietas sąrašas
Jis vadinamas dvigubai susietu sąrašu, nes yra du rodyklės , vienas taškas į kitą mazgą ir kiti taškai į ankstesnį mazgą. Dvigubai susietos operacijos atliekamos panašiai kaip ir atskirai susietame sąraše. Štai pagrindinių operacijų kodas.
#include #include struct mazgas typedef struct mazgas * PtrToNode typedef PtrToNode sąrašas typedef PtrToNode pozicijos struktūros mazgas {int e pozicija ankstesnė pozicija kita} negaliojantis intarpas (int x, sąrašas l, pozicija p) {pozicija TmpCell TmpCell = (struktūros mazgas *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Atmintyje nėra vietos') dar {TmpCell-> e = x TmpCell-> ankstesnis = p TmpCell-> kitas = p-> kitas p-> kitas = TmpCell}} negaliojantis Ištrinti (int x, sąrašas l) {Pozicija p, p1, p2 p = Rasti (x, l) if (p! = NULL) {p1 = p -> ankstesnis p2 = p -> kitas p1 - > next = p -> next if (p2! = NULL) // jei mazgas nėra paskutinis mazgas p2 -> ankstesnis = p -> ankstesnis} else printf ('Elementas neegzistuoja !!! n')} negaliojantis Rodyti (sąrašas l) {printf ('Sąrašo elementas yra ::') Pozicija p = l-> kita, kol (p! = NULL) {printf ('% d ->', p-> e) p = p- > kitas}} int main () {int x, pos, ch, i sąrašas l, l1 l = (struct mazgas *) malloc (sizeof (struktūros mazgas)) l-> ankstesnis = NULL l-> kitas = NULL sąrašas p = l printf ('DVIGUBAI SUSIJUSIŲ SĄRAŠŲ ĮGYVENDINIMAS IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnĮveskite pasirinkimą :: ') scanf ('% d ', & ch) jungiklis (ch) {atvejis 1: p = l printf (' Įveskite įterpiamą elementą :: ') scanf ('% d', & x) printf ('Įveskite elemento vietą ::') scanf ('% d', & pos) (i = 1 i)kitas} Įterpti (x, l, p) pertraukos atvejį 2: p = l printf ('Įveskite elementą, kurį norite ištrinti ::') scanf ('% d', & x) Ištrinti (x, p) 3 pertrauka: ekranas (l) pertrauka}}, kol (sk<4) } Rezultatas
Taigi, kaip matote, operacijų samprata yra gana paprasta. Dvigubai susietame sąraše yra tos pačios operacijos, kaip ir atskirai susietame sąraše C programavimo kalba. Vienintelis skirtumas yra tas, kad yra dar vienas adreso kintamasis, kuris padeda geriau pereiti sąrašą dvigubai susietame sąraše.
Tikiuosi, jūs supratote, kaip atlikti pagrindines operacijas atskirai ir dvigubai susietame C sąraše.
Jei norite išmokti susietų sąrašų „Java“, štai: a .
Jei kyla klausimų, nedvejodami užduokite visus klausimus komentarų skiltyje „Susietasis sąrašas C“, ir mūsų komanda mielai atsakys.