Умные способы реализации различных структур данных в структурах C & data, которые следует использовать чаще

Question

Каковы некоторые умные (не обычные) способы реализации структур данных в C и какие структуры данных следует использовать чаще?

Например, каков наиболее эффективный способ (создание минимальных издержек) для реализации ориентированного и циклического графа с взвешенными ребрами в C?
Я знаю, что мы можем хранить расстояния в массиве, как это сделано здесь , но какие еще есть способы для реализации такого рода графика?

Answer 1

Отвечая на ваш первый вопрос, я рекомендую инкапсулировать ваши структуры с помощью непрозрачных указателей (a.k.a Handles).

Например, вы можете объявить дескриптор связанного списка (в данном случае MS-подобного именования):

typedef struct linked_list_t* HLINKEDLIST;

Мы предполагаем, что connected_list_t является универсальным (состоит из пустых указателей).

Таким образом, вы можете скрыть, что такое «дескриптор» связанного списка или в какой форме реализовано (скрытие информации):

HLINKEDLIST LinkedListCreate();
LinkedListAdd(LLELEMENT v);
LinkedListCopy(HLINKEDLIST dst, const HLINKEDLIST src);

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

Связанные типы также могут быть определены для удобства (и для использования ограниченного сокрытия информации, доступного в C). например: тип элемента связанного списка может быть определен как

typedef void* LLELEMENT;

Есть хорошие книги по структурам данных в C, которые можно проверить. Это хорошо: http://www.amazon.com/Interfaces-Implementations-Techniques-Creating-Reusable/dp/0201498413

Также обратите внимание, что LLELEMENT фактически совместим с void *, так что если вы определяете другой тип def как:

typedef void* SYSTEMDATA;

SYSTEMDATA совместима с LLELEMENT, поэтому компилятор не будет жаловаться на:

int QuerySystemData(SYSTEMDATA* sd);

и звонят:

QuerySystemData(lle);

где lle типа LLELEMENT.

Эта проверка типа может быть принудительно инкапсулирована в простые элементы в структурах. Если я не помню плохо, объявление STRICT в программе, использующей windows.h, делает дескрипторы более безопасными по типу (несовместимыми между). Часто встречаются следующие определения:

typedef struct __HWND 
{ 
int __handle; 
} __HWND; 

typedef __HWND* HWND; 

Если бы простые определения были:

typedef int HWND;
typedef int HBITMAP;

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