データ構造第2版重点知識内容1(補)-陳越
11491 ワード
第一章：概要（補足）
(1)clock()関数
clock関数の概要:clock関数を使用するにはヘッダファイルを追加する必要があります.clock関数は、プログラムが実行されてからclock関数が呼び出されるまでの実際の時間をキャプチャすることができ、簡単に言えば、プログラムが実行されてから関数が呼び出されるまでの時間を測定する数を返します.
#includeclock関数の詳細:clock関数の戻り値タイプはclock_tは「クロックドット」であり、導入されたヘッダファイルには定数CLK_も含まれている.TCKは、マシンクロックが毎秒走行するクロックの点数を打つ.戻り値を記録するにはclock_を定義する必要がありますt変数レコード、単位秒に変換する時間はCLK_で割る必要がありますTCK.
clock_t start,stop;// clock_t
CLK_TCK; //CLK_TCK ，
clock関数の運用:コードブロックの実行時間を計算します.すなわち、コードブロックの前後にそれぞれclock関数を使用し、2つの異なるclock_を使用するt型変数は戻り値を記憶すると、ブロック実行時間は(ブロック後の変数-ブロック前の変数)/CLK_TCK.特殊な、clock_tは実際にはロング整数型(ヘッダファイルで名前を変更したもの)であるため、両者の差が非常に小さいためCLK_で割るTCKの前にdoubleタイプに変換する必要があります(そうでなければ1/2などの0に簡単です).
#include
%lf",(double)(stop-start)/CLK_TCK);//
return 0;
}
詳細なタイミング関数リンク
（2）データ構造の分類と連絡
データ構造の分類:
データ構造
論理構造
リニア・ツリー・グラフは、チェーン・ストレージを順番に格納します.
論理構造:データセット内のデータ要素間に存在する論理関係を指す. 物理構造:コンピュータにデータが格納される物理的な記憶関係を指す. 線形論理構造:すなわち、データ内の要素間に線形の関係、すなわち一対一が存在する.キューが線形である場合、本質は、各要素に1つの前駆者と1つの後続(先頭を除く)、すなわち1つの対応する論理関係しかないことである.ツリー状の論理構造:すなわち、データ内の要素は一対多の関係がある.家族の中のファミリースペクトルでは、親に複数の子供がいる可能性があり、一対多の関係を築く必要があります.本質は1つの要素が1つの前駆者しかいないが、複数の後継者がいることができる(親は1人しかいないが、複数の子供がいることができる). 図状論理構造:すなわち、データ中の要素は多対多の関係がある.例えば、交通路線図の各交差点は、複数の道(複数の後継)に通じる可能性があり、複数の道によって自分(複数の前駆者)に通じる可能性があり、本質的には多対多の論理関係である. 線形記憶構造:すなわち論理的に関連する要素であり、コンピュータに記憶される位置も隣接している.例えば、1つのキューに1つの配列を入力すると、線形論理関係が成立した2人は配列の中でも隣接しており、配列の知識から、コンピュータ記憶における記憶ユニットも隣接しているため、線形記憶であることがわかる. チェーンストレージ構造:すなわち、コンピュータに格納される位置が隣接しない論理的に関連する要素である.学習したチェーンテーブルのように、隣接するチェーンテーブルノードには直接線形関係(前駆と後続)がありますが、記憶されているメモリユニットは任意に割り当てられており、隣接していないことが多いです.
(3)抽象データ型
概念:抽象データ型(Abstract Data Type)は「抽象」である「データ型」の記述である. 抽象データ型は、データ型の記述である.説明には、1つはデータ・オブジェクト・セット、2つはデータ・セットに関連付けられたオペレーション・セットの2つの側面があります. 解釈:データ構造はデータ要素を格納し組織するために使用されると述べ、データ要素の論理構造と物理構造を研究しているが、これらはデータ要素に関連しているため、データ要素がどのようなものなのか、データ構造を議論する上で議論しなければならない.データ構造を実現する際に特定のデータオブジェクトの実現を考慮しなければならない場合、理論学習時に抽象的なデータ・オブジェクトのみを議論すればよい(この抽象的なデータ・オブジェクトは抽象的なデータ・タイプと総称され、「一時的に実装されていない」データ・タイプを表す.ああ、彼らの論理関係は、隣接する要素の間に前駆または後継の関係があることを確定することができますが、物理構造は?物理構造はシーケンスストレージであってもよく、配列を使用することはシーケンスストレージであり、チェーンテーブルを使用することはチェーンストレージである.また、各要素に格納されている情報は何ですか?各ユニットは、商品の符号化などの数値であってもよいし、文字列であってもよい(例えば、人が並んでいる情報が人名である). 所以我们可以知道,在讨论一种数据结构时,针对不同的实际应用,其数据元素要求的类型是不同的,而我们要谈论的是理论的数据结构,所以我们最开始就要把不同的数据元素种类抽象为一种类型相同的类型,并且不用细致考虑很多实现,这就是抽象数据类型.抽象データ型は、いくつかの固定的な属性と性質(オブジェクトセット)を検討し、そのデータ要素に対する理論操作(操作セット)を検討する.
(4)アルゴリズム
アルゴリズムは有限命令セットであり、入力を受け入れるか受け入れないが、必ず出力を生成する(出力は任意の形式であってもよく、つまりprintfの出力だけでなく、外部にフィードバックしなければならない).アルゴリズムの表示:コード、偽コード、自然言語.有限命令セットに比べて,擬似コードと自然言語はより理解しやすいが,いずれの形式でも正確な意味(すなわち曖昧性)が必要であり,アルゴリズムの要求を満たす必要がある. アルゴリズムの時間的複雑度と空間的複雑度:アルゴリズムにはしばしば入力があり,入力規模nのアルゴリズムについては,使用する空間サイズをF(n),実行する基本文回数をG(n),アルゴリズムの空間的複雑度をO(F(n),アルゴリズムの時間的複雑度をO(G(n))とする.O記号は関数の上界を表し,すなわち関数の中で最も成長が速い項(次数最大の項)のみをとり,係数を1にする.アルゴリズムの意義を研究する:アルゴリズムを研究するのはいつも問題を解決するためで、アルゴリズムを研究するのは問題を解決する方法を探して、問題を解決する方法を研究します.アルゴリズムの時間的複雑さと空間的複雑さは2つの角度から1つのアルゴリズムの性能を説明し,良いアルゴリズムと不適切な単純なアルゴリズムの効率は天差地別である可能性がある(例えば1からnの正の整数の和を計算し,nが大きくなると循環単回の累積は遅いが,等差数の和式を1回計算するだけで結果が得られる).
コードの例:
#includeここでの入力はnであり,nのサイズ取値は入力の規模である.アルゴリズムの空間複雑度を解析し,空間の変数n,i,jを用いた.しかし,n入力がどんなに大きくても,n,i,jの占有空間は変わらず(依然として3つの整数型),その占有空間は3 sizeof(int)であるため,その空間複雑度はO(3 sizeof(int)であり,最大次数をとり,ここで式の最高次数はゼロ次数すなわち定数項であり,定数項係数(すなわちそれ自体)を1にし,その空間複雑度はO(1)であることが分かった.
時間的複雑度については,基本文の実行回数を解析し,int nとscanfは2回,第1のforループはn+1+n+1+n+1(iがn以下であるか否かはn+1回,iがn回,int iが1回,i=nがn回,printf出力は状況を満たす場合にのみ1回実行した)である.合計3 n+3回.
同理第2サイクルは,iが1から2を乗じ,12^x>=nとするとx=log 2 n,log 2 nを乗じてlog 2 n+1と判断し,その総回数はlog 2 n+log 2 n+1+log 2 n+1とする.合計3 log 2 n+3回.
最後のサイクルはまず外層を最も見て、i 1回を定義して、iがnに等しいかn+1回未満であるかを判断して、i++がn回あって、それから内層を見て、jがn回あることを定義して(iは外層forサイクルごとに1つのjを作成して)、jがnに等しいかn*(n+1)回未満であることを判断して(内層はループごとにn+1回、外層n個i、1個iに1つの内層サイクルを判断して、だからn*(n+1)回を判断します). 同理j++はn*(n)回,最内層ifはnn回と判断しprintfを1回出力した.1+n+1+n+n(n+1)+n 2+nn+1共2*n^2+6 n+3回.
このアルゴリズムの時間的複雑度O(T)=O(3 n+3+3 log 2 n+3+2 n^2+6 n+3)=O(2 nn)=O(n*n)である.
補足-最大サブ列と