当前位置：首页 > article >正文

在顺序结构和链式结构的线性表上实现顺序检索算法

article 2025/1/24 2:24:30

线性表中各个结点的检索概率不等，可用于如下策略提高顺序检索的效率：若找到指定结点，则将该结点和其前驱结点（若存在）交换，使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

顺序表实现：

思想：查找指定结点，交换该结点与前驱

代码：

int SeqSrchArray(SSTable s,int key){
	int i=0;
	
	//找指定结点
	while(s.elem[i] !=key && i<s.length) i++;
	
	if(i<s.length && i>0){
		swap(s.elem[i-1],s,elem[i]);
		return i-1;//返回下标 
	} else{
		return -1;
	}
}

链表：

思想：查找指定结点，交换该结点与前驱

代码：


LinkNode * SeqSrchLink(LinkNode *head,int key){
	LinkNode *pre=head;//当前结点前驱
	LinkNode *p=head->next;//当前结点
	
	while(p!=NULL && p->data!=key) {//找指定结点和前驱 
		pre=p;
		p=p->next;
	}
	//找到了指定结点，且有前驱 
	if(p!=NULL && pre!=head){
		swap(pre->data,p->data);
		return pre;
	}else{
		return NULL;
	}
}

查看全文

http://www.kler.cn/a/350113.html