DTS05-22-07-52

สรุปสิ่งที่ได้จากการเรียน เรื่อง Linked List

- โครงสร้างข้อมลแบบลิงค์ลิสต์
- กระบวนงานและฟังกชันทที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต์
- ลิงค์ลิสต์แบบซับซ้อน

ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมพอยเตอร์เป็นตัวเชื่อมต่อ
แต่ละอิลลเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คอ Data จะเก็บข้อมูลของอิลิเมนท์
และส่วนที่สอง คอ Link Field จะทำหน้าที่เก็บตฎแหน่งของโนดต่อไปในลิสต์

การดำเนินการเกี่ยวกับสตริง จะใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาว
- ฟังก์ชัน strcpy(str1, str2) ใช้คัดลอกข้อมูล จากตัวที่ 2 ไปให้ตัวที่ 1
- ฟังก์ชัน strcat(str1, str2) ใช้เชื่อมต่อข้อความ เช่น ตัวแปร 1 เก็บ ชื่อ ตัวแปร 2 เก็บ นามสกุล แล้วนำตัวแปรทั้ง2 มาต่อกัน
- ฟังก์ชัน stecmp(str1, str2) ใช้ปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ยึดตามหลักพจนานุกรม

โครงสร้างข้อมูลแบบลิงค์ลิสต์
จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure ประกอบด้วย Count, Pos และ head แสดงได้ดังภาพ

2. Data Node Structure ประกอบด้วย Data และ Pointer ที่ชี้ไปยังข้อมูลตัวถัดไป แสดงได้ดังภาพ

กระบวนงานและฟังก์ชันที่ใช้ดำเนินงานพื้นฐาน
1. Create List มีหน้าที่สร้างลิสต์ว่าง ผลลัพธ์ที่ได้คือ ลิสต์ว่าง และ count จะมีค่าป็น 0

2. Insert Node มีหน้าที่เพิ่มข้อมูลลงไปในลิสต์ในตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ลิสต์ ข้อมูล และตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะมีค่าเป็น 1 หรือ 2.....n ตามจำนวนของการ insert

3. Delete Node มีหน้าที่ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ข้อมูลและตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะลดจำนวนจากเดิมลงเรื่อย ตามจำนวนลิสต์ที่ลบไป

4. Search list มีหน้าที่ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ ผลลัพธ์ที่ได้ จะเป็นค่าจริงถ้าพบข้อมูล และจะเป็นค่าเท็จถ้าไม่พบข้อมูล

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

6. Retrieve Node ทำหน้าที่หาตำแหน่งของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้ก็คือ ตำแหน่งข้อมูลที่อยู่ในลิสต์ และเมื่อรู้ตำแหน่งก็ดึงค่าที่ได้มาแสดงในโปรแกรม

7. EmptyList ทำหน้าที่ทดสอบดูว่า ลิสต์ว่างหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อลิสต์ว่าง และจะเป็นเท็จก็ต่อเมื่อลิสต์ไม่ว่าง

8. FullList ทำหน้าที่ในการทดสอบว่าลิสต์เต็มหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อหน่วยความจำเต็ม และจะเป็เท็จก็ต่อเมื่อลิสต์นั้นสามารถมีโนดอื่น

9. List Count ทำหน้าที่นับจำนวนของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้คือ จำนวนข้อมูลที่อยู่ในลิสต์นั้นๆ ซึ่งจะใช้ค่า count ที่อยู่ใน Head Node ออกมาแสดง

10. Destroy List ทำหน้าที่ในการลำลายลิสต์ หรือหยุดใช้ลิสต์นี้แล้ว

Linked List แบบซับซ้อน มี 2 แบบ

สแตก stack

สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทําที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สําคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนําออกมา จากสแตกเป็นลําดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)

การดําเนินงานพื้นฐานของสแตกการทํางานต่าง ๆ ของสแตกจะกระทําที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตําแหน่งข้อมูลบนสุดของสแตกด้วยการทํางานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สําคัญ

คือ1.Push คือ การนําข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก

ในการเพิ่มข้อมูลลงในสแตก จะต้องทําการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตําแหน่งให้ไปชี้ที่ตําแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม้สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก

2. Pop คือ การนําข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนําข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนําข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนําสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทําการ pop สแตก จะทําให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนําข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนําข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตําแหน่งให้ไปชี้ตําแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนํา ออกไป

3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นําเอาข้อมูลนั้นออกจากสแตก

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

• การใส่เสื้อผ้าเราจะต้องเริ่มใส่เสื้อผ้าที่อยู่ด้านในสุดก่อน และเมื่อเราจะถอดเสื้อผ้าเราก้อจะต้องเริ่มถอดจากชิ้นนอกก่อนเสมอถอดไล่จากชิ้นนอกไปจนถึงชิ้นในสุดเพราะเราไม่สามารถที่จะถอดชิ้นที่อยู่ด้านในออกก่อนได้
• การหยิบน้ำดื่มจากตู้แช่ตามร้านสะดวกซื้อต่างๆ ซึ่งผู้ซื้อจะต้องหยิบน้ำดืมขวดที่อยู่ด้านนอกสุด ซึ่งเป็นขวดสุดท้านในการนำเข้าในตู้แซ่
• การหยิบรถเข็นในห้างสรรพสินค้า

