《c语言程序设计与数据结构》第13章ppt课件

C语言程序设计与数据结构 第十三章线性表 C语言程序设计与数据结构 本章学习内容 线性表的定义线性表的基本运算线性表的基本操作线性表的链式存储 C语言程序设计与数据结构 线性表是最基本 最常用的一种数据结构 它在计算机内的存储方法有两种 顺序存储和链式存储 它的主要基本操作是插入 删除和检索等 C语言程序设计与数据结构 13 1线性表及其基本运算 13 1 1线性表的定义线性表是最常用和最简单的一种数据结构 特点是数据元素之间是一种线性关系 数据元素 一个接一个的排列 英文字母表 A B Z 是线性表 表中每个字母是一个数据元素 结点 扑克牌的点数 2 3 10 J Q K A 也是一个线性表 其中数据元素是每张牌的点数和花色 C语言程序设计与数据结构 线性表是具有相同数据类型的n n 0 个数据元素的有限序列 通常记为 a1 a2 ai 1 ai ai 1 an 其中n为表长 n 0时称为空表 特点 表中相邻元素之间存在着顺序关系 将ai 1称为ai的直接前趋 ai 1称为ai的直接后继 就是说 对于ai 当i 2 n时 有且仅有一个直接前趋ai 1 当i 1 2 n 1时 有且仅有一个直接后继ai 1 而a1是表中第一个元素 它没有前趋 an是最后一个元素 无后继 C语言程序设计与数据结构 13 1 2线性表的基本运算 1 InitList L L是没有初始化的线性表 为L开辟空间并将L置为空表 2 DestroyList L 线性表L已存在 将L的存储空间释放 C语言程序设计与数据结构 3 ClearList L 线性表L已存在 将表L置为空表 4 emptyList L 线性表L已存在 如果L为空表则返回真 否则返回假 5 ListLength L 线性表L已存在 如果L为空表则返回0 否则返回表中的元素个数 C语言程序设计与数据结构 6 Locate L e 表L已存在 e为线性表中元素或与之同型元素 如果L中存在元素e 则返回元素e所在位置 如果L中不存在元素e 则返回0 7 Getelem L i 表L存在 i为整数 i值合法 即1 i ListLength L 返回线性表L中第i个元素的值 否则提示出错 C语言程序设计与数据结构 8 InsertList L i e 表L已存在 e的数据类型同线性表中数据元素 且1 i ListLength L l 在L中第i个位置前插入新的数据元素e 现行表L的长度加1 9 DeleteList L i e 表L已存在且非空 i为整数 如果1 i ListLength L 删除线性表中的第i个数据元素 并用e返回其值 函数值返回真 线性表的长度减1 否则函值返回假 C语言程序设计与数据结构 13 2线性表的顺序表示及基本操作 13 2 1线性表的顺序表示线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素 用这种存储形式存储的线性表称为顺序表 C语言程序设计与数据结构 13 2 2顺序表的基本操作实现1 初始化StatusInitList sq SqList 成功返回OK InitList sq C语言程序设计与数据结构 2 插入运算在线性表L中第i个数据元素之前插入数据元素e 插入后使原表长为n的表 a1 a2 ai 1 ai ai 1 an 成为表长为n 1表 a1 a2 ai 1 e ai ai 1 an 其中i的取值范围为1 i n 1 C语言程序设计与数据结构 用类C语言实现顺序表的插入 StatusListInsert sq SqList ListInsert sq C语言程序设计与数据结构 3 删除运算线性表的删除运算是指将表中第i个元素从线性表中去掉 删除后使原表长为n的线性表成为表长为n 1的线性表 C语言程序设计与数据结构 用类C语言实现顺序表的删除运算intListDelete SQ LIST L inti EntryType e if IsEmpty L returnERROR 检测线性表是否为空if iL length returnERROR 检查i值是否合理 e L item i 1 将欲删除的数据元素内容保留在e所指示的存储单元中for j i jlength 1 j 将线性表第i 1个元素之后的所有元素向前移动L item j 1 L item j L length 线性表长度减1returnOK ListDelete C语言程序设计与数据结构 13 3线性表的链式存储 线性表的链式存储结构不需要用地址连续的存储单元来实现 因为它不要求逻辑上相邻的两个数据元素物理上也相邻 它是通过 链 建立起数据元素之间的逻辑关系 因此对线性表的插入 删除不需要移动数据元素 C语言程序设计与数据结构 13 3 1单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的 为建立起数据元素之间的线性关系 对每个数据元素ai 除了存放数据元素的自身的信息ai之外 还需要和ai一起存放其后继ai 1所在的存贮单元的地址 这两部分信息组成一个 结点 C语言程序设计与数据结构 链表是由一个个结点构成的 结点定义如下 typedefstructLNode ElemTypedata 数据域structLNode next 指针域 LNode LinkList C语言程序设计与数据结构 通常我们用 头指针 来标识一个单链表 如单链表L 单链表H等 是指某链表的第一个结点的地址放在了指针变量L H中 头指针为 NULL 则表示一个空表 C语言程序设计与数据结构 1 查找操作用类C语言实现单链表上的查询 查找第i个元素 StatusGetElem L LinkListL inti ElemType GetElem L C语言程序设计与数据结构 2 插入操作StatusListInsert L LinkList LinstInsert L C语言程序设计与数据结构 3 删除操作StatusListDelete L LinkList ListDelete L C语言程序设计与数据结构 13 3 2循环链表对于单链表而言 最后一个结点的指针域是空指针 如果将该链表头指针置入该指针域 则使得链表头尾结点相连 就构成了单循环链表 C语言程序设计与数据结构 单循环链表可以从表中任意结点开始遍历整个链表 有时对链表常做的操作是在表尾 表头进行 此时可以改变一下链表的标识方法 不用头指针而用一个指向尾结点的指针R来标识 可以使得操作效率得以提高 C语言程序设计与数据结构 p R1 next 保存R1的头结点指针 R1 next R2 next next 头尾连接 free R2 next 释放第二个表的头结点 R2 next p 组成循环链表 C语言程序设计与数据结构 13 3 3双向链表单链表的结点中只有一个指向其后继结点的指针域next 因此若已知某结点的指针为p 其后继结点的指针则为p next 而找其前驱则只能从该链表的头指针开始 顺着各结点的next域进行 每个结点再加一个指向前驱的指针域 用这种结点组成的链表称为双向链表 C语言程序设计与数据结构 双向链表结点的定义如下 typedefstructDuLnode pointer typedefstructDuLNode datatypedata pointerprior next DuLNode C语言程序设计与数据结构 双向链表通常也是用头指针标识 通过某结点的指针p即可以直接得到它的后继结点的指针p next 也可以直接得到它的前驱结点的指针p prior 这样在有些操作中需要找前驱时 则勿需再用循环 图13 8是带头结点的双向循环链表示意图 C语言程序设计与数据结构 1 双向链表中结点的插入 设p指向双向链表中某结点 s指向待插入的值为x的新结点 将 s插入到 p的前面 插入示意图如图13 9所示 操作如下 s prior p prior p prior next s s next p p prior s C语言程序设计与数据结构 2 双向链表中结点的删除 设p指向双向链表中某结点 删除 p 操作示意图如图13 10所示 操作如下 p prior next p next p next prior p prior C语言程序设计与数据结构 13 4典型习题分析解答 1 在单链表 双链表和单循环链表中 若仅知道指针P指向某结点 不知道头指针 能否将结点 P从相应的链表中删去 分析 在单链表中 由于无法找到结点 P的直接前驱的位置 所以无法删除该结点 在双链表中 结点 P的前驱位置是P PRIOR 因此可直接将 P删除掉 在单循环链表中 可从P结点依次扫描到其前驱结点 故也能删除掉该结点 C语言程序设计与数据结构 2 试分别用顺序表和单链表作为存储结构 实现线性表的就地逆置 分析 顺序表VOIDREVERSELIST SQLIST L DATATYPET INTI J FOR I 0 ILENGTH 2 1 I J L LENGTH 1 I T L ELEM I L ELEM I L ELEM J L ELEM J T C语言程序设计与数据结构 分析 单链表VOIDREVERSELIST LINKLIST L LNODE P Q P L NEXT L NEXT NULL WHILE P Q P NEXT P NEXT L NEXT L NEXT P P Q C语言程序设计与数据结构 3 已知L1和L2分别指向两个单链表的头结点 且已知其长度分别为M和N 试