|
|
上接：算法分析與設(shè)計(jì)筆記(一) 算法引論:http://m.izizhuan.cn/bbs/dpj-46008-1.html
隊(duì)列
定義：隊(duì)列是允許在一端進(jìn)行插入在另一端進(jìn)行刪除操作的線性表。
允許插入的一端叫隊(duì)伍，允許刪除的一端叫隊(duì)頭。隊(duì)列具有“先進(jìn)先出”的特性。
鏈隊(duì)的數(shù)據(jù)結(jié)構(gòu):
typedef struct Qnode{
1 QElem Type data;
2 struct Qnode * next;
3 }Qnode;
typedef struct{
1 Qnode * front;
2 Qnode * rear;
3 }LinkQueue;
入隊(duì)算法：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;
出隊(duì)算法：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;
樹(shù)
樹(shù)是一種非線性的結(jié)構(gòu)，描述元素間的層次關(guān)系。
樹(shù)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T，滿足如下關(guān)系：
1.有一個(gè)特定的結(jié)點(diǎn)稱為樹(shù)的根結(jié)點(diǎn)。
2.其余結(jié)點(diǎn)被分成m(m>=0)個(gè)互不相交的集合T1T2,T3,T4,...,Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根結(jié)點(diǎn)的子樹(shù)。
樹(shù)的基本術(shù)語(yǔ)：孩子、雙親、兄弟、結(jié)點(diǎn)的度、葉結(jié)點(diǎn)、分支結(jié)點(diǎn)、結(jié)點(diǎn)的層數(shù)、樹(shù)的深度、二叉樹(shù)、滿二叉樹(shù)、完全二叉樹(shù)。
二叉樹(shù)可以順序存儲(chǔ)在一維數(shù)組中，也可以用二叉鏈表。
二叉樹(shù)的遍歷是指按一定次序訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)都被訪問(wèn)一次。
由上至下，由左至右的順序遍歷稱為層次遍歷。若先根后左再右為先序遍歷，若先左后根再右為中序遍歷，若先左后右再根為后序遍歷。
圖
圖是由歐拉首先引入的一種重要的數(shù)據(jù)結(jié)構(gòu)。圖（G）由頂點(diǎn)(V)和邊（E）的二個(gè)集合組成。
若邊有向則成為有向圖，否則稱為無(wú)向圖。有向的帶權(quán)圖通常被稱為網(wǎng)絡(luò)。
在無(wú)向圖中，每一對(duì)頂點(diǎn)之間都存在一條路徑，則稱該圖是連通圖。如果任意一對(duì)頂點(diǎn)之間都存在路徑，則稱該有向圖式強(qiáng)連通圖。
圖的存儲(chǔ)方式：鄰接矩陣，鄰接表。
鄰接矩陣表示數(shù)據(jù)結(jié)構(gòu)
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;
迭代法
迭代法是一種不斷用變量的當(dāng)值遞推出新值的解決問(wèn)題的方法。用于數(shù)值計(jì)算、累加、累乘。
分三步：1確定迭代模型2建立迭代關(guān)系式3迭代過(guò)程的控制
遞推法
遞推法師迭代法的最簡(jiǎn)單形式。
倒推法
倒推法師指對(duì)某些特殊問(wèn)題所采取的違反常規(guī)的，從后向前推解問(wèn)題的方法。
例如輸出楊輝三角：
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;
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
