UC知道高分——数据结构题
来源：百度知道 编辑：UC知道 时间：2024/05/10 14:34:51
2-5 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
如果是程序要求完整程序，如果是问答题，请给出数字答案的详细解释。谢谢
2.2若设顺序表中已有n个元素，又设插入火删除表中各元素的概率相等，则在插入是有n+1
个插入位置每个位置插入的概率为1/(n+1)，在删除时有n个删除位置，每个位置删除的概率为1/n
。根据上述推导，插入时平均移动127/2=63.5个元素，删除时平均移动（127-1）/2=63个元素.
2.5#include <iostream.h> //双向循环链表结点的构造函数
DblNode (Type value, DblNode<Type> *left, DblNode<Type> *right ) :
data ( value ), freq ( 0 ), lLink ( left ), rLink ( right ) { }
DblNode (Type value ) :
data ( value ), freq ( 0 ), lLink ( NULL ), rLink ( NULL ) { }
template <class Type>
DblList<Type> :: DblList ( Type uniqueVal ) {
first = new DblNode<Type>( uniqueVal );
first→rLink = first→lLink = first; //创建表头结点
current = NULL;
cout << "开始建立双向循环链表：\n";
Type value; cin >> value;
while ( value != uniqueVal ) { //每次新结点插入在表头结点后面
first→rLink = new DblNode<Type>( value, first, first→rLink );
cin >> value;
}
}
template <class Type