โครงสร้างข้อมูล/ทบทวนการเขียนโปรแกรมภาษาซี

ในบทนี้เราจะทบทวนการเขียนโปรแกรมภาษาซีเบื้องต้น โดยจะกล่าวถึงการเขียนคำสั่งเงื่อนไข
คำสั่งวนรอบ อาร์เรย์เบื้องต้น รวมถึงหลักการเขียนโปรแกรมทั่วไป
โดยจะใช้ตัวอย่างเป็นโปรแกรมคำนวณนิพจน์แบบโพสต์ฟิกซ์ การกล่าวถึงการเขียนโปรแกรมภาษาซีในบทนี้ไม่ได้มีเป้าหมายที่จะอธิบายเนื้อหาให้ครอบคลุมทั้งหมด 
ประโยคสัญลักษณ์แบบโพสต์ฟิกซ์
ประโยคสัญลักษณ์แบบโพสต์ฟิกซ์.
เมื่อเราต้องการจะทราบว่า formula_1
มีค่าเท่าใด สิ่งที่เราทำก็คือการตีความประโยคสัญลักษณ์นี้.
เราเริ่มจากการคำนวณจากวงเล็บที่อยู่ด้านในสุด และค่อยๆ ไล่ออกมา.
เราทราบว่าเครื่องหมาย formula_2 และ formula_3 มีความสำคัญมากกว่าเครื่องหมาย
formula_4 และ formula_5 ดังนั้นเราจึงประมวลผลพวกมันก่อน.
สุดท้ายเราก็ได้ผลลัพธ์ออกมา.
ประโยคสัญลักษณ์ข้างต้นนี้เป็นการเขียนระบุลำดับการประมวลผลแบบหนึ่ง
ที่เราเรียกว่า 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 + / + พบเครื่องหมาย
 -->  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  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 
ที่หัวของโปรแกรม เพื่อให้คอมไพล์เลอร์อ่านการประกาศฟังก์ชั่นต่างๆ
จากแฟ้มนี้. ฟังก์ชั่น scanf ก็ถูกประกาศในไฟล์นี้เช่นเดียวกัน.
การวนรอบ
การวนรอบ.
เมื่อเราได้ข้อมูลแบบข้อความเข้ามาแล้ว
เราต้องการจะไล่พิจารณาตัวอักษรในข้อความนั้นทีละตัวจนจบ.
เราต้องการรูปแบบการสั่งให้โปรแกรมทำงานซ้ำ ซึ่งในภาษาซีมีหลายรูปแบบ.
ในที่นี้เรายกตัวอย่างแค่สองคำสั่งหลักเท่านั้น.
การทำซ้ำแบบ while
การทำซ้ำแบบ while.
การทำซ้ำแบบ while มีรูปแบบดังนี้
 while(เงื่อนไข)
 คำสั่ง;
ลักษณะทั่วไปของคำสั่งทำซ้ำนี้คือ คำสั่งที่จะถูกทำซ้ำนั้นคือคำสั่งเดียวที่อยู่ถัดจากคำสั่ง while
หรือคำสั่ง for เท่านั้น.
ถ้าเราต้องการให้คำสั่งวนรอบนี้ครอบคลุมหลายๆ คำสั่ง
เราจะทำได้โดยการจับคำสั่งหลายๆ อันให้กลายเป็น ชุดคำสั่ง
ที่มีคุณสมบัติเหมือนเป็นคำสั่งเดียว ตัวอย่างเช่น:
 while(เงื่อนไข) {
 คำสั่ง1;
 คำสั่ง2;
 คำสั่ง3;
ในกรณีของเรา เราจะเขียนส่วนวนรอบหลักของโปรแกรมได้เป็น
 i=0;
 while(line[i]!=0) {
 คำสั่ง;
 i++;
การทำซ้ำแบบ for
การทำซ้ำแบบ for.
การทำซ้ำแบบ for มีรูปแบบของคำสั่งดังนี้
 for( คำสั่งเริ่มต้น ; เงื่อนไข ; คำสั่งที่ทำก่อนจะเริ่มทำงานครั้งต่อไป )
 คำสั่ง;
คำสั่ง for นี้
โดยทั่วไปเราจะใช้ในกรณีที่เราทราบจำนวนครั้งของการวนรอบ.
เรารู้ว่าเราจะทำงานจำนวนเท่ากับความยาวของข้อความ. เรามีฟังก์ชั่น strlen จะคือค่าความยาวของข้อความที่เราป้อนไป.
ในการจะใช่้ฟังก์ชั่นนี้ เราต้องประกาศ #include 
ไว้ที่หัวของโปรแกรมด้วย. เราจะเขียนส่วนวนรอบหลักโดยใช้คำสั่ง 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.
ในภาษาซี เราจะมองว่าตัวอักษรมีค่าเป็นตัวเลขได้. ในคำสั่ง
 list[listlength] = (line[i]-'0');
เรานำตัวอักษรตัวที่ i มาแล้วลบด้วยค่าของตัวอักษร '0'
เพื่อจะได้ค่าตัวเลขของมัน ก่อนที่จะนำมันไปเก็บไว้ในลำดับ.
คำสั่ง listlength-=2 มีความหมายเหมือนกับ listlength = listlength - 2 และคำสั่ง
 printf("%d\n", list[listlength-1]);
จะพิมพ์ค่าสุดท้ายในลำดับออกมา. คำสั่ง printf
รับค่าตัวแรกเป็นข้อความที่จัดรูปแบบการแสดงผล
และรับรายการของข้อมูลที่ต้องการแสดงผลถัดไป.
รูปแบบการแสดงผลจะถูกระบุโดยเครื่องหมาย % ตามด้วยอักษรแสดงรูปแบบ.
ในกรณีนี้ %d ระบุว่าเราจะพิมพ์ตัวเลขฐานสิบ. เครื่องหมาย
\n ในการจัดรูปแบบ ระบุให้ printf ขึ้นบรรทัดใหม่.
ในการสั่งคำสั่ง printf
โดยปกติแล้วเครื่องจะยังไม่แสดงข้อความที่เราสั่งพิมพ์
ถ้าโปรแกรมยังไม่สั่งขึ้นบรรทัดใหม่.