Понятие односвязного линейного списка и его реализация на языке C

Понятие односвязного линейного списка и его реализация на языке C (C, Список)До сих пор мы с Вами рассматривали структуры данных, отображая их на массив. За это время мы успели изучить стек, очередь, очередь с приоритетами и таблицу. Однако эти структуры данных можно реализовывать и без массива, а например с использованием так называемых связных списков.

Понятие списка

Списку можно дать несколько определений. Здесь представлены некоторые из них.

Связный список  конечная последовательность однотипных элементов, которые называются узлами списка.

Связный список  последовательность, элементами которой являются записи (структуры), связанные друг с другом с помощью указателей, которые хранятся в этих же элементах.

Связный список  структура данных, определяемая следующим образом:

  1. Пустой список является списком
  2. Структура вида [Голова | Хвост] является списком, если голова — первый элемент списка, а хвост — список, состоящий из оставшихся элементов исходного списка

Обращаю Ваше внимание, что последнее определение называется рекурсивным определением списка.

Существует несколько видов списка: односвязный линейный список (ОЛС), последовательный линейный список (ПЛС), двусвязный линейный список (ДЛС) и другие. Однако в данной статье будет рассматриваться именно ОЛС.

Чтобы Вам стало более понятно, что такое список, рассмотрим следующую картинку.#image.jpg

Каждый прямоугольник на этом рисунке — элемент списка. Как и было сказано выше, в каждом элементе есть поле с данными и поле с указателем на следующий элемент. Следует отметить, диагональная черта у последнего прямоугольника — признак конца списка.

Вообще говоря, чаще всего списки используются с фиктивным элементом, который является первым в последовательности. Использование фиктивного элемента позволяет упростить реализацию некоторых операций. Добавлю, что не стоит пугаться таких элементов, это всего-навсего элемент списка, поле данных которого не используется.

Учитывая вышесказанное, список теперь будет выглядеть следующим образом.Понятие односвязного линейного списка и его реализация на языке C (C, Список)

Операции над списком

Над линейный списком определены следующие операции:

  1. Инициализация
  2. Включение элемента
  3. Исключение элемента
  4. Переход в начало списка
  5. Переход в конец списка
  6. Переход к следующему элементу
  7. Уничтожение списка

Реализация односвязного линейного списка

При реализации ОЛС в статической памяти располагают дескриптор, состоящий из двух полей:

  1. Указатель на фиктивный элемент
  2. Указатель на текущий элемент
/*Базовый тип списка*/
typedef int listOneBaseType;
/*Указатель на элемент списка*/
typedef struct element *ptrEl;
/*Структура элемента списка*/
struct element {
listOneBaseType data;					// Данные
ptrEl link;								// Указатель на следующий элемент списка
};
/*Дескриптор списка*/
typedef struct {
ptrEl start;							// Указатель на фиктивный элемент
ptrEl ptr;								// Указатель на рабочий элемент
}

Хочу обратить ваше внимание на тот факт, что в любой момент времени нам известен лишь дескриптор и, соответственно, информация в нем, поэтому все операции над списком выполняются непосредственно через него.

P.S. При использовании фиктивного элемента, все операции нужно выполнять после того элемента, на который указывает ptr.

Инициализация списка

Инициализация происходит в три шага:

  1. Выделение памяти для фиктивного элемента
  2. В дескрипторе указателю start присвоить блок с только что выделенной памятью
  3. Указателю ptr присвоить start.

Поясню, что здесь, и зачем. При инициализации происходит создание списка, но не заполнение его элементами. Создание списка подразумевает создание фиктивного элемента. Так как его поле данных не используется, то список остается по-прежнему пуст. Когда память выделена, остается лишь правильно присвоить ссылки указателям.Понятие односвязного линейного списка и его реализация на языке C (C, Список)Код инициализации таков:

