После низова, друга најпопуларнија структура података је Повезана листа. Повезана листа је линеарна структура података, направљена од ланца чворова у којем сваки чвор садржи вредност и показивач на следећи чвор у ланцу. У овом чланку, да видимо како да применимо повезану листу у Ц.
Шта је повезана листа у Ц-у?
Повезана листа је линеарна структура података. Свака повезана листа има два дела, одељак података и одељак адресе који садржи адресу следећег елемента на листи, који се назива чвор.
Величина повезане листе није фиксна и ставке података могу се додати на било које локације на листи. Мана је што да бисмо дошли до чвора, морамо да пређемо пут од првог чвора до чвора који нам је потребан. Повезана листа је попут низа, али за разлику од низа, не складишти се секвенцијално у меморији.
Најпопуларнији типови повезане листе су:
Пример повезане листе
Формат: [подаци, адреса]
Глава -> [3,1000] -> [43,1001] -> [21,1002]
У примеру је број 43 присутан на локацији 1000, а адреса на претходном чвору. Тако је представљена повезана листа.
Основне функције повезане листе
Постоји више функција које се могу применити на повезаној листи у Ц. Покушајмо да их разумемо уз помоћ примера програма.Прво креирамо листу, приказујемо је, убацујемо на било коју локацију, бришемо локацију. Следећи код ће вам показати како да извршите операције на листи.
#инцлуде #инцлуде воид цреате () воид дисплаи () воид инсерт_бегин () воид инсерт_енд () воид инсерт_пос () воид делете_бегин () воид делете_енд () воид делете_пос () струцт ноде {инт инфо струцт ноде * нект} струцт ноде * старт = НУЛЛ инт маин () {инт цхоице вхиле (1) {принтф ('н МЕНУ н') принтф ('н 1.Цреате н') принтф ('н 2.Прикажи н') принтф ('н 3.Инсерт ат почетак н ') принтф (' н 4.Уметни на крају н ') принтф (' н 5.Уметни на наведеном месту н ') принтф (' н 6.Избриши са почетка н ') принтф (' н 7.Избриши с краја н ') принтф (' н 8.Избриши са назначене позиције н ') принтф (' н 9.Излаз н ') принтф (' н ----------------- --------------------- н ') принтф (' Унесите свој избор: т ') прекидач сцанф ('% д ', & цхоице) (избор) {случај 1 : цреате () бреак цасе 2: дисплаи () бреак цасе 3: инсерт_бегин () бреак цасе 4: инсерт_енд () бреак цасе 5: инсерт_пос () бреак цасе 6: делете_бегин () бреак цасе 7: делете_енд () бреак цасе 8: делете_пос () бреак цасе 9: екит (0) бреак дефаулт: принтф ('н Вронг Цхоице: н') бреак}} ретурн 0} вои д цреате () {струцт ноде * темп, * птр темп = (струцт ноде *) маллоц (сизеоф (струцт ноде)) иф (темп == НУЛЛ) {принтф ('нОут оф Мемори Спаце: н') екит (0) } принтф ('нУнесите вредност података за чвор: т') сцанф ('% д', & темп-> инфо) темп-> нект = НУЛЛ иф (старт == НУЛЛ) {старт = темп} елсе {птр = старт вхиле (птр-> нект! = НУЛЛ) {птр = птр-> нект} птр-> нект = темп}} воид дисплаи () {струцт ноде * птр иф (старт == НУЛЛ) {принтф ('нЛист ис емпти: н ') ретурн} елсе {птр = старт принтф (' нЕлементи листе су: н ') вхиле (птр! = НУЛЛ) {принтф ('% дт ', птр-> инфо) птр = птр-> нект}}} воид инсерт_бегин () {струцт ноде * темп темп = (струцт ноде *) маллоц (сизеоф (струцт ноде)) иф (темп == НУЛЛ) {принтф ('нОут оф Мемори Спаце: н') ретурн} принтф ('нУнесите у вредност података за чвор: т ') сцанф ('% д ', & темп-> инфо) темп-> нект = НУЛЛ иф (старт == НУЛЛ) {старт = темп} елсе {темп-> нект = старт старт = темп }} воид инсерт_енд () {струцт ноде * темп, * птр темп = (струцт ноде *) маллоц (сизеоф (струцт ноде)) иф (темп == НУЛЛ) {принтф ('нОут оф Мемори Спаце: н') ретурн} стр ринтф ('нУнесите вредност података за чвор: т') сцанф ('% д', & темп-> инфо) темп-> нект = НУЛЛ иф (старт == НУЛЛ) {старт = темп} елсе {птр = старт вхиле (птр-> нект! = НУЛЛ) {птр = птр-> нект} птр-> нект = темп}} воид инсерт_пос () {струцт ноде * птр, * темп инт и, пос темп = (струцт ноде *) маллоц ( сизеоф (струцт ноде)) иф (темп == НУЛЛ) {принтф ('нОут оф Мемори Спаце: н') ретурн} принтф ('нУнесите положај за уметање новог чвора: т') сцанф ('% д' , & пос) принтф ('нУнесите вредност података чвора: т') сцанф ('% д', & темп-> инфо) темп-> нект = НУЛЛ иф (пос == 0) {темп-> нект = старт старт = темп} елсе {фор (и = 0, птр = стартинект иф (птр == НУЛЛ) {принтф ('нПоситион нот фоунд: [Хандле витх царе] н') ретурн}} темп-> нект = птр-> нект птр -> нект = темп}} воид делете_бегин () {струцт ноде * птр иф (птр == НУЛЛ) {принтф ('нЛист ис Емпти: н') ретурн} елсе {птр = старт старт = старт-> нект принтф (' нИзбрисани елемент је:% дт ', птр-> инфо) фрее (птр)}} воид делете_енд () {струцт ноде * темп, * птр иф (старт == НУЛЛ) {принтф (' нЛист ис Емпти: ') екит (0) } елсе иф (старт-> нект == НУЛЛ) {птр = старт старт = НУЛЛ принтф ('нИзбрисани елемент је:% дт', птр-> инфо) фрее (птр)} елсе {птр = старт вхиле (птр- > нект! = НУЛЛ) {темп = птр птр = птр-> нект} темп-> нект = НУЛЛ принтф ('нИзбрисани елемент је:% дт', птр-> инфо) фрее (птр)}} воид делете_пос () {инт и, пос струцт ноде * темп, * птр иф (старт == НУЛЛ) {принтф ('нТхе Лист ис Емпти: н') екит (0)} елсе {принтф ('нУнесите положај чвора који треба избрисати : т ') сцанф ('% д ', & пос) иф (пос == 0) {птр = старт старт = старт-> нект принтф (' нИзбрисани елемент је:% дт ', птр-> инфо) бесплатно (птр )} елсе {птр = старт фор (и = 0инект иф (птр == НУЛЛ) {принтф ('нПоситион нот Фоунд: н') ретурн}} темп-> нект = птр-> нект принтф ('нИзбрисани елемент је: % дт ', птр-> инфо) бесплатно (птр)}}}Први део овог кода је стварање структуре. Повезана структура листе креира се тако да може да садржи податке и адресу онако како су нам потребни. То је учињено да би компајлеру дао идеју о томе како чвор треба да буде.
струцт ноде {инт инфо струцт ноде * нект}У структури имамо променљиву података која се зове инфо за задржавање података и променљиву показивача која упућује на адресу. Постоје разне операције које се могу извршити на повезаној листи, као што су:
- Креирај()
- приказ()
- инсерт_бегин ()
- инсерт_енд ()
- ] инсерт_пос ()
- делете_бегин ()
- делете_енд ()
- делете_пос ()
Ове функције назива главна функција вођена изборником. У главној функцији користимо улаз од корисника на основу тога коју операцију корисник жели да уради у програму. Улаз се затим шаље у кућиште прекидача на основу корисничког уноса.
На основу онога што је дато, функција ће бити позвана. Даље, имамо различите функције које треба решити. Погледајмо сваку од ових функција.
Направи функцију
Прво, постоји функција креирања за креирање повезане листе. Ово је основни начин креирања повезане листе. Дозволите нам да погледамо код.
воид цреате () {струцт ноде * темп, * птр принтф ('нУнесите вредност података за чвор: т') сцанф ('% д', & темп-> инфо) темп-> нект = НУЛЛ иф (старт == НУЛЛ ) {старт = темп} елсе {птр = старт вхиле (птр-> нект! = НУЛЛ) {птр = птр-> нект} птр-> нект = темп}}Оутпут
Прво се креирају два показивача тог типа чвор, птр и темп . Од корисника узимамо вредност која је потребна за додавање на повезану листу и чувамо је у инфо делу променљиве темп и нулу додељујемо темп следећег који је адресни део. Постоји почетни показивач који држи почетак листе. Затим проверимо почетак листе. Ако је почетак листе нула, тада почетном показивачу додељујемо темп. У супротном, прелазимо до последње тачке у коју су додати подаци.
За ово додељујемо птр почетну вредност и прелазимо до птр-> нект = нулл . Затим додељујемо птр-> следећи адреса темп. На сличан начин постоји и код за уметање на почетку, уметање на крај и уметање на одређено место.
Функција приказа
Ево кода за функцију приказа.
воид дисплаи () {струцт ноде * птр иф (старт == НУЛЛ) {принтф ('нЛист ис емпти: н') ретурн} елсе {птр = старт принтф ('нЕлементи листе су: н') вхиле (птр! = НУЛЛ) {принтф ('% дт', птр-> инфо) птр = птр-> нект}}}Оутпут
У функцији приказа прво проверавамо да ли је листа празна и враћамо се ако је празна. У следећем делу почетну вредност додељујемо птр. Затим покрећемо петљу док птр није нула и исписујемо елемент података за сваки чвор, све док птр није нула, што специфицира крај листе.
Избриши функцију
Ево исечка кода за брисање чвора са повезане листе.
воид делете_пос () {инт и, пос струцт ноде * темп, * птр иф (старт == НУЛЛ) {принтф ('нТхе Лист ис Емпти: н') екит (0)} елсе {принтф ('нУнесите положај чвор за брисање: т ') сцанф ('% д ', & пос) иф (пос == 0) {птр = старт старт = старт-> нект принтф (' нИзбрисани елемент је:% дт ', птр-> инфо ) фрее (птр)} елсе {птр = старт фор (и = 0инект иф (птр == НУЛЛ) {принтф ('нПоситион нот Фоунд: н') ретурн}} темп-> нект = птр-> нект принтф ('нТхе избрисани елемент је:% дт ', птр-> инфо) бесплатно (птр)}}}Оутпут
У процесу брисања прво проверава да ли је листа празна, ако да постоји. Ако није празан, тражи од корисника брисање позиције. Једном када корисник уђе у позицију, проверава да ли је прва позиција, ако да, додељује птр за покретање и померање почетног показивача на следећу локацију и брише птр. Ако је позиција није нула , затим покреће фор петљу од 0 па све до позиције коју је корисник унео и сачувао у поз променљива. Постоји изјава иф да би се одлучило да ли унета позиција није присутна. Ако птр је једнако нулл , онда није присутан.
Ми доделити птр темп у петљи фор, а птр затим прелази на следећи део. После овога када се пронађе положај. Правимо променљиву темп да задржи вредност од птр-> следећи прескачући тако птр. Тада се птр брише. Слично томе, то се може учинити за брисање првог и последњег елемента.
Двоструко повезана листа
Назива се двоструко повезана листа јер постоје две показивачи , једна тачка до следећег чвора и друге тачке до претходног чвора. Операције изведене у двоструко повезаним сличне су операцијама појединачно повезане листе. Ево кода за основне операције.
#инцлуде #инцлуде струцт Ноде типедеф струцт Ноде * ПтрТоНоде типедеф ПтрТоНоде Лист типедеф ПтрТоНоде Поситион струцт Ноде {инт е Поситион превиоус Поситион нект} воид Инсерт (инт к, Лист л, Поситион п) {Поситион ТмпЦелл ТмпЦелл = (струцт Ноде *) маллоц (сизеоф (струцт Ноде)) иф (ТмпЦелл == НУЛЛ) принтф ('Мемори оут оф спацен') елсе {ТмпЦелл-> е = к ТмпЦелл-> превиоус = п ТмпЦелл-> нект = п-> нект п-> нект = ТмпЦелл}} воид Делете (инт к, Лист л) {Поситион п, п1, п2 п = Финд (к, л) иф (п! = НУЛЛ) {п1 = п -> превиоус п2 = п -> нект п1 - > нект = п -> нект иф (п2! = НУЛЛ) // ако чвор није последњи чвор п2 -> превиоус = п -> превиоус} елсе принтф ('Елемент не постоји !!! н')} воид Приказ (Листа л) {принтф ('Елемент листе су ::') Положај п = л-> следећи док (п! = НУЛЛ) {принтф ('% д ->', п-> е) п = п- > нект}} инт маин () {инт к, пос, цх, и Лист л, л1 л = (струцт Ноде *) маллоц (сизеоф (струцт Ноде)) л-> превиоус = НУЛЛ л-> нект = НУЛЛ Лист п = л принтф ('ПРИМЕНА ДУПЛО ПОВЕЗАНЕ ЛИСТЕ Л ИСТ АДТнн ') до {принтф (' нн1. ЦРЕАТЕн 2. ДЕЛЕТЕн 3. ДИСПЛАИн 4. КУИТннЕнтер тхе цхоице :: ') сцанф ('% д ', & цх) свитцх (цх) {цасе 1: п = л принтф (' Ентер тхе елемент то бе инсерт :: ') сцанф ('% д', & к) принтф ('Унесите положај елемента ::') сцанф ('% д', & пос) за (и = 1 иследеће} Уметни (к, л, п) случај прекида 2: п = л принтф ('Унеси елемент који треба избрисати ::') сцанф ('% д', & к) Избриши (к, п) случај прелома 3: Приказ (л) прекид}} док (гл<4) } Оутпут
Као што видите, концепт операција је прилично једноставан. Двоструко повезана листа има исте операције као и појединачно повезана листа у програмском језику Ц. Једина разлика је у томе што постоји још једна променљива адресе која помаже у бољем прелажењу листе у двоструко повезаној листи.
Надам се да сте разумели како се изводе основне операције на појединачно и двоструко повезаном списку у Ц.
јава шта је вектор
Ако желите да научите повезану листу на Јави, ево а .
Ако наиђете на неко питање, слободно поставите сва своја питања у одељку за коментаре „Повезане листе у Ц“ и наш тим ће вам радо одговорити.