المصفوفة (نوع البيانات)

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

قد يتضمن دعم اللغة لأنواع المصفوفات بعض أنواع بيانات المصفوفات المضمنة ، وبعض الإنشاءات النحوية ( منشئات نوع المصفوفة ) التي قد يستخدمها المبرمج لتحديد مثل هذه الأنواع وإعلان متغيرات المصفوفة، وترميز خاص لفهرسة عناصر المصفوفة. ^[1] على سبيل المثال، في لغة برمجة باسكال ، يحدد الإعلان type MyTable = array [1..4,1..2] of integer، نوع بيانات مصفوفة جديد يسمى MyTable. ثم يحدد الإعلان var A: MyTableمتغيرًا Aمن هذا النوع، وهو عبارة عن مجموع ثمانية عناصر، كل منها متغير عدد صحيح يتم تحديده بواسطة مؤشرين. في برنامج باسكال، يتم الإشارة إلى هذه العناصر A[1,1], A[1,2], A[2,1], …, A[4,2]. ^{[3] غالبًا ما يتم تعريف أنواع المصفوفات الخاصة بواسطة} مكتبات اللغة القياسية .

القوائم الديناميكية أكثر شيوعًا وأسهل في التنفيذ ^{[ مشكوك فيه - ناقش ]} من المصفوفات الديناميكية . تتميز أنواع المصفوفات عن أنواع السجلات بشكل أساسي لأنها تسمح بحساب مؤشرات العناصر في وقت التشغيل ، كما هو الحال في تعيين باسكال . من بين أمور أخرى، تسمح هذه الميزة لبيانA[I,J] := A[N-I,2*J] تكراري واحد بمعالجة العديد من عناصر متغير المصفوفة بشكل تعسفي.

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

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

كانت لغة البرمجة Superplan التي ابتكرها هاينز روتيسهاوزر (1949–1951) تتضمن مصفوفات متعددة الأبعاد. ومع ذلك، على الرغم من أن روتيسهاوزر وصف كيفية بناء المجمِّع للغته، إلا أنه لم يقم بتنفيذه.

لا تحتوي لغات التجميع واللغات منخفضة المستوى مثل BCPL ^[4] بشكل عام على دعم نحوي للمصفوفات.

نظرًا لأهمية هياكل المصفوفات في الحوسبة الفعالة، قدمت أقدم لغات البرمجة عالية المستوى، بما في ذلك FORTRAN (1957)، وCOBOL (1960)، و Algol 60 (1960)، الدعم للمصفوفات متعددة الأبعاد.

يمكن إنشاء نموذج رياضي لبنية بيانات المصفوفة كبنية بيانات مجردة ( مصفوفة مجردة ) باستخدام عمليتين

الحصول على ( A ، I ): البيانات المخزنة في عنصر المصفوفة A الذي تكون مؤشراته عبارة عن مجموعة الأعداد الصحيحة I.

set ( A , I , V ): المصفوفة الناتجة عن تعيين قيمة هذا العنصر إلى V.

هذه العمليات مطلوبة لتلبية البديهيات ^[5]

احصل على ( مجموعة ( أ ، ي ، ف )، ي ) =  ف

احصل على ( المجموعة ( A , I , V ), J ) =  احصل على ( A , J ) إذا كان I  ≠  J

لأي حالة مصفوفة A ، وأي قيمة V ، وأي مجموعات I و J يتم تعريف العمليات لها.

تعني البديهية الأولى أن كل عنصر يتصرف كمتغير. وتعني البديهية الثانية أن العناصر ذات المؤشرات المميزة تتصرف كمتغيرات منفصلة ، ​​بحيث لا يؤثر تخزين قيمة في عنصر واحد على قيمة أي عنصر آخر.

لا تضع هذه البديهيات أي قيود على مجموعة مؤشرات التوليف الصالحة I ، وبالتالي يمكن استخدام هذا النموذج المجرد للمصفوفات المثلثية والمصفوفات الأخرى ذات الشكل الغريب.

من أجل تنفيذ متغيرات من أنواع مثل هياكل المصفوفة بشكل فعال (مع الفهرسة التي تتم عن طريق حساب المؤشر )، فإن العديد من اللغات تقيد المؤشرات بأنواع البيانات الصحيحة ^{[6] [7]} (أو أنواع أخرى يمكن تفسيرها على أنها أعداد صحيحة، مثل البايتات والأنواع المعدودة )، وتتطلب أن يكون لجميع العناصر نفس نوع البيانات وحجم التخزين. كما تقيد معظم هذه اللغات كل مؤشر بفاصل محدود من الأعداد الصحيحة، والذي يظل ثابتًا طوال عمر متغير المصفوفة. في بعض اللغات المترجمة ، في الواقع، قد يتعين معرفة نطاقات المؤشرات في وقت التجميع .

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

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

