ผลต่างระหว่างรุ่นของ "Psl/ลิงก์ลิสต์"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
: ''หน้านี้เป็นส่วนหนึ่งของ [[problem solving lab]]''
 
: ''หน้านี้เป็นส่วนหนึ่งของ [[problem solving lab]]''
  
−
== โหนด ==
+
หน้านี้มีรายละเอียดเพิ่มเติมสำหรับการเขียนลิงก์ลิสต์ อ่านเพิ่มเติมได้ที่ [http://en.wikipedia.org/wiki/Linked_list วิกิพีเดีย]
  
−
=== พื้นฐาน ===
+
== พื้นฐาน ==
 
โครงสร้างพื้นฐานของลิงก์ลิสต์คือโหนด ซึ่งโดยมากจะมีข้อมูลสองชุดคือข้อมูลในโหนดนั้นเอง กับพอยน์เตอร์ไปยังโหนดถัดไป
 
โครงสร้างพื้นฐานของลิงก์ลิสต์คือโหนด ซึ่งโดยมากจะมีข้อมูลสองชุดคือข้อมูลในโหนดนั้นเอง กับพอยน์เตอร์ไปยังโหนดถัดไป
  
แถว 13: แถว 13:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
ตัวอย่างการสร้างแบบตรงไปตรงมา
+
ตัวอย่างการสร้างลิสต์แบบตรงไปตรงมา
  
 
<syntaxhighlight lang="cpp">
 
<syntaxhighlight lang="cpp">
แถว 27: แถว 27:
 
   n2->value = 40;
 
   n2->value = 40;
 
   n2->next = 0;
 
   n2->next = 0;
 +
 
   print_list(n1);
 
   print_list(n1);
 +
 +
  delete n1;
 +
  delete n2;
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
ใน C++ เราใช้โอเปอร์เรเตอร์ <tt>new</tt> และ <tt>delete</tt> ในการสร้างและทำลาย object  ในขั้นตอนของการสร้างจะมีการจองหน่วยความจำและกำหนดค่าเริ่มต้น เมื่อเราทำลายด้วย delete จะมีการคืนค่าหน่วยความจำ  ถ้าเราเขียนในภาษา C, โดยมากเราจะใช้คำสั่ง <tt>malloc</tt> ซึ่งจะทำหน้าที่จองหน่วยความจำ และคำสั่ง <tt>free</tt> ที่คืนหน่วยความจำ
  
 
สังเกตว่าเราสามารถเขียน <tt>var->field</tt> แทน <tt>(*var).field</tt> ได้
 
สังเกตว่าเราสามารถเขียน <tt>var->field</tt> แทน <tt>(*var).field</tt> ได้
แถว 45: แถว 51:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
=== โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header) ===
+
== โหนดฉบับปรับปรุง ==
 +
ใน C++ การประกาศ struct ก็เปรียบเสมือนการประกาศคลาสที่ข้อมูลภายในเป็น public ทั้งหมด  ในหลาย ๆ กรณี เราสามารถเพิ่ม constructor เพื่อเพิ่มความสะดวกในการใช้งานได้ ดังด้านล่าง
 +
 
 +
<syntaxhighlight lang="cpp">
 +
struct ListNode {
 +
  int value;
 +
  ListNode* next;
 +
 
 +
  ListNode(int v, ListNode* n)
 +
  {
 +
    value = v;
 +
    next = n;
 +
  }
 +
};
 +
</syntaxhighlight>
 +
 
 +
เมื่อเราสั่ง
 +
<syntaxhighlight lang="cpp">
 +
  ListNode* n = new ListNode(100,0);
 +
</syntaxhighlight>
 +
ก็จะเหมือนกับการเรียก constructor ดังกล่าว
 +
 
 +
สังเกตเพิ่มเติมว่าจริง ๆ แล้วในการกำหนดค่าเริ่มต้นให้กับ value และ next นั้น ก็เป็นเหมือนการเรียก constructor ให้กับ data member ทั้งสอง ดังนั้นเราเขียนให้ชัดเจนได้เป็น
 +
 
 +
<syntaxhighlight lang="cpp">
 +
struct ListNode {
 +
  int value;
 +
  ListNode* next;
 +
 
 +
  ListNode(int v, ListNode* n=0)
 +
    :value(v), next(n)
 +
  {}
 +
};
 +
</syntaxhighlight>
 +
 
 +
นอกจากนี้เรายังกำหนด default parameter ได้ด้วย ยกตัวอย่างเช่น n ในโค้ดด้านบน  ถ้าเขียนแบบนี้ เราสามารถสั่ง
 +
 
 +
<syntaxhighlight lang="cpp">
 +
  ListNode* header = new ListNode(0);
 +
</syntaxhighlight>
 +
 
 +
ได้เลย โดยในกรณีนี้ <tt>header->next</tt> จะมีค่าเป็น 0
 +
 
 +
== ลิงก์ลิสต์แบบมีหัว (header) ==
 +
การเพิ่มข้อมูลเข้าไปด้านหลังโหนดใด ๆ ในลิงก์ลิสต์ทำได้โดยง่าย
 +
 
 +
สมมติว่าเรามีพอยน์เตอร์ p ที่ชี้ไปยังโหนด  และต้องการเพิ่มโหนดที่เก็บค่า 100 ต่อจาก p เราทำได้ดังนี้
 +
 
 +
<syntaxhighlight lang="cpp">
 +
ListNode* new_node = new ListNode(100);
 +
new_node->next = p->next;
 +
p->next = new_node;
 +
</syntaxhighlight>
 +
 
 +
อย่างไรก็ตาม ถ้าเราต้องการแทรกข้อมูลไว้ที่ต้นลิสต์ เราจะทำไม่ได้โดยง่าย  วิธีการมาตรฐานที่นิยมใช้กันเพื่อแก้ปัญหานี้ก็คือการสร้าง dummy header ไว้ที่ต้นลิสต์ ทำให้แทรกข้อมูลที่ตอนหัวได้
 +
 
 +
โค้ดทั่ว ๆ ไปจะเป็นดังนี้
 +
 
 +
<syntaxhighlight lang="cpp">
 +
// ประกาศหัวเปล่า
 +
ListNode* header = new ListNode(0);
 +
 
 +
// แทรกข้อมูลเข้าที่หัว
 +
ListNode* new_node = new ListNode(100);
 +
new_node->next = header->next;
 +
header->next = new_node;
 +
</syntaxhighlight>
 +
 
 +
การอ้างถึงข้อมูลจากตอนต้นรายการนั้นในบางครั้งอาจจะไม่สะดวกและไม่มีประสิทธิภาพเท่าใดนัก  โดยเฉพาะกรณีที่เราต้องการเก็บข้อมูลจากตอนท้ายลิสต์ด้วย เช่น ต้องการให้มีการเพิ่มข้อมูลต่อท้ายรายการ  ดังนั้น เรามักจะเก็บพอยน์เตอร์ tail ควบคู่ไปกับ header โดยพอยน์เตอร์นี้จะชี้ไปที่ข้อมูลตัวสุดท้ายในรายการ เพื่อทำให้เราแทรกข้อมูลต่อท้ายรายการได้ง่าย
 +
 
 +
=== ตัวอย่าง ===
 +
<syntaxhighlight lang="cpp">
 +
  ListNode* header = new ListNode(0);
 +
  for(int i=0; i<10; i++) {
 +
    ListNode* nn = new ListNode(i*100);
 +
    nn->next = header->next;
 +
    header->next = nn;
 +
  }
 +
</syntaxhighlight>
 +
 
 +
== ลิสต์แบบสองทาง (doubly linked lists) ==
 +
 
 +
: อ่านที่วิกิพีเดีย: [http://en.wikipedia.org/wiki/Doubly_linked_list]
 +
 
 +
การประกาศก็จะไม่ต่างจากลิงก์ลิสต์ธรรมดานัก
 +
 
 +
<syntaxhighlight lang="cpp">
 +
struct ListNode {
 +
  int value;
 +
  ListNode* next;
 +
  ListNode* prev;
 +
 
 +
  ListNode(int v, ListNode* n=0, ListNode* p=0)
 +
    :value(v), next(n), prev(p)
 +
  {}
 +
};
 +
</syntaxhighlight>
  
−
== กิจกรรม ==
+
แต่ในการทำงานด้วย ก็จะต้องระวังการปรับพอยน์เตอร์ทั้ง next และ prev

รุ่นแก้ไขปัจจุบันเมื่อ 07:00, 26 มกราคม 2558

หน้านี้เป็นส่วนหนึ่งของ problem solving lab

หน้านี้มีรายละเอียดเพิ่มเติมสำหรับการเขียนลิงก์ลิสต์ อ่านเพิ่มเติมได้ที่ วิกิพีเดีย

พื้นฐาน

โครงสร้างพื้นฐานของลิงก์ลิสต์คือโหนด ซึ่งโดยมากจะมีข้อมูลสองชุดคือข้อมูลในโหนดนั้นเอง กับพอยน์เตอร์ไปยังโหนดถัดไป 

struct ListNode {
  int value;
  ListNode* next;
};

ตัวอย่างการสร้างลิสต์แบบตรงไปตรงมา 

main()
{
  ListNode* n1;
  ListNode* n2;

  n1 = new ListNode;
  n2 = new ListNode;
  n1->value = 10;
  n1->next = n2;
  n2->value = 40;
  n2->next = 0;

  print_list(n1);

  delete n1;
  delete n2;
}

ใน C++ เราใช้โอเปอร์เรเตอร์ new และ delete ในการสร้างและทำลาย object ในขั้นตอนของการสร้างจะมีการจองหน่วยความจำและกำหนดค่าเริ่มต้น เมื่อเราทำลายด้วย delete จะมีการคืนค่าหน่วยความจำ ถ้าเราเขียนในภาษา C, โดยมากเราจะใช้คำสั่ง malloc ซึ่งจะทำหน้าที่จองหน่วยความจำ และคำสั่ง free ที่คืนหน่วยความจำ

สังเกตว่าเราสามารถเขียน var->field แทน (*var).field ได้

ด้านล่างเป็นตัวอย่างฟังก์ชันที่วิ่งไปในลิสต์เพื่อพิมพ์รายการในลิสต์ 

void print_list(ListNode* list)
{
  while(list != 0) {
    printf("%d\n", list->value);
    list = list->next;
  }
}

โหนดฉบับปรับปรุง

ใน C++ การประกาศ struct ก็เปรียบเสมือนการประกาศคลาสที่ข้อมูลภายในเป็น public ทั้งหมด ในหลาย ๆ กรณี เราสามารถเพิ่ม constructor เพื่อเพิ่มความสะดวกในการใช้งานได้ ดังด้านล่าง 

struct ListNode {
  int value;
  ListNode* next;

  ListNode(int v, ListNode* n)
  {
    value = v;
    next = n;
  }
};

เมื่อเราสั่ง 

  ListNode* n = new ListNode(100,0);

ก็จะเหมือนกับการเรียก constructor ดังกล่าว

สังเกตเพิ่มเติมว่าจริง ๆ แล้วในการกำหนดค่าเริ่มต้นให้กับ value และ next นั้น ก็เป็นเหมือนการเรียก constructor ให้กับ data member ทั้งสอง ดังนั้นเราเขียนให้ชัดเจนได้เป็น 

struct ListNode {
  int value;
  ListNode* next;

  ListNode(int v, ListNode* n=0)
    :value(v), next(n)
  {}
};

นอกจากนี้เรายังกำหนด default parameter ได้ด้วย ยกตัวอย่างเช่น n ในโค้ดด้านบน ถ้าเขียนแบบนี้ เราสามารถสั่ง 

  ListNode* header = new ListNode(0);

ได้เลย โดยในกรณีนี้ header->next จะมีค่าเป็น 0

ลิงก์ลิสต์แบบมีหัว (header)

การเพิ่มข้อมูลเข้าไปด้านหลังโหนดใด ๆ ในลิงก์ลิสต์ทำได้โดยง่าย

สมมติว่าเรามีพอยน์เตอร์ p ที่ชี้ไปยังโหนด และต้องการเพิ่มโหนดที่เก็บค่า 100 ต่อจาก p เราทำได้ดังนี้ 

ListNode* new_node = new ListNode(100);
new_node->next = p->next;
p->next = new_node;

อย่างไรก็ตาม ถ้าเราต้องการแทรกข้อมูลไว้ที่ต้นลิสต์ เราจะทำไม่ได้โดยง่าย วิธีการมาตรฐานที่นิยมใช้กันเพื่อแก้ปัญหานี้ก็คือการสร้าง dummy header ไว้ที่ต้นลิสต์ ทำให้แทรกข้อมูลที่ตอนหัวได้

โค้ดทั่ว ๆ ไปจะเป็นดังนี้ 

// ประกาศหัวเปล่า
ListNode* header = new ListNode(0);

// แทรกข้อมูลเข้าที่หัว
ListNode* new_node = new ListNode(100);
new_node->next = header->next;
header->next = new_node;

การอ้างถึงข้อมูลจากตอนต้นรายการนั้นในบางครั้งอาจจะไม่สะดวกและไม่มีประสิทธิภาพเท่าใดนัก โดยเฉพาะกรณีที่เราต้องการเก็บข้อมูลจากตอนท้ายลิสต์ด้วย เช่น ต้องการให้มีการเพิ่มข้อมูลต่อท้ายรายการ ดังนั้น เรามักจะเก็บพอยน์เตอร์ tail ควบคู่ไปกับ header โดยพอยน์เตอร์นี้จะชี้ไปที่ข้อมูลตัวสุดท้ายในรายการ เพื่อทำให้เราแทรกข้อมูลต่อท้ายรายการได้ง่าย

ตัวอย่าง

  ListNode* header = new ListNode(0);
  for(int i=0; i<10; i++) {
    ListNode* nn = new ListNode(i*100);
    nn->next = header->next;
    header->next = nn;
  }

ลิสต์แบบสองทาง (doubly linked lists)

อ่านที่วิกิพีเดีย: [1]

การประกาศก็จะไม่ต่างจากลิงก์ลิสต์ธรรมดานัก 

struct ListNode {
  int value;
  ListNode* next;
  ListNode* prev;

  ListNode(int v, ListNode* n=0, ListNode* p=0)
    :value(v), next(n), prev(p)
  {}
};

แต่ในการทำงานด้วย ก็จะต้องระวังการปรับพอยน์เตอร์ทั้ง next และ prev

ดึงข้อมูลจาก "https://theory.cpe.ku.ac.th/wiki/index.php?title=Psl/ลิงก์ลิสต์&oldid=47995"