สารบัญ

1     บทนำ                                                                                                         1

การจัดเก็บและจัดการข้อมูล.............................................................................................................. 1

ปริศนา 15.......................................................................................................................................... 2

การสร้างเขาวงกต.............................................................................................................................. 7

กลุ่มเซตไร้ตัวร่วม....................................................................................................................... 8

สรุป................................................................................................................................................. 16

แบบฝึกหัด....................................................................................................................................... 17

2     การเก็บข้อมูลด้วยแถวลำดับ                                                              19

อินเทอร์เฟซ Collection................................................................................................................. 19

คลาส ArrayCollection.................................................................................................................. 22

แถวลำดับขยายขนาดได้.................................................................................................................. 25

ArrayCollection แบบไม่จำขนาด................................................................................................. 28

คอลเล็กชันเก็บได้แต่อ็อบเจกต์....................................................................................................... 30

บริการอื่นๆ...................................................................................................................................... 31

String toString( )..................................................................................................................... 32

Object[ ] toArray( )................................................................................................................ 33

boolean equals(Object x)...................................................................................................... 34

แบบฝึกหัด....................................................................................................................................... 36

3     การวิเคราะห์เชิงเส้นกำกับ                                                                   39

เวลาการทำงาน................................................................................................................................ 39

คำสั่งพื้นฐาน................................................................................................................................... 40

การนับจำนวนคำสั่งที่ถูกใช้งาน...................................................................................................... 40

สัญกรณ์เชิงเส้นกำกับ..................................................................................................................... 42

โอเล็ก........................................................................................................................................ 43

โอเมกาเล็ก................................................................................................................................ 43

ทีตาใหญ่................................................................................................................................... 44

โอใหญ่...................................................................................................................................... 44

โอเมกาใหญ่.............................................................................................................................. 45

การวิเคราะห์เชิงเส้นกำกับ.............................................................................................................. 47

แบบฝึกหัด....................................................................................................................................... 51

4     การเก็บข้อมูลแบบโยง                                                                          55

การโยงข้อมูล.................................................................................................................................. 55

ปมข้อมูล......................................................................................................................................... 56

คลาส LinkedCollection................................................................................................................. 57

LinkedCollection แบบมีปมหัว..................................................................................................... 62

ประสิทธิภาพการทำงาน.................................................................................................................. 64

แบบฝึกหัด....................................................................................................................................... 64

5     รายการ                                                                                                    69

อินเทอร์เฟซ List............................................................................................................................ 69

การสร้างรายการด้วยแถวลำดับ........................................................................................................ 71

boolean equals(Object x)...................................................................................................... 73

ประสิทธิภาพการทำงาน........................................................................................................... 74

การสร้างรายการโยง........................................................................................................................ 75

รายการโยงเดี่ยวแบบไม่วนที่มีปมหัว....................................................................................... 76

รายการโยงคู่แบบวนที่มีปมหัว................................................................................................. 79

ตัวอย่างการใช้งานรายการ............................................................................................................... 84

รายการที่ปรับตัวเอง.................................................................................................................. 84

ฟังก์ชันพหุนามตัวแปรเดียว..................................................................................................... 85

เวกเตอร์มากเลขศูนย์................................................................................................................ 89

เมทริกซ์มากเลขศูนย์................................................................................................................ 94

แบบฝึกหัด....................................................................................................................................... 97

6     กองซ้อน                                                                                               101

ข้อกำหนดของกองซ้อน................................................................................................................ 101

การสร้างกองซ้อนด้วยรายการ....................................................................................................... 102

การสร้างกองซ้อนด้วยแถวลำดับ................................................................................................... 103

ตัวอย่างการใช้งานกองซ้อน.......................................................................................................... 104

การตรวจสอบการใส่วงเล็บ..................................................................................................... 104

กองซ้อนภายในเครื่องเสมือนจาวา........................................................................................ 106

นิพจน์เติมหลัง....................................................................................................................... 109

แบบฝึกหัด..................................................................................................................................... 115

7     แถวคอย                                                                                                117

ข้อกำหนดของแถวคอย................................................................................................................. 117

การสร้างแถวคอยด้วยรายการ........................................................................................................ 118

การสร้างแถวคอยด้วยแถวลำดับวงวน........................................................................................... 119

ตัวอย่างการใช้งานแถวคอย........................................................................................................... 122

แถวคอยให้หยุดรอ ................................................................................................................. 123

การเรียงลำดับข้อมูลแบบฐาน................................................................................................. 124

การค้นตามแนวกว้าง............................................................................................................... 127

การหาวิถีสั้นสุดในตาราง........................................................................................................ 128

ปริศนาคูณสามหารสอง.......................................................................................................... 130

แบบฝึกหัด..................................................................................................................................... 133

8     แถวคอยบุริมภาพ                                                                               135

ข้อกำหนดของแถวคอยบุริมภาพ.................................................................................................. 135

การสร้างด้วยรายการ...................................................................................................................... 137

การสร้างด้วยฮีปแบบทวิภาค.......................................................................................................... 139

การแทนฮีปแบบทวิภาคด้วยแถวลำดับ.................................................................................... 139

void enqueue(Object e)....................................................................................................... 140

Object dequeue().................................................................................................................. 141

การสร้างฮีปจากข้อมูลในแถวลำดับ........................................................................................ 143

ฮีปมากสุดและฮีปน้อยสุด............................................................................................................. 145

ตัวอย่างการใช้งานแถวคอยบุริมภาพ............................................................................................. 146

การเรียงลำดับแบบฮีป............................................................................................................. 147

การเลือกข้อมูลตามอันดับ....................................................................................................... 148

การค้นตามต้นทุนน้อยสุด....................................................................................................... 150

