C структуры данных: Сложные типы данных в Си : структуры, объединения, битовые поля

Программирование на C и C++

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

Обычно все члены структуры связаны друг с другом. Например, информация об имени и адресе, находящаяся в списке рассылки, обычно представляется в виде структуры. Следующий фрагмент кода объявляет шаблон структуры, определяющий имя и адрес. Ключевое слово struct сообщает компилятору об объявлении структуры.

struct addr {
char name[30];
char street [40]; char city[20];
char state[3];
unsigned long int zip;
};

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

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

struct addr addr_info;

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

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

При объявлении структуры можно одновременно объявить одну или несколько переменных.

Например:

struct addr {
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
} addr_info; binfo, cinfo;

объявляет структуру addr и объявляет переменные addr_info, binfo, cinfo данного типа.

Важно понять, что каждая вновь создаваемая структурная переменная содержит свои собственный копии переменных, образующих структуру. Например, поле zip переменной binfo отделено от поля zip переменной cinfo. Фактически, единственная связь между binfo и cinfo заключается в том, что они обе являются экземплярами одного типа структуры. Больше между ними нет связи.

Если необходима только одна структурная переменная, то нет необходимости в ярлыке структуры. Это означает, что

struct {
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
} addr_info;

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

struct ярлык {
тип имя переменной;
тип имя переменной;
тип имя переменной;
} структурные переменные;

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

Структурный тип данных. Урок 16 курса «Основы языка C»

Объявление и определение структур

Примером структуры может послужить любой объект, для которого описывается ряд его характеристик, имеющих значение в данной программе. Например, для книг это может быть название, автор, количество страниц; для окружности — координаты центра, диаметр, цвет. На языке программирования C объявление вышеупомянутых структурных типов данных может выглядеть так:

struct book {
    char title[50];
    char author[30];
    int pages;
};
struct circle {
    int x, y;
    float dia;
    char color[10];
};

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

Чаще переменные структур объявляются так:

struct circle a, b, c;
struct book mybook;

Здесь объявляются три структуры типа circle и одна структура типа book. Можно объявлять типы структур и их переменные по-иному, но мы для избежания путаницы рассматривать другие способы не будем.

Каждая переменная типа circle содержит четыре элемента (или поля) — x, y, dia, color. Можно сказать, что они представляют собой вложенные переменные. Причем эти переменные разных типов. Таким образом переменная-структура позволяет объединить под одним именем ряд разнородных данных. Обычно это нужно для удобства обработки данных. Если нельзя было бы создавать структуры, то пришлось бы создавать множество независимых переменных или ряд массивов, явной взаимосвязи между которыми не было бы. Структуры же позволяют объединять взаимосвязанные данные. Это конечно еще не объектно-ориентированное программирование, но уже взгляд в его сторону.

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

a.x = 10; a.dia = 2.35;
printf("%.2f ", a.dia);

Значение элементов структуры можно сразу определять при объявлении переменной, что похоже на инициализацию массивов:

struct book lang_c = {"Language C", 
                     "Ritchi", 99};

Значение переменной-структуры можно присвоить переменной того же типа:

struct book { char *title, 
              *author; 
              int pages; };
struct book old, new;
old.title = "GNU/Linux"; 
old.author = "people"; 
old.pages = 20213;
new = old;
new.pages += 2000;
printf("%d, %d\n", old.pages, new.pages);

В четвертой строке кода данные переменной old присваиваются new. В итоге вторая структура содержит копию данных первой. То, что можно выполнять присваивание по отдельным полям должно быть понятно.

Структуры и функции

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

#include <stdio.h>
#include <math.h>
 
struct circle { 
    int x, y; 
    float dia; 
    char color[10]; };
 
struct circle new_circle();
void cross (struct circle);
 
int main () {
    struct circle a;
 
    a = new_circle();
    cross(a);
}   
 
 
struct circle new_circle() {
    struct circle new;
 
    printf("Координаты: "); 
    scanf("%d%d", &new.x, &new.y);
    printf("Диаметр: "); 
    scanf("%f", &new.dia); 
    printf("Цвет: "); 
    scanf("%s", new.color);
 
    return new;
}
 
 
void cross (struct circle c) {
    double hyp;
 
    hyp = sqrt((double) c.x * c.x +
               (double) c.y * c.y);
    printf("Расстояние: %.2lf\n", hyp);
    if (hyp <= c.dia / 2) 
        puts("Пересекает");
    else 
        puts("Не пересекает");
}

Примечание. При компиляции программы в GNU/Linux команда выглядит так: gcc program.c -lm. Это связано с использованием библиотеки с математическими функциями.

• Объявляется структура circle как глобальный тип данных. Таким образом любая, а не только main(), функция может создавать переменные этого типа.
• Функция new_circle() возвращает структуру, а функция cross() принимает структуру по значению. Следует отметить, что можно создавать функции, которые как принимают (возможно, несколько структур) так и возвращают структуру.
• В функции new_circle() создается переменная new типа struct circle, поля которой заполняются пользователем. Функция возвращает значение переменной new в функцию main(), где это значение присваивается переменной a, которая также принадлежит типу sctruct circle.
• Функция cross() определяет, пересекает ли круг начало координат. В ее теле вычисляется расстояние от центра круга до начала координат. Это расстояние является гипотенузой прямоугольного треугольника, длина катетов которого равна значениям x и у. Далее, если гипотенуза меньше радиуса, то круг пересекает начало координат, т.е. точку (0, 0).
• В функции main() при вызове cross() данные, содержащиеся в переменной a, копируются и присваиваются переменной c.

Указатели и структуры

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

// переменная-структура
struct book new; 
 
// указатель на структуру
struct book *pnew; 
 
// передаем адрес
reader(&new); 
 
pnew = &new;
 
// передаем указатель
reader(pnew); 

Тогда функция reader() должна иметь примерно такое объявление:

void reader(struct book *pb); 

Возникает вопрос, как при использовании указателей обращаться к элементам структур? Во первых надо получить саму структуру, т.е. если pnew указатель, то сама структура будет *pnew. Далее можно уже обращаться к полям через точку: *pnew.title. Однако это выражение не верно, т.к. приоритет операции «точка» (обращение к полю) выше операции «звездочка» (получить значение по адресу). Таким образом приведенная запись сначала пытается получить значение поля title у указателя pnew, но у pnew нет такого поля. Проблема решается с помощью скобок, которые изменяют порядок выполнения операций: (*pnew).title. В таком случае сначала извлекается значение по адресу pnew, это значение является структурой. Затем происходит обращение к полю структуры.

В языке программирования C записи типа (*pnew).title часто заменяют на такие: pnew->title, что позволяет синтаксис языка. Когда в программе вы видите стрелку (тире и скобка) всегда помните, то, что написано до стрелки, — это указатель на структуру, а не переменная-структура.

Пример кода с использованием указателей:

#include <stdio.h>
 
struct circle { int x, y; float dia; };
void inversion (struct circle *);
 
int main () {   
    struct circle cir, *pc = &cir;
 
    pc->x = 10; 
    pc->y = 7; 
    pc->dia = 6; 
    inversion(pc);
    printf("x = %d, y = %d\n", 
            cir.x, cir.y);
}   
 
void inversion(struct circle *p) {
    p->x = -p->x;
    p->y = -p->y;
}

Массивы структур

Обычно создание в программе одной переменной структурного типа не имеет особого смысла. Чаще структурами пользуются, когда необходимо описать множество похожих объектов, имеющих разные значения признаков. Значения каждого объекта следует объединить вместе (в структуру) и тем самым отделить от значений других объектов. Например, описание ряда книг или множества людей. Таким образом мы можем организовать массив, где каждый элемент представляет собой отдельную структуру, а все элементы принадлежат одному и тому же структурному типу.

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

Программа будет предоставлять возможность получать информацию о всех моделях и изменять количество компьютеров указанной пользователем модели. В программе будут определены две функции (помимо main()): для вывода всей информации и для изменения количества компьютеров.

#include <stdio.h>
 
#define N 5
 
struct computer { 
    char *type; 
    char *proc; 
    int qty; };
 
void viewer (struct computer *);
void changer (struct computer *);
 
int main () {
    struct computer comps[N]= {
    "Desktop", "earlier then P4", 10, 
    "Desktop", "P4", 30 ,
    "Desktop", "Core", 20 ,
    "Desktop", "AMD", 2 ,
    "Notebook", "Core", 1 };
 
    viewer(comps);
    changer(comps);
    viewer(comps);  
}
 
void viewer (struct computer *comp) {
    int i;
 
    for (i=0; i < N; i++, comp++)
        printf("%2d) %-8s - %-15s: %3d\n", 
               i+1, comp->type, comp->proc,
               comp->qty);
}
 
void changer (struct computer *comp) {
    int i, differ;
 
    printf("Введите номер модели: ");
    scanf("%d", &i); i--;
    printf(
    "На сколько уменьшить или увеличить: ");
    scanf("%d", &differ);
    (comp+i)->qty += differ;
}

• Массив структур инициализируется при его объявлении.
• Функции viewer() и changer() принимают указатели на структуру computer.
• В теле viewer() указатель инкрементируется в заголовке цикла; таким образом указывая на следующий элемент массива, т.е. на следующую структуру.
• В выражении (comp+i)->qty скобки необходимы, т.к оператор -> имеет более высокий приоритет. Скобки позволяют сначала получить указатель на i-ый элемент массива, а потом обратиться к его полю.
• Декрементирование i в функции changer() связано с тем, что индексация начинается с нуля, а номера элементов массива, которые пользователь видит на экране, с единицы.
• Для того, чтобы уменьшить количество компьютеров, при запросе надо ввести отрицательное число.

Пример результата работы программы:

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

Курс с решением части задач:
android-приложение, pdf-версия

Динамические структуры данных. Урок 17 курса «Основы языка C»

Структуры одного типа можно объединять не только в массивы. Их можно связывать между собой, создавая так называемые динамические структуры данных. Связь между отдельными структурами может быть организована по-разному, и именно поэтому среди динамических данных выделяют списки, стеки, очереди, деревья, графы и др. Мы не будем рассматривать каждый тип. Цель этого урока — понять, что такое динамические данные, и как они создаются на языке программирования C.

Для динамических данных память выделяется и освобождается в процессе выполнения программы, а не в момент ее запуска. Так, например, если в программе объявлен массив из 100 элементов, то при запуске программы резервируется память для всех ста элементов, даже если в процессе работы программы всего будут использованы первые 10 элементов массива. С другой стороны, при использовании в программе динамических типов память под них заранее не выделяется. Лишь когда поступают новые данные, вызывается специальная функция, которая выделяет память, куда эти данные записываются.

Тут появляется проблема. Для динамических типов данных не объявляются переменные, иначе память бы выделялась под переменные. Как тогда обращаться к данным, записанным неизвестно где в памяти? Можно ввести переменные-указатели и при выделении памяти записывать адрес этой памяти в указатели. Но мы же не знаем, сколько памяти потребуется в процессе выполнения. Сколько вводить указателей?

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

Идея заключается примерно в следующем:

1. В программе определяем структурный тип данных с «кое-какой изюминкой» и создаем переменную указатель на него. В итоге при запуске программы память выделяется только под указатель.
2. В процессе выполнения программы, в случае возникновения необходимости в создании структуры, с помощью специальной функции выделяем память под хранение данных (полей структуры).
3. Присваиваем указателю адрес, по которому расположена только что созданная структура.
4. Когда поступает команда на создание следующей структуры, снова с помощью функции выделяется память, а указателю присваивается адрес этой новой структуры.
5. «Изюминка» определенного ранее структурного типа данных заключается в том, что одним из его полей является указатель на структуру этого же типа.
6. В это поле-указатель записывается адрес на структуру, которая была создана перед данной структурой.

Таким образом получается цепочка взаимосвязанных структур. Самая первая созданная структура не имеет ссылки на другую структуру. Ее поле-указатель имеет значение NULL. Вторая созданная структура ссылается на первую, третья на вторую и т.д. Адрес последней созданной структуры хранится в переменной-указателе, которая была объявлена в программе программистом.

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

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

В языке программирования C выделение памяти в процессе выполнения программы можно организовать с помощью функций malloc() и calloc(), освобождение памяти с помощью free(). Объявление этих функций находится в заголовочных файлах stdlib.h и malloc.h. К исходному коду можно подключить любой из них.

