शुद्ध सी

Question

में 'बहुउद्देश्यीय' लिंक्ड सूची कार्यान्वयन यह वास्तव में एक तकनीकी प्रश्न नहीं है, क्योंकि मुझे पता है कि मुझे उन चीजों को करने के लिए पर्याप्त प्रकार की आवश्यकता है (मेरा मतलब है कि 'भाषा को आपके रास्ते में आने देना '), तो यह सवाल मूल रूप से' क्या दिशा लेने के लिए 'सवाल है।

स्थिति यह है: मैं वर्तमान में एक उन्नत एल्गोरिदम कोर्स ले रहा हूं, और 'प्रोग्रामर के रूप में बढ़ने' के लिए, मुझे व्यावहारिक असाइनमेंट को लागू करने के लिए शुद्ध सी का उपयोग करना आवश्यक है (यह अच्छी तरह से काम करता है: बहुत अधिक गलती आप इसे वास्तव में समझने के लिए मजबूर करते हैं कि आप इसे ठीक करने के लिए क्या कर रहे हैं)। कार्यान्वयन के दौरान, मैं स्पष्ट रूप से ग्राउंड अप से 'मूल' डेटा संरचनाओं को लागू करने की समस्या में भाग लेता हूं: वास्तव में न केवल लिंक्ड सूचियां, बल्कि ढेर, पेड़, और कैटर।

मैं इस विषय में सूचियों पर ध्यान केंद्रित कर रहा हूं क्योंकि यह आमतौर पर एक संरचना है जिसे मैं प्रोग्राम में बहुत अधिक उपयोग करता हूं, या तो 'मुख्य' संरचना के रूप में या अन्य बड़े लोगों के लिए 'सहायक' संरचना के रूप में (उदाहरण के लिए, हैश पेड़ जो एक लिंक्ड सूची का उपयोग करके संघर्ष का समाधान करता है)।

यह आवश्यक है कि सूची विभिन्न प्रकार के तत्वों को संग्रहित करे। मैं यहां एक आधार के रूप में मान रहा हूं कि मैं प्रत्येक प्रकार के लिए सूची को दोबारा कोड नहीं करना चाहता हूं।

• एक (थोड़े असजीला; डिबग करने के लिए कठिन) शून्य संकेत की सूची बनाना
• केवल एक सूची बनाना, लेकिन 'तत्व प्रकार' के रूप में एक संघ होने,: तो, मैं इन विकल्पों के साथ आ सकते हैं जिसमें सभी तत्व प्रकार शामिल हैं, मैं प्रोग्राम में उपयोग करूंगा (डीबग करने में आसान; तत्वों का आकार समान नहीं है)
• SGLIB की शैली में प्रत्येक प्रकार के कोड को पुन: उत्पन्न करने के लिए प्रीप्रोसेसर मैक्रो का उपयोग करके, 'अनुकरण' सी ++ एसटीएल (रचनात्मक समाधान; अंतरिक्ष बर्बाद नहीं करता है; तत्वों के पास स्पष्ट प्रकार होता है जब वे वापस आते हैं; कोई भी परिवर्तन I n सूची कोड वास्तव में नाटकीय हो सकता है)
• आपका विचार/समाधान

सवाल स्पष्ट करने के लिए: जो ऊपर से एक सबसे अच्छा है?

पीएस: चूंकि मैं मूल रूप से अकादमिक संदर्भ में हूं, इसलिए मैं उद्योग में शुद्ध सी के साथ काम करने वाले लोगों के विचार में भी रूचि रखता हूं। मैं समझता हूं कि अधिकांश शुद्ध सी प्रोग्रामर एम्बेडेड डिवाइस क्षेत्र में हैं, जहां मुझे नहीं लगता कि इस तरह की समस्या का सामना करना आम है। हालांकि, अगर वहां कोई भी जानता है कि यह 'असली दुनिया में' कैसे किया जाता है, तो मुझे आपकी राय में बहुत दिलचस्पी होगी।

Answer 1

ए void * एक लिंक्ड सूची में दर्द का थोड़ा सा दर्द है क्योंकि आपको इसे सूची में अलग से आवंटित करना होगा।

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    int payloadType; 
    char payload[1]; // or use different type for alignment. 
} tNode; 

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

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

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

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

या, ग्राफ़िकल रूप में (जहां [n] साधन:

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

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

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

node->prev = NULL; 
node->next = NULL; 
node->payloadType = PLTYP_PERSON; 
tPerson *person = &(node->payload); // cast for easy changes to payload. 
strcpy (person->Name, "Bob Smith"); 
strcpy (person->Addr, "7 Station St"); 

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

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

union { 
    int x; 
    char y[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; 

Answer 2

मेरे $ .002:

• एक (थोड़े diselegant; डिबग करने के लिए कठिन) शून्य संकेत की सूची बनाना

यह नहीं इस तरह के एक बुरा विकल्प है, IMHO, अगर आप लिखना चाहिए सी में आप एप्लिकेशन को डीबगिंग की आसानी के लिए प्रिंट() विधि प्रदान करने की अनुमति देने के लिए एपीआई विधियों को जोड़ सकते हैं। इसी प्रकार की विधियों को तब लागू किया जा सकता है जब (उदा।) आइटम सूची में जोड़े या हटा दिए जाते हैं। (लिंक्ड सूचियों के लिए, यह आमतौर पर आवश्यक नहीं है, लेकिन अधिक जटिल डेटा संरचनाओं के लिए - हैश टेबल, उदाहरण के लिए) - यह कभी-कभी जीवनभर हो सकता है।)

• , (सभी तत्व प्रकार मैं इस कार्यक्रम में इस्तेमाल करेगा युक्त डिबग करने के लिए आसान केवल एक सूची बनाना, लेकिन 'तत्व प्रकार' के रूप में एक संघ है; कचरे अंतरिक्ष अगर तत्वों सभी एक ही आकार नहीं हैं)

मैं इस प्लेग की तरह से बचूंगा। (ठीक है, आपने पूछा था।) डेटा संरचना से मैन्युअल रूप से कॉन्फ़िगर किए गए, संकलित-समय निर्भरता को अपने निहित प्रकारों में सभी दुनिया में सबसे खराब है। फिर, आईएमएचओ।

• SGLIB (sglib.sourceforge.net) की शैली में, हर प्रकार के कोड को पुनर्जीवित करने के एक पूर्वप्रक्रमक मैक्रो का उपयोग करना, 'नकल' सी ++ के एसटीएल (रचनात्मक समाधान; अंतरिक्ष बर्बाद नहीं करता है, तत्व स्पष्ट है टाइप करें जब वे वापस आते हैं; सूची कोड में कोई भी परिवर्तन वास्तव में नाटकीय हो सकता है)

दिलचस्प विचार, लेकिन चूंकि मुझे एसजीएलबीबी नहीं पता है, इसलिए मैं उससे ज्यादा कुछ नहीं कह सकता।

• आपका विचार/समाधान

मैं पहली पसंद के साथ जाना चाहते हैं।

Answer 3

मैंने इसे पहले से किया है, हमारे कोड में (जिसे बाद में सी ++ में परिवर्तित कर दिया गया है), और उस समय, शून्य * दृष्टिकोण पर निर्णय लिया गया। मैंने इसे लचीलापन के लिए अभी किया है - हम हमेशा सूची में एक सूचक को संग्रहीत करते थे, और समाधान की सादगी, और इसकी उपयोगिता अन्य दृष्टिकोणों के लिए डाउनसाइड्स से अधिक थी।

कहा जा रहा है कि, ऐसा एक समय था जहां यह कुछ गंदी बग का कारण बन गया जो डीबग करना मुश्किल था, इसलिए यह निश्चित रूप से एक आदर्श समाधान नहीं है। मुझे लगता है कि यह अभी भी एक है जिसे मैं लेता हूं, हालांकि, अगर मैं इसे फिर से कर रहा था।

Answer 4

मैं वर्षों में सी कोड नहीं किया गया है, लेकिन GLib दावों प्रदान करने के लिए "के लिए उपयोगिता कार्यों के एक बड़े सेट तार और सामान्य डेटा संरचनाएं ", जिनमें से लिंक्ड सूचियां हैं।

Answer 5

यह एक अच्छी समस्या है।

• डेव हैन्सन के C Interfaces and Implementationsvoid * संकेत की एक सूची है, जो मेरे लिए काफी अच्छा है का उपयोग करता है: वहाँ दो समाधान मुझे पसंद कर रहे हैं।

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

  यहाँ कार्यों में से एक सेट लग रहा है क्या की तरह है:

  int  lengthEL (Explist *l); 
  Exp*  nthEL (Explist *l, unsigned n); 
  Explist *mkEL  (Exp *hd, Explist *tl); 
  

  awk स्क्रिप्ट एक 150 लाइन आतंक है, यह typedef एस के लिए सी कोड खोजता है और प्रत्येक के लिए सूची कार्यों का एक सेट उत्पन्न करता है। यह बहुत पुराना है; मैं शायद अब बेहतर कर सकता हूं :-)

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

Answer 6

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

इसके बजाय, भाषा x में प्रोग्रामिंग करते समय, आपको भाषा x की मुहावरों का उपयोग करना चाहिए। जब आप अजगर का उपयोग कर रहे हों तो जावा मत लिखो। जब आप योजना का उपयोग कर रहे हों तो सी लिखें मत। जब आप C99 का उपयोग कर रहे हों तो C++ न लिखें।

मैं स्वयं, मैं शायद पैक्स के सुझाव की तरह कुछ का उपयोग कर पहुंचते हैं, लेकिन वास्तव में चार का एक संघ का उपयोग [1] और शून्य * और पूर्णांक, आम मामलों सुविधाजनक बनाने के लिए (और एक enumed प्रकार झंडा)

(मैं शायद एक फाइबोनैकी पेड़ को कार्यान्वित करना भी समाप्त कर दूंगा, सिर्फ इसलिए कि यह साफ लगता है, और आप आरबी पेड़ को केवल स्वाद खोने से पहले इसे लागू कर सकते हैं, भले ही सामान्य मामलों के लिए यह बेहतर हो के लिए।)

संपादित करें: आपकी टिप्पणी के आधार पर, ऐसा लगता है कि आपको डिब्बाबंद समाधान का उपयोग करने के लिए एक बहुत अच्छा मामला मिला है। यदि आपका प्रशिक्षक इसे अनुमति देता है, और जो सिंटैक्स प्रदान करता है वह आरामदायक महसूस करता है, इसे एक भंवर दें। यह शून्य * की एक सूची बनाने से अधिक

Answer 7

ही एक सुधार यह * के बारे में कुछ मेटा डेटा structs कि एक शून्य होते हैं की एक सूची और बनाने की जाएगी क्या शून्य * करने के लिए अंक, उसके प्रकार, आकार, आदि सहित

अन्य विचार: एक पर्ल या लिस्प दुभाषिया एम्बेड करें।

या आधे रास्ते पर जाएं: पर्ल लाइब्रेरी के साथ लिंक करें और इसे पर्ल एसवी या कुछ की सूची बनाएं।

Answer 8

मैं शायद शून्य * दृष्टिकोण के साथ जाऊंगा, लेकिन यह मेरे लिए हुआ कि आप अपने डेटा को एक्सएमएल के रूप में स्टोर कर सकते हैं। फिर सूची में डेटा के लिए केवल एक char * हो सकता है (जिसे आप जो भी उप तत्वों की आवश्यकता है, उसकी मांग पर पार्स कर सकते हैं) ....

Answer 9

प्रीप्रोसेसर मैक्रो का उपयोग करना सबसे अच्छा विकल्प है। Linux kernel linked list सी में एक परिपत्र-लिंक्ड सूची का एक उत्कृष्ट कार्यान्वयन है। बहुत पोर्टेबल और उपयोग करने में आसान है। Here लिनक्स कर्नेल 2.6.29 list.h हेडर का एक स्टैंडअलोन संस्करण।

एक सामान्य मैक्रो के लिए एक और अच्छा विकल्प जुड़ा हुआ आधारित FreeBSD/OpenBSD sys/queue है सूची