数据结构 第2章 线性表 吴忠华.

Presentation on theme: "数据结构 第2章 线性表 吴忠华."— Presentation transcript:

1 数据结构 第2章 线性表 吴忠华

2 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
数据结构

3 线性结构 线性结构是一个数据元素的有序（次序）集合。它有四个基本特征： 线性表是一种最简单的线性结构
存在唯一的一个被称作“第一个”的数据元素； 存在唯一的一个被称作“最后一个”的数据元素； 除第一个之外，集合中的每个元素均只有一个前驱； 除最后一个之外，集合中的每个元素均只有一个后继。 线性表是一种最简单的线性结构 前 后 尾 首 数据结构

4 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
数据结构

5 2.1 线性表的类型定义 2.1.1 抽象数据类型线性表的定义 2.1.2 线性表类型的应用 数据结构

6 2.1.1 抽象数据类型线性表的定义 通常可以用下列“n个数据元素的序列”表示线性表 (Linear List)
(a1, a2,..., ai,...,an ) 序列中数据元素的个数 n 定义为线性表的表长；n=0 时的线性表被称为空表。 称i为ai在线性表中的位序。 数据结构

7 2.1.1 抽象数据类型线性表的定义 ADT List {
数据对象：D＝{ ai| ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1 ,ai >| ai-1 ,ai ∈D, i=2,...,n } 基本操作： 　{结构初始化} 　InitList( &L ) 　　操作结果：构造一个空的线性表 L 。 　{销毁结构} 　DestroyList( &L ) 　　初始条件：线性表 L 已存在。 　　操作结果：销毁线性表 L 。 数据结构

8 2.1.1 抽象数据类型线性表的定义 {引用型操作} ListEmpty( L ) 初始条件：线性表L已存在。
　　　操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。 　　ListLength( L ) 　　　初始条件：线性表 L 已存在。 　　　操作结果：返回 L 中元素个数。 　　PriorElem( L, cur_e, &pre_e ) 　　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱， 　　　　　　　　否则操作失败，pre_e 无定义。 　　NextElem( L, cur_e, &next_e ) 　　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继， 　　　　　　　　否则操作失败，next_e 无定义。 数据结构

9 2.1.1 抽象数据类型线性表的定义 GetElem( L, i, &e )
　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 　　　操作结果：用 e 返回 L 中第 i 个元素的值。 　　LocateElem( L, e, compare( ) ) 　　　初始条件：线性表 L 已存在，compare( ) 是元素判定函数。 　　　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。 　　　　　　　　若这样的元素不存在，则返回值为0。 　　ListTraverse(L, visit( )) 　　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。 　 　操作结果：依次对 L 的每个元素调用函数 visit( )。 　　 　　　　　一旦 visit( ) 失败，则操作失败。 数据结构

10 2.1.1 抽象数据类型线性表的定义 {加工型操作} ClearList( &L ) 初始条件：线性表 L 已存在。
　　PutElem( &L, i, &e ) 　　　初始条件：线性表L已存在，1≤i≤LengthList(L)。 　　　操作结果：L 中第 i 个元素赋值同 e 的值。 ListInsert( &L, i, e ) 　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 　　　操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。 　　ListDelete( &L, i, &e ) 　　　初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。 　　　操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。 } ADT List 数据结构

11 2.1.1 抽象数据类型线性表的定义 List ADT( Shaffer书上的描述)
template <class Elem> class List { public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool append(const Elem&) = 0; virtual bool remove(Elem&) = 0; virtual void setStart() = 0; virtual void setEnd() = 0; 数据结构

12 2.1.1 抽象数据类型线性表的定义 virtual void prev() = 0; virtual void next() = 0;
virtual int leftLength() const = 0; virtual int rightLength() const = 0; virtual bool setPos(int pos) = 0; virtual bool getValue(Elem&) const=0; virtual void print() const = 0; }; 数据结构

13 2.1.2 线性表类型的应用 如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以利用类型中定义的各种操作。下面将举三个例子说明之。 例2-1 已知集合 A 和 B，求两个集合的并集，使 A＝A∪B，且 B 不再单独存在。 例2-2 已知一个"非纯集合" B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元素。 例2-3 判别两个集合是否相等。 数据结构

14 2.1.2 线性表类型的应用 例2-1 已知集合 A 和 B，求两个集合的并集，使 A＝A∪B，且 B 不再单独存在。
用线性表表示集合，要求对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。 　　具体操作步骤为： 　　1．从线性表 LB 中取出一个数据元素； 　　2．依值在线性表 LA 中进行查询； 　　3．若不存在，则将它插入到 LA 中。 　　重复上述三步直至 LB 为空表止。 数据结构

