โครงสร้างข้อมูล/ทบทวนการเขียนโปรแกรมภาษาซี
ในบทนี้เราจะทบทวนการเขียนโปรแกรมภาษาซีเบื้องต้น โดยจะกล่าวถึงการเขียนคำสั่งเงื่อนไข คำสั่งวนรอบ อาร์เรย์เบื้องต้น รวมถึงหลักการเขียนโปรแกรมทั่วไป โดยจะใช้ตัวอย่างเป็นโปรแกรมคำนวณนิพจน์แบบโพสต์ฟิกซ์ การกล่าวถึงการเขียนโปรแกรมภาษาซีในบทนี้ไม่ได้มีเป้าหมายที่จะอธิบายเนื้อหาให้ครอบคลุมทั้งหมด
ประโยคสัญลักษณ์แบบโพสต์ฟิกซ์[แก้ไข | แก้ไขต้นฉบับ]
เมื่อเราต้องการจะทราบว่า มีค่าเท่าใด สิ่งที่เราทำก็คือการตีความประโยคสัญลักษณ์นี้. เราเริ่มจากการคำนวณจากวงเล็บที่อยู่ด้านในสุด และค่อยๆ ไล่ออกมา. เราทราบว่าเครื่องหมาย และ มีความสำคัญมากกว่าเครื่องหมาย และ ดังนั้นเราจึงประมวลผลพวกมันก่อน. สุดท้ายเราก็ได้ผลลัพธ์ออกมา. ประโยคสัญลักษณ์ข้างต้นนี้เป็นการเขียนระบุลำดับการประมวลผลแบบหนึ่ง ที่เราเรียกว่า infix notation. ความหมายที่มันแสดงสามารถเขียนออกมาได้อีกหลายแบบ ตัวอย่างเช่น เราอาจจะเขียนโดยใช้ต้นไม้:
ในบทนี้เราจะพิจารณาการเขียนประโยคสัญลักษณ์ในอีกรูปแบบหนึ่ง ที่เขียนในรูปของข้อความได้ง่าย และยังสามารถตีความได้ง่ายอีกด้วย. จากประโยคสัญลักษณ์ข้างต้นเราเขียนใหม่ได้เป็น
2 3 x 5 6 7 3 4 - x + / +
เราเรียกวิธีการเขียนแบบนี้ว่า ประโยคสัญลักษณ์แบบ postfix. (เครื่องคิดเลขของบริษัท Texas Instruments เมื่อก่อนก็ใช้วิธีการเขียนแบบนี้. มันเป็นการเขียนประโยคที่ซับซ้อนโดยไม่ต้องใช้วงเล็บ) ในการตีความประโยคสัญลักษณ์นี้ เราจะแยกกลุ่มของ ``คำ ออกเป็นสองแบบ คือ กลุ่มของเครื่องหมาย (บางคนเรียกว่า ตัวดำเนินการ หรือ operator) และกลุ่มของตัวเลข (บางคนเรียกว่า ผู้ถูกดำเนินการ หรือ operand). เราจะอ่านประโยคนี้จากซ้ายไปขวา เมื่อเราเจอเครื่องหมายเราจะดึงเอาตัวเลขสองตัวก่อนหน้าในข้อความออกมา และประมวลผลตามเครื่องหมายนั้น. จากนั้นเราจะเขียนผลลัพธ์ลงไปในตำแหน่งเดิมนั้น และอ่านข้อความต่อไป.
ในตัวอย่างข้างต้นเราจะเขียนลำดับการทำงานในตอนต้นได้ดังนี้.
[2] 3 x 5 6 7 3 4 - x + / + 2 [3] x 5 6 7 3 4 - x + / + [2 3 x] 5 6 7 3 4 - x + / + พบเครื่องหมาย --> <6> 5 6 7 3 4 - x + / + คำนวณ 2 x 3 แล้วเขียนทับ 6 [5] 6 7 3 4 - x + / + 6 5 [6] 7 3 4 - x + / + 6 5 6 [7] 3 4 - x + / + 6 5 6 7 [3] 4 - x + / + 6 5 6 7 3 [4] - x + / + 6 5 6 7 [3 4 -] x + / + พบเครื่องหมาย --> 6 5 6 7 <-1> x + / + คำนวณ 3 - 4 แล้วเขียนทับ 6 5 6 [7 -1 x] + / + พบเครื่องหมาย --> 6 5 6 -7 + / + คำนวณ 7 x -1 แล้วเขียนทับ 6 5 [6 -7 +] / + ...
เราจะเขียนโปรแกรมเพื่อคำนวณค่าของประโยคสัญลักษณ์แบบ postfix. ก่อนที่จะเขียนนั้น เราจะทวนสิ่งที่โปรแกรมจะต้องทำเสียก่อน. สังเกตว่าโปรแกรมจะพิจารณาลำดับของตัวเลข แต่จะไม่ทำอะไรจนกว่าจะพบเครื่องหมาย. เมื่อพบเครื่องหมายแล้ว โปรแกรมจะดึงตัวเลข หลังสุด ขึ้นมาสองจำนวน ประมวลเครื่องหมายและวางผลลัพธ์คืนต่อท้ายลำดับของตัวเลข (ที่ดึงค่าปลายสุดสองจำนวนออกไปแล้ว).
หลายครั้งที่การออกแบบโครงสร้างข้อมูล คือการออกแบบโปรแกรมทั้งหมด. รูปแบบของข้อมูลที่เราเก็บก็คือลำดับของตัวเลข ที่เราสามารถอ้างถึงตัวเลขสองตัวสุดท้้ายได้ และสามารถนำผลลัพธ์วางลงไปต่อท้ายลำดับได้.
วิธีหนึ่งที่เราจะเก็บข้อมูลที่เป็นลำดับก็คือการใช้อาร์เรย์ (array).
อาร์เรย์[แก้ไข | แก้ไขต้นฉบับ]
อาร์เรย์คือการประกาศชุดของข้อมูลแบบหนึ่งหลายๆ ตัว โดยที่ข้อมูลย่อยแต่ละตัวจะถูกเรียกได้โดยการระบุหมายเลข. ในภาษาซีีเราประกาศอาร์เรย์โดยใช้รูปแบบดังนี้.
ชนิดของข้อมูล ชื่อตัวแปร[ขนาดของอาร์เรย์];
ตัวอย่างเช่น
int a[100];
เป็นการประการอาร์เรย์ของเลขจำนวนเต็มจำนวน 100 ช่อง. ข้อมูลตัวแรกจะอยู่ที่ช่องหมายเลข 0. และในกรณีนี้ข้อมูลสุดท้ายจะอยู่ที่ช่องที่ 99. หลังจากนั้นเราเรียกใช้ข้อมูลย่อยในอาร์เรย์โดยการระบุหมายเลขในลักษณะ
ชื่อตัวแปร[หมายเลข]
ตัวอย่างเช่น a[10] หรือ a[i] เป็นต้น.
เราจะใช้อาร์เรย์ในการเก็บลำดับของตัวเลข. สังเกตว่าความยาวของลำดับของตัวเลขนั้นเปลี่ยนแปลงไปมา. สิ่งที่เราต้องการก็คือความยาวของลำดับขณะในขณะนั้น. เมื่อเราเพิ่มข้อมูลหรืออ่านข้อมูลสองตัวหลังไป เราก็จะเปลี่ยนแปลงค่าของความยาวนี้เพื่อรักษาความยาวของลำดับตัวเลขให้ถูกต้อง.
ดังนั้น เราสามารถประกาศตัวแปรต่างๆ ที่เราจะใช้ในการเก็บลำดับได้ดังนี้.
int list[100]; int listlength = 0;
ค่าเริ่มต้นของ listlength ถูกกำหนดให้เป็น 0.
การเก็บค่า b เข้าต่อท้ายลำดับเราจะทำโดยคำสั่ง:
list[listlength] = b; listlength++;
ในภาษาซีการกำหนดค่าให้กับตัวแปรทำโดยใช้เครื่องหมาย = ซึ่งแตกต่างกับในภาษาปาสกาล. ส่วนเครื่องหมายสำหรับเปรียบเทียบว่าค่าสองค่าเท่ากันหรือไม่ ในภาษาซีเราจะใช้ ==. คำสั่ง listlength++ มีความหมายเช่นเดียวกับ listlength = listlength + 1 แต่การทำงานในหลายๆ กรณีจะมีประสิทธิภาพกว่า (ยิ่งไปกว่านั้น มันทำให้โปรแกรมที่เขียนนั้นกระชับยิ่งขึ้น).
เราจะอ้างค่าท้ายลำดับสองอันด้วย list[listlength-1] และ list[listlength-2].
ส่วนอ่านข้อมูล[แก้ไข | แก้ไขต้นฉบับ]
เมื่อเราได้โครงสร้างข้อมูลพื้นฐานของโปรแกรมแล้ว เราจะมาพิจารณาการอ่านข้อความที่เป็นประโยคสัญลักษณ์แบบ postfix. ตัวเลขที่เราจะใช้ในโปรแกรมนี้เราจะมองเป็นตัวเลขหลักเดียวทั้งหมด. ดังนั้น ถ้าโปรแกรมรับข้อมูลเป็น
321+*
โปรแกรมจะให้ผลลัพธ์เป็น 9.
ในภาษาซี เราจะมองข้อความเป็นอาร์เรย์ของตัวอักษร. เราจะเก็บข้อความในอาร์เรย์โดยเรามีข้อตกลงว่า เราจะเก็บอักษรลงในอาร์เรย์ไปเรื่อยๆ โดยที่จะจบข้อความด้วยตัวอักษรหมายเลข 0. (ตัวอักษรหมายเลข 0 ไม่ใช่ตัวอักษรแทนเลขศูนย์ ซึ่งในภาษาซีเราจะเขียนเป็น '0'.) เราสามารถประกาศตัวแปรที่เก็บข้อความที่มีความยาวไม่เกิน 99 ตัวอักษรได้ดังนี้
char line[100];
ตัวแปรประเภท char คือตัวแปรที่เก็บตัวอักษร. เราสามารถสั่งอ่านข้อความจากผู้ใช้เข้ามายังตัวแปร line ได้โดยใช้คำสั่ง
scanf("\%s",line);
ในการเรียกใช้คำสั่งนี้ เราต้องมีการประกาศมันเสียก่อน. เราจะเขียน
#include <stdio.h>
ที่หัวของโปรแกรม เพื่อให้คอมไพล์เลอร์อ่านการประกาศฟังก์ชั่นต่างๆ จากแฟ้มนี้. ฟังก์ชั่น scanf ก็ถูกประกาศในไฟล์นี้เช่นเดียวกัน.
การวนรอบ[แก้ไข | แก้ไขต้นฉบับ]
เมื่อเราได้ข้อมูลแบบข้อความเข้ามาแล้ว เราต้องการจะไล่พิจารณาตัวอักษรในข้อความนั้นทีละตัวจนจบ. เราต้องการรูปแบบการสั่งให้โปรแกรมทำงานซ้ำ ซึ่งในภาษาซีมีหลายรูปแบบ. ในที่นี้เรายกตัวอย่างแค่สองคำสั่งหลักเท่านั้น.
การทำซ้ำแบบ while[แก้ไข | แก้ไขต้นฉบับ]
การทำซ้ำแบบ while มีรูปแบบดังนี้
while(เงื่อนไข) คำสั่ง;
ลักษณะทั่วไปของคำสั่งทำซ้ำนี้คือ คำสั่งที่จะถูกทำซ้ำนั้นคือคำสั่งเดียวที่อยู่ถัดจากคำสั่ง while หรือคำสั่ง for เท่านั้น. ถ้าเราต้องการให้คำสั่งวนรอบนี้ครอบคลุมหลายๆ คำสั่ง เราจะทำได้โดยการจับคำสั่งหลายๆ อันให้กลายเป็น ชุดคำสั่ง ที่มีคุณสมบัติเหมือนเป็นคำสั่งเดียว ตัวอย่างเช่น:
while(เงื่อนไข) { คำสั่ง1; คำสั่ง2; คำสั่ง3; }
ในกรณีของเรา เราจะเขียนส่วนวนรอบหลักของโปรแกรมได้เป็น
i=0; while(line[i]!=0) { คำสั่ง; i++; }
การทำซ้ำแบบ for[แก้ไข | แก้ไขต้นฉบับ]
การทำซ้ำแบบ for มีรูปแบบของคำสั่งดังนี้
for( คำสั่งเริ่มต้น ; เงื่อนไข ; คำสั่งที่ทำก่อนจะเริ่มทำงานครั้งต่อไป ) คำสั่ง;
คำสั่ง for นี้ โดยทั่วไปเราจะใช้ในกรณีที่เราทราบจำนวนครั้งของการวนรอบ. เรารู้ว่าเราจะทำงานจำนวนเท่ากับความยาวของข้อความ. เรามีฟังก์ชั่น strlen จะคือค่าความยาวของข้อความที่เราป้อนไป. ในการจะใช่้ฟังก์ชั่นนี้ เราต้องประกาศ #include <string.h> ไว้ที่หัวของโปรแกรมด้วย. เราจะเขียนส่วนวนรอบหลักโดยใช้คำสั่ง for ได้เป็น
for(i=0; i<strlen(line); i++) คำสั่ง;
ในการทำงานนั้น ส่วนเงื่อนไขจะถูกตรวจสอบทุกครั้งก่อนจะมีการทำงานตาม คำสั่ง. เราไม่ควรจะต้องเรียกใช้ฟังก์ชั่น strlen ทุกครั้งที่มีการตรวจสอบ เนื่องจากฟังก์ชั่น strlen ทำงานโดยการไล่อ่านข้อความจากต้นจนจบ ซึ่งเป็นการเปลืองเวลาโดยใช่เหตุ. เราสามารถแก้โปรแกรมดังกล่าวได้โดยการเพิ่มตัวแปรอีกตัวที่เก็บค่าความยาวของข้อมูล. โปรแกรมที่ได้มีลักษณะดังนี้.
l = strlen(line); for(i=0; i<l; i++) คำสั่ง;
เงื่อนไข[แก้ไข | แก้ไขต้นฉบับ]
ในการประมวลผลข้อความแต่ละตัว เราต้องตรวจสอบว่า อักษรนั้นเป็นตัวเลขหรือเครื่องหมาย. เรามีคำสั่ง if ที่ตรวจสอบเงื่อนไข. รูปแบบของคำสั่ง if คือ
if( เงื่อนไข ) คำสั่งที่จะทำเมื่อเงื่อนไขเป็นจริง;
และ
if( เงื่อนไข ) คำสั่งที่ทำเมื่อเงื่อนไขเป็นจริง; else คำสั่งที่ทำเมื่อเงื่อนไขเป็นเท็จ;
เราต้องการทดสอบว่าอักษรตัวที่ i นั้นเป็นเครื่องหมายหรือไม่. เราสามารถเขียนเงื่อนไขได้เป็น
(line[i]=='+') || (line[i]=='-') || (line[i]=='*') || (line[i]=='/')
เครื่องหมาย || ที่คั่นระหว่างแต่ละเงื่อนไขย่อยใช้แทนการเชื่อมโยงแบบ หรือ กล่าวคือเงื่อนไขนี้จะเป็นจริงเมื่อมีเงื่อนไขย่อยอันใดอันหนึ่งที่เป็นจริง. วิธีการตรวจสอบอีกแบบก็คือการตรวจสอบว่าอักษรนั้นเป็นตัวเลขหรือไม่. เราเขียนได้โดย
(line[i]>='0') && (line[i]<='9')
ในทำนองเดียวกันกับเครื่องหมาย || เครื่องหมาย && ใช้แทนเงื่อนไขว่า และ โดยเงื่อนไขที่เชื่อมด้วยเครื่องหมายนี้จะเป็นจริงเมื่อเงื่อนไขย่อยทั้งสองเป็นจริง.
ตอนนี้เรารูจักโครงสร้างของคำสั่งมากพอแล้ว. เราจะเขียนโปรแกรมที่หนึ่งที่ประกอบขึ้นจากคำสั่งเหล่านี้.
โปรแกรมแรก[แก้ไข | แก้ไขต้นฉบับ]
ด้านล่างแสดงโปรแกรมที่เราเขียน. ในภาษาซี ทุกสิ่งที่เราเขียนคือการประกาศและนิยาม. โปรแกรมนี้เราเขียนนิยามฟังก์ชั่น main ซึ่งโดยข้อตกลง จะเป็นฟังก์ชั่นหลักที่ถูกเรียกเมื่อโปรแกรมทำงาน. รูปแบบของการเขียนนิยามฟังก์ชั่นเป็นดังนี้
ชนิดของค่าที่คืน ชื่อฟังก์ชั่น( รายการของค่าที่ส่งผ่าน ) { คำสั่ง; }
ถ้าเราไม่ระบุชนิดของค่าที่ฟังก์ชั่นคืน คอมไพล์เลอร์จะกำหนดให้โดยอัตโนมัติว่าเราจะคืนค่าเป็นจำนวนเต็ม (int.
// // โปรแกรมคำนวณประโยคสัญลักษณแบบ postfix โปรแกรมแรก. // #include <stdio.h> main() { int list[100]; int listlength = 0; char line[100]; int i; int o1, o2, r; scanf("%s",line); i = 0; while(line[i]!=0) { if((line[i]>='0') && (line[i]<='9')) { list[listlength] = (line[i]-'0'); listlength++; } else { o2 = list[listlength-1]; o1 = list[listlength-2]; listlength-=2; /* take out these numbers */ if(line[i]=='+') r = o1 + o2; else if(line[i]=='-') r = o1 - o2; else if(line[i]=='*') r = o1 * o2; else r = o1 / o2; list[listlength] = r; listlength++; } i++; } printf("%d\n", list[listlength-1]); }
ในภาษาซี เราจะมองว่าตัวอักษรมีค่าเป็นตัวเลขได้. ในคำสั่ง
list[listlength] = (line[i]-'0');
เรานำตัวอักษรตัวที่ i มาแล้วลบด้วยค่าของตัวอักษร '0' เพื่อจะได้ค่าตัวเลขของมัน ก่อนที่จะนำมันไปเก็บไว้ในลำดับ.
คำสั่ง listlength-=2 มีความหมายเหมือนกับ listlength = listlength - 2 และคำสั่ง
printf("%d\n", list[listlength-1]);
จะพิมพ์ค่าสุดท้ายในลำดับออกมา. คำสั่ง printf รับค่าตัวแรกเป็นข้อความที่จัดรูปแบบการแสดงผล และรับรายการของข้อมูลที่ต้องการแสดงผลถัดไป. รูปแบบการแสดงผลจะถูกระบุโดยเครื่องหมาย % ตามด้วยอักษรแสดงรูปแบบ. ในกรณีนี้ %d ระบุว่าเราจะพิมพ์ตัวเลขฐานสิบ. เครื่องหมาย \n ในการจัดรูปแบบ ระบุให้ printf ขึ้นบรรทัดใหม่. ในการสั่งคำสั่ง printf โดยปกติแล้วเครื่องจะยังไม่แสดงข้อความที่เราสั่งพิมพ์ ถ้าโปรแกรมยังไม่สั่งขึ้นบรรทัดใหม่.