После массивов второй по популярности структурой данных является связанный список. Связанный список - это линейная структура данных, состоящая из цепочки узлов, в которой каждый узел содержит значение и указатель на следующий узел в цепочке. В этой статье давайте посмотрим, как реализовать связанный список на C.
Что такое связанный список в C?
Связанный список - это линейная структура данных. Каждый связанный список состоит из двух частей: раздела данных и раздела адреса, который содержит адрес следующего элемента в списке, который называется узлом.
Размер связанного списка не фиксирован, и элементы данных можно добавлять в любые места в списке. Недостатком является то, что для того, чтобы добраться до узла, мы должны пройти весь путь от первого узла до нужного нам узла. Связанный список похож на массив, но, в отличие от массива, он не сохраняется в памяти последовательно.
Наиболее популярные типы связного списка:
Пример связанного списка
Формат: [данные, адрес]
Глава -> [3,1000] -> [43,1001] -> [21,1002]
как установить путь к классам в java с помощью командной строки
В примере номер 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) switch (choice) {case 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') exit (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 пуст: n ') return} else {ptr = start printf (' n Элементы списка: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEnter the значение данных для узла: 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-> 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 ('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: [Обработка с осторожностью] 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-> info) free (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- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nУдаленный элемент:% dt', ptr-> info) free (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) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nУдаленный элемент: % dt ', ptr-> info) бесплатно (ptr)}}}Первая часть этого кода - создание структуры. Структура связанного списка создается так, чтобы в ней можно было хранить данные и адрес по мере необходимости. Это сделано, чтобы дать компилятору представление о том, каким должен быть узел.
struct node {int info struct node * следующий}В структуре у нас есть переменная данных с именем info для хранения данных и переменная-указатель, указывающая на адрес. В связанном списке можно выполнять различные операции, например:
- Создайте()
- дисплей ()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Эти функции вызываются главной функцией, управляемой из меню. В функции main мы принимаем ввод от пользователя в зависимости от того, какую операцию пользователь хочет выполнить в программе. Затем ввод отправляется в корпус коммутатора и основан на вводе пользователя.
В зависимости от того, какой ввод предоставлен, будет вызвана функция. Далее у нас есть разные функции, которые нужно решить. Давайте посмотрим на каждую из этих функций.
Создать функцию
Во-первых, есть функция создания для создания связанного списка. Это основной способ создания связного списка. Давайте посмотрим на код.
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}}Вывод
что такое процедура в sql
Сначала создаются два указателя типа узел, ptr и temp . Мы берем значение, которое необходимо добавить в связанный список от пользователя, и сохраняем его в информационной части переменной temp и присваиваем temp of next, которая является частью адреса, равным нулю. Начальный указатель удерживает начало списка. Затем мы проверяем начало списка. Если начало списка равно нулю, мы присваиваем временному указателю значение temp. В противном случае мы переходим к последней точке, куда были добавлены данные.
Для этого мы назначаем ptr начальное значение и перемещаемся до ptr-> next = null . Затем мы назначаем 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-> info) ptr = ptr-> next}}}Вывод
В функции отображения мы сначала проверяем, пуст ли список, и возвращаем, если он пуст. В следующей части мы присваиваем начальное значение 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-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe удаленный элемент:% dt ', ptr-> info) free (ptr)}}}Вывод
В процессе удаления он сначала проверяет, пуст ли список, если да, то он существует. Если он не пустой, он запрашивает у пользователя удаление позиции. Как только пользователь входит в позицию, он проверяет, является ли это первой позицией, если да, он назначает ptr для запуска и перемещает указатель начала в следующее место и удаляет ptr. Если позиция не нулевая , затем запускается цикл for от 0 до позиции, введенной пользователем и сохраненной в позиция переменная. Существует оператор if, чтобы определить, отсутствует ли введенная позиция. Если ptr равно нулю , тогда его нет.
Мы назначить ptr на temp в цикле for, а затем ptr переходит к следующей части. После этого, когда позиция будет найдена. Мы делаем временную переменную для хранения значения 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) {Позиция p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> предыдущий p2 = p -> следующий p1 - > next = p -> next if (p2! = NULL) // если узел не является последним узлом p2 -> previous = p -> previous} else printf ('Элемент не существует !!! n')} void Display (Список l) {printf ('Элемент списка ::') Позиция p = l-> next while (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('ДВУСТОРОННЕ СВЯЗАННАЯ РЕАЛИЗАЦИЯ L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Введите выбор :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Введите элемент для вставки :: ') scanf ('% d', & x) printf ('Введите позицию элемента ::') scanf ('% d', & pos) for (i = 1 inext} Insert (x, l, p) break case 2: p = l printf ('Введите удаляемый элемент ::') scanf ('% d', & x) Delete (x, p) break case 3: Показать (l) break}} while (ch<4) } Вывод
способы создать одноэлементный класс в java
Итак, как видите, концепция операций довольно проста. Двусвязный список имеет те же операции, что и односвязный список в языке программирования C. Единственное отличие состоит в том, что есть еще одна адресная переменная, которая помогает лучше перемещаться по списку в двусвязном списке.
Надеюсь, вы поняли, как выполнять базовые операции с односвязным и двусвязным списком в C.
Если вы хотите изучить связанный список на Java, вот .
Если у вас возникнут какие-либо вопросы, не стесняйтесь задавать все свои вопросы в разделе комментариев «Связанного списка в C», и наша команда будет рада ответить.