72线性表描述 有序线性表:L=(e1re2,e3r…,en) ■关键字从左到右依次增大 在计算机存储器中的数据描述 ■公式化描述 链表描述 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 6 7.2 线性表描述 ◼ 有序线性表: L = (e1 , e2 , e3 , …, en ), ◼ 关键字从左到右依次增大 ◼ 在计算机存储器中的数据描述 ◼ 公式化描述 ◼ 链表描述
链表描述的有序线性表(字典) 采用链表描述的有序线性表——有序链表 ■类 Sorted Chain 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 7 链表描述的有序线性表（字典） ➢ 采用链表描述的有序线性表——有序链表 ◼ 类 SortedChain
类 Sorted chain first e template< class e; class K>>//E:链表元素,K:关键字。 class Sorted ChainNode& Friend sorted chain<EK> private e data Sorted chainnode< ek> link 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 8 类 SortedChain template<class E ,class K> >//E:链表元素，K:关键字。 class SortedChainNode{ Friend SortedChain<E,K> private: E data; SortedChainNode< E,K > *link; } ; first e1 e2 0 en … ei ei-1 … ei+1
Class sorted chain template<class e, class K> class Sorted Chain( public Sorted(first=0; sorted Chain bool isemptyo const return first==0; int Lengthy const bool search(const K&k, e& e)const Sorted chain<E, K>& delete(const K&k, e& e Sorted chain<EK>& Insert( const e&e)许关键字相同 Sorted chain<EK>& DistinctInsert( const ec&e)/不允许关 键字相同 private Sorted chainnode<e k> *first 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 9 Class SortedChain template<class E ,class K> class SortedChain{ public : SortedChain() {first =0;} ~SortedChain(); bool IsEmpty() const {return first = =0;} int Length() const; bool Search(const K& k , E& e) const; SortedChain<E ,K>& Delete(const K& k , E& e); SortedChain<E ,K>& Insert(const E& e);//允许关键字相同 SortedChain<E ,K>& DistinctInsert(const E& e);//不允许关 键字相同 private: SortedChainNode<E ,K> *first; } ;
操作 search template<class E, class K> bool Sorted chain<e, K>: Search(const K&k, e& e)const /搜索与k匹配的元素,结果放入e,返回true ∥如果没有匹配的元素,则返回 false Sorted ChainNodee, K> * p=first for(;p&&p>data<k;p=p->link),∥搜索与k相匹配的元素 ∥验证是否与k匹配 if(p&&p->data==k)∥与k相匹配 te=p->data; return true; i return false;∥/不存在相匹配的元素 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 10 操作 ‘search’ template<class E, class K> bool SortedChain<E,K>::Search(const K& k, E& e) const {// 搜索与k匹配的元素，结果放入e,返回true. //如果没有匹配的元素，则返回false SortedChainNode<E,K> *p = first; for (; p && p->data < k;p = p->link); // 搜索与k相匹配的元素 // 验证是否与k匹配 if (p && p->data = = k) // 与k相匹配 {e = p->data; return true;} return false; // 不存在相匹配的元素 }