第2章--线性表-4.ppt

1、1,数据结构,第2章 线性表 第4讲,2,本章分为（45）讲,第1讲 2.1 线性表的基本概念 2.2 线性表的顺序存储结构及实现（2.2.12.2.3）,第3讲 2.3.3（删除）2.3.4 2.4 循环链表和双向链表,第2讲 2.2.4 线性表的其他运算 2.3 线性表的链表存储结构及实现 2.3.12.3.3（插入）,第4讲 2.5 一元多项式相加问题 小结,供教师参考,3,2.5 一元多项式相加问题,一元符号多项式的相加操作是线性表处理的典型用例。数学上一个一元多项式如下： 称p为x的n阶多项式，aixi是多项式的某个单项（0in），其中x为自变量，ai为系数，i为自变量的指数。已知有

2、两个一元多项式A和B： 将这两个多项式相加得一个新的多项式C：,4,2.5.1 多项式的链表存储结构,一个多项式可以采用一条链表来表示。每个结点对应于多项式的一个项，其结点的结构如下： struct Lpoly int coef ; /自变量的系数 intexp ; /自变量的指数 Lpoly *next; /指向下一结点的指针 ; 每个多项式的链表由多个单项的结点组成，高指数的项（高次幂）结点在链表头部，低指数的项（低次幂）结点在链表的后部。A，B两个多项式的链表结构如图所示。,5,2.5.2 多项式相加的实现,一个链表中结点的顺序按照x的指数递减排列。两个多项式相加实质上是两个有序链表的合

3、并操作。 为了实现两个多项式相加，现设C链表为A、B链表相加后的新链表。为了节省内存资源，以A链表为基础将B链表的结点合并到A链表中。在此，设C链表头指针为pc，令其指向pa(pc=pa)，这样以pa链表为基础进行合并操作，最终的结果就是这条以pc为头指针的链表。,6,多项式加法（链表合并）的方法,为了进行多项式加法运算，设置p，q两个指针变量分别指向pa，pb两个链表的第一个数据元素结点。 然后对p，q两个结点的指数域进行比较： 1. 两个结点的指数相同，则结点的系数相加。新的系数非零，则连入第3条链表C；否则跳过这两个结点。 2. 两个结点的指数不同，将指数较大的结点连入C表。,7,初始状

4、态 第1次处理后 第2次处理后,多项式加法（链表合并）的图示,8,Lpoly *add_poly(Lpoly *pa, Lpoly *pb) Lpoly *pc, *p, *q, *r; p=pa-next; q=pb-next; r=pa; pc=pa; while (p!=NULL ,多项式加法（链表合并）算法2.10,9,else /指数不相等 if(p-expq-exp) /p结点指数大，接入p结点 r-next=p; r=p; p p-next; else /q结点指数大，接入q结点 r-next=q; r=q; q=q-next; / while end if(p=NULL) r-

5、next=q; else r-next=p; return pc; /返回合并后的链表头指针pc /add_poly end,多项式加法（链表合并）算法2.10,10,多项式加法（链表合并）算法说明,整个算法主体是一个循环结构，循环条件是两个while (p!=NULL /数据元素的类型 const int MAXSIZE=100; /数组的容量 class Sqlist private: ElemType elemMAXSIZE; int length; public: Sqlist( void); Sqlist() ; void Creat(); void Insert( int i, E

6、lemType e); ElemType Delet(int i); void PrintOut(); ;,14,/- Sqlist:Sqlist()length=0; void Sqlist:Creat() ;/详见2.2.2节 void Sqlist:Insert( int i, ElemType e) ;/详见2.2.3节 ElemType Sqlist:Delet(int i) ; /详见2.2.3节 void Sqlist:PrintOut() ; /详见2.2.2节 /-,15,int main( ) int i,k; ElemType e,x; Sqlist as; coutk;

7、,主函数的设计,16,switch(k) case 1: as.Creat(); as.PrintOut(); break; case 2: coutie; as.Insert(i,e); as.PrintOut(); break; case 3: couti; x=as.Delet(i); cout=1 /-,17,上机实验重视主函数的设计,主函数的基本内容： 1.声明创建数据结构的类对象； 2.菜单设计； 3.在switch-case多分支结构中，调用数据结构的各种典型算法的函数。,18,2.7 本章小结,线性表是整个“数据结构”课程的重要基础。虽然线性表的基本概念没有太大难度，但是从抽象

8、数据类型（ADT）的角度认识并不简单。在搞清它的逻辑结构之后，需要掌握两种不同的存储结构，以及相关运算的实现。 线性表采用顺序存储结构在插入、删除时，需大量移动数据元素，效率较低。由于是静态存储结构，需预先定义大小确定的数组，容量有限。但是，它适于直接（随机）存取操作。,19,2.7 本章小结,线性表采用单链表结构表示线性表在插入、删除时，不必大量移动数据元素效率较高。由于是动态存储结构，不需预先定义大小，根据需要可申请或者释放结点。但是，它不适于直接（随机）存取操作，总是需要从链表的头结点处组织循环向后查找。 从存储结构的角度看，顺序结构和链表结构都很重要，它们是整个“数据结构”课程的基础。,20,2.7 本章小结,从算法设计的角度看，重点是插入和删除算法，值得注意的是具体问题具体分析。根据给定的位置i，进行插入和