يُطلق على عدد المؤشرات اللازمة لتحديد عنصر ما اسم البعد أو الأبعاد أو الرتبة لنوع المصفوفة. (يتعارض هذا المصطلح مع مفهوم البعد في الجبر الخطي، والذي يعبر عن شكل المصفوفة . وبالتالي، يُقال إن مصفوفة من الأرقام تحتوي على 5 صفوف و4 أعمدة، وبالتالي 20 عنصرًا، لها البعد 2 في سياقات الحوسبة، ولكنها تمثل مصفوفة يُقال إنها ذات أبعاد 4×5. كما يتعارض معنى "الرتبة" في علوم الكمبيوتر مع مفهوم رتبة الموتر ، وهو تعميم لمفهوم رتبة المصفوفة في الجبر الخطي .)

تدعم العديد من اللغات المصفوفات أحادية البعد فقط. في هذه اللغات، يتم تمثيل المصفوفة متعددة الأبعاد عادةً بواسطة متجه Iliffe ، وهو مصفوفة أحادية البعد من المراجع إلى مصفوفات ذات بعد واحد أقل. سيتم تنفيذ المصفوفة ثنائية الأبعاد، على وجه الخصوص، كمتجه من المؤشرات إلى صفوفها. وبالتالي، يمكن الوصول إلى عنصر في الصف i والعمود j من المصفوفة A عن طريق الفهرسة المزدوجة ( A [ i ][ j ] في التدوين النموذجي). تسمح هذه الطريقة لمحاكاة المصفوفات متعددة الأبعاد بإنشاء مصفوفات متعرجة ، حيث قد يكون لكل صف حجم مختلف - أو بشكل عام، حيث يعتمد النطاق الصحيح لكل مؤشر على قيم جميع المؤشرات السابقة.

هذا التمثيل للمصفوفات متعددة الأبعاد شائع جدًا في برامج C وC++. ومع ذلك، ستستخدم C وC++ صيغة فهرسة خطية للمصفوفات متعددة الأبعاد التي يتم إعلانها بحجم ثابت وقت التجميع، على سبيل المثال بواسطة int A[10][20]أو int A[m][n]، بدلاً من الصيغة التقليدية int **A. ^[8]

تدعم معظم لغات البرمجة التي تدعم المصفوفات عمليات التخزين والاختيار ، ولديها قواعد نحوية خاصة للفهرسة. استخدمت اللغات المبكرة الأقواس، على سبيل المثال A(i,j)، كما في FORTRAN؛ واختارت لغات أخرى الأقواس المربعة، على سبيل المثال A[i,j]أو A[i][j]، كما في Algol 60 وPascal (لتمييزها عن استخدام الأقواس لاستدعاءات الوظائف ).

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

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

توفر بعض اللغات، مثل C، أنواع مصفوفات تعتمد على الصفر فقط ، حيث تكون القيمة الدنيا الصالحة لأي مؤشر هي 0. ^[9] يعد هذا الاختيار مناسبًا لتنفيذ المصفوفات وحسابات العناوين. باستخدام لغة مثل C، يمكن تعريف مؤشر إلى داخل أي مصفوفة يعمل رمزيًا كمصفوفة زائفة تستوعب المؤشرات السلبية. يعمل هذا فقط لأن C لا تتحقق من المؤشر مقابل الحدود عند استخدامه.

توفر اللغات الأخرى أنواع مصفوفات تعتمد على رقم واحد فقط ، حيث يبدأ كل مؤشر من 1؛ هذه هي الاتفاقية التقليدية في الرياضيات للمصفوفات والمتواليات الرياضية . تدعم بعض اللغات، مثل باسكال ولوا، أنواع مصفوفات تعتمد على n ، حيث يختار المبرمج مؤشراتها القانونية الدنيا. كانت المزايا النسبية لكل اختيار موضوع نقاش ساخن. يمكن للفهرسة القائمة على الصفر تجنب أخطاء الانحراف عن الرقم واحد أو أخطاء السياج . ^[10]

تختلف العلاقة بين الأرقام التي تظهر في إعلان المصفوفة وفهرس آخر عنصر في المصفوفة أيضًا باختلاف اللغة. في العديد من اللغات (مثل C)، يجب تحديد عدد العناصر الموجودة في المصفوفة؛ بينما في لغات أخرى (مثل Pascal و Visual Basic .NET ) يجب تحديد القيمة العددية لفهرس آخر عنصر. وغني عن القول أن هذا التمييز غير مهم في اللغات التي تبدأ فيها الفهارس من 1، مثل Lua .

تدعم بعض لغات البرمجة برمجة المصفوفات ، حيث يتم توسيع العمليات والوظائف المحددة لأنواع بيانات معينة ضمناً إلى مصفوفات من عناصر تلك الأنواع. وبالتالي يمكن للمرء أن يكتب A + B لإضافة عناصر مقابلة لمصفوفتين A و B. عادةً ما توفر هذه اللغات كلاً من عملية الضرب عنصرًا بعنصر ومنتج المصفوفة القياسي للجبر الخطي ، ويختلف أي من هذه العمليات يتم تمثيله بواسطة عامل * حسب اللغة.

