Как проверить указатель C на предмет, указывает ли он на структуру

struct node * всегда либо NULL, либо указывает на какой-то struct node, если только вы не сделали в своем коде что-то противозаконное. Если вы все сделали правильно, ответ на вопрос всегда «да». Если вы сделали что-то неправильно, вы вызвали неопределенное поведение, и поэтому задавать вопрос бесполезно.

Как проверить указатель C на предмет, указывает ли он на структуру

Короче говоря, для этого вы используете свой код. И логика. Что касается языка, вы не можете ничего о нем знать. Указатель — это просто переменная. Его содержимое: адрес. Это может быть NULL, это может быть действительный адрес, его вообще нельзя инициализировать. После free указатель все равно будет указывать на несуществующие данные...

вернемся к коду

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

struct node {
 int data;
 node next;
}

Вы не имеете. Это просто struct для узла. Узел — это не список, список — это не узел.

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

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

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

struct node *insert_sorted (struct node *nodes, 
  int d) {
  // todo
}

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

Ну, в Java нет понятия указателей. Вы можете проверить, построена вещь или нет.

Один из способов увидеть проблему — представить, что вы хотите вставить данные в список. Изначально не должно существовать даже понятия узла. Абстракция здесь не очень хорошая. Учитывать

    int so_insert ( int data, List* list);

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

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

ПРИМЕР: абстракция для списка

Это возможные узлы И список:

typedef struct st_node
{   struct st_node* prev;  // links
    struct st_node* next;
    int data;  // data
} Node;

typedef struct
{
    size_t size;
    Node*  tail;
    Node*  head;
} List;  // a (possibly empty) list of nodes

Node на самом деле это узел, List — это список, содержащий необходимые метаданные: заголовок, хвост и размер.

Некоторые операции над List:

List* so_create();
List* so_destroy(List*);
int   so_insert(int, List*);
int   so_push_back(int, List*);
int   so_push_front(int, List*);
int   so_print(List*, const char* msg);
int   so_sort(List*);
// helper for multi insert
int so_multi_insert(
    List* list, const unsigned N, ...);

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

Об операциях:

• push_back и push_front — это имена C++ для вставки в конец и начало списка.
• insert здесь используется порядок возрастания
• поскольку мы можем вставлять по порядку, а также в начале и в конце, также реализована функция sort
• для удобства вставки здесь также имеется вариант multi_insert
• print принимает необязательный заголовок, чтобы избежать классического множества printf вызовов при тестировании

Пример: v1.c

#include "List.h"
int main(void)
{
    size_t N       = 10;
    List*  my_list = so_create();
    srand(240627);
    for (int i = 0; i < N; i += 1)
        so_push_back(rand() % 1000, my_list);
    so_print(my_list, "\nelements back-inserted\n");

    for (int i = 0; i < N; i += 1)
        so_push_front(rand() % 1000, my_list);
    so_print(my_list, "\n elements inserted at front\n");
    so_sort(my_list);
    so_print(my_list, "\nList is now sorted\n");
    so_multi_insert(my_list, 4, -1, -2, -3, -4);
    so_push_front(-5, my_list);
    so_push_back(-6, my_list);
    so_print(my_list, "\n(-6..-1) inserted\n");
    so_sort(my_list);
    so_print(my_list, "\nList is again sorted\n");
    so_destroy(my_list);
    return 0;
}

Он вызывает множество функций для вставки данных спереди и сзади, а затем сортировки списка.

вывод для первого примера

list created

elements back-inserted
    #10 elements in list.
    head element: 161
    tail element: 413

161 31 680 991 329 746 705 839 886 413

[-----]


 elements inserted at front
    #20 elements in list.
    head element: 491
    tail element: 413

491 269 901 863 944 886 243 318 81 682 161 31 680 991 329 746 705 839 886 413

[-----]


List is now sorted
    #20 elements in list.
    head element: 31
    tail element: 991

31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991

[-----]


(-6..-1) inserted
    #26 elements in list.
    head element: -5
    tail element: -6

-5 -4 -3 -2 -1 31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991 -6

[-----]


List is again sorted
    #26 elements in list.
    head element: -6
    tail element: 991

-6 -5 -4 -3 -2 -1 31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991

[-----]

list deleted

второй пример: v2.c

#include "List.h"
#include <stdlib.h>

int main(void)
{
    List* my_list = so_create();
    srand(240628);
    // here use use insert to test ordering
    const int N = 20;
    for (int i = 0; i < N; i += 1)
        so_insert(rand()%1000, my_list);
    so_print(my_list, "\nsorted\n");
    so_destroy(my_list);
    return 0;
}

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

list created

sorted
    #20 elements in list.
    head element: 21
    tail element: 913

21 100 125 164 248 265 282 286 310 534 558 629 673 689 777 779 817 876 912 913

[-----]

list deleted

заголовок List.h

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct st_node
{   struct st_node* prev;  // links
    struct st_node* next;
    int data;  // data
} Node;

typedef struct
{
    size_t size;
    Node*  tail;
    Node*  head;
} List;  // a (possibly empty) list of nodes

List* so_create();
List* so_destroy(List*);
int   so_insert(int, List*);
int   so_push_back(int, List*);
int   so_push_front(int, List*);
int   so_print(List*, const char* msg);
int   so_sort(List*);
// helper for multi insert
int so_multi_insert(
    List* list, const unsigned N, ...);