Функция malloc() принимает в качестве параметра число, обозначающее объем памяти, который требуется выделить. Если свободная память есть, и malloc() удается ее «захватить», то функция возвращает указатель на нее. Этот указатель не имеет типа, поэтому программист самостоятельно должен привести его к требуемому в программе типу данных.

Функция free() принимает указатель, и освобождает память по адресу, который он содержит.
Рассмотрим программу:

#include <stdio.h>
#include <stdlib.h>
 
struct stack {
    int data;
    struct stack *next;
};
 
/* присоединение элемента к голове,
возврат адреса головы */
struct stack *create(struct stack *, int); 
 
// просмотр стека
void list(struct stack *); 
 
int main() {
    int i, n;
    // адрес, указывающий на голову стека
    struct stack *head; 
    head = NULL;
 
    scanf("%d", &n); 
    for (i=0; i <= n; i+=5) {
       head = create(head,i);
       printf("%d<--", head->data);
    }
    printf("\n");
    list(head);
    free(head);
}
 
struct stack *create(struct stack *head, 
                     int x) {
 
    // указатель на новую структуру
    struct stack *element; 
 
     // выделяем память
    element = (struct stack *)malloc(
                sizeof(struct stack));
    element->next = head;
    element->data = x;
    return element;
}
 
void list(struct stack *p){
    // пока не конец стека
    while (p != NULL) {     
      printf("%d-->", p->data);
      // продвижение по списку
      p = p->next; 
    }
    printf("\n");
}

В процессе выполнения эта программа запрашивает целое число и сначала выводит числа от 0 до указанного числа, а затем выводит их же в обратном порядке — от указанного число до нуля:

40
0<--5<--10<--15<--20<--25<--30<--35<--40<--
40-->35-->30-->25-->20-->15-->10-->5-->0-->

Осталось выяснить почему она так делает.

1. В программе определяется тип данных struct stack, одним из полей которого является указатель на структуру типа struct stack.
2. В функции main() создается указатель (head) на struct stack, которому сначала присваивается NULL, т.к. он никуда не указывает.
3. В цикле определенное количество раз вызывается функция create(), которой передается текущее значение указателя (адрес) и какое-то число.
4. В теле create() создается новый указатель (element) типа struct stack.
5. С помощью функции malloc() выделяется память, необходимая под одну структуру. Объем этой памяти вычисляется с помощью функции sizeof(). Возвращаемый malloc()указатель приводится к типу struct stack.
6. Адрес выделенной памяти под новую структуру присваивается переменной-указателю element.
7. В поле next новой структуры записывается адрес, который содержится в аргументе, переданном в функцию. При первом вызове create() там содержится NULL. При последующих вызовах адрес памяти созданной в предыдущем вызове функции структуры. Таким образом в поле next структуры, доступной по указателю element, сохраняется адрес, содержащийся в head. Следовательно head в дальнейшем можно изменить, не потеряв связь с предыдущими данными.
8. В поле data записывается число (какие-то существенные для нас данные).
9. Из функции create() возвращается указатель на только что выделенную память с новой структурой, в которой сохранен адрес на предыдущую структуру. Этот указатель присваивается head. В результате head постоянно указывает на последнюю созданную структуру.
10. На экран с помощью printf() выводится значение поля data структуры, на которую указывает в данный момент head.
11. Функция list() позволяется просмотреть стек, получив указатель на его последний (по времени создания) элемент. При вызове значение head присваивается переменной p. Обратите внимание, изменение p в теле list() не повлияет на значение head в теле main(). Переменная p получает копию адреса и далее изменяет лишь свое значение.
12. В выражении p = p->next сначала изымается значение из поля next структуры, на которую указывает p. Там содержится адрес на предыдущую структуру, и этот адрес присваивается p. Таким образом p как бы перемещается по стеку, начиная с последней вошедшей в него структуры и заканчивая на той, которая была создана первой. Поле nextпервой структуры содержит NULL, который служит условием выхода из цикла.
13. В конце с помощью функции free() освобождает память по адресу, на который указывает head. (Освобождается ли при этом вся выделенная память или только та, что была отведена на последнюю структуру?)

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

1. Напишите программу, аналогичную приведенной в уроке. При этом структурный тип данных должен быть более сложным и содержать как минимум три значащих поля (например, данные о сотрудниках: ФИ, сфера деятельности, стаж). Поля должны заполняться пользователем.
2. Напишите к вашей программе функцию, которая выводит значения полей указанной пользователем структуры. Например, пользователь пишет ФИ и получает остальные сведения о человеке.
3. Напишите еще одну функцию, которая позволяет удалять последнюю записанную структуру.
4. Подумайте над алгоритмом удаления структуры из любого места стека. Попробуйте его реализовать.

Курс с решением части задач:
android-приложение, pdf-версия

Что такое структуры данных в Objective-C?

Какие структуры данных мы можем использовать в Objective-C?

objective-c

data-structures

Поделиться

Источник

sukumar    

05 декабря 2009 в 06:11

3 ответа

34

NSArray -это ваша стандартная структура массива.

NSDictionary -это ключ-значение «hash map»

NSSet -это неупорядоченная коллекция уникальных объектов.

Каждый из них неизменен (т. Е., как только вы их создадите, вы не сможете их изменить). Если вам нужно изменить их динамически, вы будете использовать их изменяемые подклассы: NSMutableArray , NSMutableSet и т. Д.

Для структур, выходящих за рамки этого, проверьте фреймворк CHDataStructures, в котором есть очереди, стеки, деревья, трепы и многое другое: http://cocoaheads.byu.edu/code/chdatastructures

Поделиться

Dave DeLong    

05 декабря 2009 в 06:55

5

Objective-C-это C, поэтому он поддерживает struct и знакомые типы данных на языке C, такие как int и char.

Кроме того, существуют специальные классы Objective-C.

Возможно, вы захотите взглянуть на книгу Apple Objective-C .

Поделиться

Seth    

05 декабря 2009 в 06:19

2

Следующие документы могут помочь:

Поделиться

Steve Harrison    

05 декабря 2009 в 06:19

• Что такое Objective C++?

  Что такое Objective C++ и могу ли я использовать этот язык в Xcode?

• Что такое объект класса в Objective-C 2.0?

  В официальной документации для Objective C 2.0 под названием Objective-C 2.0 язык программирования от Apple, выпущенный в 2009 году, есть параграф об объектах класса на странице 28. Я не понимаю, что такое объекты класса и как их определить, кроме rest языка и каких свойств они обладают. В том же…

Похожие вопросы:

Objective C синтаксис: что такое ->?

