数据结构与算法 线性表讲解

1、 指指互相有关联的数据元素的集合，互相有关联的数据元素的集合， 用用 D_S=( D, S ) 表示表示。 数据数据的逻辑结构的逻辑结构、数据的存储、数据的存储结构和运算结构和运算。 时间时间复杂度和空间复杂度复杂度和空间复杂度 线性结构的特点线性结构的特点： 对于对于非空非空的线性表，有且仅有一个的线性表，有且仅有一个开始结点开始结点和和 一个一个终端结点终端结点；开始结点；开始结点没有没有直接前趋，有且直接前趋，有且 仅有一个直接后继；终端结点仅有一个直接后继；终端结点没有没有直接后继，直接后继， 有且仅有一个直接前趋；其余任何结点有且仅有且仅有一个直接前趋；其余任何结点有且仅 有有一个直

2、接前趋一个直接前趋和和一个直接后继一个直接后继。 非空线性表可表示为非空线性表可表示为：L = ( aL = ( a1 1 , a, a2 2 , , , , a an n ) ) 简言之，简言之，线性结构线性结构反映结点间的逻辑关系是反映结点间的逻辑关系是 的的 线性结构线性结构包括包括线性表线性表、堆栈堆栈、队列队列、字符串字符串、 数组数组等等，等等，其中，最简单、最常用的是其中，最简单、最常用的是 线性表线性表 见第见第2 2章章 1 1、了解了解线性表的线性表的结构特性结构特性，以及线性表的，以及线性表的两种两种存存 储实现方式储实现方式。 2 2、熟练掌握熟练掌握两种存储结构两种存

3、储结构的的。 。 3 3、熟练掌握熟练掌握的定义与实现，包括的定义与实现，包括查找、插入、查找、插入、 删除删除算法的实现。算法的实现。 4 4、熟练掌握熟练掌握在各种在各种结构中实现线性表操作的基本结构中实现线性表操作的基本 方法方法，能在实际应用中选用适当的链表结构。，能在实际应用中选用适当的链表结构。 5 5、能够从能够从时间时间和和空间空间复杂度复杂度的角度综合的角度综合比较线性表两比较线性表两 种存储结构种存储结构的的不同特点不同特点及其及其适用场合适用场合。 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 线性表的链式表示和实

4、现线性表的链式表示和实现 2.4 应用举例应用举例 a1, a2, ai-1, ai , ai+1 , , an P12 1. 1. 线性表的定义：线性表的定义：是是 n (n0) 个个类型相同类型相同的数据元素的数据元素 组成的组成的有限有限序列序列， n=0=0时称为时称为 aiai n 线性表线性表名称名称 9 学号学号姓名姓名性别性别籍贯籍贯电话电话通讯地址通讯地址 880001丁一丁一男男长沙长沙 8639000麓山南路麓山南路327号号 880002马二马二男男北京北京 23456789学院路学院路435号号 880003张三张三女女广州广州 30472589天河路天河路478号号

5、 880004李四李四男男上海上海 41237568南京路南京路1563号号 880005王五王五女女南京南京 5013472南京大学南京大学 880006赵六赵六女女昆明昆明 4089651云南大学云南大学 例例1 1 分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z） 例例2 2 分析学生情况登记表分析学生情况登记表 10 2、线性表的运算线性表的运算 11 线性表的基本运算有：线性表的基本运算有： 12 前面给出了一些前面给出了一些，另外可以定义更复杂的操作，另外可以定义更复杂的操作， 如如：将两个线性表合并将两个线性表合并等。等。复杂

6、操作可用基本操作实现复杂操作可用基本操作实现。 基本步骤：基本步骤： 1. 分别分别从从La和和Lb中取得当前中取得当前元素元素la.datai和和lb.dataj； 2. 若若la.datailb.dataj，则则将将la.datai插入插入到到Lc中，否则中，否则 将将lb.dataj插入插入到到Lc中；中； 3. 重复重复第第1、2步直到有一个表的元素取完步直到有一个表的元素取完为止；为止； 4. 将将没有处理完的表中所剩元素，复制到没有处理完的表中所剩元素，复制到Lc中中。 13 14 15 P13 。 用一组用一组地址连续地址连续的存储单元依次存储线性表的元素，的存储单元依次存储线性

