线性表 顺序表 单链表 循环链表 双向链表 多项式 第2章 线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式

2.1 线性表 (Linear List) 线性表的定义 线性表是 n (≥0) 个数据元素的有限序列 （a1, a2, …, an） ai 是表中数据元素，n 是表长度。 原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。 为简单起见，假定各元素类型相同。

a1 a2 a3 a4 a5 a6 直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系） 线性表的特点 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 a1 a2 a3 a4 a5 a6 直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）

线性表的抽象基类(ADT) template <class T, class E> class LinearList { public: LinearList(); //构造函数 ～LinearList(); //析构函数 virtual int Size() const = 0; //求表最大体积 virtual int Length() const = 0; //求表长度 virtual int Search(T x) const = 0; //搜索 virtual int Locate(int i) const = 0; //定位 virtual E* getData(int i) const = 0; //取值 virtual void setData(int i, E x) = 0; //赋值

virtual bool Insert(int i, E x) = 0; //插入 virtual bool Remove(int i, E& x) = 0; //删除 virtual bool IsEmpty() const = 0; //判表空 virtual bool IsFull() const = 0; //判表满 virtual void Sort() = 0； //排序 virtual void input() = 0； //输入 virtual void output() = 0； //输出 virtual LinearList<T, E>operator= (LinearList<T, E>& L) = 0; //复制 };

2.2 顺序表 (Sequential List) 25 34 57 16 48 09 data 顺序表的定义和特点： 定义：顺序存储的 n（  0）个表项的有限序列（a1, a2, …, an） ai是表项，n是表长度。 特点：所有元素的逻辑先后顺序与其物理存放顺序一致; 25 34 57 16 48 09 0 1 2 3 4 5 data 可以进行顺序访问,也可以进行随机访问

顺序表的静态存储和动态存储 #define maxSize 100 typedef int T; typedef struct { T data[maxSize]; //顺序表的静态存储表示 int n; } SeqList; T *data; //顺序表的动态存储表示 int maxSize, n;

const int defaultSize = 100; 顺序表(SeqList)类的定义 P.46 const int defaultSize = 100; template <class Type> class SeqList { Type *data; //顺序表存储数组 int MaxSize; //最大允许长度 int last; //当前最后元素下标 public: SeqList ( int sz = defaultSize ); ~SeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } int Find ( Type & x ) const;

int IsIn ( Type & x ); int Insert ( Type & x, int i ); int Remove ( Type & x ); int Next ( Type & x ) ; int Prior ( Type & x ) ; int IsEmpty ( ) { return last ==-1; } int IsFull ( ) { return last == MaxSize-1; } Type Get ( int i ) { return i < 0 || i > last？NULL : data[i]; }

template <class Type> //构造函数 顺序表部分公共操作的实现: template <class Type> //构造函数 SeqList<Type> :: SeqList ( int sz ) { if ( sz > 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; if ( data == NULL ) { cerr << “存储分配错” << endl; }

template <class Type> 顺序表的搜索算法 template <class Type> int SeqList<Type>::Search ( Type & x ) const { //搜索函数：在表中从前向后顺序查找 x int i = 0; while ( i <= last && data[i] != x ) i++; if ( i > last ) return -1; else return i; }

查找： int Search ( Type & x ) 主要思想： 顺序表的查找、插入和删除 查找： int Search ( Type & x ) 主要思想： （1）从表的第一个数据元素起，依次和x进行比较，若存在某个表项的值和x相等，则查找成功，并返回该表项的位置。 （2）如果查遍整个顺序表，都没有找到其值和x相等的表项，则查找不成功，并返回-1。

x = 50 x =48

查找算法分析： 最好： 最坏： 平均： 1 n 相等概率 * O(n)

插入： int Insert ( Type & x, int i ) 25 34 57 16 48 09 63  0 1 2 3 4 5 6 7 data 50 插入 x 25 34 57 50 16 48 09 63  i

插入的主要思想： （1）检查插入操作要求的有关参数的合理性； （2）将顺序表最后位置加1 （3）将第i至第n-1个表项依次往后移动一个位置； （4）把新的表项插入在顺序表的第i个位置

template <class Type> int SeqList<Type>::Insert ( Type & x, int i ){ //在表中第 i 个位置插入新元素 x if ( i < 0 || i > last+1 || last == MaxSize-1 ) return 0; //插入不成功 else { last++; for ( int j = last; j > i; j-- ) data[j] = data[j -1]; data[i] = x; return 1; //插入成功 }

插入算法分析(移动的元素个数) 最好： 最坏： 平均： n *O(n)

删除： int Remove ( Type & x )

删除的主要思想： (1) 在顺序表中查找x,如果x在表中不存在，则不能删除； (2)如果x在表中存在，设x在顺序表中的位置为i; (3) 将顺序表的最后位置减1； (4)把顺序表中原来第i+1至第n-1个表项依次向前移动一个表项位置

template <class Type> int SeqList<Type>::Remove ( Type & x ) { //在表中删除已有元素 x int i = Find (x); //在表中搜索 x if ( i >= 0 ) { last-- ; for ( int j = i; j <= last; j++ ) data[j] = data[j+1]; return 1; //成功删除 } return 0; //表中没有 x

删除算法分析（移动的元素个数） 最好： 最坏： 平均： n-1 *O(n)

template <class Type> 顺序表的应用：集合的“并”和“交”运算 template <class Type> void Union ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); for ( int i = 1; i <= m; i++ ) { Type x = LB.Get(i); //在LB中取一元素 int k = LA.Find (x); //在LA中搜索它 if ( k == -1 ) //若未找到插入它 { LA.Insert (n+1, x); n++; } } ？

template <class Type> void Intersection ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); int i = 0; while ( i < n ) { Type x = LA.Get (i); //在LA中取一元素 int k = LB.Find (x); //在LB中搜索它 if ( k == -1 ) { LA.Remove (i); n--; } else i++; //未找到在LA中删除它 }

顺序表： 优点：存储利用率高，存取速度快 插入和删除操作时？ 插入：AMN=n/2 删除：AMN=(n-1)/2

链表 1 4 ^ 5 7 9 31 8 13 21 指针域 数据域 43 头指针 存储地址 构成顺序表： （4，21，9，8，5）

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

单链表的存储映像 (a) 可利用存储空间 free a0 a2 a1 a3  free first (b) 经过一段运行后的单链表结构

单链表的类定义 使用面向对象方法，把数据与操作一起定义和封装，用多个类表达一个单链表。 链表结点(ListNode)类 链表(List)类 定义方式 复合方式 嵌套方式 继承方式 结构方式

class List; //复合方式 class ListNode { //链表结点类 friend class List; //链表类为其友元类 private: int data; //结点数据, 整型 ListNode * link; //结点指针 }; class List { //链表类 ListNode *first ; //表头指针

class List { //嵌套方式 private: class ListNode { //嵌套链表结点类 public: int data; ListNode *link; }; ListNode *first; //表头指针 //链表操作………

//链表类和链表结点类定义(继承方式) class ListNode { //链表结点类 protected: int data; ListNode * link; }; class List : public class ListNode { //链表类, 继承链表结点类的数据和操作 private: ListNode *first; //表头指针

//链表类和链表结点类定义(结构方式) struct ListNode { //链表结点类 int data; ListNode * link; }; class List { //链表类, 直接使用链表结点类的数据和操作 private: ListNode *first; //表头指针 //链表中的结点属于链表私有，别人无法访问

（在单链表a0,a1,a2,…,an-1的包含数据ai的结点之前插入一个新元素） 单链表中的插入与删除 插入 （在单链表a0,a1,a2,…,an-1的包含数据ai的结点之前插入一个新元素） 第一种情况：在第一个结点前插入 newnode first （插入前） newnode→link = first ; first = newnode；

第二种情况：在链表中间插入 (插入前) ai-1 newnode current newnode→link = current→link; current→link = newnode； newnode→link = current→link; current→link = newnode；

第三种情况：在链表末尾插入 (插入前) newnode→link = current→link;(NULL) ^ ^ newnode→link = current→link;(NULL) current→link = newnode；

bool List::Insert(int i, int x) { //将新元素 x 插入到第 i 个结点之后。i 从1开始， //i = 0 表示插入到首元结点之前。 if (first == NULL || i == 0) { //空表或首元结点前 LinkNode *newNode = new LinkNode(x); //建立一个新结点 newNode->link = first; first = newNode; //新结点成为首元结点 } else { //否则，寻找插入位置 LinkNode *current = first; int k = 1;

while (k < i && current != NULL) //找第i结点 { current = current->link; k++; } if (current = = NULL && first != NULL) //链短 {cerr << “无效的插入位置!\n”; return false;} else { //插入在链表的中间和末尾 LinkNode *newNode = new LinkNode(x); newNode->link = current->link; current->link = newNode; } return true; };

删除(表中第i个结点) —第一种情况: 删除表中第一个元素  ai ai+1 删除前 删除后 del = first； current del —第一种情况: 删除表中第一个元素  ai ai+1 del 删除前 删除后 first current del = first； first = first→link; delete del；

—第二种情况: 删除表中或表尾元素  ai-1 ai ai+1 current del 删除前 删除后 del= current→link; current→link = del→link; delete del；

单链表的删除算法 bool List::Remove (int i, int& x) { //将链表中的第 i 个元素删去, i 从1开始。 LinkNode *del; //暂存删除结点指针 if (i <= 1) { del = first; first = first->link; } else { LinkNode *current = first; k = 1; //找i-1号结点 while (k < i-1 && current != NULL) { current = current->link; k++; } if (current == NULL || current->link == NULL) { cout << “无效的删除位置!\n”; return false; } del = current->link; //删中间/尾结点 current->link = del->link; x = del->data; delete del; //取出被删结点数据 return true; };

关于单链表的插入和删除 实现单链表的插入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。 情况复杂，空表和在表头插入的特殊情形要考虑。 寻找插入或删除位置只能沿着链顺序检测。

^ 非空表 空表 表头结点位于表的最前端，本身不带数据，仅标志表头。 表头结点data域内的数据存放一些辅助数据或者为空。 带附加头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 表头结点data域内的数据存放一些辅助数据或者为空。 非空表 空表 ^ an a1 first

带表头结点的单链表插入操作 —（第一个结点前插入新结点） 插入 first 非空表: newnode 空表： current 非空表: 空表： newnode→link = current→link; current→link = newnode;

回忆:无表头结点的插入 bool List::Insert(int i, int x) { //将新元素 x 插入到第 i 个结点之后。i 从1开始， //i = 0 表示插入到首元结点之前。 if (first == NULL || i == 0) { //空表或首元结点前 LinkNode *newNode = new LinkNode(x); //建立一个新结点 newNode->link = first; first = newNode; //新结点成为首元结点 } else { //否则，寻找插入位置 LinkNode *current = first; int k = 1;

在链表尾插入 在链表中间插入 ai-1 newnode newnode ^ current current ^ newnode→link = current→link; current→link = newnode； newnode→link = current→link; current→link = newnode；

带附加头结点的单链表 空表或非空表第一个结点之前的插入可以不作为特殊情况专门处理,与一般情况一样统一处理; 统一了空表与非空表的操作。

带表头结点的单链表删除操作： —删除第一个结点 非空表 q = p→link; 空表 ^ p q p→link = q→link; first ^ p q 非空表 空表 q = p→link; p→link = q→link; delete q; ? if ( p→link==NULL ) last = p;

用模板定义的单链表类： template <class T, class E> //定义在“LinkedList.h” struct LinkNode { //链表结点类的定义 E data; //数据域 LinkNode<T, E> *link; //链指针域 LinkNode() { link = NULL; } //构造函数 LinkNode(E item, LinkNode<T, E> *ptr = NULL) { data = item; link = ptr; } //构造函数 bool operator== (T x) { return data.key == x; } //重载函数，判相等 bool operator != (T x) { return data.key != x; } };

template <class T, class E> class List : public LinearList<T, E> { //单链表类定义, 不用继承也可实现 protected: LinkNode<T, E> *first; //表头指针 public: List() { first = new LinkNode<T, E>; } //构造函数 List(E x) { first = new LinkNode<T, E>(x); } List( List<T, E>& L); //复制构造函数 ~List(){ } //析构函数 void makeEmpty(); //将链表置为空表 int Length() const; //计算链表的长度

LinkNode<T, E> *Search(T x); //搜索含x元素 LinkNode<T, E> *Locate(int i); //定位第i个元素 E *getData(int i); //取出第i元素值 void setData(int i, E x); //更新第i元素值 bool Insert (int i, E x); //在第i元素后插入 bool Remove(int i, E& x); //删除第i个元素 bool IsEmpty() const //判表空否 { return first->link == NULL ? true : false; } LinkNode<T, E> *getFirst() const { return first; } void setFirst(LinkNode<T, E> *f ) { first = f; } void Sort(); //排序 };

链表置空算法（保留表头结点） template <class T, class E> void List<T, E>::makeEmpty() { LinkNode<T, E> *q; while (first->link != NULL) { q = first->link; //保存被删结点 first->link = q->link; //从链上摘下该结点 delete q; //删除 } }；

first q a0 a1 a2 current

template <class T, class E> 求单链表的长度的算法 template <class T, class E> int List<T, E> :: Length ( ) const { ListNode<T, E> *p = first->link; //检测指针 p 指示第一号结点 int count = 0; while ( p != NULL ) { //逐个结点检测 p = p->link; count++; } return count;

first a0 a1 a2 c = 0 p first a0 a1 a2 c = 1 p first a0 a1 a2 c = 2 p first a0 a1 a2 c = 3 p

单链表的搜索算法 template <class T, class E> LinkNode<T, E> *List<T, E>::Search(T x) { //在表中搜索含数据x的结点, 搜索成功时函数返 //该结点地址; 否则返回NULL。 LinkNode<T, E> *current = first->link; while ( current != NULL && current->data != x ) current = current->link; //沿着链找含x结点 return current; };

单链表的定位算法 template <class T, class E> LinkNode<T, E> *List<T, E>::Locate ( int i ) { //函数返回表中第 i 个元素的地址。若i < 0或 i 超 //出表中结点个数，则返回NULL。 if (i < 0) return NULL; //i不合理 LinkNode<T, E> *current = first; int k = 0; while ( current != NULL && k < i ) { current = current->link; k++; } return current; //返回第 i 号结点地址或NULL };

单链表的插入算法 template <class T, class E> bool List<T, E>::Insert (int i, E x) { //将新元素 x 插入在链表中第 i 个结点之后。 LinkNode<T, E> *current = Locate(i); if (current == NULL) return false; //无插入位置 LinkNode<T, E> *newNode = new LinkNode<T, E>(x); //创建新结点 newNode->link = current->link; //链入 current->link = newNode; return true; //插入成功 };

template <class T, class E> 单链表的删除算法 template <class T, class E> bool List<T, E>::Remove (int i, E& x ) { //删除链表第i个元素, 通过引用参数x返回元素值 LinkNode<T, E> *current = Locate(i-1); if ( current == NULL || current->link == NULL) return false; //删除不成功 LinkNode<T, E> *del = current->link; current->link = del->link; x = del->data; delete del; return true; };

建立单链表 头建立 尾建立 first newnode ^ ^ newnode first

生成新结点； 将读入数据存放到新结点的数据域中； 将该新结点插入到链表的前端。 ^ 从一个空表开始，重复读入数据： 直到读入结束符为止。 头建立单链表 从一个空表开始，重复读入数据： 生成新结点； 将读入数据存放到新结点的数据域中； 将该新结点插入到链表的前端。 直到读入结束符为止。 first newnode ^

template <class Type> void List<Type> :: createListF(Type endTag) { Type val; ListNode<Type> *node; first = new ListNode<Type>; //表头结点 cin >> val; while ( val != endTag ) { node = new ListNode<Type>(val); node->link = first->link; first->link = node; //插入到表前端 }

^ 每次将新结点插到链表的表尾； 设置一个尾指针 last，总是指向表中最后一个结点，新结点插在它的后面； 尾建立单链表 每次将新结点插到链表的表尾； 设置一个尾指针 last，总是指向表中最后一个结点，新结点插在它的后面； 尾指针初始时置为指向表头结点地址。 ^ newnode first last

template <class Type> void List<Type> :: createListR(Type endTag) { Type val; ListNode<Type> *node, *last; first = new ListNode<Type>; //表头结点 cin >> val; last = first; while ( val != endTag ) { //last指向表尾 node = new ListNode<Type>(val); last->link = node; last = node; cin >> val; //插入到表末端 } last->link = NULL; //表收尾

2.3 线性链表的其他变形 循环链表 双向链表

循环链表 (Circular List) 示例: 带表头结点的循环链表示例：

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

循环链表类的定义 template <class T, class E> struct CircLinkNode { //链表结点类定义 E data; CircLinkNode<T, E> *link; CircLinkNode ( CircLinkNode<T, E> *next = NULL ) { link = next; } CircLinkNode ( E d, CircLinkNode<T, E> *next = NULL ) { data = d; link = next; } bool Operator==(E x) { return data.key == x.key; } bool Operator!=(E x) { return data.key != x.key; } };

template <class T, class E> //链表类定义 class CircList : public LinearList<T, E> { private: CircLinkNode<T, E> *first, *last; //头指针, 尾指针 public: CircList(const E x); //构造函数 CircList(CircList<T, E>& L); //复制构造函数 ～CircList(); //析构函数 int Length() const; //计算链表长度 bool IsEmpty() { return first->link == first; } //判表空否 CircLinkNode<T, E> *getHead() const; //返回表头结点地址

循环链表的操作 1：搜索算法 搜索成功 搜索不成功 first 31 48 15 57 搜索15   搜索25 current

template <class Type> 循环链表的搜索算法 template <class Type> CircListNode<Type> * CircList<Type> :: Find ( Type value ) { //在链表中从头搜索其数据值为value的结点 current = first->link; while ( current != first && current->data != value ) current = current->link; return current; }

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

例如 n = 8 m = 3

约瑟夫问题的解法 #include <iostream.h> #include “CircList.h” Template<Type> void CircList<Type>:: Josephus ( int n, int m ) { Firster ( ); for ( int i = 0; i < n-1; i++ ) { //执行n-1次 for ( int j = 0; j < m-1; j++ ) Next ( ); cout << “出列的人是” << getData ( ) << endl; //数m-1个人 Remove ( ); //删去 }

void main ( ) { CircList<int> clist; int n, m; cout << “输入游戏者人数和报数间隔 : ”; cin >> n >> m; for ( int i = 1; i <= n; i++ ) clist.insert (i); //形成约瑟夫环 clist.Josephus (n, m); //解决约瑟夫问题 }

问题的拓展 17世纪的法国数学家加斯帕《数目的游戏问题》 15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

双向链表 双向链表是指在前驱和后继方向上都能游历(遍历)的线性链表。 双向链表每个结点结构： 前驱方向   后继方向

通常采用带表头结点的循环链表形式 非空表 空表 结点指向 p→lLink→rLink？ =p =p p→rLink→lLink？

双向循环链表类的定义 template <class Type> class DblList; template <class Type> class DblNode { friend class DblList<Type>; private: Type data; //数据 DblNode<Type> *lLink, *rLink; //指针 DblNode ( Type value, //构造函数 DblNode<Type> *left, DblNode<Type> *right ) : data (value), lLink (left), rLink (right) { }

DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) { } }; template <class Type> class DblList { public: DblLIst ( Type uniqueVal ); ~DblList ( ); int Length ( ) const; int IsEmpty ( ) { return first→rlink == first; } int Search ( const Type & target ); Type getData ( ) const;

void Firster ( ) { current = first; } int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) { return current != NULL; } void Insert ( const Type & value ); void Remove ( ); private: DblNode<Type> *first, *current; };

双向循环链表的搜索算法 搜索成功 搜索不成功

template <class Type> int DblList<Type>:: Search( const Type & target ) { //在双向循环链表中搜索含target的结点， //搜索成功返回1，否则返回0。 DblNode<Type> *p = first→rLink; while ( p != first && p→data != target ) p = p→rLink; //循链搜索 if ( p != first ) { current = p; return 1; } return 0; }

双向循环链表的插入算法 双向循环链表的插入算法 (非空表) 双向循环链表的插入算法 (空表)

newnode->lLink = current; newnode->rLink = current->rLink; 双向循环链表的插入算法 (非空表) newnode first 31 48 15 后插入25 current 25 newnode->lLink = current; newnode->rLink = current->rLink; current->rLink = newnode; current = current->rLink; current->rLink->lLink = current;

newnode->lLink = current; newnode->rLink = current->rLink; 双向循环链表的插入算法 (空表) first first 25 current 后插入25 current newnode->lLink = current; newnode->rLink = current->rLink; current->rLink = newnode; current = current->rLink; current->rLink->lLink = current; ( = first ) ( first ->lLink = current )

template <class T> bool DblList<T>::Insert ( int i, const T& x, int d ) { //建立一个包含有值x的新结点, 并将其按 d 指定的 //方向插入到第i个结点之后。 DblNode<T, E> *current = Locate(i, d); //按d指示方向查找第i个结点 if ( current == NULL ) return false; //插入失败 DblNode<T,E> *newNd = new DblNode<T,E>(x); if (d == 0) { //前驱方向:插在第i个结点左侧 newNd->lLink = current->lLink; //链入lLink链 current->lLink = newNd; newNd->lLink->rLink = newNd; //链入rLink链 newNd->rLink = current; } else { //后继方向:插在第i个结点后面 newNd->rLink = current->rLink; //链入rLink链 current->rLink = newNd; newNd->rLink->lLink = newNd; //链入lLink链 newNd->lLink = current; } return true; //插入成功 };

双向循环链表的删除算法 双向循环链表的删除算法(删除后非空) 双向循环链表的删除算法(删除后为空)

双向循环链表的删除算法(删除后非空) 非空表 first 31 48 15 删除48 current first 31 15 current→rLink→lLink = current→lLink; current→lLink→rLink = current→rLink; 如果current指向31呢？

双向循环链表的删除算法(删除后为空) first first 31 删除31 current current current->rLink->lLink = current->lLink; current->lLink->rLink = current->rLink;

template <class T> bool DblList<T>::Remove( int i, const T& x, int d ) { //在双向循环链表中按d所指方向删除第i个结点。 DblNode<T> *current = Locate (i, d);//定位第i个结点 if (current == NULL) return false; //删除失败 current->rLink->lLink = current->lLink; current->lLink->rLink = current->rLink; //从lLink链和rLink链中摘下 x = current->data; delete current; //删除 return true; //删除成功 };

2.5 多项式 (Polynomial) n阶多项式 Pn(x) 有 n+1 项。 系数 a0, a1, a2, …, an 指数 0, 1, 2, …, n 按升幂排列

多项式(Polynomial)的抽象数据类型 class Polynomial { public: Polynomial ( ); //构造函数 int operator ! ( ); //判是否零多项式 float Coef ( int e); int LeadExp ( ); //返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); //求值 }

pl.degree = n; pl.coef[i] = ai, 0  i  n 多项式的存储表示 多项式的表示 第一种 :静态数组表示 private: int degree; float coef [maxDegree+1]; Polynomial pl; pl.degree = n; pl.coef[i] = ai, 0  i  n

Polynomial :: Polynomial (int sz) { degree = sz; 第二种:动态数组表示 private: int degree; float * coef; Polynomial :: Polynomial (int sz) { degree = sz; coef = new float [degree + 1]; } 以上两种存储表示适用于指数连续排列的多项式

a0 a1 a2 …… ai …… am coef e0 e1 e2 …… ei …… em exp 第三种:稀疏多项式 0 1 2 i m struct term { //多项式的项定义 float coef; //系数 int exp; //指数 }; static term termArray[maxTerms]; //项数组 static int free, maxTerms; //当前空闲位置指针 a0 a1 a2 …… ai …… am e0 e1 e2 …… ei …… em coef exp 0 1 2 i m

初始化： // term Polynomial::termArray[MaxTerms]; // int Polynomial::free = 0; class Polynomial { //多项式定义 public: …… private: int start, finish; //多项式始末位置 }

A(x) = 2.0x1000+1.8 例：两个多项式存放在termArray中 B(x) = 1.2 + 51.3x50 + 3.7x101 termArray

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

多项式(polynomial)类的链表定义 struct Term { int coef; int exp; Term ( int c, int e ) { coef = c; exp = e; } }; class Polynomial { List<Term> poly; friend Polynomial & operator + ( Polynomial &, Polynomial &); //加法

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

基本思想： pa和pb分别指示在两个多项式链表中当前检测到的结点；存放结果多项式链表的表头指针为CH，存放指针为pc 当pa和pb没有检测完各自的链表时，比较当前结点的指数域: (1)指数不等: 小者加入CH链，相应检测指针pa或pb进一； (2)指数相等:对应项系数相加。如相加结果不为零，则结果加入CH链，否则不加入，pa,pb进1； 当pa或pb中有一个已检测完自己的链表，把另一个链表的剩余部分加入到CH链中。

void Add(Polynomal& A, Polynomal& B, Polynomal& C) { //友元函数：两个带表头结点的按升幂排列的 //多项式链表的头指针分别是 A.first 和 B.first, //返回的是结果多项式链表 C. Term *pa, *pb, *pc, *p; float temp; pc = C.first; //结果链尾指针 pa = A.first->link; //A链检测指针 pb = B.first->link; //B链检测指针 while (pa != NULL && pb != NULL) if (pa->exp == pb->exp) { //对应项指数相等 temp = pa->coef + pb->coef; if ( fabs(temp) > 0.001) pc = pc->InsertAfter(temp, pa->exp); pa = pa->link; pb = pb->link; } else if (pa->exp < pb->exp) { //pa指数小 pc = pc->InsertAfter(pa->coef, pa->exp); pa = pa->link; } else { //pb指数小 pc = pc->InsertAfter(pb->coef, pb->exp); pb = pb->link; } p = (pa != NULL)? pa : pb; //p指示剩余链 while (p != NULL) { pc = pc->InsertAfter(p->coef, p->exp); p = p->link; };

ListNode<Term> *pa, *pb, *pc, *p; Polynomial & operator + ( Polynomial & ah, Polynomial & bh ) { //多项式加法, 结果由ah表头结点指示 ListNode<Term> *pa, *pb, *pc, *p; ListIterator<Term> Aiter ( ah.poly ); ListIterator<Term> Biter ( bh.poly ); //建立两个多项式对象 Aiter、Biter pa = pc = Aiter.First ( ); // ah 检测指针 pb = p = Biter.First ( ); // bh 检测指针 pa = Aiter.Next ( ); pb = Biter.Next ( ); // pa, pb 越过表头结点 delete p;//删去bh的表头结点

算法分析： 设两个多项式链表的长度分别为m和n,则总的数据比较次数为O(m+n)

都是从头遍历各个列表 总是选择两个列表头（pa,pb)的元素进行处理 指数相同/小于/大于 被加入的项都是指数较小的那个； 第一个while入口处： pa，pb都不为空； 所有pa,pb所指结点之前的项（指数较小的项）都已经被加入到C中了。 第一个while结束后： pa，pb中有null指针。如果有非null，那么p等于非NULL的指针。 第二个while把余下部分添加到C中。