डबल सार डेटा प्रकार

Question

के साथ इस सूची मैं सी में डबल लिंक्ड सूची में जरूरत से जुड़ा हुआ सी, लेकिन यह विभिन्न प्रकार के लिए होना चाहिए। सी ++ में हम इसके लिए टेम्पलेट का उपयोग करते हैं। अमूर्त प्रकार वस्तुओं के साथ डबल लिंक्ड सूची के लिए सी में मुझे उदाहरण कहां मिल सकता है। विशेष रूप से ज्यादातर मामलों में void * -

सी में मनमाने ढंग से डेटा हैंडलिंग आमतौर पर संकेत का उपयोग करके किया जाता है आप

Answer 1

कुछ दृष्टिकोण ले जा सकते हैं, जिनमें से एक अपने ADT में एक void* भंडारण शामिल हैं।

मैं हमेशा इस मिल गया है क्योंकि आप इसे स्वयं सूची के लिए अलग से आवंटन है प्रबंधन करने के लिए एक लिंक की गई सूची में एक दर्द का एक सा हो सकता है। दूसरे शब्दों में, एक नोड आवंटित करने के लिए, आप अलग से दोनों नोड और उसके पेलोड Alocate (और साथ ही हटाए जाने पर उन दोनों को साफ करने के लिए याद) की जरूरत है।

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

अब जब कि नहीं लगती है चर आकार किन्तु की एक संरचना इस प्रकार आवंटित कर:

एक दृष्टिकोण मैं पहले उपयोग किए गए की तरह एक 'चर आकार' संरचना है

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)); 

अब आप एक नोड कि, सभी इरादों और उद्देश्यों के लिए, इस तरह दिखता है

या, चित्रमय रूप (जहां [n] मतलब है n बाइट्स) में:

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

यही है, यह सोचते हैं आप कैसे सही ढंग से पेलोड को संबोधित करने के पता है।

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"); 

कि डाली लाइन बस payload चरित्र (tNode प्रकार में) का पता डाले वास्तविक tPerson पेलोड प्रकार का कोई पता होना करने के लिए: यह इस प्रकार किया जा सकता है।

इस पद्धति का उपयोग करके आप अगर आप संरचना अधिक की तरह बनाने के लिए, किसी भी पेलोड प्रकार आप एक नोड में चाहते हैं, प्रत्येक नोड में भी विभिन्न प्रकार पेलोड ले जा सकता है:

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

और payloadType का उपयोग स्टोर करने के लिए वास्तव में पेलोड क्या है के रूप में एक संकेतक।

यह, में यह अंतरिक्ष बर्बाद नहीं है कि एक संघ से अधिक लाभ दिया है के रूप में साथ देखा जा सकता है निम्नलिखित:

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

जहां 96 बाइट्स हर बार जब आप सूची में एक पूर्णांक प्रकार की दुकान बर्बाद हो जाते हैं (एक 4-बाइट पूर्णांक के लिए)।

tNode में पेलोड प्रकार आपको आसानी से पता लगाने की अनुमति देता है कि यह नोड किस प्रकार का पेलोड ले रहा है, इसलिए आपका कोड यह तय कर सकता है कि इसे कैसे संसाधित किया जाए। (शायद बेहतर)

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

या:: आप की तर्ज पर कुछ का उपयोग कर सकते

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

केवल एक चीज आप बाहर देखने के लिए सुनिश्चित करना है कि पेलोड के संरेखण सही है की जरूरत है। चूंकि मेरे पेलोड प्लेसहोल्डर और पेलोड दोनों ही char प्रकार हैं, यह कोई समस्या नहीं है। हालांकि, अगर आपके पेलोड में अधिक कठोर संरेखण आवश्यकताओं वाले प्रकार होते हैं (जैसे पॉइंटर्स की तुलना में कुछ अधिक सख्त, तो आपको इसके लिए समायोजन करने की आवश्यकता हो सकती है)।

हालांकि मैंने कभी भी संकेतकों के साथ वातावरण को अधिक सख्त नहीं देखा है, यह आईएसओ सी मानक के अनुसार संभव है।

आप आमतौर पर पेलोड प्लेसहोल्डर है जो इस तरह के रूप में कठोरतम संरेखण की आवश्यकता है के लिए एक डेटा प्रकार का उपयोग करके आवश्यक संरेखण बस प्राप्त कर सकते हैं:

long payload; 

---

पीछे मुड़कर देखें तो यह मेरे लिए होता है कि आप शायद को पेलोड प्लेसहोल्डर के रूप में एक सरणी की आवश्यकता नहीं है। यह केवल इतना आसान है कि आप इसका पता ले सकें। मुझे संदेह है कि मेरा विशेष मुहावरे उन दिनों तक सुनता है जहां मैंने सिर्फ पात्रों की एक सरणी (संरचना के बजाए) संग्रहीत की और उन्हें सीधे संदर्भित किया। उस स्थिति में, आप किसी अन्य प्रकार के कास्टिंग किए बिना payload[] का उपयोग कर सकते हैं।

Answer 2

धन्यवाद।

Answer 3

सी में निकटतम थिंक एक "वस्तु" आधार वर्ग या टेम्प्लेट प्रकार के लिए एक void सूचक है। void * कुछ के लिए एक सूचक का प्रतिनिधित्व करता है, लेकिन यह निर्दिष्ट नहीं करता कि किस प्रकार का डेटा इंगित किया जा रहा है। यदि आप डेटा तक पहुंचना चाहते हैं, तो आपको एक कास्ट का उपयोग करने की आवश्यकता है।

एक दोगुना लिंक्ड सूची नोड ऐसा दिखाई दे सकता:

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

असाइन करने के लिए एक नोड एक स्ट्रिंग, उदाहरण के लिए, तुम कर सकते हो:

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

एक नोड से वापस स्ट्रिंग प्राप्त करने के लिए

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

एक गैर सूचक की दुकान के लिए, आपको डेटा से एक सूचक बनाने की जरूरत है:, आप एक डाली का उपयोग करें। संरचनाओं के लिए, यदि आप अपना जीवनकाल काफी लंबा है (उपर्युक्त उदाहरण के समान) तो आप बस उदाहरण को अव्यवस्थित करने में सक्षम हो सकते हैं। यदि नहीं, तो या यदि आप एक आदिम प्रकार (उदा एक int या float) के साथ काम कर रहे हैं, आप malloc कुछ जगह की जरूरत है। जब आप पूरा कर लें तो बस स्मृति को मुक्त करना सुनिश्चित करें।

Answer 4

आप मैक्रोज़ का उपयोग here के रूप में कर सकते हैं (यह विशेष उदाहरण जेनेरिक हैश-टेबल लागू करता है)।

Answer 5

जाहिर है, लिनक्स कर्नेल कर्नेल में और कई डिवाइस ड्राइवर मॉड्यूल में कई, कई स्थानों में लिंक्ड सूचियों का उपयोग करता है। इनमें से लगभग सभी को लिनक्स/list.h

http://isis.poly.edu/kulesh/stuff/src/klist/ या http://kernelnewbies.org/FAQ/LinkedLists में अच्छी व्याख्या के लिए देखें मैक्रोज़ का एक सेट का उपयोग करके लागू किया गया है।

मैक्रोज़ पहले थोड़ा अजीब लगते हैं लेकिन उपयोग करने में आसान हैं और जल्द ही दूसरी प्रकृति बन जाते हैं। वे उपयोगकर्ता स्थान में उपयोग के लिए अनुकूलित रूप से अनुकूलित किए जा सकते हैं (list.h देखें)।