forked from jittat/dsalg
-
Notifications
You must be signed in to change notification settings - Fork 0
/
arrays-pointers.tx
1204 lines (977 loc) · 101 KB
/
arrays-pointers.tx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{อาร์เรย์และพอยน์เตอร์}
\label{chapter:arrays}
ในบทนี้เราจะพิจารณาโครงสร้างข้อมูลพื้นฐานสำหรับจัดเก็บและประมวลผลข้อมูลจำนวนมากที่เรียกว่า{\em
อาร์เรย์} (array) รวมไปถึงข้อมูลประเภท{\em พอยน์เตอร์} (pointer)
ซึ่งเก็บตำแหน่งภายในหน่วยความจำ
โดยเราจะเริ่มพิจารณาแนวคิดของโครงสร้างข้อมูลและชนิดข้อมูลดังกล่าวโดยไม่ขึ้นกับภาษาโปรแกรมที่ใช้
จากนั้นเราจะศึกษาวิธีการเขียนในภาษา C++
และศึกษาความสัมพันธ์ระหว่างพอยน์เตอร์และอาร์เรย์ซึ่งเป็นคุณลักษณะเฉพาะที่มีในภาษาตระกูล
C และ C++
ในบทนี้ เราจะเริ่มศึกษาการวิเคราะห์เวลาการทำงานของอัลกอริทึมอย่างง่าย ก่อนที่จะไปพิจารณาอย่างเป็นทางการในบทที่~\ref{chapter:analysis}
\section{อาร์เรย์}
อาร์เรย์เป็นโครงสร้างข้อมูลที่เก็บกลุ่มของข้อมูลเป็นรายการ
โดยที่ข้อมูลแต่ละตัวจะถูกเก็บต่อเนื่องกันในหน่วยความจำ และถูกอ้างถึงโดยใช้ดัชนี (index)
ตัวอย่างง่าย ๆ ของอาร์เรย์คือรายการข้อมูลด้านล่างนี้
\begin{center}
2, 3, 5, 7, 11, 13, 17, 19, 23
\end{center}
ถ้าเราเรียกรายการดังกล่าวว่ารายการ $A$ และอ้างถึงข้อมูลแต่ละตัวด้วยดัชนีที่เริ่มต้นด้วย 0
ข้อมูลแต่ละตัวในรายการจะถูกอ้างถึงได้ดังตารางในรูปที่~\ref{fig:array-array-access}
\begin{figure}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$A[0]$ & $A[1]$ & $A[2]$ & $A[3]$ & $A[4]$ & $A[5]$ & $A[6]$ & $A[7]$ & $A[8]$ \\
\hline
2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23\\
\hline
\end{tabular}
\end{center}
\caption{การอ้างถึงข้อมูลแต่ละตัวในอาร์เรย์ $A$}
\label{fig:array-array-access}
\end{figure}
---q การคำนวณค่า
จงหาผลลัพธ์ของนิพจน์เหล่านี้ (1) $A[4]$, (2) $A[7]$, (3) $A[A[0]]$,
(4) $A[A[A[0]]]$, (5) $A[200]$
===
(1) 11, (2) 19, (3) 5, (4) 13, (5) ไม่มีค่า (ดูอธิบายเพิ่มเติม)
---
การหาคำตอบของคำถามที่ (3) นั้น จำเป็นต้องเข้าใจขั้นตอนการคำนวณค่าของนิพจน์
เราต้องการหาค่า $A[A[0]]$ ดังนั้นเราต้องหาค่า $A[0]$ ก่อน
เมื่อพิจารณาในอาร์เรย์เราพบว่า $A[0]$ คือ $2$ ดังนั้น จากนั้นเราจึงพิจารณาข้อมูล
$A[2]$ ในอารเรย์ ซึ่งจะได้ค่า $5$
ในการทำงานจริง อาร์เรย์จะเก็บในหน่วยความจำที่ต่อเนื่องกัน
และมักจะมีขอบเขตที่จำกัดและต้องระบุเมื่อเริ่มใช้ เช่น อาร์เรย์จำนวน 100 ช่อง หรือ
100000 ช่องเป็นต้น รูปที่~\ref{fig:array-array-in-mem}
แสดงตัวอย่างของการเก็บข้อมูลของอาร์เรย์ในหน่วยความจำ
\begin{figure}
TODO: ใส่รูป
\caption{การเก็บข้อมูลของอาร์เรย์ในหน่วยความจำ}
\label{fig:array-array-in-mem}
\end{figure}
คำถามที่ (5) เป็นการอ้างถึงข้อมูลที่อยู่นอกขอบเขตของอาร์เรย์
ซึ่งผลลัพธ์ที่ได้จะขึ้นกับภาษาโปรแกรมที่ใช้ สำหรับภาษา C หรือ C++
ผลลัพธ์ที่ได้จะขึ้นกับข้อมูลในหน่วยความจำในตำแหน่งที่ $A[200]$ ควรจะอยู่
เราจะได้ศึกษารายละเอียดนี้ต่อไป อย่างไรก็ตาม ปกติแล้ว ในการใช้งานอาร์เรย์
เราจะไม่อ้างถึงข้อมูลที่อยู่นอกขอบเขตของอาร์เรย์
การระบุดัชนีของข้อมูลในอาร์เรย์ในหนังสือเล่มนี้จะอ้างอิงจากภาษาตระกูลภาษา C
นั่นคือเริ่มต้นที่ 0 \ \ สำหรับบางภาษา เราสามารถระบุค่าเริ่มต้นของดัชนีได้และมักเริ่มที่ 1
เช่นภาษาปาสคาล (Pascal) เป็นต้น
อย่างไรก็ตามแนวคิดในการพัฒนาโปรแกรมนั้นจะไม่ต่างกัน
เมื่อเราสามารถอ้างถึงข้อมูลได้ด้วยดัชนี
เราสามารถใช้ตัวแปรเพื่อแทนค่าดัชนีของข้อมูลที่เราต้องการใช้งานได้
ความสามารถนี้ทำให้เราสามารถเขียนโปรแกรมที่มีลักษณะดังด้านล่างได้
---algt[alg:array-sum1] *
* ให้ $x\leftarrow 0$
* พิจารณา ตัวแปร $i\leftarrow 0,1,\ldots,8$
** ให้ $x \leftarrow x + A[i]$
---
---q *
อัลกอริทึมดังกล่าวคำนวณค่าบางอย่างในตัวแปร $x$ ค่านั้นคืออะไร?
===
ผลรวมของข้อมูลทั้งหมดในอาร์เรย์ $A$
---
สังเกตว่าอัลกอริทึม~\ref{alg:array-sum1} เขียนให้ทำงานกับอาร์เรย์ $A$
ที่มีดัชนีมากที่สุดคือ 8 เท่านั้น ในการพัฒนาอัลกอริทึมทั่วไปเรามักเขียนให้ทำงานได้กับข้อมูลทั่วไป
ซึ่งในกรณีนี้ การจะปรับให้ทำงานได้กับอาร์เรย์ใด ๆ เราจะต้องระบุขนาดของอาร์เรย์ด้วย
เราสามารถเขียนอัลกอริทึมดังกล่าวโดยระบุพารามิเตอร์ให้ชัดเจนขึ้นได้ดังด้านล่าง
---algt[alg:array-sum2] คำนวณค่าบางอย่างของอาร์เรย์ $A$ ที่มีข้อมูลจำนวน $n$ ตัว
* ให้ $x\leftarrow 0$
* พิจารณา ตัวแปร $i\leftarrow 0,1,\ldots,n-1$
** ให้ $x \leftarrow x + A[i]$
* คืนค่า $x$ เป็นคำตอบ
---
\subsection{เวลาที่ใช้ในการทำงาน}
ค่าพารามิเตอร์ $n$ ที่เราส่งให้กับโปรแกรมย่อย ระบุจำนวนรอบของการทำงาน
ซึ่งจะเป็นตัวกำหนดเวลาที่โปรแกรมย่อยใช้ในการทำงานด้วย อย่างไรก็ตาม
เพียงแค่พิจารณาโปรแกรมย่อยดังกล่าว เราไม่สามารถระบุเวลาจริง ๆ
ที่โปรแกรมย่อยจะทำงานได้เนื่องจากเราไม่ทราบปัจจัยหลาย ๆ อย่าง
---q เวลาการทำงานจริงบนคอมพิวเตอร์
ปัจจัยอะไรบ้างที่กำหนดเวลาทำงานบนคอมพิวเตอร์จริง ๆ ของโปรแกรมย่อยข้างต้น
===
เวลาในการทำงานจริง ขึ้นกับ (1) โปรแกรมภาษาคอมพิวเตอร์ที่เขียนจากโปรแกรมย่อย (2)
คอมไพเลอร์ที่ใช้ (3) เครื่องคอมพิวเตอร์ที่นำโปรแกรมไปทำงาน
และสถานะของเครื่องในขณะที่โปรแกรมทำงาน
---
สังเกตว่าการพิจารณาแค่อัลกอริทึมเพียงอย่างเดียว
หรือกระทั่งจะพิจารณาโปรแกรมในภาษาเครื่องที่ถูกคอมไพล์แล้วร่วมด้วย
ก็ไม่สามารถทำให้เราระบุเวลาการทำงานบนคอมพิวเตอร์จริงได้อย่างแม่นยำ
ยิ่งในปัจจุบันที่คอมพิวเตอร์สามารถทำงานหลาย ๆ งานในเวลาเดียวกัน
การทำนายเวลาการทำงานจริงยิ่งกระทำได้ยากขึ้นด้วย
อย่างไรก็ตาม แม้การระบุเวลาการทำงานจริง ๆ ทำได้ยาก
การทำนายเวลาการทำงานของอัลกอริทึมก่อนที่จะนำไปพัฒนาเป็นโปรแกรมก็ยังเป็นสิ่งจำเป็นมาก
เนื่องจากในหลาย ๆ เราสามารถเลือกใช้อัลกอริทึมได้หลากหลาย
และอัลกอริทึมเหล่านั้นก็มีความซับซ้อนในการนำไปพัฒนาเป็นโปรแกรมที่แตกต่างกัน
โปรแกรมเมอร์จึงต้องเลือกใช้อัลกอริทึมให้เหมาะสม นั่นคือเป็นอัลกอริทึมที่เมื่อนำไปพัฒนาแล้ว
มีประสิทธิภาพพอ (ทำงานได้ทันเวลา)
และมีความซับซ้อนในการเขียนในระดับที่โปรแกรมเมอร์สามารถจัดการได้
การเลือกนำอัลกอริทึมที่ทราบว่ามีประสิทธิภาพดีที่สุดไปพัฒนานั้น
อาจไม่ใช่ทางเลือกที่ดีที่สุดก็เป็นได้
ดังนั้น เราจะพยายามวิเคราะห์เวลาการทำงานของโปรแกรมย่อย
ที่อยู่ในรูปของโปรแกรมลำลองด้านบน ให้ละเอียดเท่าที่เราพอจะทำได้
แน่นอนเราจำเป็นต้องเพิ่มข้อสมมติหลายอย่างเพื่อให้การวิเคราะห์เป็นไปได้
ข้อสมมติข้อแรก (ที่เราจะใช้ตลอดในหนังสือเล่มนี้) คือ
เราจะสมมติว่าคอมพิวเตอร์นั้นทำงานทีละคำสั่ง นั่นคือไม่ใช่คอมพิวเตอร์แบบขนาน
หรือเป็นคอมพิวเตอร์ที่มีหน่วยประมวลผลหลายตัวทำงานพร้อมกัน\footnote{TODO:
ระบุว่าถึงจะเป็นกรณีดังกล่าว การวิเคราะห์ก็ยังเป็นไปได้}
ถ้าพิจารณาต่อไป เราจะพบว่าโปรแกรมย่อย~\ref{alg:array-sum2}
ทำงานโดยใช้เวลาในการทำงานที่แปรผันตามค่าพารามิเตอร์ $n$
เพื่อจะให้เราสามารถวิเคราะห์เวลาการทำงานออกมาได้
เราจะสมมติว่าคอมพิวเตอร์เมื่อทำงานตามโปรแกรมดังกล่าว ใช้เวลา 1
หน่วยในการประมวลผลคำสั่งแต่ละบรรทัด
เราจะสามารถคำนวณเวลาที่โปรแกรมดังกล่าวใช้โดยพิจารณาจำนวนครั้งที่คำสั่งในแต่ละบรรทัดทำงาน
ดังด้านล่าง
---algt *
* ให้ $x\leftarrow 0$ \ \ \ \ $\rhd\rhd\rhd$ ทำงาน 1 ครั้ง
* พิจารณา ตัวแปร $i\leftarrow 0,1,\ldots,n-1$ \ \ \ \ $\rhd\rhd\rhd$ ทำงาน $n$ ครั้ง
** ให้ $x \leftarrow x + A[i]$ \ \ \ \ $\rhd\rhd\rhd$ ทำงาน $n$ ครั้ง
* คืนค่า $x$ เป็นคำตอบ \ \ \ \ $\rhd\rhd\rhd$ ทำงาน 1 ครั้ง
---
ดังนั้นเราจะได้ว่าเวลารวมคือ $2n + 2$ หน่วย คำถามที่ตามมาก็คือ
ผลลัพธ์จากการวิเคราะห์ดังกล่าวมีความแม่นยำ
และสามารถนำไปใช้วิเคราะห์และตัดสินใจต่อไปได้เพียงใด
เราจะพิจารณาผลจากการสมมติและความถูกต้องที่ใช้ได้ในบทที่~\ref{chapter:analysis}
\subsection{การประมวลผลรายการด้วยอาร์เรย์}
\label{sect:array-list-processing}
ในส่วนนี้เราจะพัฒนาโปรแกรมลำลองเพื่อประมวลผลข้อมูลในรายการที่เก็บในอาร์เรย์
พร้อมกับวิเคราะห์เวลาการทำงาน
---q *
สมมติว่าเรามีรายการของข้อมูล ลองนึกตัวอย่างการประมวลผลที่เราสามารถกระทำกับข้อมูลในรายการนี้
---
ก่อนที่เราจะประมวลผลได้ เราต้องพิจารณาวิธีการจัดเก็บข้อมูลแบบรายการลงในอาร์เรย์ก่อน
สังเกตว่าโครงสร้างข้อมูลแบบอาร์เรย์มีลักษณะเป็นรายการอยู่แล้ว
อย่างไรก็ตามในการจัดการกับรายการที่มีจำนวนข้อมูลเปลี่ยนแปลงได้
การใช้อาร์เรย์เพียงอย่างเดียวนั้นไม่เพียงพอ
---q *
อะไรคือสิ่งที่ขาดหายไป ถ้าเราใช้แค่อาร์เรย์ในการจัดเก็บรายการที่จำนวนข้อมูลในรายการเปลี่ยนแปลงได้
---
ดังนั้น เราจะใช้ตัวแปรอีกหนึ่งตัวในการเก็บจำนวนข้อมูลที่มีในอาร์เรย์
โปรแกรมลำลองที่เราจะพัฒนาจะเปลี่ยนค่าของตัวแปรนี้โดยตรงเพื่อปรับให้มีค่าที่ถูกต้องภายหลังการประมวลผล
ในการพัฒนาโปรแกรมลำลองให้เป็นโปรแกรมภาษา C++
การทำงานดังกล่าวจะต้องใช้การส่งรับพารามิเตอร์เป็นพอยน์เตอร์หรือส่งแบบ pass by
reference ซึ่งเราจะได้พิจารณาในส่วน~\ref{sect:array-pointer-c}
นอกจากนี้ในบทที่~\ref{chapter:classes} เราจะได้ศึกษาวิธีการที่จะ ``ประกอบรวม''
อาร์เรย์และตัวแปรที่เก็บจำนวนข้อมูลที่อยู่ในอาร์เรย์เข้าด้วยกัน
เพื่อสร้างเป็นชนิดข้อมูลใหม่ที่นำไปใช้งานได้สะดวกต่อไป
เราจะพิจารณาการประมวลผลกับอาร์เรย์ในรูปแบบต่าง ๆ ดังนี้ (1) การค้นข้อมูลในรายการ, (2) การเพิ่มข้อมูลลงไปตอนท้ายของรายการ, (3) การลบข้อมูลในรายการ, และ (4) การแทรกข้อมูลในรายการ
\subsubsection{การค้นข้อมูล}
สำหรับการค้นข้อมูลในรายการ
เป้าหมายของการทำงานคือทราบว่ามีข้อมูลที่เราต้องการหาหรือไม่ และถ้ามีอยู่ที่ตำแหน่งใด
ในกรณีนี้เราจะต้องพิจารณาข้อมูลทุกตัวในรายการ
โปรแกรมลำลองมีลักษณะไม่ต่างจากที่เราเคยเขียนเท่าใดนัก
---algt ค้นหาข้อมูล $x$ ในอาร์เรย์ $A$ ที่มีข้อมูลจำนวน $n$ ตัว
* พิจารณา ตัวแปร $i\leftarrow 0,1,\ldots, n-1$
** ถ้า $A[i] = x$
*** คืนค่า $i$ เป็นผลลัพธ์
* ตอบว่าไม่พบค่าที่ต้องการ
---
ในการพัฒนาโปรแกรมจริง ๆ
เราจะต้องจัดการในกรณีที่จะต้องตอบว่าไม่พบค่าที่ต้องการให้ชัดเจนกว่านี้
แต่ในขณะนี้เราจะสมมติว่าโปรแกรมย่อยสามารถตอบแบบนี้ได้
---q *
ในกรณีของโปรแกรมย่อยสำหรับหาผลรวม เราพบว่าโปรแกรมทำงานในเวลาที่แปรผันกับค่า $n$
เสมอ เป็นไปได้หรือไม่ ที่โปรแกรมย่อยสำหรับจะทำงานโดยวนรอบเป็นจำนวนครั้งที่น้อยกว่าค่า $n$ มาก? และเป็นในกรณีใด?
---
---q *
สำหรับอาร์เรย์ที่มีข้อมูล $n$ ตัว เมื่อใดที่โปรแกรมย่อยจะทำงานโดยวนรอบมากที่สุด
---
โปรแกรมย่อยข้างต้นอาจจะทำงานได้รวดเร็วมาก ถ้าข้อมูลที่ต้องการค้นหาอยู่ตอนต้นของอาร์เรย์
โปรแกรมย่อยลักษณะนี้เป็นตัวอย่างที่ดีของโปรแกรมย่อยที่เวลาการทำงานขึ้นกับข้อมูลป้อนเข้า
ทำให้ในการวิเคราะห์เวลาการทำงานนั้น เราจำเป็นจะต้องพิจารณาข้อมูลป้อนเข้าด้วย
อย่างไรก็ตามเราไม่สามารถที่จะวิเคราะห์เวลาการทำงานของโปรแกรมลำลองบนข้อมูลป้อนเข้าทุกรูปแบบได้
เพราะว่าจำนวนของข้อมูลป้อนเข้านั้นมีไม่จำกัด
ในทางปฏิบัติแล้ว เราจึงจะแบ่งวิเคราะห์เวลาการทำงานเป็นกรณีย่อย ๆ สามกรณีคือ
\begin{itemize}
\item การวิเคราะห์ในกรณีที่ดีที่สุด (best-case analysis),
\item การวิเคราะห์ในกรณีที่เลวร้ายที่สุด (worst-case analysis), และ
\item การวิเคราะห์ในกรณีเฉลี่ย (average-case analysis)
\end{itemize}
สำหรับการวิเคราะห์ในกรณีเฉลี่ยนั้น เป็นการวิเคราะห์เชิงความน่าจะเป็น
เราจำเป็นจะต้องนิยามลักษณะการกระจายของข้อมูลป้อนเข้าให้ชัดเจน จึงจะสามารถกระทำได้
เราจะได้ศึกษาตัวอย่างการวิเคราะห์นี้ในบทที่~\ref{chapter:analysis} (TODO:
เพิ่มหรือลบ) ในที่นี้เราจะสนใจเฉพาะการวิเคราะห์กรณีที่ดีที่สุด
และการวิเคราะห์ในกรณีที่เลวร้ายที่สุดเท่านั้น
กรณีที่ดีที่สุดคือกรณีที่มีการวนรอบเพียงรอบเดียว นั้นคือเป็นกรณีที่ $A[0] = x$
สังเกตว่าถ้าเราสมมติให้การประมวลผลแต่ละบรรทัดใช้เวลา 1 หน่วย ในกรณีที่ดีที่สุด
โปรแกรมลำลองดังกล่าวจะใช้เวลาทำงาน $4$ หน่วย
กรณีที่เลวร้ายที่สุดเกิดขึ้นเมื่อไม่พบข้อมูลที่ต้องการหา
สังเกตว่าโปรแกรมจะทำงานวนอยู่ที่สองบรรทัดแรกเป็นจำนวน $n$ ครั้ง และคืนคำตอบ
ดังนั้นโปรแกรมจะใช้เวลาทำงาน $2n + 1$ หน่วย
เช่นเดียวกับการวิเคราะห์อย่างง่ายในส่วนที่แล้ว
เราจะพิจารณาแนวคิดการวิเคราะห์ทั้งสามแบบอย่างละเอียดในบทที่~\ref{chapter:analysis}
\subsubsection{การเพิ่มข้อมูลลงไปท้ายรายการ}
เราจะเพิ่มข้อมูลลงไปตอนท้ายของข้อมูลในอาร์เรย์
นั่นคือใส่ข้อมูลในอาร์เรย์ที่มีดัชนีมากกว่าดัชนีตัวสุดท้าย
โปรแกรมลำลองที่น่าจะทำงานได้เขียนดังนี้
---algt เพิ่มข้อมูล $x$ ในตอนท้ายอาร์เรย์ $A$ ที่มีข้อมูล $n$ ตัว
* $A[n] \leftarrow x$
* $n \leftarrow n + 1$
---
อย่างไรก็ตาม ในการนำไปใช้จริง โปรแกรมลำลองดังกล่าวอาจจะทำให้เกิดข้อผิดพลาดขึ้นระหว่างการทำงานได้
---q *
กรณีใดที่โปรแกรมลำลองข้างต้นอาจทำให้เกิดข้อผิดพลาดขึ้นระหว่างการทำงาน
===
จากที่เราได้เคยเกริ่นบ้างแล้วว่า ในการใช้งานอาร์เรย์
โดยมากจะต้องระบุขอบเขตหรือจำนวนข้อมูลมากที่สุดที่เก็บในอาร์เรย์ได้
ในกรณีของโปรแกรมลำลองนี้ถ้าเราเรียกใช้เมื่อ $n$
มีขนาดมากกว่าหรือเท่ากับจำนวนข้อมูลที่อาร์เรย์เก็บได้ คำสั่ง $A[n]\leftarrow x$
ก็อาจจะเขียนข้อมูลลงในหน่วยความจำบริเวณที่อยู่นอกขอบเขตของอาร์เรย์ $A$ ได้
---
ดังนั้นเพื่อความไม่ประมาท
โปรแกรมย่อยควรจะต้องตรวจสอบขนาดของอาร์เรย์เพื่อป้องกันความผิดพลาดนี้ด้วย
ในการเขียนต่อไปเราจะให้ $MAXLEN$ เป็นค่าคงที่แทนขนาดมากที่สุดของอาร์เรย์ $A$
เราปรับแก้โปรแกรมย่อยได้ดังด้านล่าง
---algt เพิ่มข้อมูล $x$ ในตอนท้ายอาร์เรย์ $A$ ที่มีข้อมูล $n$ ตัว (แก้ไข)
* ถ้า $n < MAXLEN$ แล้ว
** $A[n] \leftarrow x$
** $n \leftarrow n + 1$
* ไม่เช่นนั้น
** รายงานว่าไม่สามารถเพิ่มข้อมูลได้
---
โปรแกรมย่อยนี้ ในการวิเคราะห์เวลาการทำงานมีสองกรณีให้เราพิจารณา สังเกตว่า
จะใช้เวลาในการทำงานไม่เกิน $3$ หน่วยไม่ว่าในกรณีใด
ในกรณีแรก (กรณีที่ $n<MAXLEN$) โปรแกรมย่อยจะใช้เวลาการทำงาน $3$ หน่วย
และในอีกกรณีจะใช้เวลาการทำงาน $2$ หน่วย อย่างไรก็ตาม
ผู้อ่านอย่าเพิ่งรีบสรุปว่ากรณีแรกทำงานจริง ๆ ได้เร็วกว่า เพราะว่าความแตกต่างนี้จริง ๆ
แล้วเกิดจากข้อสมมติว่าการทำงานในทุกคำสั่งมีความเร็วเท่ากันคือ 1 หน่วย
ดังนั้นประเด็นสำคัญของการวิเคราะห์นี้คือโปรแกรมย่อยนี้ทำงานในเวลาที่ไม่ขึ้นกับค่า $n$
\subsubsection{การลบข้อมูลในรายการและการแทรกข้อมูลในรายการ}
สำหรับการลบข้อมูลและแทรกข้อมูลในรายการ
โปรแกรมย่อยที่ประมวลผลนั้นจะรับดัชนีของข้อมูลที่ต้องการลบ
และดัชนีที่ต้องการให้นำข้อมูลไปแทรกต่อจากตำแหน่งนั้น
ถ้าอาร์เรย์เริ่มต้นของเรามีข้อมูล 9 ตัว ดังด้านล่าง
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
ดัชนี & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
ข้อมูล & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & ?\\
\hline
\end{tabular}
จำนวนข้อมูล $n = 9$
\end{center}
สังเกตว่าเราละข้อมูลที่ในอาร์เรย์ที่มีดัชนีอยู่นอกขอบเขตของข้อมูลในรายการไป
(โดยแสดงด้วยเครื่องหมาย ?)
การลบข้อมูลที่มีดัชนีเป็น 3 ให้ผลดังนี้
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
ดัชนี & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
ข้อมูล & 2 & 3 & 5 & 11 & 13 & 17 & 19 & 23 & ? & ? \\
\hline
\end{tabular}
จำนวนข้อมูล $n = 8$
\end{center}
จากอาร์เรย์ดังกล่าวส การแทรกข้อมูล 99 เข้าไปหลังข้อมูลที่มีดัชนีเป็น 1 ให้ผลดังนี้
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
ดัชนี & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
ข้อมูล & 2 & 3 & 99 & 5 & 11 & 13 & 17 & 19 & 23 & ? \\
\hline
\end{tabular}
จำนวนข้อมูล $n = 9$
\end{center}
---q *
การประมวลผลทั้งสองแบบมีกระบวนการหนึ่งที่ต้องดำเนินการคล้าย ๆ กัน คืออะไร
---
การประมวลผลทั้งสองแบบนี้แสดงให้เห็นข้อจำกัดของการเก็บข้อมูลแบบรายการด้วยอาร์เรย์
(ยกเว้นจะมีเทคนิคพิเศษอื่น ๆ ประกอบ)
ที่โครงสร้างข้อมูลเช่นลิงก์ลิสต์ที่เราจะพิจารณาในบทที่~\ref{chapter:linked-lists}
สามารถจัดการได้เป็นอย่างดี
โปรแกรมลำลองด้านล่างแสดงการลบข้อมูลที่มีดัชนี $i$ ในรายการในอาร์เรย์
---algt[algo:array-deletion1] ลบข้อมูลที่มีดัชนี $i$ ในรายการที่เก็บในอาร์เรย์ $A$ ที่มีขนาด $n$ (แก้ไข)
* พิจารณาให้ ตัวแปร $i\leftarrow i,i+1,\ldots,n-1$
** $A[i]\leftarrow A[i+1]$
* $n\leftarrow n-1$
---
---q *
โปรแกรมลำลอง~\ref{algo:array-deletion1}
อาจทำให้เกิดความผิดพลาดระหว่างการทำงานได้ในบางกรณีเพราะว่าไม่ได้ตรวจสอบเงื่อนไขบางอย่าง
เงื่อนไขนั้นคืออะไร?
---
สังเกตว่าถ้าดัชนีอยู่นอกของเขตของรายการ
หรือในกรณีที่ไม่มีข้อมูลโปรแกรมลำลองอาจเกิดปัญหาระหว่างทำงาน
โปรแกรมลำลองด้านล่างเพิ่มเงื่อนไขในการตรวจสอบนี้ สำหรับในกรณีเช่นในตัวอย่างนี้ ภาษา
C++ จะมีวิธีการจัดการรายงานความผิดพลาดกลับไปยังโปรแกรมหลักที่เรียกใช้อย่างเป็นระบบ
โดยใช้แนวคิดที่เรียกว่า exception ซึ่งเราจะได้พิจารณาต่อไปในบทที่ XXXX (TODO:
เพิ่มหรือลบ)
---algt[algo:array-deletion2] ลบข้อมูลที่มีดัชนี $i$ ในรายการที่เก็บในอาร์เรย์ $A$ ที่มีขนาด $n$ (แก้ไข)
* ถ้า $i > n-1$ หรือ $i < 0$
** รายงานความผิดพลาดว่าดัชนีอยู่นอกขอบเขต แล้วจบการทำงาน
* พิจารณาให้ ตัวแปร $i\leftarrow i,i+1,\ldots,n-1$
** $A[i]\leftarrow A[i+1]$
* $n\leftarrow n-1$
---
สังเกตว่าเวลาที่โปรแกรมลำลองข้างต้นใช้การทำงาน ขึ้นกับตำแหน่งของข้อมูล
เช่นเดียวกับการวิเคราะห์ในส่วนของการค้นข้อมูล เราสามารถพิจารณากรณีต่าง ๆ ได้สามแบบ
---q *
กรณีใดที่ทำให้โปรแกรมลำลอง~\ref{algo:array-deletion2}
ใช้เวลาในการทำงานน้อยที่สุด (best case) และใช้เวลาเป็นเท่าใด?
---
---q *
กรณีใดที่ทำให้โปรแกรมลำลอง~\ref{algo:array-deletion2} ทำงานโดยใช้เวลามากที่สุด (worst case) และใช้เวลาเป็นเท่าใด
---
เราจะละการเขียนโปรแกรมลำลองของการแทรกข้อมูลในรายการไว้เป็นแบบฝึกหัดท้ายบท
\section{การประกาศและใช้งานอาร์เรย์ในภาษา C++}
ในส่วนนี้เราจะศึกษาการใช้งานอาร์เรย์ในภาษา C++ เพื่อเป็นพื้นฐานในการเขียนโปรแกรมสำหรับโครงสร้างข้อมูลอื่น ๆ
ในทางปฏิบัติจริง ในไลบรารีมาตรฐานของ C++ มีโครงสร้างข้อมูลแบบ {\ct vector}
ที่ใช้งานได้สะดวกกว่าอาร์เรย์มาก
เราจะได้พิจารณาวิธีการใช้งานเทคโนโลยีที่มีประโยชน์เหล่านี้ในบทที่~\ref{chapter:stl}
ในภาษา C++
เราสามารถประกาศและจองเนื้อที่สำหรับตัวแปรประเภทอาร์เรย์ได้โดยใช้รูปแบบดังนี้
\begin{center}
ชนิดข้อมูล ชื่อตัวแปร[ขนาด];
\end{center}
ตัวอย่างแสดงการประกาศตัวแปรอาร์เรย์ของจำนวนเต็ม ({\ct int})
และอาร์เรย์ของอักขระ ({\ct char})
---src[cpp]
int a[100];
char buf[1000];
---
ภายหลังการประกาศ ระบบจะจองเนื้อที่ในหน่วยความจำสำหรับอาร์เรย์ที่เราประกาศไว้
ทำให้เราสามารถใช้อาร์เรย์ในการเก็บข้อมูลได้
ขนาดของเนื้อที่ที่จองจะขึ้นกับขนาดของอาร์เรย์และขนาดของข้อมูลชนิดนั้น ยกตัวอย่างเช่น
โดยทั่วไปแล้ว ตัวแปรประเภท {\ct int} ใช้เนื้อที่ในหน่วยความจำ 4 ไบท์ อาร์เรย์ {\ct
a} ก็จะมีขนาดเท่ากับ 400 ไบท์ หรือในกรณีของตัวแปรประเภท {\ct char}
ที่โดยทั่วไปใช้เนื้อที่ 1 ไบท์ในการจัดเก็บ อาร์เรย์ {\ct buf} ก็จะถูกกันเนื้อที่ไว้ 1000
ไบท์\footnote{ในการทำงานจริง ระบบอาจจะกันที่ไว้เกินกว่าขนาดที่ต้องใช้จริงก็ได้}
ในการระบุขนาดของอาร์เรย์ เราไม่จำเป็นต้องระบุขนาดของอาร์เรย์เป็นค่าคงที่ก็ได้ ดังตัวอย่างด้านล่าง
---src[cpp]
int m = 1000;
int x[m * 2];
---
อย่างไรก็ตาม หลายครั้งเราไม่ทราบขนาดที่แน่นอนของอาร์เรย์ในขณะที่เราต้องประกาศ
ตัวอย่างเช่นในกรณีของการจัดเก็บรายการด้วยอาร์เรย์
ในที่นี้เราจะประกาศอาร์เรย์ให้มีขนาดใหญ่ระดับหนึ่งไว้ก่อน
และคอยตรวจสอบว่าข้อมูลล้นอาร์เรย์แล้วหรือยัง
เราจะพิจารณาและวิเคราะห์วิธีการการขยายขนาดอาร์เรย์ระหว่างการทำงาน
ในบทที่~\ref{chapter:analysis} นอกจากนี้ การใช้งานโครงสร้างข้อมูลแบบ {\ct
vector} ก็สามารถแก้ปัญหานี้ได้เช่นกัน
เราสามารถกำหนดค่าเริ่มต้นให้กับอาร์เรย์เมื่อต่อประกาศได้ ดังตัวอย่างด้านล่างนี้
---src[cpp]
int A[9] = {2,3,5,7,11,13,19,23,29};
int b[] = {1,10,100,1000};
int c[100] = {1,2,3,4};
---
สังเกตตัวแปร {\ct B} และ {\ct c}
ที่แสดงตัวอย่างที่คอมไพเลอร์จะจองข้อมูลตามจำนวนที่ระบุเมื่อประกาศ ({\ct B})
และการกำหนดค่าเริ่มต้นให้กับข้อมูลบางตัว
เราจะเริ่มโดยเขียนฟังก์ชัน {\ct unknown} จากอัลกอริทึม~\ref{alg:array-sum2}
---src[cpp]
int unknown(int A[], int n)
{
int x = 0;
for(int i = 0; i < n; ++i)
x += A[i];
return x;
}
---
ตัวอย่างการเรียกใช้งานฟังก์ชันดังกล่าวแสดงในส่วนของโปรแกรมด้านล่าง
ซึ่งโปรแกรมจะพิมพ์ค่า {\ct 28} ออกมาเป็นผลลัพธ์
---src[cpp]
int t[] = {1,2,3,4,5,6,7};
cout << unknown(t,7);
---
สังเกตว่าเราส่งตัวแปรแบบอาร์เรย์โดยไม่ระบุขนาดของอาร์เรย์ (ประกาศ {\ct int A[]}
เป็นพารามิเตอร์ของฟังก์ชัน) แต่เราสามารถใช้งานได้เหมือนตัวแปรอาร์เรย์ปกติ
\subsubsection{การประมวลผลรายการ}
เราจะเขียนโปรแกรมที่เกี่ยวข้องกับการเก็บรายการในอาร์เรย์ที่ได้กล่าวถึงในส่วนก่อนหน้าของบทนี้
สำหรับตัวอย่างนี้ เราจะเก็บรายการของจำนวนเต็ม (ข้อมูลประเภท {\ct int})
เนื่องจากเราจะต้องจองอาร์เรย์ให้มีขนาดใหญ่พอไว้ก่อนเริ่มต้นใช้งาน เราจะประกาศค่าคงที่
{\ct max\_size} เพื่อเก็บขนาดมากสุดของอาร์เรย์ สังเกตว่าเราใช้ keyword {\ct
const} เพื่อระบุว่าค่านี้จะไม่มีการเปลี่ยนแปลง
ในการเขียนฟังก์ชันในการประมวลผลรายการ
เราจะใช้ค่าคงทีนี้ในลักษณะที่เป็นตัวแปรแบบโกลบอล (global) นั่นคือเราจะพิจารณาว่าทุก ๆ
อาร์เรย์ที่จัดเก็บรายการที่เราจะประมวลผลจะมีขนาดมากที่สุดเท่ากันคือ {\ct max\_size}
---src[cpp]
const int max_size = 10000;
---
เราจะประกาศอาร์เรย์และตัวแปรที่ใช้เก็บขนาดของรายการดังด้านล่าง
---src[cpp]
int list[max_size];
int list_size;
---
จริง ๆ แล้ว โครงสร้างข้อมูลของเราจะใช้ตัวแปรทั้งสองด้วยกันตลอด
การประกาศในลักษณะข้างต้นทำให้เมื่อเราเรียกใช้ฟังก์ชันต่าง ๆ เราต้องส่งตัวแปรสองตัวเสมอ
ซึ่งเป็นเรื่องที่ไม่สะดวก \ \ ในบทที่~\ref{chapter:classes}
เราจะศึกษาวิธีการจับตัวแปรทั้งสองให้อยู่รวมกันเป็นเสมือนตัวแปรเดียว
---q *
ภายหลังที่เราประกาศตัวแปร {\ct list} และ {\ct list\_size}
ตามตัวอย่างข้างต้นแล้ว เราสามารถนำไปใช้งาน (เช่นเพิ่มข้อมูลลงในรายการ)
ได้ทันทีหรือไม่?
---
สังเกตว่า โครงสร้างข้อมูลที่เราจะใช้เก็บรายการนั้น ต้องมีการกำหนดค่าเริ่มต้นก่อน
เพราะว่าเมื่อประกาศ ตัวแปร {\ct list\_size}
อาจจะมีค่าเป็นอะไรก็ได้\footnote{อย่างไรก็ตาม ถ้าเราประกาศตัวแปรแบบโกลบอล
ตัวแปรจะถูกกำหนดค่าเริ่มต้นให้โดยอัตโนมัติตามกฎของ C++ (TODO: ใส่ reference??)}
ด้านล่างเป็นฟังก์ชันสำหรับกำหนดค่าเริ่มต้นให้กับโครงสร้างข้อมูลของเรา
---src[cpp,การกำหนดค่าเริ่มต้นให้กับรายการ,code:array-list-init]
void list_init(int list[], int& size)
{
size = 0;
}
---
ในฟังก์ชันข้างต้นเราใช้ตัวแปรประเภท {\em reference} ในการประกาศพารามิเตอร์ {\ct
size} ตัวแปรประเภทนี้ใช้สำหรับอ้างถึงตัวแปรอื่นและมีประโยชน์มากในการส่งค่าให้กับฟังก์ชัน
การส่งค่าให้กับฟังก์ชันจะกระทำโดยการคัดลอกค่าของอาร์กิวเมนท์จากฝั่งที่เรียกฟังก์ชัน
มายังพารามิเตอร์ในฟังก์ชัน ทำให้การแก้ไขค่าของพารามิเตอร์ไม่มีผลกับอาร์กิวเมนท์ต้นทาง
อย่างไรก็ตามในกรณีนี้ เราต้องการปรับค่า {\ct size} ให้เป็นศูนย์ การใช้ตัวแปรประเภท
reference ทำให้ตัวแปร {\ct size} อ้างถึงตัวแปรที่เป็นอาร์กิวเมนท์
การอ้างถึงพารามิเตอร์ {\ct size}
ในฟังก์ชันก็จะเป็นการอ้างถึงตัวแปรที่ส่งมาเป็นอาร์กิวเมนท์ของฟังก์ชันด้วย
เพื่อความเข้าใจที่ชัดเจนขึ้น
ลองพิจารณาตัวอย่างฟังก์ชันในโปรแกรม~\ref{code:array-ref-example}
\begin{figure}
---src[cpp,ตัวอย่างการใช้ตัวแปรแบบ reference ในการส่งค่าไปยังฟังก์ชัน,code:array-ref-example]
void m1(int a, int b)
{
b += a;
}
void m2(int a, int& b)
{
b += a;
}
---
\end{figure}
ถ้าเราเรียกใช้ฟังก์ชันทั้งสองดังโปรแกรมด้านล่างนี้
---src[cpp]
int x = 10;
int y = 100;
m1(x,y); // (3)
m2(x,y); // (4)
---
เมื่อบรรทัดที่ 3 ทำเงานเสร็จ ตัวแปร {\ct y} จะมีค่า 100 เท่าเดิม แม้ว่าภายในฟังก์ชัน
{\ct m1} ตัวแปร b จะมีค่าเป็น 110 ก็ตาม อย่างไรก็ตามในการเรียกฟังก์ชัน {\ct m2}
พารามิเตอร์ {\ct b} จะอ้างถึงตัวแปร {\ct y} ทำให้เมื่อมีการเปลี่ยนแปลงค่าตัวแปร
{\ct b} แล้ว ก็เป็นการเปลี่ยนแปลงค่าในตัวแปร {\ct y} ไปด้วย
การใช้ reference ลดความซับซ้อนในการเขียนฟังก์ชันที่ต้องการส่งผลลัพธ์กลับทางพารามิเตอร์
ตัวแปรแบบ reference มีความสัมพันธ์กับตัวแปรแบบพอยน์เตอร์มาก
เราจะอธิบายความสัมพันธ์นี้เพิ่มเติมในส่วน~\ref{sect:array-pointer-c}
ส่วนของโปรแกรม~\ref{code:array-list-find} แสดงฟังก์ชัน {\ct list\_find}
ที่ค้นหาข้อมูลในรายการและฟังก์ชัน {\ct list\_append}
ที่เพิ่มข้อมูลเข้าไปตอนท้ายของรายการ
ถ้าสังเกตบรรทัดที่ 12 จะพบว่าเราแจ้งความผิดพลาดระหว่างการทำงาน
เมื่ออาร์เรย์มีขนาดไม่พอ โดยการใช้ exception (ใช้คำสั่ง {\ct throw})
\begin{figure}
---src[cpp,ฟังก์ชัน {\ct list\_find} และ {\ct list\_append},code:array-list-find]
int list_find(int list[], int size, int q)
{
for(int i = 0; i < size; ++i)
if(list[i] == q)
return i;
return -1;
}
void list_append(int list[], int& size, int val)
{
if(size >= max_size)
throw "List overflow"; // Line 12
list[size] = val;
++size;
}
---
\end{figure}
---q ฟังก์ชันหาค่ามากที่สุด
จงเขียนฟังก์ชัน {\ct list\_max} ที่รับรายการและคืนค่าดัชนีของข้อมูลที่มากที่สุดในรายการ
---
เราจะเขียนฟังก์ชัน {\ct list\_delete} ที่ลบข้อมูลดัชนี $i$ ออกจากอาร์เรย์
---q ฟังก์ชัน {\ct list\_delete}
จงเขียนฟังก์ชัน {\ct list\_delete(int list[], int\& size, int i)}
ที่รับรายการและดัชนี {\ct i} ของข้อมูลที่ต้องการลบ
และลบข้อมูลนั้นออกจากรายการโดยยังรักษาให้ของข้อมูลต่าง ๆ ยังเรียงลำดับกันเหมือนเดิม
===
แสดงในโปรแกรม~\ref{code:array-list-delete}
---
\begin{figure}
---src[cpp,ฟังก์ชัน {\ct list\_delete},code:array-list-delete]
void list_delete(int list[], int& size, int i)
{
if((i < 0) || (i >= size))
throw "Invalid index";
for(int j = i; j < n-1; ++j)
list[j] = list[j+1];
--size;
}
---
\end{figure}
---q เวลาการทำงานของ {\ct list\_delete}
สมมติให้คำสั่งทุกบรรทัดทำงานโดยใช้เวลา 1 หน่วยเท่ากัน จงวิเคราะห์เวลาการทำงานของ
{\ct list\_delete}
---
---q ฟังก์ชัน {\ct list\_delete} ที่ไม่รักษาลำดับ
ถ้าเราไม่จำเป็นต้องรักษาลำดับของข้อมูลในรายการที่เหลือให้เรียงกันเหมือนเดิม
เราสามารถเขียนฟังก์ชัน {\ct list\_delete} ขึ้นใหม่
ให้ทำงานโดยใช้เวลาที่ไม่ขึ้นกับขนาดของรายการในพารามิเตอร์ {\ct size} ได้
จงเขียนฟังก์ชันดังกล่าว
---
ตัวอย่างฟังก์ชันด้านต้น นำไปพัฒนาฟังก์ชันสำหรับลบข้อมูลในกรณีทั่วไปได้ไม่ยากนัก
---q *
จงเขียนฟังก์ชัน {\ct list\_delete\_data(int list[], int\& size, int x)}
ที่รับรายการและข้อมูล {\ct x} แล้วลบข้อมูลดังกล่าวตัวแรกออกจากรายการ
(ลบเฉพาะการปรากฏครั้งแรกในรายการ) ให้เขียนโดยเรียกใช้ฟังก์ชันด้านบน แทนที่จะเขียนใหม่ทั้งหมด
---
---q *
จงเขียนฟังก์ชัน {\ct list\_delete\_all\_data(int list[], int\& size, int
x)} ที่รับรายการและข้อมูล {\ct x} แล้วลบข้อมูลดังกล่าวทั้งหมดออกจากรายการ
สำหรับข้อนี้ เพื่อประสิทธิภาพสามารถเขียนฟังก์ชันขึ้นมาใหม่ได้
---
สำหรับคำถามด้านบน ผู้อ่านอาจจะสังเกตได้ว่า แทนที่จะเขียนฟังก์ชัน {\ct
list\_delete\_all\_data} ขึ้นมาใหม่ทั้งหมด เราสามารถเขียนโดยเรียกฟังก์ชัน {\ct
list\_delete\_data} ได้
ดังโปรแกรม~\ref{code:array-delete-all-from-delete-data}
ในบทที่~\ref{chapter:analysis}
เราจะวิเคราะห์เปรียบเทียบประสิทธิภาพวิธีการเขียนทั้งสองแบบ
\begin{figure}
---src[cpp,ตัวอย่างการเขียนฟังก์ชัน {\ct list\_delete\_all\_data} แบบหนึ่ง,code:array-delete-all-from-delete-data]
void list_delete_all_data(int list[], int& size, int x)
{
int os;
do {
os = size;
list_delete_data(list, size, x);
} while(os != size);
}
---
\end{figure}
\subsection{อาร์เรย์หลายมิติ}
TODO: เขียนส่วนนี้
\section{พอยน์เตอร์และการใช้งานในภาษา C++}
\label{sect:array-pointer-c}
เนื่องจากพอยน์เตอร์เป็นชนิดข้อมูลที่ใกล้ชิดกับสถาปัตยกรรมของคอมพิวเตอร์มากที่สุดในภาษา
C++ เราจะเริ่มโดยศึกษาโครงสร้างการเก็บข้อมูลในหน่วยความจำคอมพิวเตอร์กันก่อน
คอมพิวเตอร์เก็บข้อมูลแบบดิจิทัล หน่วยย่อยที่สุดของข้อมูลแบบดิจิทัลคือบิต (bit ย่อมาจาก
binary digit) ซึ่งเป็นข้อมูลที่มีสองสถานะ โดยมากจะแทนด้วย 0 และ 1 หรือปิดกับเปิด
แต่อาจจะเป็นอย่างอื่นก็ได้เช่น มีแสง ไม่มีแสง, ศักย์ไฟฟ้าสูง ศักย์ไฟฟ้าต่ำเป็นต้น
หน่วยความจำคอมพิวเตอร์ในปัจจุบันเก็บข้อมูลหลายล้านบิต
การอ้างถึงข้อมูลจำนวนมากเหล่านั้นกระทำผ่านทางระบบเรียกที่อยู่ (address)
กล่าวคือข้อมูลที่อ้างถึงได้ทุกหน่วยจะมีที่อยู่เฉพาะใช้สำหรับอ้างถึง
ลักษณะการอ้างถึงข้อมูลเช่นนี้ก็ไม่ต่างจากการที่เราใช้ดัชนีในการอ้างถึงข้อมูลในอาร์เรย์นั่นเอง
อย่างไรก็ตาม ในการกำหนดที่อยู่นั้น จะไม่ได้กำหนดให้กับข้อมูลทุกบิตโดยตรง
เนื่องจากบิตเป็นหน่วยที่เล็กเกินไปในหลาย ๆ กรณี แต่จะกำหนดให้กับกลุ่มของบิตที่เรียงกัน
กลุ่มละ 8 บิต ซึ่งเรียกว่าไบท์ (byte) ซึ่งสามารถพิจารณาเป็นเลขฐานสอง 8 หลักก็ได้
ตัวอย่างของการเก็บข้อมูลแสดงดังรูปที่~\ref{fig:array-memory-as-array}
\begin{figure}
\begin{center}\begin{tabular}{|c|c|c|}
\hline
\hline
ตำแหน่ง & ข้อมูลเป็นบิต & ข้อมูลถ้าพิจารณาเป็นตัวเลข\\
\hline
\hline
0 & 0000 0000 & 0 \\
\hline
1 & 0000 1111 & 15 \\
\hline
$\vdots$ & $\vdots$ & $\vdots$ \\
\hline
100 & 1001 0010 & 146 \\
\hline
101 & 1111 1111 & 255 \\
\hline
102 & 0001 0000 & 16 \\
\hline
103 & 0110 0100 & 100 \\
\hline
$\vdots$ & $\vdots$ & $\vdots$ \\
\hline
\end{tabular}\end{center}
\caption{ตัวอย่างการเก็บข้อมูลในหน่วยความจำพร้อมด้วยที่อยู่}
\label{fig:array-memory-as-array}
\end{figure}
ข้อมูลที่เก็บในหน่วยความจำหลายชนิดอาจจะมีขนาดใหญ่เกินกว่าจะเก็บได้ใน 1 ไบท์
เช่นข้อมูลประเภท {\ct int} ในภาษา C++
โดยมากข้อมูลเหล่านั้นก็จะถูกจัดเก็บอยู่ในหลายไบท์เรียงต่อกัน
รูปแบบและวิธีการจัดเก็บเหล่านี้อยู่นอกขอบเขตของหนังสือเล่มนี้
ผู้อ่านที่สนใจสามารถอ่านเพิ่มเติมได้ในหนังสือสถาปัตยกรรมคอมพิวเตอร์ทั่วไป
ข้อมูลประเภทพอยน์เตอร์เป็นข้อมูลสำหรับเก็บตำแหน่งของหน่วยความจำ
เพื่อใช้อ้างถึงข้อมูลที่อยู่ในตำแหน่งดังกล่าว ในบางภาษาเช่น Java หรือ C\#
ก็มีการใช้งานข้อมูลชนิดนี้ในการอ้างถึงข้อมูลที่เป็นวัตถุแต่เรียกว่าเป็นการอ้างถึง (reference)
สมมติว่าตัวแปร {\ct x} ใช้เนื้อที่ในหน่วยความจำที่ตำแหน่ง 100 และเก็บค่า 146
ถ้าตัวแปรแบบพอยน์เตอร์ {\ct p} ใช้เนื้อที่ในหน่วยความจำที่ตำแหน่ง 103 และ {\em ชี้}
ไปที่ตัวแปร {\ct x} ตัวแปร {\ct p} จะเก็บค่า 100 สำหรับการทำความเข้าใจทั่วไป
ข้อมูลประเภทนี้มักเขียนแทนด้วยช่องที่มีลูกศร เพื่อแสดงการชี้ไปยังตำแหน่งของข้อมูลอื่น ๆ
ดังตัวอย่างในรูป~\ref{fig:array-example-pointer}
\begin{figure}
\begin{center}
\epsfig{file=figures/arrays/pointers1.eps, height=0.75in}
\end{center}
\caption{แผนภาพแสดงพอยน์เตอร์ {\ct p}}
\label{fig:array-example-pointer}
\end{figure}
\subsection{การประกาศชนิดข้อมูล โอเปอเรเตอร์ {\ct *} และ {\ct \&}}
วิธีการประกาศและใช้ข้อมูลประเภทนี้ขึ้นกับภาษาโปรแกรมที่ใช้ สำหรับภาษา C++
เราใช้เครื่องหมาย {\ct *} ในการระบุชนิดข้อมูล กล่าวคือเราจะเขียน
\begin{center}
ชนิดข้อมูล{\ct *}
\end{center}
เพื่อระบุว่าเป็นพอยน์เตอร์ไปยังชนิดข้อมูลดังกล่าว ยกตัวอย่างเช่น
\begin{center}
{\ct int* p;}
\end{center}
เป็นการประกาศตัวแปร {\ct p} ที่เป็นพอยน์เตอร์ไปยังข้อมูลชนิด {\ct int}
ตัวแปรประเภทพอยน์เตอร์จะต้องอ้างถึงตำแหน่งในหน่วยความจำ
เราจะใช้โอเปอเรเตอร์แบบนำหน้า {\ct \&}
ในการอ้างถึงตำแหน่งในหน่วยความจำของตัวแปรหรือข้อมูล ดังแสดงในตัวอย่างด้านล่าง
---src[cpp]
int x = 146;
int* p = &x; // Line 2
---
หลังการทำงานในบรรทัดที่ 2 ตัวแปร {\ct p} จะเก็บตำแหน่งในหน่วยความจำของตัวแปร
{\ct x} หรือเราจะกล่าวว่า {\ct p} ชี้ไปที่ตัวแปร {\ct x}
ต่อไปถ้าเราอ้างถึงตัวแปร {\ct p} เราจะหมายถึง ``ตำแหน่ง'' ของข้อมูลในหน่วยความจำ
ถ้าเราต้องการอ้างถึง ``ข้อมูล'' ในหน่วยความจำตำแหน่งนั้น เราจะใช้โอเปอเรเตอร์นำหน้า
{\ct *} ยกตัวอย่างเช่นในโปรแกรมด้านล่าง
---src[cpp]
cout << *p; // Line 1
*p = 1000; // Line 2
cout << x; // Line 3
---
โปรแกรมในบรรทัดที่ 1 จะพิมพ์ค่า 146 เนื่องจากตัวแปร {\ct p} ชี้ไปที่ตำแหน่งของตัวแปร
{\ct x} ที่มีค่า 146 เมื่อเราอ้างถึง ``ข้อมูล'' ที่ตำแหน่งที่ {\ct p} เก็บอยู่
เราจึงได้ค่าเป็น 146
การอ้าง {\ct *p} หมายถึงข้อมูลในตำแหน่งหน่วยความจำที่ตัวแปร {\ct p} ชี้อยู่
ดังนั้นโปรแกรมในบรรทัดที่ 2 ก็จะเป็นการกำหนดค่าให้กับหน่วยความจำที่เดียวกับตัวแปร {\ct
x} ทำให้โปรแกรมในบรรทัดที่ 3 พิมพ์ค่า 1000 ออกมา
สังเกตว่าเครื่องหมาย {\ct *} ในคำสั่ง {\ct int* p = \&x;} กับ {\ct *p =
1000;} มีความหมายต่างกัน ในตัวอย่างแรกเป็นการขยายชนิดข้อมูล {\ct int}
เพื่อระบุชนิดข้อมูลว่าเป็นพอยน์เตอร์ไปยังจำนวนเต็ม
โดยมีการกำหนดค่าเริ่มต้นด้วยเครื่องหมายเท่ากับ ในตัวอย่างที่สอง เครื่องหมาย {\ct *}
เป็นโอเปอเรเตอร์แบบนำหน้า ที่กระทำกับตัวแปร {\ct p} ในตัวอย่างแรก ถ้าเราไม่กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์ {\ct p} ทันทีเมื่อประกาศ โปรแกรมจะเขียนได้ดังนี้
---src[cpp]
int* p;
p = &x;
---
โอเปอเรเตอร์ {\ct *} กับ {\ct \&} เป็นโอเปอเรเตอร์ที่ทำหน้าที่ตรงข้ามกัน
ถ้าพิจารณาตามแผนภาพในรูปที่~\ref{fig:array-example-pointer} โอเปอเรเตอร์
{\ct *} จะพาเราไปตามลูกศร ส่วน {\ct \&} จะพาเราย้อนกลับ
---q *
นิพจน์ {\ct *(\&x) = 1234;} มีความหมายอย่างไร?
---
---q *
สำหรับตัวแปร {\ct x} ที่ประกาศและกำหนดค่าเริ่มต้นด้วยคำสั่ง {\ct int x = 146;}
นิพจน์ {\ct \&x} หมายถึงตำแหน่งในหน่วยความจำของ {\ct x} นิพจน์ {\ct \&(\&x)} หมายถึงอะไร?
===
นิพจน์ดังกล่าวไม่มีความหมาย และจะทำให้เกิดความผิดพลาดระหว่างการคอมไพล์
เพื่อความเข้าใจที่ชัดเจนยิ่งขึ้น กรุณาอ่านส่วน~\ref{sect:array-lval-rval}
---
ผู้ที่ใช้งานพอยน์เตอร์นั้นจะต้องระวังเป็นพิเศษในการจัดการหน่วยความจำ
โดยเฉพาะเกี่ยวกับสถานะของหน่วยความจำที่พอยน์เตอร์นั้นชี้ไป
พิจารณาตัวอย่างในโปรแกรมย่อยด้านล่าง
---src[cpp]
int* crazy(int x)
{
int y = x + 10; int* z = &y;
return z;
}
---
ฟังก์ชันดังกล่าวคืนค่าพอยน์เตอร์ไปยังตัวแปร {\ct y} ซึ่งเป็นตัวแปรภายในของฟังก์ชัน {\ct
crazy}
ตัวแปรประเภทนี้โดยทั่วไปจะถูกเก็บในหน่วยความจำที่กันเนื้อที่ไว้แค่ช่วงที่ฟังก์ชันทำงานเท่านั้น
เมื่อฟังก์ชันจบการทำงานลง หน่วยความจำส่วนนี้ก็อาจจะถูกใช้โดยตัวแปรอื่น ๆ อย่างไรก็ตาม
พอยน์เตอร์ที่คืนมาก็ยังชี้ไปที่ตำแหน่งเดิมของตัวแปร {\ct y} อยู่
ทำให้เมื่ออ่านเขียนข้อมูลในตำแหน่งนั้น
อาจจะเกิดปัญหาไปเขียนทับข้อมูลของส่วนอื่นของโปรแกรมได้
\subsection{การจองหน่วยความจำ: โอเปอเรเตอร์ {\ct new} และโอเปอเรเตอร์ {\ct delete}}
นอกจากที่จะให้พอยน์เตอร์ชี้ไปยังตัวแปรต่าง ๆ แล้ว
เรายังสามารถจองหน่วยความจำเพื่อเก็บข้อมูลโดยเฉพาะได้ด้วยโอเปอเรเตอร์ {\ct new}
หน่วยความจำที่ขอจองมาได้นี้จะเป็นหน่วยความจำที่ระบบเชื่อว่ายังไม่มีการใช้
ทำให้เราสามารถใช้เนื้อที่เหล่านี้เก็บข้อมูลได้ตามต้องการ
โอเปอเรเตอร์ {\ct new} นอกจากจะจองหน่วยความจำสำหรับข้อมูลแล้ว
ยังกำหนดค่าเริ่มต้นให้กับข้อมูลดังกล่าวก่อนที่จะคืนพอยน์เตอร์กลับมา
หน่วยความจำที่จองมานี้ เมื่อไม่ใช้แล้วจะต้องถูกปล่อยคืนให้กับระบบด้วยโอเปอรเรเตอร์ {\ct
delete} เพื่อเก็บไว้จัดสรรในครั้งต่อ ๆ ไป พิจารณาตัวอย่างการใช้งานดังนี้
---src[cpp]
int* p = new int;
int* q = p; // Line 2
p = new int; // Line 3
// ... Line 4
// ... do something
delete p;
delete q;
---
เมื่อโปรแกรมทำงานผ่านบรรทัดที่ 2 พอยน์เตอร์ {\ct p} และ {\ct q}
จะชี้ไปยังตำแหน่งที่จองไว้ในหน่วยความจำเดียวกัน เมื่อถึงบรรทัดที่ 4
ตัวแปรทั้งสองจะชี้ไปยังหน่วยความจำคนละที่ เนื่องจากบรรทัดที่ 3
เราได้จองหน่วยความจำใหม่ให้กับ {\ct p} เมื่อโปรแกรมทำงานเสร็จ เราก็จะสั่ง {\ct
delete} เพื่อให้ระบบคืนค่าหน่วยความจำที่จองไว้ทั้งสองหน่วย
พิจารณาตัวอย่างโปรแกรมด้านล่าง
---src[cpp]
int c = 0;
for(int i = 0; i < N; ++i) {
int* p = new int;
p = c + i;
c = p;
}
---
---q *
โปรแกรมข้างต้นทำงานอะไร ถ้าตัวแปร {\ct N} มีค่ามาก ๆ โปรแกรมดังกล่าวจะทำให้เกิดอะไรขึ้น
---
ความสามารถในการจองหน่วยความจำเมื่อโปรแกรมทำงานนี้เป็นสิ่งที่จำเป็นมากในการพัฒนาโครงสร้างข้อมูลที่ซับซ้อนขึ้นต่อไป
อย่างไรก็ตาม ถ้าเราไม่ระมัดระวังพอและไม่คืนหน่วยความจำที่จองไว้เมื่อเลิกอ้างถึงแล้ว
เราอาจจะพบปัญหาโปรแกรมใช้หน่วยความจำมากเกินไปเนื่องจากมีการรั่วไหลของการใช้งานหน่วยความจำก็ได้
(เรียกว่า memory leak)
ในภาษา C++
เราสามารถซ่อนการทำงานของโครงสร้างข้อมูลรวมถึงการจองและคืนหน่วยความจำไว้ภายในคลาส
ถ้าพัฒนาอย่างถูกวิธี จะช่วยลดปัญหาหน่วยความจำรั่วไหลได้
\subsection{พอยน์เตอร์ว่าง}
นอกจากเราจะกำหนดค่าใหัตัวแปรพอยน์เตอร์ชี้ไปที่ตำแหน่งต่าง ๆ
ในหน่วยความจำโดยใช้โอเปอเรเตอร์ {\ct\&} แล้ว
เรายังสามารถกำหนดให้ตัวแปรพอยน์เตอร์มีสถานะเป็น ``ไม่ได้ชี้ไปที่ไหน''
ได้โดยการกำหนดค่า {\ct 0} ให้กับตัวแปรพอยน์เตอร์นั้น\footnote{ในมาตรฐาน C++11
มีการนิยามค่าคงที่ {\ct nullptr}
เพื่อใช้แทนพอยน์เตอร์ว่างเพื่อแก้ปัญหาการใช้ค่าคงที่ซ้ำซ้อน อย่างไรก็ตาม
เพื่อให้หนังสือนี้ใช้งานได้กับคอมไพเลอร์ที่ยังไม่ปรับรุ่นให้ทันมาตรฐานใหม่นี้
เราจะยังใช้ค่าคงที่ {\ct 0} เพื่อแทนพอยน์เตอร์ว่างอยู่ ถ้าผู้อ่านใช้คอมไพเลอร์รุ่นใหม่แล้ว
ขอแนะนำให้ใช้ {\ct nullptr} แทน {\ct 0}}\footnote{ในภาษา C นิยมใช้ค่าคงที่
{\ct NULL} ที่นิยามไว้ในไฟล์หัวมาตรฐาน อย่างไรก็ตาม เราสามารถใช้ค่าคงที่ 0 ใน
C++ ได้เลย} พอยน์เตอร์ดังกล่าวเรียกว่าเป็น{\em พอยน์เตอร์ว่าง} ({\em null
pointer})
พอยน์เตอร์ที่มีค่าเป็นพอยน์เตอร์ว่างนี้ ในภาษา C++
ไม่ได้ทำงานแตกต่างจากพอยน์เตอร์ธรรมดาเท่าใดนัก นั่นคือ
โปรแกรมสามารถเรียกหาค่าที่ชี้โดยพอยน์เตอร์ดังกล่าวได้
ผลลัพธ์ที่ได้ขึ้นกับคอมไพเลอร์และระบบปฏิบัติการที่ใช้ แต่โดยทั่วไปการเรียกอ่านค่าตำแหน่งที่ 0
มักจะถูกป้องกันไว้ด้วยระบบปฏิบัติการ ทำให้โปรแกรมที่เรียกใช้ดังกล่าว crash ได้เป็นต้น
อย่างไรก็ตาม ภาษา C/C++ รับประกันว่าพอยน์เตอร์ว่างสองตัวจะเปรียบเทียบได้เท่ากัน
ถึงแม้จะเป็นพอยน์เตอร์คนละชนิดก็ตาม
\subsection{ชนิดข้อมูลแบบ {\ct void} และพอยน์เตอร์ไปยัง {\ct void}}
ชนิดข้อมูล {\ct void} เป็นชนิดข้อมูลพิเศษที่ไม่มีข้อมูลใดเป็นสมาชิก
การประกาศว่าฟังก์ชันคืนค่าเป็นข้อมูลชนิดนี้คือการประกาศว่าฟังก์ชันดังกล่าวไม่คืนค่า
นอกจากเราจะใช้ {\ct void} เพื่อระบุฟังก์ชันแล้ว พอยน์เตอร์ไปยัง {\ct void}
(ชนิดข้อมูล {\ct void*})
แทนพอยน์เตอร์ที่ชี้ไปยังตำแหน่งในหน่วยความจำที่เราไม่สนใจว่าจะเป็นข้อมูลชนิดใด
เราสามารถกำหนดค่าพอยน์เตอร์ไปยังข้อมูลใด ๆ ให้กับพอยน์เตอร์ประเภท {\ct void*} ได้
และพอยน์เตอร์ประเภท {\ct void*} ก็สามารถถูกแปลง (cast) เป็นพอยน์เตอร์ประเภทอื่น
ๆ ได้ อย่างไรก็ตามการแปลงในลักษณะนี้
ถ้าไม่ระวังอาจก่อให้เกิดข้อผิดพลาดระหว่างการทำงานได้
\subsection{พอยน์เตอร์กับการส่งพารามิเตอร์}
เราสามารถใช้พอยน์เตอร์เพื่อส่งค่าผ่านพารามิเตอร์ในลักษณะเดียวกับการส่งแบบ pass by
reference ได้ พิจารณาฟังก์ชันด้านล่างที่สลับค่าในตัวแปรสองตัว
---src[cpp]
void swap1(int& a, int& b)
{
int t = a;
a = b;
b = t;
}
---
ฟังก์ชันนี้ทำงานได้ตามที่เราต้องการ เนื่องจากชนิดข้อมูลของพารามิเตอร์ {\ct a} และ {\ct
b} คือ {\ct int\&} ฟังก์ชันดังด้านล่างจะไม่สามารถสลับค่าในตัวแปรที่ส่งมาได้
แม้ว่าค่าในตัวแปร {\ct a} และ {\ct b} จะเปลี่ยนในฟังก์ชันก็ตาม
เพราะว่าการส่งค่าโดยปกติจะเป็นการส่งแบบ pass by value
---src[cpp]
void swap2(int a, int b) // broken
{
int t = a;
a = b;
b = t;
}
---
อย่างไรก็ตาม เนื่องจากเราต้องการเปลี่ยนแปลงค่าของอาร์กิวเมนท์ที่ส่งมาให้กับฟังก์ชัน
เราจำเป็นต้องอ้างถึงตำแหน่งของอาร์กิวเมนท์นั้น ด้านล่างเป็นฟังก์ชัน {\ct swap3}
ที่เขียนโดยใช้พอยน์เตอร์
---src[cpp]
void swap3(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
---
เนื่องจากฟังก์ชัน {\ct swap3} รับอาร์กิวเมนท์เป็นพอยน์เตอร์
การเรียกใช้งานก็จะยุ่งยากขึ้นเล็กน้อย ดังแสดงในโปรแกรมด้านล่าง
---src[cpp]
int x = 100;
int y = 1000;
swap3(&x, &y);
---
รูป~\ref{fig:array-swap} แสดงการชี้ของพอยน์เตอร์ในการเรียกใช้งานฟังก์ชัน {\ct swap3}
\begin{figure}
\begin{center}
\epsfig{file=figures/arrays/swap3.eps, height=1.2in}
\end{center}
\caption{พอยน์เตอร์ต่าง ๆ ในการเรียกใช้ฟังก์ชัน {\ct swap3}}
\label{fig:array-swap}
\end{figure}
---q *
ฟังก์ชัน {\ct swap1} และ {\ct swap3} แม้มีการทำงานที่เหมือนกัน การเรียกใช้งาน
{\ct swap3} นั้นดูยุ่งยากกว่า อย่างไรก็ตาม
มีบางกรณีที่การประกาศพารามิเตอร์ที่ต้องการแก้ไขด้วยพอยน์เตอร์ทำให้เรามีอิสระในการเรียกใช้งานมากกว่า กรณีนั้นคืออะไร?
===
ในกรณีของการส่งตัวแปรแบบ pass by reference
ทางฝั่งผู้เรียกใช้ฟังก์ชันจำเป็นต้องมีตัวแปรเพื่อส่งมายังพารามิเตอร์นี้
แต่ในกรณีของการส่งแบบพอยน์เตอร์
พารามิเตอร์ดังกล่าวจะเป็นพารามิเตอร์ที่สามารถละเอาไว้ได้โดยส่ง พอยน์เตอร์ว่าง {\ct 0}
มาแทน ดังนั้น ในการประกาศพารามิเตอร์ ถ้าพารามิเตอร์ใด จำเป็นต้องมีตัวแปรมารับค่า
เราควรจะใช้การประกาศแบบ pass by reference
ถ้าพารามิเตอร์นั้นไม่จำเป็นต้องมีอยู่จริงในบางกรณี
เราก็ควรจะประกาศรับพารามิเตอร์ด้วยพอยน์เตอร์แทน
---
\subsection{การคำนวณกับพอยน์เตอร์}
\label{sect:array-pointer-arith}
เราสามารถดำเนินการเชิงตัวเลขกับพอยน์เตอร์ได้ ปกติพอยน์เตอร์สำหรับชนิดข้อมูลใด ๆ
ก็จะใช้ชี้ไปยังตำแหน่งในหน่วยความจำของข้อมูลชนิดนั้น พิจารณาตัวอย่างโปรแกรมด้านล่าง