%===================================================================== % 秋田高専 2E 情報処理I テキスト %　　テーマ　今まで学習したデータ構造 % 本テキストの内容 % ・ % ・ % ・ % ・ %　　　 　・ % % last updated 2005.04.26 % created by Masashi Yamamoto % e-mail yamamoto@akita-nct.jp %===================================================================== \documentclass[10pt,a4paper]{jarticle} \usepackage{html,graphicx,amsmath,amssymb,ascmac,float} \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}} % \begin{document} \title{今まで学習したデータ構造} \author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}} \date{2005年4月27日} \maketitle % % %===================================================================== \section{本日の学習内容} %===================================================================== 本日は、授業変更に伴いセンターが使えないので、今まで学習したC言語のデータ構造を 復習する。本日の主な学習内容は、以下の通りである。 \begin{itemize} \item これまで学習したデータ構造 \item メモリーとデータ \begin{itemize} \item 単純型変数 \item 配列 \item 構造体 \end{itemize} \item 変数の適用範囲 \end{itemize} %===================================================================== \section{はじめに} %===================================================================== 現在、諸君はC言語の文法の勉強をしている。実際プログラムの勉強は、文法の勉強だけ では全く不十分である。そのため、この講義では文法の学習が住むと、「アルゴリズムと データ構造」の学習を進める。アルゴリズムとは問題を解く手順のことである。コンピュー タープログラムでは、入力データから目的のデータを作成する手順を言う。プログラマー はアルゴリズムを考え、それをプログラミング言語で表現しなくてはならない。アルゴリ ズムが大事であることは、万人が認めることである。これは、コンピュータープロ グラム作成のみならず、数学や電気の問題を解く場合も同じである。科学の問題を解く場 合は手順が重要で、それが分かれば、問題が解けたのも同様である。 一方、データ構造となると、少し様子が異なってくる。数学や電気の問題のデータ構造と なると、想像がつかない。科学の問題では、データ構造は重要視されないので、それも仕 方ないことである。データ構造を気にするのは、なんと言ってもビジネスの分野である。 たとえば、私の場合、成績処理のデータ構造を考えなくてはならない。それには、年度と 学年、学籍番号、学生氏名、教科名、試験名、点数、レポート提出状況、出欠などのデー タを分かり易くまとめなくてはならない。実際には図\ref{fig:excel_seiseki}表計算の Excelを使っているが、データ構造という意味では同じである。この例のように、データ の集まりのまとめ方をデータ構造という。 プログラムを作成する場合、そのアルゴリズムとデータ構造を考えなくてはならない。ア ルゴリズムは重要でそれの善し悪しでプログラムの性能が決まるのは、理解できるであろ う。しかし、データ構造については、結構無頓着になってしまいがちである。先 の成績処理のように単純な問題であれば誰でも同じようなデータ構造を考え、大した問題 は生じない。しかし、大量のデータがあるような場合には、いろいろなデータ構造が考え られる。大企業の顧客データなどがそれに当たる。住所や氏名、年齢、何時、どこで、購 入した商品のデータがある。これらに加えて、アンケートに答えていれば、それこを数十 の項目で、数百万人分のデータがあることも容易に想像できる。このデータをまとめ方 、すなわち構造は重要で、その後の処理の方法にも大きく影響するであろう。この構造に 従うということは、プログラマーの頭の中に、それがインプットされるので、それを用い た処理のプログラムを書くことになるからである。 また、データ構造が悪いと、効率の悪いプログラムになってしまう。たとえば、ファイル に100個の整数が書かれており、その合計を求めるプログラムでは配列を使うべきであろ う。変数を使ったプログラムでは、効率が悪くなるのはすぐに分かるであろう。 % \begin{table}[hbtp] \begin{center} \caption{データ構造の種類} \label{table:kind_of_data_structure} \begin{tabular}{|l|l|l|l|l|} \hline データ構造 & 基本データ構造 & 基本データ型 & 単純型 & 整数型 \\ \cline{5-5} & & & & 実数型 \\ \cline{5-5} & & & & 文字型 \\ \cline{5-5} & & & & 論理型 \\ \cline{5-5} & & & & 数え上げ型 \\ \cline{4-5} & & & \multicolumn{2}{l|}{ポインタ型} \\ \cline{3-5} & & 構造型 & \multicolumn{2}{l|}{配列型} \\ \cline{4-5} & & & \multicolumn{2}{l|}{レコード型} \\ \cline{3-5} & & \multicolumn{3}{l|}{抽象データ型} \\ \cline{2-5} & 問題向きデータ構造 & 線形リスト & \multicolumn{2}{l|}{単純リスト} \\ \cline{4-5} & & & \multicolumn{2}{l|}{双リスト} \\ \cline{4-5} & & & \multicolumn{2}{l|}{環状リスト} \\ \cline{3-5} & & 木 & 二分木 & 完全二分木 \\ \cline{5-5} & & & & 二分探索木 \\ \cline{5-5} & & & & バランス木 \\ \cline{4-5} & & & \multicolumn{2}{l|}{多分木} \\ \cline{4-5} & & & バランス木 & AVL木 \\ \cline{5-5} & & & & B木 \\ \cline{3-5} & & \multicolumn{3}{l|}{スタック} \\ \cline{3-5} & & \multicolumn{3}{l|}{キュー} \\ \hline \end{tabular} \end{center} \end{table} % %===================================================================== \section{これまで学習したデータ構造} %===================================================================== %--------------------------------------------------------------------- \subsection{単純型変数} %--------------------------------------------------------------------- 単純型の変数は、次のように変数に一つの数値\footnote{一つの文字のみ代入可能なもの は文字型の変数である。文字も整数として扱えるので、この範疇と考える。}しか代入で きないものを言う。 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} char c, h, moji; int i, j, seisu; double x, y, jisu; \end{verbatim} \end{quote} % 通常、これを変数と言う。変数というと、この単純型を示す場合が多いが、配列や構造体 を含める場合もあるから、文脈から適当に判断しなくてはならない。 これのイメージは、図\ref{fig:image_variable}に示しているとおりで、変数とは数値を 入れる箱のようなものである。整数型と倍精度実数型の変数は、数学の変数と全く同じで ある。 % \begin{figure}[hbpt] \begin{center} \includegraphics[keepaspectratio, scale=0.8] {figure/image_variable.eps} \caption{変数のイメージ。変数とはデータを入れる箱のようなもの。} \label{fig:image_variable} \end{center} \end{figure} % 図を見て分かるように、箱の大きさが型によって異なる。これは、一つのデータを表現す るために必要な情報量が異なるためである。情報量の単位は、ビット(bit)が使われる。2 進数の1桁を1ビットと言う。8ビットで1バイトとなり、それがコンピューターで使われる 基本単位となる。 同じ\tw{int}型でもいろいろあり、表現できる範囲が異なっている。これは一つの変数の 情報量の差から生まれる。C言語で使われる型によって表現できる範囲を \ref{table:diff_variable_type}に示す。全てのC言語は同じとなっておらず、諸君が使っ ているシステムではこの表のようになっている。いろいろな型があるが、ほとんどの場合、 \tw{char}、\tw{int}、\tw{double}で十分である。諸君が作るプログラムでは、これらで 十分、間に合うが、問題が生じたときのみ他の型を使えば良い。 % % \begin{table}[H] \begin{center} \caption{型によるデータの表現の違い} \label{table:diff_variable_type} \begin{ttfamily} \begin{tabular}{|l|l|l|l|l|l|} \hline 型 & バイト長 & 範囲 & 有効精度 \\ \hline \hline char & 1 & -128〜127 & \\ signed char & 1 &-128〜127 & \\ unsigned char & 1 & 0〜255 & \\ & & & \\ short int & 2 & -32768 〜 32767 & \\ signed short int & 2 & -32768 〜 32767 & \\ unsigned short int & 2 & 0 〜 65535 & \\ int & 4 & -2147483648 〜 2147483647 & \\ signed int & 4 & -2147483648 〜 2147483647 & \\ unsigned int & 4 & 0 〜 4294967295 & \\ long int & 4 & -2147483648 〜 2147483647 & \\ unsigned long int & 4 & -2147483648 〜 2147483647 & \\ signed long int & 4 & 0 〜 4294967295 & \\ & & & \\ float & 4 & およそ $10^{-38}$〜$10^{38}$ & およそ 6桁 \\ double & 8 & およそ $10^{-308}$〜$10^{308}$ & およそ 15桁 \\ long double & 12 & およそ $10^{-4932}$〜$10^{4932}$ & およそ 18桁 \\ \hline \end{tabular} \end{ttfamily} \end{center} \end{table} % %--------------------------------------------------------------------- \subsection{配列} %--------------------------------------------------------------------- 一次元の配列は数学のベクトルと、二次元の配列は行列とよく似ている。実際、C言語で ベクトルや行列の演算を行うときには、構造が同じ配列を使うことになる。順序 づけられた同じ型のデータが複数ある場合、配列の出番となる。添え字(これが順序を表 す)により、それらにアクセスできるので、データの操作が簡単にできる。 配列を使う場合、 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} int i[10], j[100][100]; \end{verbatim} \end{quote} % のように宣言を行う。そうすると図\ref{fig:image_array}のように、メモリー領域が確保され、 配列が使えるようになる。この配列のデータにアクセスするためには、配列名と添え字を 指定する。次のようにである。 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} i[3]=5; c=i[3]; \end{verbatim} \end{quote} % % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio, scale=0.8] {figure/image_array.eps} \caption{配列のイメージ。データを入れる箱がいっぱいある。ただし箱の大きさは全 て同じ。} \label{fig:image_variable} \end{center} \end{figure} % % %--------------------------------------------------------------------- \subsection{構造体} %--------------------------------------------------------------------- 配列は同じ型のデータの集まりであったが、構造体は異なる型のデータの集まりである \footnote{同じ型でも良い}。この構造体を使う場合、 % \begin{enumerate} \item 構造体のメンバーを規定する。これにより構造体を定義する。 \item 構造体変数の宣言。これによりメモリーが確保される。 \end{enumerate} % という手順が必要である。このようにして、構造体を定義し、メモリーを確保した後、そ れを使うことができる。今までは、データの型の内容があらかじめ決まっていたので、最 初の手順は不要であった。一方構造体のメンバー、すなわちデータの型はプログラマーが 決めなくてはならないので、最初の手順が必要となる。 最初のメンバーの規定は、つぎのように行う。 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} struct kouzoutai{ char name[8]; int seisu; double jisu; }; \end{verbatim} \end{quote} % これでは、メモリーがまだ確保されていないことに注意が必要である。これは、プログラ マーが新たに変数を定義したのと同じである。 そして、この構造体を実際に使う場合には、次のようにしてメモリーを確保する。 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} struct kouzoutai a, b[10]; \end{verbatim} \end{quote} % そうすると構造体変数が使用可能となる。この様子を、図\ref{fig:image_structure} メモリーに確保された構造体のデータにアクセスするためには、ドット(\tw{.})演算子を 使うことになる。次のようにである。 % % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} a.seisu = 5; b[5].name[3]='a'; x = b[6].jisu; \end{verbatim} \end{quote} % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio, scale=0.8] {figure/image_structure.eps} \caption{構造体のイメージ。データを入れるいろいろな大きさの箱がある。} \label{fig:image_variable} \end{center} \end{figure} % %===================================================================== \section{メモリーとデータ} %===================================================================== 諸君は方程式を使って問題を解く場合、変数というものを使っている。数学の変数とC言 語のプログラム中での変数の決定的な違いは、変数の型の宣言が必要なことである。実際 にプログラム中では、 % \begin{enumerate} \item 変数や配列、構造体の宣言。構造体の場合は、それに先だって構造体のメンバー を規定しなくてはならない。 \item データ構造に数値を格納する。 \end{enumerate} % という手順が必要である。後者は、数学の変数と似たような使い方をする。前者が数学と 異なっており、実際のプログラムのアルゴリズムでは不要に思える。これが必要なのは、 コンピューターの都合である。たいていのプログラミング言語では、これを宣言すること により、メモリーを確保する。必要なメモリー量はプログラマーが決めなくてはならない。 コンピューターは、このプログラムがどの程度のメモリーが必要か全く分からないからで ある。 % %===================================================================== \section{変数の適用範囲} %===================================================================== 宣言された変数が使える範囲を\textbf{適用範囲(Scope)}という。関数の内側で宣言した 変数を\textbf{ローカル変数}、外側で宣言した変数を\textbf{グローバル変数}と呼ぶ。 ローカル変数は宣言された関数内でしか使うことができないが、グローバル変数はどこか らでも使える。その様子を図\ref{fig:variable_local_global}に示す。 グローバル変数とローカル変数は同じ名前を使うことができるが、ローカル変数が優先さ れることになっている。ただし、実際のプログラムでは、このようにするとわかりにくい バグの原因となるので、慎むべきである。 他にいろいろな宣言を行い適用範囲を変えることができるが、これについては将来学習す る。 % \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio, scale=1.0] {figure/variable_local_global.eps} \caption{グローバル変数とローカル変数} \label{fig:variable_local_global} \end{center} \end{figure} % %===================================================================== \end{document}