目录 1.线性表的逻辑结构 2. 顺序表 3. 链表 单链表的存储结构 单链表的基本运算 循环链表 双链表.

Presentation on theme: "目录 1.线性表的逻辑结构 2. 顺序表 3. 链表 单链表的存储结构 单链表的基本运算 循环链表 双链表."— Presentation transcript:

1 目录 1.线性表的逻辑结构 2. 顺序表 3. 链表 单链表的存储结构 单链表的基本运算 循环链表 双链表

2 目录 (续) 4. 线性表的应用实例 顺序表的模板类定义及应用 单链表的模板类定义及应用 线性表在多项式运算中的应用 5. 小结

3 2.1 线性表的逻辑结构 2.1.1 线性表的基本概念 线性表是最基本、最常用的一种数据结构，它不仅有着广泛的应用，而且也是其它数据结构的基础。线性表的例子不胜枚举。例如，英文字母表（A, B, …, Z）是一个线性表，表中的每一个英文字母是一个数据元素，又如，一副扑克牌的点数也是一个线性表：（2, 3, 4, 5, 6, 7, 8, 9, 10 ,J, Q, K, A）。其中每一张牌的点数就是一个数据元素。在较为复杂的线性表中，数据元素可由若干数据项组成，如学生成绩表中，每个学生的成绩情况是一个数据元素，它由学号，姓名，各科成绩及平均成绩等数据项组成。

4 线性表（Linear List）是由n（n0）个具有相同属性的数据元素a1,a2,…,an组成的有限序列。
记作： （a 1，a 2，··· ，a i ，··· ，a n ） 这里的数据元素a i（1  i  n）只是一个抽象的符号，其具体含义在不同情况下是不同的。

5 从线性表的定义可以看出其特点是： •⑴ 同一性：线性表中的所有数据元素属于同一数据 对象； ⑵ 有穷性：线性表中的数据元素个数是有限的，其 数目就是表长； ⑶ 有序性：线性表中相邻的数据元素间存在着序偶 关系< ai , ai+1>

6 2.1.2 线性表的抽象数据类型定义 ADT LinearList{ Typedef struct List L;
InitList(L,maxSize); 说明：构造空表L，即表的初始化 ListLength(L); 说明：求表L的长度 isEmpty(L); 说明：判断表L是否为空表 isFull(L) ; 说明：判断表L是否已“满” GetNode (L,i,e); 说明：取表L中的第i个数据元素存入e

7   LocateNode(L,e); 说明：查找表L中值为e的数据元素 LocateNode(L,e,low,up); 说明：在表L的low-up范围内查找值为e的数据元素 InsertNode (L,e,i); 说明：在表L的第i个位置插入值为e的新数据元素 InsertNode (L,e); 说明：值为e的数据元素插入到有序表L，保持有序 DeleteNode (L,i ,e); 说明：删除表L中第i个数据元素，被删元素值存入e ClearList (L); 说明：将线性表L清空 } ; 

8 2.2 顺序表 2.2.1线性表的顺序存储结构 将一个线性表存储到计算机中，可以采用许多不同的方法，其中既简单又自然的是顺序存储方法：用一组地址连续的存储单元依它们的逻辑次序存储线性表的各个数据元素，称作线性表的顺序存储结构，简称为顺序表。

9 设线性表L = (a 1 , a 2 ,···, a n )，每个元素占用d个存储单元，则线性表中第i+1个元素a i+1的存储位置LOC(a i+1)和第i个元素a i的存储地址LOC(a i)之间满足关系： LOC(a i+1) = LOC(a i) + d 因此，表中第i个元素ai的存储位置可通过下式计算： LOC(a i) = LOC(a 1) + (i -1) * d 其中，LOC(a1)是第一个元素的地址称为基地址。

