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

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

admin2019-08-01  54
问题 某个任务的数据模型可以抽象为给定的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://www.kaotiyun.com/show/JkCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)