انتشرت اللغات التي توفر إمكانيات برمجة المصفوفات منذ الابتكارات في هذا المجال من APL . هذه هي الإمكانات الأساسية للغات محددة النطاق مثل GAUSS و IDL و Matlab و Mathematica . وهي ميزة أساسية في اللغات الأحدث، مثل Julia والإصدارات الحديثة من Fortran . يتم توفير هذه الإمكانات أيضًا عبر مكتبات التمديد القياسية للغات البرمجة العامة الأخرى (مثل مكتبة NumPy المستخدمة على نطاق واسع لـ Python ).

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

توفر بعض لغات البرمجة عمليات تعيد حجم (عدد العناصر) متجه، أو بشكل عام نطاق كل مؤشر في المصفوفة. في C و C++ لا تدعم المصفوفات دالة الحجم ، لذا غالبًا ما يتعين على المبرمجين إعلان متغير منفصل لاحتواء الحجم، وتمريره إلى الإجراءات كمعلمة منفصلة.

قد تحتوي عناصر المصفوفة التي تم إنشاؤها حديثًا على قيم غير محددة (كما في C)، أو قد يتم تعريفها بحيث تحتوي على قيمة "افتراضية" محددة مثل 0 أو مؤشر فارغ (كما في Java).

في لغة C++، يدعم كائن std::vector عمليات التخزين والتحديد والإضافة بخصائص الأداء التي تمت مناقشتها أعلاه. يمكن الاستعلام عن المتجهات لمعرفة حجمها ويمكن تغيير حجمها. كما يتم دعم العمليات الأبطأ مثل إدراج عنصر في المنتصف .

تأخذ عملية تقطيع المصفوفة مجموعة فرعية من عناصر كيان من نوع المصفوفة (قيمة أو متغير) ثم تجمعها ككيان آخر من نوع المصفوفة، ربما مع مؤشرات أخرى. إذا تم تنفيذ أنواع المصفوفة كهياكل مصفوفة، فيمكن إجراء العديد من عمليات التقطيع المفيدة (مثل تحديد مصفوفة فرعية، أو تبديل المؤشرات، أو عكس اتجاه المؤشرات) بكفاءة عالية من خلال التلاعب بمتجه التقطيع للهيكل. تعتمد عمليات التقطيع المحتملة على تفاصيل التنفيذ: على سبيل المثال، تسمح لغة FORTRAN بتقطيع عمود واحد من متغير مصفوفة، ولكن ليس صفًا، وتعامله كمتجه؛ بينما تسمح لغة C بتقطيع صف من مصفوفة، ولكن ليس عمودًا.

من ناحية أخرى، من الممكن إجراء عمليات تقطيع أخرى عند تنفيذ أنواع المصفوفات بطرق أخرى.

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

بالنسبة للمصفوفات أحادية البعد، يمكن توفير هذه الميزة كعملية " append( A , x )" التي تزيد من حجم المصفوفة A بمقدار واحد ثم تحدد قيمة العنصر الأخير إلى x . توفر أنواع المصفوفات الأخرى (مثل سلاسل باسكال) عامل تجميع، يمكن استخدامه مع التقطيع لتحقيق هذا التأثير والمزيد. في بعض اللغات، يؤدي تعيين قيمة لعنصر من المصفوفة إلى توسيع المصفوفة تلقائيًا، إذا لزم الأمر، لتشمل هذا العنصر. في أنواع المصفوفات الأخرى، يمكن استبدال الشريحة بمصفوفة ذات حجم مختلف، مع إعادة ترقيم العناصر اللاحقة وفقًا لذلك - كما هو الحال في تعيين القائمة في بايثون " A [5:5] = [10,20,30]"، الذي يُدرج ثلاثة عناصر جديدة (10 و20 و30) قبل العنصر " A [5]". المصفوفات القابلة لتغيير الحجم تشبه من الناحية المفاهيمية القوائم ، والمفهومان مترادفان في بعض اللغات.

يمكن تنفيذ مصفوفة قابلة للتوسيع كمصفوفة ذات حجم ثابت، مع عداد يسجل عدد العناصر المستخدمة فعليًا. appendتعمل العملية على زيادة العداد فحسب؛ حتى يتم استخدام المصفوفة بالكامل، عندها appendقد يتم تعريف العملية بالفشل. هذا تنفيذ لمصفوفة ديناميكية بسعة ثابتة، كما هو الحال في stringنوع باسكال. بدلاً من ذلك، appendقد تقوم العملية بإعادة تخصيص المصفوفة الأساسية بحجم أكبر، ونسخ العناصر القديمة إلى المنطقة الجديدة.

• تحليل الوصول إلى المصفوفة
• نظام إدارة قواعد البيانات المصفوفة
• إزالة التحقق من الحدود
• القيم المنفصلة بفاصل
• فحص الفهرس
• مصفوفة متوازية
• مجموعة متفرقة
• مصفوفة ذات طول متغير

• قاموس NIST للخوارزميات وهياكل البيانات: المصفوفة