·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法

Presentation on theme: "·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法"— Presentation transcript:

1 ·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
第二章 线性表 ·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法

2 线性表的定义 空或者只有一个结点。或 1、存在唯一的一个被称之为”第一个“ 的结点。 2、存在唯一的一个被称之为”最后一个“ 的结点。
空或者只有一个结点。或 1、存在唯一的一个被称之为”第一个“ 的结点。 2、存在唯一的一个被称之为”最后一个“ 的结点。 3、除第一个结点之外，每个结点均只有一个前驱结点。 4、除最后一个结点之外，每个结点均只有一个后继结点。 分为以下几大类： ·线性表：通过它们之间的相对位置，确定它们之间的相互关系的线性结构。 e.g: 序列：a1、 a2、 a3…………………an-1、 an ·分类表 ·时间有序表 ·频率有序表 ·序列 结点(数据元素)：由多个数据项构成，每个数据项表示该结点的某种性质。 如：学生登记表中的每个学生结点，由学号、姓名、性别、系别…… 等构成。 存放在外存中的结点通常称之为记录。

3 线性表的ADT ADT 2.1: 线性表List的ADT
Element: { xi | xi ElemSet, i=1,2,3,……n, n > 0}; ElemSet为结点集合。 Relation: {<xi, xi+1>|xi,xi+1ElemSet, i=1,2,3,……n-1}, x1为首结点，xn为尾结点 Operations: Constructor 前提: 无或指定List 的规模。 结果: 分配相应空间及初始化。 Clear 前提: 无。 结果： 删除表List 中的所有结点并进行初始化。 IsEmpty 前提： 无 结果： 表List 为空返回True，否则返回False。 IsFull 结果： 表List 为满返回True，否则返回False。

4 线性表的ADT Length 前提： 无 结果： 返回表List 中的结点个数。 Get 前提： 表List非空且已知结点序号
前提： 无 结果： 返回表List 中的结点个数。 Get 前提： 表List非空且已知结点序号 结果： 返回相应结点的数据值。 Prior 前提： 表List非空，已知结点序号且该结点非首结点。 结果： 返回其直接前驱结点的序号。 Next 前提： 表List非空，已知结点序号且该结点非尾结点 结果： 返回其直接后继结点的序号。 Find 前提： 表List非空，已知结点的数据值。 结果： 查找成功，返回相应结点序号，否则返回查找失败标志 Insert 前提： 已知待插入的数据值以及插入位置。 结果： 插入具有该数据值的结点，表List的结点个数增大1。 Delete 前提： 表List非空，已知被删结点的数据值。 结果： 首先查找相应结点，查找成功则删除该结点，表List的 结点个数将减少1。否则返回删除失败标志。

5 线性表的顺序存储结构 物理存储位置的计算： ·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。
·设第一个结点的存储地址为 LOC(a0), 余类推。设每个结点占用 L 个单元。则： LOC(ai) = LOC(ai-1) + L = LOC(ai-2) + 2L = LOC(ai-i) + i * L = LOC(a0) + i * L a0 a1 ai-1 ai ·随机存取：访问任何一个数据元素或结点花费同样多时间。 an－1

