数据结构考研分类复习真题 第五章 答案[28]

（）H(A(aa）B(b）C(cc）x）

HEAD(TAIL(HEAD(H）））=a

（）略

五算法设计题

[题目分析]本题是在向量D内插入元素问题首先要查找插入位置数据x插入到第i个数据组的末尾即是第i+个数据组的开始而第i（≤i≤n）个数据组的首地址由数组s（即数组元素s[i]）给出其次数据x插入后还要维护数组s以保持空间区D和数组s的正确的相互关系

void Insert（int s[]datatype D[]xint im）

//在m个元素的D数据区的第i个数据组末尾插入新数据x第i个数据组的首址由数组s给出

｛if（i<１|| i>n）｛printf（参数错误）exit（０）｝

if（i==n） D[m]=x // 在第n个数据组末尾插入元素

else｛for（j=m;j>=s[i+];j）D[j+]=D[j]; // 第i＋１个数据组及以后元素后移

D[s[i+]]=x; // 将新数据x插入

for(j=i+;j<=n;j++) s[j]++; // 维护空间区D和数组s的的关系

} //结束元素插入

m++; //空间区D的数据元素个数增

}// 算法Insert结束

[算法讨论] 数据在空间区从下标开始最后一个元素的下标是m设空间区容量足够大未考虑空间溢出问题数组s随机存数而向量D数据插入引起数组元素移动时间复杂度是O（n）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []