Sidebar
dsa:list
3.2. The List ADT
รูปแบบทั่วไปของ list คือ $a_1, a_2, a_3, ... , a_n$ และกล่าวว่ามันมีขนาดเป็น $n$ และเรียก list ที่มีขนาดเป็น 0 ว่า empty list สำหรับ list ใด ๆ ยกเว้น empty list, ค่า $a_{i+1}$ อยู่ตามหลังค่า $a_i\ (i < n)$ และมี $a_{i-1}$ อยู่หน้า $a_i\ (i > 1)$ สมาชิกตัวแรกของ list คือ $a_1$, และตัวสุดท้ายคือ $a_n$ เราจะไม่กำหนดนิยามของตัวที่อยู่หน้า $a_1$ หรือหลัง $a_n$ ตำแหน่งของ $a_i$ ใน list คือ $i$ เพื่อให้ง่ายแก่การอธิบายเราจะกำหนดให้สมาชิกของ list เป็นเลขจำนวนเต็ม แต่ในทางปฏิบัติมันอาจจะเป็นสมาชิกอย่างอื่นที่ซับซ้อนได้
เซตของ Operations ของ list ADT ที่มักจะมีอยู่เสมอประกอบด้วย printList เพื่อใช้ในการดึงและแสดงค่าสมาชิกของ list ทั้งหมด และ makeEmpty เพื่อลบสมาชิกใน list คือทำให้เป็น list ว่าง
การทำงาน find ให้ค่าเป็นตำแหน่งแรกที่สมาชิกตัวแรกของ list ที่มีค่าที่ต้องการปรากฏอยู่
การทำงาน insert และ remove จะเป็นการบรรจุและลบสมาชิกในบางตำแหน่งของ list และการทำงาน findKth เป็นการหาค่าของสมาชิกที่อยู่ที่ตำแหน่งที่ระบุ
ดังเช่นรายการใน list ประกอบด้วย 35, 12, 52, 16, 12, ดังนั้น find(52) อาจจะเป็นการให้ค่าเป็น 3 ฟังก์ชัน insert(10, 3) อาจจะเป็นการบรรจุค่า 10 ลงในหลังตำแหน่งที่ 3 ซึ่งทำให้ list เป็น 35, 12, 52, 10, 16, 12 และ remove(52) ลบรายการค่า 52 ออกทำให้ list เป็น 35, 12, 10, 16, 12
ความหมายของฟังก์ชันต่าง ๆ อาจจะแตกต่างกันไปได้แล้วแต่ผู้เขียนโปรแกรมจะกำหนดนิยามตามต้องการ นอกจากนี้เรายังได้กำหนดนิยามของฟังก์ชัน next และ previous ซึ่งมีหมายเลขตำแหน่งของสมาชิกเป็น argument และค่าที่ส่งกลับเป็นหมายเลขหลังและก่อนตามลำดับ
3.2.1. การใช้อะเรย์ในการใช้งาน Lists
การดำเนินการต่าง ๆ ที่ได้กล่าวมาข้างบนนี้สามารถทำได้ด้วยการใช้อะเรย์ เพียงแต่จะต้องกำหนดขนาดของอะเรย์ที่คาดว่าจะต้องใช้เอาไว้ก่อนล่วงหน้าซึ่งมักจะมากกว่าจำนวนที่ใช้งานจริงทำให้เสียพื้นที่ใช้งาน การต้องทำเช่นนี้อาจเป็นข้อจำกัดอย่างมากโดยเฉพาะอย่างยิ่งในกรณีที่มีการใช้ list จำนวนมาก ๆ ที่เราไม่สามารถรู้ขนาดที่แน่นอนล่วงหน้า
การใช้อะเรย์ในการทำงาน printList และ find ใช้ linear time และ findKth ใช้ constant time อย่างไรก็ตาม insertion และ deletion เสียค่าใช้จ่ายมาก เช่น การบรรจุค่าลงในตำแหน่ง 0 (เป็นการทำให้เกิดสมาชิกตัวแรกใหม่) ต้องทำการเลื่อนสมาชิกของอะเรย์ทั้งหมดลงไปหนึ่งตำแหน่งเพื่อให้เกิดที่ว่าง ขณะที่การทำงานการลบ (deleting) สมาชิกตัวแรกออกต้องทำการเลื่อนสมาชิกทุกตัวขึ้นมาหนึ่งตำแหน่ง ดังนั้น worst case ของการทำงาน insertion และ deletion จึงเป็น $O(n)$ การสร้าง list โดยการบรรจุสมาชิก n ตัวตามลำดับต้องใช้เวลาการทำงานเป็น quadratic time เนื่องจากการบรรจุและการลบทำงานได้ช้าและเราต้องรู้ขนาดของอะเรย์ก่อนล่วงหน้า ดังนั้นจึงไม่นิยมใช้อะเรย์ในการใช้งาน lists
3.2.2. Linked Lists
Linked list ประกอบด้วยลำดับของโนด (nodes) ซึ่งไม่จำเป็นต้องอยู่ในหน่วยความจำที่มีตำแหน่งที่ต่อเนื่องกัน แต่ละโนดประกอบด้วยสมาชิก (ค่า) และ link ที่ต่อเชื่อมไปยังโนดที่อยู่หลังมัน (เราใช้ชื่อ next เรียก link ดังกล่าวนี้) โนดสุดท้ายมี next link เชื่อมต่อกับ null รูปที่ 3.1 แสดงภาพทั่วไปของ linked list
ในการทำงาน printList และ find(x) จะเริ่มต้นด้วยโนดแรกของลิสต์แล้วท่องไปในลิสต์ด้วยตัวเชื่อม next การทำงานนี้ใช้เวลาเป็น linear time การทำงาน findKth(i) ใช้เวลาเป็น $O(i)$ ซึ่งทำงานโดยท่องไปในลิสต์
การทำงาน remove ทำงานด้วยการเปลี่ยนการอ้างอิงของ next เท่านั้น รูปที่ 3.2 แสดงผลการทำงาน delete สมาชิกตัวที่ 3 ของลิสต์
การทำงาน insert ต้องใช้การทำงานของตัวดำเนินการ new เพื่อสร้างโนดใหม่และการปรับเปลี่ยนตัวอ้างอิง 2 ครั้ง รูปที่ 3.3 แสดงผลการทำงานโดยเส้นประแสดงการอ้างอิงของ next ตำแหน่งเดิมก่อนเปลี่ยนแปรง
รูปที่ 3.1 แสดงภาพทั่วไปของ linked list
รูปที่ 3.2 แสดงผลการทำงาน delete
รูปที่ 3.3 แสดงผลการทำงาน insert
3.2.3 การเขียนโปรแกรม
ยังมีประเด็นของ linked list ที่ต้องกล่าวเพิ่มเติมจากที่ได้กล่าวมาแล้ว
ประการแรก คือยังไม่มีความชัดเจนว่าจะบรรจุโนดใหม่เข้าที่ตำแหน่งแรกของ list อย่างไร
ประการที่สอง การลบที่ทำกับโนดที่เป็นหัว list เป็นกรณีพิเศษ เนื่องจากมีการเปลี่ยนจุดเริ่มต้นของ list ดังนั้นจึงต้องระมัดระวังเพราะอาจจะทำให้ list หายไปได้
ประการที่สาม เกี่ยวข้องกับอัลกอริทึมของการลบซึ่งจะต้องจัดการกับโนดที่อยู่หน้าโนดที่ต้องการจะลบด้วย
เราจะจัดการประเด็นทั้งสามที่กล่าวข้างบนนี้ด้วยการใช้ sentinel node ซึ่งบางครั้งจะเรียกว่า header node หรือ dummy node โดยเราจะจัดให้ header node อยู่ที่ตำแหน่ง 0 (ศูนย์) รูปที่ 3.4 แสดง linked list $A_1,A_2,⋯,A_5$ ที่ใช้ header และรูปที่ 3.5 แสดง linked list ว่าง
รูปที่ 3.4 linked list ที่ใช้ header
รูปที่ 3.5 linked list ว่าง
เพื่อแก้ปัญหาการลบ เราต้องเขียนฟังก์ชัน findPrevious ซึ่งจะให้ค่ากลับเป็นตำแหน่งของโนดที่อยู่หน้าโนดที่เราต้องการจะลบ ในกรณีเช่นนี้ ถ้าเราต้องการลบสมาชิกที่เป็นโนดตัวแรกของลิสต์ ฟังก์ชัน findPrevious ก็จะให้ค่ากลับเป็นตำแหน่ง header เราจะใช้คลาส 3 คลาสสำหรับ list ADT คลาสแรกเป็นตัวลิสต์เอง คือ คลาส LinkedList คลาสที่สองคือคลาส ListNode ซึ่งเป็นคลาสสำหรับตัวโนด และ คลาสสุดท้ายคือ LinkedListItr เพื่อเป็นตัวระบุตำแหน่งในลิสต์ และถ้าคลาสทั้งสามรวมอยู่ใน package เดียวกันก็จะทำให้คลาสทั้งสามนี้เข้าถึงรายละเอียดภายในแต่ละคลาสได้
package DataStructures; class ListNode { ListNode( Object theElement ) // Constructors { this( theElement, null ); } ListNode( Object theElement, ListNode n ) { element = theElement; next = n; } Object element; ListNode next; }
รูปที่ 3.6 แสดงคลาส ListNode
รูปที่ 3.6 แสดงคลาส ListNode ประกอบด้วยฟิลด์ 2 ฟิลด์สำหรับค่าของสมาชิกและตัวเชื่อมต่อไปยังโนดถัดไป จะเห็นว่าคลาสนี้ไม่ได้รับการออกแบบให้เป็น public แต่ก็สามารถมองเห็นได้จากคลาสอื่น ๆ ใน package เดียวกันคือจากภายใน package DataStructures
package DataStructures; public class LinkedListItr { LinkedListItr( ListNode theNode ) { current = theNode; } public boolean isPastEnd( ) { return current == null; } public Object retrieve( ) { return isPastEnd( ) ? null : current.element; } public void advance( ) { if( !isPastEnd( ) ) current = current.next; } ListNode current; // Current position }
รูปที่ 3.7 คลาส LinkedListItr
รูปที่ 3.7 แสดงคลาส LinkedListItr เป็นคลาสที่ใช้เพื่อการระบุตำแหน่ง คลาสที่ใช้ทำงานในลักษณะดังกล่าวนี้รู้จักกันในนามของ iterator class เนื่องจากมันทำให้สามารถเคลื่อนไปยังตำแหน่งต่าง ๆ ซ้ำแล้วซ้ำอีกภายในโครงสร้างข้อมูลได้ LinkedListItr จะมีตัวจัดเก็บตำแหน่งอ้างอิงที่ชี้ไปยัง ListNode ซึ่งเป็นค่าของตำแหน่งปัจจุบันของ iterator ฟังก์ชัน isPastEnd ให้ค่าเป็น true ถ้าตำแหน่งที่ระบุนั้นอยู่เลยจากโนดสุดท้ายของลิสต์ซึ่งเป็นการทำงานการทดสอบว่าตำแหน่งขณะนั้นได้ผ่านท้าย list แล้วหรือไม่ ฟังก์ชัน retrieve ให้ค่ากลับเป็นหน่วยข้อมูลของสมาชิกที่เก็บอยู่ ณ ตำแหน่งนั้น และฟังก์ชัน advance จะเลื่อนตำแหน่งจากที่อยู่ปัจจุบันไปยังโนดถัดไปของ list ถ้าตำแหน่งปัจจุบันเป็น null ก็จะไม่มีการทำงานใด ๆ เกิดขึ้น
package DataStructures; public class LinkedList { public LinkedList( ) { header = new ListNode( null );} public boolean isEmpty( ) { return header.next == null;} public void makeEmpty( ) { header.next = null; } public LinkedListItr zeroth( ) { return new LinkedListItr( header );} public LinkedListItr first( ) { return new LinkedListItr( header.next ); } public void insert( Object x, LinkedListItr p ) { /* Figure 3.13 */ } public LinkedListItr find( Object x ) { /* Figure 3.10 */ } public LinkedListItr findPrevious( Object x ) { /* Figure 3.12 */ } public void remove( Object x ) { /* Figure 3.11 */ } public static void printList( LinkedList theList ) { /* Figure 3.9 */ } private ListNode header; }
รูปที่ 3.8 เค้าโครงของคลาส LinkedList
รูปที่ 3.8 แสดงเค้าโครงของคลาส LinkedList โดยที่บาง methods แสดงไว้ในรูปอื่น ๆ ถัดไป คลาส LinkedListประกอบด้วยฟิลด์เพียงฟิลด์เดียวที่ใช้สำหรับอ้างถึงโนดที่เป็น header ที่ได้รับการ allocated ด้วย constructor ฟังก์ชัน zeroth และ first ให้ค่ากลับเป็น iterator ของตำแหน่ง header และของสมาชิกตัวแรกตามลำดับ ส่วนฟังก์ชันอื่น ๆ จะเป็นการสืบค้นหรือปรับเปลี่ยนค่าสมาชิก
// Simple print method public static void printList( LinkedList theList ) { if( theList.isEmpty( ) ) System.out.print( "Empty list" ); else { LinkedListItr itr = theList.first( ); for( ; !itr.isPastEnd( ); itr.advance( ) ) System.out.print( itr.retrieve( ) + " " ); } System.out.println( ); }
รูปที่ 3.9 ฟังก์ชัน printList
รูปที่ 3.9 แสดงฟังก์ชัน printList เพื่อแสดงให้เห็นการทำงานระหว่างฟังก์ชัน LinkedList และฟังก์ชัน LinkedListItr โดยฟังก์ชัน printList จะทำการแสดงค่าข้อมูลของลิสต์
การใช้ iterator ช่วยให้เราสามารถเข้าถึงลิสต์พร้อม ๆ กันได้หลาย ๆ ตำแหน่งในเวลาเดียวกันซึ่งเป็นประโยชน์กับการดำเนินการบางอย่าง เช่น การ remove สมาชิกของลิสต์เป็นช่วงย่อย ๆ โดยใช้ iterator กำกับที่ต้นทางและอีกตัวที่ปลายทางของลิสต์ย่อยที่ต้องลบออก ฟังก์ชัน find (ดูรูปที่ 3.10) ให้ค่ากลับเป็นตำแหน่งในลิสต์ บรรทัดที่ 2 ใช้ประโยชน์จาก short-circuited ของตัวดำเนินการ && ซึ่งถ้านิพจน์หน้า && เป็น false ก็จะไม่มีการทำงานของนิพจน์หลัง && ทั้งนี้เนื่องจากในกรณีแบบนี้นิพจน์ทั้งหมดก็จะเป็น false อยู่แล้วนั่นเอง
/** * Return iterator corresponding to the first node containing an item. * @param x the item to search for. * @return an iterator; iterator isPastEnd if item is not found. */ public LinkedListItr find( Object x ) { /* 1*/ ListNode itr = header.next; /* 2*/ while ( itr != null && !itr.element.equals( x ) ) /* 3*/ itr = itr.next; /* 4*/ return new LinkedListItr( itr ); }
รูปที่ 3.10 ฟังก์ชัน find
/** * Remove the first occurrence of an item. * @param x the item to remove. */ public void remove( Object x ) { LinkedListItr p = findPrevious( x ); if( p.current.next != null ) p.current.next = p.current.next.next; // Bypass deleted node }
รูปที่ 3.11 ฟังก์ชัน remove
รูปที่ 3.11 แสดงฟังก์ชัน remove ซึ่งจะทำการลบสมาชิกที่มีค่า x ออกจากลิสต์ และจะลบเฉพาะค่าแรกเท่านั้นในกรณีที่มีค่า x มากกว่าหนึ่งค่าและจะไม่ทำสิ่งใดกรณีที่ไม่พบค่า x โปรแกรมจะทำการหาค่า p ซึ่งเป็นค่าที่อยู่หน้าตำแหน่งของค่า x โดยเรียกใช้ฟังก์ชัน findprevious ซึ่งแสดงอยู่ในรูปที่ 3.12
ฟังก์ชันสุดท้ายที่จะกล่าวถึง แสดงในรูปที่ 3.13 คือฟังก์ชัน insert ซึ่งใช้เพื่อการบรรจุค่าใหม่ลงในลิสต์ ฟังก์ชันต้องการพารามิเตอร์ 2 ตัวคือค่าที่จะบรรจุและตำแหน่ง p ที่เป็นตำแหน่งค่าใหม่จะถูกบรรจุลงไปต่อจากมัน (สิ่งนี้ขึ้นอยู่กับการตัดสินใจของผู้เขียนโปรแกรมเองว่าจะให้ค่าใหม่ที่บรรจุจะไปอยู่ในตำแหน่งหน้าหรือหลังหรือแทนที่ตำแหน่ง p) กล่าวสำหรับฟังก์ชัน find และ findprevious แล้ว ในกรณี worst case ก็จะมี running time เป็น $O(n)$ เนื่องจากจำเป็นจะต้องท่องไปในลิสต์ทั้งลิสต์ถ้าหากว่าสมาชิกที่ต้องการนั้น ๆ ไม่มีอยู่ในลิสต์หรืออยู่ในตำแหน่งสุดท้ายของลิสต์ และโดยเฉลี่ย running time ก็เป็น $O(n)$
เนื่องจากโดยเฉลี่ยก็ต้องการการท่องไปเป็นระยะครึ่งหนึ่งของลิสต์ส่วนการทำงานฟังก์ชันอื่น ๆ ใช้เวลาเป็น $O(1)$ รูปที่ 3.14 เป็นฟังก์ชัน main เพื่อทดสอบฟังก์ชันต่างๆ ที่กล่าวมา (อาจต้องทำการแก้ไขบ้าง เช่นชนิดข้อมูล)
/** * Return iterator prior to the first node containing an item. * @param x the item to search for. * @return appropriate iterator if the item is found. Otherwise, the * iterator corresponding to the last element in the list is returned. */ public LinkedListItr findPrevious( Object x ) { /* 1*/ ListNode itr = header; /* 2*/ while( itr.next != null && !itr.next.element.equals( x ) ) /* 3*/ itr = itr.next; /* 4*/ return new LinkedListItr( itr ); }
รูปที่ 3.12 ฟังก์ชัน findPrevious
/* Insert after p. * @param x the item to insert. * @param p the position prior to the newly inserted item. */ public void insert( Object x, LinkedListItr p ) { if( p != null && p.current != null ) p.current.next = new ListNode( x, p.current.next ); }
รูปที่ 3.13 ฟังก์ชัน insert
public static void main( String [ ] args ) { LinkedList theList = new LinkedList( ); LinkedListItr theItr; int i; theItr = theList.zeroth( ); printList( theList ); for( i = 0; i < 10; i++ ) { theList.insert( new MyInteger( i ), theItr ); printList( theList ); theItr.advance( ); } for ( i = 0; i < 10; i += 2 ) theList.remove( new MyInteger( i ) ); for ( i = 0; i < 10; i++ ) if ( ( i % 2 == 0 ) != ( theList.find( new MyInteger( i ) ).isPastEnd( ) ) ) System.out.println( "Find fails!" ); System.out.println( "Finished deletions" ); printList( theList ); }
รูปที่ 3.14 ฟังก์ชัน main
3.2.4. Doubly Linked Lists
ในบางกรณีเราจำเป็นต้องให้สามารถท่องไปใน lists แบบย้อนกลับได้ซึ่งลิสต์มาตรฐานที่กล่าวมาแล้วไม่สามารถทำได้ อย่างไรก็ตามเราสามารถทำได้ด้วยการเพิ่มเติม field พิเศษเพื่อเก็บตัว link ที่ชี้ไปยังโนดก่อนหน้า ค่าใช้จ่าย (Cost) ที่เพิ่มขึ้นจากการเพิ่ม link ตัวนี้คือต้องใช้เนื้อที่เพิ่มขึ้น และ ต้องใช้เวลาเพิ่มขึ้นจากเดิมสองเท่าในการ insert และ delete เนื่องจากต้องใช้เวลาในการจัดการกับตัวเชื่อมเพิ่มขึ้น แต่ในอีกด้านหนึ่ง มันทำให้การ delete ง่ายขึ้นเนื่องจากไม่ต้องใช้การอ้างถึงโนดที่อยู่ก่อนหน้ามัน รูปที่ 3.15 แสดงรูป doubly linked list
รูปที่ 3.15 doubly linked list
3.2.5. Circularly Linked Lists
รูปแบบที่ใช้ทั่วไปอีกรูปแบบหนึ่งของลิสต์ คือการให้โนดสุดท้ายมีตัวเชื่อมที่เชื่อมไปยังโนดแรก การทำแบบนี้สามารถใช้โดยให้มีหรือไม่มี header ก็ได้ และสามารถทำได้กับ doubly linked list ได้ รูปแบบที่ใช้การเชื่อมต่อแบบนี้เรียกว่า circular linked list รูปที่ 3.16 แสดงรูป circular linked list ที่ไม่ใช้ header
รูปที่ 3.16 circular linked list ที่ไม่ใช้ header
3.2.6. ตัวอย่างการใช้ linked list
ต่อไปจะกล่าวถึงตัวอย่างการใช้งาน linked list 2 ตัวอย่าง คือ ตัวอย่างแรกเป็นการใช้จำลองการใช้ single variable polynomials ตัวอย่างที่สองเป็นตัวอย่างการใช้เพื่อการจัดการการลงทะเบียนเรียนในสถานศึกษา
Polynomial ADT
เราสามารถกำหนดนิยามของ abstract data type สำหรับ single-variable polynomials (กำลังเป็นบวก) ได้โดยใช้ list ให้ $f(x)=∑_{i=0}^n a_i x^i$ กรณีที่สัมประสิทธิ์ $a_i$ ทั้งหมดไม่เป็นศูนย์ เราอาจใช้อะเรย์เพื่อเก็บค่าสัมประสิทธิ์ จากนั้นจะเป็นการเขียนฟังก์ชันการบวก ลบ คูณ หรืออื่น ๆ สำหรับ polynomial เหล่านี้
รูปที่ 3.17 เป็นรูปแบบหนึ่งของการประกาศ polynomial ADT รูปที่ 3.18 – 3.20 เป็นฟังก์ชันเพิ่มเติมอื่น running time ของฟังก์ชันที่ใช้ในการคูณจะขึ้นอยู่กับผลคูณของดีกรีของ polynomial ทั้งสอง
การใช้งานในลักษณะนี้เหมาะสำหรับ polynomial ที่เป็นแบบ dense polynomial กล่าวคือเป็น polynomial ที่ประกอบด้วยเทอมครบหรือเกือบครบทุกเทอม แต่ถ้ากรณีที่ $P_1 (x)=10x^{1000}+5x^{14}+1$ และ $P_2 (x)=3x^{1990}+2x^{1492}+11x+5$ การใช้อะเรย์ทำให้ running time เป็นสิ่งที่ยอมรับไม่ได้
เนื่องจากเวลาเกือบทั้งหมดสิ้นเปลืองไปกับการทำงานกับค่าศูนย์ซึ่งไม่ได้มีอยู่ใน polynomials ทางเลือกที่ดีกว่า คือการใช้ singly linked list แต่ละเทอมของ polynomial บรรจุอยู่ในโนดหนึ่ง และจัดเรียงโนดจากค่ามากไปหาน้อยตามค่ายกกำลัง ดังแสดงในรูปที่ 3.21 และรูปที่ 3.22 แสดงโครงร่างของคลาส polynomial ADT
public class Polynomial { public static final int MAX_DEGREE = 100; public static int max( int a, int b ){ return a > b ? a : b; } public Polynomial( ) { zeroPolynomial( ); } public void zeroPolynomial( ) { /* Figure 3.17 */ } public Polynomial add( Polynomial rhs ) { /* Figure 3.18 */ } public Polynomial multiply( Polynomial rhs ) throws Overflow { /* Figure 3.19 */ } public void print( ) { for( int i = highPower; i > 0; i-- ) System.out.print( coeffArray[ i ] + "x^" + i + " + " ); System.out.println( coeffArray[ 0 ] ); } private int coeffArray[ ] = new int [ MAX_DEGREE + 1 ]; private int highPower = 0; }
รูปที่ 3.17 การประกาศ polynomial ADT
public void zeroPolynomial( ) { for ( int i = 0; i <= MAX_DEGREE; i++ ) coeffArray[ i ] = 0; highPower = 0; }
รูปที่ 3.18 Method สำหรับ initialize ให้ polynomial เป็นศูนย์
public Polynomial add( Polynomial rhs ) { Polynomial sum = new Polynomial( ); sum.highPower = max( highPower, rhs.highPower ); for ( int i = sum.highPower; i >= 0; i-- ) sum.coeffArray[ i ] = coeffArray[ i ] + rhs.coeffArray[ i ]; return sum; }
รูปที่ 3.19 Method สำหรับการบวก polynomials 2 ตัว
public Polynomial multiply( Polynomial rhs ) throws Overflow { Polynomial product = new Polynomial( ); product.highPower = highPower + rhs.highPower; if ( product.highPower > MAX_DEGREE ) throw new Overflow( ); for ( int i = 0; i <= highPower; i++ ) for ( int j = 0; j <= rhs.highPower; j++ ) product.coeffArray[ i + j ] += coeffArray[ i ] * rhs.coeffArray[ j ]; return product; }
รูปที่ 3.20 Method สำหรับการคูณ polynomials 2 ตัว
รูปที่ 3.21 polynomials 2 ตัว ที่ใช้ linked list
public class Literal { // Various constructors… int coefficient; int exponent; } public class Polynomial { public Polynomial( ) { /* Exercise */ } public void insertTerm( int coef, int exp ) { /* Exercise */ } public void zeroPolynomial( ) { /* Exercise */ } public Polynomial add( Polynomial rhs ) { /* Exercise */ } public Polynomial multiply( Polynomial rhs ) { /* Exercise */ } public void print( ) { /* Exercise */ } private List terms; }
รูปที่ 3.22 โครงร่างของคลาส polynomials ADT ที่ใช้ linked list
Multilists
ตัวอย่างการใช้ linked lists นี้ซับซ้อนขึ้นกว่าตัวอย่างที่ได้กล่าวมาแล้ว
ถ้าในสถาบันการศึกษาประกอบด้วยนักศึกษาจำนวน 40,000 คน และมีวิชาที่เปิดให้มีการเรียน 2,500 วิชา และต้องการทำรายงาน 2 แบบ คือ แบบแรกเป็นรายการนักศึกษาที่ลงเรียนแต่ละวิชา และอีกรายงานเป็นรายการวิชาที่นักศึกษาแต่ละคนลงเรียน
การแก้ปัญหานี้สามารถทำได้อย่างตรงไปตรงมา คือการใช้อะเรย์ 2 มิติ ซึ่งต้องใช้อะเรย์ขนาด 100 ล้านเซลล์ ถ้าโดยเฉลี่ยแล้วนักศึกษาแต่ละคนลงเรียน 3 วิชา นั่นหมายความว่าจะมีการใช้จำนวนเซลล์เพียง 120,000 เซลล์ หรือคิดเป็นเพียง 0.1 เปอร์เซ็นต์ เท่านั้น
เราสามารถทำได้ดีกว่านี้ด้วยการใช้ลิสต์ที่เป็นลิสต์ของรายการแต่ละวิชาที่มีนักศึกษามาลงเรียนและลิสต์ของรายการนักศึกษาแต่ละคนที่ได้ไปลงทะเบียนเรียนวิชาต่าง ๆ รูปที่ 3.26 แสดงลิสต์แบบ multilist ที่ใช้ จากรูปจะเห็นว่าเป็นการรวมลิสต์ของรายการทั้งสองที่กล่าวข้างบนนี้เข้าด้วยกันเป็นลิสต์เดียวในรูปแบบที่เรียกว่า multilist และทุกลิสต์จะมีการใช้ header และเป็นแบบ circular การแสดงรายการของนักศึกษาทั้งหมดที่เรียนวิชา C3 ก็สามารถทำได้ด้วยการท่องไปในลิสต์โดยเริ่มต้นที่ C3 แล้วท่องไปในลิสต์ทางด้านขวาซึ่งเซลล์แรกเป็นของนักศึกษา S1 และเราทราบได้ว่าเป็นนักศึกษา S1 ด้วยการท่องไปตามตัวเชื่อมของลิสต์นักศึกษาจนกระทั่งถึงตัว header ของ S1 ก็จะทำให้รู้ได้ว่าเป็นของนักศึกษา S1 จากนั้นก็จะกลับไปยังลิสต์ของ C3 (เราต้องจัดเก็บตำแหน่งนี้เอาไว้ก่อนที่จะท่องไปในลิสต์ของ S1) และเคลื่อนไปทางขวาจะพบเซลล์ถัดไปซึ่งด้วยวิธีการเดียวกับที่ได้กล่าวมาแล้วเราก็จะรู้ว่าเป็นของนักศึกษา S3 เราสามารถทำแบบเดียวกับที่กล่าวมานี้ก็จะพบกับ S4 และ S5 ที่เรียนวิชา C3 นี้ และด้วยวิธีการเดียวกับที่กล่าวมาแล้วเราก็สามารถหาคำตอบได้ว่านักศึกษาแต่ละคนนั้นลงเรียนวิชาอะไรบ้าง
รูปที่ 3.26 ลิสต์แบบ multilist ที่ใช้ในปัญหาการลงทะเบียนเรียนวิชาต่าง ๆ
3.2.7. Cursor Implementation of Linked Lists
ตัวอย่างในหัวข้อนี้จะเป็นการจำลองการใช้งาน linked list โดยไม่ใช้ linked structure
วิธีการที่จะกล่าวถึงนี้เรียกว่า cursor implementation โดยกำหนดให้มีคุณสมบัติสำคัญ 2 ประการ คือ
- ข้อมูลได้รับการจัดเก็บภายในแหล่งเก็บโนด (collection of nodes) โดยแต่ละโนดประกอบด้วย data และ link ที่เชื่อมต่อไปยังโนดถัดไป
- สามารถสร้างโนดใหม่ขึ้นในหน่วยความจำของระบบด้วยการเรียกใช้ new และหน่วยความจำนั้นจะถูกเรียกคืนเมื่อไม่ถูกอ้างถึงอีกต่อไป
cursor ของเราจะต้องสามารถทำงานเรียนแบบการทำงานทั้งสองที่กล่าวข้างบนนั้น สำหรับเงื่อนไขข้อแรกทำได้ด้วยการใช้อะเรย์ของโนดที่เป็นแบบ static แต่ละเซลล์ในอะเรย์มีหมายเลขดัชนีเป็นตัวอ้างอิงโนด รูปที่ 3.27 แสดงการประกาศคลาส node และ iterator ในการใช้งาน
รูปที่ 3.28 แสดงโครงสร้างของคลาส CursorList ซึ่งมีอะเรย์ของโนดได้รับการจัดเก็บในอะเรย์ cursorSpace เพื่อจำลองการทำงานในเงื่อนไขข้อที่สอง เราจะใช้การทำงานที่เหมือนกับการทำงานของ new ที่ทำกับเซลล์ในอะเรย์ cursorSpace ซึ่งเราจะเรียกฟังก์ชันนี้ว่า alloc โดยเราจะเก็บเซลล์ที่ไม่ถูกใช้เป็นส่วนของลิสต์ใด ๆ เอาไว้ใน freelist และมีเซลล์ 0 เป็น header ของ freelist สถานะภาพเริ่มต้นแสดงในรูปที่ รูปที่ 3.29 ค่า 0 สำหรับ next นั้นก็เป็นเสมือน null reference การกำหนดสถานะเริ่มต้น (initialization) ของ cursorSpace ใช้การทำงานในลูปตามปกติและทำโดยใช้ static initializer ซึ่งจะถูกเรียกใช้งานเพียงหนึ่งครั้งเมื่อมีการอ้างถึงคลาสในครั้งแรก และอะเรย์ที่ได้จะถูกนำมาใช้งานร่วมกันโดย instance ทั้งหมดของ CursorList การทำงานของ alloc() เป็นการจำลองการทำงานของ new และ alloc() จะทำการลบ element แรกที่ต่อจาก header ออกจาก freelist และฟังก์ชัน free() จะเป็นผู้เรียกคืนโนดที่ไม่ใช้กลับคืนไปยังหัว freelist รูปที่ 3.30 แสดงฟังก์ชัน alloc และ free
class CursorNode { // Constructors CursorNode( Object theElement ) { this( theElement, 0 ); } CursorNode( Object theElement, int n ) { element = theElement; next = n; } // Friendly data; accessible by other package routines Object element; int next; } public class CursorListItr { CursorListItr( int theNode ) { current = theNode; } public boolean isPastEnd( ) { return current == 0; } public Object retrieve( ) { return isPastEnd( ) ? null : CursorList.cursorSpace[ current ].element; } public void advance( ) { if( !isPastEnd( ) ) current = CursorList.cursorSpace[ current ].next; } int current; // Current position }
รูปที่ 3.27 การประกาศคลาส node และ iterator
public class CursorList { private static int alloc( ) { /* Figure 3.29 */ } private static void free( int p ) {/* Figure 3.29 */ } public CursorList( ) { header = alloc( ); cursorSpace[ header ].next = 0; } public boolean isEmpty( ){ return cursorSpace[ header ].next == 0; } public void makeEmpty( ) {/* Figure 3.34 */ } public CursorListItr zeroth( ) { return new CursorListItr( header );} public CursorListItr first( ) { return new CursorListItr( cursorSpace[ header ].next );} public void insert( Object x, CursorListItr p ) {/* Figure 3.32 */ } public CursorListItr find( Object x ) {/* Figure 3.31 */ } public CursorListItr findPrevious( Object x ) {/* Figure 3.31 */ } public void remove( Object x ) {/* Figure 3.33 */ } // Simple print method static public void printList( CursorList theList ) {/* Figure 3.34 */ } private int header; static CursorNode[ ] cursorSpace; private static final int SPACE_SIZE = 100; static { cursorSpace = new CursorNode[ SPACE_SIZE ]; for( int i = 0; i < SPACE_SIZE; i++ ) cursorSpace[ i ] = new CursorNode( null, i + 1 ); cursorSpace[ SPACE_SIZE - 1 ].next = 0; } }
รูปที่ 3.28 โครงสร้างของคลาส CursorList
| Slot | Element | Next |
|---|---|---|
| 0 | 1 | |
| 1 | 2 | |
| 2 | 3 | |
| 3 | 4 | |
| 4 | 5 | |
| 5 | 6 | |
| 6 | 7 | |
| 7 | 8 | |
| 8 | 9 | |
| 9 | 10 | |
| 10 | 0 |
รูปที่ 3.29 สถานะภาพเริ่มต้นของ cursorSpace
private static int alloc( ) { int p = cursorSpace[ 0 ].next; cursorSpace[ 0 ].next = cursorSpace[ p ].next; if ( p == 0 ) throw new OutOfMemoryError( ); return p; } private static void free( int p ) { cursorSpace[ p ].element = null; cursorSpace[ p ].next = cursorSpace[ 0 ].next; cursorSpace[ 0 ].next = p; }
รูปที่ 3.30 ฟังก์ชัน alloc และ free รูปที่ 3.31 เป็นตัวอย่างของสถานะของ cursor implementation ของ linked list สถานะหนึ่งที่มีค่า L = 5 และค่า M = 3 คือ L เป็นลิสต์ที่ header อยู่ที่เซลล์ 5 และมีสมาชิกเป็น a, b, e และ M เป็นลิสต์ที่ header อยู่ที่เซลล์ 3 และมีสมาชิกเป็น c, d, f ฟังก์ชันต่าง ๆ ที่จะใช้งาน cursor implementation ของ linked list จะต้องส่งผ่านพารามิเตอร์เหมือนกับการใช้ linked list ฟังก์ชัน find (ดูรูปที่ 3.32) ให้ค่ากลับเป็นตำแหน่งของ x ในลิสต์ รูปที่ 3.33 แสดงฟังก์ชัน insert รูปที่ 3.34 แสดงฟังก์ชัน delete ในฟังก์ชันนี้เราจะต้อง save หมายเลขดัชนีของโนดที่ต้องการลบเพื่อสามารถนำไปใช้ใหม่ได้ด้วยการเรียกใช้ฟังก์ชัน free รูปที่ 3.35 แสดงฟังก์ชัน makeEmpty และรูปที่ 3.36 ฟังก์ชัน main() เพื่อทดสอบการใช้งาน
| Slot | Element | Next |
|---|---|---|
| 0 | - | 6 |
| 1 | b | 9 |
| 2 | f | 0 |
| 3 | header | 7 |
| 4 | - | 0 |
| 5 | header | 10 |
| 6 | - | 4 |
| 7 | c | 8 |
| 8 | d | 2 |
| 9 | e | 0 |
| 10 | a | 1 |
รูปที่ 3.31 ตัวอย่างของสถานะหนึ่งของ cursor implementation ของ linked list
public CursorListItr find( Object x ) { /* 1*/ int itr = cursorSpace[ header ].next; /* 2*/ while( itr != 0 && !cursorSpace[ itr ].element.equals( x ) ) /* 3*/ itr = cursorSpace[ itr ].next; /* 4*/ return new CursorListItr( itr ); } public CursorListItr findPrevious( Object x ) { /* 1*/ int itr = header; /* 2*/ while( cursorSpace[ itr ].next != 0 && !cursorSpace[ cursorSpace[ itr ].next ].element.equals( x ) ) /* 3*/ itr = cursorSpace[ itr ].next; /* 4*/ return new CursorListItr( itr ); }
รูปที่ 3.32 ฟังก์ชัน find
/** * Insert after p. * @param x the item to insert. * @param p the position prior to the newly inserted item. */ public void insert( Object x, CursorListItr p ) { if( p != null && p.current != 0 ) { int pos = p.current; int tmp = alloc( ); cursorSpace[ tmp ].element = x; cursorSpace[ tmp ].next = cursorSpace[ pos ].next; cursorSpace[ pos ].next = tmp; } }
รูปที่ 3.33 ฟังก์ชัน insert
/** * Remove the first occurrence of an item. * @param x the item to remove. */ public void remove( Object x ) { CursorListItr p = findPrevious( x ); int pos = p.current; if( cursorSpace[ pos ].next != 0 ) { int tmp = cursorSpace[ pos ].next; cursorSpace[ pos ].next = cursorSpace[ tmp ].next; free( tmp ); } }
รูปที่ 3.34 ฟังก์ชัน delete
public void makeEmpty( ) { while( !isEmpty( ) ) remove( first( ).retrieve( ) ); } static public void printList( CursorList theList ) { if( theList.isEmpty( ) ) System.out.print( "Empty list" ); else { CursorListItr itr = theList.first( ); for( ; !itr.isPastEnd( ); itr.advance( ) ) System.out.print( itr.retrieve( ) + " " ); } System.out.println( ); }
รูปที่ 3.35 ฟังก์ชัน makeEmpty และ printList
public static void main( String [ ] args ) { CursorList theList = new CursorList( ); CursorListItr theItr; int i; theItr = theList.zeroth( ); printList( theList ); for( i = 0; i < 10; i++ ) { theList.insert( new MyInteger( i ), theItr ); printList( theList ); theItr.advance( ); } for( i = 0; i < 10; i += 2 ) theList.remove( new MyInteger( i ) ); for ( i = 0; i < 10; i++ ) if ( ( i % 2 == 0 ) != ( theList.find( new MyInteger( i ) ).isPastEnd( ) ) ) System.out.println( "Find fails!" ); System.out.println( "Finished deletions" ); printList( theList ); } }
รูปที่ 3.36 ฟังก์ชัน main() เพื่อทดสอบการใช้งาน
dsa/list.txt · Last modified: 2021/09/09 10:42 by wasu
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
