某个任务的数据模型可以抽象为给定的k个集合:S1,S2,…,Sk。其中Si(1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作,查找和插入时用一个二元组(i,x)来规定一个元素,i是集合的序号,x是元素值。设计一种恰当的数

admin2019-08-01  29

问题 某个任务的数据模型可以抽象为给定的k个集合:S1,S2,…,Sk。其中Si(1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作,查找和插入时用一个二元组(i,x)来规定一个元素,i是集合的序号,x是元素值。设计一种恰当的数据结构来存储这k个集合的元素,并能高效地实现所要求的查找和插入操作。
构造数据结构,并且说明选择的理由。

选项

答案借助于分块查找思想,在建立数据顺序表的同时,建立一索引表。数据表中按k个集合分块(元素个数不一定相等),索引表中有两个域,一是各集合最后一个元素在数据表中的位置(一维数组中的下标),二是集合的个数(k)。实现数据运算时,根据给定的二元组(i,x),首先在索引表中找到集合i的位置,然后在数据表中查找x。查到x,则查找成功,返回咒在数据表中的位置,否则查找失败。若要插入,则将数据表中的数据后移,插入x,同时修改索引表。 typedef struct{datatype data;}rectype; typedef struet{ int a[]; //a数组容量够大,存储备集合最后一个数 据在数据表中的下标 int k; //集合个数 }index; int SetSearch_Insert(rectype R[],index id,datatype x,int i){ //数据表R,查找第i个集合的元素X,若查找成功,返回其位置, //否则将其插入第i个集合 if(i<1 || i>id.k){printf(”无第%d个集合\n”,i);exit(0); } if(i==1)first=0; //first指向第i个集合在数据表的首址 else first=id.a[i一1]+1; last=id.a[i]; //last是第i个集合在数据表中的末址 for(j=first;jid.A[i];j-一){ //查找失败,将x插入数据表 R[j+1]=R[j]; //元素后移 R[j+1]=x; //将x插入到原第i个集合最后一个元素之后 for(j=i;j≤k;j++)id.a[j]++; //修改索引表中各集合最后一个元素的下标 }

解析
转载请注明原文地址:https://kaotiyun.com/show/JkCi777K
0

最新回复(0)