Chapter 3 Data Representation

Chapter 3 Data Representation

山东大学计算机科学与技术学院数据结构第3章数据描述
Contents 3.1 Bird’s-eye view 3.2 linear list 3.3 formula-based representation 3.4 linked representation 3.7 The comparison on the representations 3.8 applications 山东大学计算机科学与技术学院数据结构第3章数据描述

3.1 Introduction A data object is a set of instance or values E.g:
Boolean = {false, true} Digit = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} NatualNumber={0,1,2,…} Letter = {A, B, C, …, Z, a, b, c, …, z} String = {a, b, …, aa, ab, ac,…} Instances may be a primitive (or atomic) or the composed of the instances of another objects. Each instance in NaturalNumber is atomic, 675 is composed of the instances of Digit. An element refers to the individual components of an instance of an object.

data structure A Data Structure is a data object together with the relationships that exist among the instances and elements The relations among integer instances 369 < 370 280+4 = 284 山东大学计算机科学与技术学院数据结构第3章数据描述

3.2 Linear List definition A linear list is of the form (e1,e2,…,en), where n is a finite natural number。 ei is the element of list e1 is the first one，en is the last. n denotes the length of the list. When n = 0 ，list is empty e1 comes before e2, e2 comes before e3, et al E.g： A name list of a class in the increasing order of alphabet. a exam score list in increasing order；山东大学计算机科学与技术学院数据结构第3章数据描述

