Содержание
- Введение
- Массивы и связные списки
- Создание связного списка на языке Си
- Создание связного списка в Python
- Определение длины списка
- Добавление элемента в начало списка
- Добавление элементов в конец списка
- Вставка элемента на определенную позицию в списке
- Удаление головного элемента
- Удаление элемента из списка
- Вставка элемента в отсортированный список
- Удаление повторяющихся значений
- Копирование списков
- Тестирование производительности
- Заключение
- Ресурсы для скачивания
- Похожие темы
- Комментарии
Работа со структурами данных в языках Си и Python
Часть 2. Связные списки
Серия контента:
Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python
Этот контент является частью серии:Работа со структурами данных в языках Си и Python
Следите за выходом новых статей этой серии.
В этой статье разбираются практические аспекты работы со связными списками - создание списка, добавление и удаление элементов, получение длины списка, сортировка списка и другие действия. Также в статье проводится тестирование производительности Python.
Массивы и связные списки
Связные списки используются, когда требуется структура данных, размер которой заранее неизвестен. В такие списки можно добавлять и удалять элементы уже после создания самого списка. Однако такой список требует дополнительных усилий для поддержания целостности при динамических операциях, так как при удалении элемента из списка обрывается связь между элементами, находящимися до и после него, и эти элементы необходимо снова связать между собой.
Списки широко используются в реальных проектах - операционных системах, базах данных, но для работы с ними требуется знать, как устроена арифметика указателей. В листинге 1 представлен массив из 100 элементов и инициализируются его первые 3 значения.
Листинг 1. Инициализация массива
int my_array[100]; my_array[0]=1; my_array[1]=20; my_array[2]=100;
Физически все 100 элементов располагаются в памяти последовательно, и индекс элемента - это смещение в блоке памяти от его начала, поэтому извлечение элемента по индексу выполняется крайне быстро. Это и есть адресная арифметика, но так как память для стандартного массива выделяется на этапе компиляции, то и модифицировать его впоследствии уже нельзя.
Для выделения памяти для связного списка используется иной механизм, когда память выделяется динамически, во время работы программы. Данный тип памяти называется «куча» (heap) и добавляемые элементы физически могут располагаться в такой куче без всякого упорядочивания.
Создание связного списка на языке Си
Элемент (узел) - это область памяти, в которой хранится ячейка связного списка. Узел односвязного списка состоит из 2-х полей: в первом хранятся данные (это поле также называется ключом), а во втором - указатель на следующий узел. Существует специальный указатель head, указывающий на первый узел списка. Указатель head – это отдельная переменная, не принадлежащая списку. Последний узел в списке указывает на NULL, и для него тоже создается специальная переменная - указатель tail. Если первый элемент указывает на NULL, то это будет пустой список. В листинге 2 приведена структура для определения элемента списка:
Листинг 2. Структура для элемента списка
struct node { int data; struct node* next; };
Указатель next имеет тот же тип, что и сам элемент, и указывает на следующий элемент списка. В листинге 3 приведен пример создания списка из трех элементов.
Листинг 3. Создание списка из трех элементов
// объявить три указателя на элементы списка // указатель head ведет на первый элемент списка struct node* head = NULL; struct node* second = NULL; struct node* third = NULL; // выделить память под элементы // метод sizeof вычисляет размер элемента // метод malloc выделяет требуемое количество памяти // установить указатели на выделенные фрагменты памяти head = malloc(sizeof(struct node)); second = malloc(sizeof(struct node)); third = malloc(sizeof(struct node)); // инициализировать элементы списка и связать их между собой head->data = 1; head->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL;
Создание связного списка в Python
В Python существует стандартная реализация списка, но ее не рекомендуется использовать из-за проблем с производительностью при выполнении динамических операций, о чем говорилось в прошлой статье. В листинге 4 представлен класс Node для определения элемента списка.
Листинг 4. Объявление элемента списка в Python
class Node: def __init__(self, value = None, next = None): self.value = value self.next = next
Для определения связного списка потребуется еще один класс – LinkedList, в конструкторе которого будут определяться первый и последний элементы списка и его длина. Также в классе будут использоваться встроенный метод str для распечатки содержимого списка и метод clear для очистки списка.
Листинг 5. Исходный код класса Linked List
import copy import random class LinkedList: def __init__(self): self.first = None self.last = None self.length = 0 def __str__(self): if self.first != None: current = self.first out = 'LinkedList [\n' +str(current.value) +'\n' while current.next != None: current = current.next out += str(current.value) + '\n' return out + ']' return 'LinkedList []' def clear(self): self.__init__() //создание связного списка из 3-х элементов L = LinkedList() L.add(1) L.add(2) L.add(3)
Определение длины списка
Чтобы определить размер связного списка, необходимо пройти по списку и посчитать количество узлов. В листинге 6 приведена функция для подсчета числа узлов.
Листинг 6. Функция на языке Си для определения длины списка
int Length(struct node* head) { struct node* current = head; int count = 0; while (current != NULL) { count++; current = current->next; } return count; }
В этой функции создается дополнительный указатель current, с помощью которого выполняется ИТЕРАЦИЯ связного списка:
current = current->next;
При этой операции со списком ничего не происходит, но указателю НАЗНАЧАЕТСЯ новое значение. Если вызвать эту функцию для пустого списка, у которого вершина равна NULL, то функция вернет ноль. Для определения длины списка в Python используется функция Len (см. листинг 7), которая вначале проверяет, не является ли список пустым, а затем выполняет итерацию по элементам списка.
Листинг 7. Функция на языке Python для определения длины списка
def Len(self): self.length =0 if self.first != None: self.length +=1 current = self.first while current.next != None: current = current.next self.length +=1 return self.length
Добавление элемента в начало списка
В листинге 8 приведена функция Push для добавления элементов в начало списка в обратном порядке.
Листинг 8. Функция для добавления элементов в начало списка
void Push(struct node** headRef, int data) { struct node* newNode = malloc(sizeof(struct node)); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } // пример использования этой функции struct node* head = NULL; // создание первого элемента Push(&head, 1); Push(&head, 2); Push(&head, 3);
Символ & - это указание компилятору, что параметр передается по ссылке, т.е. все изменения, которые будут сделаны с этим параметром внутри функции, останутся актуальными для переданного объекта и после выхода из функции. При передаче параметров по ссылке нужно следовать трем правилам:
- в определении функции для указателей нужно использовать двойной указатель **;
- при вызове функции перед ссылочным параметром нужно поставить &;
- в самой функции к ссылочному параметру обращаться через указатель *.
Листинг 9. Реализация функции Push на языке Python
def Push(self, x): if self.first == None: self.first = Node(x,None) self.last = self.first else: self.first = Node(x,self.first)
В Python-реализации учитываются два варианта: в первом случае список пуст, а во втором создается новый узел, в конструктор которого в качестве второго параметра передается головной элемент списка.
Добавление элементов в конец списка
В листинге 10 представлен пример добавления элементов в конец списка.
Листинг 10. Си – добавление элемента в конец списка
struct node* AppendNode(struct node** headRef, int num) { struct node* current = *headRef; struct node* newNode; newNode = malloc(sizeof(struct node)); newNode->data = num; newNode->next = NULL; // если список пуст if (current == NULL) { *headRef = newNode; } else { // иначе while (current->next != NULL) { current = current->next; } current->next = newNode; } }
В представленном коде выполняется итерация по списку для поиска последнего элемента, а затем его указатель next устанавливается на добавляемый элемент.
Листинг 11. Python - добавление элемента в конец списка
def add(self, x): if self.first == None: self.first = Node(x, None) self.last = self.first elif self.last == self.first: self.last = Node(x, None) self.first.next = self.last else: current = Node(x, None) self.last.next = current self.last = current
Вставка элемента на определенную позицию в списке
Для вставки элемента в список необходимо передать указатель на головной элемент, индекс позиции, куда будет вставлен элемент, и, собственно, сам элемент. Если индекс равен нулю, то вызывается функция Push, в противном случае выполняется итерация, а затем снова происходит вызов Push.
Листинг 12. Си - вставка элемента в список
void InsertNth(struct node** headRef, int index, int data) { if (index == 0) Push(headRef, data); else { struct node* current = *headRef; int i; for (i=0; i<index-1; i++) { current = current->next; } Push(&(current->next), data); } }
В Python необходимо сначала проверить, что список не пуст, а затем, что вставка не происходит на нулевую позицию. Если оба условия не выполняются, то происходит итерация по списку до нужной позиции и добавление элемента:
Листинг 13. Python – вставка элемента в список
def InsertNth(self,i,x): if (self.first == None): self.first = Node(x,self.first) self.last = self.first.next return if i == 0: self.first = Node(x,self.first) return curr=self.first count = 0 while curr != None: if count == i-1: curr.next = Node(x,curr.next) if curr.next.next == None: self.last = curr.next break curr = curr.next
Удаление головного элемента
Функция Pop удаляет из списка головной узел, вместе с функцией Push она реализует функциональность стека, отцепляя головной элемент от списка и освобождая память. Функция принимает на вход двойной указатель на головной элемент, а возвращает значение удаленного элемента.
Листинг 14. Функция Pop – реализация на языке Си
int Pop(struct node ** head) { struct node * temp = *head; int data=temp->data; *head = temp->next; free(temp); return data; }
Для реализации на Python потребуется создать временную локальную переменную для хранения головного элемента. Если список не пустой, то головным узлом становится элемент, следующий за узлом, сохраненным во временной переменной.
Листинг 15. Функция Pop – реализация на Python
def Pop(self): oldhead=self.first if oldhead==None: return None self.first=oldhead.next if self.first==None: self.last=None return oldhead.value
Удаление элемента из списка
В листинге 16 приведена реализация функции для удаления элемента из списка на языке Си.
Листинг 16. Си - удаление элемента из списка
int Del(struct node ** head,int index) { int data = (*head)->data; if(index==0) Pop(head); else { int i; struct node * current = *head; for(i=0;i<index-1;i++) current=current->next; Pop(&(current->next)); } return data; };
В реализации для Python потребуется проверить список на пустоту и объявить две локальных переменных: первая будет хранить текущий элемент, а вторая - предыдущий. Потом выполняется итерация по списку для поиска удаляемого элемента и проверка того, не является ли он последним в списке. Если удаляемый элемент является последним, то предыдущий узел становится последним, в противном случае предыдущий узел связывается со следующим узлом вместо текущего.
Листинг 17. Python - удаление элемента из списка
def Del(self,i): if (self.first == None): return old = curr = self.first count = 0 if i == 0: self.first = self.first.next return while curr != None: if count == i: if curr.next == self.last: self.last = curr break else: old.next = curr.next break old = curr curr = curr.next count += 1
Вставка элемента в отсортированный список
В листинге 18 представлена функция для вставки элемента в отсортированный список. Как обычно, сначала выполняется проверка, что список не пустой, а затем итерация в поисках ближайшего элемента, значение которого меньше, чем у добавляемого.
Листинг 18. Си - вставка элемента в отсортированный список
void SortedInsert(struct node** headRef, struct node* newNode) { if (*headRef == NULL || (*headRef)->data >= newNode->data) { newNode->next = *headRef; *headRef = newNode; } else { struct node* current = *headRef; while (current->next!=NULL && current->next->data < newNode->data) { current = current->next; } newNode->next = current->next; current->next = newNode; } }
В реализации на языке Python выполняется проверка списка на пустоту, а затем выполняется итерация с помощью двух временных переменных, как и в листинге 18.
Листинг 19. Python – вставка элемента в отсортированный список
def SortedInsert(self,x): if (self.first == None): self.first = Node(x,self.last) return if self.first.value > x: self.first = Node(x,self.first) return old = curr = self.first while curr != None: if curr.value > x: curr = Node(x,curr) old.next = curr return old = curr curr = curr.next curr = Node(x,None) old.next = curr
Удаление повторяющихся значений
Данная функция должна применяться к уже отсортированному списку. В качестве параметра в неё передается головной узел списка, и если в ходе итерации текущий элемент оказывается равным следующему за ним, то текущий элемент удаляется.
Листинг 20. Си – удаление повторяющихся значений
void RemoveDuplicates(struct node* head) { struct node* current = head; if (current == NULL) return; while(current->next!=NULL) { if (current->data == current->next->data) { struct node* nextNext = current->next->next; free(current->next); current->next = nextNext; } else { current = current->next; } } }
В версии на языке Python добавляется флаг, отмечающий наличие повторяющегося элемента. Этот флаг устанавливается при удалении повторяющегося элемента, и итерация прекращается, в противном случае итерация продолжается.
Листинг 21. Python – удаление повторяющихся значений
def RemoveDuplicates(self): if (self.first == None): return old = curr = self.first while curr != None: _del = 0 if curr.next != None: if curr.value == curr.next.value: curr.next = curr.next.next _del = 1 if _del == 0: curr = curr.next
Копирование списков
В листинге 22 показана функция для копирования списков. В ней используется три указателя: на первый элемент оригинального списка и на первый и последний элементы скопированного списка.
Листинг 22. Си – копирование списков
struct node* CopyList(struct node* head) { struct node* current = head; //первый элемент оригинального списка struct node* newList = NULL; //первый элемент нового списка struct node* tail = NULL; //последний элемент нового списка while (current != NULL) { if (newList == NULL) //создается первый элемент нового списка { newList = malloc(sizeof(struct node)); newList->data = current->data; newList->next = NULL; tail = newList; } else { tail->next = malloc(sizeof(struct node)); tail = tail->next; tail->data = current->data; tail->next = NULL; } current = current->next; } return(newList); }
В листинге 23 приведена реализация этой же функциональности, но на основе рекурсии.
Листинг 23. Си - копирование списков на основе рекурсии
struct node* CopyList(struct node* head) { struct node* current = head; if (head == NULL) return NULL; else { struct node* newList = malloc(sizeof(struct node)); newList->data = current->data; newList->next = CopyList(current->next); return(newList); } }
В Python для копирования списков можно использовать стандартный модуль copy, как показано ниже.
import copy L2 = copy.deepcopy(L) // создание копии списка L
Тестирование производительности
Для тестирования производительности связных списков использовался список, состоящий из 2000 элементов, при этом значение элемента могло быть от 0 до 100, и элементы вставлялись в отсортированном порядке.
В ходе тестирования было выяснено, что реализация одного и того же алгоритма для вставки элементов в отсортированный связный список ведет себя по-разному в зависимости от языка и размера списка. Производительность Python-реализации начинает снижаться, когда в списке накапливается более 2-х тысяч элементов. Анализ результатов теста показывает, что основные потери процессорного времени происходят во время итерации.
Исходный код тестов на языках Си и Python можно найти в архиве performance_benchmark.zip, прикрепленном к статье. Реализация на языке Си работает гораздо быстрее, и ее производительность начинает снижаться, когда размер списка становится значительно больше 2-х тысяч элементов. Версию на языке Python не спасает даже оптимизация кода за счет сокращения вызовов функции SortedInser, так как из-за динамического создания объектов в Python, начиная с определенного момента, возникают проблемы при итерации.
Заключение
Как было показано в этой статье, связные списки предоставляют богатый набор функций для добавления и удаления элементов, сортировки, копирования и других операций. Поэтому связные списки являются «краеугольным камнем» и первой ступенью для изучения других структур данных связного типа.
Ресурсы для скачивания
Похожие темы
- Работа со структурами данных в языках Си и Python. Часть 1.
- Работа со структурами данных в языках Си и Python. Часть 2.
Комментарии
Войдите или зарегистрируйтесь для того чтобы оставлять комментарии или подписаться на них.