【学習ノート10】基本データ構造(スタックチェーンには根樹があります)

菗1スタックと行列:
スタック
ダイナミック集合
先進後出(last-i,first-out,LIFO)
インサート-圧入-プッシュ
Delete-ポップアップ-pop
空-stack empty
アンダーフロー(空スタックにポップアップ)-アンダーフロー
オーバーフロー(スタックに圧入)-overflow
基本操作の疑似コード:
単針:S.top

is_empty(S){
if S.top == 0
	return true
else 
	return false
}

push(S,x){
S.top++
S[S.top] = x
}

pop(S){
S.top--
return S[S.top+1]
}

3つの基本操作push()、pop()、is_empty()-実行時間はすべてO(1)です.
キュー(queue)
先入先出(FIFO)
Insert-入隊-Equeue-O(1)
Delete-出隊-Dequeue-O(1)
ヘッド-ヘッド
テール
キーワード:折り返し
基本的な方法の疑似コード:
思考は針でQを一周する.
enqueueはx元素をQ.tailの指す位置に書き込みます.
dequeue把Q.head所指元素return

enqueue(Q, x) { 	
Q[Q.tail] = x	
if Q.tail == Q.length
	Q.tail = 1
else 
	Q.tail++
}

dequeue(Q){
x = Q[Q.head]
if Q.head == Q.length
	Q.head = 1
else
	Q.head++
return x
}

葃2連鎖表(linked list)
ヘッド
テール?テール
sorted-並べ替え済み
unsorted-並べ替えられていない
circuular list-サイクルチェーン(head元素のprevポインタがtail要素を指す)
空チェーンL.head=NIL
sentinel-歩哨(ダミーオブジェクト、境界の処理を簡略化し、慎重に使う)
双方向リンク(doubly linked list)-各オブジェクトはkey(キーワード)prev(前駆)next(後続)を含む
シングルチェーン表(singly linked)-各オブジェクトはkey(キーワード)を含みます. next(後継)
主な方法
search(L,元素中のキーワードk)
insert(L,元素x)
delete(L,元素x)
铅3無針型言語における構造の実現
対象の複数グループ表示
3 xnの配列を構築し、1行目はprevを表し、2行目はkeyを表し、3行目はnextを表し、同じ要素の下付きは同じで、そして1変数Lを使って、表のヘッダ要素の下付きを格納し、チェーンを使うことができます.
オブジェクトの単一配列表現
一つの配列を作って、prev key nextの順に三つの順番で配列に保存します.あるオブジェクトを指すポインタはそのオブジェクトの最初の要素の下付きです.オフセット量を考慮して、異性のオブジェクトを処理しやすいです.
ヽoo.ツ....................................................
二叉の木
p-親ノード
left-左の子供
ライト-右の子供
T.root=NILスカイツリー
無制限枝の有根樹
left rightをchild_に変更します.1,ちゅん2…チld_nこの方法は、予め各要素の子供の数を知っておく必要があり、そうでないと、予め割り当てられない.
左子供右兄弟表示法:
http://iprai.hust.edu.cn/icl2002/algorithm/datastructure/basic/tree/chapter6_3.httm