ملخص

مراجعة النقاط الرئيسية

• يمكن تصنيف بنى البيانات من منظورين: البنية المنطقية والبنية الفيزيائية. تصف البنية المنطقية العلاقات المنطقية بين عناصر البيانات، بينما تصف البنية الفيزيائية كيفية تخزين البيانات في ذاكرة الحاسوب.
• تشمل البنى المنطقية الشائعة البنية الخطية والشجرية والشبكية. ونصنّف بنى البيانات عادةً إلى خطية (المصفوفات، القوائم المترابطة، المكدسات، الطوابير) وغير خطية (الأشجار، الرسوم البيانية، الأكوام) بناءً على بنيتها المنطقية. وقد يتضمن تنفيذ جداول التجزئة بنى بيانات خطية وغير خطية معاً.
• عند تشغيل برنامج، تُخزَّن البيانات في ذاكرة الحاسوب. ولكل مساحة ذاكرة عنوان ذاكرة يقابلها، ويصل البرنامج إلى البيانات عبر عناوين الذاكرة هذه.
• تنقسم البنى الفيزيائية أساساً إلى تخزين في مساحة متجاورة (المصفوفات) وتخزين في مساحة متفرقة (القوائم المترابطة). وتُنفَّذ جميع بنى البيانات باستخدام المصفوفات أو القوائم المترابطة أو مزيج منهما.
• تشمل أنواع البيانات الأساسية في الحواسيب الأعداد الصحيحة byte وshort وint وlong، والأعداد العشرية العائمة float وdouble، والمحارف char، والقيم المنطقية bool. وتعتمد نطاقات قيمها على حجم المساحة التي تشغلها وطريقة تمثيلها.
• التمثيل بالمقدار والإشارة، ومتمم الواحد، ومتمم الاثنين ثلاث طرق لترميز الأعداد في الحواسيب، ويمكن التحويل بينها. البت الأكثر دلالةً في التمثيل بالمقدار والإشارة هو بت الإشارة، وتمثل البتات المتبقية قيمة العدد.
• تُخزَّن الأعداد الصحيحة في الحواسيب بصيغة متمم الاثنين. وفي ظل تمثيل متمم الاثنين، تستطيع الحواسيب التعامل مع جمع الأعداد الموجبة والسالبة بشكل موحّد، دون الحاجة إلى تصميم دارات عتاد خاصة للطرح، ولا يوجد غموض بشأن الصفر الموجب والسالب.
• يتكوّن ترميز الأعداد العشرية العائمة من بت إشارة واحد، و8 بتات للأُس، و23 بتاً للكسر. وبفضل بتات الأُس، يكون نطاق الأعداد العشرية العائمة أكبر بكثير من نطاق الأعداد الصحيحة، وذلك على حساب التضحية بالدقة.
• ASCII هي أقدم مجموعة محارف إنجليزية، وطولها بايت واحد، وتضم 128 محرفاً في المجموع. أما GBK فهي مجموعة محارف صينية شائعة الاستخدام، تضم أكثر من 20,000 محرف صيني. ويسعى Unicode إلى تقديم معيار كامل لمجموعات المحارف، يجمع محارف مختلف لغات العالم، وبذلك يحل مشكلة النصوص المشوّهة الناجمة عن عدم اتساق طرق ترميز المحارف.
• UTF-8 هي طريقة ترميز Unicode الأكثر شيوعاً وتتمتع بتوافق ممتاز. وهي طريقة ترميز متغيرة الطول ذات قابلية جيدة للتوسع، وتحسّن فعالية مساحة التخزين بشكل ملموس. وUTF-16 وUTF-32 طريقتان شائعتان لترميز Unicode. وعند ترميز المحارف الصينية، تشغل UTF-16 مساحة أقل من UTF-8. وتستخدم لغات برمجة مثل Java وC# ترميز UTF-16 افتراضياً.

أسئلة وأجوبة

س: لماذا تحتوي جداول التجزئة على بنى بيانات خطية وغير خطية معاً؟

البنية الأساسية لجدول التجزئة هي مصفوفة. ولحل تصادمات التجزئة، قد نستخدم "التسلسل" (سنناقشه في قسم "تصادم التجزئة" اللاحق): إذ يشير كل دلو في المصفوفة إلى قائمة مترابطة، وقد تُحوَّل إلى شجرة (عادةً شجرة حمراء-سوداء) عندما يتجاوز طول القائمة حداً معيناً.

من منظور التخزين، البنية الأساسية لجدول التجزئة هي مصفوفة، وقد يحتوي كل فتحة دلو فيها على قيمة أو قائمة مترابطة أو شجرة. لذلك، قد يحتوي جدول التجزئة على بنى بيانات خطية (المصفوفات والقوائم المترابطة) وبنى بيانات غير خطية (الأشجار) معاً.

س: هل طول النوع char بايت واحد؟

يتحدد طول النوع char بطريقة الترميز التي تستخدمها لغة البرمجة. على سبيل المثال، تستخدم Java وJavaScript وTypeScript وC# جميعاً ترميز UTF-16 (لتخزين نقاط شيفرة Unicode)، لذا يكون طول النوع char بايتين.

