Указатели на другие структуры внутри структуры

Question

Мой лектор представил следующий фрагмент кода с недостаточным объяснением того, что он представляет.

typedef struct _s { 
    int   value; 
    struct _s *next; 
} STACKITEM; 

STACKITEM *stack = NULL; 

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

2. Я не понимаю, почему структура объявлена ​​typedef. Это кажется излишним по следующим причинам:

Типичная структура гласит следующее.

struct struct_format_name { 
members; 
} individual_struct_object_name; 

Таким образом, мы объявили объект структурой и присвоили этому формату структуры имя _s. Так в чем смысл использования typedef? За исключением ключевого слова typedef, это тот же формат, который вы бы использовали для объявления любой структуры.

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

Я подозреваю, что указатель на структуру, указывающую на структурированный формат, как это сделано выше, может указывать на ЛЮБАЯ структуру этого формата? Однако указатель на структуру, указывающую на конкретную структуру, может указывать только на определенную структуру, а не на другие структуры того же формата?

Answer 1

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

Это общая реализация C структуры данных, известной как singly linked list, где каждый элемент в списке явно указывает на следующий элемент. В этом случае каждый экземпляр struct _s указывает на другой экземпляр struct _s, например, так:

+---+---+   +---+---+  +---+---+ 
| | | -----> | | | -----> | | | 
+---+---+   +---+---+  +---+---+ 
            ^^
            | | 
            | +---- next 
            +-------- value 

Вы можете реализовать stack используя сшитую структуру списка, который является тем, что делает ваш инструктор. Операция «push» будет динамически создавать новый STACKITEM, сохранить целое значение для него и сделать эту новую STACKITEM главой списка (a.k.a. вершина стека). Указатель stack всегда указывает на первый элемент в списке (NULL, если список пуст).

stack: ||| 

push(&stack, 1); 

     +---+---+ 
stack: | 1 | |---||| 
     +---+---+ 

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

push(&stack, 2); 

     +---+---+ +---+---+ 
stack: | 2 | |--->| 1 | |---||| 
     +---+---+ +---+---+ 

push(&stack, 3); 

     +---+---+ +---+---+ +---+---+ 
stack: | 3 | |--->| 2 | |--->| 1 | |---||| 
     +---+---+ +---+---+ +---+---+ 

Код будет выглядеть что-то вроде

void push(STACKITEM **stack, int value) 
{ 
    STACKITEM *newItem = malloc(sizeof *newItem); 
    if (newItem) 
    { 
    newItem->value = value; 
    newItem->next = *stack; // newItem now points to former top of stack 
    *stack   = newItem; // newItem is now the top of the stack 
    } 
} 

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

void pop(STACKITEM **stack) 
{ 
    STACKITEM *top = *stack; 
    if (top) 
    { 
    *stack = top->next; 
    free(top); 
    } 
} 

pop(&stack); 

     +---+---+ +---+---+ 
stack: | 2 | |--->| 1 | |---||| 
     +---+---+ +---+---+ 

pop(&stack); 

     +---+---+ 
stack: | 1 | |---||| 
     +---+---+ 

pop(&stack); 

stack: ||| 

Я не понимаю, почему структура объявлена ​​typedef.Это представляется излишним по следующим причинам:

typedef выполняет две основные цели:

1. имена Simplify комплекс типа
2. абстрагироваться от деталей реализации

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

ПРИМЕЧАНИЕ. Ваш инструктор не должен использовать ведущее подчеркивание в имени тега; идентификаторы с ведущими символами подчеркивания зарезервированы для использования при реализации.

Answer 2

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

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

typedef позволяет вам называть его коротким именем struct_format_name вместо struct struct_format_name.

Answer 3

Это называется связанным списком. Указатель next - это то, что позволяет вам просматривать список, указав каждый элемент на следующий, и имея последний, next указывает на NULL, чтобы вы знали, что находитесь в конце. См. https://en.wikipedia.org/wiki/Linked_list. Вы на самом деле не храните структуру, вы сохраняете указатель на следующий элемент, считаете его как массив, но где вместо выравниваемых элементов каждый из них указывает на следующий элемент, используя его адрес вместо ,

Что касается указателя next, то причина, объявленная с помощью ключевого слова struct, заключается в том, что тип STACKITEM еще не существует (он определен после определения структуры).

Answer 4

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

Невозможно определить тип, который может указывать только на конкретный объект.

Ваш код и код вашего лектора не выполняют одно и то же, поэтому нет избыточности.
Вы определяете тип и объект; они определяют тип и другое имя для этого типа.
(Это звучит немного, как вы путаете типы с объектами.)

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

И ваш вариант очень a типичный.
Типы чаще всего определяются глобально, в то время как переменные объявляются как можно более локальными.