(sorting)

DTS-10
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของ หรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพเช่น การค้นหาคำตามตัว อักษรไว้อย่างมีระบบและเป็นระเบียบ หรือการค้นหาหมายเลขโทรศัพท์ในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของเจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลข โทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ววิธีการเรียงลำดับสามารถแบ่งออกเป็น2 ประเภท คือ(1) การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลักเวลาที่ใช้ ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายใน ความจำหลัก

กราฟ (Graph)

DTS-09
เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น นิยามของกราฟกราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ (1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes) (2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุดกราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น(Source Node) และ โหนดสิ้นสุด (Target Node)

(Queue) คิว

DTS-08
ประโยชน์ที่ได้รับจากการเเรียนวิชาโครงสร้างข้อมูลครั้งที่ 7 1.ได้ความรู้พื้นฐานเกี่ยวกับโครงสร้างข้อมูลเรื่องคิว(Queue)อันได้แก่ ลักษณะการทำงานของคิวโดยคิวเป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่มเข้าของข้อมูลจะกระทำที่ปลายข้างหนึ่งโดยเรีัยกส่่วนท้ายว่าเรียร์(rear) และการนำออกข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเราเรียกว่าส่วนหน้าหรือฟรอนต์(front) ลักษณะการทำงานของคิวเป็นลักษณะการเข้าก่อนออกก่อนหรือที่เราเรียกว่า FIFO(First In First Out)2.ได้ความรู้เกี่ยวกับการดำเนินการเกี่ยวกับคิว(Queue)อันได้แก่ Create Queue คือการสร้างคิวดดยกำหนดหน่วยความจำแก่คิว Enqueue คือการเพิ่มข้อมูลลงไปในคิวDequeue คือการนำข้อมูลออกมาจากคิว Queue Front คือการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง Queue Rear คือการนำข้อมูลที่อยู่ในส่วนท้ายของคิวมาแสดงEmpty Queue คือการตรวจสอบคิวว่าคิวมีความจำว่างหรือไม่Full Queue คือการตรวจสอบคิวว่าคิวมีความจำเต็มหรือไม่Queue Count คือการนับจำนวนสมาชิกที่อยู่ในคิว Destroy Queue คือการลบข้อมูลทั้งหมดที่อยู่ในคิว3.มีความรู้ในการแก้ปัญหาของคิวโดยการสร้างคิวเป็นแบบวงกลม4.สามารถนำคิวที่ได้เรียนจากวิชาโครงสร้างข้อมูลครั้งที่ 7 นี้ไปประยกต์ให้เกิดประโยชน์ในด้านคอมพิวเตอร์

ทรี Tree

DTS-07
สรุปบทเรียน ทรีทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูลเช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆโครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนดเรียกโหนดดังกล่าวว่า โหนดแม่ (Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)นิยามของทรี1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่านัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

การแปลงนิพจน์ Inflix ให้เป็น Postfix

DTS - 06
เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปอร์เรเตอร์ซึ่งหมายความว่าโอเปอร์เรเตอร์ที่มาก่อนอาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็น LIFO List จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่างคือหนึ่งข้อมูลเข้ามาซึ่งเป็นนิพจน์ infix สองข้อมูลออกหรือผลลัพธ์คือนิพจน์ Postfix โดยอัลกอริทึมมีดังนี้ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ทำดังนี้1ถ้าสแตกยังว่างอยู่ในpush โอเปอร์เรเตอร์ลงสแตก ถ้าสแตกไม่ว่างให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก2.ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ pop สแตกไปเป็นผลลัพธ์และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท๊อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ทีเป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ ที่ท๊อปของสแตก หลังจากนั้นให้ push ข้อมูลลงสแตก ถ้าโอเปอร์เรเตอร์เข้ามีค่ามากกว่า โอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ push ลงสแตก3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก4.ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ pop สแตกจนกว่าจะถึงวงเล็บเปิดและนำผลที่ pop ออกไปเป็นผลลัพธ์ โดยทิ้งวงเล็บปิดและเปิดไป5. ถ้าข้อมูล หมด ให้ pop สแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง

สแตกในชีวิตประจำวัน

คุณสมบัติของ Stack ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน
ส่วนสแตกทำผมนำมายกตัวอย่าง นั้นคือ แก้วกาแฟเย็นในร้านสะดวกซื้อ หรือ 7-Eleven นั้นเอง
เพราะว่าเราจะใช้แก้วอันที่อยู่อันแรกนั้น เอามาใช้ใส่กาแฟก่อนนั้นเองซึ่งตรงกับเงื่อนไขของสแตก

Stack

DTS 05 25/07/2552
เรื่อง Stack
Stack สแตกคือโครงสร้างข้อมูลแบบลิเนียลลิสต์ ซึ่งความสามารถของมันคือการเพิ่มหรือลบข้อมูล
ในสแตก
ซึ่งการทำงานสแตกนั้นก้อจะประกอบไปด้วย
-Push คือการเอาข้อมูลที่ได้ใส่ลงไปในสแตก
-Pop คือการนำข้อมูลออกจากตัวส่วนบนของสแตก
ถ้าตัวสแตกนั้นไม่มีสมาชิกแล้วเกิดทำการPopสแตก จะทำให้เกิดความผิดพลาดหรือที่เรียกว่า
Stack Underflow
การดำเนินงานที่เกี่ยวข้องกับสแตก
-Create Stack
-Push Stack
-Pop Stack
-Stack Top
-Empty Stack
-Full Stack
-Stack Count
-Destroy Stack

DTS 04 -22/07/52
โครงสร้างข้อมูลแบบลิงค์ลิสต์
Linked List คือวิธีการเก็บข้อมูลแบบต่อเนื่องในอิลิเมนต์ต่างๆโดยมีPointerเป็นตัวเชื่อม
โดยตัวอิลิเมนต์นั้นเป็นสมาชิก แล้วโนด(Node)เป็นซับเซ็ตของยูเนี่ยนซึ่งในโนดจะมีตัว2ส่วนคือ
1.Data เป็นข้อในตัวอิลิเมนต์
2.Link Field จะเป็นตัวเก็บตำแหน่งของโนดในลิสต์
ซึ่งในลิงค์ลิสต์ จะมีตัวแปรไว้คอยชี้ตำแหน่งลิสต์ โนดแรกตัวแรกของลิสต์นั้น ถ้าในลิสต์ไม่มีข้อมูล
ข้อมูลในลิสต์ก้อจะเป็นNullทันที
กระบวนงานของลิงค์ลิสต์ประกอบด้วย
-Insert Node
-Delete Node
-Search List
-Traverse
-ReTrieve Node (การเรียกคืน)
-Empty List
-FullList
-List Count
-Destroy List

DTS 03 01/07/2552
ในการเรียนเรื่อง structure
structure คือ สมาชิกของข้อมูลที่มีความแตกต่าง
ในทางด้านของข้อมูล
และpointer คือ ตัวแปรที่มีหน้าที่เก็บข้อมูลตำแหน่งที่อยู่หรือว่า(Address)
ที่ประกาศชนิดตัวแปรpointer
โครงสร้างข้อมูลแบบเซ็ตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันในภาษาซี จะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาลแต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
แบบฝึกหัดบทที่2

1.ให้นักศึกษากำหนดค่าของ Array1มิติ และ 2มิติ
ตอบ char ch[5];
#include "stdio.h"
#include "conio.h"
main()
{
int a[3];
clrscr();
a[0] = 1;
a[1] = 5;
a[2] = 2;
printf("a[0] = %d\n",a[0]);
printf("a[1] = %d\n",a[1]);
printf("a[2] = %d\n",a[2]);
}
อะเรย์2
student[5][4]; #include "stdio.h"
#include "stdlib.h"
#include "conio.h"
main()
{
char student[4];
int num_student[5][4],i,j;
char fac[20];
clrscr();
for(i=0;i<=4;++i) { printf("Faculty : "); gets(fac); for(j=0;j<=3;++j) { printf("student[%d][%d] = ",i,j); gets(student); num_student[i][j] = atoi(student); } } }

2.ให้นักศึกษาหาค่าของ A[2],A[6]จากค่าA={2,8,16,24,9,7,3,8}
ตอบ #include"stdio.h"
main()
{
int a[]={2,8,16,24,9,7,3,8};
printf("%d\n",a[2]);
printf("%d\n",a[6]);
}

3.จากค่าของint a [2][3] = {{6,5,4},{3,2,1}};ให้นักศึกษาหาค่าของa[1][0]และa[0][2]
ตอบ#include"stdio.h"
main()
{
int a[2][3] = {{6,5,4},{3,2,1}};
printf("%d\n",a[1][0]);
printf("%d\n",a[0][2]);
}

4.ให้นักศึกษากำหนด Structure ที่มีค่าของข้อมูลจากน้อย 6 Records
ตอบ #include "stdio.h"
struct date
{
int day;
int month;
int year;
}
days;
struct mobile
{
char brand[20];
char modle[20];
char color[10];
int item;
float price;
}phone;
void main(){
printf("Welcome to Atomtelephone\n");
printf("day:");scanf("%d",&days.day );
printf("month:");
scanf("%d",&days.month);
printf("year:");
scanf("%d",&days.year);
printf("Mobile brand:");
scanf("%s",&phone.brand);
printf("Modle is:");
scanf("%s",&phone.modle);
printf("color:");
scanf("%s",&phone.color);
printf("item:");
scanf("%s",&phone.item);
printf("price :");
scanf("%f",&phone.price);
{
printf("Date:%d/%d/%d\n",days.day,days.month,days.year);
printf("Mobile brand: %s\n",phone.brand);
printf("Phone modle: %s\n",phone.modle);
printf("Color: %s\n",phone.color);
printf("Buy: %s Item",phone.item);
printf("Price: %f",phone.price);
}
}

5.ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวชนิด ArrayกับตัวแปรPointerในสภาพของการกำหนดที่อยู่ของข้อมูล
ตอบ อาร์เรย์ (Array) คือ ชุดหรือกลุ่มของข้อมูลที่เก็บอยู่ที่เดียวกัน ภายใต้ชื่อตัวแปรหนึ่งๆ โดยทั่วไปเราอาจเรียกว่า ชุดข้อมูล ซึ่งหลักสำคัญ คือ ถ้าเป็นตัวแปรธรรมดา ตัวแปร 1 ตัวจะสามารถเก็บค่าได้หนึ่งค่า หากเป็นตัวแปรแบบ Array ตัวแปรหนึ่งตัวจะสามารถเก็บค่าได้มากกว่า 1 ค่า
แต่ในส่วนของพอยน์เตอร์ (pointer)พอยน์เตอร์เป็นตัวแปรที่ใช้เก็บตำแหน่งของข้อมูลเช่น ตัวแปรหรือสมาชิกของอะเรย์ เราใช้พอยเตอร์บ่อย ๆ ใน ภาษาซีเนื่องจากมันมีประโยชน์ มากมาย

ทำ Structure เกี่ยวกับการซื้อโทรศัพท์
#include "stdio.h"
struct date
{int day;
int month;
int year;
}days;struct mobile
{
char brand[20];
char modle[20];
char color[10];
int item;
float price;
}phone;
void main()
{
printf("Wellcome to Atomtelephone\n");
printf("day:");scanf("%d",&days.day );
printf("month:");scanf("%d",&days.month);
printf("year:");
scanf("%d",&days.year);
printf("Mobile brand:");
scanf("%s",&phone.brand);
printf("Modle is:");
scanf("%s",&phone.modle);
printf("color:");
scanf("%s",&phone.color);
printf("item:");
scanf("%s",&phone.item);
printf("price :");
scanf("%f",&phone.price);
{printf("Date:%d/%d/%d\n",days.day,days.month,days.year);
printf("Mobile brand: %s\n",phone.brand);
printf("Phone modle: %s\n",phone.modle);
printf("Color: %s\n",phone.color);printf("Buy: %s Item",phone.item);
printf("Price: %f",phone.price);
}
}

สรุปการเรียน Lecture2 Array and Record

1 ได้รู้จักประเภทและการดำเนินการของ อะเรย์

2อะเรย์นั้นมี2ประเภทคือ

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

2.2อะเรย์หลายมิติ

3เพื่อให้ทราบความสัมพันธ์ของเรคคอร์ดกับอะเรย์

4 ได้รู้จักการกำหนดอะเรย์ และ subscript

5 การได้รู้จักโครงสร้างหรือ Structure

6 รู้จักการการทำงานและหน้าที่ของ pointer