возможная реализация List.c

#include "List.h"

// helper to sort
Node* so_locate_at(List*, size_t);

List* so_create()
{
    List* list = malloc(sizeof(List));
    if (list == NULL) return NULL;
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    fprintf(stderr, "list created\n");
    return list;
}

List* so_destroy(List* del)
{
    if (del == NULL) return NULL;  // no list
    for (size_t i = 0; i < del->size; i += 1)
    {  // delete nodes, 1 by 1
        Node* save = del->head->next;
        free(del->head);
        del->head = save;
    };
    free(del);  // delete list
    fprintf(stderr, "list deleted\n");
    return NULL;
}

int so_insert(int item, List* list)
{
    int result = so_push_back(item, list);
    if (result != 0) return result;  // could not insert...
    if (list->size == 1) return 0;   // was the 1st
    // at least 2
    Node* p = list->tail;
    for (size_t i = 0; i < list->size - 1; i += 1)
    {
        if (p->data >= p->prev->data)
        {
            p = p->prev;
            continue;
        };
        // swap the nodes
        int save      = p->data;
        p->data       = p->prev->data;
        p->prev->data = save;
        p             = p->prev;
    }
    return 0;
}

// return a pointer to the node at position 'pos'
// or 'NULL'. 'pos'starts at 0
Node* so_locate_at(List* list, size_t pos)
{
    if (list == NULL) return NULL;
    if (list->size < 1 + pos) return NULL;
    Node* nd = list->head;
    for (size_t i = 0; i < pos; i += 1) nd = nd->next;
    return nd;
}

// insert all words in the list, sorted
int so_multi_insert(List* list, const unsigned N, ...)
{
    if (list == NULL) return -1;
    va_list args;
    va_start(args, N);
    for (size_t i = 0; i < N; i += 1)
        so_insert(va_arg(args, int), list);
    va_end(args);
    return 0;
}

// inserts 'item' at the tail of the list
int so_push_back(int item, List* list)
{
    if (list == NULL) return -1;  // no list
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL) return -2;  // no alloc
    node->data = item;
    if (list->size == 0)  // first node
    {
        node->next = NULL;
        node->prev = NULL;
        list->size = 1;
        list->head = node;
        list->tail = node;
        return 0;  // 1st node
    };
    node->next       = NULL;
    node->prev       = list->tail;
    list->tail->next = node;
    list->tail       = node;
    list->size += 1;
    return 0;
}

// inserts 'Item' at the head of the list
int so_push_front(int item, List* list)
{
    if (list == NULL) return -1;  // no list
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL) return -2;  // no alloc
    node->data = item;
    if (list->size == 0)
    {
        node->next = NULL;
        node->prev = NULL;
        list->size = 1;
        list->head = node;
        list->tail = node;
        return 0;  // 1st node
    };
    node->prev       = NULL;
    node->next       = list->head;
    list->head->prev = node;
    list->head       = node;
    list->size += 1;
    return 0;
}

int so_print(List* list, const char* msg)
{
    if (list == NULL)
    {
        fprintf(stderr, "No valid list!\n");
        return 0;
    }
    if (list->size == 0) return 0;
    if (msg != NULL) printf("%s", msg);
    printf(
        "\
    #%llu elements in list.\n\
    head element: %d\n\
    tail element: %d\n\n",
        list->size, list->head->data, list->tail->data);
    Node* p = list->head;
    for (size_t i = 0; i < list->size; i += 1)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n\n[-----]\n\n");
    return 0;
}

int so_sort(List* list)
{
    if (list == NULL) return -1;
    if (list->size < 2) return -2;
    Node* p = list->tail;
    for (Node* q = list->tail; q != list->head; q = q->prev)
        for (Node* p = q->prev; p != NULL; p = p->prev)
            if (q->data < p->data)
            {  // swap the nodes
                int save = p->data;
                p->data  = q->data;
                q->data  = save;
            };
    return 0;
}

код для insert

Здесь insert очень просто, так как по сути у нас есть List структура данных и операции изолированы:

int so_insert(int item, List* list)
{
    int result = so_push_back(item, list);
    if (result != 0) return result;  // could not insert...
    if (list->size == 1) return 0;   // was the 1st
    // at least 2
    Node* p = list->tail;
    for (size_t i = 0; i < list->size - 1; i += 1)
    {
        if (p->data >= p->prev->data)
        {
            p = p->prev;
            continue;
        };
        // swap the nodes
        int save      = p->data;
        p->data       = p->prev->data;
        p->prev->data = save;
        p             = p->prev;
    }
    return 0;
}

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

код для sort

Вставка в начале или в конце нарушит порядок, поэтому необходима функция sort. Вот простой:

int so_sort(List* list)
{
   if (list == NULL) return -1;
   if (list->size < 2) return -2;
   Node* p = list->tail;
   for (Node* q = list->tail; q != list->head; q = q->prev)
       for (Node* p = q->prev; p != NULL; p = p->prev)
           if (q->data < p->data)
           {  // swap the nodes
               int save = p->data;
               p->data  = q->data;
               q->data  = save;
           };
   return 0;
}

Это простая реализация сортировки вставками.