如果无序表用单链表存储。我们用如下策略提高查找效率:如找到了指定结点,则让它移到
链表的第一个位置,是经常查找的结点尽量靠近表头。试实现这个查找函数
【解】设单链表中的结点类定义如下:
template<class T>
struct node {
T data;
node *next;
};
在带头结点的单链表中的实现见代码清单 7-12。
代码清单
7-12
程序设计题
6
的程序
1. template<class T>
2. node<T> *find(node<T> *head, const T &x)
3. {
4. node<T> *p = head;
5. while(p->next != NULL && p->next->data != x) p = p->next; // 查找 x
6. if(p->next == NULL) return NULL; // x 不存在
7. node<T> *q = p->next; // 在链表中删除 x
8. p->next = q->next;
9. q->next = head->next; // 将 x 插入到表头
10. head->next = q;
11. return q;
12. }
评论0