10 顺序表的特点是： 逻辑上相邻的元素其物理位置亦相邻。 2.2.2顺序表的基本运算 下面，我们先给出整数表的结构声明：
Typedef struct { int *elem; // 数据元素数组指针 int Size; // 线性表中当前元素数目 int maxSize; // 初始化操作中为线性表分配的单元数 }sqList;

11 在顺序表中，线性表的有些运算很容易实现。例如取第i个数据元素GetNode (L,i,e)和求表长ListLength(L)。以下主要讨论插入和删除两种运算。
⒈插入 线性表的插入运算是指：在表的第i (1  i  n+1)个位置上，插入新数据元素e，使长度为n的线性表： （a1 ,a2 , …, ai-1 , ai , …, an ） 变成长度为n+1的线性表： （a1 ,a2 , …, ai-1 , e , ai , …, an ）

12 分析： 线性表采用顺序存储结构时，由于数据元素的物理顺序必须和数据元素的逻辑顺序保持一致，因此我们必须将表中位置n ,n-1 ,…,i上的元素依次后移到位置n+1 ,n ,…,i+1上，腾出第i个位置，然后在该位置上插入新数据元素e，仅当插入位置i=n+1时，才无需移动数据元素，直接将e插入表尾。

13 bool InsertNode (sqList &L, int e, int i)
// 插入新元素e使其成为表L的第i个元素； // 若正常完成插入返回true，否则返回false。 { int j ; bool r = false; // 预置插入标志 if( i<1 || i>L.Size+1) // 非法插入位置 cout << " ERROR:invalid i !!\n"; else if(L.isFull()) // 表满 (溢出) cout << " ERROR: overflow !!\n"; else // 正常插入

14 注意元素后移的方向，必须从表中最后一个元素开始后移，直至将第i个元素后移为止。
{ for( j=L.Size; j>=i; j -- ) // 数据元素依次后移 L.elem[j]=L.elem[j-1]; L.elem[j]=e; // 插入新数据元素 L.Size++; // 表长增1 r = true; // 设置插入正常标志 } return r; 注意元素后移的方向，必须从表中最后一个元素开始后移，直至将第i个元素后移为止。

15 算法的时间复杂度分析： 问题的规模是表的长度L.Size，将其记为n ，显然该算法的时间主要花费在for循环中的元素后移语句上，该语句的循环执行次数(即移动元素的次数)是n-i+1。由此可见，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置i有关。 由于插入可能在表中任何位置上进行，因此需分析算法的平均性能。

16 令Eis(n)表示在长度为n的线性表中插入一个元素所需移动元素的期望值（即移动元素的平均次数），则
其中，pi表示在表中第i个位置上插入一个元素的概率；mi是在表中第i个位置上插入一个元素时所需移动元素的次数，那么mi = n-i+1。不失一般性，假设在表中任何有效位置（1  i  n+1）上插入元素的机会是均等的，即 p1=p2=…=pn+1=，因此，在等概率插入的情况下有：

17 即，在顺序表上做插入运算平均要移动表中的一半元素，当表长n较大时，算法的效率相当低，其平均时间复杂度是O(n)。
有时需要使得顺序表是有序的，即不指定插入位置，按元素值从小到大插入。

18 ⒉ 删除 （a1,a2,…,ai-1,ai,ai+1,…,an ） （a1,a2,…,ai-1,ai+1,…,an ）
线性表的删除运算是指将表的第i（1  i  n）个元素删去，使长度为n的线性表： （a1,a2,…,ai-1,ai,ai+1,…,an ） 变成长度为n-1的线性表： （a1,a2,…,ai-1,ai+1,…,an ）

19 分析： 和插入运算类似，在顺序表上实现删除运算也必须移动元素，才能反映出元素间逻辑关系的变化。若i == n，则只要简单地删除终端元素，不需移动元素；若1  i  n -1则必须将表中位置i+1,i+2,…,n上的元素依次前移到位置i ,i+1 , …, n-1上，以填补删除操作造成的空缺。

20 bool DeleteNode(sqList &L , int i , int &e)
// 删除L的第i个元素，被删元素值存入引用参数e ； // 若正常完成删除返回true，否则返回false。 { int j ; bool r = false; // 预置标志 if(i<1 || i>L.Size) // 非法删除位置 cout << " ERROR:invalid i !!\n"; else // 正常删除 { e=L.elem[i-1]; // 被删数据元素值放入e for(j=i; j<L.Size; j++) // 数据元素依次前移 L.elem[j-1]=L.elem[j]; L.Size --; // 表长减1

21 设表长L.Size记为n。元素前移语句的频度是n-i，因此元素的移动次数也是由表长n和位置i决定的。
r = true; // 设置删除正常标志 } return r; 算法的时间复杂度分析： 设表长L.Size记为n。元素前移语句的频度是n-i，因此元素的移动次数也是由表长n和位置i决定的。 若i==n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动元素；若i==1，则前移语句将循环执行n-1次，需移动表中除开始元素外的所有元素。这两种情况下算法的时间复杂度分别是O(1)和O(n)。

22 即，顺序表的删除与插入类似，约需移动一半元素，其平均时间复杂度也是O(n)。
令Ede(n)表示在长度为n的线性表中删除一个元素所需移动元素的平均次数，则 其中，q i表示删除表中第i个元素的概率；n i是删除表中第i个元素时所需要移动元素的次数，即n i = n-i，在等概率的假设下 q1=q2=…qn=，因此得到 即，顺序表的删除与插入类似，约需移动一半元素，其平均时间复杂度也是O(n)。

23 ⒊ 查找 线性表的查找操作可分为： 按序号查找GetNode (L, i,e) 和 按内容查找LocateNode(L, e)两种。 当然，还可以不在整个表查找元素e，只在给定low-up区间查找值为e的元素。 下面给出按内容查找的算法描述：

24 int LocateNode(sqList &L,int e)
// 查找表L中值为e的数据元素; // 返回值为-1表示没找到，否则是被查找结点的序号 { int i=0; while( i<L.Size && L.elem[i]!= e )i++; if(i< L.Size) return i+1; else return -1; }

25 ⒋ 顺序表的应用例 【例2.1】设表la和lb分别表示整数集合A和B， 且用数组存储，求：A=A∪B。 算法思路：集合中的元素是无重复的，可将Lb表中的元素从表尾起逐个删除，并在La表查找被删元素b，若找不到，则将元素b插入La表，否则不必插入，完成后集合B为空。

26 bool SetUnion(sqList &la,sqList &lb)
{ int b, n, i; bool k, r=true ; n=Lb.Size; // Lb表的初始长度存入n for(i=n; i>0 && r ; i--) // 从Lb表中逐次删除表尾元素，这样不必移动元素 { r=DeleteNode(Lb, i, b); // 调用删除算法，被删元素存入b k=LocateNode(La, b); // 在La表中查找b if(!k) r=InsertNode(La, b, La.Size+1); // La表中找不到元素b，则插入至la表尾 } // end_for return r; }

27 算法分析：由于要从Lb表中逐次删除表尾元素，则for循环执行Lb
算法分析：由于要从Lb表中逐次删除表尾元素，则for循环执行Lb.Size次，循环体中的尾删除和尾插入不需移动元素，但LocateNode(La, b) 的时间复杂度为La.Size，因此SetUnion的时间复杂度为：O(La.Size*Lb.Size)。 【例2.2】设整数表La和Lb采用顺序结构存储，且表中的整数均按值非递减有序排列，现要求由La和Lb归并产生一个新的整数表Lc，要求Lc中的数仍按值非递减有序排列。

28 算法思路：由题意可知，Lc中的数据元素或是La中的数据元素，或是Lb中的数据元素，那么只要先设Lc为空表，然后将La或Lb中的元素逐个插入到Lc中即可。为使Lc中元素按值非递减有序排列，可设两个指针i和j分别指向La和Lb中某个元素，假设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到LC中的元素c为： a 当a ≤ b 时 c = b 当 a > b时

29 显然，指针i和j的初值均为1，在所指元素插入Lc之后，在La或Lb中顺序后移。
Bool Merge(sqList& Lc,sqList& La,sqList& Lb) // 由La和Lb归并产生新的整数表Lc，La和Lb保持不变。 { int i=1, j=1, m=La.Size, n=Lb.Size; int a, b; bool r=true; GetNode(La,i,a); // 取La表指针i所指元素存入a GetNode(Lb,j,b); // 取Lb表指针j所指元素存入b while(i<=m && j<=n && r) // La和Lb表均没到表尾且插入Lc正常则进入循环体

30 if(a<=b) // La 表所指元素较小，将其插入 Lc 表，指针I 后移
{ r=InsertNode(Lc,a, Lc.Size+1); GetNode(La,++i,a); } else // Lb表所指元素较小，将其插入Lc表，指针j后移 { r=InsertNode(Lc,b, Lc.Size+1); GetNode(Lb,++j,b); // 下面两个while循环有且仅有一个被执行 while(i<=m) // 将La表中剩余元素插入Lc { GetNode(La,i++,a); r=InsertNode(Lc,a,Lc.Size+1);

31 while(j<=n) // 将Lb表中剩余元素插入Lc
{ GetNode(Lb,j++,b); r=InsertNode(Lc,b,Lc.Size+1) ; } return r ; 算法分析：由于La和Lb是有序表，每次插入Lc表的是La或Lb 的一个元素，采取尾插入，不必移动元素，故Merge时间复杂度为：O(La.Size+Lb.Size)。

32 ⒌ 小结 由顺序表的特点可知，线性表采用顺序存储有如下的优缺点。 优点： ⑴ 不需为表示元素间的逻辑关系而增加额外的存储 空间；
⑵ 可以方便地随机存取表中的任一结点。

33 缺点： ⑴ 插入和删除运算不方便，除表尾的位置外，在表 的其它位置上进行插入和删除操作都必须移动大 量的元素，因此效率较低； ⑵ 由于顺序表要求占用连续的存储空间，这样只能 在创建时进行分配，因此当表长变化较大时，难以 确定合适的存储规模，若按可能达到的最大长度预 先分配表空间，则可能造成一部分空间长期闲置而 得不到充分利用，若事先对表长估计不足，则插入 操作可能使表长超过预先分配的空间而造成溢出。

34 2.3 链表 2.3.1 线性表的链式存储结构 线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是不连续的），对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，我们把这种存储单元称为结点。根据链接方式的不同，链表又可分为单链表、循环链表、双链表等。

35 2.3.2 单链表 链表中仅只包含一个指针域用来存放直接后继(或直接前驱)结点的地址称做单链表。图2.2所示为单链表的结点结构。
头指针：由于单链表中每个结点的存储地址是存放在其前驱结点的指针域中，而第一个结点没有前驱结点，因而要专门设立一个指向首元结点的指针Head，通常称之为头指针

36 图2.3所示为线性表（Zhao，Qian，Sun，Li，Zhou，Wu，Zheng，Wang）的单链表存储结构。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。如图2.3的单链表可按照其逻辑顺序画成如图2.4所示的形式，这是因为在使用链表时，关心的只是它所表示的单表中数据元素之间的逻辑顺序，而不关心每个数据元素在存储器中的实际位置。

37 由上可见，单链表可由头指针唯一确定，假设p是指向线性表中第i个数据元素(结点ai)的指针，则p->next是指向第i+1个数据元素(结点ai+1)的指针。换句话说，若p->data=ai，则p->next->data=ai+1。由于结点的逻辑顺序与物理顺序可以不一致，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。 为了操作方便，我们经常在单链表的首元结点(第一个结点)之前附设一个结点，称之为头结点。头结点的数据域不存储任何信息，头结点的指针域存储指向首元结点的指针。

38

39 2.3.3 单链表的基本运算 我们仍然先以整数表为例，讨论单链表的算法，定义单链表的结点结构如下： 我们定义单链表结构为：
单链表的基本运算 我们仍然先以整数表为例，讨论单链表的算法，定义单链表的结点结构如下： typedef struct Node { int data; // 数据元素(数据域) struct Node *next; // 指向后继的指针(指针域） } Node; 我们定义单链表结构为：

40 假设我们要在单链表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。如图2.7(a)所示。
typedef struct { Node *Head; // 链表头指针 int Size; // 链表当前长度（结点数） } LinkedList; “插入”和“删除” 假设我们要在单链表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。如图2.7(a)所示。 图2.8所示为在单链表中删除a和c之间的元素b时结点间逻辑关系的变化。

41 假设s为指向结点x的指针，则上述指针修改用语句描述即为：s ->next = p->next ;
p ->next = s ;

42 假设p为指向结点a的指针，则修改指针用语句描述为：p -> next = p -> next -> next ;
结论：在单链表中插入和删除一个结点时，仅需修改指针而不需要移动元素。

43 ⒈插入 ⑴ 无头结点的单链表中的插入 bool InsertNode (LinkedList&L, int x, int i )
// 无头结点的单链表中插入值为x的结点，成为表L的第i个元素 { Node *p,*s ; if (i<1 || i>L.Size+1) return false; // 参数i无效，无法插入 s=new Node; s->data=x; // 建立插入结点 if(i==1) // 插入首元结点 { s->next=L.Head; // 原首元成为新插入结点的后继结点 L.Head=s; // 新插入结点成为首元结点 }

44 else // i > 1 && i <= L.Size + 1
{ p=L.Head; // p指向首元结点 for(int j=1; j<i-1; j++) p=p->next; // 寻访第i-1个结点 s->next=p->next; // 新结点为第i-1个结点的后继 p->next=s; // 原第i个结点作为新插入结点的后继 } L.Size++; // 表长增1 return true; // 返回插入操作正常完成标志

45 在算法中，我们对参数i ==1进行了特殊处理，原因是首元结点的位置是存放在头指针中，而其余结点的位置是在其前趋结点的指针域中，二者表示不一致。如果对i ==1不做判断，直接执行for语句，将会把新结点插入成链表的第2个结点。通过设置头结点，可以避免特殊处理，其原因有二： ①由于首元结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无需进行特殊处理；②无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。

46 ⑵ 带头结点的单链表中的插入 bool InsertNode (LinkedList&L, int x, int i )
⑵ 带头结点的单链表中的插入 bool InsertNode (LinkedList&L, int x, int i ) //带头结点的单链表中插入值为x的结点，成为表L的第i个元素 { Node *p,*s ; if (i<1 || i>L.Size+1) return false; // 参数i无效，无法插入 p=L.Head; // p指向头结点 for(int j=0; j<i-1; j++) p=p->next; // 寻访第i-1个结点 s=new Node; s->data=x; // 建立插入结点 s->next=p->next; // 新结点为第i-1个结点的后继 p->next=s; // 原第i个结点作为新插入结点的后继 L.Size++; // 表长增1 return true; // 返回插入操作正常完成标志 }

47 算法分析：显然，插入算法的时间主要耗费在寻访第i-1个结点，算法的平均时间复杂度仍然是O(n)，似乎和顺序表相同，但是由于单链表的插入只是顺链移动指针并不移动元素，这对于数据元素占用单元很多的表来说，实际时间耗费要少得多。

48 ⒉ 删除 带头结点的单链表的删除算法 bool DeleteNode(LinkedList&L, int i, int &x )
// 删除单链表L的第i个数据元素，被删元素值存入引用参数x { if(i<1 || i>L.Size) return false; // 参数i无效，无法删除 int j=0; Node *q,*p=L.Head; // p指向头结点 for(j=0; j<i-1; j++) p=p->next; // 寻访第i-1个结点 q=p->next; // 令q指向被删结点 p->next=q->next; // 修改第i-1个结点的后继结点 x=q->data; // 被删结点值放入x delete q; // 释放被删除结点所占空间 L.Size--; // 表长减 1 return true; // 返回删除操作正常完成标志 }

49 算法分析：删除算法的时间复杂度分析与插入算法的时间复杂度分析相同。
⒊ 查找 在单链表中，由于结点的逻辑顺序与物理顺序可以不一致，因此GetNode (L,i,e)算法必须从头指针出发寻找，其实就是上面插入算法中的寻访第i-1个结点的方法。

50 按内容查找LocateNode(L, e)算法
int LocateNode LinkedList& L ,int e) // 查找值为e的元素；返回该元素在表中的序号， 返回-1表示没找到。 { Node *p ; int j=1; p=L.Head->next; // p指向首元结点 // 如果不带头结点则此语句是： p = L.Head; while(p && p->data!=e) j++, p=p->next ; if(p) return j; else return -1; }

51 ⒋ 创建单链表 为了测试实现单链表基本运算的算法，必须批量输入数据建立起单链表，当然是通过调用插入算法建立单链表，但还根据插入新结点位置的不同，有“头插入”法和“尾插入”法。 “头插入”法：每输入一个元素，总将其插入至La表头，即插入位置参数i ==1，这样插入算法中的寻访第i-1个结点的for循环体一次都不被执行，只是建立的表中元素链接顺序与输入元素的顺序相反； “尾插入”法：设立一个尾指针（指示尾结点），初始时（空表）指向头结点，建表中，每次将元素插入至尾结点之后，再将尾指针移动到新插入结点。

52 如果是建立有序表，则应反复调用InsertNode ( LinkedList& L , int x)函数，从“空”表起，逐个插入元素，为了保持有序，该算法是根据元素值经比较插入的。
“头插入”法建立单链表的算法： #define endMark // 设定输入结束标志 void CrtLinkList(LinkedList& L) // 用"头插入"法建立带头结点的单链表L { int x ; // 以下为La表初始化（建立头结点，表长置0） L.Head=new Node; L.Head->next=NULL; L.Size=0;

53 cout<<"Please input integer Create List ";
cout<<"input " << endMark << " end! \n"; // 输出提示信息 cin>>x; // 输入L表的第一个元素 while(x!=endMark) { InsertNode(L,x,1); // 插入到表头 cin>>x; // 输入L表的其余元素 }

54 ⒌ 单链表的应用例 【例2.3】 求整数集合A = (A-B)∪(B-A)
算法思路：分别用带头结点的单链表La、Lb表示集合A和B，用for循环逐个从Lb表中取元素存入x中，在La表中查找x，若找到，则x∈A∩B，将x从La表删除；否则x∈B－A，将x插入La表，for循环结束算法完成；此时La表代表所求的(A-B) ∪(B-A)集合，Lb保持不变。

55 void Symm_diff(LinkedList& La, LinkedList& Lb)
{ int x, i; Node *p; p=Lb.Head->next; // p 指向Lb表的首元结点 for(int j=1; j<=Lb.Size; j++) // 顺Lb表逐结点检查 { x=p->data; // 取p 指针所指结点值存入x i=LocateNode(La,x); // 检查x是否在La表中 if(i==-1) InsertNode(La,x,1); // x 不在表中，插入 else DeleteNode(La, i, x); // x 在表中，删除之 p=p->next; }

56 2.3.4循环链表（circular linked list）
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其它结点。图2.9所示为单链的循环链表。类似地，还可以有多重链的循环链表。

57 循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
有时，若在循环链表中设立尾指针而不设头指针（如图2.10 (a)所示），可使某些操作简化。例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相连接。当线性表以图2.10(a)的循环链表作存储结构时，此操作仅需改变两个指针值即可，运算时间为O(1)。合并后的表如图2.10 (b)所示。

58

59 2.3.5双链表(double linked list)
我们前面讨论的链式存储结构的结点中只有一个指示直接后继的指针域，因此，从某个结点出发只能顺指针往后寻查其它结点。若要寻查结点的直接前趋，则需从表头指针出发，遍历整个链表。为了克服单链表这种单向性的缺点，可利用双链表。 在双链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋，其结点结构如图2.11所示。

60 和单循环链表类似，双链表也可以有循环表，如图2.12所示，链表中存在两个环。
在双链表中，若d为指向表中某一结点的指针，则显然有：d -> next -> prior =d -> prior -> next =d;

61 在双链表中，有些操作如： GetNode(L,i,e)，LocateNode(L,x)等算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双链表中需同时修改两个方向上的指针，图2.13和图2.14分别显示了删除和插入结点时指针修改的情况。

62 假设指针p指向数据域为a的结点，则插入时修改指针的语句是：
s->next=p->next; q = p ->next ; s->proir=p; p ->next = q ->next ; s->next->prior=s;

63 删除时修改指针的语句是： q ->next ->prior =q->prior ; p->next=s; delete q ;

64 2. 4 线性表的应用实例 2.4.1顺序表模板类定义及应用 #include <iostream.h>
template <class T> // 模板声明 , T是类参数(可变类型, 在声明顺序表对象时被具体化) class sqList { protected: T *elem; // elem是存放线性表数据元素的数组指针 int Size; // 顺序表的当前长度(元素数目) int MaxSize; // 顺序表的最大长度（容量）

65 public: sqList(int ms=10); // 构造函数 sqList(const sqList<T>&); // 复制构造函数 ~sqList() { delete [] elem; } // 析构函数 sqList& operator=(const sqList<T>&); // "="运算符重载 bool isEmpty() { return Size==0; } // 判断顺序表是否为空表 bool isFull() { return Size==MaxSize; } // 判断顺序表是否已“满” int Length() { return Size; } // 求顺序表的长度

66 bool GetNode(int index, T& e);
// 取表中第index个数据元素存入e int LocateNode(T e); // 查找值为e的元素 int LocateNode(T e, int low, int up); // 在给定范围low-up内查找值为e的元素 bool InsertNode( T e, int index); // 插入数据元素e, index是插入位置 bool InsertNode(T e); // 按元素值e的大小插入有序表 bool DeleteNode(int index,T& e); // 删除序号index的元素并存入e void traverse(char); // 遍历顺序表 }; // 结束类接口定义

67 template<class T>void visitNodeData(T); // 遍历表中要调用的输出数据域的函数
// 以下为类实现部分 template <class T>sqList<T>::sqList(int ms) // 构造函数, 申请顺序表存储空间，当前表长初始化为0 { if(ms<=0) { cout<<"ERROR:invalid MaxSize!!\n"; return; } elem=new T[ms]; MaxSize=ms ; Size=0 ;

68 template <class T> sqList<T>:: sqList (const
sqList<T>& obj) // 由顺序表obj复制构造当前对象 { MaxSize=obj.MaxSize; Size=obj.Size; // 表容量、表长赋为obj相应值 elem=new T[MaxSize]; // 为当前对象申请存放元素的存储空间 for(int j=0; j<Size; j++) elem[j] = obj.elem[j]; // 复制obj的数据元素 }

69 template <class T>sqList<T>::sqList
operator=(const sqList<T>&origin) // "="运算符重载 { if(MaxSize!=origin.MaxSize) // 当前表与origin表容量不等 { delete[ ] elem; // 释放原来的存放数据元素空间 elem=new T[MaxSize]; // 重新为当前对象申请空间 } MaxSize=origin.MaxSize; // 当前表容量赋值为origin表容量 Size=origin.Size; // 当前表长赋值为origin表长 for(int j=0; j<Size; j++) elem[j]=origin.elem[j] ; // 复制数据元素

70 template <class T>bool sqList<T>:: GetNode(int index, T& e)
// 取表中第index个数据元素存入e { if (index<1||index>Size) return false; e=elem[index-1]; return true; } template <class T>int sqList<T>:: LocateNode(T e) // 查找到值为e的元素返回元素序号，否则返回 -1 { int i=0 ; while(i<Size && elem[i]!=e ) i++; if(i<Size) return i+1; else return -1;

71 template <class T>int sqList<T>::LocateNode
(T e, int low, int up) // 在low-up间查找值为e的元素 // 返回-1表示被查元素不存在，否则是被查元素的序号 { int i =low –1 ; while( i<up && elem[i]!=e ) i++; if(i < up) return i+1; else return –1 ; } template <class T>bool sqList<T>::InsertNode( T e, int index ) // 插入元素e, index是插入位置 { int j; bool r=false ; if (index<1 || index>Size+1) // 非法插入位置 cout<<"ERROR:invalid index!!\n"; else

72 if( isFull( ) ) // 表满（溢出）
cout<<"ERROR: overflow !!"; else { for(j=Size; j>=index; j--)elem[j]=elem[j-1]; // 元素依次后移 elem[j]=e; Size++; // 插入数据元素, 表长增1 r=true; // 设置插入正常标志 } return r;

73 template <class T>int sqList<T>::InsertNode(T e)
{ int j; if(isFull()) // 返回，表溢出无法插入 {cout<<"ERROR: overflow !!"; return false; } for(j=Size; j>0; j--) // 边查找应插入位置边移动元素 if(elem[j-1]>e) elem[j]=elem[j-1]; else break; elem[j]=e; // 插入新数据元素 Size++; // 表长增1 return true; // 返回插入正常标志 }

74 template <class T>int sqList<T>::DeleteNode(int
index, T& e) // 删除序号为index的元素 被删元素存入e { int j; bool r=false; if (index<1 || index>Size) // 非法删除位置 cout<<"ERROR:invalid index!!\n"; else { e=elem[index-1]; // 被删数据元素值放入e for(j=index; j<Size; j++) elem[j-1]=elem[j]; // 数据元素依次前移 Size--; r=true; //表长减1, 设置删除正常标志 } return r;

75 template <class T>void sqList<T>::traverse
(char endchar) // 遍历顺序表 (endchar是表结束符) { for(int i=0; i<Size; i++) visitNodeData(elem[i]); cout<<endchar<<"\n Length="<<Size<<"\n"; } 用顺序表的模板类定义重新实现§2.2的例2.1（设表la和lb分别表示两个整数集合A和B，求：A=A∪B）的算法SetUnion及有关函数代码如下：

76 #include <stdlib.h>
#include <time.h> #include "SQList.h" void CrtSetList( sqList<int>&, int ); // 原型声明 产生若干互不相等的整数插入表 bool SetUnion( sqList<int>&, sqList<int>& ); // 集合“并”运算的原型声明 void main() { // 声明sqList对象La, Lb, 类参数T用<int>实例化 sqList<int> La(40),Lb(20); // La ,Lb容量分别为40、20 int s1, s2; // s1, s2是存放La,Lb大小的变量 time_t t;   srand((unsigned)time(&t)); //初始化随机数种子

77 cout<<"Please input Size of SetA && SetB =? =? (<=20)";
cin>>s1>>s2; // 输入A,B元素数<=20， 以保证"并"后La的元素数<=40 cout<<"\nSet A = { "; // 输出集合A的名称 CrtSetList(La,s1); // 为集合A产生s1个互不相等的整数插入并输出集合元素 cout<<"}\nSet B = { "; // 输出集合B的名称 CrtSetList(Lb,s2); // 为集合B产生s2个互不相等的整数插入并输出集合元素 if(SetUnion(La,Lb)) // 求集合A与集合B的“并” 若正常返回则输出结果 { cout<<"}\n\n A Union B = { "; La.traverse( ')' }; }

78 void visitNodeData(int d) // 输出数据域（集合元素值）
{ cout<<d<<" "; } void CrtSetList(sqList<int>&L,int n) // 为集合产生n个互不相等的整数插入顺序表 { int x,i,j; for(i=0; i<n; i++) // 产生n个集合元素, 不得重复 { do { x=rand() % 37; } // 产生0-36间的随机整数 while((j=L.LocateNode(x))!=-1); // 在集合中找x , 找不到则脱离循环 L.InsertNode(x,L.Length()+1); cout<< x << " "; // 输出x (集合元素边产生边输出) }

79 bool SetUnion(sqList<int>&La, sqList<int>&Lb)
{ int m,n,i,k,b; bool r = true; n=Lb.Length(); m=La.Length(); // Lb、 La的初始长度分别存入n m, 检查B集合元素是否∈A时范围小 for(i=n; i>0 && r; i--) // 从Lb表中逐次删除素尾元素不必移动元素 { Lb.DeleteNode(i,b); // 删除Lb表的元素，被删元素存入b k=La.LocateNode(b,1,m); // 在La表原来的范围内找b，不必考虑新插入的元素 if(k==-1) // La表中找不到元素b r=La.InsertNode(b,La.Length()+1); // 插入至la表尾 } //end_for return r; // 返回操作是否正常完成 }

80 2.4.2 单链表模板类定义及应用 下面我们首先定义单链表结点结构，然后定义单链表类 #include <iostream.h>
template <class T> struct Node // 定义单链表结点结构 // 模板T是类参数(可变类型, 在声明单链表对象时被具体化) { T data; // 数据元素（数据域） Node <T> *next; // 指向直接后继的指针（指针域） };

81 template <class T> class LinkedList // 定义单链表类
{ protected: Node <T> *Head; // 单链表头指针 int Size; // 单链中元素数 public: LinkedList(); // 构造函数 LinkedList(const LinkedList<T> &); // 复制构造函数 ~LinkedList(); // 析构函数 LinkedList& operator=(const LinkedList<T>&); // "=" 运算符重载 bool isEmpty(){ return Size==0; } // 判断单链表是否为“空” bool isFull(); // 判断单链表是否已"满", 无用户空间

82 int Length(){ return Size; } // 求链表的长度 bool GetNode(int, T&); // 取数据元素
bool InsertNode(T, int); // 插入数据元素 bool InsertNode(T e); // 按元素值e的大小插入有序表 bool DeleteNode(int,T&); // 删除数据元素 int LocateNode(T e); // 查找数据元素 int LocateNode(T e, int, int); // 在给定范围内查找值为e的元素 void traverse(char endchar); // 遍历单链表 friend void Poly_Add (LinkedList<T>&, LinkedList<T>&); // 多项式求和友元函数, 可访问单链表类的私有成员 }; // 结束类接口定义

83 template<class T>void visitNodeData(T); // 遍历表中要调用的输出数据域的函数
// 以下为类实现部分 template <class T>LinkedList<T>::LinkedList() // 构造“空”单链表 { Head=new Node<T>; // 用头指针申请头结点(无头结点则Head=NULL;) Head->next=NULL; Size=0; }

84 template<class T>LinkedList<T> :: LinkedList ( const
LinkedList<T> &obj ) // 由单链表obj复制构造当前单链表对象 { Node<T> *q, *p=obj.Head->next; // p指向obj的首元结点 Head=new Node<T>; // 用头指针申请头结点空间 q=Head; // q初始指向头结点 while(p) { q->next=new Node; // 用q->next申请结点空间 q=q->next; // q移动到新申请结点 q->data=p->data; // 复制结点数据 p=p->next; // p顺链前进到obj的下一结点 } q->next=NULL; Size=obj.Size;

85 template<class T>LinkedList<T>::~LinkedList()
// 析构函数 { Node<T> *q,*p=Head; // p指向头结点 do{ q=p->next; // q指向p的后继结点 delete p; // 释放p所指结点空间 p=q; // p指向下一待释放空间的结点 } while(p); } template <class T> LinkedList<T>& LinkedList<T>:: operator=(const LinkedList<T>& origin) // “=” 重载 { Node<T> *q, *s, *p = origin.Head; // p指向origin表的头结点

86 q=Head; // q指向当前表(*this)的头结点 while(p->next && q->next)
// 将origin表结点数据赋给当前表结点 { q=q->next; p=p->next; // p,q分别顺链前进 q->data=p->data; // 数据域赋值 } if(q->next) // 当前表比origin表长，需释放其余结点空间 { p=q->next; // p指向第一个要释放结点 do{ s=p->next; // s指向p的后继结点 delete p; // 释放p所指结点空间 p=s; // p指向下一待释放空间结点 }while(p); } // 注意上面的操作中q指针没有移动

87 while(p->next) //origin表更长，申请结点空间复制剩余结点
else while(p->next) //origin表更长，申请结点空间复制剩余结点 { q->next=new Node<T>; // 用q->next申请结点空间 p=p->next; // p顺链前进到源结点 q=q->next; // q 移动到新申请结点 q->data=p->data; // 数据域赋值 } // end_if q->next=NULL; // q指向当前表尾结点，其next域赋空指针 Size=origin.Size; // 当前表长赋值为origin表长 return *this; // 返回当前单链表对象 }

88 template<class T>bool LinkedList<T>::isFull()
// 试着申请结点空间 捕获到异常则无可用的用户空间 { Node<T> *p; try{ p = new Node<T>; } catch(...) {return true;} // 俘获异常，返回表“满”标志 delete p; // 释放刚刚申请的结点空间 return false; // 返回表“未满”标志 }

89 template<class T>bool LinkedList<T>::
GetNode(int i, T& e) // 取第i个数据元素存入e { if (i<1 || i>Size) // 参数i无效，无法取得数据元素 return false; Node<T> *p=Head->next; // p指向首元结点 for(int j=1; j<i; j++) p=p->next; // 顺链找第i个结点 e=p->data; return true; }

90 template<class T>bool LinkedList<T>::InsertNode(
T x, int i) // 插入结点x，使其成为表的第i个元素 { if(i<1 || i>Size+1) // 参数i无效，无法插入 { cout<<"ERROR: invalid i !!"; return false; } if(isFull()) // 无可用的用户空间 { cout<<"ERROR: overflow !!"; return false; } Node<T> *s, *p=Head; // p指向头结点 for(int j=0; j<i-1; j++) p=p->next; // 寻第i-1个结点 s=new Node<T>; s->data=x; // 建立插入结点 s->next=p->next; // 新插入结点作为第i-1个结点的后继 p->next=s; // 原第i个结点作为新插入结点的后继 Size++; return true; // 表长增1, 插入操作正常完成 }

91 template<class T>bool LinkedList<T>::InsertNode(T x)
{ if(isFull()) // 无可用的用户空间 { cout<<"ERROR: overflow !!"; return false; } Node<T> *s, *p=Head; // p指向头结点 while(p->next && x>p->next->data) p=p->next; // 找插入结点的前趋 s=new Node<T>; s->data=x; // 建立插入结点 s->next=p->next; // 新插入结点作为第i-1个结点的后继 p->next=s; // 原第i个结点作为新插入结点的后继 Size++; return true; // 表长增1, 插入操作正常完成 }

92 template<class T>bool LinkedList<T>::
DeleteNode(int i,T &e) // 删除带头结点的单链表的第i个数据元素，被删元素值存入引用参数x { if(i<1 || i>Size) return false; // 参数i无效，无法删除 int j=0; Node<T> *q,*p=Head; // p指向头结点 for(j=0; j<i-1; j++) p=p->next; // 寻访第i-1个结点 q=p->next; // 令q指向被删除结点 p->next=q->next; // 第i-1个结点的后继改为原第i个结点后继 e=q->data; // 被删结点值放入x delete q; // 释放被删除结点所占空间 Size--; return true; // 表长减1, 删除操作正常完成 }

93 template<class T>bool LinkedList<T>::LocateNode(T e)
{ int j=1; Node<T> *p=Head->next; // p指向首元结点 while(p && p->data!=e ) j++, p =p ->next ; if(p) return j ; else return –1 ; } template<class T>int LinkedList<T>::LocateNode (T e,int low, int up) //在范围low-up间找值为e的元素,返回-1为没找到，否则是被查元素的序号 { int j =1 ; Node<T> *p = Head->next; // p指向首元结点 while(p && j<low ) j++, p = p->next; // 找第low个结点

94 while(p && j<=up && p ->data!=e)
j++, p =p ->next; // 在结点low-up间查找e if(p && j <= up ) return j; else return –1; } template<class T>void LinkedList<T>::traverse (char endchar) //遍历单链表 { Node<T> *p=Head->next; while(p) { visitNodeData(p->data) ; p =p->next ; } cout<< endchar<< "\nLength="<<Size<<"\n"; // endchar是表结束符

95 用带头结点的单链表的模板类定义重新实现§2. 3的例2
用带头结点的单链表的模板类定义重新实现§2.3的例2.3（求集合A、B的对称差存入集合A），以及利用其它一些基本运算完成以单链表存储的整数集的集合运算∪、∩的函数如下： #include "SLList.h" void Symm_diff(LinkedList<int>&, LinkedList<int>&); // 求以单链表存储的两个集合“对称差”之原型声明 void CrtLinkList(LinkedList<int>&, int ); // 为集合产生若干互不相等的整数插入链表的原型声明 bool SetUnion(LinkedList<int>&La,LinkedList<int>&Lb); // 求以单链表存储的集合A、B的“并”(A∪B) 的原型声明

96 void main() { LinkedList<int> La, Lb,Lc; // 用<int>实例化单链表对象 int s1, s2; // s1, s2是存放La,Lb大小的变量 time_t t; srand((unsigned)time(&t)); // 初始化随时间变化的随机数种子 cout<<"Please input Size of SetA && SetB =? =? "; cin>>s1>>s2; // 输入集合A,B元素数 cout<<"\nSet A = { "; // 输出集合A的名称 CrtLinkList(La,s1); // 产生集合A的s1个集合成员并输出之 cout<<"}\n Length="<<s1<<"\n\nSet B = { "; // 输出A的成员数、集合B的名称 CrtLinkList(Lb,s2); // 产生集合B的s2个集合成员并输出之 Lc = La; // 用重载的"="运算符将La表赋给Lc表

97 cout<<" }\nLength="<<s2<<"\n\n(A-B)Union(B-A)={ ";
Symm_diff (La,Lb); // 求La表与Lb表的对称差，结果在La表 La.traverse(‘)’); // 输出A B所得到的结果表 成员数 cout<<"\nAUnionB={ "; SetUnion(Lc, Lb); // 求Lc表与Lb表的“并”，结果在Lc表 Lc.traverse(')'); // 输出A∪B所得到的结果表、成员数 cout<<"\nAIntersectionB = { "; Symm_diff(Lc,La); // 求Lc与La表的对称差， // 相当于求(A∪B)  ( A B) A∩B Lc.traverse(')'); // 输出A∩B所得到的结果表、成员数 }

98 void Symm_diff (LinkedList<int>& La,
LinkedList<int>& Lb) // 求以单链表La、Lb存储的集合A、B的对称差 { int x, i, count=0; // 记录Lb表中元素插入到La表中的个数 for(int j=1; j<=Lb.Length(); j++) { Lb.GetNode(j , x); // 取Lb表中元素存入x i=La.LocateNode(x, 1+count, La.Length()); // 由于集合B不在集合A中的元素插入到了La表头,因此只在A // 原来的元素中1+count~ La.Length() 范围内找即可。 if(i==-1) count++, La.InsertNode(x, 1); // 找不到x，计数并插入A集合 else La.DeleteNode(i,x); // 找到x，则删除之 } // end_for }

99 void CrtLinkList(LinkedList<int>& L,int n)
// 为链表L产生n个互不相等的整数插入表头 { int x, i, j; for(i=0; i<n; i++) // 产生n个集合元素, 不得重复 { do x=rand() % 37; // 产生0-36间的随机整数 while((j=L.LocateNode(x))!=-1); // 在集合中找x, 找不到则脱离循环（要求各元素值不等） L.InsertNode(x,1); //插入表头 cout<<x<<" "; // 输出x (集合元素边产生边输出) }

100 bool SetUnion(LinkedList<int>&La,
LinkedList<int>&Lb) // 将La表和Lb表所表示的集合做"并"，存入La表，Lb表被清空 { int m,n,i,k,b; bool r=true; n=Lb.Length(); // Lb表的初始长度存入n, 删除长度将减小 m=La.Length(); // La表的初始长度存入m, 检查范围1-m for(i=n; i>0 && r; i--) // 从Lb表中删除素尾元素 { Lb.DeleteNode(i,b); // 调用删除算法 k=La.LocateNode(b,1,m); // 调用查找算法 if(k==-1) r=La.InsertNode(b,La.Length()+1); // 找不到b则插入至la表尾 } //end_for return r; }

101 2.4.3线性表在多项式运算中的应用 在表处理中，常常要用到对符号多项式的处理。在数学上，一个一元多项式 可按升幂写成：
在表处理中，常常要用到对符号多项式的处理。在数学上，一个一元多项式 可按升幂写成： 该多项式是由n+l个系数唯一确定。因此，在计算机里，它可用一个线性表P来表示 其中每一项的指数i隐含在其系数pi的序号里。

102 设Qm(x) 是一元m次多项式，可用线性表Q来表示：
不失一般性，设m<n，则两个多项式相加的结果 可用线性表表示：

103 我们可以对P、Q和R采用顺序存储结构，也可以采用链表存储结构。使用顺序存储结构可以使多项式相加的算法十分简单。但是，当多项式中存在大量的零系数时（称这种多项式为稀疏多项式），顺序存储表示方式就会浪费大量存储空间。例如：多项式S30000(x)为： S(x) = 1 + 2x1000 – 4x x30000 若采用顺序存储，就要用一长度为30001的顺序表来表示，表中仅有3个非零元素。为了有效而合理地利用存储空间，我们自然会想到只存储非零系数项，来表示此类多项式，但是存储非零系数项的同时必须存储相应的指数，才能正确表示这样的一元多项式。

104 一般地，有m个非零系数项的一元n次多项式可写成：
其中，是指数为项的非零系数，且满足： 那么，可以用链式存储结构来表示一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表。 也就是说，用包含m个结点的单链表便可唯一确定多项式 。

105 图2.15所示为两个如上定义的带头结点的单链表分别表示多项式可写成：
也就是说，用包含m个结点的单链表便可唯一确定多项式 。

106 下面我们讨论用单链表表示一元n次多项式时，两个多项式相加（利用原结点空间）的算法，即要求：
Amax(m,n)(x) = Am(x)+Bn(x)， 算法结束，结果在A中，B成为“空”。 算法思路：多项式相加的运算规则为：两个多项式中所有指数相同的项（同类项），对应系数相加，若系数和不为零，则构成“和多项式”的一项；所有指数不同的项均复抄到“和多项式”中。

107 我们假定多项式表A, B已按升幂顺序排列好，设指针p,q分别指向A, B的当前未处理项中的指数最小项（初始均指向首元结点），那么，多项式相加的过程为：将p,q所指结点的指数进行比较，若p所指结点的指数小则p指针前移，若q所指结点的指数小则从B表中摘除该结点插入到A表，q指针前移，否则是指数相等，若系数和≠0，将p指结点系数改为系数之和，反之从A表删除当前结点，无论系数和是否为0，均须从B表删除当前结点，p,q均应当前移到下一指数最小项，重复进行之，直到p,q中至少一个指“空”，这时若q不空，则将B表剩余项转移到A表，至此算法完成。

108 定义多项式的数据项类polyNode.h的内容为：
class polyData // 多项式的数据项类 { protected: int exp; // 指数域 float coef; // 系数域 public: void GetNode(int &i, float &x) // 将当前对象的指数, 系数取到引用参数i, x { i=exp, x=coef; } void SetNode(int i, float x) // 用参数i, x的值设置当前对象的指数, 系数 { exp=i, coef=x; }

109 bool operator<(const polyData& right)
// "<" 运算符重载 (指数域比较) { return exp<right.exp; } bool operator>(const polyData& right) // ">“ 运算符重载 (指数域比较) { return exp>right.exp; } void operator+=(const polyData& right) // "+=“ 运算符重载 (系数域相加) { coef+=right.coef; } bool coefisZero() // 判断系数域是0？ { return coef==0.0; } };

110 注意：由于我们在实例化单链表类时，将<T>用<polyData>具体化，在单链表类中的成员函数InsertNode(T e) 是按元素e值的大小插入有序表，而polyData的数据元素值有2个域，因此我们将比较运算符"<"、">"重载为左对象与右对象指数比较的结果。同理，运算符"+="被重载为："+="号左、右对象系数求和赋给左对象。

111 // Poly.cpp #include "SLList.h" #include "polyNode.h" void Poly_Add(LinkedList<polyData>&, LinkedList<polyData>&); //多项式求和 void CrtpolyList(LinkedList<polyData>&); // 向多项式表插入若干输入项 void main(void) //从终端读入系数和指数建立A,B多项式链表, 求A=A+B； // 并输出原A、B多项式及和多项式 { inkedList<polyData> La, Lb; // 声明单链表对象La , Lb, <T>被代之为<polyData>

112 cout<<"input A coefficient and exponent,
exponent=-1 end!(term<50)\n"; CrtpolyList(La); // 读入若干系数和指数对, 插入到La cout<<"\n creat polyNom link list A is\n"; La.traverse('/'); // 输出La表示的多项式A cout<<"\ninput B coefficient and exponent, CrtpolyList(Lb); // 读入若干系数和指数对, 插入到Lb cout<<"\n creat polyNom link list B is\n"; Lb.traverse('/'); // 输出Lb表示的多项式B cout<<"\n A=A+B outcome is\n"; Poly_Add(La,Lb); // 求和多项式

113 La.traverse('/'); // 输出和多项式
cout<<"\n"; } void CrtpolyList(LinkedList<polyData>& L) // 按升幂序将输入的数据对插入多项式链表L { int i; float x; polyData e; cin >>i>>x; // 读入(实数, 整数) 对, 对应于(系数, 指数) while(i!=-1) // 读数对插入多项式表, 输入-1为结束标志 { e.SetNode(i,x); L.InsertNode(e); cin>>i>>x; } //按指数序插入有序表

114 void Poly_Add( LinkedList<polyData>& Pa ,
LinkedList<polyData>& Pb ) // 求升幂排列的多项式表Pa与Pb之和, 存入Pa (利用原结点空间) , // 和多项式仍是升幂排列 { Node<polyData> *p,*q,*r,*s; int m=Pa.Length(), n=Pb.Length(); int c=0, d=0; // c统计循环中Pa增加的项数，d统计循环中Pb摘除的项数 s=Pa.Head; // s指向和多项式的当前尾结点 (s ->next 指向p) p=s->next; q=Pb.Head->next; //令p,q分别指向两多项式的首项 while(p && q) //多项式Pa与Pb均有未处理的数据项

115 if(p->data<q->data){ s=p; p=p->next; }
else if(p->data>q->data) //q所指项的指数较小 { r=q->next; q->next=p; s->next=q; s=q; q=r; c++; d++; } else{ p->data+=q->data; // 同类项, 求系数和存入p所指项 if((p->data).coefisZero()) // 判断系数和是0否,是则从Pa摘除结点 { s->next=p->next; delete p; c--;

116 else s=p; // 系数之和!=0, s前移 // 无论系数和是否为0, 均摘除Pb中结点 p=s->next; r=q; q=q->next; delete r; d++; } // 结束p,q所指项为同类项的处理 if(q)s->next=q; // 若Pb表中有剩余元素则插入Pa Pb.Head->next=NULL, Pb.Size=0; // 置Pb表为“空”表 Pa.Size=m+c+(n-d); // 计算Pa表的项数，置Pa表的Size } void visitNodeData(polyData e) // 输出多项式数据域 { float x; int j; e.GetNode(j,x); cout<<"( "<<x<<','<<j<<")→";

117 2.5 小结 本章主要介绍了如下一些基本概念： 线性表 及其 两种存储结构 单链表 循环链表 双链表
单链表 循环链表 双链表 给出了线性表的模板类（顺序表、单链表）并且应用它们完成了集合运算、一元多项式的链式表示与相加等应用实例。