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

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