قدم بإيجاز الجداول الخطية وكيفية تحقيق جداول سلسلة مزدوجة

العداد الخطي هو بنية خطي ، وهو تسلسل محدود له نفس عنصر بيانات النوع N (n ≥ 0).

1. صفيف
تحتوي الصفيف على حدود علوية وأسفل ، وعناصر الصفيف مستمرة في الحدود العلوية والسفلية.

الرسم التخطيطي لمجموعة 10،20،30 ، 40 ، 50 50 هو كما يلي:

ميزات الصفيف : البيانات المستمرة ؛
الصفيف الأكثر تعقيدًا قليلاً هو مجموعة متعددة الأبعاد ومصفوفة ديناميكية. بالنسبة للغة C ، يتم تحقيق الصفيف متعدد الأبعاد أيضًا من خلال صفيف أبعاد واحد. بالنسبة إلى الصفيف الديناميكي ، فهي مجموعة من قدرة مجموعة الفهرس التي يمكن أن تنمو ديناميكيًا ؛ المتجهات ؛

ثانياً ، قائمة مرتبطة واحدة <BR /> قائمة مرتبطة (قائمة مرتبطة واحدة) هي نوع من القائمة المرتبطة.

المخطط التخطيطي لقائمة مرتبطة واحدة كما يلي:

رأس الرأس فارغ ، عقدة الخلف للرأس هي "العقدة 10" (عقدة البيانات 10) ، وعقدة الخلف "العقدة 10" هي "العقدة 20" (البيانات مع البيانات 10) ،. ..

سلسلة حذف سلسلة واحدة

حذف "العقدة 30"
قبل الحذف: عقدة "العقدة 20" هي "العقدة 30" ، وعقدة "العقدة 30" هي "العقدة 40".
بعد الحذف: عقدة "العقدة 20" هي "العقدة 40".

القائمة المفردة المرتبطة بالعقدة المضافة

أضف "العقدة 15" بين "العقدة 10" و "العقدة 20"
قبل إضافة: عقدة الخلف "العقدة 10" هي "العقدة 20".
بعد إضافة: عقدة الخلف من "العقدة 10" هي "العقدة 15" ، وعقدة الخلف "العقدة 15" هي "العقدة 20".

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

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

المخطط التخطيطي للقائمة المرتبطة المزدوجة هو كما يلي:

الرأس فارغ ، عقدة الخلف هي "العقدة 10" (عقدة البيانات 10) ؛ الخلف هي "العقدة 10" ؛ .

ساعة مزدوجة سلسلة حذف الحذف

حذف "العقدة 30"
قبل الحذف: عقدة "العقدة 20" هي "العقدة 30" ، و pre -node من "العقدة 30" هي "العقدة 20". عقدة "العقدة 30" هي "العقدة 40" ، و pre -node من "العقدة 40" هي "العقدة 30".
بعد الحذف: عقدة الخلف لـ "Node 20" هي "Node 40" ، و Pre -node لـ "Node 40" هي "Node 20".

قائمة ارتباط مزدوجة إضافة العقد

أضف "العقدة 15" بين "العقدة 10" و "العقدة 20"
قبل الإضافة: عقدة الخلف لـ "Node 10" هي "Node 20" ، والعقدة السابقة لـ "Node 20" هي "Node 10".
بعد إضافة: عقدة الخلف من "العقدة 10" هي "العقدة 15" ، و pre -node من "العقدة 15" هي "العقدة 10". عقدة "العقدة 15" هي "العقدة 20" ، والعقدة السابقة من "العقدة 20" هي "العقدة 15".

تم تقديم تنفيذ قائمة السلسلة المزدوجة أدناه ، ويتم تقديم التطبيقات الثلاثة لـ C/C ++/Java على التوالي.

1. C تنفيذ قائمة مرتبطة مزدوجة