7、表的元素， 可通过可通过来实现来实现。 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻； 若已知表中若已知表中首元素首元素在存储器中的位置，则其他元素在存储器中的位置，则其他元素 存放位置亦可求出（利用数组下标）。计算方法是存放位置亦可求出（利用数组下标）。计算方法是 （参见存储结构示意图参见存储结构示意图）： 设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），）， 设设每个元素占用存储空间（地址长度）为每个元素占用存储空间（地址长度）为L字节字节， 则则表中任一数据元素的存放地址为：表中任一数据元素的存放地址为： LOC(ai)

8、= LOC(a1) + ( i-1)*L LOC(ai+1) = LOC(ai)+L a a1 1 a ai+1 i+1 a an n 1 1 i i 2 2 n n i+1i+1 L b=LOC(a1) b + + L L b +(i-1+(i-1) )* *L L b +(n-1+(n-1) )* *L L b +(max-1+(max-1) )* *L L 一个一维数组，下标的范围是一个一维数组，下标的范围是到到，每，每 个数组元素用相邻的个数组元素用相邻的存储。存储器按字节存储。存储器按字节 编址，设存储数组元素编址，设存储数组元素的第一个字节的地址的第一个字节的地址 是是，则，则的第

9、一个字节的地址是的第一个字节的地址是 113113 因此：因此：LOC( M3 ) = 98 + (4-1) 5=1 11 13 3 地址计算通式为：地址计算通式为： LOC(ai) = LOC(a1) + ( i-1 ) * L 基地址基地址 已经存储的元素所占空间已经存储的元素所占空间 (1(1) )在线性表的第在线性表的第i个位置个位置一个元素一个元素 ： (1) （ 哪些元素？移动方向？移动次序？哪些元素？移动方向？移动次序？） 将将第第 n 至第至第 i 个个的的元素依次元素依次向后向后移动一个位置；移动一个位置； (2) 将要将要插入的元素插入的元素写到写到第第 i个位置；个位置；

10、 (3) 表表长长加加 1。 注意：注意：事先应事先应判断判断：插入插入位置位置i 是否合法是否合法?表是否已满表是否已满? 长度为长度为n的线性表的线性表变变为为长度为长度为n+1的线性表的线性表 int INSERT(sequenlist *L, datatype x, int i ) int j; if (*L).last)=MAXSIZE-1) return (NULL); if (i(*L).last)+2) return (NULL); for (j=(*L).last; j=i-1; j-) (*L).dataj+1= (*L).dataj; (*L).datai-1=x; (*

11、L).last +; return(1); (1) （ 哪些元素？移动方向？移动次序？）哪些元素？移动方向？移动次序？） 将第将第i +1至第至第n 位的元素依次位的元素依次向前向前移动一个位置；移动一个位置； (2) 表表长长减减1。 注意注意：事先需要判断，：事先需要判断，删除删除位置位置 i 是否合法是否合法? (2(2) ) 线性表的第线性表的第i个位置上的元素个位置上的元素 长度为长度为n的线性表的线性表变变为为长度为长度为n-1的线性表的线性表。 时间效率时间效率分析分析： 算法花费的时间，主要在于算法花费的时间，主要在于循环中元素的后移循环中元素的后移 （其它语句花费的时间可以省

12、去），即从插入位置到（其它语句花费的时间可以省去），即从插入位置到 最后位置的所有元素都要后移一位，最后位置的所有元素都要后移一位，使空出的位置插使空出的位置插 入元素入元素值值 。但是，插入的位置是不固定的，当插入。但是，插入的位置是不固定的，当插入 位置位置 时时，全部元素都得移动，全部元素都得移动，需需 次次移动；当移动；当 时，不需移动时，不需移动元素；故在元素；故在 位置位置插入时移动次插入时移动次 数数为为 。 时间效率分析时间效率分析： 算法花费的时间，主要在于算法花费的时间，主要在于循环中元素的前移循环中元素的前移 （其它语句花费的时间可以省去），即从删除位置到（其它语句花费的

