已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data；int freq；struct nextNode*next；}；其中，data为结点值域，freq为该结点元素的访问计数，初始为0；next为指向链表中该结点后继结点的指针域，设该链表所有结点按照freq值从大到小链接。请实现一个时间和空间上尽可能高效率的算法，编写一个查找函数Search，从链表首结点开始查找结点data值与给定值相等的结点。如果找到，则将该结点的freq值加1，然后把它前移到与结点freq值相等的结点的后面，使得所有结点仍然都保持按照freq值从大到小链接。
问答题
给出算法的基本设计思想。
【正确答案】正确答案：基本设计思想：设置3个指针p、pre和q，从链表的首元结点开始，用p作为检测指针顺序检测，比较给定值value与p-＞data，指针pre是亦步亦趋跟在*p后面的前驱指针，为从链中摘下*p而用。另外指针q用于记忆freq下降的结点，为插入结点*p而用。若设链表有n个结点，查找成功时指针*cp停留在第i(1≤i≤n)个结点，则算法的平均查找长度为n(n-1)／2。删除和插入结点*p时仅修改指针。
【答案解析】
问答题
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
【正确答案】正确答案：算法描述如下： boo1 selforganizationList(nextNode *f，int value，nextNode *＆p)； nextNode *pre，*q； p=f-＞next； q=pre=f； while(p!=NULL＆＆p-＞data!=value){ ／／出现次数改变的时候记录q if(pre!=f＆＆pre-＞freq＞p-＞freq) q=pre； pre=p； p=p-＞next； } ／／找不到的时候返回 if(p==NULL) return false； p-＞freq++； pre-＞next=p-＞next； p-＞next=q-＞next; q-＞next=p； return true， }；
【答案解析】
问答题
说明你所设计算法的时间复杂度与空间复杂度。
【正确答案】正确答案：空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。 时间复杂度分析：整个算法只会对链表进行一次扫描，扫描的时候把需要的信息都记录下来，然后用O(1)的时间完成链表的修改。因此，整个算法的时间复杂度为O(n)。
【答案解析】