جدول محاكاة واحد مرتبط
الجدول الخطي:
الجداول الخطية (التي تسمى أيضًا الجداول المتسلسلة) هي هياكل البيانات الأساسية والأبسط والأكثر استخدامًا.
العلاقة بين عناصر البيانات في الجدول الخطي هي علاقة فردية ، أي ، باستثناء عناصر البيانات الأولى والأخيرة ، يتم توصيل عناصر البيانات الأخرى بالنهاية.
البنية المنطقية للجداول الخطية بسيطة ، والتي من السهل تنفيذها وتشغيلها.
في التطبيقات العملية ، يتم استخدام الجداول الخطية في شكل جداول خطية خاصة مثل المداخن والقوائم والسلاسل.
الخصائص الأساسية للهيكل الخطي هي:
1. يجب أن يكون هناك "عنصر أول" فريد في المجموعة ؛
2. يجب أن يكون هناك "عنصر آخر" فريد في المجموعة ؛
3. باستثناء العنصر الأخير ، هناك خليفة فريد (أحدث عنصر) ؛
4. باستثناء العنصر الأول ، هناك محرك أمامي فريد (قطعة أمامية).
القائمة المرتبطة: قائمة مرتبطة
القائمة المرتبطة هي بنية تخزين غير مستمرة وغير متسلسلة على وحدة التخزين المادية. يتمثل الترتيب المنطقي لعناصر البيانات في أن كل عنصر بيانات يتم تنفيذه من خلال ترتيب ارتباط المؤشر في القائمة المرتبطة موجود في "نقطة الارتباط".
الرابط هو كائن فئة ، ويمكن استدعاء هذا النوع رابط. هناك العديد من الروابط المماثلة في القائمة المرتبطة ، ويحتوي كل رابط على حقل يشار إليه بعد ذلك إلى الرابط التالي.
يحمل كائن القائمة المرتبط نفسه مرجعًا إلى عقدة الارتباط الأولى. (إذا لم يكن هناك أولا ، فلا يمكن تحديد موقعه)
لا يمكن للقائمة المرتبطة الوصول مباشرة إلى عناصر البيانات مثل صفيف (باستخدام المشتركين) ، ولكن يجب وضعها مع العلاقة بين البيانات ، أي ، الوصول إلى الرابط التالي المشار إليه بواسطة عقدة الارتباط ، ثم العنوان التالي ، حتى يتم الوصول إلى البيانات المطلوبة وتوقيت التعقيد الزمني لإدراج وحذف البيانات المطلوبة في الرأس (1) فقط ، لأن التورط المرجعي فقط للإيجاد ، الحذف المحدد. تتطلب هذه العمليات متوسط البحث في نصف العقد في القائمة المرتبطة ، مع كفاءة O (N).
قائمة واحدة مرتبطة:
يتم تمثيل الجدول الخطي بـ "تسلسل العقد" ويسمى قائمة مرتبطة خطية (قائمة مرتبطة واحدة)
إنه بنية بيانات الوصول إلى سلسلة ، باستخدام مجموعة من وحدات التخزين مع عناوين تعسفية لتخزين عناصر البيانات في جدول خطي. (هذه المجموعة من خلايا الذاكرة يمكن أن تكون إما مستمرة أو متقطعة)
هيكل عقدة الارتباط:
بيانات حقل البيانات التي تخزن قيم العقدة ؛ حقل المؤشر (حقل السلسلة) الذي يخزن المرجع العقدة بعد ذلك
تربط القائمة المرتبطة العقد n من الجدول الخطي معًا بترتيبها المنطقي من خلال مجال الارتباط لكل عقدة.
تسمى قائمة مرتبطة مع حقل ارتباط واحد فقط لكل عقدة قائمة ارتباط واحد. في اتجاه واحد ، لا توجد سوى إشارات إلى العقيدات اللاحقة.
/*** القائمة المرتبطة الفردية: طريقة إدراج الرأس والخروج الأول* يسمى الجانب الأيسر من القائمة المرتبطة رأس السلسلة ويسمى الجانب الأيمن ذيل السلسلة. * يتم الحصول على طريقة إدراج الرأس لإنشاء قائمة مرتبطة واحدة من خلال عرض الطرف الأيمن للقائمة المرتبطة على أنها ثابتة ، وتستمر القائمة المرتبطة في التمدد إلى اليسار. * أول شيء يأتي من طريقة إدراج الرأس هو Node Node * Author Stone */ Public Class SingleLinkedList <T> {Private Link <T> أولاً ؛ . } public void insertFirst (t data) {// insert في رأس ارتباط السلسلة <T> newLink = New Link <T> (data) ؛ newLink.next = أولاً ؛ // يشير بجوار العقدة الجديدة إلى العقدة السابقة أولاً = newLink ؛ } الرابط العام <T> deletefirst () {// حذف رابط رأس السلسلة <T> temp = first ؛ أولا = الأول. // تغيير العقدة الأولى لإرجاع درجة الحرارة ؛ } الرابط العام <T> Find (t t) {link <t> find = first ؛ بينما (البحث! = null) {if (! find.data.equals (t)) {find = find.next ؛ } آخر {break ؛ }} العثور على ؛ } الرابط العام <T> delete (t t) {if (isempty ()) {return null ؛ } آخر {if (first.data.equals (t)) {link <t> temp = first ؛ أولا = الأول. // تغيير العقدة الأولى إلى درجة حرارة الإرجاع العقدة التالية ؛ }} link <t> p = first ؛ Link <t> q = first ؛ بينما (! } آخر {q = p ؛ p = p.next ؛ }} q.next = p.next ؛ العودة P ؛ } public void displaylist () {// transip system.out.println ("list (first-> last):") ؛ Link <t> current = first ؛ بينما (current! = null) {current.displayLink () ؛ الحالي = current.next ؛ }} public void displistlisterSe () {// رابط اجتياز عكسي <T> p = first ، q = first.next ، t ؛ بينما يتم عكس (Q! = null) {// مؤشر ، فإن ترتيب البيانات المسحوب هو متخلف t = q.next ؛ // no3 if (p == first) {// عندما يكون الرأس الأصلي ، يجب أن يكون. } q.next = p ؛ // no3 -> no1 مؤشر عكس p = q ؛ // البدء هو عكس Q = t ؛ // no3 ابدأ} // في IF في الحلقة أعلاه ، أولاً. بعد الانعكاس ، يتم تعيين P إلى أولاً أولا = P ؛ قائمة العرض () ؛ } رابط الفئة <T> {// Link Point T Data ؛ // رابط حقل البيانات <T> التالي ؛ // المؤشر اللاحق ، رابط مجال سلسلة العقدة (بيانات t) {this.data = data ؛ } void displaylink () {system.out.println ("البيانات هي" + data.toString ()) ؛ }} public static void main (string [] args) {singleLinkedList <integer> list = new SingLelinkedList <integer> () ؛ list.insertfirst (33) ؛ list.insertfirst (78) ؛ list.insertfirst (24) ؛ list.insertfirst (22) ؛ list.insertfirst (56) ؛ list.displaylist () ؛ list.deletefirst () ؛ list.displaylist () ؛ System.out.println ("Find:" + list.find (56)) ؛ System.out.println ("Find:" + list.find (33)) ؛ System.out.println ("DELETE Find:" + list.delete (99)) ؛ System.out.println ("delete find:" + list.delete (24)) ؛ list.displaylist () ؛ System.out.println ("--- عكس ----") ؛ list.displayListerSe () ؛ }}مطبعة
القائمة (أولاً-> أخيرا): البيانات هي 56 البيانات هي 22 البيانات هي 24 البيانات هي 78 البيانات هي 33 قائمة (أولاً-> آخر): البيانات 22 البيانات هي 24 البيانات 78 البيانات هي 33 العثور على: null find: linked_list.singleLinkedListrDELINK@4B71BBC9 DELETE Find: null DELETE البحث: linked_list.singlelinkedlistredlink@17dfafd1 قائمة (أولاً-> الأخير): البيانات هي 22 البيانات هي 78 البيانات 33 --- قائمة --- القائمة (أولاً-> الأخير): البيانات 33 هي 78 البيانات هي 22 البيانات
قائمة واحدة مرتبطة: طريقة إدراج الذيل ، مرة أخرى في البداية - إذا تم إصلاح الطرف الأيسر من القائمة المرتبطة ، فستستمر القائمة المرتبطة في التمدد إلى اليمين ، وتسمى طريقة إنشاء قائمة مرتبطة.
عند إنشاء قائمة مرتبطة مع طريقة إدخال الذيل ، يتم إصلاح مؤشر الرأس ، لذلك يجب إعداد مؤشر الذيل ليتم تمديده إلى يمين القائمة المرتبطة.
أول ما يأتي من طريقة إدخال الذيل هو عقدة الرأس.
الطبقة العامة SingLelinkedList2 <T> {Link Private <T> Head ؛ . } public void insertlast (t data) {// insert link <t> newLink = New Link <T> (data) ؛ if (head! = null) {link <t> nextp = head.next ؛ if (nextp == null) {head.next = newLink ؛ } آخر {link <t> rear = null ؛ بينما (nextp! = null) {rear = nextp ؛ NextP = nextp.next ؛ } reach.next = newLink ؛ }} آخر {head = newLink ؛ }} الرابط العام <T> DELETELAST () {// حذف ذيل الرابط السلسلة <T> p = head ؛ Link <t> q = head ؛ في حين أن (p.next! = null) {// العقدة التالية من p ليست فارغة ، Q تساوي P الحالي (أي ، Q هي السابقة و P هي العلامة التالية). عندما تنتهي الحلقة ، تكون Q مساوية للنهاية قبل الأخيرة من السلسلة Q = P ؛ p = p.next ؛ } // delete q.next = null ؛ العودة P ؛ } الرابط العام <T> Find (t t) {link <t> find = head ؛ بينما (البحث! = null) {if (! find.data.equals (t)) {find = find.next ؛ } آخر {break ؛ }} العثور على ؛ } الرابط العام <T> delete (t t) {if (isempty ()) {return null ؛ } آخر {if (head.data.equals (t)) {link <t> temp = head ؛ الرأس = head.next ؛ // تغيير العقدة الأولى لإرجاع درجة الحرارة ؛ }} Link <t> p = head ؛ Link <t> q = head ؛ بينما (! } آخر {q = p ؛ p = p.next ؛ }} q.next = p.next ؛ العودة P ؛ } public void displaylist () {// travel system.out.println ("list (head-> last):") ؛ Link <t> current = head ؛ بينما (current! = null) {current.displayLink () ؛ الحالي = current.next ؛ }} public void displistreverse () {// رابط اجتياز عكسي <T> p = head ، q = head.next ، t ؛ بينما (q! = null) {// يتم عكس المؤشر ، وترتيب البيانات المسحور متخلف t = q.next ؛ // no3 if (p == head) {// عندما يكون الرأس الأصلي ، يجب أن يكون. } q.next = p ؛ // no3 -> no1 مؤشر عكس p = q ؛ // البدء هو عكس Q = t ؛ // no3 ابدأ} // في إذا في الحلقة أعلاه ، يكون الرأس. بعد الانقلاب ، يتم تعيين P لرأس الرأس = P ؛ قائمة العرض () ؛ } رابط الفئة <T> {// Link Point T Data ؛ // رابط مجال البيانات <T> التالي ؛ // مؤشر متتالي ، رابط مجال سلسلة العقدة (T Data) {this.data = data ؛ } void displaylink () {system.out.println ("البيانات هي" + data.toString ()) ؛ }} public static void main (string [] args) {singleLinkedList2 <Steger> list = new SingLeLinKedList2 <integer> () ؛ list.insertlast (33) ؛ list.insertlast (78) ؛ list.insertlast (24) ؛ list.insertlast (22) ؛ list.insertlast (56) ؛ list.displaylist () ؛ list.deletelast () ؛ list.displaylist () ؛ System.out.println ("Find:" + list.find (56)) ؛ System.out.println ("Find:" + list.find (33)) ؛ System.out.println ("DELETE Find:" + list.delete (99)) ؛ System.out.println ("DELETE Find:" + list.delete (78)) ؛ list.displaylist () ؛ System.out.println ("---- عكس -----") ؛ list.displayListerSe () ؛ }}مطبعة
القائمة (رأس-> أخيرا): البيانات هي 33 البيانات هي 78 البيانات هي 24 البيانات هي 22 البيانات هي 56 قائمة (رأس-> آخر): البيانات 33 البيانات 78 البيانات 24 البيانات 22 البحث العثور على: linked_list.singlelinkedlist2derlink@17dfafd1 قائمة (Head-> Last): البيانات هي 33 البيانات هي 24 البيانات 22 --- قائمة --- القائمة (الرأس-> الأخير): 22 البيانات هي 24 البيانات هي 33 البيانات 33
محاكاة قائمة مرتبطة مزدوجة النتيجة لتنفيذ مكدس وقوائم مع قوائم مرتبطة
القائمة المرتبطة مزدوجة الانتشار:
القائمة المرتبطة المزدوجة تشبه إلى حد كبير القائمة المرتبطة التقليدية. إنه يحتوي فقط على سمة جديدة - أي إشارة إلى الرابط الأخير هو الخلفية.
وبهذه الطريقة ، سيصبح الإدراج في نهاية السلسلة أمرًا سهلاً للغاية. ما عليك سوى تغيير الجزء الخلفي إلى العقدة المضافة حديثًا ، دون أن يبحث عن العقدة الأخيرة ، لذلك هناك إدراج و insertlast
عند حذف رأس السلسلة ، تحتاج فقط إلى تغيير النقطة المرجعية ؛ عند حذف ذيل السلسلة ، تحتاج إلى تفريغ العقدة التالية للعقدة قبل الأخيرة.
لا توجد نقاط مرجعية لها ، لذلك هناك حاجة إلى حلقة لقراءة العملية
/ *** قائمة مرتبطة مزدوجة* @Author Stone*/ Class Public Class TwoEndPointList <T> {Link Private <T> Head ؛ // First Node Private Link <T> الخلفية ؛ // Tail Pointer Public ToinPointList () {} pular t peekhead () {if (head! = null) {return head.data ؛ } إرجاع فارغ ؛ } boolean public isempty () {return head == null ؛ } public void insertFirst (t data) {// insert to the head of the chain link <t> newLink = new link <t> (data) ؛ newLink.next = الرأس ؛ // يشير الجزء التالي من العقدة الجديدة إلى رأس العقدة السابق = newLink ؛ } public void insertlast (t data) {// insert link <t> newLink = New Link <T> (data) ؛ if (Head == NULL) {rear = null ؛ } if (الخلفية! = null) {reial.next = newLink ؛ } آخر {head = newLink ؛ head.next = الخلفية ؛ } الخلفية = newLink ؛ . Link <t> temp = head ؛ الرأس = head.next ؛ // قم بتغيير العقدة الأولى لتكون العقدة التالية if (head == null) {<span style = "white-space: pre"> </span> reach = head ؛ } إرجاع temp.data ؛ } prinic t find (t t) {if (isempty ()) {return null ؛ } Link <t> find = head ؛ بينما (البحث! = null) {if (! find.data.equals (t)) {find = find.next ؛ } آخر {break ؛ }} if (find == null) {return null ؛ } return find.data ؛ } t delete (t t) {if (isempty ()) {return null ؛ } آخر {if (head.data.equals (t)) {link <t> temp = head ؛ الرأس = head.next ؛ // قم بتغيير العقدة الأولى إلى العقدة التالية Temp.Data ؛ }} Link <t> p = head ؛ Link <t> q = head ؛ بينما (! p.data.equals (t)) {if (p.next == null) {// تشير إلى أنه لم يتم العثور على عودة فارغة في نهاية السلسلة ؛ } آخر {q = p ؛ p = p.next ؛ }} q.next = p.next ؛ إرجاع P.Data ؛ } public void displaylist () {// travel system.out.println ("list (head-> last):") ؛ Link <t> current = head ؛ بينما (current! = null) {current.displayLink () ؛ الحالي = current.next ؛ }} public void displistreverse () {// عكسي اجتياز إذا (isEmpty ()) {return ؛ } link <t> p = head ، q = head.next ، t ؛ بينما (q! = null) {// يتم عكس المؤشر ، وترتيب البيانات المسحور متخلف t = q.next ؛ // no3 if (p == head) {// عندما يكون الرأس الأصلي ، يجب أن يكون. } q.next = p ؛ // no3 -> no1 مؤشر عكس p = q ؛ // البدء هو عكس Q = t ؛ // no3 ابدأ} // في إذا في الحلقة أعلاه ، يكون الرأس. بعد الانقلاب ، يتم تعيين P لرأس الرأس = P ؛ قائمة العرض () ؛ } رابط الفئة <T> {// Link Node T Data ؛ // رابط مجال البيانات <T> التالي ؛ // مؤشر متتالي ، رابط مجال سلسلة العقدة (T Data) {this.data = data ؛ } void displaylink () {system.out.println ("البيانات هي" + data.toString ()) ؛ }} public static void main (string [] args) {twoendPointList <integer> list = new ToinPointList <integer> () ؛ list.insertlast (1) ؛ list.insertfirst (2) ؛ list.insertlast (3) ؛ list.insertfirst (4) ؛ list.insertlast (5) ؛ list.displaylist () ؛ list.deletehead () ؛ list.displaylist () ؛ system.out.println ("find:" + list.find (6)) ؛ System.out.println ("Find:" + list.find (3)) ؛ System.out.println ("delete find:" + list.delete (6)) ؛ System.out.println ("DELETE Find:" + list.delete (5)) ؛ list.displaylist () ؛ System.out.println ("--- عكس ----") ؛ list.displayListerSe () ؛ }}مطبعة
قائمة (Head-> أخيرًا): البيانات 4 البيانات هي 2 البيانات هي 1 البيانات هي 3 البيانات هي 5 قائمة (الرأس-> الأخير): البيانات 2 البيانات 1 البيانات هي 3 البيانات هي 5 العثور
استخدم القوائم المرتبطة لتنفيذ المكدس ، واستخدم القائمة المرتبطة المفردة قبل إدخالها.
يستخدم هذا الفئة قائمة مرتبطة مزدوجة النتيجة للتنفيذ:
Class Public Class LinkStack <T> {Private ToinPointList <T> بيانات ؛ Public LinkStack () {dataS = new ToinPointList <T> () ؛ } // وضعت في مكدس Public Void Push (t data) {datas.insertfirst (data) ؛ } // وضع المكدس العام t pop () {return datas.deletehead () ؛ } // تحقق من الجزء العلوي من المكدس العام t peek () {return datas.peekhead () ؛ } // ما إذا كان المكدس فارغًا منطقيًا isEmpty () {return datas.isempty () ؛ } main static void main (string [] args) {linkstack <integer> stack = new linkstack <integer> () ؛ لـ (int i = 0 ؛ i <5 ؛ i ++) {stack.push (i) ؛ } لـ (int i = 0 ؛ i <5 ؛ i ++) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ } لـ (int i = 0 ؛ i <6 ؛ i ++) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ } system.out.println ("----") ؛ لـ (int i = 5 ؛ i> 0 ؛ i--) {stack.push (i) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer peek = stack.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {Integer pop = stack.pop () ؛ System.out.println ("pop:" + pop) ؛ }}}مطبعة
نظرة خاطفة: 4 نظرة خاطفة: 4 نظرة خاطفة: 4 نظرة خاطفة: 4 نظرة خاطفة: 4 نظرة خاطفة: 4 pop: 4 pop: 3 pop: 2 pop: 1 pop: 1 pop: 0 pop :- null --- نظرة خاطفة: 1 نظرة خاطفة: 1 نظرة خاطفة: 1 نظرة خاطفة: 1 pop: 1 pop: 1 pop: 2 pop: 4 pop: 5 pop: 5
يتم تنفيذ قائمة انتظار تطبيق القائمة المرتبطة باستخدام قائمة مرتبطة مزدوجة:
Class Public Class Linkqueue <T> {private toflepointlist <T> list ؛ public linkqueue () {list = new tovenpointList <T> () ؛ } // أدخل ذيل قائمة انتظار الفراغ العام (t data) {list.insertlast (data) ؛ } // قم بإزالة رأس الفريق العام t remove () {return list.deletehead () ؛ } // عرض رئيس الفريق العام t peek () {return list.peekhead () ؛ } boolean public isempty () {return list.isempty () ؛ } public static void main (string [] args) {linkqueue <integer> queue = new linkqueue <integer> () ؛ لـ (int i = 1 ؛ i <5 ؛ i ++) {queue.insert (i) ؛ } لـ (int i = 1 ؛ i <5 ؛ i ++) {integer peek = queue.peek () ؛ System.out.println ("PEEK:" + PEEK) ؛ } لـ (int i = 1 ؛ i <5 ؛ i ++) {integer remove = queue.remove () ؛ System.out.println ("إزالة:" + إزالة) ؛ } system.out.println ("----") ؛ لـ (int i = 5 ؛ i> 0 ؛ i--) {queue.insert (i) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer peek = queue.peek () ؛ System.out.println ("PEEK2:" + PEEK) ؛ } لـ (int i = 5 ؛ i> 0 ؛ i--) {integer remove = queue.remove () ؛ System.out.println ("إزالة:" + إزالة) ؛ }}}مطبعة
نظرة خاطفة: 1 نظرة خاطفة: 1 نظرة خاطفة: 1 نظرة خاطفة: 1 نظرة خاطفة: 1 إزالة: 1 إزالة: 2 إزالة: 3 إزالة: 4 --- PEEK2: 5 PEEK2: 5 PEEK2: 5 PEEK2: 5 PEEK2: 5 إزالة: 5 إزالة: 4 إزالة: 3 إزالة: 2 الإزالة: 1