Содержание


Работа со структурами данных в языках Си и Python

Часть 1. Особенности реализации структур данных в языках Си и Python

Comments

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

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

В первой статье, открывающей серию, будут разбираться следующие вопросы:

  • структуры данных и указатели в языке Си;
  • структуры данных и ссылки в Python;
  • списки в Python;
  • ссылочная организация списков.

Структуры данных

Под структурой данных понимается способ хранения и организации данных для их дальнейшего эффективного использования. Образно выражаясь, сколько существует приложений, столько же существует и различных способов организации данных, порой весьма специфических. Например, B-tree широко используются в базах данных, а компиляторы широко используют хеш-таблицы.

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

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

Различные языки программирования сильно различаются в плане встроенной реализации базовых структур данных. Так, в языке Pascal есть встроенная поддержка многомерных массивов, а в Lisp имеется встроенная реализация связных списков. В средах Perl и Python реализованы хеш-таблицы. Но самое главное, что в различных языках используются различные реализации ссылок, записей и других объектов.

Запись (record или struct) - одна из самых «низкоуровневых» структур данных, состоит из нескольких значений или полей, которые последовательно располагаются в памяти. Все поля могут иметь различный размер, и программист может определить произвольную структуру с произвольным количеством полей. При этом для каждого поля в этой структуре необходимо задать 2 атрибута:

  • определенный тип;
  • идентификатор.

Также структура может включать в себя поля, на самом деле являющиеся функциями. Такие поля в языке Си имеют тип void *. Благодаря подобным полям можно реализовать объектно-ориентированное программирование. В общем случае, структура - это упорядоченный список элементов или объектов.

Cobol был первым языком, в котором реализовали тип record. Этот язык позволял создавать структуры с набором полей, имеющим символьный или численный тип произвольного размера и точности. Позднее такие же структуры появились в Fortran, Algol, Lisp и Pascal, а еще позже структуры были добавлены в Си, Ada, Modula.

С записями/структурами можно выполнять следующие операции:

  • объявить новый тип записи;
  • создать переменную, имеющую тип записи;
  • присвоить значение какому-то полю внутри записи;
  • выбрать поле из записи по его имени;
  • сравнить 2 записи;
  • вычислить хеш для записи.

Между двумя структурами одного типа можно выполнить операцию присваивания. При этом различные языки по-разному могут трактовать строгую типизацию: например, в некоторых языках значение поля типа short integer может быть присвоено полю типа long integer.

Как уже было сказано, поля структуры располагаются в памяти последовательно, в соответствии с их порядком записи. Некоторые компиляторы могут делать неявное выравнивание полей в памяти. Также языки могут реализовывать структуру как массив указателей на поля структуры.

Структуры в языке Си

В языке Си структура - это тип, представляющий из себя набор именованных объектов различного типа, как показано в листинге 1.

Листинг 1. Пример структуры из языка Си
struct family {
   char *father;
   char *mother;
   int[2] ages;
};

Для создания новой переменной этого типа используется следующая конструкция:

struct family f;

Используя созданный объект и оператор «точка» (.) можно получить доступ к полям структуры и изменить их значение, как показано ниже:

f.father = "john dow";

В листинге 2 приведен другой вариант объявления структуры и создания объектов на ее основе.

Листинг 2. Другой вариант объявления структуры
typedef struct {
   int    a;
   int    b;
   int    c;   
} rec;

// создание объекта типа структуры
rec r1 = {1,2,3};
// создание второго объекта этого же типа
rec r2;
// выполнение присваивания между объектами
r2 = r1;

Указатели в языке Си

Для работы со структурами могут использоваться указатели. Указатель - это переменная, применяющаяся для использования структуры по ее адресу. Преимущество указателя в том, что его можно передать в качестве параметра в другую функцию, внутри которой можно будет использовать эту структуру. Указатель можно переназначить на другой указатель с помощью оператора «звездочка» (*), а помощью другого оператора -> можно обращаться к полям структуры, как показано ниже:

 struct rec *r3 = &r1;
 r3->c=3;

