1. مقدمة
في الآونة الأخيرة ، عند مراجعة هياكل البيانات والخوارزميات ، تستخدم بعض مشكلات الخوارزمية فكرة المكدس ، وعندما يتعلق الأمر بالمداخن ، يتعين علينا التحدث عن القوائم المرتبطة. المصفوفات والقوائم المرتبطة هي أساس هياكل التخزين الخطي ، والكوابات والقوائم هي تطبيقات هياكل التخزين الخطي ~
تشرح هذه المقالة بشكل أساسي نقاط المعرفة الأساسية للقوائم المرتبطة الفردية ، وتقدم مقدمة بسيطة. إذا كان هناك أي خطأ ، يرجى تصحيحه.
2. المراجعة والمعرفة
الحديث عن القوائم المرتبطة ، دعنا نذكر أولاً الصفيف. إن مقارنتها مع المصفوفات تجعلك تفهم جدًا بنية التخزين للقوائم المرتبطة جيدًا.
2.1 راجع المصفوفة
لقد تعلمنا صفائف في كل من C و Java:
مزايا المصفوفات:
عيوب المصفوفات:
2.2 وصف قائمة الارتباط
بعد قراءة المصفوفة ، ارجع إلى قائمتنا المرتبطة:
يتم تخصيص العقد N بشكل تقديري وتوصيلها ببعضها البعض من خلال مؤشرات. تحتوي كل عقدة على عقدة سلف واحدة فقط ، وكل عقدة تحتوي على عقدة واحدة فقط ، وعقدة الأولى لا تحتوي على عقدة سلف ، وعقدة الذيل لا تحتوي على عقدة لاحقة.
مزايا القائمة المرتبطة:
عيوب القوائم المرتبطة:
سأشرح المصطلحات المتعلقة بالقائمة المرتبطة من خلال الصورة أعلاه:
لتحديد قائمة مرتبطة ، نحتاج فقط إلى مؤشر الرأس ، ويمكن استنتاج القائمة المرتبطة بأكملها من خلال مؤشر الرأس ~
هناك عدة فئات من القوائم المرتبطة:
1. جدول ارتباط في اتجاه واحد
2. جدول الارتباط ثنائي الاتجاه
3. قائمة روابط إعادة التدوير
ما تحتاج إلى تذكره عند تشغيل قائمة مرتبطة هو:
يشير حقل المؤشر في العقدة إلى عقدة!
3. قائمة ارتباط تنفيذ Java
الخوارزمية:
أولاً ، نحدد الفصل كعقدة
لراحة العملية ، قمت بتعريفها مباشرة على أنها عامة.
عقدة الفئة العامة {// Data Domain Public Data ؛ // مجال المؤشر ، مشيرًا إلى العقدة العامة العقدة التالية ؛ NODE () {} node (int data) {this.data = data ؛ } العقدة العامة (بيانات int ، العقدة التالية) {this.data = data ؛ this.next = التالي ؛ }} 3.1 إنشاء قائمة مرتبطة (إضافة عقد)
أدخل البيانات في القائمة المرتبطة:
/*** إضافة بيانات إلى القائمة المرتبطة** param بيانات القيمة المراد إضافتها*/public static void adddata (int value) {// تهيئة العقدة المراد إضافتها newNode = new node (value) ؛ // عقدة العقدة المؤقتة temp = head ؛ // ابحث عن عقدة الذيل بينما (temp.next! = null) {temp = temp.next ؛ } // الحالة التي تم فيها تضمين NODE.NEXT NODE NULL ~ temp.next = newNode ؛ } 3.2 اجتياز القائمة المرتبطة
لقد كتبنا طريقة الإضافة أعلاه ، والآن سوف نمر بها لمعرفة ما إذا كان صحيحًا ~~~
ابدأ من العقدة الأولى واستمر في البحث عن الخلف حتى لا توجد بيانات على العقدة اللاحقة:
/ *** اجتياز القائمة المرتبطة** Param Head Head Head Node*/ Public Static Void Traverse (Node Head) {// Node Crepary ، ابدأ من العقدة الأولى temp = head.next ؛ بينما (temp! = null) {system.out.println ("اتبع الحساب الرسمي java3y:" + temp.data) ؛ // متابعة مع temp = temp.next ؛ }}نتيجة:
3.3 أدخل العقدة
/*** insert Node** param head head pointer* param index موضع إدراجها* قيمة قيمة param ليتم إدراجها*/public static void insertnode (head node ، ind int ، int value) {// first all all all ، you us ust to to to explistr in explists (extrint <1 || index> internallenge (head) + 1) غير قانوني.")؛ يعود؛ } // العقدة المؤقتة ، ابدأ من عقدة البداية temp = head ؛ // انقر فوق الموضع الحالي للمادة الحالية int currentpos = 0 ؛ // تهيئة العقدة المراد إدراجها insertNode = عقدة جديدة (قيمة) ؛ بينما تم العثور على (temp.next! = null) {// تم العثور على موقع العقدة السابقة إذا ((الفهرس - 1) == currentpos) {// temp يمثل العقدة السابقة // نقطة المؤشر الأصلي من العقدة السابقة إلى العقدة المدرجة إلى insertnode.next = temp.next ؛ // نقطة حقل مؤشر العقدة السابقة إلى العقدة المراد إدراجها temp.next = insertNode ؛ يعود؛ } CurrentPos ++ ؛ temp = temp.next ؛ }} 3.4 احصل على طول القائمة المرتبطة
من السهل جدًا الحصول على طول القائمة المرتبطة. يمكن القيام به عن طريق اجتيازه والحصول على +1 لكل عقدة ~
/ *** احصل على طول القائمة المرتبطة* param head head pointer*/ public static int linklistlength (node head) {int length = 0 ؛ // العقدة المؤقتة ، ابدأ من العقدة الأولى temp = head.next ؛ // ابحث عن عقدة الذيل بينما (temp! = null) {length ++ ؛ temp = temp.next ؛ } طول الإرجاع ؛ } 3.5 حذف العقد
إن حذف العقدة في موقع معين يشبه في الواقع إلى حد كبير عقدة الإدراج ، وتحتاج أيضًا إلى العثور على العقدة السابقة. قم بتغيير حقل المؤشر للعقدة السابقة ويمكنك حذفه ~
/** * حذف العقد وفقًا للموقع * * Param Head Pointer * Param INDEX المراد حذفه */public static void deletenode (Head Head ، int index) {// أولاً وقبل كل شيء ، تحتاج إلى تحديد ما إذا كان الموقع المحدد قانونيًا ، إذا كان (index <1 || index> linklistlength (head) + 1) يعود؛ } // العقدة المؤقتة ، ابدأ من عقدة البداية temp = head ؛ // الموقع الحالي لتجاوز السجل هو int currentpos = 0 ؛ بينما (temp.next! = null) {// تم العثور على موقع العقدة السابقة إذا ((الفهرس - 1) == CurrentPos) {// temp يمثل العقدة السابقة // temp.next تمثل العقدة التي تريد حذفها // تخزين العقدة التي تريد حذفها للعقدة deletenode = temp.next ؛ // العقدة التالية التي تريد حذف العقدة يتم تسليمها إلى العقدة السابقة للتحكم في temp.next = deletenode.next ؛ // ستقوم Java بإعادة تدويره ، ويجب ألا يكون من المنطقي ضبطه على NULL (أعتقد شخصياً ، إذا لم يكن صحيحًا ، فيرجى الإشارة إلى ذلك ~) DELETENODE = NULL ؛ يعود؛ } CurrentPos ++ ؛ temp = temp.next ؛ }} 3.6 فرز القائمة المرتبطة
لقد تحدثت بالفعل عن 8 خوارزميات فرز [ملخص لثمانية خوارزميات فرز]. سأختار فرز فقاعة بسيطة هذه المرة (في الواقع ، أريد أن أكتب نوعًا سريعًا ، لكن من الصعب بعض الشيء تجربتها ...)
/ ** * فرز القائمة المرتبطة * * param head * */ public static void sortLinkList (node head) {node currentNode ؛ العقدة NextNode ؛ لـ (currentNode = head.next ؛ currentnode.next! = null ؛ currentNode = currentnode.next) {for (nextNode = head.next ؛ nextNode.next! = null ؛ nextNode = nextNode.next) {if (nextNode.data> nextnode.next.data) nextNode.data = nextNode.next.data ؛ nextNode.next.data = temp ؛ }}}} 3.7 ابحث عن العقدة K-Last في القائمة المرتبطة
هذه الخوارزمية مثيرة للاهتمام للغاية: تعيين مؤشرتين P1 و P2 لجعل العقد P2 K أسرع من P1 ، وتجتاز إلى الوراء في نفس الوقت. عندما يكون P2 فارغًا ، فإن P1 هي العقدة الأخيرة K-Th
/ *** ابحث عن k-th حتى العقدة الأخيرة في القائمة المرتبطة (تعيين مؤشرين p1 و p2 ، وجعل p2 k أسرع من p1 ، وتجارة للخلف في نفس الوقت. عندما يكون p2 فارغا ، p1 هو k-th حتى kode kode** param head* param k-th حتى آخر node*/ public static node LinkListlength (Head) NULL ؛ P1 ؛
3.8 حذف البيانات المكررة في القائمة المرتبطة
إنه مشابه لفرز الفقاعة ، طالما أنه متساوٍ ، يمكن حذفه ~
/ ** * حذف بيانات مكررة على القائمة المرتبطة (على غرار الفقاعات ، فإنها تعادل الحذف) * * Param Head Head Node */ Public Static Void deleteduplecate (Node Head) {// العقدة المؤقتة ، (بدءًا من العقدة الأولى-> العقدة مع البيانات الحقيقية) Node Temp = Head.Next ؛ // العقدة التالية للعقدة الحالية (العقدة الأولى) node nextNode = temp.next ؛ بينما (temp.next! = null) {بينما nextNode.next! = null) {if (nextNode.next.data == nextNode.data) {// حذف العقدة التالية (نقاط العقدة الحالية إلى العقدة التالية) nextNode.next = nextNode.next.next.next ؛ } آخر {// متابعة مع nextNode التالي = nextNode.next ؛ }} // الجولة التالية من temp = temp.next ؛ }} 3.9 الاستعلام عن العقد الوسيطة للقائمة المرتبطة
هذه الخوارزمية مثيرة للاهتمام أيضًا: مؤشر يأخذ خطوة واحدة في كل مرة ، وهو مؤشر يتطلب خطوتين في كل مرة ، ثم يأخذ خطوة واحدة ، وهي العقدة الوسيطة
/ *** Query العقدة الوسيطة لقائمة واحدة مرتبطة*/ public static node searchmid (node head) {node p1 = head ؛ العقدة p2 = الرأس ؛ // اتخذ خطوة واحدة وخطوة واحدة خطوتين حتى تصبح فارغة. العقدة الوسطى التي تصل إليها (p2! = null && p2.next! = null && p2.next.next! = null) {p1 = p1.next ؛ p2 = p2.next.next ؛ } إرجاع p1 ؛ }3.10 إخراج الجداول المفردة من ذيل إلى رأس متكرر
/ *** الإخراج قائمة مرتبطة واحدة من الذيل إلى الرأس بواسطة متكرر** Param Head Head Node*/ public static void printListReverSely (node head) {if (head! = null) {prinistReverSely (head.next) ؛ System.out.println (Head.Data) ؛ }} 3.11 قائمة الارتباط العكسي
/ *** قم بتنفيذ انعكاس القائمة المرتبطة** param عقدة الرأس للقائمة المرتبطة*/ public static node reverselinklist (عقدة العقدة) {node prev ؛ if (node == null || node.next == null) {prev = node ؛ } آخر {node tmp = resplistelinklist (node.next) ؛ node.next.next = node ؛ node.next = null ؛ PRED = TMP ؛ } إرجاع السابق ؛ } مرجع إلى قائمة الارتباط العكسي من: //www.vevb.com/article/136185.htm
4. أخيرًا
ليس من الصعب فهم القائمة المرتبطة نفسها ، ولكن يمكن أن تسبب الصداع عند القيام بعمليات ذات صلة. Head.Next التالي التالي التالي .... (ما زلت ضعيفة في الخوارزمية ... ليس لدي ما يكفي من العقول ...) كتبت هذا الشيء الصغير بعد يومين ...
يمكنك فعل أي شيء عن طريق معرفة مؤشر رأسه عند تشغيل قائمة مرتبطة.
1. أضف بيانات إلى القائمة المرتبطة
2. اجتياز القائمة المرتبطة
3. أدخل العقد في القائمة المرتبطة في موقع معين
4. احصل على طول القائمة المرتبطة
5. حذف العقدة في الموقع المحدد
6. فرز القائمة المرتبطة
7. ابحث عن العقدة K-Last في القائمة المرتبطة
8. حذف البيانات المكررة في القائمة المرتبطة
9. الاستعلام عن العقد الوسيطة للقائمة المرتبطة
10. إخراج طاولة مرتبط واحد من الذيل إلى الرأس بشكل متكرر
11. قائمة الارتباط العكسي
ملاحظة: سيكون تطبيق الجميع مختلفًا ، لذلك ستتغير بعض التفاصيل الصغيرة حتماً ، ولا توجد طريقة ثابتة لكتابتها ، حتى تتمكن من إدراك الوظائف المقابلة ~
لخص
ما سبق هو المحتوى الكامل لهذه المقالة. آمل أن يكون لمحتوى هذه المقالة قيمة مرجعية معينة لدراسة أو عمل الجميع. إذا كان لديك أي أسئلة ، فيمكنك ترك رسالة للتواصل. شكرا لك على دعمك إلى wulin.com.
مراجع: