7/28/2009
DTS04/22/07/2552
Stack
-สแต็ก คือ ส่วนที่ใช้สำหรับอ่านและเขียนในหน่วยความจำ (RAM) และใช้สำหรับ CPU เท่านั้นในการนำข้อมูลเข้าไปเก็บ ซึ่งเป็นที่เก็บข้อมูลชั่วคร่าว เพราะว่าพื้นที่ที่ใช้สำหรับเก็บข้อมูลของ CPU (รีจีสเตอร์) มีใช้งานอย่างจำกัดในส่วนที่เป็นสแต็กเราจะมีรีจีสเตอร์ที่ใช้อยู่ 2 ตัวคือ SS(Stack Segment) และ SP(Stack Pointer) โดยที่ SS จะเป็นตัวกำหนดที่อยู่ของสแต็ก และมี SP เป็นตัวชี้ที่อยู่ของข้อมูลแต่ละตัว โดยจะมีคำสั่งที่ใช้สำหรับเขียนและอ่าน อยู่ 4 คำสั่ง คือคำสั่งที่ใช้สำหรับเขียน PUSH คำสั่งที่ใช้สำหรับอ่าน POP คำสั่งที่ใช้สำหรับเก็บสถานะของแฟล็ก PUSHF คำสั่งที่ใช้สำหรับอ่านสถานะของแฟล้ก POPFการเก็บข้อมูลลงในสแต็ก PUSHในการเก็บข้อมูลลงในสแต็กนั้น จะทำการลดค่าของ SP ลงครั้ง 2 ไบต์ในการเขียนแต่ละครั้ง เพราะว่าในการเขียนแต่ละครั้งจะทำการเขียนครั้งละ 16 บิต ซึ่งต้องใช้หน่วยความจำ 2 ไบต์ และในเก็บข้อมูลลงสู่สแต็ก นั้นใน 80x86 จะทำการเก็บไบต์ต่ำก่อน สมมุตว่า AH = 24H และ AL=12H เมื่อเราใช้คำสั่ง PUSH AX และนำไปเก็บในตำแหน่งหน่วยความจำที่แอดเดรส SS:1234 เก็บข้อมูลดังนี้ 12H และตำแหน่งที่ SS:1235 จะเก็บข้อมูลดังนี้ 24Hการอ่านข้อมูลออกจากสแต็ก POPในการในการอ่านข้อมูลออกจากสแต็กนั้น จะทำการเพิ่มค่าของ SP ขึ้นครั้ง 2 ไบต์ในการอ่านแต่ละครั้ง เพราะว่าในการอ่านแต่ละครั้งจะทำการอ่านครั้งละ 16 บิต ซึ่งต้องใช้หน่วยความจำ 2 ไบต์ และในอ่านข้อมูลออกจากสแต็ก นั้นใน 80x86 จะทำการอ่านไบต์ต่ำก่อน สมมุตว่าที่แอดเดรสที่ SS:1234Hมีข้อมูลดังนี้ 12H และที่ตำแหน่ง SS:1235Hมีข้อมูล 24Hตามลำดับ เมื่อเราใช้คำสั่ง POP AX ข้อมูลในรีจีสเตอร์ AX จะได้ดังนี้ AH=24H และAL=12H***สิ่งที่นำเข้าก่อนออกหลัง เช่น การวางกองผลไม่ที่เป็นรูปสามเหลี่ยม*
วันอังคารที่ 28 กรกฎาคม พ.ศ. 2552
DTS03-02-07-2552
7/14/2009
DTS03-02-07-2552
สรุปเรื่อง Pointer และ Set and String
ตัวแปร pointer แปรตรงๆ ว่าตัวชี้จะต่างจากตัวแปรธรรมดาตรงที่แทนที่จะจองram เอาใว้เก็บข้อมูลแต่เอาใว้เก็บ Address ของตัวแปรที่มันชี้อยู่แทนจะมีประโยชน์ก็ตรงที่เราสามารถเข้าถึงข้อมูลข้างใน Address ได้โดยตรงเลยและสามารถเอามาใช้แทนตัวแปร string ที่สร้างโดยใช้ array ได้อีกด้วยรูปแบบชนิด *ชื่อของ pointer;การประกาศก็คล้ายๆ กับตัวแปรธรรมดาแต่จะต่างกันตรงที่ต้องใส่เครื่องหมาย star (*)เอาใว้หน้าชื่อตัวแปรแค่นั้น เพื่อบอกให้รู้ว่านี่คือ pointerเครื่องหมาย & เป็นเครื่องหมายที่บอกตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำ** ในกรณีที่ตัวแปรใดมีเครื่องหมาย & นำหน้าจะไม่สามารถนำมาคำนวณได้การประกาศตัวแปรพอยน์เตอร์ (Declaration of Pointer Variables)type *variable_name ;หรือ type *variable_name1, *variable_name2,... ,*variable_nameN ;โดย type คือ ชนิดของตัวแปร เช่น int ,float ,char ฯลฯ โดยต้องเป็นชนิดเดียวกับของตัวแปรหรือข้อมูลที่พอยน์เตอร์นั้นเก็บตำแหน่งที่อยู่* เป็นเครื่องหมายที่ระบุว่าเป็นตัวแปรพอยน์เตอร์variable_name1, variable_name2,..., variable_nameN ชื่อตัวแปรพอยน์ตัวที่ 1 ถึง ตัวสุดท้ายที่ประกาศในการประกาศครั้งนี้ตัวอย่างint *ptr1, *prt2; char *word, *str1;การกำหนดตำแหน่งของข้อมูลให้ตัวแปรพอยน์เตอร์การกำหนดตำแหน่งที่เก็บข้อมูลในหน่วยความจำของตัวแปรทำได้โดยใช้เครื่องหมาย & (ampersand) นำหน้าชื่อตัวแปร นำมากำหนดให้เป็นค่าของพอยน์เตอร์เช่นint num1 = 120; /* ประกาศและกำหนดค่าให้แก่ตัวแปร ในที่นี้เป็นตัวแปร ชื่อ num1 เป็นประเภท int โดยมีค่า เป็น 120 */int *ptr1; /* ประกาศตัวแปรพอยน์เตอร์ ในที่นี้เป็นประเภท int เพราะใช้เก็บตำแหน่งของตัวแปรประเภท int */ptr1 = &num1; /* กำหนดค่าตำแหน่งของตัวแปรให้เป็นค่าของพอยน์เตอร์ */** ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่ คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่Setเป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย1.set intersection2.set union3.set differenceStringเป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกันความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้นต้องทำการจองเนื้อที่ให้กับ \0 ด้วย
DTS03-02-07-2552
สรุปเรื่อง Pointer และ Set and String
ตัวแปร pointer แปรตรงๆ ว่าตัวชี้จะต่างจากตัวแปรธรรมดาตรงที่แทนที่จะจองram เอาใว้เก็บข้อมูลแต่เอาใว้เก็บ Address ของตัวแปรที่มันชี้อยู่แทนจะมีประโยชน์ก็ตรงที่เราสามารถเข้าถึงข้อมูลข้างใน Address ได้โดยตรงเลยและสามารถเอามาใช้แทนตัวแปร string ที่สร้างโดยใช้ array ได้อีกด้วยรูปแบบชนิด *ชื่อของ pointer;การประกาศก็คล้ายๆ กับตัวแปรธรรมดาแต่จะต่างกันตรงที่ต้องใส่เครื่องหมาย star (*)เอาใว้หน้าชื่อตัวแปรแค่นั้น เพื่อบอกให้รู้ว่านี่คือ pointerเครื่องหมาย & เป็นเครื่องหมายที่บอกตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำ** ในกรณีที่ตัวแปรใดมีเครื่องหมาย & นำหน้าจะไม่สามารถนำมาคำนวณได้การประกาศตัวแปรพอยน์เตอร์ (Declaration of Pointer Variables)type *variable_name ;หรือ type *variable_name1, *variable_name2,... ,*variable_nameN ;โดย type คือ ชนิดของตัวแปร เช่น int ,float ,char ฯลฯ โดยต้องเป็นชนิดเดียวกับของตัวแปรหรือข้อมูลที่พอยน์เตอร์นั้นเก็บตำแหน่งที่อยู่* เป็นเครื่องหมายที่ระบุว่าเป็นตัวแปรพอยน์เตอร์variable_name1, variable_name2,..., variable_nameN ชื่อตัวแปรพอยน์ตัวที่ 1 ถึง ตัวสุดท้ายที่ประกาศในการประกาศครั้งนี้ตัวอย่างint *ptr1, *prt2; char *word, *str1;การกำหนดตำแหน่งของข้อมูลให้ตัวแปรพอยน์เตอร์การกำหนดตำแหน่งที่เก็บข้อมูลในหน่วยความจำของตัวแปรทำได้โดยใช้เครื่องหมาย & (ampersand) นำหน้าชื่อตัวแปร นำมากำหนดให้เป็นค่าของพอยน์เตอร์เช่นint num1 = 120; /* ประกาศและกำหนดค่าให้แก่ตัวแปร ในที่นี้เป็นตัวแปร ชื่อ num1 เป็นประเภท int โดยมีค่า เป็น 120 */int *ptr1; /* ประกาศตัวแปรพอยน์เตอร์ ในที่นี้เป็นประเภท int เพราะใช้เก็บตำแหน่งของตัวแปรประเภท int */ptr1 = &num1; /* กำหนดค่าตำแหน่งของตัวแปรให้เป็นค่าของพอยน์เตอร์ */** ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่ คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่Setเป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย1.set intersection2.set union3.set differenceStringเป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกันความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้นต้องทำการจองเนื้อที่ให้กับ \0 ด้วย
DTS04-15-07-2552
สรุปเรื่อง Linked -List
ลิงค์ลิสต์เดี่ยว
รูปแบบการเก็บข้อมูลโดยการใช้โครงสร้างแบบ Linked -List อาจมีการเชื่อมต่อกันเป็นเส้นตรง(linear) หรือไม่เรียงเป็นเส้นตรง ติดต่อกันไป (nonlinear) ในจำนวนที่ไม่แน่นอน เรียกสมาชิก ของลิงค์ลิสต์ว่า "โหนด" (node) แต่ละโหนดไม่จำเป็นต้องมีสมาชิกในตำแหน่งที่ประชิดกัน โครงสร้างของแต่ละโหนดจะประกอบด้วย 2 ส่วน ส่วนแรกบรรจุสารสนเทศของสมาชิก (INFO) ส่วนที่สองบรรจุตำแหน่งของโหนดถัดไป หรือ โหนดที่ตามมาหลัง (LINK) โหนดสุดท้ายของลิงค์ลิส จะไม่มีโหนดตามหลัง หรือลิงค์ไม่มีการเก็บตำแหน่งของโหนดใด ๆ แต่จะเก็บ ค่า NULL แทน (แทนด้วยเครื่องหมาย / ) ซึ่งเป็นสัญญาณว่าสิ้นสุดลิงค์ลิสต์ ลิงค์ลิสต์เดี่ยวจึงหมายถึง ลิงค์ลิสต์ที่ แต่ละโหนดมีลิงค์ตัวเดียว ส่วนลิงค์ลิสต์ใดที่ไม่มีโหนดเลยเรียกว่า ลิสค์ว่าง (empty)
การท่องลิงค์ลิสต์โหนดที่ถูกชี้โดย พอยเตอร์ใด จะมีชื่อเช่นเดียวกับชื่อพอยเตอร์นั้น ในการท่องลิงค์ลิสต์จะเริ่มต้นค้นหาจาก โหนดแรกไปเรื่อย ๆ จนกว่าจะพบโหนดที่ต้องการการแทรกข้อมูลและการลบข้อมูลการแทรกข้อมูลลงในลิงค์ลิสต์ สามารถจะกระทำได้โดยการเปลี่ยนพอยเตอร์บางตัว และค้นหาข้อมูลใน ลิงค์ลิสต์ เพื่อหาตำแหน่งของโหนดที่มาก่อนโหนดที่ต้องการแทรก สิ่งสำคัญในการแทรกข้อมูลในลิงค์ลิสต์ คือ ลำดับการ เปลี่ยนพอยเตอร์การลบโหนดออกจากลิงค์ลิสต์ จะกระทำโดยการเปลี่ยนพอยเตอร์บางตัว เริ่มต้นก็จะต้องหาโหนดที่มาก่อน โหนดที่ต้องการลบ จากนั้นก็ทำการเปลี่ยนพอยเตอร์ ลิสต์พร้อมใช้งานในทางความคิดโหนดทั้งหมด จะเก็บอยู่ ในรายการอิสระ ซึ่งเราเรียกว่า ลิงค์ลิสต์พร้อมใช้งาน (availability list ) หรือ หน่วยเก็บรวม (storage pool ) เมื่อต้องการนำโหนดมาแทรกในลิงค์ลิสต์ ก็จะมีพอยเตอร์ 1 ตัวในการที่จะชี้ไปยังสมาชิกตัวแรกของลิสต์พร้อมใช้งาน แล้วนำหนดอิสระมาจากลิงค์ลิสต์พร้อมใช้งาน และเชื่อมกับ ลิสต์ในตำแหน่งที่ต้องการในขณะเดียวกัน ถ้ามีการลบโหนดออกจากลิสต์ เราก็จะต้องมีการคืนโหนดไปยังลิสต์พร้อมใช้งาน เพื่อให้สามารถจะนำมาใช้ได้ในภายหลัง ลิงค์ลิสวงกลมลิงค์ลิสต์ชนิดนี้ เกิดจากการปรับปรุงค่าลิงค์ลิสต์ เพื่อให้การประมวลผลที่ดีขึ้น โดยการแทนค่าลิงค์ที่เป็น NULL ของโหนดสุดท้ายของลิงค์ลิสต์ด้วยตำแหน่ง ที่อยู่ของโหนดแรก ลิงค์ลิสต์ในลักษณะนี้เราเรียกว่า ลิงค์ลิสต์วงกลม (circular linking linear list ) หรือ ลิสต์วงกลม ( circular list)ลิงค์ลิสต์วงกลม มีประโยชน์กว่าลิงค์ลิสต์ธรรมดามากกล่าวคือ1. ในการเข้าถึงข้อมูล ของโหนดลิงค์ลิสต์วงกลมโหนดทุกโหนด สามารถเข้าถึงได้จากโหนดใด ๆ ที่กำหนดให้ โดยผ่านทางสายโซ่ (ลิงค์ ) ของลิสต์2. ในการลบโหนด ในการค้นหาโหนดที่มาก่อนโหนดใด ๆ สามารถเริ่มต้นค้นหาในโหนดนั้นได้เลย ข้อเสียของลิงค์ลิสต์วงกลม1. ในการประมวลผลหากไม่ระมัดระวัง อาจทำให้การประมวลผลวนรอบซ้ำไม่รู้จบ (infinite loop )จึงต้อง รู้จุดสิ้นสุดของการทำงาน โดยเราจะแทนจุดสุดท้ายของลิงค์ด้วยโหนดพิเศษ ที่ง่ายต่อการจำแนกโหนดในลิสต์วงกลม ซึ่งเราเรียกโหนดพิเศษนี้ว่า " โหนดหัว" (head node) หรือ "หัวลิสต์" (head list ) ของลิสต์วงกลม เทคนิคนี้จะทำให้ ลิสต์ไม่สามรถเป็นลิสต์ว่างได้ ลิงค์ลิสต์คู่ในลิงค์ลิสต์ประเภทนี้จะมีโหนดซึ่งประกอบด้วยลิงค์ลิสต์ 2 ส่วน เพื่อแสดงโหนดที่มาก่อน และโหนดที่มาที หลัง โหนดที่มาก่อนเราเรียกว่า ลิงค์ซ้าย (left link) ซึ่งแทนด้วยพอยเตอร์ LLINK และลิงค์ที่แทนโหนดที่มาหลังเรา เรียกว่า ลิงค์ขวา(rigth ilnk) ซึ่งแทนด้วยพอยเตอร์ RLINK ซึ่งลิงค์ลิสต์ที่ประกอบด้วย คุณสมบัติดังกล่าวเราเรียกว่า "ลิงค์ลิสต์เชิงเส้นคู่ "(double linked linear list) หรือลิงค์ลิสต์คู่ (double linked list) ในแต่ละทิศทาง ไม่ว่าขวาสุด หรือซ้ายสุด จะมีค่า NULL เพื่อแสดงว่าสิ้นสุดลิสต์ในแต่ละทิศทาง การแทรกข้อมูลในลิงค์ลิสต์คู่การพิจารณาแทรกโหนดในลิงค์ลิสต์คู่มีดังกรณีที่จะเป็นไปได้ดังนี้1. เมื่อลิงค์ลิสต์ว่าง ให้แทนโดยการกำหนดให้ พอยเตอร์ L และพอยเตอร์ R ชี้ไปยังตำแหน่งโหนดใหม่ และกำหนดให้ลิงค์ซ้ายและลิงค์ขวาของโหนดใหม่มีค่า NULLblockquote>
2.เมื่อแทรกโหนดใหม่ลงในกึ่งกลางของลิงค์ลิสต์ ลิงค์ลิสต์ก่อนการแทรกและหลังการแทรก ลำดับการเปลี่ยน พอยเตอร์มีความสำคัญมาก หากเปลี่ยนในลำดับที่ไม่ถูกต้องอาจทำให้โหนดที่บรรจุค่าเดิมสูญหายไป3. เมื่อมีการแทรกโหนดใหม่ทางด้านซ้ายของโหนดซ้ายสุดของลิสต์ จะทำให้พอยเตอร์ L มีค่าเปลี่ยนไป การลบข้อมูลอกจากลิงค์ลิสต์คู่ในการลบโหนดประเภทนี้ แตกต่างจากการลบโหนดในลิงค์ลิสเดี่ยวคือไม่จำเป็นต้องมีการค้นหาโหนดที่มาก่อน โหนดที่จะลบ เพียงกำหนดตำแหน่งของโหนดที่จะลบก็สามารถทราบตำแหน่งของโหนดที่มาก่อน และโหนดที่มาทีหลังโหนดนั้นถ้าลิงค์ลิสต์มีโหนดเพียงโหนดเดียว การลบโหนดออกจากลิงค์ลิสต์จะทำให้ได้ลิงค์ลิสต์ว่าง คือพอยเตอร์ซ้ายสุด และขวาสุดจะถูกกำหนดให้มีค่าเป็น NULL หากพิจารณาขั้นตอนการลบข้อมูลและแทรกข้อมูลในลิงค์ลิสต์ แบบลิงค์ลิสต์คู่ สามารถทำให้ง่ายขึ้นได้ คือในกรณีที่ลิงค์ลิสต์ว่าง สามารถกำหนดให้ลิงค์ลิสต์ไม่เคยว่างได้ โดยการกำหนดโหนดพิเศษ ขึ้นมา 1 โหนด ซึ่งจะเป็นโหนดที่มีอยู่ในลิงค์ลิสต์ตลอดเวลา จึงทำให้ลิงค์ลิสต์ว่างมีเพียง 1 โหนด ที่เป็นโหนดพิเศษเท่านั้น ซึ่งเรียกว่าโหนดหัว (Head node)ของลิงค์ลิสต์ และนอกจกนั้นยังสามารถสร้างลิงค์ลิสคู่เป็นลิงค์ลิสต์วงกลมได้ ขั้นตอนวิธีในการแทรกและลบโหนดตามหลังโหนดที่กำหนดให้ใด ๆ จะลดลำดับขั้นตอนให้น้อยลง
ลิงค์ลิสต์เดี่ยว
รูปแบบการเก็บข้อมูลโดยการใช้โครงสร้างแบบ Linked -List อาจมีการเชื่อมต่อกันเป็นเส้นตรง(linear) หรือไม่เรียงเป็นเส้นตรง ติดต่อกันไป (nonlinear) ในจำนวนที่ไม่แน่นอน เรียกสมาชิก ของลิงค์ลิสต์ว่า "โหนด" (node) แต่ละโหนดไม่จำเป็นต้องมีสมาชิกในตำแหน่งที่ประชิดกัน โครงสร้างของแต่ละโหนดจะประกอบด้วย 2 ส่วน ส่วนแรกบรรจุสารสนเทศของสมาชิก (INFO) ส่วนที่สองบรรจุตำแหน่งของโหนดถัดไป หรือ โหนดที่ตามมาหลัง (LINK) โหนดสุดท้ายของลิงค์ลิส จะไม่มีโหนดตามหลัง หรือลิงค์ไม่มีการเก็บตำแหน่งของโหนดใด ๆ แต่จะเก็บ ค่า NULL แทน (แทนด้วยเครื่องหมาย / ) ซึ่งเป็นสัญญาณว่าสิ้นสุดลิงค์ลิสต์ ลิงค์ลิสต์เดี่ยวจึงหมายถึง ลิงค์ลิสต์ที่ แต่ละโหนดมีลิงค์ตัวเดียว ส่วนลิงค์ลิสต์ใดที่ไม่มีโหนดเลยเรียกว่า ลิสค์ว่าง (empty)
การท่องลิงค์ลิสต์โหนดที่ถูกชี้โดย พอยเตอร์ใด จะมีชื่อเช่นเดียวกับชื่อพอยเตอร์นั้น ในการท่องลิงค์ลิสต์จะเริ่มต้นค้นหาจาก โหนดแรกไปเรื่อย ๆ จนกว่าจะพบโหนดที่ต้องการการแทรกข้อมูลและการลบข้อมูลการแทรกข้อมูลลงในลิงค์ลิสต์ สามารถจะกระทำได้โดยการเปลี่ยนพอยเตอร์บางตัว และค้นหาข้อมูลใน ลิงค์ลิสต์ เพื่อหาตำแหน่งของโหนดที่มาก่อนโหนดที่ต้องการแทรก สิ่งสำคัญในการแทรกข้อมูลในลิงค์ลิสต์ คือ ลำดับการ เปลี่ยนพอยเตอร์การลบโหนดออกจากลิงค์ลิสต์ จะกระทำโดยการเปลี่ยนพอยเตอร์บางตัว เริ่มต้นก็จะต้องหาโหนดที่มาก่อน โหนดที่ต้องการลบ จากนั้นก็ทำการเปลี่ยนพอยเตอร์ ลิสต์พร้อมใช้งานในทางความคิดโหนดทั้งหมด จะเก็บอยู่ ในรายการอิสระ ซึ่งเราเรียกว่า ลิงค์ลิสต์พร้อมใช้งาน (availability list ) หรือ หน่วยเก็บรวม (storage pool ) เมื่อต้องการนำโหนดมาแทรกในลิงค์ลิสต์ ก็จะมีพอยเตอร์ 1 ตัวในการที่จะชี้ไปยังสมาชิกตัวแรกของลิสต์พร้อมใช้งาน แล้วนำหนดอิสระมาจากลิงค์ลิสต์พร้อมใช้งาน และเชื่อมกับ ลิสต์ในตำแหน่งที่ต้องการในขณะเดียวกัน ถ้ามีการลบโหนดออกจากลิสต์ เราก็จะต้องมีการคืนโหนดไปยังลิสต์พร้อมใช้งาน เพื่อให้สามารถจะนำมาใช้ได้ในภายหลัง ลิงค์ลิสวงกลมลิงค์ลิสต์ชนิดนี้ เกิดจากการปรับปรุงค่าลิงค์ลิสต์ เพื่อให้การประมวลผลที่ดีขึ้น โดยการแทนค่าลิงค์ที่เป็น NULL ของโหนดสุดท้ายของลิงค์ลิสต์ด้วยตำแหน่ง ที่อยู่ของโหนดแรก ลิงค์ลิสต์ในลักษณะนี้เราเรียกว่า ลิงค์ลิสต์วงกลม (circular linking linear list ) หรือ ลิสต์วงกลม ( circular list)ลิงค์ลิสต์วงกลม มีประโยชน์กว่าลิงค์ลิสต์ธรรมดามากกล่าวคือ1. ในการเข้าถึงข้อมูล ของโหนดลิงค์ลิสต์วงกลมโหนดทุกโหนด สามารถเข้าถึงได้จากโหนดใด ๆ ที่กำหนดให้ โดยผ่านทางสายโซ่ (ลิงค์ ) ของลิสต์2. ในการลบโหนด ในการค้นหาโหนดที่มาก่อนโหนดใด ๆ สามารถเริ่มต้นค้นหาในโหนดนั้นได้เลย ข้อเสียของลิงค์ลิสต์วงกลม1. ในการประมวลผลหากไม่ระมัดระวัง อาจทำให้การประมวลผลวนรอบซ้ำไม่รู้จบ (infinite loop )จึงต้อง รู้จุดสิ้นสุดของการทำงาน โดยเราจะแทนจุดสุดท้ายของลิงค์ด้วยโหนดพิเศษ ที่ง่ายต่อการจำแนกโหนดในลิสต์วงกลม ซึ่งเราเรียกโหนดพิเศษนี้ว่า " โหนดหัว" (head node) หรือ "หัวลิสต์" (head list ) ของลิสต์วงกลม เทคนิคนี้จะทำให้ ลิสต์ไม่สามรถเป็นลิสต์ว่างได้ ลิงค์ลิสต์คู่ในลิงค์ลิสต์ประเภทนี้จะมีโหนดซึ่งประกอบด้วยลิงค์ลิสต์ 2 ส่วน เพื่อแสดงโหนดที่มาก่อน และโหนดที่มาที หลัง โหนดที่มาก่อนเราเรียกว่า ลิงค์ซ้าย (left link) ซึ่งแทนด้วยพอยเตอร์ LLINK และลิงค์ที่แทนโหนดที่มาหลังเรา เรียกว่า ลิงค์ขวา(rigth ilnk) ซึ่งแทนด้วยพอยเตอร์ RLINK ซึ่งลิงค์ลิสต์ที่ประกอบด้วย คุณสมบัติดังกล่าวเราเรียกว่า "ลิงค์ลิสต์เชิงเส้นคู่ "(double linked linear list) หรือลิงค์ลิสต์คู่ (double linked list) ในแต่ละทิศทาง ไม่ว่าขวาสุด หรือซ้ายสุด จะมีค่า NULL เพื่อแสดงว่าสิ้นสุดลิสต์ในแต่ละทิศทาง การแทรกข้อมูลในลิงค์ลิสต์คู่การพิจารณาแทรกโหนดในลิงค์ลิสต์คู่มีดังกรณีที่จะเป็นไปได้ดังนี้1. เมื่อลิงค์ลิสต์ว่าง ให้แทนโดยการกำหนดให้ พอยเตอร์ L และพอยเตอร์ R ชี้ไปยังตำแหน่งโหนดใหม่ และกำหนดให้ลิงค์ซ้ายและลิงค์ขวาของโหนดใหม่มีค่า NULLblockquote>
2.เมื่อแทรกโหนดใหม่ลงในกึ่งกลางของลิงค์ลิสต์ ลิงค์ลิสต์ก่อนการแทรกและหลังการแทรก ลำดับการเปลี่ยน พอยเตอร์มีความสำคัญมาก หากเปลี่ยนในลำดับที่ไม่ถูกต้องอาจทำให้โหนดที่บรรจุค่าเดิมสูญหายไป3. เมื่อมีการแทรกโหนดใหม่ทางด้านซ้ายของโหนดซ้ายสุดของลิสต์ จะทำให้พอยเตอร์ L มีค่าเปลี่ยนไป การลบข้อมูลอกจากลิงค์ลิสต์คู่ในการลบโหนดประเภทนี้ แตกต่างจากการลบโหนดในลิงค์ลิสเดี่ยวคือไม่จำเป็นต้องมีการค้นหาโหนดที่มาก่อน โหนดที่จะลบ เพียงกำหนดตำแหน่งของโหนดที่จะลบก็สามารถทราบตำแหน่งของโหนดที่มาก่อน และโหนดที่มาทีหลังโหนดนั้นถ้าลิงค์ลิสต์มีโหนดเพียงโหนดเดียว การลบโหนดออกจากลิงค์ลิสต์จะทำให้ได้ลิงค์ลิสต์ว่าง คือพอยเตอร์ซ้ายสุด และขวาสุดจะถูกกำหนดให้มีค่าเป็น NULL หากพิจารณาขั้นตอนการลบข้อมูลและแทรกข้อมูลในลิงค์ลิสต์ แบบลิงค์ลิสต์คู่ สามารถทำให้ง่ายขึ้นได้ คือในกรณีที่ลิงค์ลิสต์ว่าง สามารถกำหนดให้ลิงค์ลิสต์ไม่เคยว่างได้ โดยการกำหนดโหนดพิเศษ ขึ้นมา 1 โหนด ซึ่งจะเป็นโหนดที่มีอยู่ในลิงค์ลิสต์ตลอดเวลา จึงทำให้ลิงค์ลิสต์ว่างมีเพียง 1 โหนด ที่เป็นโหนดพิเศษเท่านั้น ซึ่งเรียกว่าโหนดหัว (Head node)ของลิงค์ลิสต์ และนอกจกนั้นยังสามารถสร้างลิงค์ลิสคู่เป็นลิงค์ลิสต์วงกลมได้ ขั้นตอนวิธีในการแทรกและลบโหนดตามหลังโหนดที่กำหนดให้ใด ๆ จะลดลำดับขั้นตอนให้น้อยลง
สมัครสมาชิก:
บทความ (Atom)
