第2章线性表(java版)探析.ppt

第二章 线性表;教学内容;教学重点与难点;课前思考;2.1.1 线性表的基本概念;2.1.1 线性表的基本概念;2.1.2 线性表的抽象数据类型描述;2.1.2 线性表的抽象数据类型描述;2.2.1 线性表的顺序存储;2.2.1 线性表的顺序存储;2.2.1 线性表的顺序存储;2.2.1 线性表的顺序存储;2.2.1 线性表的顺序存储;2.2.1 线性表的顺序存储;5. 顺序表类的描述;5. 顺序表类的描述;2.2.2 顺序表上基本操作的实现;1. 插入操作 insert(i, x)的实现（书中算法 2.1);1. 插入操作 insert(i, x)的实现（书中算法 2.1);1. 插入操作 insert(i, x)的实现（书中算法 2.1);1. 插入操作 insert(i, x)的实现（书中算法 2.1);1. 插入操作 insert(i, x)的实现（书中算法 2.1);;;;2. 删除操作 remove ( i )的实现（书中算法 2.2);2. 删除操作 remove ( i )的实现（书中算法 2.2) ;2. 删除操作 remove ( i )的实现（书中算法 2.2) ;;;;;2.2.3 顺序表应用举例;2.2.3 顺序表应用举例;2.2.3 顺序表应用举例;2.2.3 顺序表应用举例;2.3.1 单链表的表示;2.3.1 单链表的表示;1. 结点类的描述;2. 单链表类的描述（P40-41）;2. 单链表类的描述（P40-41）;2. 单链表类的描述（P40-41？）;2. 单链表类的描述（P40-41？）;2. 单链表类的描述（P40-41？）;2.3.2 单链表上基本操作的实现;2.3.2 单链表上基本操作的实现;按位序号查找操作 get(i）的算法;2.3.2 单链表上基本操作的实现;2.3.2 单链表上基本操作的实现;按值查找操作 indexOf(x）的算法;2.3.2 单链表上基本操作的实现; a. 查找第i个结点的前驱结点(或确定待插入的位置) b.产生新结点S c.修改链指针，将S插入到链表指定的位置;单链表上插入操作insert(i,x)的算法; 在不带表头结点的单链表上实现插入操作的算法应该如何描写？？;2.3.2 单链表上基本操作的实现; a. 查找待删除结点的前驱结点(即第i-1个结点） b.修改链指针，使待删结点从单链表中脱离出来 ;单链表上删除操作remove(i)的算法;2.3.2 单链表上基本操作的实现;方法一、头插法（逆位序法）;头插法创建单链表creat2(n)的算法;方法二、尾插法（顺序法）;尾插法创建单链表creat1(n)的算法;2.3.3 单链表的应用举例;2）删除多余结点的算法;3）程序代码 （P49）;2）程序代码 ;2.3.3 单链表的应用举例;2）两个有序表合并的算法思想;1.置初值：;2）主要代码 （P50）;if (da = db) { } else { };2.3.4 其它链表--;也就是说：;2.3.4 其它链表--; 例：在单循环链表上实现将线性表 (a0,a1,…,an-1)和（b0,b1,…,bm-1)合成一个线性表(a0,a1,…,an-1,b0,b1,…,bm-1)的运算。 ; a0 a1 … an-1 ;2.3.4 其它链表--;2.3.4 其它链表--;双向链表的操作特点：;2.3.4 其它链表--;2.3.4 其它链表--;2.3.4 其它链表--;2.3.4 其它链表--;?;【例1】编程实现一元多项式的加法 ; 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 ┄ em = n; P999(x) = 7x3 - 2x12 - 8x999;多项式的加法： A=2+3x+5x3+2x4 B=3+2x+4x2-5x3 实现： A=A+B;线性表的应用——一元多项式的加法;一元多项式加法-实现算法 （P59-60）;一元多项式加法-实现算法;一元多项式加法-实现算法;一元多项式加法-实现算法;本 章 小 结;作业：