|
|
上接：算法分析与设计笔记(一) 算法引论:http://www.51hei.com/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;
|
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
