スゴ技

平成23年度特別基本情報技術者試験【問11】（その1）

Blog：IT・情報処理BLOG | 2011.07.11

ソフトⅡコース担当　ブログのおにーさまこと高橋です。

昨日は、基本情報技術者試験とＩＴパスポートの特別試験日でした。受験した人、できはどうだったでしょうか？

折角（？）なので、今日は基本上技術者試験の午後問１１、Ｊａｖａの問題を考えてみたいと思います。

この問題は、追加可能な文字の並びを配列と連結リストを用いて実装するというものです。問題文が長いので難しく感じるかもしれませんが、どのように文字が格納されているかを考えると、それほど複雑ではありません。

設問１

空欄ａ
配列で実装するArrayAppendableCharSequenceクラスのメソッドappendです。appendメソッドは、プログラムの説明（３）より、引数で指定した文字を、文字列の末尾に追加します。文字は、フィールドdataで参照する配列に格納します。配列の要素数は、生成時に指定します。無限に大きな配列を生成するわけにはいかないので、EXT_SIZEの倍数の大きさで生成することになっています。追加するとその内に配列に文字が詰まってしまうので、更にEXT_SIZE分大きな配列を生成し、現文字並びをコピーした上で追加します。空欄ａのある繰り返しは、1文字ずつコピーを行っていく繰り返しです。従って空欄ａには現文字並びの文字数が入ります。lengthかdata.lengthですが、解答群よりlengthとなります。

空欄ｂ
連結リストで実装するListAppendableCharSequenceクラスのメソッドcharAtです。charAtメソッドは、プログラムの説明（１）より、引数で指定した位置の文字を返します。文字は、連結リストの要素に格納されています。１つの要素にはEXT_SIZE文字ずつ、配列dataに格納されます。EXT_SIZEは10なので、例えば位置25の文字は、3番目（25÷10＋1）の連結リストの要素の位置5（25÷10の余り）です。getBucketメソッドにより、引数の位置にある文字が格納されている連結リストの要素を取得します。空欄ｂには、得た連結リストの要素内での位置が入ります。index%EXT_SIZEになります。

空欄ｃ
文字を追加するには、追加する文字を格納する連結リストの要素が必要です。追加する文字を格納する連結リストの要素は、最後の文字を格納している要素です。その上で、要素内の格納する位置（offset）が先頭（0）であれば、新しい要素を生成し、リストに追加します。新しい文字を追加する（最後の文字＋1を格納する）要素ではなく、最後の文字を格納している要素を求めるのは、文字が詰まっていて新しい要素を追加する場合に、新しい文字を格納する要素はまだ存在しないからです。（これから生成してリストに追加する）空欄ｃには、最後の文字の位置、length-1が入ります。

空欄ｄ
toStringメソッドは、プログラムの説明（４）より、文字の並びを文字列として返します。連結リストの要素ごとに、char型配列dataに文字をコピーします。最初の要素では、先頭から順にコピーします。2つ目の要素では、最初の要素に格納されていた文字数分進んだところからコピーします。3つ目の要素では、2つ目の要素に格納されていた文字数分更に進んだところからコピーします。各要素に格納されている文字数は、変数sizeに求めています。このsizeを使って、外側の繰り返しでlenの値を減らしています。空欄ｄには、各要素の文字をコピーし始める位置が入ります。length-lenとなります。

空欄ｅ
ArrayAppendableCharSequenceクラス、ListAppendableCharSequenceクラスのどちらでも使えるようにするには、インターフェースAppendableCharSequence型にします。AppendableCharSequence型にすることにより、このインターフェースを実現するクラスのオブジェクトを実引数として渡すことができます。また、インターフェースで宣言されている抽象メソッドは、変数名.メソッド名で実行できます。このとき、その変数で参照しているオブジェクトのメソッドが実行されます。つまり、１つのコードで、両方のクラスに対応できます。

それでは、設問２は次回にしたいと思います。それまでに、図を書くツールを探しておきたいと思います。言葉ばかりだとわかりにくい．．．