Возможный Дубликат : Что такое “->” в Objective C? начинающий вопрос здесь. Я просматриваю это вступление к objective c runtime (…

Что более эффективно при программировании в objective C? Структуры или какой-то тип данных objective C, похожий на структуры?

Существуют ли более эффективные типы данных в objective c, реализующие структуры, или структура C, даже если она используется в objective c, более эффективна?

Что такое Objective C эквивалент EventWaitHandle?

Что такое Objective C эквивалент EventWaitHandle в .NET?

что такое протокол в objective-c

Возможный Дубликат : Что такое протокол привет, как использовать протокол в Objective-c ? в чем же его преимущество? Спасибо и с уважением+

Что такое сообщение в objective-c?

Что такое сообщение в objective-c?

Что такое Objective C++?

Что такое Objective C++ и могу ли я использовать этот язык в Xcode?

Что такое объект класса в Objective-C 2.0?

В официальной документации для Objective C 2.0 под названием Objective-C 2.0 язык программирования от Apple, выпущенный в 2009 году, есть параграф об объектах класса на странице 28. Я не понимаю,…

Наследование структуры в Objective-C?

Есть ли что-то похожее на наследование структуры в Objective-C? Например, C++ позволяет мне сделать что — то вроде: struct animal { int weight; string name; } struct dog : animal { string breed; }…

Что такое приемник в Objective C?

Я не понимаю, что такое ‘receiver’ в Objective-C? На сайте follwing говорится следующее о том, что такое приемник: https://quizlet.com/104540068/objective-c-flash-cards / В Objective-C вы указываете…

Что такое Big O структуры данных deque в c++?

Что такое Big O структуры данных deque в c++? И как это реально реализовано! Я нигде не нашел ответа.

О выборе структур данных для начинающих / Хабр

Часть 1. Линейные структуры

Когда вам нужен один объект, вы создаёте один объект. Когда нужно несколько объектов, тогда есть несколько вариантов на выбор. Я видел, как многие новички в коде пишут что-то типа такого:

// Таблица рекордов
int score1 = 0;
int score2 = 0;
int score3 = 0;
int score4 = 0;
int score5 = 0;

Это даёт нам значение пяти рекордов. Этот способ неплохо работает, пока вам не потребуется пятьдесят или сто объектов. Вместо создания отдельных объектов можно использовать массив.

// Таблица рекордов
const int NUM_HIGH_SCORES = 5;
int highScore[NUM_HIGH_SCORES] = {0};

Будет создан буфер из 5 элементов, вот такой:

Заметьте, что индекс массива начинается с нуля. Если в массиве пять элементов, то они будут иметь индексы от нуля до четырёх.

Недостатки простого массива

Если вам нужно неизменное количество объектов, то массив вполне подходит. Но, допустим, вам нужно добавить в массив ещё один элемент. В простом массиве этого сделать невозможно. Допустим, вам нужно удалить элемент из массива. В простом массиве это так же невозможно. Вы привязаны к одному количеству элементов. Нам нужен массив, размер которого можно менять. Поэтому нам лучше выбрать…

Динамический массив — это массив, который может менять свой размер. Основные языки программирования в своих стандартных библиотеках поддерживают динамические массивы. В C++ это

vector

. В Java это

ArrayList

. В C# это

List

. Все они являются динамическими массивами. В своей сути динамический массив — это простой массив, однако имеющий ещё два дополнительных блока данных. В них хранятся действительный размер простого массива и объём данных, который может на самом деле храниться в простом массиве. Динамический массив может выглядеть примерно так:

// Внутреннее устройство класса динамического массива
sometype *internalArray;
unsigned int currentLength;
unsigned int maxCapacity;

Элемент

internalArray

указывает на динамически размещаемый буфер. Действительный массив буфера хранится в

maxCapacity

. Количество использовуемых элементов задаётся

currentLength

.

Добавление к динамическому массиву

При добавлении объекта к динамическому массиву происходит несколько действий. Класс массива проверяет, достаточно ли в нём места. Если

currentLength < maxCapacity

, то в массиве есть место для добавления. Если места недостаточно, то размещается больший внутренний массив, и всё копируется в новый внутренний массив. Значение maxCapacity увеличивается до нового расширенного значения. Если места достаточно, то добавляется новый элемент. Каждый элемент после точки вставки должен быть скопирован на соседнее место во внутреннем массиве, и после завершения копирования пустота заполняется новым объектом, а значение

currentLength

увеличивается на единицу.

Поскольку необходимо перемещать каждый объект после точки вставки, то наилучшим случаем будет добавление элемента к концу. При этом нужно перемещать ноль элементов (однако внутренний массив всё равно требует расширения). Динамический массив лучше всего работает при добавлении элемента в конец, а не в середину.

При добавлении объекта к динамическому массиву каждый объект может переместиться в памяти. В таких языках, как C и C++, добавление к динамическому массиву означает, что ВСЕ указатели на объекты массива становятся недействительными.

Удаление из динамического массива

Удаление объектов требует меньше работы, чем добавление. Во-первых, уничтожается сам объект. Во-вторых, каждый объект после этой точки сдвигается на один элемент. Наконец, currentLength уменьшается на единицу.

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

Удаление объекта из динамического массива приводит к смещению в памяти всего после удалённого элемента. В таких языках, как C и C++, удаление из динамического массива означает, что указатели на всё после удалённого массива становятся недействительными.

Недостатки динамических массивов

Допустим, массив очень велик, а вам нужно часто добавлять и удалять объекты. При этом объекты могут часто копироваться в другие места, а многие указатели становиться недействительными. Если вам нужно вносить частые изменения в середине динамического массива, то для этого есть более подходящий тип линейной структуры данных…

Массив — это непрерывный блок памяти, и каждый элемент его расположен после другого. Связанный список — это цепочка объектов. Связанные списки тоже присутствуют в стандартных библиотеках основных языков программирования. В C++ они называются

list

. В Java и C# это

LinkedList

. Связанный список состоит из серии узлов. Каждый узел выглядит примерно так:

// Узел связанного списка
sometype data;
Node* next;

Он создаёт структуру такого типа:

Каждый узел соединяется со следующим.

Добавление к связанному списку

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

Удаление из связанного списка

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

Преимущества связанного списка

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

Недостатки связанного списка

Вспомните, что динамический массив — это непрерывный блок памяти.

Если вам нужно получить пятисотый элемент массива, то достаточно просто посмотреть на 500 «мест» вперёд. В связанном списке память соединена в цепочку. Если вам нужно найти пятисотый элемент, то придётся начинать с начала цепочки и следовать по её указателю к следующему элементу, потом к следующему, и так далее, повторяя пятьсот раз.

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

Ещё один серьёзный недостаток связанного списка не особо очевиден. Каждому узлу необходимо небольшое дополнительное место. Сколько ему нужно места? Можно подумать, что для него нужен только размер указателя, но это не совсем так. При динамическом создании объекта всегда существует небольшой запас. Некоторые языки программирования, например, C++, работают со страницами памяти. Обычно страница занимает 4 килобайта. При использовании операторы добавления и удаления, размещается целая страница памяти, даже если вам нужно использовать только один байт.

В Java и C# всё устроено немного иначе, в них есть специальные правила для небольших объектов. Для этих языков не требуется вся 4-килобайтная страница памяти, но всё равно у них есть небольшой запас. Если вы используете стандартные библиотеки, то о втором недостатке волноваться не нужно. Они написаны таким образом, чтобы минимизировать занимаемое впустую место.

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

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

Часть 2. Линейные структуры данных с конечными точками

Представьте, что у вас есть куча листов бумаги.

Мы кладём один лист в стопку. Теперь мы можем получить доступ только к верхнему листу.

Мы кладём ещё один лист в стопку. Предыдущий лист теперь скрыт и доступ к нему невозможен, мы можем использовать верхний лист. Когда мы закончим с верхним листом, мы можем убрать его со стопки, открыв доступ к лежащему под ним.

В этом заключается идея стека. Стек — это структура LIFO. Это расшифровывается как Last In First Out («последним вошёл, первым вышел»). При добавлении и удалении из стека последний добавленный элемент будет первым удаляемым.

Для стека нужно всего три операции: Push, Pop и Top.

Push добавляет объект в стек. Pop удаляет объект из стека. Top даёт самый последний объект в стеке. Эти контейнеры в большинстве языков являются частью стандартных библиотек. В C++ они называются stack. В Java и C# это Stack. (Да, единственная разница в названии с заглавной буквы.) Внутри стек часто реализуется как динамический массив. Как вы помните из этой структуры данных, самыми быстрыми операциями на динамических массивах являются добавление и удаление элементов из конца. Поскольку стек всегда добавляет и удаляет с конца, обычно push и pop объектов в стеке выполняется невероятно быстро.

Представьте, что вы стоите в очереди за чем-то.

Первого человека в очереди обслуживают, после чего он уходит. Потом обслуживается и уходит второй в очереди. Другие люди подходят к очереди и встают в её конец. Вот в этом заключается идея структуры данных «очередь».

Очередь — это структура FIFO (First In First Out, «первым зашёл, первым вышел»).

При добавлении и удалении из очереди первый добавляемый элемент будет первым извлекаемым. Очереди нужно только несколько операций: Push_Back, Pop_Front, Front и Back. Push_Back добавляет элемент к концу очереди. Pop_Front удаляет элемент из начала очереди. Front и Back позволяют получить доступ к двум концам очереди.

Программистам часто нужно добавлять или удалять элементы из обоих концов очереди. Такая структура называется двухсторонней очередью (double ended queue, deque). В этом случае добавляется ещё пара операций: Push_Front и Pop_Back. Эти контейнеры тоже включены в большинство основных языков. В C++ это queue и deque. Java определяет интерфейсы для очереди и двухсторонней очереди, а затем реализует их через LinkedList. В C# есть класс Queue, но нет класса Deque.

Внутри очередь и двухсторонняя очередь могут быть устроены довольно сложно. Поскольку объекты могут поступать и извлекаться с любого конца, внутренний контейнер должен уметь наращивать и укорачивать очередь с начала и с конца. Во многих реализациях используются множественные страницы памяти. Когда любой из концов разрастается за пределы текущей страницы, добавляется дополнительная страница. Если страница больше не нужна, то она удаляется. В Java используется следующий способ: для связанного списка требуется немного дополнительной памяти, а не страниц памяти, но для этого языка такая реализация вполне работает.

Это очень распространённая вариация очереди. Очередь с приоритетом очень похожа на обычную очередь.

Программа добавляет элементы с конца и извлекает элементы из начала. Разница в том, что можно задавать приоритеты определённым элементам очереди. Все самые важные элементы обрабатываются в порядке FIFO. Потом в порядке FIFO обрабатываются элементы с более низким приоритетом. И так повторяется, пока не будут обработаны в порядке FIFO элементы с самым низким приоритетом.

При добавлении нового элемента с более высоким приоритетом, чем остальная часть очереди, он сразу же перемещается в начало очереди. В C++ эта структура называется priority_queue. В Java это PriorityQueue. В стандартной библиотеке C# очереди с приоритетом нет. Очереди с приоритетом полезны не только для того, чтобы встать первым на очереди к принтеру организации. Их можно использовать для удобной реализации алгоритмов, например, процедуры поиска A*. Наболее вероятным результатам можно отдать более высокий приоритет, менее вероятным — более низкий. Можно создать собственную систему для сортировки и упорядочивания поиска A*, но намного проще использовать встроенную очередь с приоритетом.

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

Часть 3. Деревья и кучи.

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

Дерево — это… дерево. У настоящего дерева есть корень, ветви, а на концах ветвей есть листья.

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

Одним из первых возникает вопрос: сколько каждый узел может иметь дочерних элементов?

Многие деревья имеют не больше двух дочерних узлов. Они называются двоичными деревьями. На примере выше показано двоичное дерево. Обычно дочерние элементы называются левым и правым дочерними узлами. Ещё одним распространённым в играх типом деревьев является дерево с четырьмя дочерними узлами. В дереве квадрантов (quadtree), которое можно использовать для покрытия сетки, дочерние узлы обычно называются по закрываемому ими направлению: NorthWest (северо-запад) или NW, NorthEast (северо-восток) или NE, SouthWest (юго-запад) или SW и SouthEast (юго-восток) или SE.

Деревья используются во многих алгоритмах (я уже упоминал о двоичных деревьях). Существуют сбалансированные и несбалансированные деревья. Бывают красно-чёрные деревья, АВЛ-деревья, и многие другие.

Хотя теория деревьев и удобна, она страдает от серьёзных недостатков: места для хранения и скорости доступа. Каким способом лучше всего хранить дерево? Наиболее простым способом является построение связанного списка, он же оказывается самым худшим. Предположим, что нам нужно построить сбалансированное двоичное дерево. Мы начинаем со следующей структуры данных:

// Узел дерева
Node* left;
Node* right;
sometype data;

Достаточно просто. Теперь представим, что в нём нужно хранить 1024 элемента. Тогда для 1024 узлов придётся хранить 2048 указателей.

Это нормально, указатели малы и можно обойтись небольшим пространством.

Вы можете помнить, что при каждом размещении объекта он занимает небольшую часть дополнительных ресурсов. Точное количество дополнительных ресурсов зависит от библиотеки используемого вами языка. Многие популярные компиляторы и инструменты могут использовать различные варианты — от всего лишь нескольких байтов для хранения данных до нескольких килобайтов, позволяющих упростить отладку. Я работал с системами, в которых размещение занимает не меньше 4 КБ памяти. В этом случае 1024 элементов потребуют около 4 МБ памяти. Обычно ситуация не настолько плоха, но дополнительные затраты на хранение множества мелких объектов нарастают очень быстро.

Вторая проблема — скорость. Процессорам «нравится», когда объекты находятся в памяти рядом друг с другом. У современных процессоров есть участок очень быстрой памяти — кэш — который очень хорошо справляется с большинством данных. Когда программе требуется один фрагмент данных, кэш загружает этот элемент, а также элементы рядом с ним. Когда данные не загружены в очень быструю память (это называется «промахом кэша»), программа приостанавливает свою работу, и ждёт загрузки данных. В самом очевидном формате, когда каждый элемент дерева хранится в собственном участке памяти, ни один из них не находится рядом с другим. Каждый раз при обходе дерева программа приостанавливается.

Если создание дерева напрямую связано с такими проблемами, то стоит выбрать структуру данных, работающую как дерево, но не обладающую его недостатками. И эта структура называется…

Чтобы вас запутать, скажу, что существует два вида куч.

Первая — это куча в памяти. Это большой блок памяти, в котором хранятся объекты. Но я буду говорить о другой куче.

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

При добавлении или удалении объектов из кучи структура сортирует себя, чтобы стать «полным» деревом, в котором каждый уровень дерева заполнен, за исключением, возможно, только последнего ряда, где всё должно быть смещено в одну сторону. Это позволяет очень эффективно обеспечить пространство для хранения и поиск по куче.

Кучи можно хранить в простом или динамическом массиве, то есть на её размещение тратится мало места. В C++ есть такие функции, как push_heap() и pop_heap(), позволяющие реализовать кучи в собственном контейнере разработчика. В стандартных библиотеках Java и C# нет похожего функционала. Вот дерево и куча с одинаковой информацией:

Это простые, фундаментальные и очень полезные структуры данных. Многие считают, что они должны присутствовать в стандартных библиотеках. За несколько секунд в поисковике вы можете найти тысячи реализаций деревьев.

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

Важно знать о структурах данных «дерево», потому что в работе вам часто придётся их использовать. Также важно знать, что эти структуры данных при прямой реализации имеют недостатки. Вы можете реализовывать собственные структуры деревьев, просто знайте, что существуют более компактные типы. Зачем же я рассказал о них, если они на самом деле не используются в стандартных библиотеках? Они применяются в качестве внутренних структур в нашей следующей теме:

Часть 4. Нелинейные структуры данных.

Эти структуры данных отличаются от массивов и списков. Массивы — это последовательные контейнеры. Элементы в них расположены по порядку. При добавлении нескольких элементов в определённом порядке, они остаются в этом порядке.

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

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

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

Если словари не были бы отсортированы, то поиск слов в них был невероятно сложным.

Существует два основных способа сортировки элементов в словаре: сравнение или хэш. Традиционное упорядочивание сравнением обычно более интуитивно. Оно похоже на порядок бумажном словаре, где всё отсортировано по алфавиту или по числам.

При сортировке элементов таким образом может потребоваться функция сравнения. Обычно эта функция по умолчанию является оператором «меньше чем», например a < b.

Второй способ сортировки элементов — использование хэша. Хэш — это просто способ преобразования блока данных в одно число. Например, строка «blue» может иметь хэш 0xa66b370d, строка «red» — хэш 0x3a72d292. Когда словарь данных использует хэш, он обычно считается неотсортированным. В действительности он всё равно отсортирован по хэшу, а не по удобному человеку критерию. Словарь данных работает тем же образом. Есть небольшая разница в скорости между использованием словарей с традиционной сортировкой и сортировкой по хэшу. Различия так малы, что их можно не учитывать.

В C++ есть семейство контейнеров map/mutimap или unordered_map/unordered_multimap. В Java семейство называется HashMap, TreeMap или LinkedHashMap. В C# это Dictionary или SortedDictionary. Каждое из них имеет собственные особенности реализации, например сортировка по хэшу или сравнением, допущение дубликатов, но в целом концепция одинакова. Заметьте, что в каждой из стандартных библиотек имеется их упорядоченная версия (в которой задаётся сравнение) и неупорядоченная версия (где используется хэш-функция). После добавления элементов в словарь данных вы сможете изменять значения, но не ключ.

Вернёмся к аналогии с бумажным словарём: можно менять определение слова, не перемещая слово в книге; если изменить написание слова, то придётся удалять первое написание и повторно вставлять слово с новым написанием. Подробности работы вы можете узнать в учебниках. Достаточно знать, что словари очень быстры при поиске данных, и могут быть очень медленными при добавлении или удалении значений.

Упорядоченное множество — это почти то же самое, что и словарь. Вместо ключа и значения в нём есть только ключ. Вместо традиционного словаря со словами и определениями там только слова. Множества полезны, когда вам нужно хранить только слова без дополнительных данных. В C++ семейство структур называется

set

/

multiset

или

unordered_set

/

unordered_multiset

. В Java это

HashSet

,

TreeSet

или

LinkedHashSet

. В C# они называются

HashSet

и

SortedSet

.

Как и в случае со словарями, существуют упорядоченные версии (где задаётся сравнение) и неупорядоченные версии (где используется хэш-функция). После добавления ключа его тоже нельзя изменять. Вместо этого нужно удалить старый объект и вставить новый. Часто они реализуются точно так же, как словарь данных, просто хранят только значение. Поскольку они реализуются так же, то они имеют те же характеристики. В множествах очень быстро ищутся и находятся значения, но они медленно работают при добавлении и удалении элементов.

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

Часть 5. Правильный выбор структур данных.

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

Вкратце повторим их.

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

Есть линейные структуры данных с конечными точками: семейство стеков и очередей. Оба они работают примерно так же, как их аналоги в реальном мире. В стеке, например, в стопке тарелок или в стеке данных, можно «затолкнуть» (push) что-нибудь наверх, можно получить доступ к верхнему элементу и можно «столкнуть» (pop) этот элемент. Очередь, так же как очередь людей, работает добавлением к концу линии и удалением с начала линии.

Затем существуют нелинейные структуры данных: словарь данных, упорядоченное и неупорядоченное множество. Все они внутренне нелинейны, порядок, в котором вы добавляете их, в сущности, не связан с порядком, в котором вы получаете их обратно. Словарь данных работает примерно так же, как настоящий бумажный словарь. У него есть ключ (слово, которое мы ищем) и значение (определение слова). Упорядоченное множество — это точно то же, что и словарь данных, содержащий ключи, но не значения, и отсортированный. Неупорядоченное множество — это просто «мешок» с объектами. Название немного сбивает с толку, потому что на самом деле они упорядочены, просто способ упорядочивания неудобен для человека. Все эти структуры идеальны для быстрого поиска.

Бо́льшую часть времени программистам приходится итеративно обрабатывать наборы данных.

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

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

Одна из самых частых задач в играх — поиск пути: необходимо найти маршрут из точки А в точку Б. Один из наиболее распространённых алгоритмов поиска пути — это A*. В алгоритме A* существует структура данных, содержащая частичные пути. Структура сортируется таким образом, чтобы наиболее вероятный частичный путь находился в передней части контейнера. Этот путь оценивается, и если он не является законченным, алгоритм превращает этот частичный путь в несколько частичных путей большего размера, а потом добавляет их в контейнер.

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

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

Динамический массив — выбор по умолчанию

В случае сомнений используйте динамический массив. В C++ это

vector

. В Java он называется

ArrayList

. В C# это

List

. В общем случае динамический массив — это то, что нужно. У него хорошая скорость для большинства операций, и неплохая скорость для всех остальных. Если вы выясните, что вам нужна другая структура данных, то с него перейти будет легче всего.

Стек — только один конец

Если вы используете добавление и удаление только с одного конца, то выбирайте стек. Это

stack

в C++,

Stack

в Java и C#. Существует много алгоритмов, использующих стековую структуру данных. Первый, который приходит мне в голову — это двухстековый калькулятор. Численные задачи, такие как «Ханойские башни», можно решить с помощью стека. Но, вероятно, вы не будете использовать эти алгоритмы в своей игре. Однако игровые инструменты часто выполняют парсинг данных, а парсеры активно используют стековые структуры данных, чтобы обеспечить правильное сочетание пар элементов. Если вы работаете с широким диапазоном типов ИИ, то стековая структура данных будет невероятно полезна для семейства автоматов, называемых автоматом с магазинной памятью (pushdown automaton).

Семейство очередей — первый вошёл, первый вышел.

Если вы добавляете и удаляете только с обоих концов, то используйте или очередь, или двухстороннюю очередь. В C++ это

queue

или

deque

. В Java можно использовать интерфейсы

Queue

или

Deque

, оба они реализованы с помощью

LinkedList

. В C# есть класс

Queue

, но нет встроенной Deque. Если вам нужно, чтобы важные события происходили первыми, но в остальном всё происходило по порядку, то выберите очередь с приоритетом. В C++ это

priority_queue

, в Java это

PriorityQueue

. В C# нужно реализовывать её самостоятельно.

Нелинейные структуры — быстрый поиск.

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

Связанный список — частые изменения с сохранением порядка

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

list

. В Java и C# это

LinkedList

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

Выбор подходящей структуры данных может сильно повлиять на скорость работы алгоритмов. Понимание основных структур данных, их преимуществ и недостатков, поможет вам в использовании наиболее эффективной структуры для любой задачи. Рекомендую вам в конечном итоге изучить их подробно. Полное изучение этих структур данных в колледже по специальности «Информатика» обычно занимает несколько недель. Надеюсь, вы уяснили основные структуры данных и сможете выбрать подходящую без долгой учёбы в колледже.

На этом статья завершается. Благодарю за чтение.

Искусство упаковки структур в C

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

Упаковка структур в C — старая, почти забытая, но все еще актуальная тема, если вы занимаетесь низкоуровневыми приложениями.

Кому предназначается данная статья

В этой статье я рассмотрю технику, с помощью которой можно уменьшить потребление памяти в программах на C путем реорганизации объявляемых структур. Вам потребуются базовые знания языка C.

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

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

Почему я написал эту статью

В 2013 мне пришлось использовать технику оптимизации, о которой я узнал более 20 лет назад и с тех пор практически не использовал. Мне понадобилось уменьшить потребление памяти программой, которая использовала тысячи, а иногда и десятки тысяч С-структур. Это был cvs-fast-export, и очень часто он рушился из-за недостатка памяти.

Существует способ значительно уменьшить потребление памяти в таких ситуациях путем грамотной реорганизации элементов структур. В моем случае программа стала потреблять на 40% меньше памяти и стала способна переработать бо́льшие репозитории без падений.

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

Этому есть вполне разумное объяснение. На всех курсах по информатике студентов приучают (и вполне обоснованно) избегать микрооптимизаций в пользу поиска лучшего алгоритма. Снижение цены на оборудование сделало охоту за байтами менее актуальной. И сегодня все реже встречается опыт глубокого погружения в различные архитектуры процессоров.

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

Выравнивание

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

На процессорах x86 и ARM примитивные типы не могут находиться в произвольной ячейке памяти. Каждый тип, кроме char, требует выравнивания. char может начинаться с любого адреса, однако двухбайтовый short должен начинаться только с четного адреса, четырехбайтный int или float — с адреса, кратного 4, восьмибайтные long или double — с адреса, кратного 8. Наличие или отсутствие знака значения не имеет. Указатели — 32-битные (4 байта) или 64-битные (8 байт) — также выравниваются.

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

Я специально упомянул, что это происходит на современных процессорах, потому что на некоторых старых процессорах небезопасный код (например, приведение некратного адреса в указатель на int и его использование) не просто замедлит работу процессора, он упадет с ошибкой о невалидной инструкции. Так вел себя, например, Sun SPARK. На самом деле такое поведение можно воспроизвести на x86 с правильным флагом (e18) в детерминированной ситуации.

Иногда можно дать указание процессору не использовать выравнивание, к примеру, с помощью директивы #pragma pack. (Не делайте этого без серьезной необходимости, потому что результатом будет более ресурсоемкий и медленный код.) Обычно это позволяет сохранить почти столько же памяти, сколько и описываемый мной способ.

Единственная хорошая причина использования #pragma pack — если вы хотите, чтобы расположение данных в памяти точно соответствовало требованиям низкоуровневого протокола или оборудования, как, например, порт с прямым доступом к памяти, и нарушение соглашения необходимо для работы программы. Если вы с этим столкнулись и не знакомы с тем, что описано в этой статье, я вам сочувствую, вы действительно в трудной ситуации.

Заполнение

Давайте посмотрим на простой пример расположения переменных в памяти. Допустим, у нас есть следующие строки в C-коде:

char *p;
char c;
int x;

Если вы не знакомы с выраниванием, вы можете предположить, что эти три значения располагаются в памяти последовательно. Таким образом, на 32-битной машине за четырьмя байтами указателя сразу расположится 1 байт char, а следом за ним четыре байта целого. На 64-битной машине отличие будет в размере указателя — 8 байт вместо 4.

А вот что происходит на самом деле (на x86, ARM или другом процессоре с выравниваением данных). Память для p начинается с адреса, кратного 4. Выравнивания указателя — самое строгое.

Следом за ним идет c. Но четырехбайтный x требует заполнения (padding) пустыми байтами. Происходит примерно то же самое, как если бы мы добавили еще одну переменную:

char *p /* 4 or 8 байт */
char c /* 1 байт */
char pad[3] /* 3 байт */
int x /* 4 байт */

Массив символов pad[3] в данном случае указывает на то, что мы заполняем пространство тремя пустыми байтами. Раньше это называли «мусор» («slop»).

Если тип x будет short, который занимает 2 байта, данные будут располагаться так:

char *p /* 4 or 8 байт */
char c /* 1 байт */
char pad[1] /* 1 байт */
short x /* 2 байт */

С другой стороны, на 64-битной машине эти данные расположатся в памяти следующим образом:

char *p /* 8 байт */
char c /* 1 байт */
char pad[7] /* 7 байт */
long x /* 8 байт */

У вас наверняка уже возник вопрос: а что, если переменная с меньшим размером будет объявлена в начале:

char c;
char *p;
int x;

Если мы представим расположение структуры в памяти как:

char c;
char pad1[M];
char *p;
char pad2[N];
int x;

что мы можем сказать о M и N?

Для начала, N в данном случае будет равно 0. Адрес x гарантированно будет выравниваться по адресу указателя p, выравнивание которого, в свою очередь, более строгое.

Значение M менее предсказуемо. Если компилятор расположит c в последнем байте машинного слова, следующий за ним байт (первый байт p) будет находиться в начале следующего машинного слова. В этом случае M будет равен 0.

Более вероятно, что c расположится в первом байте машинного слова. В этом случае размер M будет таким, чтобы p был выровнен по началу следующего слова — 3 на 32-битной машине, 7 на 64-битной.

Возможны промежуточные ситуации. M может быть от 0 до 7 (от 0 до 3 на 32-битной машине), потому что char может начинаться на любом байте машинного слова.

Если вы хотите, чтобы эти переменные занимали меньше памяти, вы можете поменять местами x и c.

char *p /* 8 байт */
long x /* 8 байт */
char c /* 1 байт */

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

Прежде чем мы коснемся структур, следует упомянуть массивы скалярных величин. На платформе с выравниванием данных массивы char/short/int/long или указателей располагаются в памяти последовательно, без заполнения.

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

Выравнивание и заполнение структур

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

Также, в C адрес структуры совпадает с адресом ее первого элемента, без сдвига в начале. Осторожно: в C++ классы, которые выглядят как структуры, могут нарушать это правило. (Это зависит от того, как устроен базовый класс и реализованы виртуальные методы, и может отличаться в различных компиляторах.)

(В случае сомнений вы можете использовать макрос offsetof() из ANSI C, с помощью которого можно рассмотреть расположение элементов струтур в памяти.)

Давайте рассмотрим следующую структуру:

struct foo1 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
    char pad[7]; /* 7 байт */
    long x; /* 8 байт */
};