قم بتنفيذ ملف القائمة المرتبطة بالدولة الثانية (double_link.h)

 #ifndef_double_link_h#define_double_link_h // قم بإنشاء "قائمة مرتبطة بالدوار". النجاح ، العودة إلى الرأس ؛ النجاح ، إرجاع 0 ؛ العودة إلى 1 للفراغ. extern dlink_is_empty () ؛ النجاح ، العودة إلى مؤشر العقدة. extern void* dlink_get (int index) ؛ النجاح ، العودة إلى مؤشر العقدة. extern void* dlink_get_first () ؛ النجاح ، العودة إلى مؤشر العقدة. extern void* dlink_get_last () ؛ النجاح ، عودة 0 ؛ extern int dlink_insert (int index ، void *pval) ؛ النجاح ، عودة 0 ؛ extern int dlink_insert_first (void *pval) ؛ النجاح ، عودة 0 ؛ extern int dlink_append_last (void *pval) ؛ النجاح ، إرجاع 0 ؛ النجاح ، إرجاع 0 ؛ النجاح ، إرجاع 0 ؛

double_link.c في قائمة مرتبطة اثنين

 #include <stdio.h> #include <malloc.h>/*** c lingle اثنين من القائمة المرتبطة يمكن تخزين البيانات التعسفية. ** Author Skywang* @Date 2013/11/07*/// اثنين من العقد المرتبطة Typedef tag_node {stroct tag_node*prev ؛ لاحظ أن قيمة الرأس لا تخزن قيمة العنصر! التقاطع التقاطع عقدة ثابتة *phead = null ؛ العد الثابت = 0 ؛ النجاح ، العودة إلى مؤشر العقدة. static node *create_node (void *pval) {node *pnode = null ؛ ") PVAL ؛ النجاح ، عودة 0 ؛ int create_dlink () {// إنشاء رأس phead = create_node (null) ؛ إرجاع العدد == 0 ؛} // ارجع إلى "القائمة المرتبطة بالدوار" int dlink_size () {return count ؛} // احصل Node (int index) {ifx <0 || index> = count) {printf ("٪ s فشل! if (index <(count/2)) {int i = 0 ؛ البحث j = 0 ؛ العقدة "static node * g et_first_node () () return get_node (0) ؛} // احصل على" العقدة الأخيرة "static node * get_last_node () {return get_node (count-) ؛} // الحصول في القائمة المرتبطة ثنائية الاتجاه ". النجاح ، قيمة العقدة ؛ void * dlink_get (int index) {node * pindex = get_node (index) ؛ 1 个元素的值 "void* dlink_get_first () {return dlink_get (0) ؛} // 获取" 双向链表中最后 1 个元素的值 "void* dlink_get_last () {return dlink_get (count- 1) ؛} // أدخل "pval" في موضع الفهرس. النجاح ، عودة 0 ؛ int dlink_insert (int index ، void * pval) {// insert header if (index == 0) return dlink_insert_first (pvalt (pval) ؛ // احصل على عقدة العقدة المقابلة للموضع المراد إدراجه. إذا! -> prev-> next = pnode ؛ {node *pnod e = create_node (pval) ؛ ++ ؛ ؛ القائمة المرتبطة بطريقة ". النجاح ، عودة 0 ؛ int dlink_delete (int index) {node *pindex = get_node (index) ؛ > next-> prev = pindex-> ​​prev ؛ pindex-> ​​prev-> next = pindex-> ​​next ؛ free (pindex) ؛ count-؛ return 0 ؛} // 删除第一个节点 int dlink_delete_first () {return DLINK_DELETE (0) ؛} // حذف عقدة int dlink_delete_last () {return dlink_delete (count-) ؛} // Revisit "قائمة مرتبطة ثنائية الاتجاه". النجاح ، عودة 0 ؛ int destroy_dlink () {if (! phead) {printf ("٪ s فشلت! ؛

برنامج اختبار قائمة مرتبطين (DLINK_TEST.C)

 #include <stdio.h> #include "double_link.h"/*** C Language لتنفيذ برنامج اختبار قائمة مرتبطين. ** (01) int_test ()* أظهر "بيانات int" في قائمة مرتبطة اثنين. * (02) string_teest ()* إظهار "بيانات الطبقات" في قائمة مرتبطة اثنين. * (03) Object_teest ()* أظهر "الكائن" في قائمة مرتبطة بالمرتين. ** Author Skywang* date 2013/11/07* /// قائمة مرتبطة ثنائية الاتجاه Void int_teest () {int iarr [4] = {10 ، 20 ، 30 ، 40} ؛ n -----٪ s ------ "، __func __) ؛ create_dlink () ؛ // إنشاء قائمة مرتبطة ثنائية الاتجاه dLink_Insert (0 ، & iarr [0]) ؛ // أدخل البيانات dLink_Insert (0 ، & & ig & & ig & & ig & & & 1]) ؛ Data PrintF ("DLINK_IS_EMPTY () = ٪ D/N" ، DLINK_IS_EMPTY ()) ؛ الحجم من القائمة المرتبطة بالمسافة اثنين ) DLINK_GET (i) ؛ Twenty "،" Thirty "، 0 ، Sarr [0]) ؛ اثنين من القائمة المرتبطة n "، dlink_size ()) ؛ // حجم القائمة المرتبطة اثنين // بطباعة جميع البيانات int i في القائمة المرتبطة اثنين ؛ char *p ؛ int sz = dlink_size () ؛ for (i = 0 ؛ tag_stu {int id ؛ {40 ، {40 ، {40 ، {40 ، "dan"} ،} ؛#define arr_stu_size "، __func __) ؛ create_dlink () ؛ // إنشاء قائمة مرتبطة اثنين dlink_insert (0 ، & arr_stu [0] ) ؛ "DLINK_IS_EMPTY () = ٪ D/N" ، DLINK_IS_EMPLE ()) ؛ اثنين من القائمة المرتبطة // جميع البيانات في القائمة المرتبطة int i ؛ ) DLINK_GET (I) ؛ ) ؛ string_test () ؛ Object_test () ؛ العودة 0 ؛}

نتيجة التشغيل

 ---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = اثنان وثلاثينك (1) = twentdlink_get (2) = 10 -Object_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30 ، vic] dlink_get (1) = [20 ، jody] dlink_get (2) = [10 ، sky]

2. C ++ يدرك قائمة السلسلة المزدوجة

قم بتنفيذ ملف القائمة المرتبطة بالدولة الثانية (doublelink.h)

 #ifndef double_link_hxx#defines double_link_hxx#include <ioStream> باستخدام std. Prev ، dnode *{this-> that- Size () int delete_last () ؛ ) {// إنشاء "السرعة". ملاحظة: لا توجد بيانات تخزين على الرأس! phead = new dnode <T> () ؛ > :: ~ doughlink () {// حذف جميع العقد dnode <T>* ptmp ؛ ؛ قائمة السلسلة 为空 قالب <class t> int doubleLink <T> :: is_empty () {return count == 0 ؛} // 获取第 index 位置的节点 قالب <class t> dnode <t>* doubleLink <T>: : get_node (int index) {// justice paruality if (index <0 || index> = count) {cout << " / العثور على (index <= count/ 2) {int i = 0 ؛ ؛} / عكس البحث j = 0 ؛ ؛ المعبد <class t> trivelink <T> :: get_first () {return get_node (0)->} // احصل على قيمة العقدة الأخيرة. فهرس الموضع قبل القالب <class t> int doublelink <T>: > Prev) ؛ القالب <class t> int doublelink <T>: > التالي = count ++ ؛ > prev = pnode ؛ > التالي-Prev = Pindex- t> int doubleLink <T> :: delete_first () {return del (0) ؛} // 删除最后一个节点 template <class t> int doublelink <t> :: delete_last () {return del (count-) ؛} #endif

