【自考】データ構造試験前まとめ【CH 1-CH 3】
1803 ワード
CH 1 データ構造の概要
1. 論理構造:セット(CH 6ルックアップテーブル)、線形構造(CH 2線形テーブル、CH 3スタック、キュー、配列)、ツリー構造(CH 4ツリー、および二叉ツリー)、図構造(CH 5図)
2. 記憶構造:順次記憶、チェーン記憶(コード:初期化、挿入、削除)、インデックス記憶、ハッシュ記憶.
3. アルゴリズム:与えられた問題を解くために必要な処理ステップとその実行順序を規定する.
4. アルゴリズムの性質:正確性、読みやすさ、時空性、頑丈さ.
5. アルゴリズムの時間複雑さはアルゴリズム入力規模の関数である.
6. データ、データ要素(リニアテーブルの特性が同じ)、データ項目(ドメイン、フィールド)
CH 2リニアメーター CH 3スタック、キュー、配列
1.チェーンテーブルの初期化
head=malloc(sizeof(Node);
sizeof(Node)取得と構造体Nodeの空間サイズが一致するアドレス空間 拡張子:
ノードへのポインタを作成するステートメント
eg:p=(LkQueNode*)mallo(sizeof(LKQueNode) [教科書P 86]
構造体チェーン・キュー・ポイントのアドレス空間サイズを取得し、構造体の一例を動的に作成し、インスタンスのアドレスを取得し、pにアドレスを割り当てます.
チェーン記憶方式が他の複雑な論理構造で運用される場合(例えば、キュー、スタック、図、数)、作成されるのはポインタです.
2.スタックとキュー
本質的には、線形表であり、ヘッダー(スタックの底と列の頭)は、データを記憶しないか、または、lengthなどの共通データを記憶しないことができる.
スタック 何が先ですか? 後進先出
キュー 何が先ですか? 先入れ先出し
3. 擬似オーバーフローシーケンス列は、rear++を入れて、front++を出します.
4. 列を循環させ、記憶空間を犠牲にして列の先頭と後尾を区別します.本質はリニアテーブルなので、frontとは表の頭、表の最初のデータ要素の前の一つを指します.
rear=(front+CQ.length)%m.
キュー空CQ.rear=CQ.front 列が満ちる (CQ.rear+1)%m=CQ.front
5. 双方向循環チェーンに結点を挿入する
まず積極的に環境に自己紹介して、環境に自分を受け入れてもらいます.
新しい结点を挿入すると、作业指针sによって始まります.s=...s=です.
6. 双方向循環チェーンは空です. 孤独な頭が結点して自分を抱き、左手が自分を抱き、右手が自分を抱く.
7. スタックとスタックの一番上の要素の違い Push(圧、スタックに入る)、Pop(泡のように上に上がる)
8. 圧縮メモリ
疎行列,三元組表現法(i,j,v)
三元組表((Ai 1,Aj 2,v 1)、(Ai 2,Aj 2,v 2),…,(Ain,Ajn,vn)
1. 論理構造:セット(CH 6ルックアップテーブル)、線形構造(CH 2線形テーブル、CH 3スタック、キュー、配列)、ツリー構造(CH 4ツリー、および二叉ツリー)、図構造(CH 5図)
2. 記憶構造:順次記憶、チェーン記憶(コード:初期化、挿入、削除)、インデックス記憶、ハッシュ記憶.
3. アルゴリズム:与えられた問題を解くために必要な処理ステップとその実行順序を規定する.
4. アルゴリズムの性質:正確性、読みやすさ、時空性、頑丈さ.
5. アルゴリズムの時間複雑さはアルゴリズム入力規模の関数である.
6. データ、データ要素(リニアテーブルの特性が同じ)、データ項目(ドメイン、フィールド)
CH 2リニアメーター CH 3スタック、キュー、配列
1.チェーンテーブルの初期化
LinkList InitateLinkList( )
//
{
//
LinkList head;
// malloc ,
head = malloc(sizeof(Node));
//
head -> next = NULL;
return head;
}
話があります.head=malloc(sizeof(Node);
sizeof(Node)取得と構造体Nodeの空間サイズが一致するアドレス空間 拡張子:
ノードへのポインタを作成するステートメント
eg:p=(LkQueNode*)mallo(sizeof(LKQueNode) [教科書P 86]
構造体チェーン・キュー・ポイントのアドレス空間サイズを取得し、構造体の一例を動的に作成し、インスタンスのアドレスを取得し、pにアドレスを割り当てます.
チェーン記憶方式が他の複雑な論理構造で運用される場合(例えば、キュー、スタック、図、数)、作成されるのはポインタです.
2.スタックとキュー
本質的には、線形表であり、ヘッダー(スタックの底と列の頭)は、データを記憶しないか、または、lengthなどの共通データを記憶しないことができる.
スタック 何が先ですか? 後進先出
キュー 何が先ですか? 先入れ先出し
3. 擬似オーバーフローシーケンス列は、rear++を入れて、front++を出します.
4. 列を循環させ、記憶空間を犠牲にして列の先頭と後尾を区別します.本質はリニアテーブルなので、frontとは表の頭、表の最初のデータ要素の前の一つを指します.
rear=(front+CQ.length)%m.
キュー空CQ.rear=CQ.front 列が満ちる (CQ.rear+1)%m=CQ.front
5. 双方向循環チェーンに結点を挿入する
まず積極的に環境に自己紹介して、環境に自分を受け入れてもらいます.
新しい结点を挿入すると、作业指针sによって始まります.s=...s=です.
6. 双方向循環チェーンは空です. 孤独な頭が結点して自分を抱き、左手が自分を抱き、右手が自分を抱く.
7. スタックとスタックの一番上の要素の違い Push(圧、スタックに入る)、Pop(泡のように上に上がる)
8. 圧縮メモリ
疎行列,三元組表現法(i,j,v)
三元組表((Ai 1,Aj 2,v 1)、(Ai 2,Aj 2,v 2),…,(Ain,Ajn,vn)