Chapter3 Data Representation Linear Lists Formula-Based Representation Linked Representation Indirect Addressing Simulating Pointers 11/15/2018

本章重点 公式化描述、链表、间接寻址（查找、插入、删除）。 箱子排序、基数排序。 11/15/2018

数据描述 数据不同的描述形式。 最常见的数据描述方法：公式化描述、链接描述、间接寻址和模拟指针。 11/15/2018

数据描述 在公式化描述中，元素地址是由数学公式来确定的； 在链接描述中，元素地址分布在每一个表元素中； 在间接寻址方式下，元素地址则被收集在一张表中。 11/15/2018

3.2 Linear Lists 线性表，实例形式为 (e1,e2,...en)，其中n 是有穷自然数。ei 是表中的元素，n 是表的长度。元素可以被视为原子，因为它们本身的结构与线性表的结构无关。 当n=0 时，表为空；当n>0时，e1是第一个元素，en是最后一个元素，可以认为el优先于e2，e2 优先于e3，如此等等。 除了这种优先关系之外，在线性表中不再有其他的结构。 11/15/2018

线性表上的操作 • 创建一个线性表。 • 确定线性表是否为空。 • 确定线性表的长度。 • 查找第k个元素。 • 查找指定的元素。 11/15/2018

ADT 3-1 线性表的抽象数据类型描述 抽象数据类型LinearList{ 实例 0或多个元素的有序集合 操作 Create():创建一个空线性表 Destroy():删除表 IsEmpty():如果表为空则返回true，否则返回false Length():返回表的大小(即表中元素个数) Find(k,x):寻找表中第k个元素，并把它保存到x中；如果不存在，则返回false Search(x):返回元素x在表中的位置；如果x不在表中，则返回0 Delete(k,x):删除表中第k个元素，并把它保存到x中；函数返回修改后的线性表 Insert(k,x):在第k个元素之后插入x；函数返回修改后的线性表 Output(out):把线性表放入输出流out之中 } 11/15/2018

3.1 Formula-Based Representation 公式化描述采用数组来表示一个对象的实例。 数组中的每个位置被称之为单元(cell)或节点(node)。 每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。 11/15/2018

映射 使用数组来描述表，需要把表中的每个元素映射到数组的具体位置上。 可用数学公式来确定每个元素的位置。一个简单的映射公式如下：location(i )= i – 1 指明表中第i个元素(如果存在的话)位于数组中i-1位置处。 11/15/2018

公式化描述 11/15/2018

线性表的顺序存储结构示意图 逻辑地址 数据元素 存储地址 k0 Loc(k0) 1 k1 Loc(k0)+c … i ki k0 Loc(k0) 1 k1 Loc(k0)+c … i ki Loc(k0)+i*c n-1 kn-1 Loc(k0)+(n-1)*c 11/15/2018