13、时间可以省去），即从删除位置到 最后位置的所有元素都要前移一最后位置的所有元素都要前移一位位。但是但是，删除的位，删除的位 置是不固定的，当删除置是不固定的，当删除位置位置 时，全部元素都得移时，全部元素都得移 动，动，需需 次次移动，移动，当当 时时，不需移动元素，故，不需移动元素，故在在 位置位置删除时移动次数删除时移动次数为为 假定在表中任意位置插入、删除元素都是假定在表中任意位置插入、删除元素都是等概率等概率的，的， 概率概率 ，概率概率 ，则：则： 操作时间效率（平均移动次数）操作时间效率（平均移动次数） 2 )1( 1 1 )1( 1 1 1 1 n in n inpE n i n

14、 i iis 操作时间效率（平均移动次数）操作时间效率（平均移动次数） 2 1 )( 1 )( 11 n in n inqE n i n i idl 显然，顺序表的显然，顺序表的空间复杂度空间复杂度 （没有占用辅助空间）（没有占用辅助空间） 线性表顺序存储结构线性表顺序存储结构：逻辑关系上逻辑关系上相邻相邻的两个元的两个元 素在物理存储位置上也素在物理存储位置上也相邻相邻； 可以可以随机随机存取表中任一元素存取表中任一元素；存储空间使；存储空间使 用紧凑。用紧凑。 在插入，删除某一元素时，需要移动大量元素在插入，删除某一元素时，需要移动大量元素 ；预先预先分配空间需按最大空间分配，利用不分配空

15、间需按最大空间分配，利用不充分充分； 表表容量难以扩充。容量难以扩充。 为克服这一为克服这一，我们引入另一种存储形式：，我们引入另一种存储形式： 用一组用一组任意任意的存储单元存储线性表的数据元素的存储单元存储线性表的数据元素 利用利用指针指针实现了用不相邻的存储单元存放逻辑上实现了用不相邻的存储单元存放逻辑上 相邻的元素相邻的元素 每个数据每个数据元素元素 ，除存储本身信息外，还需存储其除存储本身信息外，还需存储其 直接后继的信息直接后继的信息 结点 数据数据域域data：元素本身信息元素本身信息 指针指针域域next：指示直接后继的指示直接后继的存储位置存储位置 数据域 指针域 结点结点

16、例例 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 数据域数据域指针域指针域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存储地址存储地址 1 7 13 19 25 31 37 43 31 H 头指针头指针 与链式存储有关的术语：与链式存储有关的术语： 1、结点：、结点：数据元素的存储映像。由数据元素的存储映像。由数据域数据域和和指针域指针域两部分组成；两部分组成； 2、链表：、链表： n 个结点由个结点由指针指针链组成一个链表。它是线性表的链式链组成一个链表。它是线性表的链式 存储映像，

17、称为存储映像，称为线性表的链式存储结构线性表的链式存储结构。 3、单链表、双链表、多链表、循环链表：单链表、双链表、多链表、循环链表： 结点只有结点只有一个指针域一个指针域的链表，称为的链表，称为单链表单链表或线性链表；或线性链表； 结点结点有有两个指针域两个指针域的链表，称为的链表，称为双链表双链表； 结点结点有有多个指针域多个指针域的链表，称为的链表，称为多链表多链表； 首尾相接首尾相接的链表称为的链表称为循环链表循环链表。 a1 head a2anhead 示意图示意图： 何谓头指针、头结点和开始结点？何谓头指针、头结点和开始结点？ 是指向链表中是指向链表中第一个第一个结点（或为头结点或

18、开始结点（或为头结点或开始 结点）的指针。结点）的指针。 单单链表可由一个链表可由一个头指针头指针唯一确定。唯一确定。 头结点头结点是在链表的是在链表的开始结点开始结点之前之前附设附设的一个结点；的一个结点；数数 据域内只放空表标志和表长等据域内只放空表标志和表长等信息信息； 开始结点开始结点是指链表中存储线性表第一个数据是指链表中存储线性表第一个数据元素元素a1的的 结点。结点。 头指针头指针头结点头结点开始结点开始结点 a1 一个线性表的逻辑结构为一个线性表的逻辑结构为： （ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），）， 其存储结构用单链表表示如下，请问其其

19、存储结构用单链表表示如下，请问其头指针头指针的值是的值是 多少？多少？ 存储地址存储地址数据域数据域指针域指针域 1LI43 7QIAN13 13SUN1 19WANG 25WU37 31ZHAO7 37ZHENG19 43ZHOU25 例： 答：答：是指向链是指向链 表中第一个结点的指表中第一个结点的指 针，因此关键是要寻针，因此关键是要寻 找找第一个结点第一个结点的的地址地址。 7ZHAO H 31 的值是的值是31 上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式： ZHAOQIANLISUN ZHOUWUZHENGWANG H ZHAOQIANLISUN Z

20、HOUWUZHENGWANG H 无头结点无头结点 有头结点有头结点 在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？ 如何表示如何表示空表空表？ 头结点头结点即在链表的即在链表的首结点首结点之前附设的一个结点，该之前附设的一个结点，该 结点的数据域中不存储线性表的数据元素，其作用是为结点的数据域中不存储线性表的数据元素，其作用是为 了对链表进行操作时，可以对了对链表进行操作时，可以对空表空表、非空表非空表的情况以及的情况以及 对对开始结点开始结点进行统一处理，编程更方便进行统一处理，编程更方便。 无无头结点时，头结点时，当头指针的值为空当头指针的值为空时表示时表示空表空表； 有有

21、头结点时，头结点时，当头结点的指针域为空当头结点的指针域为空时表示时表示空表空表。 头指针头指针头指针头指针头结点头结点 无头结点无头结点有头结点有头结点 typedef struct node datatype data; /数据域数据域 struct node *next; /指针域指针域 linklist; linklist *head, *p; 教材对于的描述: 补充：结构类型的补充：结构类型的C语言表示法语言表示法 介绍三个有用的介绍三个有用的库函数库函数（都在（都在 中）：中）： sizeof(x) 计算变量计算变量x的长度；的长度； malloc(m) 开辟开辟m字节长度的地址空

22、间，并返回这段空间字节长度的地址空间，并返回这段空间 的首地址；的首地址； free(p) 释放指针释放指针p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除 一个变量。一个变量。 1. 单链表的建立和输出单链表的建立和输出 2. 单链表的修改单链表的修改 3. 单链表的插入单链表的插入 4. 单链表的删除单链表的删除 5. 应用举例应用举例 6. 其它链表形式其它链表形式 1. 单链表的建立和单链表的建立和输出输出 头插法建单链表的演示头插法建单链表的演示 尾插法建单链表的演示尾插法建单链表的演示 1. 单链表的建立和输出单链表的建立和输出 实例实例：用单链表结构来存放用单链表结

23、构来存放26个英文字母组成的线性个英文字母组成的线性 表（表（a，b，c，z）,请写出请写出C语言程序。语言程序。 每个数据元素在内存中是每个数据元素在内存中是“零散零散”存存 放的，其放的，其首地址首地址怎么找？又怎么一一链接？怎么找？又怎么一一链接？ 先开辟头指针，然后陆续为每个数据先开辟头指针，然后陆续为每个数据 元素开辟存储空间并赋值，并及时将地址送给前面元素开辟存储空间并赋值，并及时将地址送给前面 的指针的指针。 #include #include typedef struct node datatype data; /数据域数据域 struct node *next; /指针域指针

24、域 linklist; linklist *head, *p, *q; /一般需要一般需要3个指针变量个指针变量 int n ; / 数据元素的个数数据元素的个数 int m=sizeof(linklist); /* 结构类型定义好之后，每个变量的长度就固定了，结构类型定义好之后，每个变量的长度就固定了， m求一次即可求一次即可 */ VOID BUILD( ) /字母链表的生成。要一个一个慢慢链入字母链表的生成。要一个一个慢慢链入 int i; head=(linklist *)malloc(m); /前面已求出前面已求出M值值 p=head; for( i=1; idata=i+a-1;

25、/ 第一个结点值为第一个结点值为字符字符a p-next=(linklist *)malloc(m); /为后继结点开新空间！为后继结点开新空间！ p=p-next； /让指针变量让指针变量P改为指向后继结点改为指向后继结点 p-data=z; /最后一个元素要单独处理最后一个元素要单独处理 p-next=NULL; 单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！ 新手特别容易忘记！新手特别容易忘记！ VOID DISPLAY() /*字母链表的输出字母链表的输出*/ p=head-NEXT; while (p!=NULL) /* 只要没到最后一个元素，就不只要没到最后一个元素，就不

26、 停地停地“顺藤摸瓜顺藤摸瓜”输出输出*/ printf(%c, p-data); p=p-next; 要统计链表中数据元素的个数，该如何改写？要统计链表中数据元素的个数，该如何改写？ sum +; 2. 单链表的读取单链表的读取(或修改）或修改） 启发：启发：要修改第要修改第i个数据元素，关键是要先找到该结点个数据元素，关键是要先找到该结点 的指针的指针p，然后用，然后用p-data=new_value 即可。即可。 提问：提问：如何实现按值查找？如何实现按值查找？ 单链表中想取得第单链表中想取得第i个元素，必须从头指针出个元素，必须从头指针出 发寻找（发寻找（顺藤摸瓜顺藤摸瓜），），不能随

27、机存取不能随机存取 。 datatype Get(linklist *L, int i) p=L-next; j=1; while ( jnext; +j; if(!p|ji)return NULL; e=p-data; return e; p Step 2：p-next=s ； p-next s-next 元素元素x结点应预先生成：结点应预先生成： S=(linklist*)malloc(m); S-data=x; void INSERTAFTER( linklist *p, datatype x) linklist *s; s=(LinkList *)malloc(sizeof(linkl

28、ist); s-data=x; s-next=p-next; p-next=s; 单链表结点插入的演示单链表结点插入的演示 3. 单链表的插入单链表的插入前插法前插法 即：在链表中即：在链表中(*p)结点前面插入一个元素。结点前面插入一个元素。 思考思考： 1、如何实现？、如何实现？（P25：INSERTBEFORE() 函数函数） 必须找到必须找到(*p)结点的直接前趋结点结点的直接前趋结点(*q)，并借助此结，并借助此结 点完成插入操作。点完成插入操作。 2、如何改进？、如何改进？ （P25：INSERTBEFORE1() 函数函数） 先实现后插操作，再交换结点的关键字值。先实现后插操作，

29、再交换结点的关键字值。 4. 单链表的删除单链表的删除 在链表中删除在链表中删除(*p)结点的直接后继结点结点的直接后继结点 c a b p 删除步骤（即删除步骤（即核心语句核心语句）： q = p-next; /保存保存b的指针，后面释放时有用的指针，后面释放时有用 p-next=q-next; /a、c两结点相连两结点相连 free(q) ； /删除删除b结点，彻底释放结点，彻底释放 p-next 思考思考：不要不要q行不行？省略行不行？省略free(q)语句行不行？语句行不行？ (p-next) - next datatype DeleteAfter ( linklist *p ) li

30、nklist *q; q=p-next; p-next=q-next; x=q-data; free(q); return x; 单链表结点的删除演示单链表结点的删除演示 思考：思考： 如何删除如何删除（*p）结点本身？结点本身？ 5.应用举例：两个链表的应用举例：两个链表的归并归并 P29 算法要求：算法要求： 已知：线性表线性表 A、B，分别由单链表，分别由单链表 La , Lb 存储，其存储，其 中数据元素按值中数据元素按值非递减非递减有序排列，有序排列， 要求：将将 A ，B 归并归并为一个新的线性表为一个新的线性表C , C 的数据元的数据元 素仍按值素仍按值非递减非递减排列排列 。

31、设线性表。设线性表 C 由单链表由单链表 Lc 存储。存储。 假设：A=（3，5，8，11），），B=（2，6，8，9，11） 预测：合并后合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ） 用链表可表示为：用链表可表示为： 3 3 5 51111 / / 8 8 2 2 6 61111 / 8 8 9 9 2 3 6 5 8 811 / 911 算法分析：算法分析： 算法主要包括：算法主要包括：搜索搜索、比较比较、插入插入三个操作三个操作： 搜索搜索：需要两个指针搜索两个链表；：需要两个指针搜索两个链表； 比较比较：比较结点数据域中数据的大小：比较结点数

32、据域中数据的大小； 插入插入：将两个结点中数据小的结点插入新链表。：将两个结点中数据小的结点插入新链表。 La 3 5 8 11 Lb 2 6 8 119 Pa Pb Pa Pb Pa、Pb用于搜索用于搜索La和和Lb， Pc指向新链表当前结点指向新链表当前结点 Lc Pa 3 Pc Pa 5 Pc 11 Pc 2 Pb Pc Pa 算法实现：算法实现： Void MergeList_L(LinkList *La,LinkList *Lb,LinkList *Lc) /按值排序的单链表按值排序的单链表LA,LB，归并为，归并为LC后也按值排序后也按值排序 free(Lb); /释放释放Lb的头

33、结点的头结点 /MergeList_L pc-next = pa?pa:pb ; /插入剩余段插入剩余段 while(pa pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pa=La-next; pb=Lb-next; Lc=pc=La； /初始化初始化 6. 其它链表其它链表形式形式 讨论讨论1： 链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？ 答：答：能。只要将表中最后一个结点的指针域指向头结能。只要将表中最后一个结点的指针域指向头结 点即可点即可 (P-next=head;) 。这种形成环路的链表称为。这种形成环

34、路的链表称为 循环链表循环链表。 特点特点： 1、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。 2、操作仅有、操作仅有 一一 点与单链表不同：点与单链表不同：循环条件循环条件 单链表：单链表： p = NULL 或或 p -next =NULL 循环链表循环链表：p= head 或或 p-next = head 特别特别：带头结点的带头结点的循环链表样式循环链表样式 H 讨论讨论2：单单链表只能查找结点的直接后继，能不能查链表只能查找结点的直接后继，能不能查 找直接前驱？如何实现？找直接前驱？如何实现？ 答：答：能。只要把单链表再多开一个指针域即可能。只要把单链表

35、再多开一个指针域即可( (例如例如 用用* *nextnext和和* *prior;prior;) ) 。 双向链表在非线性结构（如树结构）中将大量使用。双向链表在非线性结构（如树结构）中将大量使用。 priordatanext 这种有这种有两个指针两个指针的链表称为的链表称为双向链表双向链表。其特点是可以。其特点是可以 双向查找表中结点双向查找表中结点。参见参见教材教材P3235。 特别特别：带头结点的带头结点的双向链表样式双向链表样式：P33 1. 1. 查找查找 因线性链表因线性链表只能顺序存取只能顺序存取，即在查找时要，即在查找时要从从 头指针头指针找起，查找的时间复杂度为找起，查找的

36、时间复杂度为 O(n)。 2. 2. 插入和删除插入和删除 因线性链表因线性链表不需要移动元素不需要移动元素，只要，只要 修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为 O(1)。 但是但是，如果要在单链表中进行，如果要在单链表中进行前插前插或或删除删除操作，由操作，由 于要从头查找前驱结点，所耗时间复杂度为于要从头查找前驱结点，所耗时间复杂度为 O(n)。 链表链表中每个结点都要增加一个指针空间，相当中每个结点都要增加一个指针空间，相当 于总共增加了于总共增加了n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)。 A (x)=anxn+an-1xn-1+.+a1

37、x+a0 , 用用线性表表示为线性表表示为： A=(an,an-1, . ,a1,a0) 若若多项式的阶次很高，而系数多项式的阶次很高，而系数ai又大多为零，又大多为零，则则这种这种 表示浪费空间表示浪费空间。可。可写为：写为： A(x)=amxem+an-1xem-1+.+a1xe1+a0 xe0, 用线性表表示用线性表表示为为： A=(am,em),(am-1,em-1),.,(a1,e1),(a0,e0) A+B=C 1、线性表、线性表C置空置空 2、各取线性表、各取线性表A和和B的第一个元素作为当前处理的元素的第一个元素作为当前处理的元素 3、比较当前处理的元素的指数值，相等，系数相加

38、若、比较当前处理的元素的指数值，相等，系数相加若 不为零追加到线性表不为零追加到线性表C，各取线性表，各取线性表A和和B的下一个元的下一个元 素作为当前处理的元素；若指数不相等，则把大的元素作为当前处理的元素；若指数不相等，则把大的元 素追加到线性表素追加到线性表C，取该元素所在线性表的下一个元，取该元素所在线性表的下一个元 素作为当前处理的元素。素作为当前处理的元素。 4、重复步骤、重复步骤3直到其中一个线性表处理完毕，再把另一直到其中一个线性表处理完毕，再把另一 个线性表的剩余元素追加到线性表个线性表的剩余元素追加到线性表C。 #define MAXN 100 typedef struct

39、 term float coef; int exp; TERM; TERM polyMAXN; int ah,at,bh,bt,ch,ct,free; int append(float c,int e) if(free=MAXN) return(1); polyfree.ceof=c; polyfree.exp=e; free+; return(0); int poly_add(int ah,int at,int bh,int bt,int *ch_p,int *ct_p) int a_p,b_p,a_exp,b_exp; float c_coef; a_p=ah;b_p=bh; *ch_p=

40、free; while(a_p=at a_p+; else if(append(polyb_p.coef,b_exp) return(1); b_p+; while(b_p=bt) if(append(polyb_p.coef,polyb_p.exp) return(1); b_p+; while(a_pcoef=c; t-exp=e; pc-link=t; return(t); NODE *poly_add(NODE *ah,NODE *bh) NODE *pa,*pb,*pc,*ch; ch=(NODE *)malloc(sizeof(NODE); pc=ch; pa=ah;pb=bh; while(pa!=NU