山东大学：《数据结构》课程教学资源（PPT课件讲稿）第7章 跳表和散列（Skip List and Hashing）

操作‘ Delete tp->link-p->link e first=p ->link first 0 e +1 山东大学计算机科学与技术学院数据结构第7章跳表和散列 11

山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 11 操作 ‘Delete’ first e1 e2 0 en … ei ei-1 … ei+1 tp p first e1 e2 0 en … ei ei-1 … ei+1 p tp=0 tp-> link=p->link first=p ->link

template<class E, class K> Sorted Chain<E, k>& Sorted Chain<E, K> Delete(const k& k, E& e) /删除与k相匹配的元素,并将被删除的元素放入e ∥如果不存在匹配元素,则引发异常 BadInput Sorted chainnode<E,K>*p=frst,*tp=0;∥跟踪p for( p&&p->data<k;tp=p,p=p>link;)搜索与k相匹配的元素 ∥/验证是否与k匹配 if(p&&p->data==k){找到一个相匹配的元素 e=p->data;∥保存data域 if(tp)tp>link=p>link;∥/从链表中删除p所指向的元素 else first=p->link;∥lp是链首节点 delete p, return*this; i throw badInput(O;∥/不存在相匹配的元素 山东大学计算机科学与技术学院数据结构第7章跳表和散列

山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 12 template<class E, class K> SortedChain<E,K>& SortedChain<E,K>::Delete(const K& k, E& e) {// 删除与k相匹配的元素，并将被删除的元素放入e // 如果不存在匹配元素，则引发异常BadInput SortedChainNode<E,K> *p = first, *tp = 0; //跟踪p for (; p && p->data < k; tp = p, p = p->link; )// 搜索与k相匹配的元素 // 验证是否与k匹配 if (p && p->data = = k) {// 找到一个相匹配的元素 e = p->data; // 保存data域 if (tp) tp->link = p->link; // 从链表中删除p所指向的元素 else first = p->link; // p是链首节点 delete p; return *this;} throw BadInput(); // 不存在相匹配的元素 }

操作‘ Distinctinsert first 0 l p first n 山东大学计算机科学与技术学院数据结构第7章跳表和散列 13

山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 13 操作 ‘DistinctInsert’ first e1 e2 0 en … ei ei-1 … ei+1 tp p first e1 e2 0 en … ei ei-1 … ei+1 p tp=0 e q e q

template<class e, class K Sorted Chain<E, K>& Sorted Chain<E, K>: DistinctInsert( const E& e) ∥/如果表中不存在关键值与e相同的元素,则插入e 则引发异常 BadInput Sorted ChainNode<EK>*p=frst,*p=0;∥/跟踪p ∥移动tp以便把e插入到tp之后 for(p&& p->data <e; tp=p, p=p->link) if(p&&p->data==e) throw badinputo;∥检查关键值是否重复 ∥若没有出现重复关键值,则产生一个关键值为e的新节点 Sorted ChainNodee, k> *q= new Sorted ChainNodee, k: q->data=e q->link=p; if(tp)tp>link=q;,∥将新节点插入到tp之后 else first =q: return *this 山东大学计算机科学与技术学院数据结构第7章跳表和散列 14

山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 14 template<class E, class K> SortedChain<E,K>& SortedChain<E,K>::DistinctInsert(const E& e) {// 如果表中不存在关键值与e相同的元素，则插入e //否则引发异常BadInput SortedChainNode<E,K> *p = first, *tp = 0; // 跟踪p // 移动tp 以便把e 插入到tp之后 for (; p && p->data < e; tp = p, p = p->link); if (p && p->data = = e) throw BadInput(); // 检查关键值是否重复 // 若没有出现重复关键值, 则产生一个关键值为e的新节点 SortedChainNode<E,K> *q = new SortedChainNode<E,K>; q->data = e; q->link = p; if (tp) tp->link = q; // 将新节点插入到t p之后 else first = q; return *this; }

操作‘ Insert template<class E, class k> Sorted Chain<E, K>& Sorted Chain<E, K> DistinetInsert(const E&e) 与相同的亓妻,则插入e Sortedchainnode<EK>*p= first,*tp=0;∥跟踪p ∥移动tp以便把e插入到tp之后 for( p&& p->data <e, tp=p, p=p->link); Rad 会态兰估旦 则产生一个关键值为e的新节点 Sorted ChainNode<e, k>*g=new Sorted ChainNode<E, K> q->data=e q->link=p if(tp)tp->link=q;∥将新节点插入到t之后 else first=q; return *this 山东大学计算机科学与技术学院数据结构第7章跳表和散列

山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 15 操作 ‘Insert’ template<class E, class K> SortedChain<E,K>& SortedChain<E,K>::DistinctInsert(const E& e) {// 如果表中不存在关键值与e相同的元素，则插入e //否则引发异常BadInput SortedChainNode<E,K> *p = first, *tp = 0; // 跟踪p // 移动tp 以便把e 插入到tp之后 for (; p && p->data < e; tp = p, p = p->link); if (p && p->data = = e) throw BadInput(); // 检查关键值是否重复 // 若没有出现重复关键值, 则产生一个关键值为e的新节点 SortedChainNode<E,K> *q = new SortedChainNode<E,K>; q->data = e; q->link = p; if (tp) tp->link = q; // 将新节点插入到tp之后 else first = q; return *this; }