使用工具：Djgpp(编译器以及相关工具集), Allegro（游戏函数库）
基本简介：
这是一个支持基本计算统计功能和其他一些表格管理/处理功能的计算机软件，用户可在该软件的支持下，用交互方式进行表格建立、数据输入、数据编辑及其他一些表格操作。
功能：
1.建立表格
2．输入数据与编辑数据
通过键盘将数据输入到显示在屏幕上的电子表格上，支持基本的数据输入编辑。能通过左右、Delete等键编辑，方便用户。
3．基本统计计算
基本支持统计计算。由于时间等原因，没有把单元块功能写进公式分析里面，造成原计划使用写好的公式支持去支持统计，而使用对话框形式也没空去实现。目前只能手动进行求和，平均等。例如，=Sum(a1,b3,…)
4．排序
使任一行/列中的数据按大小（升或降）排列，对字符串型数据，可选大小写敏感。
5．表格保存
使电子表格存储在磁盘上（磁盘文件），并可随时读入，供继续处理。
6．数据复制
将表格中任一块数据，复制到另一块中。复制到目标快时，对目标快中原内容，可选择下列几种处理方式：
代替（己实现）
相加(留下接口，没有实现)
相减(留下接口，没有实现)
按条件替换(留下接口，不能确保实现)
7．公式支持
单元格内可输入公式（表达式），使对应单元格的最终内容为公式的计算结果。
公式最基本的形式是算数计算公式。公式中可以按名引用其他单元格（或单元格构成的单元块）。
公式中支持预定义的数学函数(Sum,Avg,Max,Min)，字符处理函数(Left,Len)。
7．对话功能支持
使用了菜单，按钮能熟悉的界面，亲切友好，便于使用。
8．鼠标支持
支持鼠标控制，使用了拦截鼠标中断的技术，确保了实时性。
9 支持中文
支持汉字显示、输入（试验部分，存在问题）
10.超大表格支持
使用改良的数据结构，具有更好的稀疏性，保持内存空间的高利用率，从而支持超大表格。
11.运行在32位保护模式下
直接利用所有内存，更好的段保护，确保程序的安全。
功能基本符合设计要求。
设计分析：
综述
本次设计使用Djgpp作为编译器，直接在保护模式下跑。经过测试，在win98的Dos Console 的DPMI 下，能顺利运行。利用Allegro提供的强大图形功能，工作在 800 X 600 ,16 bit的环境下。中文显示方面，利用Allegro的Unicode功能，补写了GB编码的解码代码并丛HZK16、ASC16生成对应字库。界面管理方面，参考了Windows的设计思想，通过消息去管理各种窗口，同时也借鉴了MFC的继承处理消息思想。而在数据内部，通过改良的十字链表做到大表的支持。
下面就数据结构、保护模式、图形函数运用、字符串分析以及界面设计管理等方面展开分析。
●数据结构：
采用了二次稀疏十字链表储存电子表格。采用十字链表是因为十字链表在行列顺序读取方面拥有先天优势，适合被电子表格的数据统计功能运用。
普通十字链表的数据部分是稀疏的，但是存放头接点却是使用数组形式。如果表格非常大，光头结点就耗费大量内存。
下面以我制作的电子表格为例，分析改进的好处。现要求支持一个 702 X 65536 的表格。
参看数据结构：
struct CCell
{
char attrib;
union
{
char text[80];
double value;
struct
{
char attrib;
double fvalue;
char ftext[80];
char formula[80];
} f;
} v;
};class CrsNode
{
public:
long row,col;
CCell Data;
CrsNode *down,*right;
};
class CrsNodeHead:public CrsNode
{
public:
int ColWidth;
int Col_Item_Count;
int Row_Item_Count;
};
Ccell为基本存储单元，存储各单元格的值。CrsNode为十字链表的基本结点，包含一个Ccell和行列记录变量Row,Col；CrsNodeHead是管理头结点，丛CrsNode派生，增加成员Col_Item_Count、Row_Item_Count和ColWidth用以记录管理数据。
一个 702 X 65536 的表格要求有65536个头结点。经过测试：sizeof(CCell)为176，sizeof(CrsNode)为192，sizeof(CrsNodeHead)为204。
如果采取旧有的方式，头数组固定大小为65536 X sizeof(CrsNodeHead) =64k X 204B = 12.75MB。 也就是说一个空表就耗费 几乎13MB的内存空间。一个完全填满的100 x 100 子表，耗费12.75+10000 X 176 =12.75 + 1.678 = 14.428 MB。 用户数据比例:1.678/14.428=11.63%。
改进后，现在把头接点存在额外的一个链表中，一个存放头结点的 节点耗费 204 + 4(一个int) =208B，一个完全填满的100 x 100 子表， 耗费 100 X 208B + 10000 X 160B =1.55 MB。用户数据比例：1.53/1.55=98.7%。
空间利用率明显上升。同时，头结点可以放手增加成员变量，不用复用变量，方便了管理而且不容易由于名字的问题而产生不必要的变成错误，而不用担心空间耗费的问题。
十字链表声明：
class CrsLink
{
struct _CrsHeadNode
{
int num;
CrsNodeHead *head;
};
CrsNode* NextRightNode,*NextDownNode; //Pre Read Cacheing!
TLinkList<_CrsHeadNode> HeadList;
long MaxRow,MaxCol;
public:
……………
CCell * GetNextCell(int Mode); //Can be ROW or COL
………
};
增加了 CrsNode* NextRightNode,*NextDownNode 两个成员变量，在每次set 和 get 等操作中，记下操作单元格的 下一个和右一个单元格的指针，从而在连续行列操作中，通过调用GetNextCell函数快速取得指针，而不用重新搜索。
●保护模式：
在仔细设计十字链表后，发现实模式下只直接支持1MB一下的内存，要利用1MB以上内存，还要学习XMS的使用。时间有限，无法一一研究。最后采用Djgpp编译，从而直接支持大内存，段保护。使用上，没有汇编的痛苦，用Djgpp编译C++就可以了。同时，通过DPMI，也支持虚拟内存。正是由于虚拟内存的引入，在写中断代码的时候，一定要使用函数锁定代码里面涉及的内存段，包括使用到的全局变量，局部变量，代码段，堆栈段等，否则会由于换页的问题而出错。查Djgpp文档得知，C/C++难以知道代码段、使用到的堆栈区地址等。所以设计里面屏蔽了虚拟内存的支持。
●图形模式：
原计划使用文本方式，这样可以直接利用中文系统支持中文。后考虑到现在流行GUI，而且在字符模式下，限制了一屏显示内容。最后选用Allegro这个游戏开发库作为图形库，搭配Djgpp进行开发。Allegro是Internet上由自由开发者联合开发的游戏库，能方便的支持动画播放，声卡支持，直接写屏等强大的功能，是写游戏的好助手。这里仅仅利用到它的Svga图形支持和鼠标，键盘中断拦截。
类似Borland C++的图形库，使用allegro_init()作为总初始化后，可以马上通过set_gfx_mode()切换显示模式。不像BC的图形库，它支持1024 X 768@ 32 bit 这样的Svga显示模式，使得作品在颜色上更加的丰富细致。textout等一系列函数，作为打印文本到屏幕。Allegro的textout使用非常方便，而且能随时更换输出用字体。Allegro使用了BITMAP的概念，而所有的Drawing的对象都是BITMAP。屏幕作为一个常用BITMAP全局存在，称为screen。
还有sub_bitmap的概念，就是原bitmap的一个局部引用。这次设计利用了这点，通过创建screen的sub bitmap，使得窗口里面的画图使用相对坐标，而且不用切换，而又同时直接写到屏幕上了。
●公式的字符串分析：
公式包括有 括号、运算符、数字和单元名称。使用了递规分治的方法，不考虑子部分的处理，首先，会把公式分拆成零散的部分，递规运算部分的值，然后再算整体的值，最后填充返回信息。分拆流程图见下：
struct _Token
{
union
{
float Value;
char Text[40];
char Operator;
} Result;
int ResultType;/* */
int Type; /*TEXT,VALUE,FORMULA,OPERATOR,CELL,CELLRANGE,OTHERS */
char Content[80];
_Token *pSub,*pNext,*pParent;
};
struct CalcBlock
{
union
{
float Value;
char Op;
} c;
int Type;
};
struct Range
{
int start,end;
};
struct ParseRes
{
union
{
float Value;
char Text[40];
} Result;
int ResultType;
};
详细分割计算过程：首先，ParseIt函数经过简单的括号对应检查和浮点输入格式检查以后，去掉多余空格，并且去掉”=”号。生成母Token，交给Parse函数处理。Parse接手，判断类型。通过看典型特性，入公式比较长，有操作符；单元格为前面ascii后面数字等。如果是公式类型外的类型，能直接得到值，马上就能返回。如果是公式，还要把整个字符串分割成独立部分。独立部分是由括号和操作符分割的。 当分割完成以后，按照RangeList的起止位置，截取字符串到各新生成之Token的Content里面。填充pSub,pNext,pParent指针。(Token详细解释见后) 然后，把各新的Token再次用Parse处理，检查他们计算的返回结果，如果正确就继续，否则返回BAD。经过上面的步骤，已经把函数、单元格和括号等影响直接计算的东西分块计算好，剩下的只能是简单的由四则运算符连接的值，这里把操作符也算为一种独立部分，所以TOKEN也有OPERATOR类型。总之，这里的Token类型只能是：VALUE,OPERATOR,EMPTY，其他的类型如果存在将被忽略。由于Token结构复杂，不方便运算。又再次转换为CalcBlock结构。运算采取如下策略：从左扫描CalcBlock链表，发现有’*'或’/'就把运算符两边的CalcBlock计算合拼，然后重来。直到不能发现任何乘除号，从左顺序加减各CalcBlock，得到最后结果，填充Token的ResultType为VALUE,Result.Value为运算结果。结束Parse.最后ParseIt把生成Token多叉树删除。填充返回的ParseRes结构。
关于Token：Token其实就是一个多叉树的结点。pSub指向首子树，pNext指向兄弟，pParent指向父亲。ResultType和Result一起，表示这个Token的计算结果的类型，可以是数值、字符串和操作符。而Type表示这个Token的类型，可以是公式，单元格，数值，字符串等。Max(3,4)的Tpye是FORMULA，而ResultType是VALUE,Result.Value是4。Token的递规解释见下图：
从图上可以看出，当分解到一个基本计算单位的时候，就可以得到结果，返回信息了。而相应的上一层，就能计算出结果。
●界面Windows和消息管理：
由于程序有着各种各样的窗口，参照Windows设计，也把各种各样的UI Windows化。参见CWnd定义。
struct _Token
{
union
{
float Value;
char Text[40];
char Operator;
} Result;
int ResultType;/* */
int Type; /*TEXT,VALUE,FORMULA,OPERATOR,CELL,CELLRANGE,OTHERS */
char Content[80];
_Token *pSub,*pNext,*pParent;
};
struct CalcBlock
{
union
{
float Value;
char Op;
} c;
int Type;
};
struct Range
{
int start,end;
};
struct ParseRes
{
union
{
float Value;
char Text[40];
} Result;
int ResultType;
};
一个CWnd对象，记录了在屏幕中的位置，大小，能否隐藏等信息。pWndArea储存了前面提及的Sub_bitmap，所有在CWnd里面的画图，都是画在它上面，从而得到画图与窗口屏幕位置无关。PParent储存了父窗口，为消息传递服务。CWnd还有两个关键函数：Draw，WndProc。Draw负责画出窗体内容，而WndProc则负责处理消息。他们都为虚拟函数，这为以后的派生扩充提供了可能性。可以看到，CWbd::Draw为纯虚函数，这表明CWnd无法生成实体，所有的窗体都得以CWnd为蓝本，起码得提供自己得Draw才能生成对象。在这里，CWnd::WndProc提供最基本的消息服务，把送过来的各种鼠标事件，键盘事件调用正确转换参数，送到相应的处理虚拟函数中，并释放参数空间。以后派生的窗口如果要用到基本事件，可以写一个自己的事件处理虚拟函数，即可被CWnd::WndProc调用，而不用纠缠于参数转换释放等麻烦中。例如CEditCtrl，要处理OnMouseLDown，只要声明有OnMouseLDown虚函数并填写内容即可。
消息：消息可以是窗体之间沟通的信息，也可以是用户通过键盘或鼠标输入的信息。所有这些信息，都通过Capp::SendMessage函数发送到统一的消息管理队列Capp::MsgQ中。MsgQ采用的是数组循环式储存的队列。整个程序运行以后，经过初始化，就进入一个大循环中。循环不断检查是否有新消息，没有则继续循环等待。如果有，首先，通过TranslateMsg去把信息预处理一下，然后发送给相应的窗体，把对头指针后挪一位。继续处理下一条消息或等待。
预处理的任务就是把发送过来的基本鼠标事件转换成特定鼠标事件，以及产生MouseOut，ClickOut等状态变换触发事件和处理全局热键。转换为特定鼠标事件，就是按照鼠标所处的位置，判断目前在哪个窗体上，也就是按键事件发生在哪里。然后把鼠标的按键信息跟窗体对象组合起来，另外把MOUSE_ACTION这个普通鼠标消息转换为特定的LDOWN之类的消息。这里涉及判断窗口的问题。我是通过CWnd::Layer来辅助判断的。因为窗口极可能重叠，而消息只能是送到最上层，所以检索的时候发现鼠标坐标在窗体中，并不马上认为就是发生在相应窗体，而是记录下Layer数值，找到更大的就把相应的窗体指针再记录下来，最后Layer最大的窗体获胜。Layer的赋值发生在对象Show的时候，其值为父窗口的Layer+1。另外，为方便使用，还设置了锁定对象的功能。如果锁定标志变量不为NULL，所有消息无条件发送到指定窗体。
消息的流动：当目前WndProc无法处理发过来的消息，可以选择两条路发送：发往父窗口或送父类的窗体处理。不过这些都要求程序员手动在消息处理函数尾部加上代码。例如，CeditCtrl的WndProc无法处理Mouse_LDOWN，可以发送到父类CWnd处理：CWnd::WndProc(Message,Parm1,Parm2)，也可以发送到父窗口：pParent->WndProc(Message,Parm1,Parm2)。
总结：首次尝试使用BC以外的编程环境，开始不是很适应。由于不是商业软件的缘故，功能虽然强大，单有些细节部分感觉不够友好。Djgpp的最佳IDE RHIDE虽然自带调试器，单对我的显卡支持不好，唯有选择用命令行的GDB去调试。另外，个人感觉每个DPMI Server都有自己的特性。Windows提供的DPMI居然在有些时候，可以取一个NULL指针内容而不发生段保护错！以致留下隐患，表现为后期的一些正确语句反而产生保护错。Dos的CWSDPMI相对不会，但是Djgpp由于直接从Linux下的Gcc Port到Dos,没有考虑长文件名的问题，有些内定库文件是长文件名的，在Dos下无法正常编译。所以最后还是使用Windows Console作为开发平台。可能也是这个原因，目前有些错误实在是找不到错处，无法修正。
虽然借鉴了Windows的设计，仿照窗体的概念，但缺乏系统的分析，整个底层系统都是在边开发应用程序发现需求边修改搞出来的。很不系统，而且感觉还有很多的漏洞和不足。目前最明显就是无法做到好像Windows MFC变成那样，DoModal。因为设计上所有的窗口响应了事件，就马上回到主循环里面。所以目前选择了“打开文件”对话框，依然能选菜单。而唯一能屏蔽住的，就是特意写的Evil_MessageBox函数。因为要求函数把主消息循环屏蔽掉，自己用自己的消息循环，很麻烦，无法推广。
Leave a passing comment »
Leave a Reply