ตัวจำลองวงจรตรรก................................................................................................................ 154

แบบฝึกหัด..................................................................................................................................... 163

9     ต้นไม้แบบทวิภาค                                                                               165

การสร้างต้นไม้.............................................................................................................................. 165

ต้นไม้นิพจน์................................................................................................................................. 169

บริการพื้นฐานของต้นไม้.............................................................................................................. 171

โครงสร้างเวียนเกิดของต้นไม้แบบทวิภาค............................................................................. 172

int numNodes(Node r)......................................................................................................... 173

int height(Node r)................................................................................................................. 173

int numLeaves(Node r)........................................................................................................ 174

Node copy(Node r).............................................................................................................. 174

Object[ ] toArray()............................................................................................................... 175

การแวะผ่านต้นไม้.................................................................................................................. 177

การวาดรูปต้นไม้..................................................................................................................... 182

รหัสฮัฟฟ์แมน............................................................................................................................... 186

การหาอนุพันธ์ด้วยต้นไม้นิพจน์.................................................................................................. 189

การลดรูปต้นไม้นิพจน์.................................................................................................................. 192

แบบฝึกหัด..................................................................................................................................... 194

10   ต้นไม้ค้นหาแบบทวิภาค                                                                    197

ลักษณะของต้นไม้ค้นหาแบบทวิภาค........................................................................................... 197

การค้นหาข้อมูล............................................................................................................................. 200

การค้นหาข้อมูลน้อยสุดและมากสุด............................................................................................. 203

การเพิ่มข้อมูล................................................................................................................................ 204

การลบข้อมูล.................................................................................................................................. 208

ความลึกเฉลี่ยของปม.................................................................................................................... 211

การเรียงลำดับแบบต้นไม้.............................................................................................................. 215

การสร้างเซต คอลเล็กชัน และแมป............................................................................................... 216

การสร้างเซตด้วยต้นไม้ค้นหาแบบทวิภาค.............................................................................. 216

การสร้างคอลเล็กชันด้วยต้นไม้ค้นหาแบบทวิภาค.................................................................. 217

การสร้างแมปด้วยต้นไม้ค้นหาแบบทวิภาค............................................................................ 218

ต้นไม้เอวีแอล................................................................................................................................ 222

การหมุนลูก............................................................................................................................. 224

โครงสร้างปมของต้นไม้เอวีแอล............................................................................................ 225

การเพิ่มและลบข้อมูล............................................................................................................. 226

การปรับต้นไม้ให้ถูกกฎ.......................................................................................................... 226

ต้นไม้ค้นหาแบบอื่น ๆ.................................................................................................................. 231

ต้นไม้บาน............................................................................................................................... 232

ต้นไม้ได้ดุล 2-3-4................................................................................................................... 235

ต้นไม้แดงดำ........................................................................................................................... 237

ต้นไม้ทรีป............................................................................................................................... 239

รายการก้าวกระโดด................................................................................................................. 240

แบบฝึกหัด..................................................................................................................................... 243

11   ตารางแฮช                                                                                            247

ตารางเก็บข้อมูล............................................................................................................................. 247

ตารางแฮชแบบแยกกันโยง............................................................................................................ 251

ฟังก์ชันแฮช................................................................................................................................... 254

การแปลงคีย์ให้เป็นจำนวนเต็ม.............................................................................................. 255

กลวิธีการเขียนฟังก์ชันแฮช.................................................................................................... 257

ปฏิทรรศน์วันเกิด.......................................................................................................................... 260

ตารางแฮชแบบกำหนดเลขที่อยู่เปิด.............................................................................................. 261

การตรวจเชิงเส้น..................................................................................................................... 262

การตรวจกำลังสอง.................................................................................................................. 267

การแฮชสองชั้น....................................................................................................................... 272

ประสิทธิภาพของการแฮชเอกรูป............................................................................................ 273

การเลือกใช้ตารางแฮช................................................................................................................... 276

ข้อควรระวัง................................................................................................................................... 278

แบบฝึกหัด..................................................................................................................................... 279

12   ตัวแจงย้ำ                                                                                              283

การใช้งาน...................................................................................................................................... 283

ตัวแจงย้ำสำหรับการเก็บข้อมูลในแถวลำดับ................................................................................. 286

ตัวแจงย้ำสำหรับรายการโยง......................................................................................................... 290

ตัวแจงย้ำสำหรับตารางแฮช........................................................................................................... 291

ตัวแจงย้ำสำหรับต้นไม้แบบทวิภาค.............................................................................................. 292

ตัวแจงย้ำสำหรับต้นไม้ค้นหาแบบทวิภาค.................................................................................... 295

ตัวแจงย้ำแบบขัดข้องอย่างเร็ว...................................................................................................... 296

แบบฝึกหัด..................................................................................................................................... 299

13   การเรียงลำดับข้อมูล                                                                          301

ข้อกำหนด..................................................................................................................................... 301

การเรียงลำดับแบบเลือก................................................................................................................ 303

การเรียงลำดับแบบฟอง................................................................................................................. 305

การเรียงลำดับแบบแทรก............................................................................................................... 307

การเรียงลำดับแบบเชลล์................................................................................................................ 310

การเรียงลำดับแบบผสาน............................................................................................................... 314

การเรียงลำดับแบบฮีป................................................................................................................... 318

การเรียงลำดับแบบเร็ว................................................................................................................... 320

การเปรียบเทียบวิธีเรียงลำดับแบบต่าง ๆ...................................................................................... 329

ขอบเขตล่างของเวลาการเรียงลำดับ.............................................................................................. 330

แบบฝึกหัด..................................................................................................................................... 332

บรรณานุกรม                                                                                               337

ดัชนี                                                                                                              339