线性表和数组.ppt

1 第二讲线性表 线性结构特点 在数据元素的非空有限集中 存在唯一的一个被称作 第一个 的数据元素 存在唯一的一个被称作 最后一个 的数据元素 除第一个外 集合中的每个数据元素均只有一个前驱 除最后一个外 集合中的每个数据元素均只有一个后继 2 2 1线性表的逻辑结构定义 一个线性表是n个数据元素的有限序列 例1英文字母表 A B C Z 是一个线性表 特征 元素个数n 表长度 n 0空表1 i n时ai的直接前驱是ai 1 a1无直接前驱ai的直接后继是ai 1 an无直接后继 3 顺序表 定义 用一组地址连续的存储单元存放一个线性表叫元素地址计算方法 LOC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址 特点 逻辑上相邻 物理地址相邻 随机存取 可用C语言的一维数组实现 2 2线性表的顺序存储结构 4 defineM1000intdata M 例structcard intnum charname 20 charauthor 10 charpublisher 30 floatprice structcarddata M 数据元素不是简单类型时 可定义结构体数组 5 1 插入节点定义 线性表的插入是指在第i 1 i n 1 个元素之前插入一个新的数据元素x 使长度为n的线性表加 变成长度为n 1的线性表 需将第i至第n共 n i 1 个元素后移 2 3线性表的插入和删除算法 6 x 7 简化插入算法 voidinsert intA n i X 类c语言描述 i表示第i个元素 intj if in 1 printf i值错 n else for j n j i j A j A j 1 将第i个元素及其后面的元素后移 A i 1 X n 线性表长度加1 8 2 删除 线性表的删除是指将第i 1 i n 个元素删除 使长度为n的线性表 变成长度为n 1的线性表 需将第i 1至第n共 n i 个元素前移 9 10 简化删除函数 voiddelete intA intn i i表示第i个元素 intj if in printf i值错 n else for j i j n 1 j A j 1 A j 元素依次前移 n 11 顺序存储结构的优缺点 优点逻辑相邻 物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点插入 删除操作需要移动大量的元素 预先分配空间需按最大空间分配 利用不充分 表容量难以扩充 12 特点 用一组任意的存储单元存储线性表的数据元素 每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息 结点数据域 元素本身信息指针域 指示直接后继的存储位置 2 3线性表的链式存储结构 13 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 链式存储 43 13 1 NULL 37 7 19 25 14 typedefstructnode datatypedata structnode link JD JD p 2 3 1单链表定义 结点中只含一个指针域的链表叫单链表 15 2 单链表的插入 实现插入算法主要完成三个基本操作 1 在单链表上找到插入位置 即找到第i个结点 可以用遍历的方法 即从表头起顺次访问单链表的结点 直至找到第i个结点 2 生成一个以x为值的新结点 可通过C的库函数malloc size 来产生 3 将新结点链入单链表中 需要改变相关结点的指针 如下面的图所示 单链表的插入 所谓插入是指在单链表中第i个结点 i 0 之后插入一个元素为x的结点 16 假设指针p指向单链表中的第i个结点 指针s指向已生成的新结点 链入新结点的操作如下 将新结点 s的链域指向结点 p的后继结点 即s next p next 将结点 p的链域指向新结点 即p next s 17 3 单链表的删除 删除单链表上一个其值为x的结点的主要操作是 1 用遍历的方法在单链表上找到该结点 2 从单链表上删除该结点 注意 从单链表上删除一个结点 需修改该结点的前一个结点的指针 如下面的图所示 18 假设指针q指向待删除结点的前一个结点 指针p指向要删除的结点 删除该结点的操作如下 将该结点的前一个结点 q的链域指向 p的后继结点 即q next p next 19 单链表特点 它是一种动态结构 整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取 查找速度慢 20 3 链表的应用3 1一元多项式的算术运算 设一个一元多项式为如果用数组来表示一元多项式 以各项的指数作为下标 将各个系数存入一维数组中 21 2 用单链表表示一元多项式 将单链表的每个结点对应着一元多项式中的一个非零项 它由三个域组成 分别表示非零项的系数 指数和指向下一个结点的指针 设两个一元多项式为 求此两一元多项式之和C x A x B x 22 3 运算规则 将二个一元多项式中所有指数相同项的系数相加 相加后 若和不为零 则构成 和一元多项式 中的一项 若和为零 则 和一元多项式 中无此项 所有指数不相同的项均抄到 和一元多项式 中 23 24 习题与练习 一 基础知识题1 试比较顺