%===================================================================== % 秋田高専 2E 情報工学概論 テキスト %　　テーマ　サーチ % 本テキストの内容 % ・ % ・ % ・ % ・ %　　　 　・ % % last updated 2005.11.13 % created by Masashi Yamamoto % e-mail yamamoto@akita-nct.jp %===================================================================== \documentclass[10pt,a4paper]{jarticle} \usepackage{graphicx,amsmath,amssymb,ascmac,float} \usepackage{html, listings, jlisting} \oddsidemargin 0mm %左の余白 25.4mm-0mm　奇数ページ \evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ \textwidth 160mm \newcommand{\command}[1]{「\texttt{#1}」} \newcommand{\cl}[1]{\texttt{#1}} \newcommand{\tw}[1]{\texttt{#1}} % \newcounter{toi_num} \newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]} \addtocounter{toi_num}{1}} \newcommand{\qbox}[1]{ {\fboxsep=2pt\fboxrule=0.4pt\fbox{\hspace{3mm}{#1}\hspace{3mm}}} } % \renewcommand{\lstlistingname}{リスト} \lstset{language=C,% basicstyle=\footnotesize,% commentstyle=\textit,% classoffset=1,% keywordstyle=\bfseries,% frame=tRBl,framesep=5pt,% showstringspaces=false,% numbers=left,stepnumber=1,numberstyle=\footnotesize% }% % \begin{htmlonly} \usepackage{verbatimfiles} \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}} \end{htmlonly} % \begin{document} \title{リスト} \author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}} \date{2005年11月21日} \maketitle % % %===================================================================== \section{前回の復習と本日の学習内容} %===================================================================== %--------------------------------------------------------------------- \subsection{前回の復習} %--------------------------------------------------------------------- 先週は，サーチについて学習した．学習したサーチの方法は，以下の2通りの方法である． \begin{itemize} \item リニアサーチ \begin{quote} マッチするデータを端から，順に捜していく方法である．データがランダムに並 んでいる場合，この方法しかない．計算のオーダーは，$O(N)$である． \end{quote} \item バイナリーサーチ \begin{quote} まずは，データを規則に従って並び替える(ソート)．マッチするデータは，その 真ん中と比較して，候補を半分に絞る．これを繰り返すことにより，高速に候補 の数を減らし，サーチを行う．計算のオーダーは，$\log_2N$である． \end{quote} \end{itemize} % %--------------------------------------------------------------------- \subsection{本日の学習内容} %--------------------------------------------------------------------- 本日は，データ構造である．リストについて学習する．特に，配列との比較を行い，その 違いを理解しなくてはならない． 後期の最初の講義で述べたように，データ構造とはデータのメモリー上の表現方法のこと である．このことを忘れないで，講義を聴くように． % %===================================================================== \section{プログラムで解くべき問題} %===================================================================== リストと配列の違いを説明するために，教科書では次のような処理をするプログラムが書 かれている． \begin{itemize} \item 整数をキーボードから読み込む \item 読み込まれた整数の合計を表示する． \item ただし，ゼロが読み込まれると，読み込む整数の終わりとする． \end{itemize} 教科書のList 3-1〜List 3-3が配列を使った例である．List 3-4がリストを使った例であ る． いたって，単純な問題である．ただし，ここでは，読み込む毎に加算する方法は取らない こととする．読み込んだデータは，一旦，メモリーの中に記憶するものとする．さあ，ど うするか? % %===================================================================== \section{リストを使わない方法} %===================================================================== %--------------------------------------------------------------------- \subsection{固定長さの配列を使う方法} %--------------------------------------------------------------------- %------------------- \subsubsection{原理} %------------------- もっとも単純な方法は，配列に入力データを格納する方法である．教科書のList 2-1(p.70)の方法である．このプログラムをプリントのリスト\ref{prog:list_1}にフロー チャートを図\ref{fig:flow_1}に示す． このプログラムの大きな問題点は， \begin{itemize} \item データを10個以上，入力すると，プログラムがクラッシュする． \end{itemize} ことである．コンパイラーによって，予約した分以上のメモリーの領域にデータを書き込 むと，プログラムは異常な動作を行う\footnote{配列を越えて書き込みが行われないよう にするのはプログラマーの仕事である．}． それで，最初から配列を大きくする方法もある．ただ，データ数が分からないと，それも 限界がある．とてつもなく大きな配列を用意することも考えられるが，そうすると次の問 題が生じる． \begin{itemize} \item メモリー領域の大部分に値が格納されないことが生じ，メモリーの無駄遣いにな る． \end{itemize} このようにデータ数が分からない場合，配列を使うのははなはだ無駄が生じやすい． % %---------------------------- \subsubsection{フローチャート} %---------------------------- 教科書のList 3-1(p.70-71)あるいはこのプリントのリスト\ref{prog:list_1}のプログラム のフローチャートを図\ref{fig:flow_1}に示す． このプログラムは，おもに， \begin{itemize} \item キーボードの整数を配列に格納する． \item 格納された配列を合計する． \end{itemize} から構成される．このプログラムのもっともまずい点は，配列の終わりを確認しないで， データを格納しているところである\footnote{この本の筆者の弁護をしておこう．これほ どの本を書く人であるから，当然分かっている．読者に分かりやすくするために，本論か ら外れる部分は省いたと考えられる．}．普通のプログラマーであれば，確実に配列の大きさ を確認しながら，データを格納する． % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=1.0] {figure/flow_1.eps} \caption{固定長の配列を使うリスト\ref{prog:list_1}のフローチャート．} \label{fig:flow_1} \end{center} \end{figure} % %------------------------ \subsubsection{プログラム} %------------------------ 固定長の配列を使うプログラムのリスト\ref{prog:list_1}に示す．これは，教科書の List 3-1(p.70-71)と同じである．ここで使われているプログラムのテクニックは，すで に学習済みであるが，分かりにくいものだけ述べておく． \begin{itemize} \item 2行目 \tw{\#include }\vspace{-3mm} \begin{quote} これは，コンパイルの作業を行う前に，ソースファイルに，\tw{stdlib.h}というヘッ ダーファイルを取り込む命令(プリプロセッサー) である．このプログラムでは， \tw{main}関数の戻り値を\tw{EXIT\_SUCCESS}としている．\tw{EXIT\_SUCCESS}の定義 が\tw{stdlib.h}に書かれている．私のコンパイラーでは， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} #define EXIT_SUCCESS 0 \end{verbatim} \end{quote}\vspace{-5mm} となっていた．戻り値を示すリスト\ref{prog:list_1}の32行目は， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} return 0; \end{verbatim} \end{quote}\vspace{-5mm} と同じである． \end{quote} % \item 4行目 \tw{\#define NMAX 10} \begin{quote} これもプリプロセッサーで，ソースプログラムをコンパイルする前に，文字列 \tw{NMAX}を10に置き換える．文字列を置き換えるので，これを文字列置換と言う．いっ ぺんに多くの文字列や値を置き換えたいときに便利である．置き換える元の文字をすべ て大文字で書くのが習慣となっている． \end{quote} % \item 16行目 \tw{if(buf)} \begin{quote} これには，比較の演算子がない．変数\tw{buf}の値の真/偽を判断することになる．最 初，\tw{if}文を学習したときのことを思い出してほしい．C言語では， \begin{itemize} \item 値が0の時は，偽である． \item 値が0以外の時は，真である． \end{itemize} となっていた． \end{quote} \item 25行目 \tw{sum=n=0} \begin{quote} 代入演算子(\tw{=})は右辺から評価していく．このことから，この文は次のように解釈する． \begin{itemize} \item \tw{n=0}が実行される．すなわち，\tw{n}に\tw{0}が代入される． \item \tw{n=0}という文の値は\tw{0}となる．この\tw{0}が\tw{sum}に代入される． \end{itemize} \end{quote} \end{itemize} % \lstinputlisting[caption=固定長の配列を使い合計を計算するプログラム,label=prog:list_1] {program/list3-1e.c} % %--------------------------------------------------------------------- \subsection{配列のサイズを実行の最初に決める} %--------------------------------------------------------------------- %------------------- \subsubsection{原理} %------------------- ユーザーに合計を計算するデータの数を最初に聞いて，その分，配列を用意する方法であ る．通常であれば，これは良い方法である．一般的に，よく使われる方法である． ただし，最初に決めた配列をこえてのデータ入力ができない．ユーザーの気が変わって， データ数を増加させるときに問題が発生する．さらに，ユーザー自身，データの個数が分 からないときには，対応ができない． % %---------------------------- \subsubsection{フローチャート} %---------------------------- 教科書のList 3-2(p.72)あるいはこのプリントのリスト\ref{prog:list_2}のプログラム のフローチャートを図\ref{fig:flow_2}に示す． このプログラムは，おもに， \begin{itemize} \item ユーザーが指定したデータ数分の配列領域を確保する． \item キーボードの整数を配列に格納する． \item 格納された配列を合計する． \end{itemize} から構成される．このプログラムも，配列のサイズを確認しないで，配列にデータを格納 している．これは問題である． % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=1.0] {figure/flow_2.eps} \caption{最初に配列のサイズを決めるプログラムのリスト\ref{prog:list_1}のフローチャート．} \label{fig:flow_2} \end{center} \end{figure} % %------------------------ \subsubsection{プログラム} %------------------------ 最初に配列のサイズを決めてそれに値を代入するプログラムをリスト\ref{prog:list_2} に示す．これは，教科書のList 3-2(p.72)と同じである．ここで使われているプログラム のテクニックは，次の通りである． \begin{itemize} \item 12行目 \tw{array=(int *)malloc(sizeof(int)*count);}\vspace{-3mm} \begin{quote} 少々複雑に見えるが，処理される順に見ていけば簡単である． \begin{enumerate} \item 最初に\tw{sizeof(int)}が評価される．関数\tw{sizeof()}は，型のバイト数を 返す．ここでは，整数型\tw{int}のバイト数である4が返される． \item 次に，この4とデータ数である\tw{count}の乗算が行われる．この結果は，デー タを格納するために必要なバイト数の計算になっている． \item \tw{malloc()}関数は，\textit{Memory ALLOCate}(記憶割付)の略で，引数で渡 されたバイト数のメモリーを確保して，その先頭のポインター(アドレス)を返す． \item \tw{(int *)}はキャストと呼ばれる強制型変換である．\tw{malloc}で返される ポインターは強制的に整数型としている．従って，ポインターを+1加算すると， アドレスは4つ進むことになる． \item 整数型のポインター(アドレス)を整数型のポインター\tw{array}に代入してい る． \end{enumerate} \end{quote} % \item 7行目 \tw{int *array}と21行目 \tw{array[n]} \begin{quote} ポインターで宣言しているものを配列として使っている．これは，配列がどのように処 理されているか，考えればよく分かる．配列\tw{array[n]}は，\tw{*(array+n)}と評価 される．すなわち，配列\tw{array[n]}は，ポインター\tw{array}に\tw{n}加算したポ インター(アドレス)が示す値と言うことである．このようなことから，配列で宣言して いなくても，配列のように使うことができるのである． \end{quote} % \item 35行目 \tw{free(array);} \begin{quote} 関数\tw{free()}は，そのプログラムで使用しているメモリー領域を開放するた めにある．ここでは，12行目の\tw{malloc}で確保された領域を開放している． \end{quote} \end{itemize} % \lstinputlisting[caption=最初に配列サイズを決めてから，値を代入するプログラム．,label=prog:list_2] {program/list3-2e.c} % % %--------------------------------------------------------------------- \subsection{実行時に配列のサイズを拡張する} %--------------------------------------------------------------------- %------------------- \subsubsection{原理} %------------------- データの数が分からないので，最初に小さな配列を用意する．データ数が多く不足した 場合，さらに大きな配列を用意する方法である． この方法も良さそうですが，以下のような問題があります． \begin{itemize} \item 配列のコピー回数が多く，コストがかかりすぎる． \item コピー回数を減らすために，一度に多くの配列の領域を確保すると，大きな使わ れないメモリー領域ができてしまう可能性がある． \end{itemize} % %---------------------------- \subsubsection{フローチャート} %---------------------------- 教科書のList 3-3(p.74)あるいはこのプリントのリスト\ref{prog:list_3}のプログラム のフローチャートを図\ref{fig:flow_3}に示す． このプログラムは，おもに， \begin{itemize} \item キーボードの整数を配列に格納する． \begin{itemize} \item 配列の範囲を超える場合，より多くのメモリーを確保する． \item 確保された多くのメモリーに元のデータをコピーする． \item 不要になったメモリー領域は，解放する． \end{itemize} \item 格納された配列を合計する． \end{itemize} から構成される．このプログラムも，配列のサイズを確認しないで，配列にデータを格納 している．これは問題である． % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=1.0] {figure/flow_3.eps} \caption{番兵を使うリニアサーチのフローチャート．} \label{fig:flow_3} \end{center} \end{figure} % %------------------------ \subsubsection{プログラム} %------------------------ リスト\ref{prog:list_3}に示す．これは，教科書のList 3-3(p.74)と同じである． このプログラムで使われている主なテクニックは，以下の通りである． \begin{itemize} \item 3行目 \tw{\#include }\vspace{-3mm} \begin{quote} これは，30行目の\tw{memcpy()}関数を使うために必要で，その関数の宣言などが書か れている． \end{quote} \item 30行目 \tw{memcpy(temp, array, sizeof(int)*size)}\vspace{-3mm} \begin{quote} \tw{memcpy()}関数は，\textit{MEMory CoPY}(メモリー複写)の略で，メモリーの内容 をコピーする．ここでは，ポインター\tw{array}が示す場所から\tw{4*size}バイト分 のデータを，先頭をポインター\tw{temp}が示す場所としてコピーする． \end{quote} \end{itemize} \lstinputlisting[caption=実行時に配列のサイズを拡張する方法．,label=prog:list_3] {program/list3-3e.c} % %===================================================================== \section{リストを使う方法} %===================================================================== %--------------------------------------------------------------------- \subsection{配列とリストとの違い} %--------------------------------------------------------------------- リストと配列はともにデータの列をメモリーに確保するという点では似ている．ここで話 を簡単にするために，データは整数とする．データは整数の数列である．配列の場合，こ の数列はメモリーの連続した領域に格納される．そして，配列の添え字を使って，目的の データにアクセスする. それに対して，リストは前後のデータのある位置をメモリーに入れておく．それを元に数 列を構成する． ここのところの図は，本日間に合わなかったので，来週渡す． %--------------------------------------------------------------------- \subsection{リストを使ったプログラム} %--------------------------------------------------------------------- %------------------- \subsubsection{原理} %------------------- データを入力する毎に，新たにノードを作成して，そのノードにデータを格納している． 前後のデータの関係は，リストを用いて表現している． % %---------------------------- \subsubsection{フローチャート} %---------------------------- 教科書のList 2-1(p.37)あるいはこのプリントのリスト\ref{prog:list_1}のプログラム のフローチャートを図\ref{fig:flow_1}に示す． % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=0.85] {figure/flow_4.eps} \caption{リストを使ったプログラムのリスト\ref{prog:list_4}のフローチャート．} \label{fig:flow_4} \end{center} \end{figure} % %------------------------ \subsubsection{プログラム} %------------------------ 固定長の配列を使うプログラムのリスト\ref{prog:list_4}に示す．これは，教科書の List 3-4(p.75-77)と同じである． このプログラムで使われている主なテクニックは，以下の通りである． \begin{itemize} \item 5行目 \tw{typedef}\vspace{-3mm} \begin{quote} これは，\textit{TYPE DEFine}(型定義)と呼ばれるもので，型に別名をつける役割があ る．ここでは，\tw{struct tagListNode}と言う型を，\tw{ListNode}と呼ぶことにして いる．15行目にそれが使われている． \end{quote} % \item 17行目 \tw{lastnode=NULL}\vspace{-3mm} \begin{quote} これは，ヌルポインター，あるいは空ポインターと呼ばれるものである．これは， \tw{lastnode}が何も指し示していないことを保証するために，使っている． \end{quote} % \item 27行目 \tw{newnode->data=buf;}\vspace{-3mm} \begin{quote} \tw{newnode}はポインターである．ポインターが指し示す構造体のメンバーにアクセス する場合，アロー演算子(\tw{->})を使う．ここでは，ポインター\tw{newnode}が示す 構造体のメンバー\tw{data}に\tw{buf}の値を代入している．ポインターではなく，普 通の変数となっている構造体の場合，そのメンバーにアクセスするにはドット演算子 (\tw{.})を使う． \end{quote} \end{itemize} % \lstinputlisting[caption=リストを使ったプログラム,label=prog:list_4] {program/list3-4e.c} % %--------------------------------------------------------------------- \subsection{リストと配列の違い} %--------------------------------------------------------------------- \begin{table}[H] \caption{配列とリストとの違い} \label{table:diff_list_array} \begin{center} \begin{tabular}{lll} \hline & 配列 & リスト \\ \hline \hline データへのアクセス & 添え字によるランダムアクセス可能 & リストを順にたどる \\ アクセスのための計算量 & $O(1)$ & $O(N)$ \\ データの挿入/削除 & 計算コスト大($O(N)$) & 計算コスト小($O(1)$)\\ メモリーのコスト & 小 & 配列より大 \\ \hline \end{tabular} \end{center} \end{table} % %===================================================================== \section{練習問題} %===================================================================== \setcounter{toi_num}{1} \begin{quote} \begin{itemize} \item[\toi] クラスメイトの名前を読み込んで，読み込んだ逆の順にディスプレイに表 示するプログラムを作成せよ．ただし，プログラムは以下の通りとする． \begin{itemize} \item 名前はローマ字で，30文字以内とする． \item 名前のデータはリストで管理するものとする． \item 教科書のp.75 List 3-3(プリントのリスト\ref{prog:list_4})を 参考にすること． \end{itemize} \end{itemize} \end{quote} %===================================================================== % 参考文献 %===================================================================== \bibliographystyle{jplain} \bibliography{reference} %===================================================================== \end{document}