数据结构实用课件-第一章.ppt

1、第2章 线性表2.1 线性表的类型定义2.1 线性表的类型定义2.1 线性表的类型定义2. 线性表的基本操作 p19p20线性表的基本操作举例2.2 线性表的顺序表示和实现 1.顺序表线性表的顺序存储结构1.顺序表线性表的顺序存储结构2.顺序存储线性表的描述v C语言中静态分配描述 p222.顺序存储线性表的描述v C语言中静态分配描述 p222.顺序存储线性表的描述v C语言中静态分配描述 p222.顺序存储线性表的描述v C语言中静态分配描述 p222. 顺序表的描述1) C语言中动态分配描述 p222) 几个基本操作初始化插入 p24算法2.4 插入 p24算法2.4 插入（续）删除 p

2、24p25算法2.5 插入和删除算法时间分析查找查找的另一种描述合并 P26算法2.7的另外一种描述 合并 P26算法2.7建立递增插入递减插入4. 顺序表的分析作业顺序表之整体概念： elem01length-1 listsizelength数组下标 内存状态变量操作算法listsize-1初始化操作插入操作删除操作查找操作排序操作 . . . . . . . . . . . . .空闲表区 elem 顺序表之整体概念：顺序表有下列缺点：（1）插入、删除操作时需要移动大量元素， 效率较低；（2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。因此，在插入和删除操作是经常性操作的应用场合选

3、用顺序存储结构不太合适，此时可以选用链式存储结构，数据元素之间的逻辑关系由结点中的指针来指示。2.3 线性表的链式表示和实现1. 线性链表datanext1）线性链表的描述 p282）术语3）带头结点的单链表示意图 p28图2.72. 基本操作取元素（按序号查找） p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下搜索，直至找到第i个结点为止（j=i)插入元素p30 算法2.9在第i个元素之前插入，先找到第i-1个结点esP-next=s(2)(3)ps-next=p-nexta(1)b newnodenext = pnext; if ( pnext =NULL ) last

4、= newnode; pnext = newnode;删除元素p30 算法2.10 q = pnext; pnext = qnext; delete q; if ( pnext = NULL ) last = p;建立链表（头插法建表）p31 算法2.11在链表表头插入新结点，结点次序与输入次序相反。合并有序链表p31 算法2.12查找（按值查找）求长度集合并运算5-2 A=AB说明：3. 循环链表2）循环链表的操作合并两个循环链表循环链表的建立算法显示输出算法（带头结点）循环链表n双向链表是指在前驱和后继方向都能游双向链表是指在前驱和后继方向都能游历历(遍历遍历)的线性链表。的线性链表。1)

5、 双向链表的结点结构：双向链表的结点结构： 前驱方向前驱方向 (a)(a)结点结构结点结构 后继方向后继方向双向链表通常采用带表头结点的循环链双向链表通常采用带表头结点的循环链表形式。表形式。 p p r r i i o o r r ( ( 左左左左 链链链链 指指指指 针针针针 ) ) d d a a t t a a ( ( 数数数数 据据据据 ) ) n n e e x x t t ( ( 右右右右 链链链链 指指指指 针针针针 ) ) n对双向循环链表中任一结点的指针，对双向循环链表中任一结点的指针，有：有：p = ppriornext = pnextpriorn置空表：置空表： ppr

6、ior = p ; pnext = p; 2）双向循环链表存储结构的 描述 p35p36pprior = current;(1)pnext =currentnext; (2)currentnext = p; (3)pnextprior = p; (4)3）基本操作：双向循环链表的建立显示输出iniinnnxaxaxaxaaxP02210 )(nn阶多项式阶多项式Pn(x)有有n+1项。项。u 系数系数 a0, a1, a2, , anu 指数指数 0, 1, 2, , n。按升幂排列。按升幂排列n在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示 uP=(a0,a1, , a

7、n)n12mi12m999312999ADT Polynomial 数据对象数据对象: D=ai|ai TermSet, i=1,2,m, m0 TermSet中的每个元素中的每个元素包含一个表示系数的实数和表示指数的包含一个表示系数的实数和表示指数的整数整数数据关系：数据关系：R1=|ai-1,ai D,且且ai-1中的指数值中的指数值ai中的指数值中的指数值, i=2,n 基本操作：基本操作：ADT Polynomial typedef struct float coef; int expn;term, ElemType;/term用于本用于本ADT, ElemType为为LinkList

8、的数据对象名的数据对象名typedef LinkList polynomial;AH = 1 - 10 x6 + 2x8 +7x14BH = - x4 + 10 x6 - 3x10 + 8x14 +4x18n结果多项式另存结果多项式另存n扫描两个相加多项式，若都未检测完：扫描两个相加多项式，若都未检测完：u 若当前被检测项指数相等，系数相若当前被检测项指数相等，系数相加。若未变成加。若未变成 0，则将结果加到结果，则将结果加到结果多项式。多项式。u 若当前被检测项指数不等，将指数若当前被检测项指数不等，将指数小者加到结果多项式。小者加到结果多项式。n若有一个多项式已检测完，将另一个若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。多项式剩余部分复制到结果多项式。