На 64-битной машине любой экземпляр foo1 будет выравниваться по 8 байтам. Расположение в памяти идентично тому, которое мы получили бы, если бы в памяти находились скалярные величины. Однако, если мы перенесем c в начало, все поменяется:

struct foo2 {
    char c; /* 1 байт */
    char pad[7]; /* 7 байт */
    char *p; /* 8 байт */
    long x; /* 8 байт */
};

Если бы мы рассматривали отдельные переменные, c мог бы начинаться с произвольного байта и размер заполнения мог бы варьироваться. Но выравнивание структуры foo2 идет по указателю, c также должен быть выровнен по указателю. В итоге мы получаем фиксированное заполнение в 7 байт.

Рассмотрим теперь концевое заполнение структур. Общее правило такое: компилятор заполняет все место до адреса следующей структуры так, чтобы она была выровнена по самому длинному элементу структуры. sizeof() возвращает размер структуры с учетом заполнения.

Например, на 64-битном x86 процессоре или ARM:

struct foo3 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
};

struct foo3 singleton;
struct foo3 quad[4];

Вы можете подумать, что sizeof(struct foo3) вернет 9, однако верным ответом будет 16. Адрес следующей структуры будет (&p)[2]. Таким образом, в массиве из 4 элементов у каждого будет заполнение в 7 пустых байт, поскольку первые элементы каждой структуры должны быть выровнены в данном случае по 8 байтам. Расположение в памяти такое, какое было бы, если бы структура была объявлена следующим образом:

struct foo3 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
    char pad[7];
};