/*Инициализация списка. L -- дескриптор*/
void initListOne(ListOne *L) {
// Выделение пямяти под фиктивный элемент
L->start = (ptrEl) malloc(sizeof(element));
/*Если памяти не хватило*/
if (!L->start) {
listOneError = listOneNoMem;
return;
}
/*Иначе*/
// ptr указывает на то, что и start -- на фиктивный
L->ptr = L->start;
// Нет ссылки на следующий элемент
L->ptr->link = NULL;
}

Включение элемента

Включение элемента порой сложно понять, поэтому постараюсь как можно доходчиво объяснить. Рассмотрим список из нескольких элементов.#image.jpg

Так как ptr указывает на фиктивный элемент, то новый элемент нужно вставить после него, но перед элементом со значением 5. Прежде чем вставить, нужно выделить память под новый элемент и занести информацию в него. Допустим, мы вставляем элемент с данными — 100.Понятие односвязного линейного списка и его реализация на языке C (C, Список)Теперь нужно вставить новый элемент между двумя элементами списка, то есть изменить ссылки, находящиеся в полях ptr.#image.jpgТеперь рассмотрим код операции включения.

/*Включение элемента в список L -- дескриптор. E -- данные*/
void putListOne(ListOne *L, listOneBaseType E) {
// Выделение памяти под новый элемент
ptrEl temp = (ptrEl) malloc(sizeof(element));
/*Если памяти недостаточно*/
if (!temp) {
listOneError = listOneNoMem;
return;
}
/*Иначе перемычка*/
// Внесение информции в новый элемент
temp->data = E;
// Новый элемент указывает на следующий
temp->link = L->ptr->link;
// Текущий элемент указывает на новый
L->ptr->link = temp;
}

 Исключение элемента

Пусть нам дан тот же список, что и в примере с включением элемента.

#image.jpgТак как ptr указывает на фиктивный — исключаем первый. Здесь перемычка ссылок немного сложнее, чем в предыдущем примере. Нужно создать временный элемент так, чтобы он был равен исключаемому, т.е. имел один и тот же с ним адрес. Это нужно для того, чтобы не потерять тот элемент, на который исключаемый ссылается.#image.jpgТеперь — перемычка указателей и удаление временного элемента. #image.jpg

Вот и вся операция исключения. Ниже представлен код.

/*Исключение элемента из списка. L -- дескриптор. E -- переменная для данных*/
void getListOne(ListOne *L, listOneBaseType *E) {
/*Если список пуст*/
if (isEmptyListOne(L)) {
return;
}
/*Если рабочий указатель указывает на последний элемент*/
if (!L->ptr->link) {
listOneError = listOneEnd;
return;
}
/*Иначе*/
// Временный элемент
ptrEl pntr = L->ptr->link;
// Текущий элемент ссылается на тот, на который ссылается исключаемый
L->ptr->link = pntr->link;
// Считывание информации из элемента списка
*E = pntr->data;
// Временный элемент ни на что не ссылается
pntr->link = NULL;
// Удаление временного элемента
free((void *) pntr);
}

Остальные операции я не буду так подробно расписывать, так как они просты в реализации.

Готовая реализация односвязного линейного списка

Файл List_One.h

/****************************************/
/*		Односвязный линейный список		*/
/****************************************/
#ifndef _lIST_ONE_H_
#define _lIST_ONE_H_
/*Описание исключительных ситуаций*/
const int listOneOK = 0;
const int listOneEmpty = 1;
const int listOneNoMem = 2;
const int listOneEnd = 3;
/**********************************/
/*Переменная ошибок*/
extern int listOneError;
/*Базовый тип списка*/
typedef int listOneBaseType;
/*Указатель на элемент списка*/
typedef struct element *ptrEl;
/*Структура элемента списка*/
struct element {
listOneBaseType data;						// Данные
ptrEl link;									// Указатель на следующий элемент списка
};
/*Дескриптор списка*/
typedef struct {
ptrEl start;								// Указатель на фиктивный элемент
ptrEl ptr;									// Указатель на рабочий элемент
} ListOne;
/*Функции работы со списком*/
void initListOne(ListOne *L);					// Инициализация списка
void putListOne(ListOne *L, listOneBaseType E);	// Включение элемента в список
void getListOne(ListOne *L, listOneBaseType *E);// Исключение элемента из списка
void movePtrListOne(ListOne *L);				// Сдвиг рабочего указателя
void beginPtrListOne(ListOne *L);				// Установка рабочего указателя в начало списка
void endPtrListOne(ListOne *L);					// Установка рабочего указателя в конец списка
void doneListOne(ListOne *L);					// Удаление списка
int isEmptyListOne(ListOne *L);					// Предикат: является ли список пустым
/***************************/
#endif