ملف اختبار قائمة مرتبطة اثنين (DLINKTEST.CPP)

 #include <ioStream> #include "doublelink.h" std ؛ --- "<< endl ؛ // قم بإنشاء قائمة مرتبطة ثنائية الاتجاه doubleLink <int>* pdLink = جديد doubleLink <int> () ؛ pdlink-> إدراج (0 ، 20) PdLink-> append_last (10) << "is_empty () =" << pdlink-> is_empty () << endl ؛ << endl ؛ -> get (i) << endl ؛} void string_test () {String sarr [4] = {"Ten" ، "Twenty" ، "Thirty" ، "Forty"} ؛ ---- "<< endl ؛ العنصر الثاني في SARR في أول pdlink-> append_last (Sarr [0]) ؛ ) ؛ () = "<< pdlink-> size () << endl ؛ // جميع البيانات int sz = pdlink-> size () ؛ for (int i = 0 ؛ i <sz ؛ i ++)" <") = "<< pdlink-> get (i) << endl ؛} struct stu {int id ؛ char name [20] ؛} ؛ static stu arr_stu [] = {10 ،" sky "، {20 20 ، "} ، {30 ،" vic "} ، {40 ،" dan "،} ؛#define arr_stu_size cout <<"/n ---- object_test ---- "<< endl ؛ // إنشاء اثنين- قائمة المرتبطة طريقة doublelink <stu>* pdlink = جديد doublelink <stu> () ؛ > append_last (ARR_STU [0]) إلى الموضع الأول // ما إذا كانت القائمة المرتبطة ثنائية الاتجاه فارغة << "is_empty () =" << pdlink-> is_empty () << endl ؛ = "<< pdlink-> size () << endl ؛ // طباعة جميع البيانات int sz = pdlink-> size () في القائمة المرتبطة ثنائية الاتجاه ؛ = 0 ؛ i <sz ؛ i ++) {p = pdlink-> get (i) ؛ Main () {int_teest () ؛ string_test () ؛ Object_test () ؛ العودة 0 ؛}

مثال الوصف

في المثال أعلاه ، وضعت "البيان" و "تنفيذ" القائمة المرتبطة بالدورين في ملف الرأس. تحذرنا مواصفات البرمجة: افصل إعلان المطالبة وتنفيذها ، وكان مبلغ ملف الرأس (ملف .h أو .hpp) يحتوي فقط على البيان ، وكان مسؤولاً عن التنفيذ في ملف التنفيذ (ملف .cpp)!
فلماذا تفعل هذا؟ هذا لأنه في تنفيذ قائمة مرتبطة بالمسارين ، يتم اعتماد القالب ؛ بكل بساطة ، إذا تم الإعلان عنها في doublelink. لأسباب محددة ، يمكنك الرجوع إلى "لماذا لا يمكن لمرسلات C ++ دعم تجميع منفصل للقوالب".

نتيجة التشغيل

 ---- int_test ---- is_empty () = 0size () = 3pdLink (0) = 30pdLink (1) = 20pdLink (2) = 10 ---- string_test ----- فارغ () = 0Size () = 3pdLink (0) = thirtypdLink (1) = TenyPdLink (2) = Ten ---- Object_teest ---- is_empty () = 0size () = 3pdLink (0) = [30 ، VIC] pdLink (1) = [ 20 20 ، جودي] pdlink (2) = [10 ، السماء]

3. جافا تدرك قائمة السلسلة المزدوجة