س: هل هناك غموض في وصف بنى البيانات القائمة على المصفوفات بأنها "بنى بيانات ساكنة"؟ فالمكدسات يمكنها أيضاً تنفيذ عمليات "ديناميكية" مثل الدفع والسحب.

يمكن للمكدسات بالفعل تنفيذ عمليات بيانات ديناميكية، لكن بنية البيانات تظل "ساكنة" (ثابتة الطول). فرغم أن بنى البيانات القائمة على المصفوفات تستطيع إضافة عناصر أو حذفها ديناميكياً، فإن سعتها ثابتة. وإذا تجاوز حجم البيانات الحجم المخصص مسبقاً، يلزم إنشاء مصفوفة جديدة أكبر، ونسخ محتويات المصفوفة القديمة إلى المصفوفة الجديدة.

س: عند إنشاء مكدس (أو طابور)، لا يُحدَّد حجمه. فلماذا يُعدّان "بنيتي بيانات ساكنتين"؟

في لغات البرمجة عالية المستوى، لا نحتاج إلى تحديد السعة الأولية للمكدس (أو الطابور) يدوياً؛ إذ تتولى الفئة ذلك تلقائياً. على سبيل المثال، السعة الأولية لـ ArrayList في Java هي عادةً 10. وإضافة إلى ذلك، تُنفَّذ عملية التوسيع تلقائياً أيضاً. راجع قسم "القائمة" اللاحق للتفاصيل.

س: طريقة التحويل من التمثيل بالمقدار والإشارة إلى متمم الاثنين هي "انفِ أولاً ثم أضف 1". لذا ينبغي أن يكون التحويل من متمم الاثنين إلى التمثيل بالمقدار والإشارة هو العملية العكسية "اطرح 1 أولاً ثم انفِ". ومع ذلك، يمكن أيضاً التحويل من متمم الاثنين إلى التمثيل بالمقدار والإشارة عبر "انفِ أولاً ثم أضف 1". فما سبب ذلك؟

يعود سبب ذلك إلى أن التحويل المتبادل بين التمثيل بالمقدار والإشارة ومتمم الاثنين هو في الحقيقة عملية حساب "المتمم". لنعرّف المتمم أولاً: بافتراض أن $a + b = c$، نقول إن $a$ هو متمم $b$ بالنسبة إلى $c$، وبالعكس، $b$ هو متمم $a$ بالنسبة إلى $c$.

بإعطاء عدد ثنائي من $n = 4$ بتات هو $0010$، إذا عاملنا هذا العدد كتمثيل بالمقدار والإشارة (بغض النظر عن بت الإشارة)، فإن متمم الاثنين له يمكن الحصول عليه عبر "انفِ أولاً ثم أضف 1":

$$0010 \rightarrow 1101 \rightarrow 1110$$

نجد أن مجموع التمثيل بالمقدار والإشارة ومتمم الاثنين هو $0010 + 1110 = 10000$، مما يعني أن متمم الاثنين $1110$ هو "متمم" التمثيل بالمقدار والإشارة $0010$ بالنسبة إلى $10000$. وهذا يعني أن "انفِ أولاً ثم أضف 1" المذكور أعلاه هو في الحقيقة عملية حساب المتمم بالنسبة إلى $10000$.

إذن، ما "متمم" متمم الاثنين $1110$ بالنسبة إلى $10000$؟ لا يزال بإمكاننا استخدام "انفِ أولاً ثم أضف 1" للحصول عليه:

$$1110 \rightarrow 0001 \rightarrow 0010$$

بعبارة أخرى، التمثيل بالمقدار والإشارة ومتمم الاثنين هما "متمم" كل منهما للآخر بالنسبة إلى $10000$، لذا يمكن تنفيذ "التحويل من التمثيل بالمقدار والإشارة إلى متمم الاثنين" و"التحويل من متمم الاثنين إلى التمثيل بالمقدار والإشارة" بالعملية نفسها (انفِ أولاً ثم أضف 1).

وبالطبع، يمكننا أيضاً استخدام العملية العكسية لإيجاد التمثيل بالمقدار والإشارة لمتمم الاثنين $1110$، أي "اطرح 1 أولاً ثم انفِ":

$$1110 \rightarrow 1101 \rightarrow 0010$$

خلاصةً، كل من "انفِ أولاً ثم أضف 1" و"اطرح 1 أولاً ثم انفِ" يحسب المتمم بالنسبة إلى $10000$، وهما متكافئان.

في جوهر الأمر، عملية "النفي" هي في الحقيقة إيجاد المتمم بالنسبة إلى $1111$ (لأن "التمثيل بالمقدار والإشارة + متمم الواحد = 1111" يتحقق دائماً)؛ وإضافة 1 إلى متمم الواحد تعطي متمم الاثنين، وهو المتمم بالنسبة إلى $10000$.

استخدم المثال أعلاه $n = 4$، ويمكن تعميمه على الأعداد الثنائية بأي عدد من البتات.