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

ในบทนี้เราจะทบทวนการเขียนโปรแกรมภาษาซีเบื้องต้น โดยจะกล่าวถึงการเขียนคำสั่งเงื่อนไข คำสั่งวนรอบ อาร์เรย์เบื้องต้น รวมถึงหลักการเขียนโปรแกรมทั่วไป โดยจะใช้ตัวอย่างเป็นโปรแกรมคำนวณนิพจน์แบบโพสต์ฟิกซ์ การกล่าวถึงการเขียนโปรแกรมภาษาซีในบทนี้ไม่ได้มีเป้าหมายที่จะอธิบายเนื้อหาให้ครอบคลุมทั้งหมด

ประโยคสัญลักษณ์แบบโพสต์ฟิกซ์

เมื่อเราต้องการจะทราบว่า $2\times 3+5/(6+7\times (3-4))$ มีค่าเท่าใด สิ่งที่เราทำก็คือการตีความประโยคสัญลักษณ์นี้. เราเริ่มจากการคำนวณจากวงเล็บที่อยู่ด้านในสุด และค่อยๆ ไล่ออกมา. เราทราบว่าเครื่องหมาย $\times$ และ $/$ มีความสำคัญมากกว่าเครื่องหมาย $+$ และ $-$ ดังนั้นเราจึงประมวลผลพวกมันก่อน. สุดท้ายเราก็ได้ผลลัพธ์ออกมา. ประโยคสัญลักษณ์ข้างต้นนี้เป็นการเขียนระบุลำดับการประมวลผลแบบหนึ่ง ที่เราเรียกว่า 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 โดยปกติแล้วเครื่องจะยังไม่แสดงข้อความที่เราสั่งพิมพ์ ถ้าโปรแกรมยังไม่สั่งขึ้นบรรทัดใหม่.