冯诺依曼提出“存储程序控制”思想并做了硬件实现,自此,程序运行前先要加载到内存,同时,全局或静态数据也要提前加载到内存。
程序包括需要处理的数据和处理这些数据的代码,如何组织数组和代码?自然成了编程需要考虑的核心思想。
1 如何组织数据?
按照冯诺依曼的“存储程序控制”思想,数据要先存储(内存是一个线性存储结构)才能被处理,数据可以顺序存储,也可以链式存储,存储的数据不仅有数据本身,更重要的是数据之间的逻辑关系(一对一、一对多、多对多),同时,如何存储可以实现最大化的数据处理(增删改查)的效率?所有这些都属于数据结构的范畴。
当然,数据及关系的存储的目的是为了操作,数据元素的基本操作包括增删改查、遍历等,对元素操作的不同定义或限制也可以构成不同的数据结构(操作受限的数据结构),如栈和队列就是对存储与访问的顺序加以限制构成的适配(适应特定需求)的数据结构。对内容的特定限制,如字符串,也构成一类特殊的数据结构,称为内容受限的数据结构。
树和图的关系需要特殊存储:
树(tree)的数据结构:注意其用结构体定义的数据域与表示数据关系的域:
/
ADT 树(tree)
Data
结点及结点之间的层次关系
Operation
……
end ADT /
/ 树的双亲表示法结点结构定义 /
define MAX_TREE_SIZE 100
typedef int TElemType; / 树结点的数据类型,目前暂定为整型 /
typedef struct PTNode / 结点结构 /
{
TElemType data; / 结点数据 /
int parent; / 双亲位置 /
} PTNode;
typedef struct / 树结构 /
{
PTNode nodes[MAX_TREE_SIZE]; / 结点数组 /
int r,n; / 根的位置和结点数 /
} PTree;
/ 树的孩子表示法结构定义 /
define MAX_TREE_SIZE 100
typedef int TElemType; / 树结点的数据类型,目前暂定为整型 /
typedef struct CTNode / 孩子结点 /
{
int child;
struct CTNode next;
} ChildPtr;
typedef struct / 表头结构 /
{
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct / 树结构 /
{
CTBox nodes[MAX_TREE_SIZE]; / 结点数组 /
int r,n; / 根的位置和结点数 /
} CTree;
/ 树的孩子兄弟表示法结构定义 /
typedef struct CSNode
{
TElemType data;
struct CSNode firstchild,rightsib;
} CSNode,*CSTree;
/ 二叉树的二叉链表结点结构定义 /
typedef struct BiTNode / 结点结构 /
{
TElemType data; / 结点数据 /
struct BiTNode lchild,rchild; / 左右孩子指针 /
}BiTNode,*BiTree;
图(Graph)的数据结构:
/
ADT 图(Graph)
Data
顶点(vertext)集合与边(edge)集合
Operation
……
end ADT /
typedef char VertexType; / 顶点类型应由用户定义 /
typedef int EdgeType; / 边上的权值类型应由用户定义 /
define MAXVEX 100 / 最大顶点数,应由用户定义 /
define INFINITY 65535 / 用65535来代表∞ /
typedef struct
{
VertexType vexs[MAXVEX]; / 顶点表 /
EdgeType arc[MAXVEX][MAXVEX]; / 邻接矩阵,可看作边表 /
int numNodes, numEdges; / 图中当前的顶点数和边数 /
}MGraph;
//代码效果参考:http://www.zidongmutanji.com/bxxx/105874.html
typedef char VertexType; / 顶点类型应由用户定义 /
typedef int EdgeType; / 边上的权值类型应由用户定义 /
typedef struct EdgeNode / 边表结点 /
{
int adjvex; / 邻接点域,存储该顶点对应的下标 /
EdgeType info; / 用于存储权值,对于非网图可以不需要 /
struct EdgeNode next; / 链域,指向下一个邻接点 */
}EdgeNode;
typedef struct VertexNode / 顶点表结点 /
{
VertexType data; / 顶点域,存储顶点信息 /
EdgeNode firstedge; / 边表头指针 */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes,numEdges; / 图中当前顶点数和边数 /
}GraphAdjList;
2 如何组织代码?
2.1 结构化编程
1966 年 Bohm和Jacpini用数学方法证明了只用三种结构(顺序、选择、重复)和任意数量的布尔型标志就能表示任何算法。
三种结构的一处重要特征就是一个入口和一个出口。代码中只使用三种结构,约束的指令的方向,让代码更易读和维护。
2.2 功能模板化:将代码组织成函数
2.2.1 函数调用关系
函数的调用可以实现代码的模块化与代码重用。
2.2.2 代码参数化:函数回调
2.2.3 类型参数化:函数模板
2.2.4 函数多态
函数多态可以实现一个函数名,多种功能实现,一个接口,多个子类行为。
3 如何组织数据和代码?
3.1 抽象数据类型、类
如果有成千上万个函数,如何组织?将这些函数和函数处理的数据进行分类,封装,做更高一层的抽象,封装成抽象数据类型或类类型。
封装后的抽象类型具有更好的模块性,能够成为设计与框架的基础。
3.2 面向对象的设计原则和设计模式
如果有成百上千个类,可以使用这些类和对象,如同乐高积木一样来搭建程序,这些类如何组织?要实现类内部的高内聚和类间关系的低耦合,这方面的一些套路就是设计模式,其指导思想就是设计原则。
-End-