《图形数据的组织与管理.ppt》由会员分享，可在线阅读，更多相关《图形数据的组织与管理.ppt（15页珍藏版）》请在三一办公上搜索。
1、计算机图形学,中南大学国土与测绘系主讲：向南平 教授E-mail:harry.,第4章 图形数据的组织与管理,4.1 图形数据的组织4.2 图形数据的管理4.3 带图形数据I/O的交互式图形软件,第4章 图形数据的组织与管理,程序是由算法和数据结构两部分组成的。好的程序不但要有好的算法，还需要有好的数据结构。选择和构思一个好的数据结构与编写管理这些数据的程序同样重要。常用的数据组织方式有4种：队列、堆栈、链表和树。这里我们只介绍单向链表结构。,4.1.1 单向链表的基本结构,单向链表的每一项至少包含两部分内容，一部分为该表项保存的各种信息，另一部分为一个指向链表中下一个表项的指针。其一般形式为
2、：Struct table(该项保存的各种信息）；struct table*next;/*指向下一表项的链表指针*/;单向链表在内存中的影像如下图：,4.1.2 单向链表的基本特性,单向链表是一种允许随机存取链表中任意项的数据链。链表的取数操作不破坏链表内该项的信息（在队列和堆栈中取数是破坏性的）。由于链表的下一项是由链表指针指向的某个内存位置，所以链表不要求放在一块物理上连续的存储区内，对于那些事先不知道数据量大小的应用情况（如图形程序），使用链表是合适的。链表的另一个重要优点是，它可以迅速方便地在数据链中插入或删除一项，而不需要重新整理整个数据链。链表的缺点：它不能象数组一样由下标指定某项
3、进行操作，而必须从链表头开始检索链表。,4.2 图形数据的管理,图形数据的管理主要包括建立链表、修改链表中的数据项、在链表中插入或删除数据项等。我们仍结合前面的交互式图形例程来讲解。4.2.1 图形数据的结构4.2.2 图素链表的建立4.2.3 链表中数据的遍历4.2.4 向单向链表中插入数据项4.2.5 在数据链中删除数据项,图形数据的结构,1、折线的数据结构struct line_table int numpoints,*xy;int color;struct line_table*next;2、圆的数据结构struct circle_table int x,y,r;int color;s
4、truct circle_table*next;3、矩形的数据结构 struct box_table int xleft,ytop,xright,ybottom;int color;struct box_table*next;,图素链表的建立,建立链表的方法主要有两种：1）把每一个新加入的数据项添加到数据链中间某个位置；主要用于需进行排序（包括升序或降序）的数据项序列。2）把每一个新加入的数据项添加到数据链的头部或尾部。主要用于那些只注重建立链表的顺序，而不需进行数据项排序的场合。在交互式图形程序中，一般更注重原图的绘制顺序，所以图形数据链一般采用该方法建立。下面的例子以该方法建立圆的数据链表
5、。,图素链表的建立,void addcircle(int x,int y,int r,int clr)/*建圆数据链表*/struct circle_table*info=NULL;/*声明一个结构变量*/static struct circle_table*last=NULL;/*声明一个静态结构变量*/if(r=0.0)return;/*若圆的半径为零，则不向链表中追加该数据项*/info=(struct circle_table*)farmalloc(sizeof(struct circle_table);/*为新的数据项申请内存空间*/if(!info)printf(out of me
6、mory.);return;/*若未申请到表项内存空间则提示错误信息，并退出函数*/info-x=x;/*向表项的结构变量 x 赋值*/info-y=y;/*向表项的结构变量 y 赋值*/info-r=r;/*向表项的结构变量 r 赋值*/info-color=clr;/*向表项的结构变量 clr 赋值*/if(!last|!circletable)circletable=info;/*若链表为空，则当前表项为链表头*/else last-next=info;/*否则，使前一表项的info-next 指向当前表项的首地址*/info-next=NULL;/*清当前表项的后项指针*/last=i
7、nfo;/*将当前表项做为链尾*/,图素链表的建立,函数中last是一个静态结构变量，它保存着链表的尾项。注意：在C语言中，静态变量的初始化只在程序开始执行时进行一次。circletable为一个circle_table型的全程结构指针变量，它保存的是链表的表头。,链表中数据的遍历,对于一个链表，一般不建立一个专门的函数来遍历（即读取）链表中的各项。这是因为链表的遍历比较简单，一般就合并到其它一些对链表的操作中了。如链表的搜索、删除和形式操作。下例以圆链表的刷新显示，说明链表的遍历。void refresh(void)/*图形重绘*/int i,x1,y1,x2,y2;struct circl
8、e_table*circletop;/*声明一个结构指针变量作为当前项*/circletop=circletable;/*将链表头赋给当前项*/while(circletop)setcolor(circletop-color);x1=Xpixel(circletop-x);y1=Ypixel(circletop-y);circle(x1,y1,Xpixel(circletop-r);/*以当前表项参数画园*/circletop=circletop-next;/*将链表中下一项作为当前项*/,在数据链中插入数据项,在单向链表中插入数据有三种可能：1）插在最前端，即成为新的链表头；2）插在中部两个
9、表项之间；3）插在最尾部，即成为新的链表尾。下面的例程可实现向链表插入数据并将链表排序，排序是根据圆心的x坐标按升序进行的。,在数据链中插入数据项,void InstCircle(struct circle_table*inst)struct circle_table*before;struct circle_table*circletop;if(!circletable)circletable=inst;else before=circletable;circletop=before-next;if(circletop)while(circletop)if(before-x x,在数据链中删
10、除数据,在链表中删除一个数据项的工作更为简单。与插入一个新项类似，删除一项的操作也会遇到三种情况：删除第一项、删除中间项、删除最后一项。删除第一项就会出现新的第一项，因此要修改指向整个链表（即指向链表第一项）的指针。如下例函数。void DelCircle(struct circle_table*delete)int i=1;struct circle_table*before;struct circle_table*circletop;circletop=circletable;while(circletable)if(circletop-x=delete-x,4.2 带图形数据I/O的交互式图形软件,本例41熔进了本章讲述的内容，将读者说绘图形保存在各自的数据链表中，允许用户将所绘图形以数据文本方式保存到磁盘中，也允许用户将磁盘中保存的图形数据还原成屏幕图形。相应的，程序中设置了一个重绘屏幕图形功能。因此，本程序共有下述功能，分别由一个对应的字母选键进入：1）O 键：将屏幕图形保存到磁盘2）I 键：从磁盘中读取图形3）R 键：屏幕图形重显4）C 键：进入绘图功能5）B 键：进入绘矩形功能6）缺省状态为绘折线功能,
