C Soyut veri türü ile çift bağlantılı liste

Question

C'ye çift bağlantılı listeye ihtiyacım var, fakat farklı tipler için olmalı. C++ 'da bunun için şablonlar kullanıyoruz. Soyut öğelerle çift bağlantılı liste için C örneğini nerede bulabilirim. çoğu durumda özellikle void * -

genellikle işaretçileri kullanılarak yapılır C keyfi veri işleme sizi

Answer 1

Yapabileceğiniz birkaç yaklaşım vardır; bunlardan biri, ADT'nize bir void* depolamayı içerir.

Bağlantılı bir listeyi her zaman bir ağrının olduğunu fark ettim, çünkü bu listeyi kendi başına ayrı olarak yönetmek zorundasınız. Başka bir deyişle, bir düğümü tahsis etmek için, hem düğümü hem de yükünü ayrı ayrı yerleştirmeniz gerekir (ve bunları silme işleminde de temizlemeyi unutmayın). Şimdi ölçekli değişken görünmüyor

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    char payload[1]; 
} tNode; 

ama en böylece bir yapıya tahsis edelim:

ben geçmişte kullandığınız

Bir yaklaşım gibi 'değişken büyüklükte' bir yapıya sahip olmaktır

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    char Name[30]; 
    char Addr[50]; 
    char Phone[20]; 
} tNode; 

:

typedef struct { 
    char Name[30]; 
    char Addr[50]; 
    char Phone[20]; 
} tPerson; 
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson)); 

Artık tüm niyet ve amaçlar için, şöyle bir düğüme sahip

veya ([n]n bayt anlamına gelir) grafik şeklinde:

+------------+ 
| prev[4] | 
+------------+ 
| next[4] | 
+------------+ +-----------+ 
| payload[1] | | Name[30] | <- overlap 
+------------+ +-----------+ 
       | Addr[50] | 
       +-----------+ 
       | Phone[20] | 
       +-----------+ 

doğru yükü gidermek için nasıl varsayarak vardır. hat sadece (tNode türü) payload karakter adresini atan döküm

node->prev = NULL; 
node->next = NULL; 
tPerson *person = &(node->payload); // cast for easy changes to payload. 
strcpy (person->Name, "Richard Cranium"); 
strcpy (person->Addr, "10 Smith St"); 
strcpy (person->Phone, "555-5555"); 

gerçek tPerson yük tipi bir adres olarak aşağıdaki gibidir: bu yapılabilir.Bu yöntemi kullanarak

, size yapısını daha fazla gibi yaparsanız, bir düğümünde istediğiniz herhangi yük türünü, her düğüm bile farklı yük türleri taşıyabilir:

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    int payloadType;  // Allows different payload type at each node. 
    char payload[1]; 
} tNode; 

ve depolamak için payloadType kullanmak Yükün gerçekte ne olduğuna dair bir gösterge.

ile görülebileceği gibi bu, bu alan atık etmediğini bir birlik üzerinde bir avantaja sahiptir aşağıdadır: 96 byte Listedeki bir tamsayı türünü depolamak her zaman boşa

union { 
    int fourBytes; 
    char oneHundredBytes[100]; 
} u; 

(4 baytlık bir tamsayı için).

tNode'daki yük kapasitesi, bu düğümün taşıdığı yük türünü kolayca algılamanıza olanak tanır, böylece kodunuz nasıl işleneceğine karar verebilir. Sen çizgisinde bir şey kullanabilirsiniz:

#define PAYLOAD_UNKNOWN  0 
#define PAYLOAD_MANAGER  1 
#define PAYLOAD_EMPLOYEE 2 
#define PAYLOAD_CONTRACTOR 3 

ya da (muhtemelen daha iyi):

typedef enum { 
    PAYLOAD_UNKNOWN, 
    PAYLOAD_MANAGER, 
    PAYLOAD_EMPLOYEE, 
    PAYLOAD_CONTRACTOR 
} tPayLoad; 

Eğer yükün hizalama doğru olduğundan emin olmak için dikkat etmeniz gereken tek şey. Hem yük kapasitem hem de yük yükümün tümü char tür olduğundan, bu bir sorun değil. Ancak, yükünüz daha sıkı hizalama gereksinimlerine sahip türlerden oluşuyorsa (işaretçilerden daha katı bir şey gibi), bunun için ayarlama yapmanız gerekebilir.

ISO C standardına göre mümkündür, hizalamalardan daha sıkı bir ortam görmemiş olmam gerekir.

Genellikle sıkı hizalama gereksinimi gibi sahip yük tutucu için bir veri türü kullanılarak gerekli uyum basitçe alabilirsiniz:

long payload; 

---

Geriye doğru bakıldığında, bana oluşur muhtemelen , kodunun, yer tutucu yer tutucusu olarak bir diziye gerek duymaz. Adresini alabileceğiniz birşeye sahip olmak için yeterince basit. Ben belirli bir deyim olan maden ocaklarının, bir dizi karakter (bir yapıdan ziyade) sakladığım ve onları doğrudan referans aldığı günlere geri döndüğünden şüpheleniyorum. Bu durumda, payload[]'u kendi başına başka bir türe dökmeksizin kullanabilirsiniz.

Answer 2

ederiz.

Answer 3

Bir "object" temel sınıfına veya şablonlu türlerine C en yakın düşünceyi bir void işaretçisidir. Bir void *, bir şeye işaretçiyi temsil eder, ancak ne tür verilerin işaret edildiğini belirtmez. Verilere erişmek istiyorsanız, bir yayın kullanmanız gerekir.

bir iki kat bağlantılı liste düğümü bu gibi görünebilir:

struct DoubleLinkedListNode { 
    struct DoubleLinkedListNode *previous, *next; 
    void *data; 
}; 

atamak için bir düğüm bir dize, örneğin, bunu yapabilirsiniz:

char myString[80] = "hello, world"; 
struct DoubleLinkedListNode myNode; 
myNode.data = myString; 

bir düğümden geri dize almak için

char *string = (char *)myNode.data; 
puts(string); 

Eğer verilerden bir işaretçi yapmak gerekir olmayan bir işaretçi saklamak için: Eğer bir döküm kullanın. Yapılar için, ömrünün yeterince uzun olması durumunda (yukarıdaki örneğe benzer şekilde) örneği basitçe belirtebilirsiniz. Eğer değilse veya ilkel bir türle (örneğin, bir int veya float) uğraşıyorsanız, bir alan için malloc gerekir. Sadece işiniz bittiğinde hafızayı boşaltdığınızdan emin olun.

Answer 4

Gösterildiği gibi makroları here kullanabilirsiniz (bu özel örnek, genel karma tabloları uygular).

Answer 5

Açıkçası, linux çekirdeği, hem çekirdek hem de birçok aygıt sürücüsü modülünde birçok yerde bağlantılı listeler kullanır. Bunların hemen hepsi, linux/list.h içinde tanımlanmış bir dizi makro kullanılarak gerçekleştirilmiştir.

İyi bir açıklama için http://isis.poly.edu/kulesh/stuff/src/klist/ veya http://kernelnewbies.org/FAQ/LinkedLists'a bakın.

Makrolar ilk başta biraz garip görünüyorlar, ancak kullanımı kolay ve kısa süre sonra ikinci doğaya dönüşüyorlar. Kullanıcı alanında kullanım için uyarlanabilirler (bkz. list.h).