|
|
上接：算法分析與設計筆記(一) 算法引論:http://m.zg4o1577.cn/bbs/dpj-46008-1.html
隊列
定義：隊列是允許在一端進行插入在另一端進行刪除操作的線性表。
允許插入的一端叫隊伍，允許刪除的一端叫隊頭。隊列具有“先進先出”的特性。
鏈隊的數據結構:
typedef struct Qnode{
1 QElem Type data;
2 struct Qnode * next;
3 }Qnode;
typedef struct{
1 Qnode * front;
2 Qnode * rear;
3 }LinkQueue;
入隊算法：EnQuenue(LinkQueue & Q,QElemType e)
1 p<-(Qnode *)malloc(sizeof(Qnode));
2 if NULL=p
3 then exit(OVERFLOW);
4 Q.rear=p;
5 p.data<-e;
6 p.next<-NULL;
7 Q.rear.next<-p;
8 return OK;
出隊算法：DeQuenue(LinkQueue &Q,QElemType &e)
1 e<-Q.front.data
2 q<-Q.front
3 Q.front<-Q.front.next
4 free(Q.front)
5 return OK;
樹
樹是一種非線性的結構，描述元素間的層次關系。
樹是由一個或多個結點組成的有限集合T，滿足如下關系：
1.有一個特定的結點稱為樹的根結點。
2.其余結點被分成m(m>=0)個互不相交的集合T1T2,T3,T4,...,Tm，其中每一個集合本身又是一棵樹，稱為根結點的子樹。
樹的基本術語：孩子、雙親、兄弟、結點的度、葉結點、分支結點、結點的層數、樹的深度、二叉樹、滿二叉樹、完全二叉樹。
二叉樹可以順序存儲在一維數組中，也可以用二叉鏈表。
二叉樹的遍歷是指按一定次序訪問二叉樹中的每個結點，使每個結點都被訪問一次。
由上至下，由左至右的順序遍歷稱為層次遍歷。若先根后左再右為先序遍歷，若先左后根再右為中序遍歷，若先左后右再根為后序遍歷。
圖
圖是由歐拉首先引入的一種重要的數據結構。圖（G）由頂點(V)和邊（E）的二個集合組成。
若邊有向則成為有向圖，否則稱為無向圖。有向的帶權圖通常被稱為網絡。
在無向圖中，每一對頂點之間都存在一條路徑，則稱該圖是連通圖。如果任意一對頂點之間都存在路徑，則稱該有向圖式強連通圖。
圖的存儲方式：鄰接矩陣，鄰接表。
鄰接矩陣表示數據結構
typedef struct{
1 VRType adj;
2 InfoType * info;
3 }AdjMartrix[Max_Vertex_num][Max_Vertex_num];
typeef strcut{
1 vertextype vexs[Max_Vertex_num];
2 AdjMatrix arcs;
3 int vexnum,arcnum;
4 GraphKind kind;
5 }MGraph;
迭代法
迭代法是一種不斷用變量的當值遞推出新值的解決問題的方法。用于數值計算、累加、累乘。
分三步：1確定迭代模型2建立迭代關系式3迭代過程的控制
遞推法
遞推法師迭代法的最簡單形式。
倒推法
倒推法師指對某些特殊問題所采取的違反常規的，從后向前推解問題的方法。
例如輸出楊輝三角：
Yhui_Tri(int n)
1 print("1");
2 print("/n");
3 a[1]<-1;
4 a[2]<-1;
5 print(a[1],a[2]);
6 print("/n");
7 for i<-3 to n
8 do{ a[1]<-1;
9 a<-1;
10 for j<-i-1 to 1
11 do a[j]<-a[j]+a[j-1];
12 for j<-1 to i
13 do print(a[j]);
14 print("/n");
例子迭代法解方程
二分法求解方程算法
Ddliv_Root(int a, int b, float x1, float x2)
1 f1<-0.5*(x1)^3+2*(x1)^2-8;
2 f2<-0..5*(x2)^3+2*(x2)^2-8;
3 if f1*f2>0
4 then{ print("No Root"};
5 return;
6 do{x<-0.5*(x1+x2);
7 f<-0.5*x^3+2*(x2)^2-8;
8 if f=0
9 then break;
10 if f1*f<0
11 then {x2=x;
12 f2<-0.5*(x2)^3+2*(x2)^2-8;}
13 else {x1=x;
14 f1<-0.5*(x1)^3+2*(x1)^2-8;}
15 }while fabs(f)>=le-4;
16 print("root="x);
17 return;
|
|
