第2章线性表(java版)解答.ppt

一元多项式加法-实现算法 （P59-60） public PolynList addPolyn(PolynList LA, PolynList LB) { } while (qa != null qb != null) { PolynNode a = (PolynNode) qa.data; PolynNode b = (PolynNode) qb.data; switch (cmp(a, b)) { } } Node ha = LA.head; Node qa = LA.head.next; Node qb = LB.head.next; …… ha.next=(qa != null ? qa : qb); //插入剩余结点 return LA; 一元多项式加法-实现算法 switch (cmp(a, b)) { } case -1: // 多项式LA中当前结点的指数值小 ha.next=qa; ha = qa; qa = qa.next; break; …… 一元多项式加法-实现算法 switch (cmp(a, b)) { } case 0: // 两者的指数值相等 double sum = a.coef+ b.coef; if (sum != 0.0) { a.coef=sum; ha.next=qa; ha = qa; qa = qa.next; qb = qb.next; } else { qa = qa.next; qb = qb.next; } break; …… 一元多项式加法-实现算法 switch (cmp(a, b)) { } case 1: // 多项式LB当前结点的指数值小 ha.next=qb; ha = qb; qb = qb.next; break; …… 本 章 小 结 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构类的描述方法，以及线性表的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 作业： 习题二中的 三、1，3，4，6 3.19讲到此 * * * 3。26讲到此 * * 2.3.2 单链表上基本操作的实现 4. 单链表的建立操作creat(n)的实现 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。 方法： 头插法 尾插法 方法一、头插法（逆位序法） 操作步骤 当前链表是一个“空表”； 1、读入数据元素an-1， 建立结点并插入在表头； 2、读入数据元素an-2， 建立结点并插入在表头； an-1 an-1 an-2 3、依次类推，直至插入a0为止。 算法2.9 头插法创建单链表每次都是将创建的新结点插入到当前形成的单链表的表头。 头插法创建单链表creat2(n)的算法 public void create2(int n) throws Exception { } //算法2.9结束 Scanner sc = new Scanner(System.in); // 构造用于输入的对象 for (int j = 0; j n; j++) //从键盘读入n个数依次插入到表头 insert(0, sc.next() ); 时间复杂度：O（n) 方法二、尾插法（顺序法） 操作步骤 当前链表仍是一个“空表”； 1、输入数据元素a0， 建立结点并插入在表尾； 2、输入数据元素a1， 建立结点并插入在表尾； 3、依次类推，直至插入an-1为止。 算法