6 线性表的顺序存储结构 template <class ElemType> class SeqList { private:
ElemType * elem; // 顺序表存储数组，存放实际的数据结点。 int length; // 顺序表中的结点个数，亦称表的长度。 int MaxSize; // 顺序表的最大可能的长度。 public: SeqList ( int InitSize ); // 构造函数 ~SeqList ( ); // 析构函数 void Clear( ); // 清空顺序表 bool IsEmpty ( ) const { return ( length = = 0 ); } //表为空返回TRUE,否则返回FALSE。 bool IsFull ( ) const { return (length = =MaxSize) }; // 表是否已经满，满则返回TRUE，否则FALSE。 int Length ( ) const; // 表的长度 ElemType Get ( int i ) const; // 返回第i个结点的值 int Next ( int i ) const; // 若第i个结点的直接后继结点存在，返回其下标， 否则返回 0 int Prior ( int i ) const; // 若第i个结点的直接前驱结点存在，返回其下标，否则返回 0   int Find (ElemType e ) ; // 返回值等于e的结点的序号，无则返回0

7 线性表的顺序存储结构 template <class ElemType> class SeqList { ……
  int Find (ElemType e ) const; // 返回值等于e的结点的序号，无则返回0 int Insert (int i, const ElemType & e ); // 在第i个位置上插入新的结点（值为e），并使原来的第i个结点至最后一个 结点的序号依次加1。插入成功返回1，否则为0 int Delete ( ElemType & e, int i ); // 若第i个结点存在，删除并将其值放入e, // 若i 非法，则删除失败，返回0。 }; 注意：本处惯例，0号单元不用。Length 既是顺序表的当前结点个数，同时又是尾结点的指针。

8 主要函数的实现：顺序表的创建 25 12 47 99 89 36 template <class ElemType>
SeqList<ElemType>::SeqList ( int InitSize ) { // 构造函数 if ( InitSize > 0 ) { elem = new ElemType[ InitSize]; // 申请连续空间，返回空间首地址。 Exception( !elem, ”there is no space in memory”) // 若申请空间失败，则程序中断。 length=0; MaxSize = InitSize-1; } 25 12 47 99 89 36 length

9 主要函数的实现：查找及其分析 25 12 47 99 89 36 template <class ElemType>
int SeqList<ElemType>::Find ( ElemType e ) { // 按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。 // elem[0]做哨兵用,保证即使查找失败，也可以在哨兵位上能找到值e。 elem[0] = e; int i = length; // 初始位置为尾结点所在下标 while (elem[i] != e ) i--; // 不等时继续向前比较，找到返回结点下标，否则返回0。 return i; } 25 12 47 99 89 36 length 成功查找时的平均比较次数：等概率情况, n为表中结点数 ∑ (n-i+1) / n = (n+1)/2 时间复杂性为 O(n)。 1 i=n

10 主要函数的实现：插入及其分析 template <class ElemType> int SeqList<ElemType>::Insert (int i, const ElemType & e) { //在位置 i 上插入一个值为e的结点，原来的第i个结点变为第 // i+1个结点，其余后继结点序号同样加1，插入成功返回1。 Exception( ( i < 1) || ( i > length+1 ), ”i is not correct .”); // 插入位置i不合法 Exception( MaxSize = = length, ”no space for new item.”); // 存储空间已经满了，无法插入。 //从尾结点起到第i个结点逐个向后移动一个位置 for ( int j = length; j >= i; j--) elem[j+1]=elem[j]; elem[i]=e; // 将要插入的结点值放入第i个结点的位置 length++; // 顺序表结点个数加1 return 1; // 插入成功返回1 } 1 2 3 4 5 6 7 8 12 47 89 36 14 99插入 length

11 主要函数的实现：插入及其分析 ·插入（插 如之后成为第 i 个结点，注意从第 1 个结点开始） ： 1 2 3 4 5 6 7 8 12 47 89 36 14 12 47 89 36 14 12 47 89 36 14 12 47 89 36 14 12 47 99 89 36 14 99插入 ·如图 99 插入之后成为第 3 个结点，移动 5－（3－1） 次。 在一般情况下，插入之后成为第i个结点，移动 n-(i-1)= n-i+1 次。

12 主要函数的实现：插入及其分析 ·插入后成为第 3 个结点，移动 5－（3－1） 次。
在一般情况下，插入后成为第 i 个结点，移动 n-i+1) 次 插入后成为第 1 个结点，移动 n 次 插入后成为第 i 个结点，移动 n-i+1 次 插入后成为第 n 个结点，移动 1 次。 插入后成为第 n＋1 个结点，移动 0 次。 总共 n+1 种情况 ·在长度为 n 的线性表中插入一个结点的平均次数为： ∑(n-i+1)/(n+1) = n/2 时间复杂性为 O(n)。 n+1 i =1

13 主要函数的实现：删除及其分析 1 2 3 4 5 6 7 8 12 47 89 36 14 template <class ElemType> int SeqList<ElemType>::Delete( ElemType & e, int i ) { // 若第i个结点存在，删除并将其值放入e, 若i 非法，删除失败。 Exception( ( i < 1) || ( i > length ), ”i is illgeal .”); e = elem[i]; // 将第i个结点值首先读出，用于返回。 for (int j=i; j<length; j++) elem[j]=elem[j+1]; // 第i+1个结点到尾结点逐个前移。 length--; // 表长度减1。 return i; // 返回成功标志 i。 } 删除89 length ·如图结点的数据值为 89 的结点删除将移动 5－3 次。 在一般情况下，删除第i个结点，移动 n-i 次。

14 主要函数的实现：删除及其分析 1 2 3 4 5 6 7 8 12 47 89 36 14 12 47 36 14 12 47 36 14 12 47 36 14 删除

15 主要函数的实现：删除及其分析 ·删除第 3 个结点，移动 5- 3 次。 在一般情况下，删除第 i 个结点，移动 n-i 次
∑(n-i)/n = (n-1)/2 时间复杂性为 O(n)。 n i =1 ·另外，通过数据场之值 x 查找结点，代价 O(n)。 查找第 i 个结点，代价O(1)。

16 线性表的链接存储结构 单链接表：通常用于表示线性结构，如：线性表 · 结点的表示：参照下图所示的情况：
Element: 数据场－通常用于保存结 点的数据元素或数据值 Next: 指针场－给出直接后继结点 的地址 Element Next · 单链接表的表示：参照下图所示的情况： 其中 head 是表首指针。 Element Next head 头结点：不是线性表 之中的结点。但增加 此结点后，操作容易。 head A A B B Z ∧ Z ∧

17 单链接表、双链表和双向循环链表

18 链表的ADT ADT2.2 链表类 AbsList 的定义。
template <class ElemType> class AbsList { public: AbsList ( ) { }; // 构造函数 virtual ~AbsList ( ) { } // 析构函数 virtual IsEmpty ( ) const = 0; // 判表空吗？ virtual IsFull ( ) const = 0; // 判表满吗？ virtual void MakeEmpty( ) = 0; // 将表清空。 firiend class AbsListItr< ElemType >; private: AbsList( const AbsList & ) { } // 冻结复制另一链表的构造函数。 }；

19 链表类迭代器类 ADT2.3 链表迭代器类 AbsListItr 的定义。 template <class ElemType>
class AbsListItr { public: AbsListItr ( const AbsList< ElemType > & L ) { } //构造函数。 AbsListItr ( const AbsListItr & ); // 通过复制构造当前迭代器 virtual ~ AbsListItr ( ) { } // 析构函数 // 以下函数是基本数据操纵类成员函数。 virtual void Insert( const ElemType & x ) = 0; //插入在当前结点(值为x)之后。 virtual int Remove( const ElemType & x ) = 0; //删除值为x的结点。 virtual int Find( const ElemType & x ) = 0; // 查找值为x的结点。 virtual int IsFound( const ElemType & x ) const = 0; //查找值为x的结点成功否。 // 访问当前结点运算符。 virtual int operator+ ( ) const = 0; // 判当前结点存在吗？ virtual const ElemType & operator ( ) ( ) const = 0; // 取当前结点内容。 // 定位运算符及函数。 virtual void Zeroth ( ) = 0; // 定位于链表的首结点之前。 virtual void First ( ) = 0; // 定位于链表的首结点。 virtual void operator ++ ( ) = 0; // 定位于链表的下一个结点。 virtual void operator ++ ( int ) = 0; // 定位于链表的下一个结点。 protected: AbsListItr( ) { } // 冻结无参的构造函数。 }； 请改正书上这行！

20 单链表结点类 · 结点类的定义： Element: 数据场－通常用于保存结点的数据元素或数据值。 Element Next
程序2.5 单链表结点类。 template <class ElemType> class List; // 单链表类的向前说明。 template <class ElemType> class ListItr; // 单链表迭代器类的向前说明。 template <class ElemType> class ListNode{ friend class List <ElemType>; // 单链表类为其友元类, 便于访问结点类中的私有成员。 friend class ListItr <ElemType>; // 单链表迭代器类为其友元类, 便于访问结点类中的私有成员。 private: ListNode<ElemType> * Next; // 指向下一个结点的指针。 ElemType Element; // 结点数据。 public: ListNode ( const ElemType & E, ListNode< ElemType > * N = NULL ) : Element( E ), Next(N) { } // 构造函数 ListNode( ) : Next( NULL ) { } // 构造函数 ~ListNode ( ) { }; // 析构函数 };

21 单链表类 · 单链接表类： Element Next 程序2.6: 单链表类。
template <class ElemType> class ListItr; // 单链表迭代器类的向前说明。 template <class ElemType> class List : public AbsList<ElemType> { friend class ListItr <ElemType>; // 单链表迭代器类为其友元类。 private: ListNode<ElemType> * head; // 指向头结点的指针。 public: List( ) { head = new ListNode< ElemType >( ); } ~ List( ) { MakeEmpty( ); delete head; } // 析构函数 const List & operator = ( const List & R ); // 完成复制功能。 int IsEmpty( ) const { return head->Next = = NULL; } int IsFull( ) const { return 0; } void MakeEmpty( ); };

22 迭代器类 Element Next 迭代器类： 程序2.7: 迭代器类。
template <class ElemType> class ListItr : public AbsListItr<ElemType> { private: ListNode<ElemType> * const head; // 指向头结点的常指针。 ListNode<ElemType> * Current; // 指向当前结点的指针。 public: ListItr( const List<ElemType> & L) : head( L.head ) { Current = L.IsEmpty( ) ? head : head->Next; } ~ ListItr( ) { } // 析构函数 int Find( const ElemType & x ); // 查找值为x的结点，查找成功则使其成为当前结点，并返回True。 int IsFound( const ElemType & x ) const; //查找值为x的结点，查找成功返回 // True，否则返回False;不改变指针Current的值。 void Insert( const ElemType & x ); // 插入成功，新结点成为当前结点。 int Remove( const ElemType & x ); // 删除值为x的结点的操作。

23 迭代器类 Element Next 迭代器类： 程序2.7: 迭代器类（续）。 …………
int operator + ( ) const { return Current && Current != head; } // 当前结点非空则返回True。 const ElemType & operator ( ) ( ) const; // 取当前结点的数据值。 void operator ++ ( ); // 使当前结点的直接后继结点成为当前结点。 void operator ++ ( int ) { operator ++ ( ); } // 定义为前缀++运算符。 void Zeroth ( ) { Current = head; } // 当前指针指向头结点。 void First( ); // 当前指针指向首结点。 const ListItr & operator=( const ListItr & ); // 赋值运算符。 };

24 插入操作 · 插入操作的实现：将新结点插入到当前结点（指针Current指向的结点）之后。 A B Current
Tmp = new ListNode( ); Tmp->Element = x; x Tmp

25 插入操作 ·插入操作的实现：将新结点插入到当前结点（指针Current指向的结点）之后。 2. Current->Next = Tmp
A B Current 1. Tmp->Next = Current->Next x 注意：1、2 不可颠倒，否则链表将脱链。时间代价： O(1) 可用一个语句取代上述操作， 即：Current->Next = new ListNode(x, Current->Next ); Tmp · 指针 p 和指向的对象的关系： Element Next a b c p · 程序语句： p->next ->next->next

26 删除操作 ·删除 Current 所指向的结点之后继结点。要知被删结点的前驱结点的地址 Current a b c p
p = Current ->Next Current

27 删除操作 删除 Current 所指向的结点之后继结点。要知被删结点的前驱结点的地址 Current a b c p Current
Current->Next = p->Next;

28 删除操作 删除 Current 所指向的结点之后继结点。要知被删结点的前驱结点的地址 Current a c Current
delete p; 注意：必须释放 p ->。时间 O(1)。养成良好的程序设计习惯。

29 链接存储 vs. 顺序存储 · 和顺序存储的线性表的操作的比较： 插入： O(1) 插入： O(n) 删除： O(1) 删除： O(n)
· 和顺序存储的线性表的操作的比较： 插入： O(1) 删除： O(1) FINDith: O(i) 平均 O(n) FINDkey : 平均 O(n) 插入： O(n) 删除： O(n) FINDith: O(1) FINDkey : 平均 O(n) 单链表 顺序存储的线性表

30 迭代器中基本操作的实现 · 迭代器中基本操作 Find 和 IsFound的实现
template <class ElemType> int ListItr<ElemType> :: Find( const ElemType & x ) { ListNode<ElemType> * Ptr = head->Next; while ( Ptr != NULL && !( Ptr->Element = = x ) ) Ptr = Ptr->Next; if ( Ptr = = NULL ) return 0; Current = Ptr; return 1; } int ListItr<ElemType> :: IsFound( const ElemType & x ) const { while ( Ptr != NULL && !( Ptr->Element = = x) ) Ptr = Ptr->Next; return Ptr != NULL;

31 迭代器中基本操作的实现 · 在迭代器中，基本操作Insert 和Delete 的实现
template <class ElemType> void ListItr<ElemType> :: Insert( const ElemType & x ) { // 插入操作。 Exception( Current = = NULL, “ The location is illegal!” ); ListNode<ElemType> *p; p = new ListNode<ElemType> ( x, Current->Next); Current = Current->Next = p; // 插入到当前结点之后 } int ListItr<ElemType> :: Remove( const ElemType & x ) { ListNode<ElemType> * Ptr = head; while ( Ptr->Next != NULL && !( Ptr->Next->Element == x) ) Ptr = Ptr->Next; if ( Ptr ->Next = = NULL ) return 0; // 未找到数据值为x的结点，删除失败。 ListNode<ElemType> * P = Ptr->Next; Ptr->Next = Ptr->Next->Next; delete P; Current = head; return 1;

32 迭代器中基本操作的实现 程序2.8: 类List 的赋值运算符 = 的实现。 template <class ElemType>
const List<ElemType> & List<ElemType> :: operator = ( const List<ElemType> & R ) { if ( this = = &R ) return *this; // 同一单链表，不必赋值。 MakeEmpty( ); // 清空单链表。 ListItr<ElemType> Itr( *this ); for ( ListItr<ElemType> Ritr( R ); +Ritr; Ritr++ ) Itr.Insert( Ritr( ) ); // 根据单链表R 的结点数据值，创建新结点，并插入到当前链表。 return *this; }

33 单向循环链表 带头结点的单向循环链表 1、带头结点的单向循环链表 2、带头结点的单向循环链表的初态 不带头结点的单向循环链表
…… head 1、带头结点的单向循环链表 2、带头结点的单向循环链表的初态 head 不带头结点的单向循环链表 …… head 1、不带头结点的单向循环链表 head ＝NULL 2、不带头结点的单向循环链表的初态

34 单向循环链表 不带头结点的单向循环链表（使用尾指针） 1、不带头结点的单向循环链表 2、不带头结点的单向循环链表的初态 tail
…… 1、不带头结点的单向循环链表 tail tail ＝NULL 2、不带头结点的单向循环链表的初态

35 双链表、双向循环链表 B (1). 带头结点和最后一个结点的双链表 Prior Element Next 初始化
A B C head tail 初始化 head tail (2). 双向循环链表的一种实现方案 Prior Element Next A B C D head head = NULL; 初始化

36 双链表的删除 · 删除：给出待删结点的地址就可以把它删除。如；删除数据场之值为 a 的结点，地址由 current 给出。 head c a
b tail Current head c a b tail 执行： Current ->Prior->Next = current ->Next ; 后 Current head c a b tail 执行： Current ->Next->Prior = Current ->Prior; 后 最后执行：delete Current; 将结点删除。 Current

37 双链表的插入 · 插入：注意插入次序。如：将数据场为 x 的结点，插在当前结点之后。 head c a b tail Current p x
·p->prior = Current; Current p x ·p->Next = Current ->Next; head tail c a b Current ·Current ->Next->prior = p; p x ·Current ->Next = p;

38 一元多项式的表示及加法 ·如：多项式： AH = 7+3x+9x8+5x17 BH = 8x+22x7-9x8 Struct Term {
float coef; int exp; Term(int c, int e) { coef=c;exp=e;} ………… } ; coef exp link AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 -9 8 ∧ CH ∧ 7 0 11 1 22 7 5 17

39 一元多项式的加法 ·如：多项式： AH = 7+3x+9x8+5x17
BH = 8x+22x7-9x8 ； 结果保留在 CH 的单链表之中。 AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 -9 8 ∧ coef expn Next CH 7 0 ∧ ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb 后移。 否则将相加后的系数、及相应指数送入单链表 C, pa、pb 后移。 pa->指数小：将系数、及相应指数送入单链表 C, pa 后移。 pa->指数大：将链表 B系数、及相应指数送入单链表 C, pb 后移。 注意： 将任何一个多项式的多余部分，插入在单链表 C 之后。

40 一元多项式的加法 ·如：多项式： AH = 7+3x+9x8+5x17
BH = 8x+22x7-9x8 ； 结果保留在 CH 的单链表之中。 AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 -9 8 ∧ coef expn Next CH 7 0 11 1 ∧ ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb 后移。 否则将相加后的系数、及相应指数送入单链表 C, pa、pb 后移。 pa->指数小：将系数、及相应指数送入单链表 C, pa 后移。 pa->指数大：将链表 B系数、及相应指数送入单链表 C, pb 后移。 注意： 将任何一个多项式的多余部分，插入在单链表 C 之后。

41 一元多项式的加法 ·如：多项式： AH = 7+3x+9x8+5x17
BH = 8x+22x7-9x8 ； 结果保留在 CH 的单链表之中。 AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 -9 8 ∧ coef expn Next CH 7 0 11 1 22 7 ∧ ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb 后移。 否则将相加后的系数、及相应指数送入单链表 C, pa、pb 后移。 pa->指数小：将系数、及相应指数送入单链表 C, pa 后移。 pa->指数大：将链表 B系数、及相应指数送入单链表 C, pb 后移。 注意： 将任何一个多项式的多余部分，插入在单链表 C 之后。

42 一元多项式的加法 ·如：多项式： AH = 7+3x+9x8+5x17
BH = 8x+22x7-9x8 ； 结果保留在 CH 的单链表之中。 AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 - 9 8 ∧ coef expn Next CH 7 0 11 1 22 7 ∧ ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb 后移。 否则将相加后的系数、及相应指数送入单链表 C, pa、pb 后移。 pa->指数小：将系数、及相应指数送入单链表 C, pa 后移。 pa->指数大：将链表 B系数、及相应指数送入单链表 C, pb 后移。 注意： 将任何一个多项式的多余部分，插入在单链表 C 之后。

43 一元多项式的加法 一元多项式的表示及相加； ·如：多项式： AH = 7+3x+9x8+5x17
BH = 8x+22x7-9x8 ； 结果保留在 CH 的单链表之中。 AH ∧ 7 0 3 1 9 8 5 17 BH 8 1 22 7 -9 8 ∧ coef expn Next CH ∧ 7 0 11 1 22 7 5 17 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb 后移。 否则将相加后的系数、及相应指数送入单链表 C, pa、pb 后移。 pa->指数小：将系数、及相应指数送入单链表 C, pa 后移。 pa->指数大：将链表 B系数、及相应指数送入单链表 C, pb 后移。 注意： 将任何一个多项式的多余部分，插入在单链表 C 之后。 ·注意：迭代器是一种“指针”抽象。

44 一元多项式的加法 程序的实现 main( ) { Term R(-1,-1); // 多项式输入的结束标志。
Polynomial<Term > a(R), b(R), c; cin >> a >> b; // 读入 2 个多项式，通过对 >> 重载实现。 c = a; // 多项式 a 并不破坏，将其值送入 c 。 c + b; // 完成多项式c、b相加，结果保存在多项式 c 之中。 cout << c; // 将多项式 c 输出。 return 0; }

45 一元多项式的加法 template <class ElemType>
Polynomial<ElemType> & Polynomial<ElemType> :: operator + (const Polynomial<ElemType> & T ) { ElemType elemA, elemB; Polynomial< ElemType > C; ListItr<ElemType > ItrA(poly); ListItr<ElemType > ItrB(T. poly); ListItr<ElemType > ItrC(C. poly); for ( ; +ItrA && +ItrB; ) { elemA = ItrA( ); elemB = ItrB( ); switch ( compare( elemA, elemB)) { case ‘=’: elemA += elemB; if ( !Is_Empty( elemA ) ) ItrC.Insert(elemA); ++ItrA; ++ItrB; break; case ‘>’ : ItrC.Insert(elemB); ++ItrB; break; case ‘<’ : ItrC.Insert(elemA); ++ItrA; break; } if ( +ItrA ) for ( ; +ItrA; ++ItrA ) { elemA = ItrA( ); ItrC.Insert(elemA); } else for ( ; +ItrB; ++ItrB ) { elemB = ItrB( ); ItrC.Insert(elemB); } *this = C; return *this; ∧ 3 1 9 8 5 17 pa pc ∧ 13 12 5 27 pb p

46 应用：静态链表 · 静态链表的实现： 用于没有动态存储分配功能的语言，如 FORTRAN、COBOL等；当然也可用于C/c++ 等高级语言。缺点：必须预估存区的大小，造成浪费。优点：插、删操作省时。 · e.g: 设集合 A = (c,b,e,g,f,d) 和 B = (a,b,n,f) 。求集合运算 (A－B) ∪ (B－A) 的结 果。 解： A－B = (c,e,g,d); B－A = (a,n)。 (A－B) ∪ (B－A) = (c,e,g,d,a,n)。 程序执行步骤： 1、将用作存储空间的数组的所有单元分配至可利用空间表(也称：空闲栈或备 用链(保存未被使用的结点的单链表)。 2、建立集合 A 的静态链表。 3、逐个输入集合 B 的元素，同时查找 A 的静态链表有无该元素。有则删 除，无则插入该结点。 4、集合 B 的元素输入完毕，则在原集合 A 的静态链表中得到了集合运算 (A－B) ∪ (B－A)的结果。

47 应用：静态链表 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 data cur data cur space[0] 1
2 space[2] 3 space[3] 4 space[4] 5 space[5] 6 space[6] 7 space[7] 8 space[8] 9 space[9] 10 space[10] 11 space[11] -1

48 应用：静态链表 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 · 备用链经初始化之后的情况：注意此处的地址是下标地址。 1 2
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 data cur 9 10 11 · 为了形象起见，和动态分配的单链表表示相似，备用链初 始化之后通常表示成以下形式。 10 11 -1 1 2 3 4 5 6 7 8 data cur 9 10 11 -1 void InitSpace_SL(SLinkList & Space) { for ( i=0; i < MAXSIZE -1; ++i ) space[i].cur = i+1; space[MAXSIZE-1] = -1; } int Malloc_SL(SLinkList &Space) { i = space[0].cur; if ( space[0].cur != -1) space[0].cur = space[i].cur; return i; } int free_SL(SLinkList &Space, int k) { space[k].cur = space[0].cur; space[0].cur = k; }

49 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表的初始化。 1 工作链： s 备用链： 2 3 4 5 6 7 8
备用链： 2 3 4 5 6 7 8 data cur 9 10 11 -1

50 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 c 之后。 1 2 工作链： s c 备用链： r 3
备用链： r 3 4 5 6 7 8 data cur 9 10 11 -1

51 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 b 之后。 1 2 3 工作链： s c b 备用链：
备用链： r 4 5 6 7 8 data cur 9 10 11 -1

52 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 e 之后。 1 2 3 4 工作链： s c b e
备用链： r 5 6 7 8 data cur 9 10 11 -1

53 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 g 之后。 1 2 3 4 5 工作链： s c b
e g 备用链： r 6 7 8 9 10 11 -1 data cur

54 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 f 之后。 1 2 3 4 5 6 工作链： s c
b e g f 备用链： r 7 8 9 10 11 -1 data cur

55 应用：静态链表 2、建立集合 A 的静态链表: · 集合 A 的静态链表：在输入元素 d 之后。 1 2 3 4 5 6 7 工作链： s
c b e g f d 备用链： r 8 9 10 11 -1 data cur

56 应用：静态链表 3、逐个输入集合 B 的元素。 · 输入 a, 查找 A 的静态链表。a 不在，插入。 1 2 3 4 5 6 7 工作链：
s c b e g f d r 8 a 备用链： 9 10 11 -1 data cur

57 应用：静态链表 3、逐个输入集合 B 的元素。 · 输入 b, 查找 A 的静态链表。b 在，在表中删除它。注意：回收单元至备用链。 1 2
4 5 6 7 8 工作链： s c e g f d a r 备用链： 3 9 10 11 b -1 data cur

58 应用：静态链表 3、逐个输入集合 B 的元素。 · 输入 n, 查找 A 的静态链表。n 不在，插入。 1 2 4 5 6 7 8 工作链：
s c e g f d n r 3 a 备用链： 9 10 11 -1 data cur

59 应用：静态链表 3、逐个输入集合 B 的元素。 · 输入 f, 查找 A 的静态链表。f 在，在表中删除它。注意：回收单元至备用链。 1 2
4 5 7 8 工作链： s c e g d a r 3 n 备用链： 6 9 10 11 f -1 data cur

60 应用：静态链表 4、集合 B 的元素输入完毕，则在原集合 A 的静态链表 中得到了集合运算 (A－B) ∪ (B－A)的结果 1 2 4 5
7 8 工作链： s c e g d a r 3 n 备用链： 6 9 10 11 f -1 data cur 时间复杂性：和集合 A、B 的长度之积成正比。

61 应用：稀疏矩阵 2. 链表的应用：稀疏矩阵－只有少数非 0 矩阵元素的情况。 0 1 2 3 4 5 6 ·稀疏矩阵：
2. 链表的应用：稀疏矩阵－只有少数非 0 矩阵元素的情况。 ·稀疏矩阵： 1 2 3 4 5 ·稀疏矩阵的结点结构： F 表示本结点表示非 0 矩阵元素 head row col down value right F - 4 指向本行值为-8的结点 F 表示本结点表示非 0 矩阵元素 指向本列值为-9的结点 F 7 6、7 表示稀疏矩阵共有6行、7列 特殊结点 headnode 指向表头H0 7 表示稀疏矩阵共有 7个非0元素。

62 应用：稀疏矩阵 2. 链表的应用：稀疏矩阵－只有少数非 0 矩阵元素的情况。 0 1 2 3 4 5 6 ·稀疏矩阵：
2. 链表的应用：稀疏矩阵－只有少数非 0 矩阵元素的情况。 ·稀疏矩阵： 1 2 3 4 5 ·稀疏矩阵的行、列表头结点结构：0行，0列表头结点共用一个表头结点，余类推。 Head next down right T next down 列表头：next: 给出下一个列表头结点地址 down:给出本列中第一个非0矩阵元素结点地址 T right 行表头：right:给出本行中第一个非0矩阵元素结点地址

63 应用：稀疏矩阵 2. 链表的应用；稀疏矩阵－只有少数非 0 矩阵元素的情况，稀疏矩阵正交链表表示 1 2 3 4 5 6 H指针数组：
2. 链表的应用；稀疏矩阵－只有少数非 0 矩阵元素的情况，稀疏矩阵正交链表表示 1 2 3 4 5 6 H指针数组： headnode F 7 T T T T T T T T F 11 F 13 T F 12 F 14 T F - 4 F - 8 T T T F - 9