تنفيذ doublelink.java

 /*** قائمة Java's اثنين مرتبطة. * ملاحظة: هناك قائمة مرتبطة بالمسارين في حزمة مجموعة Java. / Top Headpate DNODE <T> MED ؛ {this.value = value ؛ ملاحظة: لا توجد بيانات تخزين على الرأس! Mead = new dnode <T> (NULL ، NULL) ؛ Return Mcount ؛} // ما إذا كانت القائمة المرتبطة فارغة isempty () {return mcount == 0 ؛} // العقدة الخاصة dnode <t> getNode (int index) {IFX) {index <0 || index> = MCOUNT) رمي indexoutofbound () ؛} // 反向查找 dnode <T> rnode = mhead.prev ؛ int reindex = mcount - index ؛ for (int j = 0 ؛ j <rindex ؛ j ++) rnode = rnode / احصل على قيمة عقدة الفهرس. <T> (T ، Mhead ، Mead) ؛ t> (t ، inode.prev ، inode) ؛ public void insertfirst (t t) {insert (0 ، t) ؛} // أضف العقدة إلى نهاية القائمة المرتبطة بملحق الفراغ العام (t t) {dnode <t> new dnode <t> (t ، mhead. Prev Mead) ؛ .next = inode.next. العقدة العامة void deletelast () {del (mcount-) ؛}}

برنامج اختبار (dlinktest.java)

 /*** قائمة Java's اثنين مرتبطة. * ملاحظة: هناك قائمة مرتبطة بالمسارين في حزمة التجميع التي تأتي مع Java. Two-table Table Operation int static void int_teest () {int [] {10 ، 20 ، 40} ؛ = DoubleLink جديد <Nereger> () ؛ الموقف الأول // ما إذا كانت القائمة المرتبطة بالمسافة هي system.out.printf ("isempty () = ٪ b/n" ، dlink.isempty ()) ؛ d/n "، dlink.size ()) ؛ // طباعة جميع العقد (int i = 0 ؛ i <dlink.size () ؛ i ++) system.out .println (" dLink ("+i+") = "+dlink.get (i)) ؛} private static void string_test () {string [] sarr = {" ten "،" Twenty "،" Thirty "،" Forty "} ؛ بر في الموضع الأول dlink.appendlast (sarr [0]) الموضع الأول // ما إذا كانت القائمة المرتبطة اثنين هي system.out.printf ("isempty () = ٪ b/ n" ، dlink.isempty ()) ؛// system.out.printf ("size () = ٪ d/ n "، dlink.size ()) ؛ // طباعة جميع العقد لـ (int i = 0 ؛ i <dlink.size () ؛ i ++) system.out.println (" dLink ("+i+ ") ="+dlink.get (i)) ؛} // الطالب الداخلي للفئة الثابتة {private string id student (int ، اسم السلسلة) {this.id = id ؛ ouverridepublic string tostring () {"+id+" ، "+name+"] "؛} tudent [] studers = new student [] {New Student (10 ،" Sky ") ، New Student (20 ،" Jody ") ، New الطالب (30 ، "طالب جديد ،" دان ") ،} ؛ قائمة المرتبطة ثنائية الاتجاه <Student> dLink = New DoubleLink <Student> () ؛ العنصر الأول في الطلاب إلى dlink.insertfirst (الطلاب [الطلاب [الطلاب [2]) ؛ printf ("isempty () = ٪ b/n" ، dlink.isempty ()) ؛ العقد لـ (int i = 0 ؛ i <dlink.size ()) ؛ static void main (string [] Arts) {int_test () ؛ string_test () ؛ Object_test () ؛ }}

نتيجة التشغيل

 ---- int_test ---- isEmpty () = falesesize () = 3dlink (0) = 30dlink (1) = 20dlink (2) = 10 ---- string_test ———- isempty () = falsesize () =) =) 3dlink (0) = ThirtydLink (1) = TwentyDlink (2) = Ten ---- Object_teest --- isEmpty () = falsesize () = 3dlink (0) = [30 ، Vic] dLink (1) = [20 20 20 20 ، جودي] dlink (2) = [10 ، السماء]

ما سبق هو كل محتويات هذه المقالة.