DTS04-15-07-52

สรุปบทเรียนเรื่อง เซ็ตและสตริง


เซ็ตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้ตัวดำเนินการของเซ็ต (Set operators)ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้นสตริง (String) หรือ สตริงของอักขระ (Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริง มีการนําไปใช้สร้างโปรแกรมประเภทบรรณาธิการข้อความ(text editor) หรือโปรแกรมประเภทประมวลผลคํา (wordprocessing) ซึ่งมีการทํางานที่อํานวยความสะดวกหลายอย่าง เช่น การตรวจสอบข้อความ การจัดแนวข้อความในแต่ละย่อหน้าและการค้นหาคํา เป็นต้นสตริงกับอะเรย์สตริง คือ อะเรย์ของอักขระ เช่น char a[6]อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่นchar a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};char a[ ]=“HELLO”;

ความยาวของสตริง จะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่วยความจำให้กับ \0ด้วย เช่น“This is String !”
จะเป็นข้อมูลแบบสตริงยาว 16 อักขระ
การกำหนดสตริงการกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว(String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
การกำหนดค่าคงตัวสตริงสามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอกฟังก์ชัน ชื่อค่าคงตัวจะเป็นพอยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริงนั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่วยความจำที่เก็บตัวมันเองการกำหนดค่าให้กับสตริงนั้น เราจะใช้เครื่องหมาย double quote (“ ”) เช่น “abc” คือ ชุดของอักขระที่มีขนาด 4(รวม \0 ด้วย)

DTS03-01-07-2552

Data Structure

เรื่อง Set and String
Pointer ตัวแปร pointer เป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งที่อยู่ของตัวแปร
สามารถอ้างอิงกลับไปกลับมาได้ มีขนาด 2 ไบต์เท่ากันหมด ไม่ว่าจะเป็น
char,int,floatหรืออื่นๆในการประกาศตัวแปร pointer จะต้องนำหน้าด้วย
เครื่องหมาย * เช่น int*x เป็นตัวแปร pointer

เครื่องหมาย & เป็นเครื่องหมายที่บอกตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำ
ในกรณีที่ตัวแปรใดมีเครื่องหมาย & นำหน้าจะไม่สามารถนำมาคำนวณได้

ตัวอย่าง
int *ptr,count เป็นการประกาศตัวแปร ptr เป็นตัวแปร pointer
และประกาศตัวแปร count
count = 100 เป็นการกำหนดค่าให้กับ count มีค่าเท่ากับ 1
00ptr = &count เป็นการกำหนดค่าให้กับ ptr มีค่าเท่ากับตำแหน่งที่อยู่ของ count


ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่
คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่


Set
เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย
1.set intersection
2.set union
3.set difference


String
เป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกัน
ความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้น ต้องทำการจองเนื้อที่ให้กับ \0 ด้วย

DTS02-24-06-2552

สรุป
เรื่อง Array and Record

-การดําเนินการเกี่ยวข้องกับอะเรย์ 1 มิติ หลายมิติ
-การส่งค่าของอะเรย์ ในโปรแกรม และฟังก์ชัน
-การดําเนินการที่เกี่ยวข้องกับ เรคคอร์ด
-ความสัมพันธ์ระหว่าง เรคคอร์ด กับอะเรย์ และอะเรย์ชนิดโครงสร้าง

อะเรย์เป็นโครงสร้างข้อมูลที่เรียกว่า Linear List มีลักษณะคล้ายเซ็ตในคณิตศาสตร์ คือ อะเรย์จะประกอบด้วยสมาชิกที่มีจํานวนคงที่ มีรูปแบบข้อมูลเป็นแบบเดียวกัน สมาชิกแต่ละตัวใช้เนื้อที่จัดเก็บที่มีขนาดเท่ากัน เรียงต่อเนื่องในหน่วยความจําหลัก

การกำหนด Array

อะเรย์จะต้องกําหนดชื่ออะเรย์ พร้อม subscript ซึ่งเป็นตัวกําหนดขอบเขตของอะเรย์ มีได่มากกว่า 1 ตัว จํานวน subscript จะเป็น ตัวบอกมิติของอะเรย์นั้น อะเรย์ที่มี subscript มากกว่า 1 ตัวขึ้นไป จะเรียกว่า อะเรย์หลายมิติ การกําหนด subscript แต่ละตัวจะประกอบไปด้วย ค่าสูงสุดและ ค่าต่ําสุดของ subscript นั้น

ข้อกําหนดของการกําหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ

1.ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
2.ค่าต่ำสุด เรียกว่า ขอบเขตล่าง (lower bound)
3.ค่าสูงสุด เรียกว่า ขอบเขตบน (upper bound)

ขนาดของ index แต่ละตัว ของ Array หาได้จาก
(ขนาดของ subscript = upper bound – lower bound + 1)
จํานวนสมาชิกหรือขนาดของอะเรย์ n มิติ หาได้จาก
(ขนาดของอะเรย์ = ผลคูณของขนาดของsubscript แต่ละตัว)

อะเรย์ 1 มิติ
อะเรย์ 2 มิติ

รูปแบบของอะเรย์ 1มิติ
data-type array-name[expression]

data-type คือ ประเภทของข้อมูลอะเรย์ เช่น inchar float
array-name คือ ชื่อของอะเรย์
expression คือ นิพจน์จำนวนเต็มซึ่งระบุจำนวนสมาชิกของอะเรย์

ตัวอย่าง char a[4]; int num[10];

การประกาศอาร์กิวเมนต์ในฟังก์ชันเป็นอะเรย์

1. มีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

2. ไม่ต้องมีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

3. ตัวแปรที่ทำหน้าที่รับค่าถูกกำหนดเป็นพอยน์เตอร์

รูปแบบของอะเรย์ 2 มิติ

type array-name[n] [m];

type หมายถึง ชนิดของตัวแปรที่ต้องการประกาศเป็นอะเรย์

array-name หมายถึง ชื่อของตัวแปรที่ต้องการประกาศเป็นอะเรย์

n หมายถึง ตัวเลขที่แสดงตำแหน่งของแถว

m หมายถึง ตัวเลขที่แสดงตำแหน่งของคอลัมน์

ตัวอย่าง

หมายถึง คอมพิวเตอร์จะจองเนื้อที่ในหน่วยความจำ จำนวน 6 ที่สำหรับตัวแปร a กำหนดค่าเริ่มต้นได้หลายลักษณะ

ตัวอย่าง

กำหนดค่าเริ่มต้นให้ int a[2][3]

int a[2][3] = {1,2,3,4,5,6}; หรือ

int a[2][3] = {{1,2,3},{4,5,6}}; หรือ

int a[][3] = {{1,2,3},{4,5,6}};

Record or Structure

Structure คือ โครงสร้างที่สมาชิกแต่ละตัวมีประเภทข้อมูลแตกต่างกันได้ โดยที่ใน structure อาจมีสมาชิกเป็นจํานวนเต็ม ทศนิยม อักขระ อะเรย์หรือพอยเตอร์ หรือแม้แต่ structure ด้วยกันก็ได้

struct เป็นคําหลักที่ต้องมีเสมอ

struc-nameชื่อกลุ่ม structure

type ชนิดของตัวแปรที่อยู่ในกลุ่ม structure

name-n ชื่อของตัวแปรที่อยู่ในกลุ่ม structure

struc-variable ชื่อตัวแปรชนิดโครงสร้าง

คือ ตัวแปรที่มีโครงสร้าง เหมือนกับที่ประกาศไว้ในชื่อของกลุ่ม structure อาจมีหรือไม่มีก็ได้ถ้ามีมากกว่า 1 ชื่อ แยกกันด้วยเครื่องหมายคอมม่า (,)

การผ่าน structure ให้ฟังก์ชัน ประเภทของการส่งผ่าน structure ให้ฟังก์ชันนั้น มี่ 2 ประเภท คือ

1. ส่งสมาชิกแต่ละตัวของ structure
2. ส่งทั้ง structure

1. ส่งสมาชิกแต่ละตัวของ structureสมาชิกแต่ละตัวของ structure สามารถส่งเป็นอาร์กิวเมนต์ ของฟังก์ชันและส่งกลับจากฟังก์ชันได้โดยใช้ค่าส่ง return ซึ่งมีทั้งการส่งค่าของตัวแปรที่อยู่ในตัวแปรstructure และก็ส่งตำแหน่งที่อยู่ของตัวแปรนั้น ๆ ไปยังฟังก์ชัน

2. ส่งผ่านทั้ง structure ให้กับฟังก์ชันจะส่งผ่านในลักษณะของพอยน์เตอร์ไปยัง structure โดยหลักการจะเหมือนกับการส่งผ่านอะเรย์ไปให้ฟังก์ชัน ซึ่งเป็นลักษณะที่เรียกว่า Pass by reference

ส่งงาน

struct notebook
{

char brand[30];

char series[20];

int price;

char cpu[30];

char ram[30];

float lcd;

int hdd;

char cd[10];

}product={"Acer","4935G-742G32Mn/C011",27900, "CORE 2 Duo 2.13 GHz.","2048/667",14.1,320,"DVD-RW"};

จากด้านบนกำหนดให้ notebook เป็นชื่อ structureโดยมีตัวแปร char brand[30] , char series[20] , int price , char cpu[30] , char ram[30] , float lcd , int hdd , char cd[10] โดยมี product เป็นตัวแปรชนิดโครงสร้างข้อมูล ชนิดเดียวกับ notebook

brand[30] = Acer

series[20] = 4935G-742G32Mn/C011

price = 27900

cpu[30] = CORE 2 Duo 2.13 GHz .

ram[30] = 2048/667

lcd = 14.1

hdd = 320

cd[10] = DVD-RW

ประวัติ

นาวสาว ขนิษฐา คล้ายมณี รหัส 50172792026 Miss Khanitta Klaimanee หลักสูตร บริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัการ หมาวิทยาลัยราชภัฏสวนดุสิต Email: u50172792026@gmail.com