Для сравнения, рассмотрим такой пример:

struct foo4 {
    short s; /* 2 байт */
    char c; /* 1 байт */
    char pad[1];
};

Поскольку s требует 2-байтового выравнивания, следующий адрес будет отстоять от c на один байт, вся структура foo4 будет заполнена одним пустым байтом в конце и sizeof(struct foo4) вернет 4.

Выравнивание битовых полей и вложенных структур

Битовые поля позволяют объявить переменные, занимающие меньшую, чем char память, вплоть до 1 бита. Например:

struct foo5 {
    short s;
    char c;
    int flip:1;
    int nybble:4;
    int septet:7;
};

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

С точки зрения компилятора битовые поля структуры foo5 выглядят как двухбайтовые значения, из 16 бит которых используются только 12. Место после них заполняется так, чтобы размер структуры был кратен sizeof(short) — размеру наибольшего элемента.

struct foo5 {
    short s; /* 2 байт */
    char c; /* 1 байт */
    int flip:1; /* всего 1 бит */
    int nybble:4; /* всего 5 бит */
    int septet:7; /* всего 12 бит */
    int pad1:4; /* всего 16 бит = 2 байт */
    char pad2; /* 1 байт */
};

Ограничения битового поля на выход за пределы машинного слова приведет к тому, что на 32-битной машине первые две структуры поместятся в одно или два слова, но третья (foo8) займет три слова, причем у последнего будет занят только первый бит. С другой стороны, структура foo8 поместится в одно 64-битное слово.

struct foo6 {
    int bigfield:31; /* Начало первого 32-битного слова */
    int licodelefield:1;
};

struct foo7 {
    int bigfield1:31; /* Начало первого 32-битного слова */
    int licodelefield1:1;
    int bigfield2:31; /* Начало второго 32-битного слова */
    int licodelefield2:1;
};

struct foo8 {
    int bigfield1:31; /* Начало первого 32-битного слова */
    int bigfield2:31; /* Начало второго 32-битного слова */
    int licodelefield1:1;
    int licodelefield2:1; /* Начало третьего 32-битного слова */
};

Важная деталь: если элементом вашей структуры является структура, она также будет выравниваться по самому длинному скаляру. Например:

struct foo9 {
    char c;
    
    struct foo9_inner {
        char *p;
        short x;
    } inner;
};

char *p во внутренней структуре требует выравнивания по указателю как во внутренней, так и во внешней структуре. Реальное расположение в памяти на 64-битной машине будет примерно такое:

struct foo9 {
    char c; /* 1 байт*/
    char pad1[7]; /* 7 байт */

    struct foo9_inner {
        char *p; /* 8 байт */
        short x; /* 2 байт */
        char pad2[6]; /* 6 байт */
    } inner;
};

Эта структура дает нам подсказку, где и как мы можем сэкономить память переупаковкой. Из 24 байт 13 заполняющие. Это больше 50% потерянного места!

Реорганизация структур

Теперь, когда мы знаем как и зачем компилятор выравнивает данные в памяти, посмотрим, как мы можем уменьшить количество «мусора». Это и будет называться «искусство упаковки структур».

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

Наиболее простой способ избавиться от мусора — расположить элементы структуры по уменьшению размера. Таким образом, указатели будут располагаться в начале, поскольку на 64-битной машине они займут по 8 байт. Потом 4-битовые int; 2-байтовые short; затем char.

Рассмотрим, например, односвязный список:

struct foo10 {
    char c;
    struct foo10 *p;
    short x;
};

Или, если мы явно укажем заполняющие байты:

struct foo10 {
    char c; /* 1 byte */
    char pad1[7]; /* 7 bytes */
    struct foo10 *p; /* 8 bytes */
    short x; /* 2 bytes */
    char pad2[6]; /* 6 bytes */
};

Всего 24 байта. Однако, если мы перепишем следующим образом:

struct foo11 {
    struct foo11 *p;
    short x;
    char c;
};

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

struct foo11 {
    struct foo11 *p; /* 8 bytes */
    short x; /* 2 bytes */
    char c; /* 1 byte */
    char pad[5]; /* 5 bytes */
};

Переупаовкой мы добились сокращения занимаемого места с 24 до 16 байт. Это может показаться незначительным, но что, если у вас односвязный список из 200 тысяч элементов? Эффект растет быстро, особенно на встроенных системах с ограниченым объемом памяти или в критических участках ядра ОС.

Замечу, что реорганизация не всегда позволяет сохранить память. Если мы применим этот прием к нашей структуре foo9, мы получим следующее:

struct foo12 {
    struct foo12_inner {
        char *p; /* 8 bytes */
        int x; /* 4 bytes */
    } inner;
    
    char c; /* 1 byte*/
};

Явно укажем заполнение:

struct foo12 {
    struct foo12_inner {
        char *p; /* 8 bytes */
        int x; /* 4 bytes */
        char pad[4]; /* 4 bytes */
    } inner;

    char c; /* 1 byte*/
    char pad[7]; /* 7 bytes */
};

Размер foo12 — также 24 байта, потому что c выравнивается по внутренней структуре. Для уменьшения занимаемой памяти нам придется изменить дизайн самой структуры данных.

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

Выравнивания перечислений и целочисленных типов

Использование перечислений («enumerated types») вместо директивы #define — отличная идея, если отладчик может их отличить от целых чисел. Перечисления гарантировано совместимы с целочисленным типом, однако стадарт C не специфицирует, с помощью какого именно типа они реализованы.

Будьте осторожны: несмотря на то, что обычно в перечислениях используется int, в некоторых компиляторах по умолчанию может использоваться short, long или char. Также в компиляторе может быть предусмотрена директива или опция для явного указания размера.

Тип long double также может создавать некоторые проблемы. Некоторые платформы реализуют его с помощью 80 бит, некоторые — 128 бит, некоторые 80-битные реализации заполняют место после данных до 96 или 128 бит.

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

Наконец, иногда на x86 Linux-машинах double может быть исключением: 8-байтный double может требовать выравнивания по 4 байтам в структуре, несмотря на то, что стоящий отдельно выравнивается по 8 байтам. Это зависит от компилятора и его опций.

Читаемость кода и локальность кэша

Несмотря на то, что реорганизация структур — самый простой способ избавиться от мусора в памяти, он не всегда будет оптимальным. Необходимо также учесть читаемость кода и локальность кэша («cache locality»).

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

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

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

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

Если в вашем коде есть конкурентный (concurrent) доступ к данным, появляется третья проблема: «cache line bouncing». Для минимизации трафика в шине следует располагать данные так, чтобы чтение из одного кэша и запись в другой производились с меньшим промежутком.

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

Другие способы упаковки

Реорганизация структур лучше всего работает вместе с другими способами уменьшения их размера. Например, если у вас есть несколько булевых флагов, вы можете привести их к битовым полям и упаковать их в структуру, которая в противном случае располагалась бы в памяти с зазорами.

Это освободит вам столько памяти, что эффект от уменьшения количества промахов в кэше перевесит увеличенное время доступа к данным.

В общем случае старайтесь уменьшить размер полей с данными. В cvs-fast-export, например, я воспользовался знанием от том, что CVS и RCS репозитории не существовали до 1982 года. Я заменил 64-битное Unix-время time_t (начинающееся с 1970) на 32-битное время с начальной точкой 1982-01-01T00:00:00; это должно покрыть даты до 2118 года. (Если вы применяете подобный трюк, не забудьте проверять границы устанавливаемого значения, чтобы избежать трудноуловимых багов.)

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

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

Инструменты

Компилятор clang имеет опцию -Wpadded, которая будет генерировать сообщения о заполнении.

Я слышал много хороших отзывов о программе pahole, хотя сам ее не использовал. Она работает вместе с компилятором и позволяет генерировать отчет, описывающий реальное расположение данных в памяти.

Доказательства и исключения

Исходный код небольшой программы, которая иллюстрирует вышеописанное можно скачать здесь: packtest.c.

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

Следующий уровень владения данной техникой — знать, где и когда ожидать, что правила будут нарушены. В то время, когда я изучал ее (ранние 80-е), людей, которые не освоили эту технику называли «жертвами VAX» («all-the-world’s-a-VAX syndrome»). Помните, что не все компьютеры в мире — PC.

Полезные ссылки

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

A Guide to Undefined Behavior in C and C++
Time, Clock, and Calendar Programming In C

_{Источник: The Lost Art of C Structure Packing (Eric S. Raymond, [email protected])}

Основные структуры данных.

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

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

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

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

Вполне вероятно, читателю приходилось сталкиваться со структурами данных непосредственно в информатике, например, с теми, что встроены в язык программирования. Часто они именуются типами данных. К таковым относятся: массивы, числа, строки, файлы и т. д.

Методы хранения информации, называемые «простыми», т. е. неделимыми на составные части, предпочтительнее изучать вместе с конкретным языком программирования, либо же глубоко углубляться в суть их работы. Поэтому здесь будут рассмотрены лишь «интегрированные» структуры, те которые состоят из простых, а именно: массивы, списки, деревья и графы.

Массивы.

Массив – это структура данных с фиксированным и упорядоченным набором однотипных элементов (компонентов). Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива. Так, например, чаще всего встречаются одномерные (вектора) и двумерные (матрицы) массивы. Первые имеют один индекс, вторые – два.

Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A[i, j], где i – номер строки, j – номер столбца.

В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.

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

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

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

Списки.

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

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

Односвязный список

В односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.

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

Двусвязный список

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

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

Кольцевой список

Помимо рассмотренных видов списочных структур есть и другие способы организации данных по типу «список», но они, как правило, во многом схожи с разобранными, поэтому здесь они будут опущены.

Кроме различия по связям, списки делятся по методам работы с данными. О некоторых таких методах сказано далее.

Стек

Стек.

Стек характерен тем, что получить доступ к его элементом можно лишь с одного конца, называемого вершиной стека, иначе говоря: стек – структура данных, функционирующая по принципу LIFO (last in — first out, «последним пришёл — первым вышел»).

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

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

Если бы было, например 6 элементов, а вставить конкретный элемент требовалось также в пятую ячейку, то исключить бы пришлось уже два элемента.

Очередь.

Структура данных «Очередь» использует принцип организации FIFO (First In, First Out — «первым пришёл — первым вышел»). В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры.

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

Очередь

Дек.

