第2章线性表 2.4其它链表形式《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第二章 线性表 讨论1： 链表能不能首尾相连？怎样实现？ 答：能。只要将表中最后一个结点的指针域指向头结点即可 (P->next=head;) 。这种形成环路的链表称为循环链表。 特别：带头结点的空循环链表样式 H 特点： 1、从任一结点出发均可找到表中其他结点。 2、操作仅有 一 点与单链表不同：循环条件 单链表 ----- p = NULL 或 p ->next =NULL 循环链表----- p= head 或 p->next = head 6. 其它链表形式 讨论2： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？ 答：能。只要把单链表再多开一个指针域即可(例如用*next和*prior;) 。 双向链表在非线性结构（如树结构）中将大量使用。 prior data next 这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。 特别：带头结点的空双向链表样式： 2.3.3 链表的运算效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 时间效率分析 2. 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。 空间效率分析 链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。 2.4.1 多项式的线性表表示 An(x)=anxn+an-1xn-1+...+a1x+a0 , 用线性表表示为： A=(an,an-1,...,a1,a0) 若多项式的阶次很高，而系数ai不为零的很少，则这 种表示浪费空间。 可写为： A(x)=amxem+an-1xem-1+...+a1xe1+a0xe0, 用线性表表示为: A=((am,em),(am-1,em-1),...,(a1,e1),(a0,e0)) 2.4 应用举例 (一元多项式的计算) 举例说明 二、多项式相加的方法 A+B=>C 1、线性表C置空 2、各取线性表A和B的第一个元素作为当前处理的元素 3、比较当前处理的元素的指数值，相等，系数相加若不为零追加到线性表C，各取线性表A和B的下一个元素作为当前处理的元素；若指数不相等，则把大的元素追加到线性表C，取该元素所在线性表的下一个元素作为当前处理的元素。 4、重复步骤3直到其中一个线性表处理完毕，再把另一个线性表的剩余元素追加到线性表C。 2.4.2顺序结构的加法实现 一、多项式的数组存放 #define MAXN 100 typedef struct term { float coef; int exp; }TERM; TERM poly[MAXN]; 二、程序实现 int ah,at,bh,bt,ch,ct,free; int append(float c,int e) { if(free>=MAXN) return(1); poly[free].ceof=c; poly[free].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=free; while(a_p<=at&&b_p<=bt) { a_exp=poly[a_p].exp;b_exp=poly[b_p].cexp; if(a_exp==b_exp) { c_coef=poly[a_p].coef+poly[b_p].coef; if(c_coef) if(append(c_coef,a_exp)) return(1); a_p++;b_p++; } else if(a_exp>b_exp) { if(append(poly[a_p].coef,a_exp)) return(1); a_p++; } else { if(append(poly[b_p].coef,b_exp)) return(1); b_p++;}} whi