Файл List_One.c

/****************************************/
/*		Односвязный линейный список		*/
/****************************************/
#include <stdio.h>
#include <stdlib.h>
#include "List_One.h"
/*Переменная ошибок*/
int listOneError;
/*Инициализация списка. L -- дескриптор*/
void initListOne(ListOne *L) {
// Выделение пямяти под фиктивный элемент
L->start = (ptrEl) malloc(sizeof(element));
/*Если памяти не хватило*/
if (!L->start) {
listOneError = listOneNoMem;
return;
}
/*Иначе*/
// ptr указывает на то, что и start -- на фиктивный
L->ptr = L->start;
// Нет ссылки на следующий элемент
L->ptr->link = NULL;
}
/*Включение элемента в список L -- дескриптор. E -- данные*/
void putListOne(ListOne *L, listOneBaseType E) {
// Выделение памяти под новый элемент
ptrEl temp = (ptrEl) malloc(sizeof(element));
/*Если памяти недостаточно*/
if (!temp) {
listOneError = listOneNoMem;
return;
}
/*Иначе перемычка*/
// Внесение информции в новый элемент
temp->data = E;
// Новый элемент указывает на следующий
temp->link = L->ptr->link;
// Текущий элемент указывает на новый
L->ptr->link = temp;
}
/*Исключение элемента из списка. L -- дескриптор. E -- переменная для данных*/
void getListOne(ListOne *L, listOneBaseType *E) {
/*Если список пуст*/
if (isEmptyListOne(L)) {
return;
}
/*Если рабочий указатель указывает на последний элемент*/
if (!L->ptr->link) {
listOneError = listOneEnd;
return;
}
/*Иначе*/
// Временный элемент
ptrEl pntr = L->ptr->link;
// Текущий элемент ссылается на тот, на который ссылается исключаемый
L->ptr->link = pntr->link;
// Считывание информации из элемента списка
*E = pntr->data;
// Временный элемент ни на что не ссылается
pntr->link = NULL;
// Удаление временного элемента
free((void *) pntr);
}
/*Сдвиг рабочего указателя*/
void movePtrListOne(ListOne *L) {
/*Если рабочий указатель указывает на последний элемент*/
if (!L->ptr->link) {
listOneError = listOneEnd;
return;
}
/*Иначе смещение указателя*/
L->ptr = L->ptr->link;
}
/*Установка рабочего указателя в начало списка*/
void beginPtrListOne(ListOne *L) {
L->ptr = L->start;
}
/*Установка рабочего указателя в конец списка*/
void endPtrListOne(ListOne *L) {
while (L->ptr->link) {
movePtrListOne(L);
}
}
/*Удаление списка*/
void doneListOne(ListOne *L) {
beginPtrListOne(L);											// Установка рабочего указателя в начало
listOneBaseType temp;										// Создание временной переменной
while (!isEmptyListOne(L)) {								// Пока список не пуст
getListOne(L, &temp);									// Извлечь элемент
}
free((void *) L->ptr);										// Удалить фиктивный элемент
}
/*Предикат: является ли список пустым*/
int isEmptyListOne(ListOne *L) {
if (!L->start->link) {
listOneError = listOneEmpty;
return 1;
}
return 0;
}

Осталось только добавить, что перечисленные мной операции — далеко не все, которые можно реализовать для списка. Вы сами можете создавать новые. На этом все, если что было не понятно, пишите в комментариях.

2 отзыва на “Понятие односвязного линейного списка и его реализация на языке C

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *