p-link new ListNodeschar>(w0; int stringl : Find( string l& ob)i /求子串在串中位置(模式匹配) int slen curLen, olen =obcurLen, i=slen -oblen: if( temp i, oblen )==ob) break; else i--: return 1: 3-12试设计一个实现下述要求的 Locate运算的函数。设有一个带表头结点的双向链表L,每个结点 有4个数据成员:指向前驱结点的指针pror、指向后继结点的指针next、存放数据的成员daa和访 问频度∫req。所有结点的freg初始时都为0。每当在链表上进行一次 Locate(L,x)操作时,令元素值为 x的结点的访问频度∫req加1,并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表 中所有结点保持按访问频度递减的顺序排列,以使频繁访问的结点总是靠近表头。 【解答】 #include <iostream h> ∥双向循环链表结点的构造函数 DbINode(Type value, Db/Node<Type> "left, Db/Node<Type> *right DbINode (type value ) data( ralue ) freq (0), ILink( NULL), rLink( NULL)( DblLisk<Type>: DblList( Type unique val) le<Type>( unique val); ∥创建表头结点 cout<<"开始建立双向循环链表:n"; Type t cin > value 每次新结点插入在表头结点后面 first-rLink =new Db/Node<Type>( value, first, first-rLink ) template <class Type> if( p I=first)i ∥链表中存在xp→link = new ListNode<char> ( '\0' ); } int string1 :: Find ( string1& ob ) { //求子串在串中位置(模式匹配) int slen = curLen, oblen = ob.curLen, i = slen - oblen; string1 temp = this; while ( i > -1 ) if ( temp( i, oblen ) == ob ) break; else i-- ; return i; } 3-12 试设计一个实现下述要求的 Locate 运算的函数。设有一个带表头结点的双向链表 L，每个结点 有 4 个数据成员：指向前驱结点的指针 prior、指向后继结点的指针 next、存放数据的成员 data 和访 问频度 freq。所有结点的 freq 初始时都为 0。每当在链表上进行一次 Locate (L, x)操作时，令元素值为 x 的结点的访问频度 freq 加 1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表 中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 【解答】 #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> void DblList<Type> :: Locate ( Type & x ) { //定位 DblNode<Type> *p = first→rLink; while ( p != first && p→data != x ) p = p→rLink; if ( p != first ) { //链表中存在 x