第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

本章主要内容 线性表 顺序表 单链表 线性表的变形 双向链表 循环链表 多项式及其运算

线性表 定义：n个数据元素的有限序列，记为(a1,a2,…,an) 线性表的性质 ai是线性表中的数据元素 n是线性表的长度 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 a1 an

线性表 线性表的一些基本操作 线性表的存储方式 查找 插入 删除 ∙∙∙∙∙∙ 基于数组 (顺序表) 基于链表 (链表) 基于散列 (散列表) ……

顺序表 顺序表是线性表基于数组的存储表示 a1 a2 ∙∙∙ ai ai+1 an 1 n-1 i i-1 存储空间 下标 SIZE-1

顺序表 顺序表的查找操作 25 34 57 16 48 09 63 ∙∙∙ 1 4 3 2 5 6 查找16 平均比较次数 1 4 3 2 5 6 查找16 平均比较次数 Search(Type x) { for(i=0; i<n; i++) if(a[i] == x) return i+1; return 0; } 假设每个值查找概率相同

顺序表 顺序表的插入操作 25 34 57 16 48 09 63 ∙∙∙ 1 4 3 2 5 6 7 顺序表大小加1 插入 50 1 4 3 2 5 6 7 顺序表大小加1 插入 50 平均移动次数：

顺序表 顺序表的删除操作 25 34 57 16 48 09 63 ∙∙∙ 1 4 3 2 5 6 顺序表大小减1 删除16 平均移动次数：

顺序表 顺序表的优点 无需保存与逻辑关系相关的信息 给定下标时，存取速度快 顺序表的缺点 插入删除操作移动开销大 需要固定的存储空间

单链表 单链表也是线性表的一种存储表示 data link 单链表的一个结点： struct LinkNode { Type data; LinkNode *link; }; LinkNode *first = null; a1 first a2 a3 an null ∙∙∙ 单链表结构：

单链表 单链表的查找操作 a1 first a2 a3 an ∙∙∙ null 查找a3 p p p p = first; while (p!=null) { if(p->data == a3)　{ return p; } p = p->link; return null;

单链表 单链表的插入操作 在非空表头部或空表插入 first a1 a2 ∙∙∙ anew null pnew->link = first; first = pnew; pnew

单链表 单链表的插入操作 在非空表头部或空表插入 在非空表中部或尾部插入 p ∙∙∙ ai ai+1 ∙∙∙ pnew->link = p->link; p->link = pnew; anew null pnew

单链表 单链表的删除操作 在单链表头部删除 first a1 a2 ∙∙∙ p p = first; first = first->link; delete p;

单链表 单链表的删除操作 在单链表头部删除 在单链表中部或尾部删除 p ∙∙∙ ai ai+1 ai+2 ∙∙∙ temp temp = p->link; p->link = temp->link; delete temp;

单链表 单链表的删除操作 在单链表头部删除 在单链表中部或尾部删除 空链表删除：无结点删除

带附加头结点的单链表 附加头结点 struct LinkNode { Type data; LinkNode *link; }; 不带附加头结点单链表结构： a1 first a2 a3 an null ∙∙∙ 不带附加头结点头指针初始化： LinkNode *first = null; a1 first a2 a3 an null ∙∙∙ 带附加头结点单链表结构： 带附加头结点时头指针初始化： LinkNode *first = new LinkNode; first->link = null;

带附加头结点的单链表 附加头结点 插入操作(空表、表头、中部、尾部操作相同) first pnew ax null a1 a2 a3 ∙∙∙ an null

带附加头结点的单链表 附加头结点 插入操作(空表、表头、中部、尾部操作相同) 删除操作(表头、中部、尾部操作相同) first temp = p->link; p->link = temp->link; Delete temp; a1 a2 a3 ∙∙∙ an null 删除a1 temp

带附加头结点的单链表 附加头结点优点 附加头结点缺点 空表和非空表的表示统一 在任意位置插入删除代码统一 浪费了一个节点的空间 作业： 顺序表和链表存储表示的优缺点 若表的长度经常动态变化，应使用什么存储表示？为什么？ 若表很少进行插入删除操作，应使用什么存储表示？为什么？ 针对不带附加头结点的单链表，找到值为x的结点 (假设只有一个结点的值为x)，并删除该结点，函数名 FindAndDelete(LinkNode *first, Type x)

单链表的应用：多项式运算 多项式

单链表的应用：多项式运算 多项式的表示 数组表示 动态数组表示（动态申请空间） 只保存非零系数 a0 a1 a2 ∙∙∙ an coef 下标 1 2 n maxDegree a0 a1 a2 ∙∙∙ an coef 下标 1 2 n a0 a1 a2 ∙∙∙ am coef 下标 1 2 n maxDegree e0 e1 e2 exp

单链表的应用：多项式运算 多项式的表示 单链表 PA(x) = 3 + 7x11 - 9x51 3 -9 51 null 7 11 -9 51 null 7 11 firstA

单链表的应用：多项式运算 多项式的加法运算 PA(x) = 3 + 4x2 - 6x3 PB(x) = 2x1 - 5x2 firstA 3 4 2 -6 3 null pa firstB 2 1 -5 2 null pb firstC null 3 null 2 1 null -1 2 null -6 3 null

单链表的应用：多项式运算 多项式的乘法运算 PA(x) = 3 + 4x2 - 6x3 PB(x) = 2x1 - 5x2 firstA 3 4 2 -6 3 null pa firstB 2 1 -5 2 null pb pb pb coef 1 2 3 4 5 3*2 3*-5 4*2 4*-5 -6*-5 + -6*2 6 -15 8 -32 30 Pc=6x-15x2+8x3-32x4+30x5

作业：使用无附加头结点单链表，实现多项式加法和乘法运算

静态链表 数组中每一个元素附加一个链接 first 25 45 92 57 11 36 78 null 1 2 3 4 5 6 7 25 1 2 3 4 5 6 7 25 92 57 36 78 11 45 1 7 3 6 5 -1 4 2