15 2.1.2 线性表类型的应用 算法2.1 void union(List &LA, List &LB){
// 将所有在线性表LB中但不在LA中的数据元素插入到 LA 中, // 算法执行之后，线性表 LB 不再存在。 La_len = ListLength(LA);　// 求得线性表 LA 的长度 while (!ListEmpty(LB)){ // 依次处理 LB 中元素直至 LB 为空表止 ListDelete(LB,1,e);　　// 从 LB 中删除第1个数据元素并赋给 e // 当LA中不存在和 e 值相同的数据元素时进行插入 if (!LocateElem(LA, e, equal( )) ListInsert(LA, ++La_len, e); } // while　　 DestroyList(LB);　　　　　// 销毁线性表 LB　 } // union 数据结构

16 2.1.2 线性表类型的应用 例2-2 已知一个“非纯集合” B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元素。
容易看出，应对线性表作和上例相同的操作，具体的三步也都相同，所不同之处仅仅在于两点： 一是例2-1的算法中 LA 是已知的，而在此例算法中的 LA 是待新建的； 二是例2-1在求得并集之后，原来的两个集合不再保留，而在此例中构建新的集合 A 的同时，原来的集合 B 不变。 数据结构

17 2.1.2 线性表类型的应用 算法2.2 void purge(List &LA, List LB) {
// 构造线性表LA，使其只包含LB中所有值不相同的数据 // 元素,算法不改变线性表LB　 InitList(LA); 　　　　　　　　// 创建一个空的线性表 LA La_len = 0; Lb_len = ListLength(LB);　 　 // 求线性表 LB 的长度 for (i = 1; i <= Lb_len; i++){　 // 依次处理 LB 中每个元素 GetElem(LB, i, e); 　　　　　// 取 LB 中第 i 个数据元素赋给 e 　// 当 LA 中不存在和 e 值相同的数据元素时进行插入 if (!LocateElem( LA, e, equal( ) ) ListInsert( LA, ++La_len, e ); } // for } // purge 数据结构

18 2.1.2 线性表类型的应用 例2-3 判别两个集合是否相等。
两个集合相等的充分必要条件是它们具有相同的元素。当以线性表表示集合时，两个线性表的长度应该相等，且表中所有数据元素都能一一对应，但相同的数据元素在各自的线性表中的“位序”不一定相同。 由此，"判别两个线性表中的数据元素是否完全相同"的算法的基本思想为：首先判别两者的表长是否相等；在表长相等的前提下，如果对于一个表中的所有元素，都能在另一个表中找到和它相等的元素的话，便可得到"两个线性表表示的集合相等"的结论；反之，只要有一个元素在另一个表中不能找到相等元素时，便可得出"不等"的结论。 数据结构

19 2.1.2 线性表类型的应用 bool isEqual(List LA, List LB){ //算法2.3
// 若线性表 LA 和 LB 不仅长度相等，且所含数据元素也相同， // 则返回 TRUE，否则返回 FALSE。 La_len = Listlength(LA); Lb_len = Listlength(LB); if ( La_len != Lb_len ) return FALSE; // 两表的长度不等 else { i = 1; found = TRUE; while ( i<= La_len && found ){ GetElem( LA, i, e );　　　　　// 取得 LA 中一个元素 if ( LocateElem(LB, e, equal( ) ) i++; // 依次处理下一个 else found = FALSE;　 // LB中没有和该元素相同的元素 } // while return found; } // else } // isEqual 数据结构

20 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
数据结构

21 2.2 线性表的顺序表示和实现 2.2.1 顺序表 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其它算法举例 数据结构

22 2.2.1 顺序表 顺序表是线性表的顺序存储表示的简称，它指的是，"用一组地址连续的存储单元依次存放线性表中的数据元素"，即以"存储位置相邻"表示"位序相继的两个数据元素之间的前驱和后继的关系(有序对<ai-1，ai>)"，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。 不失一般性，假设每个数据元素占据的存储量是一个常量 C，则后继元素的存储地址和其前驱元素相隔一个常量， 即：LOC(ai) = LOC(ai-1) + C (一个数据元素所占存储量) 由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到 LOC(ai) = LOC(a1) + (i-1)×C a1 a2 … ai-1 ai an 线性表的起始地址，称作线性表的基地址 数据结构

23 2.2.1 顺序表 用C语言描述的顺序表类型如下所示： // 存储结构
　　const int MAXLISTSIZE=80; // 预设的存储空间最大容量 　　typedef struct { 　　ElemType *elem;　　// 存储空间基址 　　int length; 　　　　// 当前长度 　　int listsize;　　　 // 允许的最大存储容量(以sizeof(ElemType)为单位) 　　} SqList;　　　　　　 // 俗称 顺序表 // 基本操作接口(函数声明) 　void InitList ( SqList &L, int maxsize ); //　构造一个最大存储容量为 maxsize 的空的顺序表 L。 　void DestroyList ( SqList &L ) //　销毁顺序表 L。 　bool ListEmpty ( SqList L ) //　若顺序表 L 为空表，则返回TRUE，否则返回 FALSE。 数据结构

24 2.2.1 顺序表 int ListLength ( SqList L ) // 返回顺序表 L 中元素个数。
　int PriorElem ( SqList L, ElemType cur_e ) //　若 cur_e 是顺序表 L 的元素，则返回其前驱的位序 //　(设第一个元素的前驱的位序为0)，否则返回 -1。 　int NextElem ( SqList L, ElemType cur_e ) //　若 cur_e 是顺序表 L 的元素，则返回其后继的位序 // (设最后一个元素的后继的位序为L的表长+1)，否则返回 -1。 　bool GetElem ( SqList L, int pos, ElemType &e ) //　若1≤pos≤LengthList(L)，则用 e 带回顺序表 L 中第 pos 个元素 //　的值且返回函数值为TRUE，否则返回函数值为FALSE。 　int LocateElem ( SqList L, ElemType e, bool (*compare)(ElemType, ElemType ) ) //　返回顺序表L中第1个与 e 满足关系 compare( ) 的数据元素的位序。 //　若这样的元素不存在，则返回值为0。compare( )为数据元素的判定函数。 数据结构

25 2.2.1 顺序表 void ListTraverse ( SqList L, void (*visit)(ElemType ))
//　依次对顺序表 L 的每个元素调用函数 visit( )。 //　一旦 visit( ) 失败，则操作失败。 　void ClearList( SqList &L ) //　将顺序表 L 重置为空表。 　bool PutElem ( SqList L, int pos, ElemType &e ) //　若1≤pos≤LengthList(L)，则对顺序表 L 中第 pos 个元素 //　赋值同 e 的值且返回函数值为 TRUE，否则返回函数值为 FALSE。 　bool ListInsert ( SqList &L, int pos, ElemType e ) //　若存储空间未满且1≤pos≤LengthList(L)+1，则在顺序表 L 的 //　第 pos 个元素之前插入新的元素 e，L的长度增1，且返回函数值为TRUE， //　否则不改变顺序表且返回函数值为 FALSE。 　bool ListDelete ( SqList &L, int pos, ElemType &e) //　若1≤pos≤LengthList(L)，则删除顺序表 L 的第 pos 个元素 e， //　L的长度增1，且返回函数值为TRUE，否则不改变顺序表且返回函数值为FALSE。 数据结构

26 2.2.1 顺序表 以上定义的函数可在程序设计中引用，例如，上述算法2.2可改写为下列可在主函数中调用的函数。
void purge(SqList &La, SqList Lb) { // 构造顺序表 La，使其只包含 Lb 中所有值不相同的数据元素, 　// 算法不改变顺序表 Lb 　bool b; 　int Lb_len = Listlength( Lb );　　　 // 求线性表 Lb 的长度 　InitList( La,L b_len ); 　　　　　　　// 创建一个空的线性表 La 　int La_len = 0;　　　　　　　　　　　 　for ( i = 1; i <= Lb_len; i++ ){ 　　 // 依次处理 Lb 中每个元素 　　b = GetElem( Lb, i, e );　　　　　　// 取Lb中第 i 个数据元素赋给 e 　　if ( !LocateElem( La, e, equal( ) ) ){ 　　　++La_len; 　　　b = ListInsert( La,La_len,e );　　// 当 La 中不存在和 e 值相同的 　　} 　　　　　　　　　　　　　　　　　// 数据元素时，进行插入 　} // for } // purge 数据结构

27 2.2.2 顺序表中基本操作的实现 从顺序表的存储结构定义容易看出，由于顺序表的"长度"是个"显值"，且由于第i个元素恰好存储在数组的第 i 个分量(数组下标为 i-1)中，因此其"求长"、"判空"以及"存取第 i 个数据元素"等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。 　　一、初始化操作 　　二、元素定位操作 　　三、插入元素操作 　　四、删除元素操作 　　五、销毁结构操作 数据结构

28 2.2.2 顺序表中基本操作的实现 一、初始化操作 算法2.4
　　void InitList(SqList &L, int maxsize) { 　　　// 构造一个空的线性表 L 　　　if ( maxsize == 0 ) 　　　　　 maxsize = MAXLISTSIZE; 　　　L.elem = (ElemType *)malloc( sizeof( ElemType)*maxsize); 　　　if (!L.elem) 　exit(1);　　 // 存储分配失败 　　　L.length = 0;　　　　　　 　// 顺序表的初始长度为0 　　　L.listsize = maxsize;　　// 该顺序表可以存储元素的最大容量 　　} // InitList 此算法的时间复杂度为 O (1)。 数据结构

29 2.2.2 顺序表中基本操作的实现 二、元素定位操作 算法 2.5 int LocateElem(SqList L, ElemType e,
二、元素定位操作 算法 2.5 　int LocateElem(SqList L, ElemType e, 　　　　　　　　　　void (*compare)(ElemType, ElemType)) { 　　// 在顺序表L中查找第1个值与 e 满足判定条件compare( )的元素， 　　// 若找到，则返回其在 L 中的位序，否则返回0。 　　i = 1;　　　　　　　　　// i 的初值为第1元素的位序 　　p = L.elem; 　　　　　　// p 的初值为第1元素的存储位置 　　while (i <= L.length && !(*compare)(*p++,e)) 　　　++i;　 　　　　　　　// 依次进行判定 　　if (i <= L.length) return i; 　　　　　　　　　　　// 找到满足判定条件的数据元素为第 i 个元素 　　else return 0;　　　　// 该线性表中不存在满足判定的数据元素 　} // LocateElem 　　此算法的时间复杂度为： O ( ListLength(L)) 数据结构

30 2.2.2 顺序表中基本操作的实现 三、插入元素操作 数据结构

31 2.2.2 顺序表中基本操作的实现 三、插入元素操作 算法 2.6
三、插入元素操作 算法 2.6 　bool ListInsert(SqList &L, int pos, ElemType e) { 　　// 若存储空间不满且1≤pos≤Listlength(L)+1，则在顺序表 L 的 　　// 第 pos 个元素之前插入新的元素 e 且返回TRUE，否则返回FALSE 　　if (pos < 1 || pos > L.length+1) return FALSE ; // 插入位置不合法 　　if (L.length >= L.listsize) return FALSE; 　　　　　　　　　　　　　　　　// 当前存储空间已满，无法插入 　　for (j=L.length-1; j>=pos-1; --j) 　　　L.elem[j+1] = L.elem[j]; // 插入位置及之后的元素右移 　　L.elem[pos-1] = e; 　　　　 // 插入 e 　　++L.length; 　　　　　　　 // 表长增1 　　return TRUE; 　} // ListInsert 　　此算法的时间复杂度为： O (ListLength(L)) 数据结构

32 2.2.2 顺序表中基本操作的实现 四、删除元素操作 算法 2.7
bool ListDelete(SqList &L, int pos, ElemType &e){ 　　// 若1≤pos≤Listlength(L)，则 e 带回顺序表 L 中删除的 　　// 第 pos 个元素且返回 TRUE，否则返回 FALSE 　　if ((pos < 1) || (pos > L.length)) 　　return FALSE ; 　　　　　　　　// 删除位置不合法 　　for (j = pos; j<L.length; ++j) 　　　L.elem[j-1] = L.elem[j]; 　 // 被删除元素之后的元素左移 　　--L.length; 　　　　　　　　　　 // 表长减1 　　return TRUE; 　} // ListDelete 此算法的时间复杂度为： O (ListLength(L)) 数据结构

33 2.2.2 顺序表中基本操作的实现 五、销毁结构操作 算法 2.8 void DestroyList( SqList &L ) {
　{ 　　// 释放顺序表 L 所占存储空间 　free( L.elem); 　　L.listsize = 0; 　　L.length = 0; 　} // DestroyList_Sq 　　此算法的时间复杂度为： O (1) 数据结构

34 2.2.2 顺序表中基本操作的实现 六、插入和删除操作的性能分析
在顺序存储表示的线性表中插入或删除一个数据元素，平均约需移动表中一半元素。这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺序存储要求线性表的元素依次紧挨存放造成的。 因此，这种顺序存储表示仅适用于不常进行插入和删除操作、表中元素相对稳定的线性表。 数据结构

35 2.2.2 顺序表中基本操作的实现 Shaffer书中的实现： 位置从0开始，与C++中数组用法一致 引入fence概念，定义当前位置
数据结构

36 2.2.2 顺序表中基本操作的实现 template <class Elem> // Array-based list
Shaffer template <class Elem> // Array-based list class AList : public List<Elem> { private: int maxSize; // Maximum size of list int listSize; // Actual elem count int fence; // Position of fence Elem* listArray; // Array holding list public: AList(int size=DefaultListSize) { maxSize = size; listSize = fence = 0; listArray = new Elem[maxSize]; } 数据结构

37 2.2.2 顺序表中基本操作的实现 ~AList() { delete [] listArray; } void clear() {
Shaffer ~AList() { delete [] listArray; } void clear() { delete [] listArray; listSize = fence = 0; listArray = new Elem[maxSize]; } void setStart() { fence = 0; } void setEnd() { fence = listSize; } void prev() { if (fence != 0) fence--; } void next() { if (fence <= listSize) fence++; } int leftLength() const { return fence; } int rightLength() const { return listSize - fence; } 数据结构

38 2.2.2 顺序表中基本操作的实现 bool setPos(int pos) {
Shaffer bool setPos(int pos) { if ((pos >= 0) && (pos <= listSize)) fence = pos; return (pos >= 0) && (pos <= listSize); } bool getValue(Elem& it) const { if (rightLength() == 0) return false; else { it = listArray[fence]; return true; 数据结构

39 2.2.2 顺序表中基本操作的实现 // Insert at front of right partition
Shaffer // Insert at front of right partition template <class Elem> bool AList<Elem>::insert(const Elem& item) { if (listSize == maxSize) return false; for(int i=listSize; i>fence; i--) // Shift Elems up to make room listArray[i] = listArray[i-1]; listArray[fence] = item; listSize++; // Increment list size return true; } 数据结构

40 2.2.2 顺序表中基本操作的实现 // Append Elem to end of the list
Shaffer // Append Elem to end of the list template <class Elem> bool AList<Elem>::append(const Elem& item) { if (listSize == maxSize) return false; listArray[listSize++] = item; return true; } 数据结构

41 2.2.2 顺序表中基本操作的实现 // Remove and return first Elem in right
Shaffer // Remove and return first Elem in right // partition template <class Elem> bool AList<Elem>::remove(Elem& it) { if (rightLength() == 0) return false; it = listArray[fence]; // Copy Elem for(int i=fence; i<listSize-1; i++) // Shift them down listArray[i] = listArray[i+1]; listSize--; // Decrement size return true; } 数据结构

42 O (Min(A.length, B.length))。
2.2.3 顺序表其它算法举例 例2-4 试编写算法“比较”两个顺序表的大小。 算法 2.9 　int compare( SqList A, SqList B )　{ 　　// 若 A<B，则返回 -1；若 A=B，则返回 0；若 A>B，则返回 1 　　j=0; 　　while ( j<A.length && j<B.length ) 　　　if ( A.elem[j] < B.elem[j] ) return(-1); 　　　else if ( A.elem[j] > B.elem[j] ) return(1); 　　　else j++; 　　if ( A.length == B.length ) return (0); 　　else if ( A.length < B.length ) return(-1); 　　else return(1); 　} // compare 上述算法中只有一个 while 循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法2.9 的时间复杂度为 O (Min(A.length, B.length))。 数据结构

43 2.2.3 顺序表其它算法举例 例2-5　试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表(a1,a2,…,am,b1,b2,…,bn) 改变成( b1,b2,…,bn,a1,a2,…,am)。 算法2.10 　　void invert( ElemType &R[], int s, int t )　{ 　　// 本算法将数组 R 中下标自 s 到 t 的元素逆置，即将 　　// （Rs,Rs+1,…,Rt-1,Rt）改变为（Rt,Rt-1,…,Rs+1,Rs） 　　for ( k=s; k<=(s+t)/2; k++ ){ 　　　w = R[k]; 　　　R[k] = R[t-k+s]; 　　　R[t-k+s] = w; 　　} // for 　} // invert 数据结构

44 2.2.3 顺序表其它算法举例 算法2.11 void exchange ( SqList &A,int m ) {
　　// 本算法实现顺序表中前 m 个元素和后 n 个元素的互换 　　if ( m > 0 && m < A.length ){ 　　　n = A.length - m; 　　　invert( A.elem, 0, m+n-1 ); 　　　invert( A.elem, 0, n-1 ); 　　　invert( A.elem, n, m+n-1 ); 　　} 　} // exchange 数据结构

45 2.2.3 顺序表其它算法举例 例2-6 编写算法删除顺序表中"多余"的数据元素，即使操作之后的顺序表中所有元素的值都不相同。
例2-6　编写算法删除顺序表中"多余"的数据元素，即使操作之后的顺序表中所有元素的值都不相同。 　　void purge_Sq( SqList &L )　{ //算法2.12 　　// 删除顺序表L中的冗余元素，即使操作之后的顺序表中只保留 　　// 操作之前表中所有值都不相同的元素 　　k = -1; 　　　　　　　　　　　　// k 指示新表的表尾 　　for (i=0; i<L.length; ++i){　　 // 顺序考察表中每个元素 　　　j=0; 　　　while(j<=k && L.elem[j]!=L.elem[i]) 　　　　++j;　　　　　　　// 在新表中查询是否存在和L.elem[i]相同的元素 　　　if ( k==-1 || j>k )　// k=-1 表明当前考察的是第一个元素 　　　　L.elem[++k] = L.elem[i]; 　　} // for 　　L.length = k+1;　　　　　　　　// 修改表长 　} // purge_Sq 　　此算法的时间复杂度为 O (ListLength2(L)) 数据结构

46 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
数据结构

47 2.3 线性表的链式表示和实现 2.3.1 单链表和指针 2.3.2 单链表中基本操作的实现 2.3.3 单链表其它算法举例
2.3.4 循环链表 2.3.5 双向链表 数据结构

48 2.3.1 单链表和指针 链式存储表示指的是以"附加信息(指针)" 表示数据元素之间的逻辑关系。
除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"，表示线性表中一个数据元素 其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。 数据结构

49 2.3.1 单链表和指针 为了便于处理一些特殊情况，在第一个结点之前附加一个"头结点"，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示。 a1 a2 an ^ … 头指针 头结点 空指针 数据结构

50 2.3.1 单链表和指针 可以用 C 语言中的"结构指针"来描述链表结构。 typedef struct LNode {
　　　　ElemType data; 　　　　struct LNode *next; 　　　} *SLink; 　 若设 LNode *p,*q; 　　　　SLink H; 　　则 p，q 和 H 均为以上定义的指针型变量。若 p 的值非空，则表明 p 指向某个结点，p->data 表示 p 所指结点中的数据域，p->next 表示 p 所指结点中的指针域，若非空，则指向其"后继"结点。 数据结构

51 2.3.2 单链表中基本操作的实现 一、初始化操作 根据上一节的约定，初始化建一个空的链表即为建立一个只有头结点的链表。 算法2.13
　　根据上一节的约定，初始化建一个空的链表即为建立一个只有头结点的链表。 算法2.13 　void InitList( SLink &L ) 　{ 　　// 创建一个带头结点的空链表,L 为指向头结点的指针 　　L = (LNode *)malloc( sizeof( LNode)); 　　if (!L) exit(1); 　// 存储空间分配失败 　　L->next = NULL; 　} // InitList 数据结构

52 2.3.2 单链表中基本操作的实现 二、销毁结构操作 算法2.14 void DestroyList( SLink &L) {
　{ 　　// 销毁以L为头指针的单链表，释放链表中所有结点空间 　　while (L) 　　{ 　　　p = L; 　　　L = L->next; 　　　free( p); 　　} // while 　　L = NULL; 　} // DestroyList 数据结构

53 2.3.2 单链表中基本操作的实现 三、存取元素操作 算法2.15
　bool GetElem ( SLink L, int pos, ElemType &e )　{ 　　// 若1≤pos≤LengthList(L)，则用 e 带回指针L指向头结点的单链表 　　// 中第 pos 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE 　　p = L->next; j =1; 　　　　// 变量初始化，p 指向第一个结点 　　while ( p && j< pos ) 　　{ 　　　// 顺结点的指针向后查找，直至 p 指到第pos个结点或 p 为空止 　　　p = p->next; ++j; 　　} // while 　　if ( !p || j>pos ) return FALSE; // 链表中不存在第 pos 个结点 　　e = p->data; 　　　　　　　　　　 // 取到第 pos 个元素 　　return TRUE; 　} // GetElem 　　算法的时间复杂度为 O (ListLength(L))。 数据结构

54 算法时间复杂度为O (ListLength(L))。
2.3.2 单链表中基本操作的实现 四、插入元素操作 bool ListInsert ( SLink &L, int pos, ElemType e )　{ //算法2.16 　　// 若1≤pos≤LengthList(L)+1，则在指针L指向头结点的单链表 　　// 的第 pos 个元素之前插入新的元素 e，且返回函数值为 TRUE, 　　// 否则不进行插入且返回函数值为 FALSE 　　p=L; j=0; 　　while(p && j<pos-1)　{ 　// 查找第pos-1个结点，并令指针p指向该结点 　　　p=p->next; ++j; 　　} // while 　　if(!p||j>pos-1)　return FALSE;// 参数不合法，pos 小于1或者大于表长+1 　　s=(LNode *)malloc( sizeof( LNode)); 　　if (!s) exit(1); 　　　　 　// 存储空间分配失败 　　s->data=e; 　　　　　　　　// 创建新元素的结点 　　s->next=p-> next; p->next=s; // 修改指针 　　return TRUE; } // ListInsert 　　算法时间复杂度为O (ListLength(L))。 数据结构

55 2.3.2 单链表中基本操作的实现 五、删除元素操作 　bool ListDelete ( SLink &L, int pos, ElemType &e){ //算法2.17 　　// 若1≤pos≤LengthList(L)，则删除指针L指向头结点的单链表 　　// 中第 pos 个元素并以 e 带回其值，返回函数值为 TRUE， 　　// 否则不进行删除操作且返回函数值为 FALSE 　　p = L; j = 0; 　　while (p->next && j < i-1){　　 // 寻找第pos个结点，并令p指向其前驱 　　　p = p->next; ++j; 　　} 　　if (!(p->next) || j > i-1) return FALSE; 　　　　// 删除位置不合理 　　q = p->next; p->next = q->next;　// 修改指针 　　e = q->data; free(q);　　　　// 释放结点空间 　　return TRUE; 　} // ListDelete_L 　　算法时间复杂度为 O (ListLength(L))。 数据结构

56 2.3.2 单链表中基本操作的实现 Shaffer书中的实现： 单链表结点类的定义 // Singly-linked list node
template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } }; 数据结构

57 2.3.2 单链表中基本操作的实现 Shaffer Fence的选择与head节点的使用 数据结构

58 2.3.2 单链表中基本操作的实现 // Linked list implementation
Shaffer // Linked list implementation template <class Elem> class LList: public List<Elem> { private: Link<Elem>* head; // Point to list header Link<Elem>* tail; // Pointer to last Elem Link<Elem>* fence;// Last element on left int leftcnt; // Size of left int rightcnt; // Size of right void init() { // Intialization routine fence = tail = head = new Link<Elem>; leftcnt = rightcnt = 0; } 数据结构

59 2.3.2 单链表中基本操作的实现 void removeall() {
Shaffer void removeall() { // Return link nodes to free store while(head != NULL) { fence = head; head = head->next; delete fence; } public: LList(int size=DefaultListSize) { init(); } ~LList() { removeall(); } // Destructor void clear() { removeall(); init(); } 数据结构

60 2.3.2 单链表中基本操作的实现 void setStart() { fence = head; rightcnt += leftcnt;
Shaffer void setStart() { fence = head; rightcnt += leftcnt; leftcnt = 0; } void setEnd() { fence = tail; leftcnt += rightcnt; rightcnt = 0; } void next() { // Don't move fence if right empty if (fence != tail) { fence = fence->next; rightcnt--; leftcnt++; } } int leftLength() const { return leftcnt; } int rightLength() const { return rightcnt; } bool getValue(Elem& it) const { if(rightLength() == 0) return false; it = fence->next->element; return true; } 数据结构

61 插入 2.3.2 单链表中基本操作的实现 // Insert at front of right partition
Shaffer // Insert at front of right partition template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence->next); if (tail == fence) tail = fence->next; rightcnt++; return true;} // Append Elem to end of the list bool LList<Elem>::append(const Elem& item) { tail = tail->next = new Link<Elem>(item, NULL); rightcnt++; 插入 数据结构

62 删除 2.3.2 单链表中基本操作的实现 // Remove and return first Elem in right
Shaffer // Remove and return first Elem in right // partition template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; it = fence->next->element; // Remember val // Remember link node Link<Elem>* ltemp = fence->next; fence->next = ltemp->next; // Remove if (tail == ltemp) // Reset tail tail = fence; delete ltemp; // Reclaim space rightcnt--; return true; } 数据结构

63 2.3.2 单链表中基本操作的实现 // Move fence one step left;
Shaffer // Move fence one step left; // no change if left is empty template <class Elem> void LList<Elem>::prev() { Link<Elem>* temp = head; if (fence == head) return; // No prev Elem while (temp->next!=fence) temp=temp->next; fence = temp; leftcnt--; rightcnt++; } 数据结构

64 2.3.2 单链表中基本操作的实现 // Set the size of left partition to pos
Shaffer // Set the size of left partition to pos template <class Elem> bool LList<Elem>::setPos(int pos) { if ((pos < 0) || (pos > rightcnt+leftcnt)) return false; fence = head; for(int i=0; i<pos; i++) fence = fence->next; return true; } 数据结构

65 2.3.3 单链表其它算法举例 例2-7 逆序创建链表 例2-8 以链表作存储结构解例2-5的问题，即将线性表 (a1,a2,…,am,b1,b2,…,bn) 改变成 (b1,b2,…,bn,a1,a2,…,am) 。 例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。 数据结构

66 2.3.3 单链表其它算法举例 void CreateList_L(SLink &L, int n, ElemType A[]) {
例2-7 逆序创建链表 算法2.19 　　void CreateList_L(SLink &L, int n, ElemType A[]) 　{ 　　// 已知数组 A 中存有线性表的 n 个数据元素， 　　// 逆序建立带头结点的单链表。 　　L = new LNode; 　　if (!L) exit(1); 　　　　// 存储空间分配失败 　　L->next = NULL;　　// 先建立一个带头结点的空的单链表 　　for (i = n; i > 0; --i) 　　{ p = new LNode; 　　　if (!p) exit(1); 　　　　// 存储空间分配失败 　　　　p->data = A[i-1]; 　　　　　 　// 赋元素值 　　　　p->next = L->next; L->next = p; // 插入在头结点之后 　　} // for 　} // CreateList_L 　　容易看出，算法的时间复杂度为O (ListLength(L))。 数据结构

67 2.3.3 单链表其它算法举例 例2-8 以链表作存储结构解例2-5的问题，即将线性表 (a1,a2,…,am,b1,b2,…,bn) 改变成 (b1,b2,…,bn,a1,a2,…,am) 。 算法2.20 　　void exchange_L( SLink &L，int m )　{ 　　// 本算法实现单链表中前 m 个结点和后 n 个结点的互换 　　if ( m && L->next ){ 　　　　// 链表不空且 m!=0 　　　p = L->next; k = 1; 　　　while( k< m && p ){　　　　// 查找 所在结点 　　　　p = p->next; ++k; 　　　} // while 循环的条件中为什么要有p!=NULL的判断？ 　　　if (p && p->next) {　　　　// n!=0 时才需要修改指针 　　　　ha = L->next; 　　　　　 // 以指针 ha 记 结点的位置 　　　　L->next = p->next;　　　 // 将 结点链接在头结点之后 　　　　p->next = NULL;　　　　　// 设 的后继为空 　　　　q = L->next;　　　　　　 // 令q 指向 结点 　　　　while (q->next) q = q->next; // 查找 结点 　　　　q->next = ha; 　　　　　 // 将 结点链接到 结点之后 　　　} // if(p) 　　} // if(m) 　} // exchange_L 翻页后有 大字版本 数据结构

68 2.3.3 单链表其它算法举例 例2-8 以链表作存储结构解例2-5的问题，即将线性表 (a1,a2,…,am,b1,b2,…,bn) 改变成 (b1,b2,…,bn,a1,a2,…,am) 。 算法2.20 　　void exchange_L( SLink &L，int m )　{ 　　// 本算法实现单链表中前 m 个结点和后 n 个结点的互换 　　if ( m && L->next ){ 　　　　// 链表不空且 m!=0 　　　p = L->next; k = 1; 　　　while( k< m && p ){　　　　// 查找 所在结点 　　　　p = p->next; ++k; 　　　} // while 循环的条件中为什么要有p!=NULL的判断？ ………………. 　　} // if(m) 　} // exchange_L 数据结构

69 2.3.3 单链表其它算法举例 例2-8 以链表作存储结构解例2-5的问题，即将线性表 (a1,a2,…,am,b1,b2,…,bn) 改变成 (b1,b2,…,bn,a1,a2,…,am) 。 算法2.20 …………… 　　　if (p && p->next) {　　　　// n!=0 时才需要修改指针 　　　　ha = L->next; 　　　　　 // 以指针 ha 记 结点的位置 　　　　L->next = p->next;　　　 // 将 结点链接在头结点之后 　　　　p->next = NULL;　　　　　// 设 的后继为空 　　　　q = L->next;　　　　　　 // 令q 指向 结点 　　　　while (q->next) q = q->next; // 查找 结点 　　　　q->next = ha; 　　　　　 // 将 结点链接到 结点之后 　　　} // if(p) 　　} // if(m) 　} // exchange_L 数据结构

70 2.3.3 单链表其它算法举例 例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。 算法2.21 　　void purge_L(SLink &L ){ 　　// 删除单链表L中的冗余元素，即使操作之后的单链表中只保留 　　// 操作之前表中所有值都不相同的元素 　　p = L->next; 　　L->next = NULL;　　　　　// 设新表为空表 　　while ( p ){　　　　　　　 // 顺序考察原表中每个元素 　　　succ = p->next;　　　　　// 记下结点 *p 的后继 　　　q = L->next;　　　　　　 // q 指向新表的第一个结点 　　　while( q && p->data!=q->data ) q = q->next; 　　　　　　　　　　　　// 在新表中查询是否存在和p->data相同的元素 　　　if ( !q ){　　　　　　　 // 将结点 *p 插入到新的表中 　　　　p->next = L->next; 　　　　L->next = p; 　　　}else delete p;　　　　// 释放结点 *p 　　　p = succ; 　　} // while p 　} // purge_L　　此算法的时间复杂度为O (ListLength2(L))。 翻页后有 大字版本 数据结构

71 2.3.3 单链表其它算法举例 例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。 算法2.21
　void purge_L(SLink &L ){ 　// 删除单链表L中的冗余元素，即使操作之后的单链表中只保留 　// 操作之前表中所有值都不相同的元素 　　p = L->next; 　　L->next = NULL;　　　　　// 设新表为空表 　　while ( p ){　　　　　　　 // 顺序考察原表中每个元素 　　　succ = p->next;　　　　　// 记下结点 *p 的后继 　　　q = L->next;　　　　　　 // q 指向新表的第一个结点 　　　while( q && p->data!=q->data ) q = q->next; 　　　　　　　　// 在新表中查询是否存在和p->data相同的元素 ………………. 　　} // while p 　} // purge_L　　此算法的时间复杂度为O (ListLength2(L))。 数据结构

72 2.3.3 单链表其它算法举例 例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。 算法2.21
　void purge_L(SLink &L ){ 　// 删除单链表L中的冗余元素，即使操作之后的单链表中只保留 　// 操作之前表中所有值都不相同的元素 …………….. 　　　if ( !q ){　　　　　　　 // 将结点 *p 插入到新的表中 　　　　p->next = L->next; 　　　　L->next = p; 　　　}else delete p;　　　　// 释放结点 *p 　　　p = succ; 　　} // for 　} // purge_L　　此算法的时间复杂度为O (ListLength2(L))。 数据结构

73 2.3.3 单链表其它算法举例 从以上对链表的各种操作的讨论可知，链式存储结构的优势在于： (1) 能有效利用存储空间；
(2) 用"指针"指示数据元素之间的后继关系，便于进行"插入"、"删除"等操作； 数据结构

74 2.3.3 单链表其它算法举例 链式存储的劣势是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的“表长”和数据元素在线性表中的“位序”，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 数据结构

75 2.3.3 单链表其它算法举例 为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设"尾指针"和"表长"两个属性，同时，我们从上面讨论的链表基本操作的实现算法中可以看出，在对链表进行操作时，经常需要一个指针在链表中巡游，由此可以设想，如果将这个在操作中进行巡游的"指针"以及它所指结点的数据元素在线性表中的"位序"纳入链表结构中，作为链表定义中的两个成员，必然会对链表的操作带来很多方便。 数据结构

76 2.3.4 循环链表 循环链表(Circular Linked List)是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。 循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"。 a1 a2 an … 头指针 头结点 数据结构

77 2.3.5 双向链表 双向链表(Double Linked List)的特点是其结点结构中含有两个指针域，其一指向数据元素的"直接后继"，另一指向数据元素的"直接前驱"，用 C 语言描述如下： typedef struct DuLNode { 　　　　ElemType data; 　　　　struct DuLNode *prior; 　　　　struct DuLNode *next; 　　　} DuLNode, *DuLink; 数据结构

78 2.3.5 双向链表 与单链表类似，双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示。 空表 非空表 a1 a2 an ... 数据结构

79 2.3.5 双向链表 在双向链表上进行操作基本上和单向链表相同，例如，查找结点也是要从头指针指示的头结点开始，但插入和删除时必须同时修改两个方向上的指针，它们的算法分别如下所示。 算法2.22 void ListInsert_DuL(DuLink &L, DuLNode* p, DuLNode* s ) 　{ 　　// 在带头结点的双向循环链表 L 中结点 *p 之后插入结点 *s 　　s->next = p->next; p->next = s; 　　s->next->prior = s; s->prior = p; 　}// ListInsert_DuL 数据结构

80 2.3.5 双向链表 算法2.23 　　void ListDelete_DuL(DuLink &L, DuNode* p, ElemType &e) 　{ // 删除带头结点的双向循环链表L中结点 *p 的后继， // 并以 e 返回它的数据元素 　　q = p->next; e = q->data; 　　p->next = q->next; 　　p->next->prior = p; 　　free( q); 　} // ListDelete_DuL 数据结构

81 静态链表 可以利用数组表示链表 设关键字存储在数组 key 中 指针存储在数组 prev 和 next 中
对于某一个下标 n，key[n]、prev[n]、next[n] 一起构成链表中的一个节点，这个 n 相当于指向该节点的指针，其中 prev[n]、next[n] 存放的分别是该节点前驱、后继节点的数组下标。 静态链表在某些没有指针的程序设计语言、在一些特定的应用中被广泛采用。 prev key next 数据结构

82 静态链表 静态链表的实现要点： 表示前驱、后继的数组中用特定值如-1表示空指针
数组中的元素可以分成两类，要么属于该链表，要么不属于该链表（尚未使用）。通常将未使用的元素链接起来，称作自由表(free list)，用于维护插入、删除操作所需要的节点变化。 数据结构

83 静态链表 一个例子(page 269) 3 2 7 4 5 1 8 6 52 27 13 76 97 65 38 49 key next index 在某些情形下，为了对该静态链表进行随机存取，需要对其记录进行重新排列，使其按序存储。 8 7 6 5 4 3 2 1 97 76 65 52 49 38 27 13 key next index 一个问题：如何在尽量少的辅助存储下实现记录的重排？ 数据结构

84 静态链表 算法的说明： 基本的作法是把第i个节点移动至数组的第i个分量中。
根据头节点中指针域的指示，链表的第一个节点移至数组的第一个分量中（将其与第一个互换），为了不中断静态链表中的“链”，即在继续顺链扫描时仍能找到互换之前的第一个节点，令其指针域修改为链表第一个所在的序号。 一般地，若第i个最小关键字的节点是数组中下标为p且p>i的分量，则互换SL.r[i]和SL.r[p]，且令SL.r[i]中的指针域的值改为p；由于此时数组中所有小于i的分量中已经是“到位”的记录，则当p<i时，应顺链继续查找直道p>=i为止。 数据结构

85 静态链表 过程： 1 2 3 4 5 6 7 8 K 49 38 65 97 76 13 27 52 1 2 3 4 5 6 7 8 K 13 38 65 97 76 49 27 52 (6) i=1 p=6 1 2 3 4 5 6 7 8 K 13 27 65 97 76 49 38 52 (6) (7) i=2 p=7 数据结构

86 静态链表 过程： i=3 p=(2)7 i=4 p=(1),6 i=5 p=8 1 2 3 4 5 6 7 8 K 13 27 38 97
1 2 3 4 5 6 7 8 K 13 27 38 97 76 49 65 52 (6) (7) i=3 p=(2)7 1 2 3 4 5 6 7 8 K 13 27 38 49 76 97 65 52 (6) (7) i=4 p=(1),6 1 2 3 4 5 6 7 8 K 13 27 38 49 52 97 65 76 (6) (7) (8) i=5 p=8 数据结构

87 静态链表 void Arrange( SLinkListType &SL){ p =SL.r[0].next
for( i=1; i<SL.length; ++i){ while(p<i) p = SL.r[p].next; q = SL.r[p].next; if( p!=i){ SL.r[p]  SL.r[i]; SL.r[i].next = p;} p=q; } 数据结构

88 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
数据结构

89 2.4 一元多项式的表示及相加 一元多项式： Pn(x) = p0+p1x+p2x2 … + pnxn 在计算机中，可以用一个线性表来表示:
P = (p0, p1, …，pn) 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？ 数据结构

90 2.4 一元多项式的表示及相加 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + … + pmxem
其中：pi 是指数为ei 的项的非零系数， 0≤ e1 < e2 < ┄ < em = n 可以用下列线性表表示： （（p1, e1）, (p2, e2), …, (pm,em) ） 数据结构

91 2.4 一元多项式的表示及相加 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示 例如:
P999(x) = 7x3 - 2x12 - 8x999 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示 数据结构

92 2.4 一元多项式的表示及相加 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象： 数据关系：
D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } 数据结构

93 2.4 一元多项式的表示及相加 基本操作： DestroyPolyn ( &P ) PrintPolyn ( &P )
CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。 数据结构

94 2.4 一元多项式的表示及相加 AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) … …
PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) … … } ADT Polynomial 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。 数据结构

95 2.4 一元多项式的表示及相加 一元多项式的实现： 结点的数据元素类型定义为:
typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType; 数据结构

96 2.4 一元多项式的表示及相加 Status CreatPolyn ( polynomail &P, int m ) {
// 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项 } return OK; scanf (e.coef, e.expn); if (!LocateElem ( P, e, (*cmp)()) ) if ( !InsAfter ( P, e ) ) return ERROR; 注意: 1.输入次序不限; 2.指数相同的项只能输入一次 数据结构

97 2.4 一元多项式的表示及相加 Status AddPolyn ( polynomial &Pc,
polynomial &Pa, polynomial &Pb) { // 利用两个多项式的结点构成“和多项式” Pc = Pa＋Pb … … if (DelAfter(Pa, e1)) a=e1.expn else a=MAXE; if (DelAfter(Pb, e2)) b=e2.expn else b=MAXE; while (!(a==MAXE && b==MAXE)) { } } // AddPolyn 数据结构

98 2.4 一元多项式的表示及相加 switch (*cmp(e1, e2)) { case -1: { // 多项式PA中当前结点的指数值小
… … break; } case 0: { // 两者的指数值相等 e1.coef= a.coef + b.coef ; if ( a.coef != 0.0 ) InsAfter(Pc, e1); … … break; } case 1: { //多项式PB中当前结点的指数值小 数据结构

99 2.4 一元多项式的表示及相加 输入输出 简单实现 完整实现 A sample step by step implementation:
数据结构