Psl/ลิงก์ลิสต์ - ประวัติรุ่นแก้ไข

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

2015-01-26T07:00:32Z

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

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

2015-01-26T05:49:13Z

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

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

2015-01-26T05:48:42Z

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

Jittat เมื่อ 05:37, 26 มกราคม 2558

2015-01-26T05:37:12Z

Jittat เมื่อ 05:35, 26 มกราคม 2558

2015-01-26T05:35:44Z

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

2015-01-26T05:34:57Z

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

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

2015-01-26T05:28:02Z

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

Jittat: /* โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header) */

2015-01-26T05:26:11Z

โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header)

Jittat: /* โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header) */

2015-01-26T05:23:03Z

โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header)

Jittat: /* โหนด */

2015-01-25T23:42:11Z

โหนด

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:00, 26 มกราคม 2558
แถว 120:		แถว 120:

	การอ้างถึงข้อมูลจากตอนต้นรายการนั้นในบางครั้งอาจจะไม่สะดวกและไม่มีประสิทธิภาพเท่าใดนัก โดยเฉพาะกรณีที่เราต้องการเก็บข้อมูลจากตอนท้ายลิสต์ด้วย เช่น ต้องการให้มีการเพิ่มข้อมูลต่อท้ายรายการ ดังนั้น เรามักจะเก็บพอยน์เตอร์ tail ควบคู่ไปกับ header โดยพอยน์เตอร์นี้จะชี้ไปที่ข้อมูลตัวสุดท้ายในรายการ เพื่อทำให้เราแทรกข้อมูลต่อท้ายรายการได้ง่าย		การอ้างถึงข้อมูลจากตอนต้นรายการนั้นในบางครั้งอาจจะไม่สะดวกและไม่มีประสิทธิภาพเท่าใดนัก โดยเฉพาะกรณีที่เราต้องการเก็บข้อมูลจากตอนท้ายลิสต์ด้วย เช่น ต้องการให้มีการเพิ่มข้อมูลต่อท้ายรายการ ดังนั้น เรามักจะเก็บพอยน์เตอร์ 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) ==		== ลิสต์แบบสองทาง (doubly linked lists) ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:49, 26 มกราคม 2558
แถว 138:		แถว 138:
	};		};
	</syntaxhighlight>		</syntaxhighlight>
		+
		+	แต่ในการทำงานด้วย ก็จะต้องระวังการปรับพอยน์เตอร์ทั้ง next และ prev

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:48, 26 มกราคม 2558
แถว 123:		แถว 123:
	== ลิสต์แบบสองทาง (doubly linked lists) ==		== ลิสต์แบบสองทาง (doubly linked lists) ==

−	อ่านที่วิกิพีเดีย: [http://en.wikipedia.org/wiki/Doubly_linked_list]	+	: อ่านที่วิกิพีเดีย: [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>

@@ แถว 1: / แถว 1: @@
 : ''หน้านี้เป็นส่วนหนึ่งของ [[problem solving lab]]''
 == พื้นฐาน ==
@@ แถว 120: / แถว 122: @@
 == ลิสต์แบบสองทาง (doubly linked lists) ==

@@ แถว 1: / แถว 1: @@
 : ''หน้านี้เป็นส่วนหนึ่งของ [[problem solving lab]]''
-== โหนด ==
+== พื้นฐาน ==
 โครงสร้างพื้นฐานของลิงก์ลิสต์คือโหนด ซึ่งโดยมากจะมีข้อมูลสองชุดคือข้อมูลในโหนดนั้นเอง กับพอยน์เตอร์ไปยังโหนดถัดไป
@@ แถว 51: / แถว 49: @@
 </syntaxhighlight>
-=== โหนดฉบับปรับปรุง ===
+== โหนดฉบับปรับปรุง ==
 ใน C++ การประกาศ struct ก็เปรียบเสมือนการประกาศคลาสที่ข้อมูลภายในเป็น public ทั้งหมด  ในหลาย ๆ กรณี เราสามารถเพิ่ม constructor เพื่อเพิ่มความสะดวกในการใช้งานได้ ดังด้านล่าง
@@ แถว 94: / แถว 92: @@
 ได้เลย โดยในกรณีนี้ <tt>header->next</tt> จะมีค่าเป็น 0
-=== ลิงก์ลิสต์แบบมีหัว (header) ===
+== ลิงก์ลิสต์แบบมีหัว (header) ==
 การเพิ่มข้อมูลเข้าไปด้านหลังโหนดใด ๆ ในลิงก์ลิสต์ทำได้โดยง่าย
@@ แถว 121: / แถว 119: @@
 การอ้างถึงข้อมูลจากตอนต้นรายการนั้นในบางครั้งอาจจะไม่สะดวกและไม่มีประสิทธิภาพเท่าใดนัก  โดยเฉพาะกรณีที่เราต้องการเก็บข้อมูลจากตอนท้ายลิสต์ด้วย เช่น ต้องการให้มีการเพิ่มข้อมูลต่อท้ายรายการ  ดังนั้น เรามักจะเก็บพอยน์เตอร์ tail ควบคู่ไปกับ header โดยพอยน์เตอร์นี้จะชี้ไปที่ข้อมูลตัวสุดท้ายในรายการ เพื่อทำให้เราแทรกข้อมูลต่อท้ายรายการได้ง่าย
-== กิจกรรม ==
+== ลิสต์แบบสองทาง (doubly linked lists) ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:28, 26 มกราคม 2558
แถว 95:		แถว 95:

	=== ลิงก์ลิสต์แบบมีหัว (header) ===		=== ลิงก์ลิสต์แบบมีหัว (header) ===
		+	การเพิ่มข้อมูลเข้าไปด้านหลังโหนดใด ๆ ในลิงก์ลิสต์ทำได้โดยง่าย
		+
		+	สมมติว่าเรามีพอยน์เตอร์ p ที่ชี้ไปยังโหนด และต้องการเพิ่มโหนดที่เก็บค่า 100 ต่อจาก p เราทำได้ดังนี้
		+
		+	<syntaxhighlight lang="cpp">
		+	ListNode* new_node = new ListNode(100);
		+	new_node->next = p->next;
		+	p->next = new_node;
		+	</syntaxhighlight>

	== กิจกรรม ==		== กิจกรรม ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:23, 26 มกราคม 2558
แถว 52:		แถว 52:

	=== โหนดฉบับปรับปรุง 1 และลิงก์ลิสต์แบบมีหัว (header) ===		=== โหนดฉบับปรับปรุง 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

	== กิจกรรม ==		== กิจกรรม ==

@@ แถว 13: / แถว 13: @@
 </syntaxhighlight>
-ตัวอย่างการสร้างแบบตรงไปตรงมา
+ตัวอย่างการสร้างลิสต์แบบตรงไปตรงมา
 <syntaxhighlight lang="cpp">
@@ แถว 27: / แถว 27: @@
    n2->value = 40;
    n2->next = 0;
    print_list(n1);
+}
 </syntaxhighlight>
 สังเกตว่าเราสามารถเขียน <tt>var->field</tt> แทน <tt>(*var).field</tt> ได้