图形数据的组织与管理.ppt

计算机图形学 中南大学国土与测绘系主讲 向南平教授E mail harry xiang 第4章图形数据的组织与管理 4 1图形数据的组织4 2图形数据的管理4 3带图形数据I O的交互式图形软件 第4章图形数据的组织与管理 程序是由算法和数据结构两部分组成的 好的程序不但要有好的算法 还需要有好的数据结构 选择和构思一个好的数据结构与编写管理这些数据的程序同样重要 常用的数据组织方式有4种 队列 堆栈 链表和树 这里我们只介绍单向链表结构 4 1 1单向链表的基本结构 单向链表的每一项至少包含两部分内容 一部分为该表项保存的各种信息 另一部分为一个指向链表中下一个表项的指针 其一般形式为 Structtable 该项保存的各种信息 structtable next 指向下一表项的链表指针 单向链表在内存中的影像如下图 4 1 2单向链表的基本特性 单向链表是一种允许随机存取链表中任意项的数据链 链表的取数操作不破坏链表内该项的信息 在队列和堆栈中取数是破坏性的 由于链表的下一项是由链表指针指向的某个内存位置 所以链表不要求放在一块物理上连续的存储区内 对于那些事先不知道数据量大小的应用情况 如图形程序 使用链表是合适的 链表的另一个重要优点是 它可以迅速方便地在数据链中插入或删除一项 而不需要重新整理整个数据链 链表的缺点 它不能象数组一样由下标指定某项进行操作 而必须从链表头开始检索链表 4 2图形数据的管理 图形数据的管理主要包括建立链表 修改链表中的数据项 在链表中插入或删除数据项等 我们仍结合前面的交互式图形例程来讲解 4 2 1图形数据的结构4 2 2图素链表的建立4 2 3链表中数据的遍历4 2 4向单向链表中插入数据项4 2 5在数据链中删除数据项 4 2 1图形数据的结构 1 折线的数据结构structline table intnumpoints xy intcolor structline table next 2 圆的数据结构structcircle table intx y r intcolor structcircle table next 3 矩形的数据结构structbox table intxleft ytop xright ybottom intcolor structbox table next 4 2 2图素链表的建立 建立链表的方法主要有两种 1 把每一个新加入的数据项添加到数据链中间某个位置 主要用于需进行排序 包括升序或降序 的数据项序列 2 把每一个新加入的数据项添加到数据链的头部或尾部 主要用于那些只注重建立链表的顺序 而不需进行数据项排序的场合 在交互式图形程序中 一般更注重原图的绘制顺序 所以图形数据链一般采用该方法建立 下面的例子以该方法建立圆的数据链表 4 2 2图素链表的建立 voidaddcircle intx inty intr intclr 建圆数据链表 structcircle table info NULL 声明一个结构变量 staticstructcircle table last NULL 声明一个静态结构变量 if r 0 0 return 若圆的半径为零 则不向链表中追加该数据项 info structcircle table farmalloc sizeof structcircle table 为新的数据项申请内存空间 if info printf outofmemory return 若未申请到表项内存空间则提示错误信息 并退出函数 info x x 向表项的结构变量x赋值 info y y 向表项的结构变量y赋值 info r r 向表项的结构变量r赋值 info color clr 向表项的结构变量clr赋值 if last circletable circletable info 若链表为空 则当前表项为链表头 elselast next info 否则 使前一表项的info next指向当前表项的首地址 info next NULL 清当前表项的后项指针 last info 将当前表项做为链尾 4 2 2图素链表的建立 函数中last是一个静态结构变量 它保存着链表的尾项 注意 在C语言中 静态变量的初始化只在程序开始执行时进行一次 circletable为一个circle table型的全程结构指针变量 它保存的是链表的表头 4 2 3链表中数据的遍历 对于一个链表 一般不建立一个专门的函数来遍历 即读取 链表中的各项 这是因为链表的遍历比较简单 一般就合并到其它一些对链表的操作中了 如链表的搜索 删除和形式操作 下例以圆链表的刷新显示 说明链表的遍历 voidrefresh void 图形重绘 inti x1 y1 x2 y2 structcircle 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 将链表中下一项作为当前项 4 2 4在数据链中插入数据项 在单向链表中插入数据有三种可能 1 插在最前端 即成为新的链表头 2 插在中部两个表项之间 3 插在最尾部 即成为新的链表尾 下面的例程可实现向链表插入数据并将链表排序 排序是根据圆心的x坐标按升序进行的 4 2 4在数据链中插入数据项 voidInstCircle structcircle table inst structcircle table before structcircle table circletop if circletable circletable inst else before circletable circletop before next if circletop while circletop if before xx 4 2 5在数据链中删除数据 在链表中删除一个数据项的工作更为简单 与插入一个新项类似 删除一项的操作也会遇到三种情况 删除第一项 删除中间项 删除最后一项 删除第一项就会出现新的第一项 因此要修改指向整个链表 即指向链表第一项 的指针 如下例函数 voidDelCircle structcircle table delete inti 1 structcircle table before structcircle table circletop circletop circletable while circletable if circletop x delete x 4 2带图形数据I O的交互式图形软件 本例4 1熔进了本章讲述的内容 将读者说绘图形保存在各自的数据链表中 允许用户将所绘图形以数据文本方