Дек (deque — double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.

Дек

Эта структура одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов списка.

Графы.

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами (узлами), а линии – ребрами (дугами).

Как показано на рисунке различают два основных вида графов: ориентированные и неориентированные. В первых ребра являются направленными, т. е. существует только одно доступное направление между двумя связными вершинами, например из вершины 1 можно пройти в вершину 2, но не наоборот. В неориентированном связном графе из каждой вершины можно пройти в каждую и обратно. Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

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

Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.

Деревья.

Неупорядоченное дерево

Дерево как математический объект это абстракция из соименных единиц, встречающихся в природе. Схожесть структуры естественных деревьев с графами определенного вида говорит о допущении установления аналогии между ними. А именно со связанными и вместе с этим ациклическими (не имеющими циклов) графами. Последние по своему строению действительно напоминают деревья, но в чем то и имеются различия, например, принято изображать математические деревья с корнем расположенным вверху, т. е. все ветви «растут» сверху вниз. Известно же, что в природе это совсем не так.

Поскольку дерево это по своей сути граф, у него с последним многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры.

Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

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

Представление данных в рассмотренной структуре выгодно в случае наличия у информации явной иерархии. Например, работа с данными о биологических родах и видах, служебных должностях, географических объектах и т. п. требует иерархически выраженной структуры, такой как математические деревья.

Похожие записи:

структур данных — GeeksforGeeks

• Последнее обновление:
  18 июн, 2021 г.

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

Например, мы можем сохранить список элементов с одним и тем же типом данных, используя структуру данных array .

Структура данных массива

Эта страница содержит подробные руководства по различным структурам данных (DS) с тематическими проблемами.

Темы:

Обзор:

Связанный список:

Односвязный список:

1. Введение в связанный список
2. Связанный список
4. в сравнении с массивом
5. Удаление связанного списка (удаление заданного ключа)
6. Удаление связанного списка (удаление ключа в заданной позиции)
7. Подход программиста, рассматривающий как массив vs.Связанный список
8. Найти длину связного списка (итеративный и рекурсивный)
9. Как написать функции C, которые изменяют указатель заголовка связного списка?
10. Поменять местами узлы в связанном списке без обмена данными
11. Обратить связанный список
12. Объединить два отсортированных связанных списка
13. Сортировка слияния для связанных списков
14. Обратить связанный список в группах заданного размера
15. Обнаружить и удалить петлю в Связанный список
16. Сложение двух чисел, представленных связными списками | Set 1
17. Rotate a Linked List
18. Generic Linked List in C

Circular Linked List:

1. Circular Linked List Introduction and Applications,
2. Circular Singly Linked List Insertion <
3. Обход круговых связанных списков
4. Разделение кругового связного списка на две половины
5. Сортированная вставка для кругового связанного списка

Двусвязный список:

1. Введение и вставка двусвязного списка
2. Удаление узла в двусвязном списке
3. Обратный двусвязный список
4. Большая проблема рекурсии древовидного списка.
5. QuickSort в двусвязном списке
6. Сортировка слиянием для двусвязного списка

Все статьи связанного списка
Викторина в связанном списке
Практика кодирования в связанном списке
Последние статьи в связном списке

Стек:

1. Введение в стек
2. Преобразование инфикса в постфикс с использованием стека
3. Оценка выражения Postfix
4. Обратное преобразование строки с помощью стека
5. Реализация двух стеков в массиве
6. Проверка сбалансированных скобок в выражении
7. Next Greater Element
8. Next Greater Element
9. стек с использованием рекурсии
10. Сортировка стека с использованием рекурсии
11. Проблема диапазона запасов
12. Разработка и реализация специальной структуры данных стека
13. Реализация стека с использованием очередей
14. Создание стека с операциями над средним элементом
15. Как эффективно реализовать k стеков в одном массиве?
16. Сортировка стека с использованием рекурсии

Викторина в стеке
Все статьи в стеке
Практика кодирования в стеке
Последние статьи в стеке

Очередь:

1. Введение в очередь и связанный список реализации массива
2. Реализация очереди
3. Приложения структуры данных очереди
4. Введение в приоритетную очередь
5. Deque (Введение и приложения)
6. Реализация Deque с использованием кругового массива
7. Реализация очереди с использованием стеков
8. Найдите первый круговой тур, который посещает все бензонасосы
9. Максимум всех подмассивов размером k
10. Интересный метод генерации двоичных чисел от 1 до n
11. Как эффективно реализовать k очередей в одном массиве?

Тест по очереди
Все статьи в очереди
Практика кодирования в очереди
Последние статьи по очереди

Двоичное дерево:

1. Введение в двоичное дерево
2. Свойства двоичного дерева
3. Типы двоичного дерева
4. Лемма о подтверждении связи и интересные свойства дерева
5. Перечисление двоичного дерева
6. Приложения древовидной структуры данных
7. Обходы по дереву
8. Сравнение BFS и DFS для двоичного дерева

Обход дерева порядка

10. Диаметр двоичного дерева
11. Неупорядоченный обход дерева без рекурсии
12. Неупорядоченный обход дерева без рекурсии и без стека!
13. Многопоточное двоичное дерево
14. Максимальная глубина или высота дерева
15. Если вам даны две последовательности обхода, можете ли вы построить двоичное дерево?
16. Клонировать двоичное дерево со случайными указателями
17. Построить дерево из заданных обходов в порядке и в порядке
18. Максимальная ширина двоичного дерева
19. Печать узлов на расстоянии k от корня
20. Печать предков данного узла в двоичном дереве
21. Проверка если двоичное дерево является поддеревом другого двоичного дерева
22. Подключить узлы на том же уровне

Тест по двоичному дереву
Тест по обходам двоичного дерева
Все статьи о двоичном дереве
Практика кодирования двоичного дерева
Последние статьи о дереве

Дерево двоичного поиска:

1. Поиск и вставка в BST
2. Удаление из BST
3. Минимальное значение в дереве двоичного поиска
4. Неупорядоченный предшественник и преемник для данного ключа в BST
5. Проверить, есть ли двоичное дерево является BST или нет
6. Самый низкий общий предок в двоичном дереве поиска.
7. Последователь порядкового номера в дереве двоичного поиска
8. Найдите k-й наименьший элемент в BST (Статистика заказов в BST)
9. Объедините два BST с ограниченным дополнительным пространством
10. Два узла BST поменяны местами, исправьте BST
11. Floor и Ceil из BST
12. Преобразование на месте сортированной DLL в сбалансированный BST
13. Найдите пару с заданной суммой в сбалансированном BST
14. Общее количество возможных деревьев двоичного поиска с n ключами
15. Объединение двух сбалансированных деревьев двоичного поиска
16. Преобразование двоичного дерева в двоичное дерево поиска

Тест по деревьям двоичного поиска
Тест по деревьям сбалансированного двоичного поиска
Все статьи о дереве двоичного поиска
Практика кодирования в дереве двоичного поиска
Последние статьи по BST

Куча:

1. Двоичная куча
2. Почему двоичная куча предпочтительнее BST для приоритетной очереди?
3. Биномиальная куча
4. Куча Фибоначчи
5. Сортировка кучи
6. K-й самый большой элемент в массиве
7. Сортировка почти отсортированного массива /
8. Дерево турниров (дерево победителей) и двоичная куча

Все статьи
Викторина по куче
Практика кодирования в куче
Последние статьи о куче

Хеширование:

1. Введение в хеширование
2. Отдельная цепочка для обработки коллизий
3. Открытая адресация для обработки коллизий
4. Печать двоичного дерева в вертикальном порядке
5. Найти, является ли массив подмножеством другого массива
6. Объединение и пересечение двух связанных списков
7. Найти пару с заданной суммой
8. Проверить, содержит ли данный массив повторяющиеся элементы на расстоянии k друг от друга
9. Найти маршрут из заданного списка билетов
10. Найдите количество сотрудников на каждого сотрудника

Тест по хешированию
Все статьи по хешированию
Практика кодирования по хешированию
Последние статьи по хешированию

График:

Введение, DFS и BFS:

1. Первый график и его представления
2. Обход по ширине График
3. Обход в первую очередь по глубине для графа
4. Приложения поиска по глубине
5. Приложения обхода в ширину
6. Цикл обнаружения в направленном графике
7. Цикл обнаружения в неориентированном графике
8. Цикл обнаружения

в неориентированном графике

9. Самый длинный путь в направленном ациклическом графе
10. Топологическая сортировка
11. Проверить, является ли данный граф двудольным или нет
12. Задача змейки и лестницы
13. Минимизировать денежный поток среди заданной группы друзей, которые занимали деньги друг у друга
14. Буггл (Найдите все возможные слова на доске символов)
15. Назначьте d направления к ребрам, чтобы ориентированный граф оставался ациклическим

Все статьи о структуре данных графа
Викторина по графику
Викторина по обходам графа
Тест по кратчайшим путям графа
Тест по графу Минимальное связующее дерево
Практика кодирования на графике
Недавние Статьи на графике

Расширенная структура данных:

Расширенные списки:

1. Двусвязный список с эффективным использованием памяти
2. Связанный список XOR — Двусвязный список с эффективным использованием памяти | Set 1
3. Связанный список XOR — эффективный с точки зрения памяти двусвязный список | Set 2
4. Пропустить список | Набор 1 (Введение)
5. Самоорганизующийся список | Набор 1 (Введение)
6. Развернутый связанный список | Набор 1 (Введение)

Дерево сегментов:

1. Дерево сегментов | Набор 1 (сумма заданного диапазона)
2. Дерево сегментов | Установить 2 (запрос минимального диапазона)
3. Ленивое распространение в дереве сегментов
4. Постоянное дерево сегментов | Набор 1 (Введение)

Все статьи о дереве сегментов
Trie:

1. Trie | (Вставка и поиск)
2. Trie | (Удалить)
3. Соответствие самого длинного префикса — решение на основе Trie в Java
4. Печать уникальных строк в заданной логической матрице
5. Как реализовать кэш обратного просмотра DNS?
6. Как реализовать кэш прямого просмотра DNS?

Все статьи о Trie
Двоичное индексированное дерево:

1. Двоичное индексированное дерево
2. Двумерное двоичное индексированное дерево или дерево Фенвика
3. Двоичное индексированное дерево: обновления диапазонов и запросы точек
4. Двоичное дерево индекса : Обновление диапазона и запросы диапазона

Все статьи о двоичном индексированном дереве
Суффиксный массив и Суффиксное дерево :

1. Суффиксный массив Введение
2. Суффиксный массив nLogn Алгоритм

для построения алгоритма

kas массива LCP из массива суффиксов

3. Введение в суффиксное дерево
4. Построение суффиксного дерева Укконена — часть 1
5. Построение суффиксного дерева Укконена — часть 2
6. Построение суффиксного дерева Укконена — часть 3
8. Строительство дерева укконена
9. — часть 4 Построение суффиксного дерева Укконена — Часть 5
10. Построение дерева суффиксов Укконена — Часть 6
11. Обобщенное дерево суффиксов
12. Построение линейного массива суффиксов времени с использованием дерева суффиксов
13. Проверка подстроки
14. Поиск всех шаблонов
15. Самая длинная повторяющаяся подстрока,

самая длинная подстрока,

, самая длинная подстрока


Все статьи о дереве суффиксов
Дерево AVL:

1. Дерево AVL | Набор 1 (Вставка)
2. AVL Tree | Набор 2 (Удаление)
3. AVL с повторяющимися ключами

Дерево Splay:

1. Дерево Splay | Набор 1 (Поиск)
2. Splay Tree | Набор 2 (вставка)

Дерево B:

1. Дерево B | Набор 1 (Введение)
2. B-Tree | Набор 2 (Вставка)
3. B-Tree | Набор 3 (Удалить)

Красно-черное дерево:

1. Красно-черное дерево Введение
2. Красно-черное дерево Вставка.
3. Удаление красно-черного дерева
4. Программа для вставки красно-черного дерева


Все статьи о самобалансирующихся BST

Дерево измерений K:

1. Дерево KD (поиск и вставка)
2. Дерево KD (минимум поиска)
3. Дерево KD (удаление)

Другие:

1. Treap (рандомизированное двоичное дерево поиска)
2. Дерево троичного поиска
3. Дерево интервалов LRU
5. Сортировка чисел, хранящихся на разных машинах
6. Найдите k наиболее часто встречающихся слов из файла
7. Для заданной последовательности слов распечатайте все анаграммы вместе
8. Дерево турниров (Дерево победителей) и двоичная куча
9. Деревья решений — Подделка (Подделка ) Головоломка с монетами (Головоломка с 12 монетами)
10. Стек спагетти
11. Структура данных для словаря и средства проверки орфографии?
12. Декартово дерево
13. Сортировка декартового дерева
14. Разреженное множество
15. Центроидная декомпозиция дерева
16. Дерево Гомори-Ху

Последние статьи по расширенным структурам данных.

Массив:

1. Поиск, вставка и удаление в несортированном массиве
2. Поиск, вставка и удаление в отсортированном массиве
3. Напишите программу для переворота массива
4. Лидеры в массиве
5. Учитывая массив A [] и число x, проверьте наличие пары в A [] с суммой x
6. Элемент большинства
7. Найдите число, встречающееся нечетное количество раз
8. Непрерывный подмассив наибольшей суммы
9. Найдите недостающее число
10. Найдите элемент в отсортированном и повернутом массиве
11. Объединить массив размера n в другой массив размера m + n
12. Медиана двух отсортированных массивов
13. Программа для вращения массива
14. Алгоритм обращения для вращения массива
15. Алгоритм перестановки блоков для массива вращение
16. Максимальная сумма, при которой нет двух соседних элементов
17. Сортировка элементов по частоте | Набор 1
18. Инверсии счетчика в массиве

Все статьи о массиве
Практика кодирования в массиве
Викторина по массиву
Практика кодирования в массиве
Последние статьи по массиву

Матрица:

1. Поиск в сортированной матрице по строкам и столбцам
2. Печать заданной матрицы в спиральной форме
3. Вопрос о логической матрице
4. Печать уникальных строк в заданной логической матрице
5. Квадратная подматрица максимального размера со всеми единицами
6. Вывести уникальные строки в заданной логической матрице
7. Inplace M x N матрица транспонировать | Обновлено
8. Динамическое программирование | Установить 27 (прямоугольник максимальной суммы в 2D-матрице)
9. Умножение матриц Штрассена
10. Создание матрицы с чередующимися прямоугольниками O и X
11. Распечатать все элементы в отсортированном порядке из сортированной по строкам и столбцам матрицы
12. Дана квадратная матрица nxn , найти сумму всех подквадратов размера kxk
13. Подсчитать количество островов, где каждый остров разделен по строкам и столбцам
14. Найти общий элемент во всех строках заданной матрицы, отсортированной по строкам

Все статьи о матрице
Практика кодирования на матрице
Последние статьи о матрице.

Разное:

1. Часто задаваемые вопросы о структуре данных на собеседовании | Набор 1
2. Структура данных для n элементов и операций O (1)
3. Дерево выражений

Курсы Geeksforgeeks:

1. Курсы базового языка [C ++ / JAVA / Python]
Изучите любой язык программирования из поцарапать и понять все его основные концепции для прочной основы программирования самым простым способом с помощью курсов GeeksforGeeks Language Foundation — Java Foundation | Python Foundation | C ++ Foundation

2. Занятия для компьютерных фанатов в прямом эфире
Получите интерактивные онлайн-классы, ориентированные на собеседование, по структуре данных и алгоритмам из любого географического места, чтобы изучить и освоить концепции DSA для улучшения ваших навыков решения проблем и программирования, а также для прохождения собеседования в любой производственной компании. Классы для компьютерных фанатов: Live Session

3. Полная подготовка к собеседованию
Выполните все свои потребности по подготовке к собеседованию в одном месте с помощью полного курса подготовки к собеседованию , который предоставляет вам все необходимые материалы для подготовки к любому продукту. , сервисная или начинающая компания по самым доступным ценам.

4. DSA Self-Paced
Начните изучать структуры данных и алгоритмы, чтобы подготовиться к собеседованию с ведущими ИТ-гигантами, такими как Microsoft, Amazon, Adobe и т. Д., С DSA Self-Paced Course , где вы сможете учиться и освоите DSA от начального до продвинутого уровня, и это тоже в вашем собственном темпе и удобстве.

5. Курсы для конкретных компаний — Amazon, Microsoft, TCS и Wipro
Взломайте интервью любой продуктовой гигантской компании, специально подготовив вопросы, которые эти компании обычно задают в ходе собеседований по программированию.Обратитесь к GeeksforGeeks Специальные курсы компании: серия тестов Amazon SDE и т. Д.

Мои личные заметки
arrow_drop_up

Структура данных связанного списка — GeeksforGeeks

• Последнее обновление:
  16 июля 2021 г.

Практические проблемы в связанном списке
Последние статьи в связанном списке

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

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

Темы:

Односвязный список:

1. Введение в связанный список
2. Связанный список и массив
3. Вставка связанного списка
4. Удаление связанного списка (удаление заданного ключа)
5. Удаление связанного списка (удаление связанного списка) ключ в заданной позиции)
6. Напишите функцию для удаления связанного списка
7. Найдите длину связанного списка (итеративный и рекурсивный)
8. Поиск элемента в связанном списке (итеративный и рекурсивный)
9. Напишите функцию для получения N-й узел в связанном списке
10. N-й узел от конца связанного списка
11. Распечатать середину данного связанного списка
12. Напишите функцию, которая подсчитывает, сколько раз данное int встречается в связном списке
13. Обнаружить цикл в связанном списке
14. Найти длину цикла в связанном списке
15. Функция проверки, является ли односвязный список палиндромом
16. Удаление дубликатов из отсортированного связанного list
17. Удалить дубликаты из несортированного связного списка
18. Поменять местами узлы в связанном списке без обмена данными
19. Попарно поменять местами элементы данного связанного списка
20. Переместить последний элемент в начало данного связанного списка
21. Пересечение двух отсортированных связанных Списки
22. Точка пересечения двух связанных списков.
23. QuickSort в односвязном списке
24. Разделение четных и нечетных узлов в связанном списке
25. Обратный связанный список

