28 กรกฎาคม 2552

DTS_ 05 22/07/2552

สรุป Linked List

กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน ต่อ
5. กระบวนงาน Traverse หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูล นำเข้าลิสต ผลลัพธ์ ขึ้นกับการประมวลผล เช่นเปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์, คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Nodeหน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น Empty List หน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่างเป็นเท็จ ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น fullest หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามารถมีโนดอื่น
9. ฟังก์ชั่น list countหน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy list หน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์

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

การดำเนินงานพื้นฐานของสแตก
การทำงานสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการ คือ
1. Push คือ การนำข้อมูลใส่ในสแตก และสามารถตรวจสอบว่าสแตกเต็มหรือไม่ ถ้าไม่เต็มสามารถเพิ่มข้อมูลลงไปได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่สแตกว่าง ถ้าเต็ม (Stack Overflow) ก็ไม่สามารถเพิ่มข้อมูลได้
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก ถ้ามีข้อมูลออกจากสแตกเพียงหนึ่งตัว จะเกิดสภาวะว่าง (Stack Empty) คือการไม่มีข้อมูลในสแตก ถ้าไม่มีข้อมูลในสแตก แล้วทำการ Pop จำทำให้เกิดความผิดพราดที่เรียกว่า Stack Underflow ดังนั้นก่อนการนำข้อมูลออกจากสแตกต้องทำการตรวจสอบก่อนว่าว่างหรือเปล่า จึงจะนำข้อมูลออกได้ และปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งข้อมูลที่ต่อจากข้อมูลที่ถูกนำออกไป
3. Stack Top คือ การคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำข้อมูลออกจากสแตก

การบ้าน
ยกตัวอย่างในการใช้ชีวิตประจำวันเกี่ยวกับ Stack


1. ตั๋วรถประจำทางที่พนักงานรถประจำทางขายให้กับผู้โดยสารที่ใช้บริการ ที่จะต้องดึงจากด้านนอกจนกว่าจะถึงด้านในสุด โดยไม่มีการถึงจากด้านในมาใช้ก่อนทั้งที่ด้านในเป็นสิ่งที่ต้องม้วนเข้าไปก่อน
2. แก้วน้ำที่ไว้ขายกาแฟโบราณหรือในร้านเซเว่น จะมีการเรียงจากด้านล่างขึ้นด้านบน และมีการหยิบใช้โดยหยิบจากด้านบนใช้ก่อนด้านล่าง
3. กระดาษที่ใช้ใส่ในเครื่องถ่ายเอกสารหรือเครื่องprint จะต้องเป็นกระดาษแผ่นบนที่ถูกใช้กอ่นและกระดาษแผ่นที่วางก่อนจถูกให้เป็นแผ่นสุดท้ายเสมอ

22 กรกฎาคม 2552

DTS_04 15/07/2552

เรื่อง Linked List

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

โครงสร้างข้อมูลแบบลิงค์ลิสต์

โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure
2. Data Node Structure

กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน

1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่าง ผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Node หน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูลนำเข้า ลิสต์ ข้อมูล และตำแหน่ง ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Node หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูล นำเข้า ข้อมูลและตำแหน่งผลลัพธ์ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search list หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการ ข้อมูลนำเข้าลิสต์ ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่ พบข้อมูล


การบ้าน

เขียนโปรแกรมเปรียบเทียบการใช้ฟังก์ชั่น Stdio.h กับ iostream.h แต่ผลลัพธ์ออกมาต้องเหมือนกัน

#include

main()
{
char name[30];
char surname[40];
int high;
char sex[10];
printf("Name :");
scanf("%s",&name);
printf("Surame :");
scanf("%s",&surname);
printf("High :");
scanf("%d",&high);
printf("Sex :");
scanf("%s",&sex);
if(sex=="male")
{
printf("Name : %s\n",name);
printf("Surname : %s\n",surname);
printf("High : %d\n",high-100);
printf("Sex : %s\n",sex);
}
else {
printf("Name : %s\n",name);
printf("Surname : %s\n",surname);
printf("High : %d\n",high-110);
printf("Sex : %s\n",sex);
return 0;
}
}


#include
main()
{
char name[30];
char surname[40];
int high;
char sex[10];
cout<<"Name :"; cin>>name;
cout<<"Surame:"; cin>>surname;
cout<<"High :"; cin>>high;
cout<<"Sex :"; cin>>sex;
if(sex=="male")
{
cout<<"Name : "<



14 กรกฎาคม 2552

DTS_ 03 01/07/2552

สรุปเนื้อหาบทเรียน

เรื่อง Pointer และ Set and String

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

ตัวอย่าง

int *ptr,count // เป็นการประกาศตัวแปร ptr เป็นตัวแปร pointer และประกาศตัวแปร count
count = 300 // เป็นการกำหนดค่าให้กับ count มีค่าเท่ากับ 300
ptr = &count // เป็นการกำหนดค่าให้กับ ptr มีค่าเท่ากับตำแหน่งที่อยู่ของ count
** ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่
คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่ Set เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย

1. set intersection

2. set union

3. set difference

Set and String

โครงสร้างข้อมูลแบบเซตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน Set and Stringโครงสร้างข้อมูลแบบเซตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้

โครงสร้างข้อมูลแบบสตริง

สตริงเป็นโครงสร้างข้อมูลที่เป็นการรวบรวมโครงสร้างข้อมูลคาร์แรคเตอร์ (Character)ซึ่งเป็นตัวอักษรและสัญลักษณ์ (Symbol) ต่าง ๆ เป็นชนิดข้อมูลที่ถูกใช้งานมากชนิดหนึ่ง ภาษาเขียนโปรแกรมหลายภาษาจะกำหนดให้มาใช้งานได้ทันที