程序3-1基于公式的类LinearList template<class T> Class LinearList{ public: LinearList(int MaxListSize=10);//构造函数(Create) ~LinearList(){delete []element;}//析构函数(Destroy) bool IsEmpty()const{return length==0;} 复杂性 O(?) int Length()const{return length;} 复杂性 O(?) bool Find(int k,T& x)const;//返回第k个元素至x中 int Search(const T& x)const;//返回x所在位置 LinearList<T>& Delete(int k,T& x);//删除第k个元素并将它返回至x中 LinearList<T>& Insert(int k,constT& x);//在第k个元素之后插入x void Output(ostream& out)const; }; 11/15/2018

程序3-1基于公式的类LinearList template<class T> Class LinearList{ private: int length; int MaxSize; T *element;//一维动态数组 }; 11/15/2018

操作-Create template<class T> LinearList<T>::LinearList(int MaxListSize) {//基于公式的线性表的构造函数 MaxSize=MaxListSize; element=new T[MaxSize]; length=0; } 11/15/2018

操作-Find template<class T> bool LinearList<T>::Find(int k,T& x)const {//把第k个元素取至x中 //如果不存在第k个元素则返回false，否则返回true if(k<1||k>length) return false;//不存在第k个元素 x=element[k-1]; return true; } 复杂性 O(?) 11/15/2018

操作-Search template<class T> int LinearList<T>::Search(const T& x)const ( //查找x，如果找到，则返回x所在的位置 //如果x不在表中，则返回0 for(int i=0;i<length;i++) if(element[i]==x) return ++i; return 0; } 复杂性 O(?) 11/15/2018

删除元素 为了从一个表中删除第k个元素，需要首先确认表中包含第k个元素，然后再删除这个元素。 如果表中不存在第k个元素，则出现一个异常。 11/15/2018

操作-Delete template<class T> LinearList<T>& LinearList<T>::Delete(int k,T& x) {//把第k个元素放入x中，然后删除第k个元素 //如果不存在第k个元素，则引发异常OutOfBounds if(Find(k,x)){//把元素k+l,...向前移动一个位置 for(int i=k;i<length;i++) element[i-l]=element[i]; length--; return *this; } else throwOutOfBounds(); } 复杂性 O(?) 11/15/2018

插入元素 为了在表中第k个元素之后插入一个新元素，首先需要把k+1至length元素向后移动一个位置，然后把新元素插入到k+1位置处。 11/15/2018

操作-Insert template<class T> LinearList<T>& LinearList<T>::Insert(int k,const T& x) { //在第k个元素之后插入x //如果不存在第k个元素，则引发异常OutOfBounds //如果表已经满，则引发异常NoMem if(k<0||k>length) throw OutOfBounds(); if(length==MaxSize) throw NoMem(); //向后移动一个位置 for(int i=length-1;i>=k;i--) element[i+l]=element[i]; element[k]=x; length++; return *this; } 复杂性 O(?) 11/15/2018

操作-Output template<class T> void LinearList<T>::Output(ostream& out) const { //把表输送至输出流 for(int i=0;i<length;i++) out<<element[i]<<""; } 复杂性 O(?) 11/15/2018

重载<< template <class T> ostream& operator<<(ostream& out, const LinearList<T>& x) { x.Output(out); return out; } 11/15/2018

使用类LinearList的C++程序 void main(void) { LinearList<int> L(5); cout<<"Length="<<L.Length()<<endl<<"IsEmpty="<<L.IsEmpty()<<endl; L.Insert(0,2).Insert(1,6); cout<<"List is"<< L <<endl<<"IsEmpty="<<L.IsEmpty()<<endl; int z; L.Find(1,z); cout<<"First element is"<<z<<"Length="<<L.Length()<<endl; L.Delete(1,z); cout << "Deleted element is " << z << endl; cout << "List is " << L << endl; } 11/15/2018

线性表顺序存贮优点 不需要为表示结点间的逻辑关系而增加额外的存储空间 可以方便的随机存取表中的任一结点 11/15/2018

线性表顺序存贮缺点 插入、删除元素需要移动表内数据。 空间需要事先申请，专用，空闲空间不能共享。 容量难以扩充。 11/15/2018

3.3 Linked Representation 在链表描述中，数据对象实例的每个元素都放在单元或节点中进行描述。 不过，节点不必是一个数组元素，因此没有什么公式可用来定位某个元素。 取而代之的是，每个节点中都包含了与该节点相关的其他节点的位置信息。这种关于其他节点的位置信息被称之为链(link)或指针(pointer)。 11/15/2018

3.3 Linked Representation 令L= (e1,e2, ...,en)是一个线性表。 链表描述中，每个元素ei 都放在不同的节点中加以描述。 每个节点都包含一个链接域，用以指向表中的下一个元素。所以节点ei 的指针将指向ei + 1，其中1≤i＜n。节点en 没有下一个节点，所以它的链接域为N U L L (或0 )。 指针变量first 指向描述中的第一个节点。 11/15/2018

链表描述 每个链表节点都正好有一个链接域，所以该链表结构称为单向链表(singly linked list)。 11/15/2018

单链表 特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充 11/15/2018

单链表的存储映像 11/15/2018

节点类 template<class T> class ChainNode{ friend Chain<T>; private: T data; ChainNode<T> *link; }; 11/15/2018

程序3-8链表的类定义 template<class T> class Chain{ public:Chain(){first=0;} ~Chain(); bool IsEmpty() const{ return first==0; } int Length()const; bool Find(intk,T& x) const; int Search(constT& x) const; Chain<T>& Delete(int k,T& x); Chain<T>& Insert(int k,constT& x); void Output(ostream& out)const; private: ChainNode<T> *first;//指向第一个节点的指针 }; 11/15/2018

操作-删除链表中的所有节点 template<class T> Chain<T>::~ Chain( ) {// 链表的析构函数，用于删除链表中的所有节点 ChainNode<T> *next; // 下一个节点 while (first) { next = first->link; delete first; first = next; } } 复杂性 O(?) 与公式化描述比较? 11/15/2018

操作-确定链表的长度 template<class T> int Chain<T>::Length() const (// 返回链表中的元素总数 ChainNode<T> *current = first; int len = 0; while (current) { len++ ; current = current->link; } return len;} 复杂性 O(?) 与公式化描述比较? 11/15/2018

操作-在链表中查找第k个元素 template<class T> bool Chain<T>::Find(int k, T& x) const { // 寻找链表中的第k个元素，并将其传送至x //如果不存在第k个元素，则返回false，否则返回true if (k < 1) return false; ChainNode<T> *current = first; int index = 1; // current的索引 while (index < k && current) { current = current->link; index++ ; } if (current) {x = current->data; return true;} return false; // 不存在第k个元素 } 复杂性 O(?) 与公式化描述比较? 11/15/2018

操作-在链表中搜索 template<class T> int Chain<T>::Search(const T& x) const { // 寻找x，如果发现x，则返回x的地址 //如果x不在链表中，则返回0 ChainNode<T> *current = first; int index = 1; // current的索引 while (current && current->data != x) { current = current->link; index++ ; } if (current) return index; return 0;} 复杂性 O(?) 11/15/2018

操作-输出链表 template<class T> void Chain<T>::Output(ostream& out) const {// 将链表元素送至输出流 ChainNode<T> *current; for (current=first; current; current=current->link) out << current->data << " "; } 复杂性 O(?) //重载< < template <class T> ostream& operator<<(ostream& out, const Chain<T>& x) {x.Output(out); return out;} 11/15/2018

链表删除方法 11/15/2018

删除运算: 若删除ai (i≠1) ，其步骤如下: ① 使ai的直接后继成为ai-1的直接后继 ② 释放结点ai所占用的存储空间 ① … ai-1 ai ai+1 ②

若删除a1，则步骤如下: ② ① 使a2成为首结点 head a1 … a2 ② 释放结点a1所占 用的存储空间 ①

操作-从链表中删除元素 P134 template<class T> Chain<T>& Chain<T>::Delete(int k, T& x) {// 把第k个元素取至x，然后从链表中删除第k个元素 //如果不存在第k个元素，则引发异常OutOfBounds if (k < 1 || !first) throw OutOfBounds(); //不存在第k个元素 //1.链为空 // p最终将指向第k个节点 ChainNode<T> *p = first; // 将p移动至第k个元素，并从链表中删除该元素 if (k == 1) // p已经指向第k个元素 //2.删除首结点 first = first->link; // 删除之 11/15/2018

操作-从链表中删除一个元素 else ( // 用q指向第k - 1个元素 //3.删除其它结点 ChainNode<T> *q = first; for (int index = 1; index < k - 1 && q; index++) q = q->link; if (!q || !q->link) throw OutOfBounds(); //不存在第k个元素 p = q->link; // 存在第k个元素 q->link = p->link; ) // 从链表中删除该元素 //保存第k个元素并释放节点p x = p->data; delete p; return *this;} 复杂性 O(?) 与公式化描述比较? 11/15/2018

链表插入 11/15/2018

插入运算：若将x插入在ai之后，则插入步骤如下: … ai ai+1 ③ ② ① q x ① 创建新结点q , q ->data ← x ② 使ai的直接后继成为q 的直接后继 ③ 使q成为ai的直接后继

若将x插入在a1之前，则插入步骤如下: ① 创建新结点q , q ->data ← x head ② 使a1成为q 的直接后继 ③ ②

操作-向链表中插入元素 P135 template<class T> Chain<T>& Chain<T>::Insert(int k, const T& x) {// 在第k个元素之后插入x (k>=0) / /如果不存在第k个元素，则引发异常OutOfBounds // 如果没有足够的空间，则传递NoMem异常 if (k < 0) throw OutOfBounds(); // p最终将指向第k个节点 ChainNode<T> *p = first; / /将p移动至第k个元素 for (int index = 1; index < k && p; index++) p = p->link; 11/15/2018

操作-向链表中插入元素 if (k>0 && !p) throw OutOfBounds();//不存在第k个元素 // 插入 ChainNode<T> *y=new ChainNode<T>; y->data = x; if (k) {// 在p之后插入 y->link = p->link; p->link = y;} else {// 作为第一个元素插入 y->link = first; first = y;} return *this; } 复杂性 O(?) 与公式化描述比较? 11/15/2018

操作-扩充 程序3-16 删除链表中的所有节点 template<class T> void Chain<T>::Erase() { //删除链表中的所有节点 ChainNode<T> *next; while (first) { next = first->link; delete first; first = next;} } //可以把类的析构函数简单地定义为对Erase的调用。 11/15/2018

操作-在链表右端添加一个元素 template < class T > Chain<T> & Chain < T > ::Append(const T& x) { //在链表尾部添加x ChainNode< T > *y = new ChainNode<T>; y->data = x; y->link = 0; if (first) {//链表非空 last->link = y; last = y;} else // 链表为空 first = last = y; return *this;} 复杂性 O(?) 11/15/2018

思考 假定Output不是Chain类的成员函数，如何输出链表？ 11/15/2018

方案 int len = X.Length(); for (int i = 1;i<= len;i++) { X.Find(i,y) ; cout << y << ' ' ; } 复杂性 O(?) 11/15/2018

如何提高性能？ 许多使用链的应用代码都要求从链表的第一个元素开始，从左至右依次检查每一个元素。 11/15/2018

链表遍历器 遍历器的功能是纪录当前位置并每次向前移动一个位置。 11/15/2018

链表遍历器组成 私有变量location，用来跟踪我们在链表中所处的位置。 共享成员Initialize。返回一个指针，该指针指向第一个链表节点中所包含的数据，同时把设置为指向链表的第一个节点。 共享成员Next。用来调整location，使其指向链表中的下一个节点，并返回指向该节点数据域的指针。 11/15/2018

链表遍历器类 template<class T> class ChainIterator { public : T* Initialize(const Chain<T>& c) {location = c.first; if (location) return &location->data; return 0;} T* Next() {if (!location) return 0; location = location->link; private: ChainNode<T> *location; } ; 11/15/2018

采用链表遍历器输出整数链表 Int *x; ChainIterator<int> c; x=c.Initialize(X); while(x){ cout<<*x<<''; x=c.Next(); } cout<<endl; 复杂性 O(?) 11/15/2018

带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。 first a1 an first last last 非空表 空表 11/15/2018

first … first … first 不带头结点的单链表 a1 a2 an ∧ 开始结点 终端结点 带头结点的单链表（非空表） a1 带头结点的单链表（空表） 11/15/2018

newnode→link = p→link; 在带表头结点的单链表 第一个结点前插入新结点 newnode→link = p→link; if ( p→link == NULL ) last = newnode; p→link = newnode; 11/15/2018

从带表头结点的单链表中删除第一个结点 q = p→link; p→link = q→link; delete q; if ( p→link == NULL ) last = p; 11/15/2018

思考 从任意结点出发都可以到达其它结点？ 11/15/2018

循环链表(Circular List) 把单向链表最后一个节点的链接指针改为指向第一个节点，可以把一个单向链表改造成循环链表。 11/15/2018

循环链表 11/15/2018

循环链表 (Circular List) 循环链表是单链表的变形。 循环链表最后一个结点的 link 指针不 为 0 (NULL)，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。 11/15/2018

循环链表的示例 带表头结点的循环链表 11/15/2018

节点类 template<class T> class ChainNode{ friend Circular<T>; private: T data; ChainNode<T> *link; }; 11/15/2018

单向循环链表的类定义 template<class T> class Circular { public: Circular() {last = 0;} ~Circular(); bool IsEmpty() const {return last == 0;} int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Circular<T>& Delete(int k, T& x); Circular<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: ChainNode<T> *last; // pointer to last node }; 11/15/2018

操作-删除链表 template<class T> Circular<T>::~Circular() {// Circular destructor. Delete all nodes. if (!last) return; // list is empty // delete all nodes ChainNode<T> *current = last->link, *next; while (current != last) { next = current->link; delete current; current = next; } delete last; 11/15/2018

操作-链表的长度 template<class T> int Circular<T>::Length() const { if (!last) return 0; // list is empty // count nodes ChainNode<T> *current = last->link; int len = 0; while (current != last) { len++; current = current->link; } len++; // for last node return len; 11/15/2018

操作-查找第k个元素 template<class T> bool Circular<T>::Find(int k, T& x) const {if (k < 1 || !last) return false; ChainNode<T> *current = last->link; int index = 1; // index of current while (index < k && current != last) { current = current->link; // move to next node index++; } if (index == k) {x = current->data; return true;} return false; // no k'th element 11/15/2018

操作-在链表中搜索 template<class T> int Circular<T>::Search(const T& x) const { if (!last) return 0; // list is empty ChainNode<T> *current = last->link; int index = 1; // index of current while (current->data != x && current != last) { current = current->link; index++; } if (current->data == x) return index; return 0;} 11/15/2018

操作-删除元素 template<class T> Circular<T>& Circular<T>::Delete(int k, T& x) { if (k < 1 || !last) throw OutOfBounds(); // no k'th ChainNode<T> *p = last->link, *q = last; if (k == 1) {// p already at k'th if (p != last) // nonempty list remains last->link = p->link;} // remove else { // move q to k-1'st q = p; for (int index = 1; index < k - 1 && q != last; index++) q = q->link; if (q == last) throw OutOfBounds(); // no k'th 11/15/2018

操作-删除元素 p = q->link; // k'th q->link = p->link;} // remove // save k'th element and free node p x = p->data; if (p == last) // check if new list is empty if (k == 1) // new list is empty last = 0; else // not empty last = q; delete p; return *this; } 11/15/2018

操作-插入元素 template<class T> Circular<T>& Circular<T>::Insert(int k, const T& x) { if (k < 0) throw OutOfBounds(); ChainNode<T> *p = last; if (k) {// advance p to k'th node if (!last) throw OutOfBounds(); // empty list p = p->link; int index = 1; for (; index < k && p != last;index++) if (index != k) throw OutOfBounds(); } // no k'th 11/15/2018

操作-插入元素 ChainNode<T> *y = new ChainNode<T>; y->data = x; if (k) {// insert after p y->link = p->link; p->link = y; if (p == last) last = y;} else // insert as first element if (last) {y->link = last->link; last->link = y;} else {last = y; y->link = y;} return *this; } 11/15/2018

操作-输出 template<class T> void Circular<T>::Output(ostream& out) const { if (!last) return; ChainNode<T> *current; for (current = last->link; current != last; current = current->link) out << current->data << " "; } // overload << template <class T> ostream& operator<<(ostream& out, const Circular<T>& x) {x.Output(out); return out;} 11/15/2018

在带有头节点的循环链表中进行查找 template<class T> int CircularList<T>::Search(const T& x) const {// 在带有头节点的循环链表中寻找x ChainNode<T> *current = first->link; int index = 1; // current的索引 first->data = x; // 把x放入头节点 // 查找x while (current->data != x) { current = current->link; index+ + ; } // 是链表表头吗？ return ((current == first) ? 0 : index); 11/15/2018

插入和删除？ 11/15/2018

用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 11/15/2018

例如 n = 8 m = 3 11/15/2018

多项式及其相加 在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。 优点是： 多项式的项数可以动态地增长，不存在存储溢出问题。 插入、删除方便，不移动元素。 11/15/2018

多项式链表的相加 AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18 11/15/2018

一元多项式 template<class T> class PolyNode { friend CPolynomial<T>; private: T coeff; // coefficient int exp; // exponent PolyNode<T> *link; // pointer to next node }; 11/15/2018

一元多项式 template<class T> class CPolynomial { private: void Append(T c, int e, PolyNode<T> * &last) const; PolyNode<T> *head; // pointer to head node }; 11/15/2018

一元多项式 public: CPolynomial(); ~CPolynomial() {}; void Erase(); int Degree() {if (head->link == head) return 0; return head->link->exp; } CPolynomial<T>& operator=(const CPolynomial<T>& m); CPolynomial<T> operator+(const CPolynomial<T>& m) const; CPolynomial<T> operator-(const CPolynomial<T>& m) const; CPolynomial<T> operator*(const CPolynomial<T>& m) const; CPolynomial<T> operator/(const CPolynomial<T>& m) const; T operator()(const T& x) const; void Input(istream& in); void Output(ostream& out) const; 11/15/2018

一元多项式-构造 template<class T> CPolynomial<T>::CPolynomial() {// Create the zero polynomial. head = new PolyNode<T>; head->exp = -1; head->link = head; } 11/15/2018

一元多项式-删除 template<class T> void CPolynomial<T>::Erase() {// Free all nodes including the head node. PolyNode<T> *current = head->link; while (current != head) { PolyNode<T> *next = current->link; delete current; current = next; } // free the head node delete head; head = 0; 11/15/2018

一元多项式-添加 template<class T> void CPolynomial<T>::Append(T c, int e, PolyNode<T> * &last) const { last->link = new PolyNode<T>; last = last->link; last->coeff = c; last->exp = e; } 11/15/2018

一元多项式-加法运算 template<class T> CPolynomial<T> CPolynomial<T>:: operator+(const CPolynomial<T>& p) const {// Return w = (*this) + p. // define result polynomial w CPolynomial<T> w; // define cursors for w, p, and *this PolyNode<T> *lastw = w.head, // last node of w *cp = p.head->link, // p cursor *ct = head->link; //cursor for *this 11/15/2018

一元多项式-加法运算 while (true) if (ct->exp > cp->exp) { Append(ct->coeff, ct->exp, lastw); ct = ct->link; } else if (ct->exp < cp->exp) { Append(cp->coeff,cp->exp,lastw); cp = cp->link; 11/15/2018

一元多项式-加法运算 else { if (ct->exp == -1) { //Finished? lastw->link = w.head; return w; } // not finished, add coeffecients // and append if sum is nonzero T sum = ct->coeff + cp->coeff; if (sum) Append(sum, ct->exp, lastw); ct = ct->link; cp = cp->link; 11/15/2018

采用尾指针的循环链表 rear->next->next 非空表 rear … 空表 rear 11/15/2018

合并两个循环链表 ④ ② ra rb p ① 存储池 ③ 11/15/2018

双向链表(Doubly Linked List) 双向链表是这样一个有序的节点序列，其中每个节点都有两个指针：left和right。left指针指向左边节点（如果有），right指针指向右边节点（如果有）。 11/15/2018

双向链表 11/15/2018

双向链表 为了能快速找到一个结点的直接前驱，可以在单链表中的结点中增加一个指针域指向它的直接前驱，称这样的链表为双向链表。 … head ^ a1 head rear a2 … an

程序3-21 双向链表的类定义 template <class T> class DoubleNode { friend Double<T>; private: T data; DoubleNode<T> *left, *right; } ; 11/15/2018

程序3-21 双向链表的类定义 class Double { public: Double() {LeftEnd = RightEnd = 0;}; ~Double( ) ; int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Double<T>& Delete(int k, T& x); Double<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: DoubleNode<T> *LeftEnd, *RightEnd; } ; 11/15/2018

双向链表 双向链表:在前驱和后继方向都能游历(遍历) 。 双向链表每个结点结构： 前驱方向   后继方向 前驱方向   后继方向 双向链表通常采用带表头结点的循环链表形式。 11/15/2018

双向循环链表 如果每条链构成一个循环链表，则为双向循环链表。示意如下： a1 head rear a2 … an

双向循环链表的结点插入 p r s 11/15/2018

双向循环链表的插入算法 p→lLink = current; p→rLink =current→rLink; current→rLink→lLink = p; current→rLink = p; 非空表插入 空表插入 11/15/2018

双向循环链表的结点删除 q p r 11/15/2018

节点类 template <class T> class DoubleNode { friend Double<T>; public: T data; DoubleNode<T> *left, *right; }; 11/15/2018

双向链表的类定义 template<class T> class Double { public: Double() {LeftEnd = RightEnd = 0;} ~Double(); bool IsEmpty() const {return LeftEnd == 0;} int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Double<T>& Delete(int k, T& x); Double<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: DoubleNode<T> *LeftEnd, // pointer to leftmost node *RightEnd; // pointer to rightmost node }; 11/15/2018

操作-删除双向链表 template<class T> Double<T>::~Double() {// Double destructor. Delete all nodes. DoubleNode<T> *curr = LeftEnd, // current node *next; // next node while (curr) { next = curr->right; delete curr; curr = next; } 11/15/2018

操作-双向链表的长度 template<class T> int Double<T>::Length() const {// Return the number of elements in the list. // count nodes DoubleNode<T> *curr = LeftEnd; int len = 0; // number to left of curr while (curr) { len++; curr = curr->right; } return len; 11/15/2018

操作-查找第k个元素 template<class T> bool Double<T>::Find(int k, T& x) const { if (k < 1 || !LeftEnd) return false; DoubleNode<T> *curr = LeftEnd; int index = 1; // index of curr while (index < k && curr) { curr = curr->right; index++; } if (index == k) {x = curr->data; return true;} return false; // no k'th element 11/15/2018

操作-在双向链表中搜索 template<class T> int Double<T>::Search(const T& x) const { if (!LeftEnd) return 0; // list is empty DoubleNode<T> *curr = LeftEnd; int index = 1; // index of curr while (curr && curr->data != x) { curr = curr->right; index++; } if (curr) return index; return 0; } 11/15/2018

操作-删除元素 template<class T> Double<T>& Double<T>::Delete(int k, T& x) { if (k < 1 || !LeftEnd) throw OutOfBounds(); DoubleNode<T> *p = LeftEnd; int index = 1; // index of p for (; index < k && p; index++) p = p->right; if (index != k) throw OutOfBounds(); // no k'th if (p == LeftEnd) { // delete first node LeftEnd = LeftEnd->right; if (!LeftEnd) // list is empty RightEnd = 0; else // list is not empty LeftEnd->left = 0; } 11/15/2018

操作-删除元素 else if (p == RightEnd) { // delete last node RightEnd = RightEnd->left; RightEnd->right = 0; } else { // delete an interior node p->right->left = p->left; p->left->right = p->right; // save k'th element and free node p x = p->data; delete p; return *this; 11/15/2018

操作-插入元素 template<class T> Double<T>& Double<T>::Insert(int k, const T& x) { if (k < 0) throw OutOfBounds(); if (k) {// locate k'th node if (!LeftEnd) throw OutOfBounds(); DoubleNode<T> *p = LeftEnd; int index = 1; for (; index < k && p; index++) p = p->right; if (index != k) throw OutOfBounds(); 11/15/2018

操作-插入元素 DoubleNode<T> *y = new DoubleNode<T>; y->data = x; y->right = p->right; p->right = y; y->left = p; if (p == RightEnd)// y is now the last node RightEnd = y; else // y is not the last node y->right->left = y; } 11/15/2018

操作-插入元素 else {// insert as first element DoubleNode<T> *y = new DoubleNode<T>; y->data = x; if (LeftEnd) {// insert into nonempty list y->right = LeftEnd; y->left = 0; LeftEnd->left = y; } else {// insert into an empty list LeftEnd = RightEnd = y; y->left = y->right = 0; } LeftEnd = y; } return *this; } 11/15/2018

操作-输出 template<class T> void Double<T>::Output(ostream& out) const {// Insert the chain elements into the stream out. for (DoubleNode<T> *curr = LeftEnd; curr; curr = curr->right) out << curr->data << " "; } // overload << template <class T> ostream& operator<<(ostream& out, const Double<T>& x) {x.Output(out); return out;} 11/15/2018

11/15/2018

双向循环链表的类定义 template<class T> class DoubleCircular { public: DoubleCircular() {last = 0;} ~DoubleCircular(); bool IsEmpty() const {return last == 0;} int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; DoubleCircular<T>& Delete(int k, T& x); DoubleCircular<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: DoubleNode<T> *last; // pointer to rightmost node }; 11/15/2018

操作-删除双向循环链表 template<class T> DoubleCircular<T>::~DoubleCircular() { if (!last) return; // list is empty DoubleNode<T> *current = last->right,*next; while (current != last) { next = current->right; delete current; current = next; } delete last; 11/15/2018

操作-双向循环链表的长度 template<class T> int DoubleCircular<T>::Length() const { if (!last) return 0; // list is empty DoubleNode<T> *current = last->right; int len = 0; while (current != last) { len++; current = current->right; } len++; // for last node return len; 11/15/2018

操作-查找第k个元素 template<class T> bool DoubleCircular<T>::Find(int k, T& x) const { if (k < 1 || !last) return false; DoubleNode<T> *current = last->right; int index = 1; // index of current while (index < k && current != last) { current = current->right; index++; } if (index == k) {x = current->data; return true;} return false; // no k'th element 11/15/2018

操作-在双向链表中搜索 template<class T> int DoubleCircular<T>::Search(const T& x) const { if (!last) return 0; // list is empty DoubleNode<T> *current = last->right; int index = 1; // index of current while (current->data != x && current != last) { current = current->right; index++; } if (current->data == x) return index; return 0; } 11/15/2018

操作-删除元素 template<class T> DoubleCircular<T>& DoubleCircular<T>::Delete(int k, T& x) { if (k < 1 || !last) throw OutOfBounds(); DoubleNode<T> *p = last->right; int index = 1; // index of p for (; index < k && p != last; index++) p = p->right; if (index != k) throw OutOfBounds(); // no k'th p->right->left = p->left; p->left->right = p->right; 11/15/2018

操作-删除元素 // save k'th element,update last,and free node p x = p->data; if (p == last) // check if new list is empty if (k == 1) // new list is empty last = 0; else // not empty last = last->left; delete p; return *this; } 11/15/2018

操作-插入元素 template<class T> DoubleCircular<T>& DoubleCircular<T>::Insert(int k, const T& x) { if (k < 0) throw OutOfBounds(); if (k) {// locate k'th node if (!last) throw OutOfBounds(); DoubleNode<T> *p = last->right; int index = 1; for (; index < k && p != last; index++ ) p = p->right; if (index != k) throw OutOfBounds(); 11/15/2018

操作-插入元素 // insert after p DoubleNode<T> *y = new DoubleNode<T>; y->data = x; y->right = p->right; y->right->left = y; p->right = y; y->left = p; if (p == last) last = y; } 11/15/2018

操作-插入元素 else {// insert as first element DoubleNode<T> *y = new DoubleNode<T>; y->data = x; if (last) {// insert into nonempty list y->right = last->right; y->right->left = y; last->right = y; y->left = last; } else {// insert into an empty list last = y; y->left = y; y->right = y; } } return *this;} 11/15/2018

操作-输出 template<class T> void DoubleCircular<T>::Output(ostream& out) const { if (!last) return; DoubleNode<T> *current; for (current = last->right; current != last; current = current->right) out << current->data << " "; } template <class T> ostream& operator<<(ostream& out, const DoubleCircular<T>& x) {x.Output(out); return out;} 11/15/2018

与公式化描述方法的比较 空间 效率(插入删除，访问第k个元素) 能折半搜索？ 11/15/2018

小结 单向链表:令x 是一个单向链表。当且仅当x.first=0时x 为空。如果x 不为空，则x.first指向链表的第一个节点。第一个节点指向第二个节点；第二个节点指向第三个节点，如此进行下去。最后一个节点的链指针为0。 单向循环链表:它与单向链表的唯一区别是最后一个节点又反过来指向了第一个节点。当循环链表x为空时，x.first= 0。 11/15/2018

小结 头指针:是在链表中引入的附加节点。利用该节点通常可以使程序设计更简洁，因为这样可以避免把空表作为一种特殊情况来对待。使用头指针时，每个链表（包括空表）都至少包含一个节点（即头指针）。 双向链表:双向链表由从左至右按序排列的节点构成。right 指针用于把节点从左至右链接在一起，最右边节点的right指针为0。lef t指针用于把节点从右至左链接在一起，最左边节点的left指针为0。 11/15/2018

小结 双向循环链表:双向循环链表与双向链表的唯一区别在于，最左边节点的l e f t指针指向最右边的节点，而最右边节点的r i g h t指针指向最左边的节点。 11/15/2018

循环链表和双向链表 循环链表：表尾结点的next指针指向表头结点的链表。 双向链表：结点存在两个指针域，一个指向后继结点，另一个指向前驱结点。 双向循环链表： ^ 11/15/2018

提问 请大家把课本翻到8.1节，Trees。 11/15/2018

3.4 Indirect Addressing 间接寻址是公式化描述和链表描述的组合。 采用这种描述方法，可以保留公式化描述方法的许多优点——可以根据索引在Θ(1)的时间内访问每个元素、可采用二叉搜索方法在对数时间内对一个有序表进行搜索等等。 与此同时，也可以获得链表描述方法的重要特色——在诸如插入和删除操作期间不必对元素进行实际的移动。 因此，大多数间接寻址链表操作的时间复杂性都与元素的大小无关。 11/15/2018

间接寻址 在间接寻址方式中，使用一个指针表来跟踪每个元素。可采用一个公式来定位每个指针的位置，以便找到所需要的元素。元素本身可能存储在动态分配的节点或节点数组之中。 11/15/2018

间接寻址 11/15/2018

间接寻址与链表比较 在链表方式中，指针位于每个节点中，而在间接寻址方式中，指针全放在数组table之中，就像是一本书的目录索引一样。为了找到一本书中的某一项内容，首先需要查目录索引，索引会告诉我们该项内容在哪里。 11/15/2018

程序3-22 间接寻址表的类定义 template<class T> class IndirectList { public: IndirectList(int MaxListSize = 10); ~IndirectList( ) ; bool IsEmpty() const {return length == 0 ;} int Length() const {return length;} bool Find(int k, T& x) const; int Search(const T& x) const; IndirectList<T>& Delete(int k, T& x); IndirectList<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: T **table; // 一维T类型指针数组 int length, MaxSize; } 11/15/2018

程序3-23 间接寻址的构造函数和析构函数 template<class T> IndirectList<T> :: IndirectList(int MaxListSize) {// 构造函数 MaxSize = MaxListSize; table = new T*[MaxSize]; length = 0; } IndirectList<T> ::~IndirectList( ) {// 删除表 for (int i = 0; i < length; i++) delete table[i]; delete [ ]table; 11/15/2018

程序3-24 间接寻址的Find函数 template<class T> bool IndirectList<T>::Find(int k, T& x) const { //取第k个元素至x //如果不存在第k个元素，函数返回false，否则返回true if (k<1||k>length) return false;//不存在第k个元素 x = *table[k-1]; return true; } 复杂性 O(?) 11/15/2018

程序3-25 从间接寻址表中删除元素 template<class T> IndirectList<T>& IndirectList<T>::Delete(int k, T& x) { //把第k个元素传送至x，然后删除第k个元素 / /如果不存在第k个元素，则引发异常OutOfBounds if (Find(k, x)) {//向前移动指针k+l, ... for (int i = k; i < length; i++) table[i-l] = table[i]; length-- ; return *this; } else throw OutOfBounds(); } 复杂性 O(?) 11/15/2018

向间接寻址表中插入元素 11/15/2018

程序3-26 向间接寻址表中插入元素 template<class T> IndirectList<T>& IndirectList<T> ::Insert(int k, const T& x) {//在第k个元素之后插入x //如果不存在第k个元素，则引发异常OutOfBounds //如果没有足够的空间，则传递NoMem异常 if (k < 0 || k > length) throw OutOfBounds(); if (length == MaxSize) throw NoMem(); //向后移动一个位置 for (int i = length-1; i >= k; i--) table[i+l] = table[i]; table[k] = new T; *table[k] = x; length++ ; return *this; } 复杂性 O(?) 11/15/2018

3.5 Simulating Pointers 有时候采用一个节点数组以及对该数组进行索引的模拟指针，可以使设计更方便、更高效。 11/15/2018

模拟指针 11/15/2018

模拟指针 利用数组定义，运算 过程中存储空间大小不变 分配节点： j = avil; avil = A[avil].link; 模拟指针 利用数组定义，运算 过程中存储空间大小不变 分配节点： j = avil; avil = A[avil].link; 释放节点： A[i].link = avil; avil = i; 11/15/2018

程序3-27 模拟指针的类定义 template <class T> class SimNode { friend SimSpace<T>; private: T data; int link; } ; 11/15/2018

程序3-27 模拟指针的类定义 template <class T> class SimSpace { public: SimSpace (int MaxSpaceSize=100); ~SimSpace() {delete [] node;} int Allocate(); //分配一个节点 void Deallocate (int& i) ; //释放节点i private: int NumberOfNodes, first; SimNode<T> *node;//节点数组 } ; 11/15/2018

描述方法比较 11/15/2018

思考 假定一个链表中包含了一个班级内所有学生的信息，每个节点中含有这样的域：学生姓名、考试分数。假定所有的分数均为0 ~ 1 0 0范围内的整数。如果采用第2章中所给出的任一种排序算法对表中的学生按分数进行排序，所需要花费的时间均为O(n2) 有更快的方法吗？ 11/15/2018

方法 一种更快的排序方法为箱子排序（bin sort）。 在箱子排序过程中，节点首先被放入箱子之中，具有相同分数的节点都放在同一个箱子中，然后通过把箱子链接起来就可以创建一个有序的链表。 11/15/2018

11/15/2018

箱子排序引入 一个班级内学生成绩排序？ 11/15/2018

箱子排序 在箱子排序过程中，节点首先被放入箱子之中，具有相同分数的节点都放在同一个箱子中，然后通过把箱子链接起来就可以创建一个有序的链表。 11/15/2018

11/15/2018

箱子的实现 每个箱子都是一个由节点组成的线性表。 箱子中的节点数目介于0到n之间。 把每个箱子都描述成一个链表。 在进行节点分配之前，所有的箱子都是空的。 11/15/2018

需求 1 )从欲排序链表的首部开始，逐个删除每个节点，并把所删除的节点放入适当的箱子中（即相应的链表中）； 2) 收集并链接每个箱子中的节点，产生一个排序的链表。 11/15/2018

程序3-40 一种用于箱子排序的节点类 class Node { friend ostream& operator<<(ostream&, const Node &); public: int operator !=(Node x) const {return (score!= x.score);} private: int score; char *name; } ; ostream& operator<<(ostream& out, const Node& x) {out << x.score << ' '; return out;} 11/15/2018

程序3-43箱子排序 voidBinSort(Chain<Node>& X,int range) {//按分数排序 intlen=X.Length(); Node x; Chain<Node> *bin; bin=new Chain<Node>[range+1]; //分配到每个箱子中 for(inti=1;i<=len;i++){ X.Delete(1,x); bin[x.score].Insert(0,x); } //从箱子中收集各元素 for(intj=range;j>=0;j--) while(!bin[j].IsEmpty()){ bin[j].Delete(1,x); X.Insert(0,x);} delete[]bin;} 11/15/2018

时间复杂性 在两个for循环中执行的每一次插入和删除操作所需要的时间均为Θ(1) 因此第一个for循环的的复杂性为Θ(n)，其中n为输入链表的长度 第二个for循环的复杂性为Θ(n+range) 因此函数BinSort总的复杂性为Θ(n+range)(如果成功的话)。 11/15/2018

程序3-44Binsort作为Chain类的成员 template<class T> Void Chain<T>::BinSort(int range) {//按分数排序 int b;//箱子索引号 ChainNode<T> **bottom,**top; //箱子初始化 bottom=new ChainNode<T>*[range+1]; top=new ChainNode<T>*[range+1]; for(b=0;b<=range;b++) bottom[b]=0; 11/15/2018

程序3-44Binsort作为Chain类的成员 //把节点分配到各箱子中 for(;first;first=first->link){//添加到箱子中 b=first->data; if(bottom[b]){//箱子非空 top[b]->link=first; top[b]=first;} else//箱子为空 bottom[b]=top[b]=first; } 11/15/2018

程序3-44Binsort作为Chain类的成员 //收集各箱子中的元素，产生一个排序链表 ChainNode<T>*y=0; for(b=0;b<=range;b++) if(bottom[b]){//箱子非空 if(y)//不是第一个非空的箱子 y->link=bottom[b]; else//第一个非空的箱子 first=bottom[b]; y=top[b];} if(y)y->link=0; delete[]bottom; delete[]top; } 11/15/2018

时间复杂性 第一和第三个for循环所需要的时间为Θ(range) 第二个for循环所需要的时间为Θ(n) 因此总的时间复杂性为Θ(n+range) 11/15/2018

思考 b=first->data; ? 11/15/2018

从Node类型到数字类型的转换 程序3-42 又一种处理操作符重载的方法 class Node { friend ostream& operator<<(ostream&, const Node &); public: int operator !=(Node x) const {return (score != x.score|| name[0] != x.name[0];} operator int() const {return score;} private: int score; char *name; } ; ostream& operator<<(ostream& out, const Node& x) { out << x.score << ' ' << x.name[0] << ' '; return out;} 11/15/2018

分析 可以注意到BinSort函数并未改变具有同样分数的节点之间的相对次序。 例如，假定在输入链中E、G和H的分数均为3，E出现在G之前，G出现在H之前，那么，在排序后的链表中，E仍出现在G之前，G也仍然出现在H之前。 在有些排序应用中，要求排序算法不得改变同值元素之间的相对次序。 11/15/2018

稳定排序 如果一个排序算法能够保持同值元素之间的相对次序，则该算法被称之为稳定排序(stable sort)。 11/15/2018

思考 如果一个学生有多门课程成绩？ 11/15/2018

函数指针 函数在编译时被分配一个入口地址，称为函数的指针。 T F(T &x)  T (*value)(T &x) 通过指针变量来访问它指向的函数。 函数指针变量常用于参数传递。 11/15/2018

方案 为BinSort增加一个附加的参数value，并使该函数返回排序所使用的值。 其语法如下： Void Chain<T>::BinSort(int range , int(*value)(T &x)) 该语句表明函数Chain<T>::BinSort带有两个参数，而不返回任何值。第一个参数range的类型为int，第二个参数value是一个函数的名字，该函数带有一个类型为T&的参数x并返回一个int值。 11/15/2018

方案 当BinSort按照上述形式定义时，程序3-44中的语句 b=first->data; 需要被改写为：b=value(first->data); 11/15/2018

例子 Inline int F1(Node &x){return x.exam1;} Inline int F3(Node &x){return x.exam1+x.exam2+x.exam3;} Void main(void) { Node x; Chain<Node> L; randomize(); for(inti=1;i<=20;i++){ x.exam1=i/2; x.exam2=20-i; x.exam3=random(100); x.name=i; L.Insert(0,x);} 11/15/2018

例子 L.BinSort(10,F1); cout<<"Sort on exam1"<<endl; cout<<L<<endl; L.BinSort(20,F2); cout<<"Sort on exam2"<<endl; L.BinSort(130,F3); cout<<"Sort on sum of exams"<<endl; } 11/15/2018

箱子排序约束 关键值介于一个“合适的范围内”。 11/15/2018

例子 假定对范围在0~999之间的10个整数进行排序。 如果使用range=1000来调用BinSort，那么箱子的初始化将需要1000个执行步，节点分配需要10个执行步，从箱子中收集节点需要1000个执行步，总的执行步数为2010。 11/15/2018

基数排序 不直接对这些数进行排序，而是采用一些基数r来分解这些数。 在基数排序（radix sort）中，把数按照某种基数分解为数字，然后对数字进行排序。 基数r=箱子个数 11/15/2018

11/15/2018

解释 由于箱子排序是稳定排序，次低位数字相同的节点，其相对次序保持不变（与按最低位数字排序时所得到的次序相同）。 11/15/2018

时间复杂性 由于每个数都至少有三位数字，所以要进行三次排序，每次排序都使用range=10的箱子排序过程来完成。在每次的箱子排序过程中，需要10个执行步来对箱子进行初始化，10个执行步用来把数分配至相应的箱子节点，10个执行步用来收集箱子节点。总的执行步数为90。 比使用range=1000进行10个数的箱子排序要少得多。 11/15/2018

比较 对1000个范围在0~106-1之间的整数进行排序。 使用基数r=106的排序方法（即直接使用BinSort排序函数）需要106执行步对箱子初始化，1000个执行步分配箱子节点，另外106执行步收集箱子节点，因此总的执行步数为2001000。 11/15/2018

比较 对于r=1000的排序。 每次排序都需要3000个执行步，所以排序完成时共需要6000个执行步。 11/15/2018

比较 若使用r=100 则需使用三次箱子排序过程依次对每两位数字进行排序，每次箱子排序需要1200个执行步，总的执行步数为3600。 11/15/2018

比较 如果使用r=10。 则要进行六次箱子排序，每次针对一位数字，总的执行步数为6(10+1000+10)=6120。 11/15/2018

结论 对于一般的基数r，相应的分解式为： x%r;(x%r2)/r;(x%r3)/r2;... 当使用基数r=n对n个介于0~nc-1范围内的整数进行分解时，每个数将可以分解出c个数字。 因此，可以采用c次箱子排序，每次排序时取range=n。整个排序所需要的时间为Θ(cn)= Θ(n)（因为c是一个常量）。 11/15/2018