Подробнее >>

Циркулярный связанный список:

1. Циклический связанный список Введение и приложения,
2. Обход кругового связного списка
3. Разделение кругового связного списка на две половины
4. Сортированная вставка для кругового связанного списка
5. Проверка, является ли связанный список круговым связным списком
6. Преобразование двоичного дерева в круговой список с двумя двойными связями
7. Циркуляр Односвязный список | Вставка
8. Удаление из кругового связного списка
9. Круговая очередь | Набор 2 (реализация кругового связного списка)
10. Подсчет узлов в круговом связном списке
11. Джозефус Круг с использованием кругового связного списка
12. Преобразование односвязного списка в круговой связанный список
13. Круговой связанный список | Комплект 1 (Введение и приложения)
14. Циркулярный связанный список | Set 2 (Traversal)
15. Реализация Deque с использованием кругового массива
16. Обмен первым и последним узлами в круговом связном списке

Подробнее >>

Двусвязный список:

1. Двусвязный список Введение и вставка
2. Удалить узел в двусвязном списке
3. Обратный двусвязный список
4. Большая проблема рекурсии древовидного списка.
5. Копировать связанный список со следующим и арбитражным указателем
6. QuickSort в двусвязном списке
7. Поменять местами K-й узел с начала на K-й узел от конца в связанном списке
8. Сортировка слиянием для двусвязного списка
9. Создать двусвязный список из a Ternary Tree
10. Найти пары с заданной суммой в двусвязном списке
11. Вставить отсортированное значение в отсортированный двусвязный список
12. Удалить узел двусвязного списка в заданной позиции
13. Подсчитать тройки в отсортированном двусвязном списке, чьи сумма равна заданному значению x
14. Удаление дубликатов из отсортированного двусвязного списка
15. Удаление всех вхождений данного ключа в двусвязном списке
16. Удаление дубликатов из несортированного двусвязного списка
17. Сортировка биотонического двусвязного списка
18. Сортировка отсортированного двусвязного списка
19. Преобразование заданного двоичного дерева в двусвязный список | Установить
20. Программа для определения размера двусвязного списка
21. Отсортированная вставка в двусвязный список с указателями на начало и конец
22. Арифметика с большими числами с использованием двусвязного списка
23. Повернуть двусвязный список по N узлам
24. Очередь приоритетов с использованием двусвязной list
25. Переворачивает двусвязный список в группы заданного размера
26. Двуручный связанный список | Набор 1 (Введение и вставка)
27. Двухконтактный связанный список | Набор 2 (Удаление)

Подробнее >>

Разное:

1. Пропустить список | Набор 1 (Введение)
2. Пропустить список | Набор 2 (вставка)
3. Список пропуска | Набор 3 (поиск и удаление)
4. Обратный стек без использования дополнительного места в O (n)
5. Интересный метод печати обратного связанного списка
6. Представление структур данных несвязанного набора в виде связанного списка
7. Поиск подсписка (поиск в связанный список в другом списке)
8. Как вставить элементы в список C ++ STL?
9. Развернутый связанный список | Набор 1 (Введение)
10. Подход программиста к рассмотрению Array vs.Связанный список
11. Как написать функции C, которые изменяют указатель заголовка связного списка?
12. Учитывая отсортированный связанный список, как вы будете вставлять отсортированный
13. Можем ли мы отменить связанный список менее чем за O (n)?
14. Практические вопросы для связанного списка и рекурсии
15. Создайте связанный список с максимальной суммой из двух отсортированных связанных списков, имеющих несколько общих узлов
16. Если в односвязном списке имеется только указатель на узел, который нужно удалить, как его удалить ?
17. Почему быстрая сортировка предпочтительна для массивов и сортировка слиянием для связанных списков?
18. Квадратный (n) -й узел в связанном списке
19. Найдите дробный (или n / k-ый) узел в связанном списке
20. Найдите модульный узел в связанном списке
21. Создайте связанный список из 2D-матрицы
22. Найдите наименьшие и наибольшие элементы в односвязном списке
23. Расположите узлы согласных и гласных в связанном списке
24. Разделение связного списка вокруг заданного значения и Если мы не заботимся о том, чтобы сделать элементы списка «стабильными»
25. Изменить содержание связанного списка

Быстрые ссылки:

Курсы Geeksforgeeks:

1.Курсы Language Foundation [C ++ / JAVA / Python]
Изучите любой язык программирования с нуля и поймите все его основные концепции для создания прочной основы программирования самым простым способом с помощью курсов GeeksforGeeks Language Foundation — Java Foundation | Python Foundation | C ++ Foundation

2. Занятия для компьютерных фанатов в прямом эфире
Получите интерактивные онлайн-классы, ориентированные на собеседование, по структуре данных и алгоритмам из любого географического места, чтобы изучить и освоить концепции DSA для улучшения ваших навыков решения проблем и программирования, а также для взлома интервью любой продуктовой компании — Geeks Classes: Live Session

3. Подготовка к интервью по самым доступным ценам.

4. DSA Self Paced
Начните изучать структуры данных и алгоритмы, чтобы подготовиться к собеседованию с ведущими ИТ-гигантами, такими как Microsoft, Amazon, Adobe и т. Д.с DSA Self-Paced Course , где вы сможете изучить и освоить DSA от начального до продвинутого уровня, и это тоже в вашем собственном темпе и удобстве.

5. Курсы для конкретных компаний — Amazon, Microsoft, TCS и Wipro
Взломайте интервью любой продуктовой гигантской компании, специально подготовив вопросы, которые эти компании обычно задают в ходе собеседований по программированию. Обратитесь к специальным курсам GeeksforGeeks для компании: серия тестов Amazon SDE и т. Д.

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

Мои личные заметки
arrow_drop_up

Обзор структур данных | Набор 1 (линейные структуры данных)

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

1. Массив
2. Связанный список
3. Стек
4.Очередь

Массив
Массив — это структура данных, используемая для хранения однородных элементов в смежных местах. Перед сохранением данных необходимо указать размер массива.

Пусть размер массива равен n.
Время доступа: O (1) [Это возможно, потому что элементы
                      хранятся в смежных местах]
Время поиска: O (n) для последовательного поиска:
               O (log n) для двоичного поиска [если массив отсортирован]
Время вставки: O (n) [В худшем случае происходит вставка
                     происходит в начале массива и
                     требует сдвига всех элементов]
Время удаления: O (n) [в худшем случае происходит удаление
                     происходит в начале массива и
                     требует сдвига всех элементов] 

Пример: Например, допустим, мы хотим сохранить оценки всех учащихся в классе, мы можем использовать массив для их хранения.Это помогает сократить использование количества переменных, поскольку нам не нужно создавать отдельную переменную для оценок по каждому предмету. Доступ ко всем отметкам можно получить, просто пройдя по массиву.

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

Типы связного списка:
1. Односвязный список: В этом типе связанного списка каждый узел хранит адрес или ссылку на следующий узел в списке, а последний узел имеет следующий адрес или ссылку как NULL.Например, 1-> 2-> 3-> 4-> NULL

2. Двусвязный список: В этом типе связанного списка есть две ссылки, связанные с каждым узлом, одна из опорных точек на следующий узел и один к предыдущему узлу. Преимущество этой структуры данных в том, что мы можем перемещаться в обоих направлениях, и для удаления нам не нужен явный доступ к предыдущему узлу. Например. NULL23-> NULL

3. Циклический связанный список : Циклический связанный список — это связанный список, в котором все узлы соединены в круг.В конце нет NULL. Циклический связанный список может быть односвязным списком или двусвязным списком. Преимущество этой структуры данных в том, что любой узел можно сделать стартовым. Это полезно при реализации круговой очереди в связанном списке. Например. 1-> 2-> 3-> 1 [Следующий указатель последнего узла указывает на первый]

Время доступа к элементу: O (n)
Время поиска элемента: O (n)
Вставка элемента: O (1) [Если мы находимся в позиции
                                где мы должны вставить
                                элемент]
Удаление элемента: O (1) [Если мы знаем адрес узла
                               предыдущий узел, который будет
                               удалено] 

Пример: Рассмотрим предыдущий пример, в котором мы создали массив оценок студента.Теперь, если в курс добавляется новый предмет, его оценки также добавляются в массив оценок. Но размер массива был фиксированным, и он уже заполнен, поэтому он не может добавлять новые элементы. Если мы сделаем массив размером намного больше, чем количество субъектов, возможно, что большая часть массива останется пустой. Мы сокращаем потери пространства. Формируется связанный список, который добавляет узел только при вводе нового элемента. С помощью связанного списка также становится проще вставлять и удалять.
Один большой недостаток связанного списка — невозможен произвольный доступ.С массивами мы можем получить доступ к i-му элементу за O (1) раз. В связанном списке это занимает Θ (i) времени.

