本文目錄一覽：
Golang-基於TimeingWheel定時器
在linux下實現定時器主要有如下方式
在這當中 基於時間輪方式實現的定時器 時間複雜度最小，效率最高，然而我們可以通過 優先隊列 實現時間輪定時器。
優先隊列的實現可以使用最大堆和最小堆，因此在隊列中所有的數據都可以定義排序規則自動排序。我們直接通過隊列中 pop 函數獲取數據，就是我們按照自定義排序規則想要的數據。
在 Golang 中實現一個優先隊列異常簡單，在 container/head 包中已經幫我們封裝了，實現的細節，我們只需要實現特定的接口就可以。
下面是官方提供的例子
因為優先隊列底層數據結構是由二叉樹構建的，所以我們可以通過數組來保存二叉樹上的每一個節點。
改數組需要實現 Go 預先定義的接口 Len , Less , Swap , Push , Pop 和 update 。
timerType結構是定時任務抽象結構
首先的 start 函數，當創建一個 TimeingWheel 時，通過一個 goroutine 來執行 start ,在start中for循環和select來監控不同的channel的狀態
通過for循環從隊列中取數據，直到該隊列為空或者是遇見第一個當前時間比任務開始時間大的任務， append 到 expired 中。因為優先隊列中是根據 expiration 來排序的，
所以當取到第一個定時任務未到的任務時，表示該定時任務以後的任務都未到時間。
當 getExpired 函數取出隊列中要執行的任務時，當有的定時任務需要不斷執行，所以就需要判斷是否該定時任務需要重新放回優先隊列中。 isRepeat 是通過判斷任務中 interval 是否大於 0 判斷，
如果大於0 則，表示永久就生效。
防止外部濫用，阻塞定時器協程，框架又一次封裝了timer這個包，名為 timer_wapper 這個包,它提供了兩種調用方式。
參數和上面的參數一樣，只是在第三個參數中使用了任務池，將定時任務放入了任務池中。定時任務的本身執行就是一個 put 操作。
至於put以後，那就是 workers 這個包管理的了。在 worker 包中， 也就是維護了一個任務池，任務池中的任務會有序的執行，方便管理。
Golang數據結構-樹
二叉樹是n(n=0)個節點的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個根節點和兩棵互不相交的、分別稱為根節點的左子樹和右子樹的二叉樹組成
二叉樹的遍歷
5.1樹的概念
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次，如上圖，其深度為4；
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
5.樹的表示
樹的表示方法有許多，常用的方法是用括號：先將根結點放入一對圓括號中，然後把它的子樹由左至右的順序放入括號中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來。如上圖可寫成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5. 2 二叉樹
1.二叉樹的基本形態：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：
(1)空二叉樹——(a)；
(2)只有一個根結點的二叉樹——(b)；
(3)右子樹為空的二叉樹——(c)；
(4)左子樹為空的二叉樹——(d)；
(5)完全二叉樹——(e)
注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
2.兩個重要的概念：
(1)完全二叉樹——只有最下面的兩層結點度小於2，並且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹；
(2)滿二叉樹——除了葉結點外每一個結點都有左右子女且葉結點都處在最底層的二叉樹,。
如下圖：
完全二叉樹
滿二叉樹
3.二叉樹的性質
(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；
(2) 深度為h的二叉樹最多有2h-1個結點(h=1)，最少有h個結點；
(3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，
則N0=N2+1；
(4) 具有n個結點的完全二叉樹的深度為int（log2n）+1
(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關係：
若I為結點編號則 如果I1，則其父結點的編號為I/2；
如果2*I=N，則其左兒子（即左子樹的根結點）的編號為2*I；若2*IN，則無左兒子；
如果2*I+1=N，則其右兒子的結點編號為2*I+1；若2*I+1N，則無右兒子。
4.二叉樹的存儲結構：
(1）順序存儲方式
type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;
(2)鏈表存儲方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
5.普通樹轉換成二叉樹：凡是兄弟就用線連起來，然後去掉父親到兒子的連線，只留下父母到其第一個子女的連線。
6.二叉樹的遍歷運算（遞歸定義）
(1)先序遍歷
訪問根；按先序遍歷左子樹；按先序遍歷右子樹
(2)中序遍歷
按中序遍歷左子樹；訪問根；按中序遍歷右子樹
(3)後序遍歷
按後序遍歷左子樹；按後序遍歷右子樹；訪問根
例1.用順序存儲方式建立一棵有31個結點的滿二叉樹，並對其進行先序遍歷。
program erchashu1;
var b:array[1..31] of char;
e:array[1..63] of byte;
n,h,i,k:integer;
procedure tree(t:integer);
begin
if e[t]=0 then exit
else
begin
write(b[t]);e[t]:=0;
t:=2*t;tree(t);
t:=t+1;tree(t);
end;
end;
begin
repeat
write(‘n=’);readln(n);
until (n0) and (n6);
fillchar(e,sizeof(e),0);
k:=trunc(exp(n*ln(2)))-1;
for i:=1 to k do e[i]:=1;
for i:=1 to 26 do b[i]:=chr(64+i);
for i:=1 to 5 do b[26+i]:=chr(48+i);
h:=1 ;tree(h);
writeln;
end.
例2.用順序存儲方式建立一棵如圖所示的二叉樹，並對其進行先序遍歷。
program tree1;
const n=15;
type node=record
data:char;
l,r:0..n;
end;
var tr:array[1..n] of node;
e:array[1..n] of 0..1;
i,j:integer;
procedure jtr;
var i:integer;
begin
for i:=1 to n do
with tr[i] do
readln(data,l,r);
end;
procedure search(m:integer);
begin
with tr[m] do
begin
write(data);
if l0 then search(l);
if r0 then search(r);
end;
end;
begin
jtr;search(1);writeln;
end.
例3 用鏈表存儲方式生成上述二叉樹，中序遍歷之。
1.將上述二叉樹用廣義表表示為A(B(D,E(G)),C(F(,H)))
2.根據廣義表串（以#結束）生成二叉樹。
program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch’#’ do
begin
case ch of
‘A’..’Z’:begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top0 then
case k of
1:s[top]^.l:=p;
2:s[top]^.r:=p;
end
end;
‘(‘:begin top:=top+1;s[top]:=p;k:=1;end;
‘)’: top:=top-1;
‘,’: k:=2;
end;
read(ch);
end;
head:=s[1];
end;
procedure inorder(head:trlist);
begin
if head^.lnil then inorder(head^.l);
write(head^.da);
if head^.rnil then inorder(head^.r);
end;
begin
write(‘Input tree string:’);
creat(root);
inorder(root);
end.
5.3 二叉樹的應用
1. 哈夫曼樹與哈夫曼碼
樹的路徑長度：一棵樹的每一個葉結點到根結點的路徑長度的和。
帶權二叉樹：給樹的葉結點賦上某個實數值（稱葉結點的權）。
帶權路徑長度：各葉結點的路徑長度與其權值的積的總和。
哈夫曼樹（最優二叉樹）：帶權路徑長度最小的二叉樹。
如何構建哈夫樹：（思想是：權越大離跟越近）
program gojiantree;
const n=4;m=7;
type node=record
w:real;
parent,lchild,rchild:0..m
end;
htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
small1,small2:real;
p1,p2:0..m;
begin
for i:=1 to m do
with ht[i] do
begin
w:=0;lchild:=0;rchild:=0;parent:=0;
end;
for i:=1 to n do read(ht[i].w);
for i:=n+1 to m do
begin
p1:=0;p2:=0;
small1:=1000;small2:=1000;
for j:=1 to i-1 do
if ht[j].parent=0 then
if ht[j].wsmall1 then
begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
else if ht[j].wsmall2 then begin small2:=ht[j].w;p2:=j end;
ht[p1].parent:=i;
ht[p2].parent:=i;
ht[i].lchild:=p1;
ht[i].rchild:=p2;
ht[i].w:=ht[p1].w+ht[p2].w;
end;
end;
begin
gjtree(htree1);
end.
哈夫曼碼：哈夫曼樹的非葉結點到左右孩子的路徑分別用0，1 表示，從根到葉的路徑序列即為哈夫曼碼。
哈夫曼碼是不會發生譯碼多義性的不等長編碼，廣泛應用實際中。
（原因是任何一字符的編碼不是更長編碼的前綴部分，為什麼？）
2.排序二叉樹
排序二叉樹：每一個參加排列的數據對應二叉樹的一個結點，且任一結點如果有左（右）子樹，則左（右）子樹各結點的數據必須小（大）於該結點的數據。中序遍歷排序二叉樹即得排序結果。程序如下：
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if leftnil then hyt1(left);
write(w:4);
if rightnil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.
3.堆排序
堆：設有數據元素的集合（R1,R2,R3,…Rn)它們是一棵順序二叉樹的結點且有
Ri=R2i 和Ri=R2i+1(或=)
堆的性質：堆的根結點上的元素是堆中的最小元素，且堆的每一條路徑上的元素都是有序的。
堆排序的思想是：
1）建初始堆（將結點[n/2],[ n/2]-1,…3,2,1分別調成堆）
2）當未排序完時
輸出堆頂元素，刪除堆頂元素，將剩餘的元素重新建堆。
程序如下：
program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j=m do
begin
if (jm) and (a[j]a[j+1]) then j:=j+1;
if ta[j] then
begin a[i]:=a[j];i:=j;j:=2*i; end
else exit;
end;
a[i]:=t;
end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/153825.html
微信掃一掃 
支付寶掃一掃 