数据结构课程设计 2报告

学号：2008302605 姓名：张坤实验日期：12.28

高维数据检索方法的实现及评价。

一、需求分析：

1. 本程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应的命令，然后计算机根据用户输入的命令执行相应的操作；

2. 程序功能：在给定特征数据集a中寻找待处理数据集bi中每一个元素的最近邻元素（最近邻元素定义为两者之间的欧式距离最小）。

3. 测试数据：给定的八组数据。

二、概要设计：

1. 储存结构定义：

1) “特征数据”结构定义：

typedef struct feature

这里计算的是坐标总和，在另外的两套**中是计算到原点的距离。

2. 建立检索结构模块：

三套**中含有两种检索结构，第一种是平衡二叉树，第二种是静态的顺序表。对两种结构做简单的叙述：

平衡二叉树(insert**l函数)：在这一函数里以到原点的距离为关键字建立平衡二叉树，在具体的建立过程中要进行四种旋转处理。与课本上算法不同的是，若遇到相同的点还需插入到二叉树的结点后的链表中，同时每次在二叉树上插入结点和进行旋转操作时还必须考虑其双亲指针。

为此，对课本上的左旋和右旋函数做了改进。以左旋为例：

status l_rotate(bstree *p)

//对以**p为根的二叉排序树做左旋平衡处理，处理之后*p指向//新的树的根结点，即旋转处理之前的右子树的根结点。

bstree rc;

rc=(*p)->rchild; rc->parent=(*p)->parent;

(*p)->rchild=rc->lchild;

if(rc->lchild) rc->lchild->parent=(*p);

rc->lchild=(*p); p)->parent=rc; (p)=rc;

return ok;

这里以双重指针来实现对*p的改变，就不用将其parent作为函数参数了。

静态顺序表(creat_sqlist函数)：有两套**都用静态顺序表作为检索结构。

若以到原点的距离为关键字检索，在建立静态表时先要统计出数据集a中到原点有多少种不同的距离，种数即为要建立的顺序表l的length的值。然后再用malloc函数申请一个长度为length的redtype型数组l->r。将已得到的到原点的不同距离存入数组l->r每一分量的key域中，再对l->r数组按key进行插入排序。

最后再全搜索数据集a，对每个数据以到原点距离为关键字找到与之相等key在的l->r中的位置，然后再以该数据在数据集a中的位置为关键字插入到该分量后的链表中。

若以坐标总和为关键字，则相对较简单。算法描述如下：

status creat_sqlist(datalist a,sqlistpoint l)

//以坐标总和作为关键字建立检索结果。

l->length=a->total_number; l->r=(redtypelist)malloc((a->total_number+1)*sizeof(redtype0号单元不用。

for(i=1;itotal_number+1;i++)

insertsort(l);/对l中的数组r排序。

3. 检索模块：

第一种算法在具体的检索过程中，对顺序表进行折半查找，对平衡二叉树按树搜索即可。在写查找函数时都对课本的算法做了改进，以保证在找到的情况下返回该结点在检索结构中的位置，若找不到时也返回与之最邻近的结点在检索结构中的位置。例如，课本的折半查找，找不到就返回0，改进后无论找到与找不到均返回mid的指向。

经简单的分析即可得即使在找不到的情况下mid指向的值已为最临近的值了。由于顺序表已经有序，两种检索都能很快的找到相等的点或与之最临近的点。最后各个数据欧式距离的比较，主要集中在各个结点所链的链表中了。

检索结构中寻找前驱和后继时，顺序表通过简单的下标值加减一就能实现。而平衡二叉树则要通过中需遍历该树来实现，这也就是增加parent域的原因。

第二种算法在检索的过程中也是针对有序的顺序表进行折半检索，但结点后无链表故每次检索只得到一个数据的位置而不是一组数据的位置。

两种算法在各个检索结构上检索出数据在a中的位置后，计算出该数据和bi的欧式距离，算出的欧式距离和当前的最短欧式距离比较，若小则更新最短欧式距离，同时更新结果(最终的数据位置)。

由于到原点的距离差距太小，所以两种检索的结束条件均为搜索数据的个数。若个数据到原点的距离差距较大，则可采用在“算法概述”里提到的第一种的结束条件。

数据结构课程设计 2报告

数据结构课程设计报告 2

数据结构课程设计 2

数据结构课程设计报告

其他用户还读了