Стек
Стек или LIFO (последний пришел, первый ушел) — это абстрактный тип данных, который служит коллекцией элементов с двумя основными операциями: push, который добавляет элемент в коллекцию, и pop, который удаляет последний добавленный элемент. В стеке операции push и pop выполняются на одном конце, который является вершиной стека. Это может быть реализовано с использованием как массива, так и связанного списка.

Вставка: O (1)
Удаление: O (1)
Время доступа: O (n) [наихудший случай]
Вставка и удаление разрешены на одном конце. 

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

Очередь
Очередь или FIFO (первый пришел — первый ушел) — это абстрактный тип данных, который служит набором элементов с двумя основными операциями: постановка в очередь, процесс добавления элемента в коллекцию (элемент — это добавлено с задней стороны) и dequeue, процесс удаления первого добавленного элемента. (Элемент снимается с лицевой стороны). Это может быть реализовано с использованием как массива, так и связанного списка.

Вставка: O (1)
Удаление: O (1)
Время доступа: O (n) [наихудший случай] 

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

Циклическая очередь Преимущество этой структуры данных состоит в том, что она уменьшает потери пространства в случае реализации массива, поскольку вставка (n + 1) -го элемента выполняется по 0-му индексу, если он пуст.

Обзор структур данных | Набор 2 (двоичное дерево, BST, куча и хэш)

Эта статья предоставлена ​​ Abhiraj Smit .Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Структура данных массива — GeeksforGeeks

Массив — это набор элементов, хранящихся в непрерывных ячейках памяти. Идея состоит в том, чтобы хранить вместе несколько предметов одного типа. Это упрощает вычисление позиции каждого элемента, просто добавляя смещение к базовому значению, то есть местоположению в памяти первого элемента массива (обычно обозначаемого именем массива).

Это изображение можно рассматривать как вид верхнего уровня лестницы, где вы находитесь у основания лестницы. Каждый элемент можно однозначно идентифицировать по их индексу в массиве (аналогично тому, как вы могли идентифицировать своих друзей по шагу, на котором они были в приведенном выше примере).

1. Поиск, вставка и удаление в несортированном массиве
2. Поиск, вставка и удаление в отсортированном массиве
3. Учитывая массив A [] и число x, проверьте пару в A [] с суммой x
4. Поиск в массиве, где смежные отличаются не более чем на k
5. Найти общие элементы в трех отсортированных массивах
6. Найти позицию элемента в отсортированном массиве бесконечных чисел
7. Найти единственный повторяющийся элемент от 1 до n-1
8. Найти элемент, который появляется один раз
9. Максимальная сумма подмассива без определенных элементов
10. Максимальная сумма равновесия в массиве
11. Индекс равновесия массива
12. Лидеры в массиве
13. Верхний предел в отсортированном массиве
14. Элемент большинства
15. Проверка на мажоритарный элемент в отсортированном массиве
16. Проверить, имеет ли массив мажоритарный элемент
17. Метод двух указателей
18. Найдите пиковый элемент
19. Найдите два повторяющихся элемента ентов в заданном массиве
20. Найти фиксированную точку в заданном массиве
21. Найти подмассив с заданной суммой
22. Максимальная сумма триплетов в массиве
23. Триплет наименьшей разности из трех массивов
24. Найти триплет, сумма которого равна заданному значению
25. Найти все триплеты с нулевой суммой

Подробнее >>

Матрица:

Подробнее >>

Разное:

Ссылки:

Geeksforgeeks Courses:

97 9.Курсы Language Foundation [C ++ / JAVA / Python]
Изучите любой язык программирования с нуля и поймите все его основные концепции для создания прочной основы программирования самым простым способом с помощью курсов GeeksforGeeks Language Foundation — Java Foundation | Python Foundation | C ++ Foundation

2. Занятия для компьютерных фанатов в прямом эфире
Получите интерактивные онлайн-классы, ориентированные на собеседование, по структуре данных и алгоритмам из любого географического места, чтобы изучить и освоить концепции DSA для улучшения ваших навыков решения проблем и программирования, а также для взлома интервью любой продуктовой компании — Geeks Classes: Live Session

3. Подготовка к интервью по самым доступным ценам.

4. DSA Self Paced
Начните изучать структуры данных и алгоритмы, чтобы подготовиться к собеседованию с ведущими ИТ-гигантами, такими как Microsoft, Amazon, Adobe и т. Д.с DSA Self-Paced Course , где вы сможете изучить и освоить DSA от начального до продвинутого уровня, и это тоже в вашем собственном темпе и удобстве.

5. Курсы для конкретных компаний — Amazon, Microsoft, TCS и Wipro
Взломайте интервью любой продуктовой гигантской компании, специально подготовив вопросы, которые эти компании обычно задают в ходе собеседований по программированию. Обратитесь к специальным курсам компании GeeksforGeeks: серия тестов Amazon SDE и т. Д.

Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по электронной почте по адресу review-team @ geeksforgeeks.орг. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное или хотите поделиться дополнительной информацией по теме, обсуждаемой выше

Мои личные заметки
arrow_drop_up

Понимание структур данных в C и C ++

Чтобы стать опытным программистом, важно иметь представление о структурах данных.

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

Мы выпустили видеокурс на YouTube-канале freeCodeCamp.org, который научит вас структурам данных и способам их реализации на C или C ++.

Курс разработан Harsha и Animesh из MyCodeSchool. MyCodeSchool — один из старейших программных каналов на YouTube. В настоящее время Animesh работает инженером в поисковой команде Google.Харша был индийским программистом с самым высоким рейтингом на платформе соревновательного программирования Top Coder.

MyCodeSchool имеет вдохновляющую и печальную историю. Вы можете прочитать об этом здесь, в статье Куинси Ларсона.

Вот темы, затронутые в этом курсе:

• Введение в структуры данных
• Список как абстрактный тип данных
• Введение в связанный список
• Массивы и связанные списки
• Связанный список — реализация на C / C ++
• Связанный список в C / C ++ — вставка узла в начало
• Связанный список в C / C ++ — вставить узел в позицию n
• Связанный список в C / C ++ — удалить узел в позиции n
• Обратить связанный список — итерационный метод
• Распечатать элементы связанного списка в прямом и обратном порядке с использованием рекурсии
• Обратить связанный список с помощью рекурсии
• Введение в двусвязный список
• Двусвязный список — реализация на C / C ++
• Введение в стек
• Реализация массива стеков
• Реализация стеков связным списком
• Обратить строку или связанный список с помощью стека.
• Проверка сбалансированности скобок с использованием стека
• Инфикс, префикс и постфикс
• Оценка префиксных и постфиксных выражений с использованием стека
• Инфикс в постфикс с использованием стека
• Введение в очереди
• Реализация очереди в виде массива
• Реализация очереди в виде связанного списка
• Введение в деревья
• Двоичное дерево
• Двоичное дерево поиска
• Двоичное дерево поиска — реализация на C / C ++
• Реализация BST — выделение памяти в стеке и куче
• Найти минимальный и максимальный элемент в двоичном дереве поиска
• Найти высоту двоичного дерева
• Обход двоичного дерева — стратегии в ширину и в глубину
• Двоичное дерево: обход порядка уровней
• Обход двоичного дерева: предварительный порядок, порядок следования, последующий порядок
• Проверить, является ли двоичное дерево деревом двоичного поиска или нет
• Удалить узел из двоичного дерева поиска
• Неупорядоченный преемник в бинарное дерево поиска
• Введение в графы
• Свойства графов
• Часть представления графа 01 — список ребер
• Часть представления графа 02 — матрица смежности
• Часть представления графа 03 — список смежности

курс на freeCodeCamp.org YouTube канал (10 часов просмотра).

Изучите структуры данных и алгоритмы

---

Зачем изучать DSA?

• Напишите оптимизированный и масштабируемый код — Получив знания о различных структурах данных и алгоритмах, вы можете определить, какую структуру данных и алгоритм выбрать в различных условиях.
• Эффективное использование времени и памяти — Знание структур данных и алгоритмов поможет вам писать коды, которые работают быстрее и требуют меньше памяти.
• Лучшие возможности трудоустройства — Вопросы о структурах данных и алгоритмах часто задают на собеседованиях в различных организациях, включая Google, Facebook и т. Д.

---

Как узнать структуру данных и алгоритмы?

Узнайте DSA из Programiz

Programiz предлагает полную серию простых в использовании руководств по DSA вместе с подходящими примерами. Эти учебные пособия предназначены для абсолютных новичков, которые хотят погрузиться в сферу компьютерного программирования.

Учите DSA по книгам

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

Вот несколько книг, которые мы рекомендуем.

• Введение в алгоритмы, Томас Х. Кормен — это одна из лучших книг по алгоритмам, в которой подробно рассматривается широкий спектр алгоритмов
• Алгоритмы, Роберт Седжвик — это ведущий учебник по алгоритмам, широко используемый в колледжах и университетах
• Искусство программирования, Дональд Э.Knuth — эта книга считается лучшей, если вы знакомы с предметом и ищете более глубокое понимание

Изучите DSA через визуализацию

Если у вас есть некоторое представление о структуре данных и алгоритмах, в Data Structure Visualizations есть отличный ресурс, который позволяет вам учиться с помощью анимации.

структур данных | Учебник DS

Учебник

Data Structures (DS) предоставляет базовые и расширенные концепции структуры данных.Наше руководство по структуре данных предназначено для новичков и профессионалов.

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

— это способ хранения и организации данных для эффективного использования.

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

Что такое структура данных?

Имя структуры данных указывает само на то, что упорядочивает данные в памяти. Существует много способов организации данных в памяти, поскольку мы уже видели одну из структур данных, т.е.е., массив на языке C. Массив — это набор элементов памяти, в которых данные хранятся последовательно, то есть один за другим. Другими словами, мы можем сказать, что массив хранит элементы непрерывно. Эта организация данных осуществляется с помощью массива структур данных. Есть и другие способы организации данных в памяти. Давайте посмотрим на различные типы структур данных.

Структура данных — это не какой-либо язык программирования, такой как C, C ++, java и т. Д. Это набор алгоритмов, которые мы можем использовать на любом языке программирования для структурирования данных в памяти.

Для структурирования данных в памяти было предложено n алгоритмов, и все эти алгоритмы известны как абстрактные типы данных. Эти абстрактные типы данных представляют собой набор правил.

Типы структур данных

Есть два типа структур данных:

• Примитивная структура данных
• Непримитивная структура данных

Примитивная структура данных

Примитивные структуры данных являются примитивными типами данных.Int, char, float, double и pointer — это примитивные структуры данных, которые могут содержать одно значение.

Непримитивная структура данных

Непримитивная структура данных делится на два типа:

• Линейная структура данных
• Нелинейная структура данных

Линейная структура данных

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

Когда один элемент связан с числом n элементов, известным как нелинейная структура данных. Лучший пример — деревья и графы. В этом случае элементы располагаются случайным образом.

Мы кратко обсудим вышеупомянутые структуры данных в следующих темах. Теперь мы увидим общие операции, которые мы можем выполнять с этими структурами данных.

Структуры данных также можно классифицировать как:

• Статическая структура данных: Это тип структуры данных, размер которой выделяется во время компиляции.Поэтому максимальный размер фиксирован.
• Динамическая структура данных: Это тип структуры данных, размер которой выделяется во время выполнения. Таким образом, максимальный размер может быть гибким.

Основные операции

Основные или общие операции, которые могут выполняться со структурами данных:

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

Какая структура данных?

Структура данных — это способ организации данных для эффективного использования. Здесь мы использовали слово эффективно, как в пространстве, так и во времени.Например, стек — это ADT (абстрактный тип данных), который для реализации использует либо массивы, либо структуру данных связанного списка. Таким образом, мы приходим к выводу, что нам нужна некоторая структура данных для реализации конкретного ADT.

ADT сообщает , что нужно сделать , а структура данных сообщает , как это должно быть сделано. Другими словами, мы можем сказать, что ADT дает нам план, а структура данных обеспечивает часть реализации. Теперь возникает вопрос: как узнать, какую структуру данных использовать для конкретного ADT ?.

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

Преимущества структур данных

Преимущества структуры данных:

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

---

Индекс структур данных

---

Основы DS

Массив DS

Связанный список DS

Стек DS

Очередь DS

DS Дерево

DS График

DS Поиск

DS Сортировка

Вопросы для интервью

Программы односвязных списков

Программы с двусвязным списком

Циркулярные связанные списки программ

Древовидные программы

---

Необходимое условие

Перед изучением структуры данных вы должны иметь базовые знания C.

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

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

Комментарий *

Имя *

Email *

Сайт