%=====================================================================
% ���Ĺ��� 2E ���󹩳س���
% 
% last updated 2005.11.27
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float,misc}
\usepackage{html, listings, jlisting}
\oddsidemargin 0mm  %����;�� 25.4mm-0mm������ڡ���
\evensidemargin 0mm %����;�� 25.4mm-0mm�������ڡ���
\textwidth 160mm
%
\newcommand{\command}[1]{��\texttt{#1}��}
\newcommand{\tw}[1]{\texttt{#1}}
\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{����ޤǤ�����(�����ֻ�˸�����)}
\date{2005ǯ11��28��}
\author{���ܾ���\thanks{��Ω���Ĺ��ȹ�������ع����ŵ����󹩳ز�}}
\maketitle
%
����ޤǤΡ��ؽ���ޤȤ�롣�����ֻ�ˤϡ����Υץ��Ȥ˽񤤤Ƥ������Ƥ�����
�����פळ�ȡ��������Ƥ�ʬ���äƤ��ʤ��Ԥϡ����ʤ��Ȥ�10���֤Ͻ��椷���ٶ����뤳
�ȡ��ɤ����Ƥ�����Ǥ��ʤ����ϡ����Ӥ��ɤ��Ԥ�ʹ���ʤꡤ���ե�����������Ѥ�
�ơ���˼��䤹�뤳�ȡ�
%=====================================================================
\section{���르�ꥺ��ȥǡ�����¤}
%=====================================================================
%---------------------------------------------------------------------
\subsection{���르�ꥺ��}
%---------------------------------------------------------------------
���르�ꥺ��ϡ������򤯤���μ�����᤿��ΤǤ��롥����ʳؤ�ʬ��Ǥϡ�����
�ԥ塼������Ȥä������򤯾��μ��Τ��Ȥ򤤤����ץ������ϡ����μ���ɽ��
������ΤǤ��롥���Τ��ᡤ���르�ꥺ��Ǥ�ۣ��ʤ��Ȥϵ����줺�����ʤ˼�����
�ʤ��ƤϤʤ�ʤ����������ʤ��ȡ��ץ������Ͻ񤱤ʤ���

�����򤯾�硤���������ʥ��르�ꥺ�ब�ͤ����뤬���ʲ��Τ褦�ʤ�Τ��ɤ�����
���ꥺ��Ǥ��롥
\begin{itemize}
 \item �׻����ᤤ�����ɤ����르�ꥺ��Ǥ��롥
 \item ���Ѥ�����꡼�������ʤ������ɤ����르�ꥺ��Ǥ��롥
\end{itemize}
%---------------------------------------------------------------------
\subsection{�ǡ�����¤}
%---------------------------------------------------------------------
�ǡ�����¤(data structure)�Ȥϡ��ǡ����Υ��꡼���ɽ����ˡ�Τ��Ȥ�����������ϡ�
����ޤǤˤ��������ʥǡ�����¤��ؽ��������ޤ��ϡ�C������Ѱդ���Ƥ��뼡�Τ褦
�ʤ�ΤǤ��롥
\begin{itemize}
 \item ñ�㷿�ѿ�
 \item ����
 \item ��¤��
\end{itemize}

����μ��ȤǤϹ�¤�Τ�Ȥä��ꥹ�Ȥȸ�����ǡ�����¤��ؽ�����������Ͻ��פǤ�
�롥
%
%=====================================================================
\section{�����ȤΥ��르�ꥺ��}
%=====================================================================
�����ȤȤϡ��ǡ����򤢤뵬§�ˤ����������֤��¤��ؤ��뤳�ȤǤ��롥�����Ǥϡ����
������¤������(����)�򾺽���¤��ؤ��뤳�Ȥ�ؽ�������
%
%---------------------------------------------------------------------
\subsection{�Х֥륽����}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
������٤ɤ��������Ǥ��羮����Ӥ��Ƥ�����򴹤��ʤ��饽���Ȥ�����ˡ�Ǥ��롥��
����1��������ʤ��ä��顤�����Ȥ���λ�Ǥ��롥����ϡ��������ͤΥǡ�����ˢ(�Х֥롨
bubble)�Τ褦���⤫��ǹԤ��褦�˸�����\footnote{����˥����Ȥ����硥}���Ȥ���
����̾�����Ĥ���줿��

�ꥹ��\ref{prog:buble_sort}������\tw{sort}�˳�Ǽ���줿�����򾺽���¤��ؤ���ץ�
�����Ǥ��롥���Υץ�������ư���ͤ��뤿��ˡ��ǡ�������\tw{N}�Ȥ��ơ�
\tw{sort[0]}��ü��\tw{sort[N]}��ü�Ȥ��롥����ȡ��ʲ��Τ��Ȥ�ʬ���롥
\begin{itemize}
 \item ��äȤ��ͤ��礭���ǡ����ϡ���¦��1��Υ롼��(5���ܤ�\tw{do})�Ǳ�ü�˰�ư���롥
 \item ���˰�ư���٤��������ǡ����ϡ����Υ롼�פǰ�Ĥ��Ĥ�����ư�Ǥ��ʤ������ΰ�Ĥ�
       �Ĥ�����ư�Ǥ��ʤ��Τǡ������¿���η׻������ɬ�פȤʤ롥
\end{itemize}

���Υץ������Ǥϡ�\tw{do}�롼�����11���ܤ�
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	if(sort[i]>sort[i+1])
 \end{verbatim}
\end{quote}\vspace{-5mm}
%
����äȤ�¿���¹Ԥ����ʸ�Ǥ��롥����ʸ�κǾ��¹Բ���ϡ��ǽ餫������Ǥ��Ƥ���
���Ǥ��롥���ΤȤ��Ρ��¹Բ���ϡ�$N-1$��Ǥ���Τ����餫�Ǥ��롥�ǰ��ξ��ϡ�
�Ǿ����ͤ���ü�ˤ�����Ǥ��롥���ξ��μ¹Բ���ϡ�$(N-1)^2$�Ȥʤ롥�ʤ��ʤ�
�С�
\begin{itemize}
 \item ���κǾ����ͤϡ�1��¦�Υ롼��(\tw{do}ʸ�ΤȤ���)��¹Ԥ�����ˡ���ĺ��˰�ư���롥
 \item ����ΰ��֤˰�ư���뤿��ˡ�$N-1$�󡤳�¦�Υ롼�פ�¹Ԥ���ɬ�פ����롥
 \item ��¦�Υ롼�פ�1��¹Ԥ�����ˡ���¦�Υ롼�פ�$N-1$�󡤼¹Ԥ���롥
\end{itemize}
�Ȥʤ뤫��Ǥ��롥

�ǽ�Υǡ������¤����ˤ�ꡤ$N-1$�󤫤�$(N-1)^2$�ޤǳ��������롥������֤�����
λ���֤Ȥκ��κ���δ����ͤ�׻����뤳�Ȥˤʤ뤬�������$(N-2)/2$���٤Ǥ�
�뤳�Ȥ�ʬ������������Ǿ��ͤν�����֤�����λ���֤Ȥκ��δ����ͤǤ��롥����
���٤Ȥ���ȡ������Ӥμ¹Բ���ϡ�
\begin{align}
 \frac{(N-1)(N-2)}{2}=\frac{N^2}{2}-\frac{3}{2}N+1
\end{align}
�Ȥʤ롥�ǡ�����$N$���礭����硤$N^2$�����㤷�Ʒ׻��̤����ä��롥

����$N^2$�����㤷�Ʒ׻��̤�ɬ�פʾ�硤$O(N^2)$�Ƚ񤯡�����ɽ��ˡ��
\textbf{$O$��ˡ}($O$-notation)�Ȥ������׻����������򼨤������ؤǻȤ��������ε�
��˻��Ƥ��롥�Х֥륽���Ȥη׻��Υ��������ϡ�$O(N^2)$�Ǥ��롥
%------------------------
\subsubsection{�ץ������}
%------------------------
���ʽ��List 1-1(p.3-4)�ΥХ֥륽���Ȥδؿ��ϡ��ꥹ��\ref{prog:buble_sort}���̤�
�Ǥ��롥�����\tw{main}�ؿ�����ƤӽФ����Ȥˤ�ꡤ����\tw{sort}�˳�Ǽ���줿����
��������¤��ؤ����롥
\begin{itemize}
 \item ����\tw{sort}�ϥ������Х��ѿ�\footnote{�ؿ��γ���������줿�Τǡ��ɤδؿ�
       ����Ǥ⥢�������Ǥ��롥}�ʤΤǡ��ؿ��ΰ����Ȥ����Ϥ��Ƥ��ʤ���
 \item ����θĿ�\tw{N}�ϡ�\tw{\#define}��Ϳ�����롥
 \item �����ؤ���������ȡ�\tw{flag}���ͤ�1�ˤʤ롥�����ؤ��������ʤ��Ȥ��ϡ�
       \tw{flag}���ͤ�0�Ǥ��롥����ϥե饰(flag:��)�ȸƤФ���Τǡ��׻��ξ���
       ��ɽ����
\end{itemize}
%
\lstinputlisting[caption=�Х֥륽���Ȥδؿ�,label=prog:buble_sort]
{program/buble_sort.c}
%
%---------------------------------------------------------------------
\subsection{�����å�������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�����Ĥ����Ǥ���Ȥ�����ͤ���礭�����롼�פȾ��������롼�פ�ʬ���롥ʬ����
�줿���롼�פ�Ʊ�ͤ���ˡ��ʬ���롥���ƤΥ��롼�פ����Ǥ�1�Ĥˤʤ�ޤǤ��κ�Ȥ�
���꤫���������ΤȤ������Ȥ���λ���롥���������ʥ����Ȥ���ǡ�ʿ��Ū�ˤϺ�®�Ǥ�
�뤫�顤����̾�����Ĥ��Ƥ��롥
%
%------------------------
\subsubsection{�ץ������}
%------------------------
���ʽ��List 1-3(p.8-9)�Υ����å������Ȥδؿ��ϡ��ꥹ��\ref{prog:quick_sort}���̤�
�Ǥ��롥�����\tw{main}�ؿ�����ƤӽФ����Ȥˤ�ꡤ����\tw{data}�˳�Ǽ���줿����
��������¤��ؤ����롥
\begin{itemize}
 \item �ؿ��ΰ����ϡ������Ȥ��������ξü(\tw bottom, top)�������ɽ���ݥ��󥿡�
       (\tw{*data})�Ǥ��롥
 \item ����Υݥ��󥿡�(\tw{*data})�ϡ�����̾�Ȥ��ƻȤ��롥
\end{itemize}
%
\lstinputlisting[caption=�����å������Ȥδؿ�,label=prog:quick_sort]
{program/quick_sort.c}
%---------------------------------------------------------------------
\subsection{�ޡ���������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�ǽ�˾��ʤ��Ŀ��ο�����¤��ؤ������롼�פ��롥���ˡ�2�ĤΥ��롼�פ�ʻ��(�ޡ�
��)���ơ�����礭���¤��ؤ���줿���롼�פ��롥����򷫤��֤����Ȥˤ�ꡤ�礭
�ʥ��롼�פ��Ǥ����ǽ�Ū�ˤϰ�ĤΥ��롼�פˤʤ��¤��ؤ�����λ���롥
%------------------------
\subsubsection{�ץ������}
%------------------------
%
\lstinputlisting[caption=�ޡ��������Ȥδؿ�,label=prog:merge_sort]
{program/merge_sort.c}
%---------------------------------------------------------------------
\subsection{�����ॽ����}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�Х֥륽���Ȥ��٤Ȥ���ӤΤ��ᡤ�������ͤϰ�Ĥ��Ĥ�����ư�Ǥ��ʤ�(����)����Ӥ�
��ֳ֤򹭤����ơ��쵤�˰�ư��������ˡ�������ॽ���ȤǤ��롥���Υ����ȤǤϡ�Ŭ��
�ʴֳ֤ǥХ֥륽���Ȥ�Ԥ������ˤ��δֳ֤򶹤����ˡ���Ȥ��롥�¸����顤�ֳ֤�
$1/1.3$���ľ��������Ƥ����Τ��ɤ��ȸ����Ƥ��롥�ǽ�Ū�ˤ��٤Ȥ����(�ֳ֤�1)��
�Ԥ����򴹤�������ʤ���Х����Ȥδ�λ�Ǥ��롥
%------------------------
\subsubsection{�ץ������}
%------------------------
%
\lstinputlisting[caption=�ޡ��������Ȥδؿ�,label=prog:comb_sort]
{program/comb_sort.c}
%
%---------------------------------------------------------------------
\subsection{ñ������������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�ޤ����ǽ�ο����2�Ĥ���Ӥ��ơ��������ۤ��򺸤ˡ��礭���ۤ��򱦤ˤ��롥���˿�
���3���ܤ򡤤��κ��ˤ���2�Ĥο���Ⱦ������ۤ���������Ӥ������ޤ���֤�õ����
�ơ��������롥�����4����,5���ܡ�$\cdots$�Ƚ缡������κǸ�ޤǷ����֤����Ǹ�
�ο����������줿�饽���Ȥ���λ�Ǥ��롥
%------------------------
\subsubsection{�ץ������}
%------------------------
%
\lstinputlisting[caption=ñ�����������Ȥδؿ�,label=prog:simple_sort]
{program/merge_sort.c}
%
%---------------------------------------------------------------------
\subsection{2ʬ����������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
ñ�����������ȤǤϡ�����Τ����ͤ���������Ŭ���ʰ��֤�ü������õ���Ƥ���(���
����������)�����֤�õ��������¤��ؤ����Ƥ���Τǡ�������ͤ�����Ӥ���Х���
�꡼����������ǽ�ǡ������Ŭ�Ѥ���®�٤θ����ޤä���ˡ����2ʬ���������ȤǤ��롥
%------------------------
\subsubsection{�ץ������}
%------------------------
%
\lstinputlisting[caption=2ʬ���������Ȥδؿ�,label=prog:binary_sort]
{program/binary_sort.c}
%
%---------------------------------------------------------------------
\subsection{�����ȤΥ��르�ꥺ������}
%---------------------------------------------------------------------
�����ȤΥ��르�ꥺ���ɾ���˷׻��̤�¾�ˡ��������Ȥ�����Τ��Ȥ��롥
\begin{itemize}
 \item ����ʥ����ȤȤϡ�Ʊ�����Ǥ����ä��Ȥ��������������ؤ��ʤ���
 \item �԰���ʥ����ȤȤϡ�Ʊ�����Ǥ����ä��Ȥ��������������ؤ����ǽ�������롥
\end{itemize}

�����ؽ����������Ȥη׻��̤Ȱ������ˤĤ��Ƥϡ�ɽ
\ref{table:sort_characteristic}(���ʽ�� Table 1-2)�ΤȤ���Ǥ��롥

\begin{table}[H]
  \caption{�����ȤΥ��르�ꥺ�����ħ}
  \label{table:sort_characteristic}
  \begin{center}
    \begin{tabular}{lll}
      \hline
      \multicolumn{1}{c}{���르�ꥺ��} &
      \multicolumn{1}{c}{�׻��̥�������} &
      \multicolumn{1}{c}{������} \\
      \hline \hline
      �Х֥륽���� & $O(N^2)$ & ���� \\
      �����å������� &$O(N\log N)$ ��$O(N^2)$ & �԰��� \\
      �ޡ��������� & $O(N\log N)$ & ���� \\
      �����ॽ���� & $O(N\log N)$ & �԰��� \\
      ñ������������ & $O(N^2)$ & ���� \\
      2ʬ���������� & $O(N^2)$ & ���� \\
      \hline
    \end{tabular}
  \end{center}
\end{table}
%
%=====================================================================
\section{�������Υ��르�ꥺ��}
%=====================================================================
�������Ȥϡ�
\begin{quote}
 ʸ���ɤ��ꤿ������Υǡ������椫����Ū�Υǡ���(����)���ɤ��ˤ��뤫(�⤷���ϡ����뤫��
 ����)��Ĵ�٤���
\end{quote}
�Ǥ��롥�����Υǡ���������˳�Ǽ����Ƥ�����ˤĤ��ơ���Ū�Υǡ�����õ����ˡ��
�ؽ�������
%
%---------------------------------------------------------------------
\subsection{��˥�������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
��Ū�Υǡ�����ü������õ��������ˡ�Ǥ��롥�ǡ�������������¤�Ǥ����硤��
����ˡ�����ʤ���

���Υ��르�ꥺ��η׻��Υ��������ϡ�$O(N)$�Ǥ��롥�ʤ��ʤ�С�ü����õ�����Ƥ���
���ᡤ�ǡ��������פ��뤿��ˤ�ʿ��$N/2$�����Ӥ�ɬ�פǤ��뤫��Ǥ���\footnote
{��Ū�Υǡ�����õ�����٤������ˤ�����}��
%------------------------
\subsubsection{�ץ������}
%------------------------
���ʽ��List 2-1(p.37-38)�Υ�˥��������δؿ��ϡ��ꥹ��
\ref{prog:linear_search}���̤�Ǥ��롥�����\tw{main}�ؿ�����ƤӽФ����Ȥˤ�ꡤ
����\tw{x}�Ȱ��פ�������\tw{a}��ź�������ֹ椬�����롥
\begin{itemize}
 \item \tw{x}��õ������ǡ����Ǥ��롥
 \item ����ϥݥ��󥿡��Ȥ����Ϥ���Ƥ��롥\tw{main}�ؿ��μ°���������̾�ϡ��ݥ�
       �󥿡��Ǥ��롥���δؿ��Ǥϡ�\tw{main}�ؿ��θƤӽФ�¦������ϡ�\tw{a[]}
       �Ȥ�������ˤʤ롥
 \item \tw{num}���ǡ�������ɽ����
 \item ��Ū�Υǡ����Ȱ��פ����Τ�̵���ä���硤\tw{NOT\_DOUND}���֤��������ͤϡ�
       \tw{\#define}���ִ������롥
\end{itemize}
%
\lstinputlisting[caption=��˥��������δؿ�,label=prog:linear_search]
{program/linear_search.c}
%
%---------------------------------------------------------------------
\subsection{��ʼ��Ĥ��ä���˥�������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�ꥹ��\ref{prog:linear_search}�η׻�®�٤�夲�뤿��ˡ��̾�Υ�˥��������Ǥ���ʼ��
�Ĥ������ꥹ��\ref{prog:linear_search}�Ǥϡ�1��Υ롼�פǡ�
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	n<num&&a[n]!=x
 \end{verbatim}
\end{quote}\vspace{-5mm}
�Τ褦��2������(\tw{n<num}��\tw{a[n]!=x})��ԤäƤ��롥��Ū�Υǡ���(����)����
��κǸ�������(��ʼ)���Ȥˤ�ꡤ\tw{n<num}����Ӥη׻���Ԥ�ʤ��ǺѤ�褦�ˤ�
���롥�������������κǸ�Ǥϡ�\tw{a[n]!=x]}����Ω���ʤ��ʤ�Τǡ��롼�פ���ȴ
���뤳�Ȥˤʤ롥�롼�פ���ȴ�����塤�����ȸ������ä�����κǸ���ͤ���Ӥ���Ф�
���ΤǤ��롥

���Τ褦�ˤ���ȡ���Ӥο���Ⱦʬ�ˤʤ롥���������׻��̤Υ���������$O(N)$���Ѥ��
�ʤ����Ȥ����դ��褦��
%------------------------
\subsubsection{�ץ������}
%------------------------
���ʽ��List 2-2(p.38-39)����ʼ���Ѥ�����˥��������δؿ��ϡ��ꥹ��
\ref{prog:linear_sentinel_search}���̤�Ǥ��롥�����ϡ���ۤɤ���ʼ���Ѥ��ʤ���
�˥���������Ʊ����
%
\lstinputlisting[caption=��ʼ��Ĥ��ä���˥��������δؿ�,label=prog:linear_sentinel_search]
{program/linear_sentinel_search.c}
%
%---------------------------------------------------------------------
\subsection{�Х��ʥ꡼������}
%---------------------------------------------------------------------
%--------------------
\subsubsection{����}
%--------------------
�ǡ������¤Ӥ˵�§����̵����硤��˥��������Τ褦��ü�������ܤ������ʤ�������
�����ǡ������¤Ӥ˵�§���������硤�������������ѤǤ��롥

���Ȥ��С��ǡ�����������¤�Ǥ�����硤ü������Ӥ���ΤǤϤʤ����ǽ�˿�����˰��֤�
��ǡ�������Ӥ��롥����ȡ����������٤��ǡ����θĿ���1�����ӤǤ�Ⱦʬ�ˤʤ롥Ʊ����
�Ȥ򷫤��֤��ȡ���Ӥ��٤��оݤ�$1/2$���ĸ������롥�ǡ����θĿ���¿����硤����
��ˡ�Ϸ�Ū�˥��������᤯�ʤ롥������ˡ��Х��ʥ꡼�������ȸ�����

��˥����������ȡ�1�����Ӥ�1�Ĥ����ǡ����θ��䤬����ʤ��Τˡ��Х��ʥ꡼������
����Ⱦʬ�˸��������뤳�Ȥ��Ǥ���ΤǤ��롥���������Х��ʥ꡼��������Ȥ������
�ϡ��ǡ�����ͽ�᥽���Ȥ��Ƥ���ɬ�פ����롥�������β����1��Ǥ���С������Ȥμ�
�֤�ͤ���ȥ�˥��������������ɤ����������β�������ä���ȡ��Х��ʥ꡼��������
����ͭ���ˤʤ롥

1��η׻����ꥹ��\ref{prog:binary_search}��5��15�ԤΥ롼�פǡ����������ϰϤ�$1/2$�ˤ�
�롥�������äơ�$\alpha$��Υ롼�פǤ����ϰϤ�1�ˤʤ�з׻�����λ���롥�ǡ�����
�Ŀ���$N$�Ȥ��ơ�����ɽ���ȡ�
\begin{align}
 N\left(\frac{1}{2}\right)^{\alpha}=1
\end{align}
�Ȥʤ롥���줫�顤�׻����$\alpha$�ϡ�
\begin{align}
 \alpha=\log_2 N
\end{align}
��Ƴ���Ф���\footnote{�����η׻��ϡ�
$\left(\frac{1}{2}\right)^{\alpha}=\frac{1}{N}\quad\Rightarrow\quad 2^{\alpha}=N
\quad\Rightarrow\quad \log_2 2^{\alpha}=\log_2 N \quad\Rightarrow\quad
\alpha\log_2 2=\log_2 N \quad\Rightarrow\quad \alpha=\log_2 N$}���Х��ʥ꡼�������ξ��η׻��̤Υ��������ϡ�$O(\log_2 N)$�Ǥ��롥
%------------------------
\subsubsection{�ץ������}
%------------------------
���ʽ��List 2-3(p.41-42)�ΥХ��ʥ꡼�������δؿ��ϡ��ꥹ��
\ref{prog:binary_search}���̤�Ǥ��롥�����\tw{main}�ؿ�����ƤӽФ����Ȥˤ�ꡤ
����\tw{x}�Ȱ��פ�������\tw{a}��ź�������ֹ椬�����롥
\begin{itemize}
 \item ����ϥݥ��󥿡��Ȥ����Ϥ���Ƥ��롥\tw{main}�ؿ��μ°���������̾�ϡ��ݥ�
       �󥿡��Ǥ��롥
 \item \tw{left}���ǡ�����¸�ߤ��뺸ü�ǡ�\tw{right}����ü��ɽ����
 \item ��Ū�Υǡ����Ȱ��פ����Τ�̵���ä���硤\tw{NOT\_DOUND}���֤��������ͤϡ�
       \tw{\#define}���ִ������롥
\end{itemize}
%
\lstinputlisting[caption=�Х��ʥ꡼�������δؿ�,label=prog:binary_search]
{program/binary_search.c}
%
%=====================================================================
\section{�ꥹ��}
%=====================================================================
%---------------------------------------------------------------------
\subsection{����}
%---------------------------------------------------------------------
�ꥹ�Ȥ�����Υǡ����Τ�����֤���꡼������뤳�Ȥˤ�ꡤ�ǡ�������(�����Ǥ�
����)�������롥�ǽ�Υǡ����ΰ��֤򸵤ˡ����줫���ˤ��ɤꤹ�٤ƤΥǡ������
�ʤ��ǡ�����(����)�������롥�����ͻҤ��\ref{fig:list}�˼�����
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/list.eps}
  \caption{�ꥹ��}
  \label{fig:list}
 \end{center}
\end{figure}
%

���Τ褦�ˤ���ȡ������Υǡ����Ͻ�˥�������(�������󥷥�륢������)���뤳�Ȥˤ�
�ꡤ����®�٤ϰ��̤��٤����������ǡ����κ���������ϡ��ǡ����ΰ��֤򵭲�����ݥ�
�󥿡����ѹ���������ʤΤǡ���®�ˤʤ롥
%--------------------------------------------------------------------
\subsection{�ץ������}
%--------------------------------------------------------------------
���ʽ��List 3-3(p.75-77)�Ǥϡ��ꥹ��\ref{prog:list}�˼�����¤�Τ��Ѥ��ƥꥹ�Ȥ�
��äƤ��롥
\begin{itemize}
 \item \tw{*prev}�����ΥΡ��ɤ򼨤��ݥ��󥿡��Ǥ��롥
 \item \tw{*next}�����ΥΡ��ɤ򼨤��ݥ��󥿡��Ǥ��롥
 \item \tw{*data}�����ΥΡ��ɤΥǡ����Ǥ��롥
\end{itemize}
%
\lstinputlisting[caption=�ꥹ�Ȥ�ɽ����¤��,label=prog:list]
{program/list.c}
%
%---------------------------------------------------------------------
\subsection{�ꥹ�Ȥ�����ΰ㤤}
%---------------------------------------------------------------------
�����ꥹ�Ȥ⡤ʣ���Υǡ������ͤȽ���򵭲�����ǡ�����¤�Ǥ��롥�����������λ�
�����Ϥ��ʤ�ۤʤꡤ����������褯���򤷤ʤ��ƤϤʤ�ʤ���

�������Ū�Υǡ����˥����ॢ����������ǽ�ǡ���Ū�Υǡ������ͤ������ꡤ�ǡ�����
�ͤ��ѹ�����®�ˤǤ��롥ź��������ꤹ������ǡ�����餬��ǽ�Ǥ��롥���������ǡ�
���κ���������ˤϷ׻������¿���ʤ롥���Ȥ��С�10���ܤΥǡ�����������Ȥʤ�ȡ�
11���ܤ�10���ܤ˰�ư��12���ܤ�11���ܤ˰�ư��13���ܤ�12���ܤ˰�ư$\cdots$�ȥǡ���
��缡��ư������ɬ�פ����롥

�������ꥹ�Ȥ���Ū�Υǡ����˥����������뤿��ˤϡ��������󥷥�륢������
\footnote{�ǡ�������Ƭ������֤��ɤ߹��ߡ����뤤�Ͻ񤭹��ߤ�Ԥʤ���ˡ��}��Ԥ���
���Τ��ᡤ�ǡ����ؤΥ������������¿���ʤ���������®�ˤʤ롥���������ǡ����κ�
���������ϴ�ñ�ǡ���������ؤΥΡ��ɤΥݥ��󥿡����ͤ��ѹ���������Ǥ��롥��������
�ơ������Ⱥ���Ϲ�®�ˤʤ롥

\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{C����ץ������ƥ��˥å�}
%=====================================================================
���ʽ��List 3-2(p.72)�Ǥϡ�C����Υץ������Ǥ褯�Ȥ�����꡼�γ��ݤ�����
�˴ؤ���ƥ��˥å����񤫤�Ƥ��롥�ޤ���List 3-4(p.75-77)�ǤϷ�����Ȥ�����ˡ��
�Ȥ��Ƥ��롥�����Ͻ��פʤΤǡ��褯���򤹤뤳�ȡ�
\begin{itemize}
 \item \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 \tw{free(array);}\vspace{-3mm}
       \begin{quote}
	�ؿ�\tw{free()}�ϡ����Υץ������ǻ��Ѥ��Ƥ�����꡼�ΰ�������뤿
	��ˤ��롥�����Ǥϡ�\tw{malloc}�ǳ��ݤ��줿�ΰ�������Ƥ��롥
       \end{quote}
%
  \item \tw{int *array}��\tw{array[n]}\vspace{-3mm}
       \begin{quote}
	�ݥ��󥿡���������Ƥ����Τ�����Ȥ��ƻȤäƤ��롥����ϡ����󤬤ɤΤ褦�˽�
	������Ƥ��뤫���ͤ���Ф褯ʬ���롥����\tw{array[n]}�ϡ�\tw{*(array+n)}��ɾ��
	����롥���ʤ��������\tw{array[n]}�ϡ��ݥ��󥿡�\tw{array}��\tw{n}�û�������
	���󥿡�(���ɥ쥹)�������ͤȸ������ȤǤ��롥���Τ褦�ʤ��Ȥ��顤������������
	���ʤ��Ƥ⡤����Τ褦�˻Ȥ����Ȥ��Ǥ���ΤǤ��롥
       \end{quote}
%
 \item \tw{typedef struct tagListNode\{} \\
       \hspace{3em}\tw{struct tagListNode *prev;}\\
       \hspace{3em}\tw{struct tagListNode *next;}\\
       \hspace{3em}\tw{int data;}\\
       \tw{\} ListNode;}\vspace{-3mm}
       \begin{quote}
	����ϡ�\textit{TYPE DEFine}(�����)�ȸƤФ���Τǡ�������̾��Ĥ�����䤬��
	�롥�����Ǥϡ�\tw{struct tagListNode}�ȸ�������\tw{ListNode}�Ȥ�����̾
	�ǻȤ��롥���Τ��Ȥˤ�ꡤ�������ñ�ˤʤ롥
       \end{quote}
%
 \item \tw{lastnode=NULL}\vspace{-3mm}
       \begin{quote}
	����ϡ��̥�ݥ��󥿡������뤤�϶��ݥ��󥿡��ȸƤФ���ΤǤ��롥����ϡ�
	\tw{lastnode}������ؤ������Ƥ��ʤ����Ȥ��ݾڤ��뤿��ˡ��ȤäƤ��롥
       \end{quote}
%
 \item \tw{newnode->data=buf;}\vspace{-3mm}
       \begin{quote}
	\tw{newnode}�ϥݥ��󥿡��Ǥ��롥�ݥ��󥿡����ؤ�������¤�ΤΥ��С��˥�������
	�����硤�������黻��(\tw{->})��Ȥ��������Ǥϡ��ݥ��󥿡�\tw{newnode}������
	��¤�ΤΥ��С�\tw{data}��\tw{buf}���ͤ��������Ƥ��롥�ݥ��󥿡��ǤϤʤ�����
	�̤��ѿ��ȤʤäƤ��빽¤�Τξ�硤���Υ��С��˥�����������ˤϥɥåȱ黻��
	(\tw{.})��Ȥ���
       \end{quote}
\end{itemize}
%=====================================================================
\section{��������뤿��ˤ�}
%=====================================================================
\begin{itemize}
 \item �����ǳؽ��������르�ꥺ����Ѥ��ơ�10�����٤������������ȤǤ��뤳�ȡ�
 \item ���ʤ��Ƥ⡤�Х֥륽���Ȥȥ����å������ȤΥץ����������򤹤뤳�ȡ�
 \item �׻��̤򼨤�\textbf{$O$��ɽ}�����򤹤뤳�ȡ��Х֥륽���ȤȥХ��ʥ꡼����
       ���η׻��̤Υ��������ˤĤ��ơ������Ǥ��뤳�ȡ�
 \item ��˥��������ȥХ��ʥ꡼�������Υץ�����ब����Ǥ��뤳�ȡ�
 \item ��˥��������ˤ�������ʼ�����Ȥ����¸�����ץ����������򤹤뤳�ȡ�
 \item �ꥹ�Ȥ�������뤿��ι�¤�Τ����񤱤뤳�ȡ�
 \item �ꥹ�Ȥ�����ΰ㤤������Ǥ��뤳�ȡ�
 \item �����ǳؽ�����C����Υץ������ƥ��˥å�������Ǥ��뤳�ȡ�
\end{itemize}
%=====================================================================
\end{document}



