След масивите втората по популярност структура на данните е Linked List. Свързаният списък е линейна структура от данни, направена от верига от възли, в която всеки възел съдържа стойност и указател към следващия възел във веригата. В тази статия нека да видим как да приложим свързан списък в C.
Какво е свързан списък в C?
Свързаният списък е линейна структура от данни. Всеки свързан списък има две части, секцията с данни и адресната секция, която съдържа адреса на следващия елемент в списъка, който се нарича възел.
Размерът на свързания списък не е фиксиран и елементи от данни могат да се добавят на всяко място в списъка. Недостатъкът е, че за да стигнем до възел, трябва да преминем през целия път от първия възел до възела, който ни е необходим. Свързаният списък е като масив, но за разлика от масива, той не се съхранява последователно в паметта.
Най-популярните видове свързан списък са:
методът system.exit ще прекрати приложението.
Пример за свързан списък
Формат: [данни, адрес]
Глава -> [3,1000] -> [43,1001] -> [21,1002]
В примера числото 43 присъства в местоположение 1000, а адресът е в предишния възел. Ето как е представен свързан списък.
Основни функции на свързан списък
Има множество функции, които могат да бъдат внедрени в свързания списък в C. Нека се опитаме да ги разберем с помощта на примерна програма.Първо, ние създаваме списък, показваме го, вмъкваме на всяко място, изтриваме местоположение. Следващият код ще ви покаже как да извършвате операции от списъка.
#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. Insert at началото n ') printf (' n 4.Вмъкване в края n ') printf (' n 5.Инсталиране на определена позиция n ') printf (' n 6. Изтриване от началото n ') printf (' n 7.Изтриване от края n ') printf (' n 8. Изтриване от определена позиция n ') printf (' n 9. Изход n ') printf (' n ----------------- --------------------- n ') printf (' Въведете своя избор: t ') scanf ('% d ', & choice) превключвател (избор) {случай 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') изход (0) } printf ('nВъведете стойността на данните за възела: 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 display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n ') return} else {ptr = start printf (' nЕлементите на списъка са: n '), докато (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> следващ}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nВлезте в стойност на данните за възела: 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 ('nOut of Memory Space: n') return} стр rintf ('nВъведете стойността на данните за възела: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> следващ! = NULL) {ptr = ptr-> следващ} ptr-> следващ = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nВъведете позицията за новия възел, който ще бъде вмъкнат: t') scanf ('% d' , & pos) printf ('nВъведете стойността на данните на възела: 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 ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' n Изтритият елемент е:% dt ', ptr-> информация) безплатно (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nИзтриваният елемент е:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > следващ! = NULL) {temp = ptr ptr = ptr-> следващ} temp-> следващ = NULL printf ('nИзтриваният елемент е:% dt', ptr-> информация) безплатно (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nВъведете позицията на възела, който трябва да бъде изтрит : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nИзтриваният елемент е:% dt ', ptr-> info) безплатно (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nИзтриваният елемент е: % dt ', ptr-> информация) безплатно (ptr)}}}Първата част на този код е създаване на структура. Създадена е свързана структура на списъка, така че да може да съхранява данните и адреса, както ни е необходимо. Това се прави, за да даде на компилатора представа как трябва да бъде възелът.
struct node {int info struct node * следващ}В структурата имаме променлива за данни, наречена info, която да съхранява данни, и променлива за указател, която да сочи към адреса. Има различни операции, които могат да бъдат извършени в свързан списък, като:
- създаване ()
- дисплей ()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Тези функции се извикват от основната функция, управлявана от менюто. В основната функция ние вземаме данни от потребителя въз основа на това, каква операция потребителят иска да направи в програмата. След това входът се изпраща към корпуса на превключвателя и въз основа на потребителския вход.
Въз основа на предоставения вход функцията ще бъде извикана. След това имаме различни функции, които трябва да бъдат решени. Нека да разгледаме всяка от тези функции.
Създаване на функция
Първо, има функция за създаване, за да се създаде свързаният списък. Това е основният начин за създаване на свързания списък. Позволяваме ни да разгледаме кода.
void create () {struct node * temp, * ptr printf ('nВъведете стойността на данните за възела: 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}}Изход
Първо се създават два указателя от типа node, ptr и temp . Вземаме от потребителя стойността, която е необходима за добавяне в свързания списък, и я съхраняваме в информационната част на временната променлива и присвояваме temp на следващата, която е адресната част, за нула. Има начален указател, който държи началото на списъка. След това проверяваме за началото на списъка. Ако началото на списъка е нула, тогава присвояваме temp на началния указател. В противен случай преминаваме към последната точка, в която са добавени данните.
За това присвояваме ptr началната стойност и преместваме до ptr-> следващ = нула . След това възлагаме ptr-> следващ адресът на темп. По подобен начин има код, даден за вмъкване в началото, вмъкване в края и вмъкване на определено място.
Функция на дисплея
Ето кода за функцията за показване.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nЕлементите на списъка са: n') while (ptr! = NULL) {printf ('% dt', ptr-> информация) ptr = ptr-> следващ}}}Изход
Във функцията за показване първо проверяваме дали списъкът е празен и се връщаме, ако е празен. В следващата част присвояваме началната стойност на ptr. След това изпълняваме цикъл, докато ptr е нула и отпечатваме елемента с данни за всеки възел, докато ptr е нула, което указва края на списъка.
Функция за изтриване
Ето фрагмента от код за изтриване на възел от свързания списък.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nВъведете позицията на възел за изтриване: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nИзтриваният елемент е:% dt ', ptr-> информация ) безплатно (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe изтритият елемент е:% dt ', ptr-> информация) безплатно (ptr)}}}Изход
В процеса на изтриване първо проверява дали списъкът е празен, ако да, съществува. Ако не е празно, той иска от потребителя позицията да бъде изтрита. След като потребителят влезе в позицията, той проверява дали това е първата позиция, ако да, той определя ptr за стартиране и преместване на стартовия указател към следващото място и изтрива ptr. Ако позиция не е нула , след това изпълнява цикъл for от 0 чак до позицията, въведена от потребителя и съхранена в поз променлива. Има изявление if, за да се реши дали въведената позиция не е налице. Ако ptr е равно на null , тогава не е налице.
Ние задайте ptr на temp в цикъла for и след това ptr преминава към следващата част. След това, когато позицията бъде намерена. Правим променливата temp, за да задържим стойността на ptr-> следващ като по този начин прескача ptr. След това ptr се изтрива. По същия начин може да се направи за първо и последно изтриване на елемент.
Двойно свързан списък
Той се нарича двойно свързан списък, защото има два указатели , една точка към следващия възел и други точки към предишния възел. Операциите, извършени в двойно свързани, са подобни на тези в единично свързан списък. Ето кода за основните операции.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> предишен p2 = p -> следващ p1 - > следващ = p -> следващ if (p2! = NULL) // ако възелът не е последният възел p2 -> предишен = p -> предишен} else printf ('Елемент не съществува !!! n')} void Показване (Списък l) {printf ('Елементът на списъка са ::') Позиция p = l-> следваща докато (p! = NULL) {printf ('% d ->', p-> e) p = p- > следващ}} int main () {int x, pos, ch, i Списък l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> предишен = NULL l-> следващ = NULL Списък p = l printf ('ИЗПЪЛНЕНИЕ НА ДВОЙНО СВЪРЗАН СПИСЪК НА L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEnter the choice :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('Въведете позицията на елемента ::') scanf ('% d', & pos) за (i = 1 iследваща} Вмъкване (x, l, p) случай на прекъсване 2: p = l printf ('Въведете елемента, който ще се изтрие ::') scanf ('% d', & x) Изтриване (x, p) случай на прекъсване 3: Показване (l) почивка}} докато (гл<4) } Изход
Както виждате, понятието операции е съвсем просто. Двойно свързаният списък има същите операции като този на единично свързан списък в програмен език C. Единствената разлика е, че има и друга променлива на адреса, която помага да се премине по-добре по списъка в двойно свързан списък.
Надявам се, че сте разбрали как да извършвате основни операции в единично и двойно свързан списък в C.
Ако искате да научите свързан списък в Java, ето a .
Ако попаднете на някакви въпроси, не се колебайте да зададете всичките си въпроси в раздела за коментари на „Свързан списък в C“ и нашият екип ще се радва да отговори.