सी में जेनेरिक सूची मैनिपुलेशन फ़ंक्शन क्या है? (मैंने यह देखा कि जब मैं कुछ सामग्रियों से गुज़र रहा था।)सी में जेनेरिक सूची मैनिपुलेशन समारोह?
इस फ़ंक्शन और फ़ंक्शन के बीच क्या अंतर है जो किसी भी प्रकार के तत्वों को स्वीकार कर सकता है?
क्या वे वही हैं ...? यदि वे समान नहीं हैं तो हम उन्हें अलग-अलग कैसे कार्यान्वित कर सकते हैं?
एक सामान्य सूची अकेले से जुड़े होने की संभावना है, और शायद यह मानता है कि सूची में आइटम्स इस तरह की एक संरचना है:
typedef struct list_item list_item;
struct list_item
{
list_item *next;
...data for node...
};
बस का उपयोग करके सूचियां हेरफेर करने के लिए, आप कार्यों लिख सकते हैं इस लेआउट का उपयोग करना अगले पॉइंटर्स।
कभी-कभी, '...data for node...' एक सरल 'void *' होगा; यानी, सूची आइटम सूची में अगले नोड (या नल अगर कोई अगला नोड नहीं है) और पॉइंटर्स को डेटा में पॉइंटर्स रखेंगे।
typedef struct list list;
struct list
{
list *next;
void *data;
};
जब से तुम 'void *' के लिए किसी भी सूचक डाल सकता, आप सूची में कोई भी डेटा प्रकार मिश्रण हो सकता है - लेकिन अपने कोड पता होना चाहिए कि उन्हें संभालने के लिए।
आप 'ए' जेनेरिक सूची फ़ंक्शन के बारे में पूछते हैं, लेकिन शायद एक ही फ़ंक्शन-नहीं-सभी डिज़ाइन नहीं है, और निश्चित रूप से एक साधारण नहीं है। ऐसे कार्यों के कई संभावित सेट हैं जो सामान्य सूची फ़ंक्शन बना सकते हैं। एक सेट, लिस्प से प्रेरित, मिलकर की जाएगा:
void *car(list *lp); // Return the data for the first item on the list
list *cdr(list *lp); // Return the tail of the list
list *cons(list *lp1, list *lp2); // Construct a list from lists lp1 and lp2
list *cond(list *lp, void *data); // Append data item to list
आप शायद परीक्षण करने के लिए है कि क्या सूची रिक्त है की क्षमता है, और कुछ अन्य वस्तुओं प्रदान करना चाहते हैं।
स्वीकार्य रूप से सी ++ में एक अच्छा प्रदर्शन, कोएनिग के "Ruminations on C++" में पाया जाता है। विचारों को सी में आसानी से अनुकूलित किया जा सकता है - यह बहुत कठिन नहीं है (हालांकि सी में स्टोरेज प्रबंधन सी ++ से कठिन है)।
सी में "जेनेरिक" पॉइंटर्स या ऑब्जेक्ट्स की कोई अवधारणा नहीं है - निकटतम आप void* पॉइंटर का उपयोग कर सकते हैं। यदि आप चाहते हैं कि कोड का एक टुकड़ा किसी भी डेटा प्रकार को संभालने में सक्षम हो, तो आपको void* पॉइंटर्स का उपयोग करना होगा। आकार वाले डेटा प्रकारों के लिए पॉइंटर से बड़ा नहीं, आप प्रकार और void* के बीच कास्ट कर सकते हैं; बड़े डेटा प्रकारों के लिए, आपको गतिशील स्मृति का उपयोग करना होगा और void* गतिशील स्मृति के लिए सदस्य बिंदु होना होगा। बस स्मृति लीक के लिए बाहर देखो!
typedef struct list_node {
struct list_node *next;
void *data;
} list_node;
void list_insert(list_node *node, void *data) {
// ...
}
दूसरी ओर, यदि आप प्रत्येक संभव डेटा प्रकार के लिए कोड जनरेट करना चाहते हैं, तो आप मैक्रो के साथ यह करना होगा, और फिर प्रत्येक डेटा के लिए मैक्रो का दृष्टांत टाइप आप का उपयोग हो सकता है। उदाहरण के लिए:
#define DEFINE_LIST(type) \
typedef struct list_node_##type { \
struct list_node_##type *next; \
type data; \
}
#define IMPLEMENT_LIST_INSERT(type) \
void list_##type##_insert(list_node_##type *node, type data) { \
... \
}
DEFINE_LIST(int); // defines struct list_node_int
DEFINE_LIST(double); // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int); // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert
लिनक्स कर्नेल इसके linux/list.h हैडर पर सी में एक सामान्य लिंक्ड सूची का एक दिलचस्प कार्यान्वयन है।कोई डेटा की आवश्यकता होगी,
struct mystruct {
...
/* Contains the next and prev pointers */
struct list_head mylist;
...
/* A single struct can be in several lists */
struct list_head another_list;
...
};
struct list_head mylist_head;
struct list_head another_list_head;
इस छोटे से उदाहरण में कुछ दिलचस्प बातें: यह एक सिर नोड के साथ एक दोगुना से जुड़े सूची, इस तरह इस्तेमाल किया जाता है सूचक।
struct list_head पर इंगित करता है, लक्ष्य संरचना के लिए नहीं (ऊपर दिए गए उदाहरण पर, वे पहली सूची के लिए &(foo->mylist) और दूसरी सूची के लिए &(foo->another_list) पर इंगित करते हैं)।सभी सूची में गड़बड़ी कार्यों struct list_head की ओर इशारा करते हैं (और सबसे सब पर है कि क्या यह अलग सिर नोड या एम्बेडेड नोड्स में से एक है परवाह नहीं है)। लक्ष्य संरचना में struct list_head से प्राप्त करने के लिए, आप list_entry मैक्रो (containter_of मैक्रो के समान linux/kernel.h शीर्षलेख के समान) का उपयोग करते हैं, जो एक साधारण सूचक घटाव में फैलता है।
चूंकि यह एक सिर नोड के साथ एक दोगुना से जुड़े सूची है, आप कर सकते हैं O(1) में:
सी और इसकी मानक लाइब्रेरी कोई भी सूची विशिष्ट फ़ंक्शंस प्रदान नहीं करती है।
लेकिन वहाँ सी के लिए कई उपयोगी कार्यों के साथ पुस्तकालयों कि अन्य प्रोग्रामिंग भाषाओं से भी जाना जाता है डेटा प्रकार का समर्थन कर रहे हैं: http://library.gnome.org/devel/glib/2.18/glib-data-types.html
ऊपर उल्लेख किया है, मैं इस सूची में गड़बड़ी कार्यों बनाने के लिए मैक्रो दृष्टिकोण का उपयोग करने की कोशिश की। आईएनएसईआरटी ऑपरेशन दिनचर्या बनाना आसान है लेकिन डिलीट और ट्रैवर्स ऑपरेशंस बनाना मुश्किल है। यह सूची संरचना और सम्मिलित दिनचर्या हस्ताक्षर के बाद:
#define LIST_DEFINE(type) \
struct list_node_##type \
{ \
type *data; \`
struct list_node_##type *next; \
};
LIST_INSERT(&ListHead,&Data, DataType);
कहाँ:
ListHead - डेटा जिसके लिए एक नए नोड बनाया जाएगा और डेटा नोड में डाला जाता है - लिंक्ड सूची
Data के प्रमुख DataType - डेटा का डेटा प्रकार
FYI, मैं फ़ंक्शन में स्मृति आवंटित कर रहा हूं और नव निर्मित नोड में पारित सभी डेटा की प्रतिलिपि बना रहा हूं और उन्हें नोड को लिंक की गई सूची में जोड़ना है।
अब, जब LIST_DELETE दिनचर्या बनाई जाती है, तो नोड को हटाया जाना चाहिए डेटा के भीतर एक अद्वितीय पहचानकर्ता का उपयोग करके पहचाना जाएगा। यह पहचानकर्ता MACRO दिनचर्या में कुंजी के रूप में भी पास किया जाता है जिसे MACRO विस्तार में बदल दिया जाएगा। दिनचर्या हस्ताक्षर हो सकता है:
LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);
कहाँ:
ListHead - लिंक्ड सूची
DataType के प्रमुख - डेटा के डेटा प्रकार है
myvar->data->str - अद्वितीय कुंजी
char* - कुंजी प्रकार
अब, जब कुंजी का विस्तार किया जाता है, तो उसी कुंजी को तुलना के लिए उपयोग नहीं किया जा सकता है जैसे कि हम
0 लिखते हैंयह
ListHead->data->myvar->data->str == myvar->data->str
के लिए विस्तारित और यहाँ वहाँ की तरह कोई चर रहा है: ListHead->data->myvar->data->str
तो, यह दृष्टिकोण दिनचर्या को नष्ट लिखने के लिए काम नहीं कर सकता और, एक ही रूप में ट्रावर्सल और खोज दिनचर्या भी अद्वितीय कुंजी का उपयोग करें उनमें भी समस्या का सामना किया जाएगा।
और, एक असंबंधित नोट पर, अद्वितीय कुंजी के लिए मिलान तर्क निर्धारित करने के लिए, क्योंकि अद्वितीय कुंजी कुछ भी हो सकती है।
मेरी शिक्षाओं के लिए मैं इस "जेनेरिक" सूची मॉड्यूल को विकसित करने के लिए आया था, शायद लिनक्स कर्नेल एक का सरलीकृत संस्करण, अतिरिक्त अनदेखा बग शामिल है, और यह जीसीसी एक्सटेंशन का उपयोग करता है ... कोई भी टिप्पणी का स्वागत है!
#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
struct liste_s * suivant ;
} * liste ;
#define newl(t) ((liste) malloc (sizeof (struct liste_s) + sizeof (t)))
#define elt(l,t) (* ((t *) (l + 1)))
#define liste_vide NULL
#define videp(l) (l == liste_vide)
#define lvide() liste_vide
#define cons(e,l) \
({ liste res = newl(typeof(e)) ; \
res->suivant = l ; \
elt(res,typeof(e)) = e ; \
res ; })
#define hd(l,t) ({ liste res = l ; if (videp(res)) exit (EXIT_FAILURE) ; elt(res,t) ; })
#define tl(l) ({ liste res = l ; if (videp(res)) exit (EXIT_FAILURE) ; res->suivant ;})
#endif
मैं कुछ अलग करने की कोशिश कर रहा हूं। यह एक और दृष्टिकोण है कैसे समस्या
अगर हम पालन संरचना है बोर्ड:
typedef struct token {
int id;
char *name;
struct token *next;
} Token;
और हम एक समारोह है कि एक लिंक्ड सूची की पूंछ रिटर्न बनाने की जरूरत है, लेकिन समारोह सामान्य होना चाहिए किसी भी लिंक्ड सूची है, तो के लिए:
void* tail(void* list, void* (*f)(void *)) {
void *head = list;
while(f(head) != NULL) {
head = f(head);
}
return head;
}
अब एक समारोह पूंछ समारोह में एक सामान्य प्रयोज्य करने के लिए हमारे कस्टम struct के बीच का पुल करने के लिए जिम्मेदार बनाने के लिए आवश्यक हो जाएगा। कि रास्ते में, हमने:
void* nextToken(void *a) {
Token *t = (Token *) t;
return (void *) (a->next);
}
अंत में हम बस का उपयोग कर सकते हैं:
Token *listTokens;
(...)
Token *lastToken = tail(listTokens, nextToken);