Abstract Data Type— ADT
ADT : we provide a specification of the instances as well as of the operations that are to be performed . The abstract data type specification is independent of any representation and a C ++ class definition. (定义和语言无关）山东大学计算机科学与技术学院数据结构第3章数据描述

AbstractData Type linearList
abstrctDataType LinearList{ //use natural language to represent Instances ordered finite collections of zero or more elements operations 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之中 } 山东大学计算机科学与技术学院数据结构第3章数据描述

represention 公式化描述（Formula-based）借助数学公式来确定元素表中的每个元素分别存储在何处（如存储器地址）。链接描述（Linked list）元素表中的每个元素可以存储在存储器的不同区域中每个元素都包含一个指向下一个元素的指针。山东大学计算机科学与技术学院数据结构第3章数据描述

3.3 Formula-based representation
Use an array to represent the instance of an object .(数组存储/顺序存储) A meth formula determines the location of each element。 E.g.： location(i) = i–1 ith element (if exist) is located at i-1 th postion of the array。 (5,2,4,8,1) element [0] [1] [2] [3] [4] MaxSize-1 length=5 山东大学计算机科学与技术学院数据结构第3章数据描述

基于公式化的线性表类 LinearList
template <class T> class LinearList { // 程序 3.1 public: LinearList(int MaxListSize = 10); //构造函数 ~LinearList() {delete [] element;} //析构函数 bool IsEmpty() const {return length = = 0;} int Length() const {return length;} 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, const T& x); // 在第k个元素之后插入x void Output(ostream& out) const; Private int length; int MaxSize; T *element; }; 基于公式化的线性表类 LinearList 山东大学计算机科学与技术学院数据结构第3章数据描述

Operation The create and destroy are implemented as the class constructor and destructor respectively. However if no enough memory, the operator new throws an exception of type NoMem. Usually the constructor cannot catch the Nomen, we expect the application code to catch the exception. E.g LinearList<int> y(100); 山东大学计算机科学与技术学院数据结构第3章数据描述

//insufficient memory class Nomen { public; NoMem () {} }; //change new to throw Nomem instead of xalloc void my_new_handler () { Throw Nomem 90; } New_handler Old_handler_ = set_new_handler (my_new_handler); //C++ function 山东大学计算机科学与技术学院数据结构第3章数据描述

构造函数 ‘LinearList’ template<class T> LinearList<T>::LinearList(int MaxListSize) { //基于公式的线性表的构造函数 MaxSize = MaxListSize; element = new T[MaxSize]; length = 0; } 时间复杂性 : Q(1) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Find’ template<class T> bool LinearList<T>::Find(int k, T& x) const { // //把第k个元素取至x中 //如果不存在第k个元素则返回false，否则返回true if (k<1 || k>length) //不存在第k个元素 return false; x=element[k-1]; return true; } 时间复杂性 : Q(1) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘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;// 返回的不是下标，而是rank } 时间复杂性 : O(length) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘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-1] = element[i]; length--; return *this; } else throw OutOfBounds(); 时间复杂性 : O((length-k)s) 山东大学计算机科学与技术学院数据结构第3章数据描述

Insert x at kth position
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+1]=element[i]; element[k]=x; length++; return *this; } 时间复杂性 : O((length-k)s) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Output’ template<class T> void LinearList<T>::Output(ostream& out) const { //把表输送至输出流 for (int i=0; i<length; i++) out<<element[i]<< “ ”; } 时间复杂性 : Q(length). //重载<< template <class T> ostream& operator<<(ostream& out, const Chain<T>& x) {x.Output(out); return out;} 山东大学计算机科学与技术学院数据结构第3章数据描述

类LinearList的应用(程序3-7) #include <iostream.h> #include "llist.h“ // contains program #include "xcept.h“ // has all exceptions void main(void) { try { LinearList<int> L(5); cout << "Length = " << L.Length() << endl; cout << "IsEmpty = " << L.IsEmpty() <<endl; L.Insert(0,2).Insert(1,6); cout << "List is " << L <<endl; cout << "IsEmpty = " << L.IsEmpty() << endl; int z; L.Find(1,z); cout << "First element is " << z << endl; L.Delete(1,z); cout << "Deleted element is " << z << endl; cout << "List is " << L << endl; } catch (...) { cerr << "An exception has occurred" << endl; 山东大学计算机科学与技术学院数据结构第3章数据描述

3.3.4 evaluation 线性表的公式化描述方法优点：各种操作可以用非常简单的C++函数来实现。线性表的公式化描述方法缺点：执行查找、删除和修改的函数都有一个最差的、与表的大小呈线性关系的时间复杂性。空间的低效利用。例：需要维持三个表，在任何时候这三个表所拥有的元素总数都不会超过5000个。然而，很有可能在某个时刻一个表就需要5000个元素，而在另一时刻另一个表也需要5000个元素。若采用类LinearList，这三个表中的每一个表都需要有5000个元素的容量。因此，即使我们在任何时刻都不会使用5000以上的元素，也必须为此保留总共15000个元素的空间。在一个数组中描述几个线性表比每个表用一个数组来描述空间的利用率更高，但在最坏的情况下，插入操作将耗费更多的时间。山东大学计算机科学与技术学院数据结构第3章数据描述

作业： 2（1）（2），7 （1）（2）山东大学计算机科学与技术学院数据结构第3章数据描述

3.4 Linked Representation
Each element of an instance is represent in a cell or node。 Each node keeps the information itself (data filed) and the location information of other relevant nodes (link field). The explicit information about the locations of other nodes is called link (链） or pointer (指针)。山东大学计算机科学与技术学院数据结构第3章数据描述

类 ChainNode 和 Chain singly linked list or chain L = (e1,e2,…,en) is a linear list Each element ei is represented in a node Each node has a filed pointing to next element En has no next node, its link = NULL( or 0 ) e1 e2 e3 en …… first Link Field Data Field 山东大学计算机科学与技术学院数据结构第3章数据描述

Using class ChainNode to represent Chain
template <class T> class ChainNode { friend Chain<T>; private: T data; ChainNode<T> *link; }; 由于Chain<T>是ChainNode<T>的一个友类，所以Chain<T>可以访问ChainNode<T>的所有成员（包括私有成员）。山东大学计算机科学与技术学院数据结构第3章数据描述

类‘Chain’ template <class T> class Chain { public: Chain() { first = 0; } ~Chain(); bool IsEmpty() const { return first == 0; } int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Chain<T>& Delete(int k, T& x); Chain<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: ChainNode<T> *first; }; 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘~Chain’ template <class T> Chain<T>::~Chain() { //链表的析构函数，用于删除链表中的所有节点 ChainNode<T> *next; while (first) { next = first->link; delete first; first = next; } 时间复杂性 : Q(n) e1 e2 e3 en …… first 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Length’ template <class T> int Chain<T>::Length() const { //返回链表中的元素总数 ChainNode<T> *current = first; int len = 0; while (current) { len++; current = current->link; } return len; 时间复杂性 : Q(n) e1 e2 e3 en …… first 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Find’ 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(k) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Search’ 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(n) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Output’ template<class T> void Chain<T>::Output(ostream& out) const {//将链表元素送至输出流 . ChainNode<T> *current; for (current = first; current; current = current->link) out << current->data << " "; } //重载<< template <class T> ostream& operator<<(ostream& out, const Chain<T>& x) {x.Output(out); return out;} 时间复杂性 : Q(n) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Delete’ 删除第k个元素: q→link=p →link 20 10 30 11 first link data 80 q p 山东大学计算机科学与技术学院数据结构第3章数据描述

template<class T> Chain<T>& Chain<T>::Delete(int k, T& x) { //把第k个元素取至x，然后从链表中删除第k个元素； //如果不存在第k个元素，则引发异常OutOfBounds If (k < 1 || !first) throw OutOfBounds( ); //不存在第k个元素 ChainNode<T> *p = first; // p最终将指向第k个节点 if (k = = 1) first = first->link; //删除之 else { //用q指向第k - 1个元素 ChainNode<T> *q = first; for (int index = 1; index<k-1 && q; index++) q=q->link;//移动到第k-1个节点 if (!q || !q->link) //不存在第k个元素 throw OutOfBounds(); p = q->link; //存在第k个元素 q->link = p->link;//从链表中删除该元素 } x = p->data; delete p; //保存第k个元素并释放节点p return *this; 时间复杂性 : O(k) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作 ‘Insert’ Inserting an element behind the kth one： k=0 y 第k 个元素 k>0 p … first y 山东大学计算机科学与技术学院数据结构第3章数据描述

template<class T> Chain<T>& Chain<T>::Insert(int k, const T& x) {//在第k个元素之后插入x,如果不存在第k个元素，则引发异常OutOfBounds if (k < 0) throw OutOfBounds(); ChainNode<T> *p = first; for (int index = 1; index < k && p; index++) p = p->link; //将p移动至第k个元素 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(k) 山东大学计算机科学与技术学院数据结构第3章数据描述

Using the class to create a list
If we want to create an empty integer list, we can use： Chain<int> L; 山东大学计算机科学与技术学院数据结构第3章数据描述

3.4.3 Extension to the class Chain
In some applications we want to extend new functions to the ADT LinearList, we can extend the definition of the class Chain by adding following functions. Erase() delete the nodes in the chain// same as the function of destructor; Zero(): set the first point to zero，but do not delete any node; Append(x): add an element to the end of the list; 山东大学计算机科学与技术学院数据结构第3章数据描述

The extension of Chain template <class T> Void Chain <T>:: Erase() {// Delete all nodes in chain, ChainNode<T> *next; while {first) { next = first->link; delete first; first = next;} } 山东大学计算机科学与技术学院数据结构第3章数据描述

Zero function template <class T> Void Chain <T>:: Zero()
{// set the first to zero, first = 0;} }

Append(x) Append(x):在链表的尾部添加一个元素; … first last 山东大学计算机科学与技术学院数据结构第3章数据描述

Extension to the class Chain
template <class T> class Chain { public: Chain() { first = 0; } ~Chain(); …… Void Erase(); Void Zero() {first =0} Chain <T> & Append(const T& x); private: ChainNode<T> *first; ChainNode<T> *last; }; 山东大学计算机科学与技术学院数据结构第3章数据描述

Extensional Chain --Append
template < class T > Chain <T> & Chain <T> ::Append(const T& x) { //add x at the right end ChainNode<T> *y; y = new ChainNode<T>; y->data = x; y->link = 0; if (first) {//链表非空 last->link = y; last = y;} else //链表为空 first = last = y; return *this; } 时间复杂性 : Q(1) 山东大学计算机科学与技术学院数据结构第3章数据描述

作业对扩展的Chain 类, 相应Chain的delete, insert 函数的程序是否需要修改，若需要的话，请给出修改后的程序代码。

3.4.4 A Chain Iterator Class链表遍历器类
Suppose Output is not a member function of Chain and that << is not overloaded for the class, to output the chain X, we have to execute following code。 int len = X.Length(); for (int i = 1; i <= len; i++) { X . Find ( i , x ) ; cout << x << ' ' ; } Time complexity : Q(n2). However O(n) is enough. Many applications use chains require us to start at the first element and then examine the remainder from left to right. We use iterator that records the current position and advances one position right each time it is invoked. 山东大学计算机科学与技术学院数据结构第3章数据描述

链表遍历器类返回一个指针，该指针指向第一个链表节点中所包含的数据。把location设置为指向链表的第一个节点 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; if (location) return &location->data; private : ChainNode<T> *location; } ; 调整location指向链表中下一个节点；返回指向该节点数据域的指针。跟踪我们在链表中所处的位置山东大学计算机科学与技术学院数据结构第3章数据描述

链表遍历器类 Output X: int *x; ChainIterator<int> c; x = c.Initialize(X); while (x) { cout << *x << ' ' ; x = c.Next( ); } cout << endl; Time Complexity : O(n) ChainIterator should be declared a friend of Chain in order to access the private member first of Chain 山东大学计算机科学与技术学院数据结构第3章数据描述

3.4.5 Circular List 循环链表采取下面的一条或两条措施，使用链表的应用代码可以更简洁、更高效：把线性表描述成一个单向循环链表（singly linked circular list），或简称循环链表（circular list），而不是一个单向链表；在链表的前部增加一个附加的节点，称之为头节点（ head node）。山东大学计算机科学与技术学院数据结构第3章数据描述

Circular List 循环链表带头节点的循环链表空表 Head node 山东大学计算机科学与技术学院数据结构第3章数据描述

3.4.5 Comparison with formula-based
Which one is faster? template<class T> int Chain<T>::Search(const T& x) const { ChainNode<T> *current = first; int index = 1; // current的索引 while (current && current->data != x) { current = current->link; index++; } if (current) return index; return 0; 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 //查找x while (current->data != x) { current = current->link); index++; } //是链表表头吗？ return ((current == first) ? 0 : index); 山东大学计算机科学与技术学院数据结构第3章数据描述

3.4.7 Doubly Linked List 双向链表
Each node has two links, points its left and right nodes respectively, and two points denotes the end-nodes. Left data right 山东大学计算机科学与技术学院数据结构第3章数据描述

class ‘DoubleNode’ template <class T> class DoubleNode { friend Double<T>; private: T data; DoubleNode<T> *left, *right; }; 山东大学计算机科学与技术学院数据结构第3章数据描述

class‘Double’ template <class T> 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; }; 山东大学计算机科学与技术学院数据结构第3章数据描述

双向循环链表 e1 e2 e3 en …… LeftEnd rightend e1 e2 en …… LeftEnd rightend 带表头的双链表作业：把Double类的函数写出其实现。山东大学计算机科学与技术学院数据结构第3章数据描述

3.5 间接寻址间接寻址（indirect addressing）是公式化描述和链表描述的组合。采用一维数组把指针组织起来。保留两种描述方法的优点，即1)公式化描述方法，可以根据索引在Q(1)的时间内访问每个元素。2)链表描述方法：在诸如插入和删除操作期间不必对元素进行实际的移动,对一维数组进行移动，若数据比指针尺寸大很多时，时间快。山东大学计算机科学与技术学院数据结构第3章数据描述

间接寻址描述使用一个指针表来跟踪每个元素。可采用一个公式（如公式location(i) = i-1 ）来定位每个指针的位置，以便找到所需要的元素。元素本身可能存储在动态分配的节点或节点数组之中。山东大学计算机科学与技术学院数据结构第3章数据描述

类 ‘IndirectList’ 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; int length, MaxSize; }; 山东大学计算机科学与技术学院数据结构第3章数据描述

操作--构造函数和析构函数 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; 山东大学计算机科学与技术学院数据结构第3章数据描述

操作---‘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; } 时间复杂性： Q(1) 山东大学计算机科学与技术学院数据结构第3章数据描述

操作---‘Delete’ template<class T> IndirectList<T>& IndirectList<T>::Delete(int k, T& x) {//把第k个元素传送至x，然后删除第k个元素 //如果不存在第k个元素，则引发异常OutOfBounds if (Find(k, x)) { for (int i = k; i < length; i++) table[i-1] = table[i]; //向前移动指针 length--; return *this; } else throw OutOfBounds(); } 时间复杂性：O(length-k). 与表元素的大小无关. 山东大学计算机科学与技术学院数据结构第3章数据描述

操作--- ‘Insert(Insert(int k, const T& x )’
（10,20,30,40,50）（10,20,25,30,40,50）山东大学计算机科学与技术学院数据结构第3章数据描述

操作--- ‘Insert’ template<class T> IndirectList<T>& IndirectList<T>::Insert(int k, const T& x) { if (k < 0 || k > length) throw OutOfBounds(); if (length == MaxSize) throw NoMem(); for (int i = length-1; i >= k; i--) table[i + 1] = table[i]; //向后移动一个位置 table[k] = new T; *table[k] = x; length++; return *this; } 时间复杂性: O(length). 与表元素的大小无关. 山东大学计算机科学与技术学院数据结构第3章数据描述

3.8 applications 3.8.1 箱子排序(Bin Sort) 3.8.2 基数排序(Radix Sort ) 3.8.3 等价类(Equivalence Classes) 3.8.4 凸包(Convex Hull) 山东大学计算机科学与技术学院数据结构第3章数据描述

3.8.1 Bin Sort 箱子排序若学生考试的分数是0 ~ 100范围内的整数，若按分数对学生排序，若有n个学生，采用第2章中所给出的任一种排序算法进行排序，所需要花费的时间均为O(n2). 一种更快的排序方法为箱子排序（bin sort），理论上可以在 O(n)时间完成。基本操作是“放入”，而不是比较。和前面的算法不同，是一种受限的排序算法，即取值整数值。山东大学计算机科学与技术学院数据结构第3章数据描述

Score in 0-5, using the score as the indices of bins
name (b)箱子中的节点 (c)排好序的链表山东大学计算机科学与技术学院数据结构第3章数据描述

sorting When a node is examined, it is placed into the bin that corresponding to its score, Collect the nodes from the bins, beginning with those from bin0 to bin 5,then we get a sorted list in increasing order. Clearly, to implement the bins, each bin is a linear list of nodes with number of nodes varying from 0 to n. 山东大学计算机科学与技术学院数据结构第3章数据描述

The two operations in Bin sort
1)Move down the input chain deleting nodes from this chain and adding them to the chain for the appropriate bin; )Collect the concatenate the chains from the bins into a single sorted chain. 注意：在整个计算过程中，节点data 部分不变，只是修改指针，delete只是从原链上取下，而没有释放。山东大学计算机科学与技术学院数据结构第3章数据描述

Implementation If the input chain is of type Chain, we can do 1) by successively deleting the first element from the chain and inserting it as the first element in the appropriate bin chain; do 2) by deleting the elements from the bins and inserting into the first position of the initial empty chain. The data field of the chain nodes will be of type Node, the operation !=, and << have been overloaded, as these operators are used by the class Chain

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;} 山东大学计算机科学与技术学院数据结构第3章数据描述

箱子排序程序1 (假定BinSort是Node的一个友元）
void BinSort(Chain<Node>& X, int range) // Chain’s element is Node. {// 按分数排序 int len = X.Length(); Node x; Chain<Node> *bin; bin=new Chain<Node> [range+1]; //分配到每个箱子中 for (int i = 1; i <= len; i++) { X.Delete(1,x); bin[x.score].Insert(0,x); } //bin 头指针数组 //从箱子中收集各元素 for (int j = range; j >= 0; j--) while (!bin[j].IsEmpty()) { bin[j].Delete(1,x); X.Insert(0,x); } delete[]bin; // T= Node, 数据有score, name 两个域。时间复杂性：Q(n+range). 山东大学计算机科学与技术学院数据结构第3章数据描述

B E D H G F A J I C X: C X: B->D->G->I->C … X: F->A->E->H->J->B->D->G->I->C 山东大学计算机科学与技术学院数据结构第3章数据描述

箱子排序的另一种实现方法把BinSort定义成Chain类的成员,可以把一串数据直接链接到输出。 template<class T> void Chain<T>::BinSort(int range) {// 按分数排序 int b; // 箱子索引号 ChainNode<T> **bottom, **top; //箱子初始化。每个箱子两个指针,bottom指向头，top指向尾 bottom = new ChainNode<T>* [range + 1]; top = new ChainNode<T>* [range + 1]; for (b = 0; b <= range; b++) bottom[b] = 0; 山东大学计算机科学与技术学院数据结构第3章数据描述

箱子排序程序2—(2/3) //把节点分配到各箱子中 for (; first; first = first->link) {// 添加到箱子中 b = first->data; // score if (bottom[b]) {//箱子非空 top[b]->link = first;// top[b] = first;} else // 箱子为空 bottom [b] = top[b] = first; } //结束时，first =0 Top[b] Bottom[b] 山东大学计算机科学与技术学院数据结构第3章数据描述

箱子排序程序2—(3/3) //收集各箱子中的元素，产生一个排序链表 ChainNode<T> *y = 0; // first is the point of the output list, y points the end of the list 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;//set the link value of last node be 0 delete [] bottom; delete [] top; } y (top[b] first (bottom[b]) 山东大学计算机科学与技术学院数据结构第3章数据描述

Bin 排序程序2 时间复杂性：第一和第三个for循环所需要的时间为Q (range) Range 指数值取值范围，n为节点数目。第二个for循环所需要的时间为Q(n)，总的时间复杂性为Q(n+range)。如果一个排序算法能够保持同值元素之间的相对次序，则该算法被称之为稳定排序（stable sort）。箱子排序是稳定的，因为具有同样score的元素，在新的链表仍保持原列表中的顺序（bottom给出的链表是按原表的顺序）。山东大学计算机科学与技术学院数据结构第3章数据描述

3.8.2 基数排序Radix Sort 对范围在0 ~ nc –1 (c:常量) 之间的n个整数进行排序。使用箱子排序Binsort Range = nc. 时间复杂性: Q(n+range)= Q(n+nc)= Q(nc). 使用基数排序（radix sort） : 基数排序把数按照某种基数r分解为数字，然后对数字进行排序. 十进制数928可以按照基数10分解为数字9，2和8 . 用基数10来分解3725可得到3，7，2和5，. 3725用基数60来进行分解(mod60)则可以得到1，2和5. ((3725)10=(125)60 山东大学计算机科学与技术学院数据结构第3章数据描述

Radix Sort 因为bin Sort是稳定性排序，我们可以对整数分解后的表示法中，从低位（右）到高位（左），在上次排序的基础上，对每一位进行bin 排序。因为bin排序时 stable，最高位的取值决定最终的排序，当最高位经过bin排序后，得到的序列是排序序列。山东大学计算机科学与技术学院数据结构第3章数据描述

基数排序举例输入链表按最后一位数字排序后的链表按倒数第2位数字排序后的链表按最高位数字排序后的链表山东大学计算机科学与技术学院数据结构第3章数据描述

基数排序时间复杂性对范围在0 ~ nc –1 (c:常量) 之间的n个整数进行排序。 r=n range =n 每个数分解的数字的个数=c 时间复杂性 : Q(cn)= Q(n)，若c可认为是常数的话. 山东大学计算机科学与技术学院数据结构第3章数据描述

3.8.3 equivalence relation等价类
Definition and Motivation: U= {1,2,3,4,……n} is a set of n elements R={(i1,j1),( i2,j2 ),……(ir,jr )} is a set of r relations R is called equivalence relation iff (a,a)R for all a, ( reflective 自反）。 (a,b)R iff (b,a)R, （symmetric 对称）。 If ( a,b)R and (b,c)R imply (a,c)R（transitive 传递的）。山东大学计算机科学与技术学院数据结构第3章数据描述

Equivalence relations
If we say R is an equivalence relation, for the purpose of saving space, we may only give the ones giving information, while omit (a,a), symmetrical ones and one can be gained by transitive property. E.g: n= 14; R= { ( 1 , 11 )，( 7 , 11 )，( 2 , 12 )，( 12 , 8 )， ( 11 , 12 )，( 3 , 13 )，( 4 , 13 )，( 13 , 14 )， ( 14 , 9 )，( 5 , 14 )，( 6 , 10 ) } 山东大学计算机科学与技术学院数据结构第3章数据描述

The definition of equivalence class
An equivalence class C is defined as a maximal set, i.e., ：C U, and u,v C, u and v has the relations, but v  U-C, C {v} is not a equivalent class anymore. If R is an equivalence relation, U can be partitioned into U=C1 C2…Ck , and Ci  Cj =, for any i  j. Offline equivalence class, we are given n and R, and are to determine the equivalence classes, each element only belong to one class. 山东大学计算机科学与技术学院数据结构第3章数据描述

Online equivalence class
Begin with n elements, each in a separate equivalence class, we are to process a sequence of operations: (1) Combine(a,b)----combine the equivalence classes that contain a and b into a single one. (2) Find(e)—detemine the class that currently contains e. combine(a,b) is equivalent to i=Find(a); j=Find(b); If (i!=j) Union(i,j); add new relation (a,b) into R by function union If (i!=j) Union(i,j); 在线等价类问题，通常又称之为union-find问题. 山东大学计算机科学与技术学院数据结构第3章数据描述

例:根据最后期限进行调度例 3-5 某工厂有一台机器能够执行n 个任务，任务i的释放时间为ri（是一个整数），最后期限为di（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。任务: 释放时间: 最后期限 : 完成每个任务都需要一个单元的时间 . 山东大学计算机科学与技术学院数据结构第3章数据描述

调度方法 1. 按释放时间的非递增次序对任务进行排序。
1. 按释放时间的非递增次序对任务进行排序。 2. 考察1中所得到的任务序列。对于每个任务，确定与最后期限最接近的空闲时间段（位于最后期限之前）。如果这个空闲时间段位于任务的释放时间之前，则失败，否则把这个时间段分配给任务。例: 任务: 释放时间: 最后期限: 1. 任务: 释放时间: 最后时间 2. 1 3 4 2 3 4 1 2

Online equivalence problem on step 2
Let d denote the latest deadline of any task, the usable time slots are of the form “from i-1 to i”, where 1 id, We shall refer to these usable slots as slots 1 through d.

调度实现 d=所有任务中最后一个的完成期限 . …… 1 2 d-1 d For any slot a: define near(a) as the largest i such that i<=a and slot i is free. 如果不存在这样的 i : near(a)= near(0)=0 当且仅当 near(a)= near(b) 两个时间段a和b属于同一个等价类山东大学计算机科学与技术学院数据结构第3章数据描述

scheduling Let near(a)= a for all slots and each slot is in a separate equivalence class. When slot a is assigned a task in step 2, near changes for all slots b with near(b)=a to near(a-1). Perform a Union on the equivalence classes that currently contains slots a and a-1. Near(a) = N[find(a)], where N[E] is the equivalence class we retain (记住）.

调度实现假设:等价类E={e1,e2,…,ek} 1≤ei≤d N[E]=near(ei ) ei =e1,e2,…,ek ; near(a)=N[find(a)] 当时间段a被分配给某个任务时对于所有near(b)=a的时间段b near(b)=near(a-1) 当时间段a被分配给一个任务时，需要对当前包含时间段a和a-1的等价类进行合并（执行Union操作）。 i=find(a); j=find(a-1) Union(i,j); 山东大学计算机科学与技术学院数据结构第3章数据描述

调度方法例: 任务: 释放时间: 最后期限: 1. 任务: 释放时间: 2. 1 3 4 2 3 4 1 2 n(1)=1 n(2)=2 n(3)=3 n(4)=4 n(3)=2 n(2)=1 n(3)=1 n(4)=1 n(1)=0 n(2)= 0 n(3) =0 n(4)=0 88

在线等价类问题的解决办法第一种解决方案: 使用一个数组E E[e]：包含元素e 的等价类第二种解决方案针对每个等价类设立一个相应的链表山东大学计算机科学与技术学院数据结构第3章数据描述

第一种解决方案 void Initialize(int n) {//初始化n个类，每个类仅有一个元素 E=new int [n+1]; For (int e=1; e<=n; e++) E[e]=e; } void Union(int i, int j) {//合并类i和类j For (int k=1; k<=n; k++) if (E[k]= =j) E[k]=i; int Find(int e) {return E[e]; //搜索包含元素i的类山东大学计算机科学与技术学院数据结构第3章数据描述

第二种解决方案针对每个等价类设立一个相应的链表 node[1:n]用于描述n个元素（每个元素都有一个对应的等价类链表） node[e]：EquivNode类私有数据成员（int）： E：元素e所在的等价类(用等价类链表中的首节点位置表示) Size：元素e所在等价类中的元素数目（等价类链表中的节点数，仅当e是链表的首节点时，才定义node[e].size ） Link：链表指针（模拟指针）， 0表示空指针。山东大学计算机科学与技术学院数据结构第3章数据描述

void Initialize(int n)
node = new EquivNode [n+1]; for (int e = 1; e <= n; e++) { node[e].E = e; node[e].link = 0; node[e].size = 1; }

int Find(int e) { //搜索包含元素i 的类 return node[e].E; }

void Union(int i, int j) { //合并类i 和类j； // 使i 代表较小的类 if (node[i]
void Union(int i, int j) { //合并类i 和类j； // 使i 代表较小的类 if (node[i].size > node[j].size) swap ( i , j ) ; //改变较小类的E值 int k; for (k = i; node[k].link; k = node[k].link) node[k].E = j; node[k].E = j; // 链尾节点 //在链表j的首节点之后插入链表i；并修改新链表的大小 node[j].size += node[i].size; node[k].link = node[j].link; node[j].link = i; }

How to find the partition
Represent the relation in an undirected graph G(V,E), where V is the element of U, (u,v) E, iff (u,v) R. Then find the connected components of G, each connected component is an equivalence class. 山东大学计算机科学与技术学院数据结构第3章数据描述

Convex Hull (凸包） A polygon (多边形） is a closed planar figure with three or more straight edges. A polygon is convex iff all lines segment that join two points on or in the polygon include no point that is outside the polygon. The convex hull of a set of points in the plane is the smallest convex polygon that contains all these points. 山东大学计算机科学与技术学院数据结构第3章数据描述

3.8.4 凸包凸多边形非凸多边形山东大学计算机科学与技术学院数据结构第3章数据描述

3.8.4 凸包 1 2 3 4 5 6 7 8 9 12 10 13 11 • • x 山东大学计算机科学与技术学院数据结构第3章数据描述

exercises P124, 1 P : 22,23,24,24,27,31

Chapter 3 Data Representation

Similar presentations

Presentation on theme: "Chapter 3 Data Representation"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Chapter 3 Data Representation

Similar presentations

Presentation on theme: "Chapter 3 Data Representation"— Presentation transcript:

Similar presentations

About project

反馈