Указатели отличаются от обычных переменных тем, что при создании указателя создается ссылка на объект, в то время как в обычной переменной хранится адрес объекта. При использовании указателей необходимо учитывать следующие правила:

  • Указатель может указывать как на конкретный объект, так и ни на что не указывать. В последнем случае имеется в виду, что указатель установлен в NULL.
  • Указатель может быть разыменован. Это значит, что указатель не связан жестко с конкретным объектом, и в любой момент можно заменить объект, на который он указывает.
  • Указатель может быть плохим, когда после создания он не был инициализирован, то есть привязан к объекту. В языке Java при создании указателя он по умолчанию всегда устанавливается в NULL.
  • Указатель может быть назначен. Например, если есть два указателя - a и b, то между ними возможна операция назначения:
    a = b

    После этого оба указателя указывают на одну и ту же область памяти. Такая память называется общей (shared).
Листинг 3. Пример использования указателя
int *money = NULL
int a = 5;
money = &a;

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

Листинг 4. Передача параметров по ссылке
void alter(int *n) {
		*n = 120;
}

void not_alter(int n) {
	n = 10;
}

int x = 24;
alter(&x);
not_alter(x);

После вызова функции alter() значение переменной x изменится и станет равно 120, а вызов функции not_alter() никак не скажется на значении переменной x. Следует отметить, что работать с указателями нужно аккуратно и следовать перечисленным выше правилам, иначе возникновение проблем неизбежно.

Если в качестве параметра использовать не обычную переменную, а указатель, тогда в языке Си используется термин «двойной указатель». Например, в листинге 5 определяется элемент связного списка и указатель на первый элемент списка:

Листинг 5. Использование «двойных указателей»
struct element
{
    struct element * next;
    int    value;
};
 
struct element *head = NULL;

Если потребуется передать указатель head в функцию в качестве параметра по ссылке, то необходимо будет использовать двойной указатель:

void insert(struct element **head, int item) { }

Для добавления элемента в пустой список используется вызов:

insert(&head, item);

После этого указатель head будет указывать на первый элемент только что созданного связного списка.

Структуры данных в Python

В языке Python нет стандартного объекта struct, как в языке Си. Но этот объект можно легко реализовать с помощью классов. В листинге 6 представлен вариант преобразования структуры Си в класс Python.

Листинг 6. Структура в языке Си и аналогичный класс в Python
struct Employee {
			char * name;
			int salary;
	}

//объявление класса
class Employee(object):
	def __init__(self, name=None,  salary=2000):
		self.name = name
		self.salary = salary
	
//создание объекта
john = Employee('John Johnson',  3000)

В листинге 7 показано объявления класса, реализующего элемент в связном списке.

Листинг 7. Реализация связного списка в Python
class Element:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

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

Ссылки в Python

В Python нет указателей в том смысле, в каком они используются в языке Си. Зато все переменные одновременно являются и ссылками. Эта особенность Python избавляет от необходимости создавать дополнительные объекты типа указателей. При создании переменной в Python автоматически создается и ссылка на этот объект.

Ниже приведен фрагмент кода на языке Си:

	int foo = 3;
	int &bar = foo;

В нем создаются два объекта - переменная foo и ссылка bar. Оба объекта указывают на один и тот же адрес. Если изменить значение foo, то и значение bar автоматически изменится, и наоборот. Также ссылка bar не может быть переназначена на другой объект, так как ссылки в Си являются неизменяемыми (immutable).

В Python ссылка может быть переназначена, поскольку она одновременно является и переменной. В следующем примере создаются два списка:

>>> a1 = [1, 2, 3]
>>> a2 = [11, 22, 33]

Затем создается новая ссылка на первый список и в этот список добавляется элемент:

>>> b = a1
>>> a1.append(4)

Ссылка b по-прежнему ведет на первый список с уже измененными значениями:

>>> b
[1, 2, 3, 4]

Также можно переназначить ссылку на другой объект:

>>> b = a2
>>> b
[11, 22, 33]

Python также отличается от Си тем, что все параметры, передаваемые в функцию, по умолчанию имеют ссылочный тип. Но если говорить точнее, то почти все, так как в Python есть несколько стандартных типов, на которые это правило не распространяется: например immutable типы: целые и вещественные типы и строки. В листинге 8 в функцию в качестве параметра передается список:

Листинг 8. Передача параметров по ссылке в Python
def append(lst):
    lst.append(4)

a = [1, 2, 3]
append(a)
print a

После вызова функции список, переданный в качестве параметра, изменится, так как по умолчанию в Python аргументы функции имеют ссылочный тип.

Python относится к динамическим языкам с поздним связыванием (late-binding), так как переменные не имеют типовой привязки к объектам. Поэтому преобразование типов в Python выполняется на лету. Сначала необходимо создать список и ссылку на него, как показано ниже:

>>>	a = [1,2]
>>>	b = a

Можно проверить, была ли создана новая копия объекта или просто ссылка:

>>>print id(a) 
>>>print id(b) 
134806220
134806220

Одинаковые значения говорят, что обе переменные - это ссылки, указывающие на один и тот же объект. Теперь можно создать второй объект целочисленного типа на основе уже существующей ссылки и проверить, что получилось:

>>> a = 2    
>>> print(a) 
>>> print(b) 
>>> print id(a) 
>>> print id(b) 

2
[1, 2]
134573404
134806220

Разные значения говорят о том, что каждая ссылка указывает на разный объект, причем тип переменной a был неявно изменен.

Списки в языке Python

В общепринятом смысле, список - это структура, состоящая из последовательности элементов, с которой можно выполнять следующие операции:

  • получить доступ к элементу по индексу;
  • вставить элемент в произвольную позицию списка;
  • удалить произвольный элемент;
  • объединить 2 списка в один;
  • сделать копию списка;
  • сортировать список;
  • найти элемент в списке и т.д.

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

Стек (stack) - список, в котором операции вставки и удаления всегда выполняются над последним элементом. Стек еще называют LIFO-списком: last-in-first-out (последним пришел – первым ушел). В стеке есть верхняя позиция - top, куда всегда добавляется новый элемент, и нижняя позиция - bottom, которая извлекается из стека в последнюю очередь. Очередь (queue) - список, в котором операции вставки и удаления выполняются на разных концах списка. Очереди еще называют FIFO-списками: first-in-first-out (первым пришел – первым ушел).

В языке Python присутствует встроенный тип данных – «список», который можно определить с помощью квадратных скобок:

>>> list = []

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

Листинг 9. Работа со списками в Python
//добавление элементов в конец списка
>>> list.append(1)
>>> list.append(2)

//вставка элемента в начало списка
>>> list.insert(0,4)

//удаление элемента со значением 2
>>> list.remove(2)

//поиск позиции элемента в списке
>>> list.index(3)

//сортировка списка
>>> list.sort()
>>> list.reverse()

//реализация стека на основе стандартного списка и методов append() и top()
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack.pop()
>>> stack.pop()

//реализация очереди на основе встроенного класса
from collections import deque
>>> queue = deque([1,2,3,4,5])
>>> queue.append(6)     
>>> queue.append(7)     
>>> queue.popleft()

Организация списков на основе ссылок

В дальнейшем будут рассматриваться связные списки и деревья, построение которых немыслимо без ссылок. Под ссылкой понимается переменная, хранящая адрес объекта. На рисунке 1 показан список, построенный на основе ссылок.

Рисунок 1. Связанный список на основе ссылок
Рисунок 1. Связанный список на основе ссылок
Рисунок 1. Связанный список на основе ссылок

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

Преимущества:

  1. Удаление элементов в таком списке более эффективно, нежели удаление элементов из стандартного списка Python, который рассматривался в предыдущем разделе. Так как этот элемент удаляется из середины стандартного списка, то время, необходимое на эту операцию, будет зависеть от нескольких факторов: размера списка, положения удаляемого элемента относительно конца. Чем больше размер списка, тем медленнее будет происходить данная операция. В данном случае со ссылочной организацией списка удаление будет происходить одинаково быстро, независимо от размера списка и относительного положения элемента, так как потребуется всего лишь перевести ссылку в предыдущем элементе на следующий за удаляемым элемент.
  2. То же самое можно сказать и про вставку элементов - она выполняется так же эффективно, как и удаление.
  3. Объединение или разбиение 2-х списков будет выполняться быстрее, нежели в стандартном варианте.
  4. Преимуществом связных списков является и то, что элемент такого списка может иметь произвольную структуру, и включать не одну, а сразу несколько ссылок, что является отличительной особенностью деревьев.

Недостатки:

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

Заключение

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


Ресурсы для скачивания


Похожие темы

  • Работа со структурами данных в языках Си и Python. Часть 1.
  • Работа со структурами данных в языках Си и Python. Часть 2.

Комментарии

Войдите или зарегистрируйтесь для того чтобы оставлять комментарии или подписаться на них.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=648303
ArticleTitle=Работа со структурами данных в языках Си и Python: Часть 1. Особенности реализации структур данных в языках Си и Python
publish-date=04192011