В современных языках, таких как C++, python или java, мы использовали множество встроенных структур данных, таких как массивы, стеки, очереди, и мы никогда не сталкивались с проблемой типа «тип данных XYZ несовместим со структурой данных ABC». строки не могут быть созданы. Независимо от того, является ли тип данных примитивным или определяемым пользователем, структура данных ABC всегда работала.

В динамически типизированных языках, таких как Python, мы можем напрямую написать

my_list = [100, 3.14, 'hello']

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

Stack<Integer> s = new Stack<Integer>();      // Stack for Integers
Stack<Character> s = new Stack<Character>();  // Stack for Character
Stack<CustomClass> s = new Stack<CustomClass>(); // Stack for custom classes

Как мы видим, с помощью дженериков мы можем использовать один и тот же класс (стек) с разными типами данных.

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

  • Указатели и как они работают
  • Работа с массивами
  • Недооцененный тип данных в C
  • Выполнение

Указатели и как они работают:

Указатели — это ссылки на переменные.

Указатели указывают на адрес, где хранится переменная.

Указатель хранит адрес переменной, в которой хранится значение.

Синтаксис объявления указателя: datatype* name;

  • int a — это переменная, которая содержит значение 100 и хранится по адресу 1000.
  • int* a_address — это переменная (указатель), которая содержит адрес переменной a.
#include<stdio.h>
int main() {
    int a = 10;
    int* a_addr;
    a_addr = &a;
    printf("%d %d\n", &a, a_addr);
    printf("%d %d", a, *a_addr);
}
>> 6422296 6422296
>> 10 10
  • & — унарный оператор, который дает адрес операнда, таким образом, &a дает адрес переменной a.
  • * — унарный оператор, который возвращает значение переменной, расположенной по адресу, указанному ее операндом. Таким образом, *a_addr дает значение переменной a.

Работа с массивами

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

Когда мы пишем int arr[]; мы создаем указатель, указывающий на место, где хранится 0-й элемент массива. Поскольку arr является указателем на первый элемент массива, доступ к первому элементу массива можно получить как *arr, а к i-му элементу массива можно получить доступ как *(arr + i).

#include <stdio.h>
int main() {
    int i;
    int arr[] = {1, 2, 3, 4};
    for(i=0; i<4; i++) {
        printf("%d ", *(arr + i));
    }
}
>> 1 2 3 4

Недооцененный тип данных в C

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

void displayArray(int[] arr)

Указатель void — это очень мощный инструмент, который можно использовать для создания универсальной структуры данных. Пустой указатель, объявленный void* <var_name>, может указывать/ссылаться на любой тип данных.

Выполнение

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

#include <stdio.h>
int main() {
    void *arr[3];
    int a = 100;
    float f = 3.14;
    char s[] = "hello";

    arr[0] = &a;
    arr[1] = &f;
    arr[2] = s;

    printf("Integer = %d\\n", *(int *)arr[0]);
    printf("Float = %f\\n", *(float *)arr[1]);
    printf("String = %s\\n", arr[2]);
}
>> Integer = 100
>> Float = 3.140000
>> String = hello

Таким образом, мы создали массив, похожий на массив в начале этого блога my_list = [100, 3.14, 'hello']

Что делать, если я хочу создать динамический общий массив?

Чтобы создать динамический массив указателей void, нам нужно использовать двойной указатель void…

void **arr; Здесь мы будем динамически выделять arr с помощью malloc следующим образом:

void **arr;
arr = (void **)malloc(n*sizeof(void *));
// This will create an array of ‘n’ void pointers.

Благодаря этому мы узнали, как создать общую структуру данных, которая может хранить данные любого типа, будь то int, float, string, struct, enum или даже массив. Эти знания можно использовать для разработки пользовательской библиотеки структур данных, которая не ограничивается типом данных в C.