第2章-线性表

返回主目录 本章说明2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式存储结构2 4循环链表和双向链2 5一元多项式的表示及相加本章小结 本章说明 学习目标了解线性表的逻辑结构特性是数据元素之间存在着线性关系 在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构 用前者表示的线性表简称为顺序表 用后者表示的线性表简称为链表 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合 结合线性表类型的定义增强对抽象数据类型的理解 本章说明 重点和难点链表是本章的重点和难点 扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求 分清链表中指针p和结点 p之间的对应关系 区分链表中的头结点 头指针和首元结点的不同所指以及循环链表 双向链表的特点等 知识点线性表 顺序表 链表 有序表 线性结构的特点 在数据元素的非空有限集中存在唯一的一个被称做 第一个 的数据元素存在唯一的一个被称做 最后一个 的数据元素除第一个之外 每个元素都只有一个前驱除最后一个之外 每个元素都只有一个后继 1 线性表定义 一个线性表是n个数据元素的有限序列 2 1线性表的类型定义 例如 英文字母 A B C Z 是一个线性表 表中元素是一个字母 例如 星期 星期日 星期一 星期二 星期六 是一个线性表 表中的数据元素是星期中一天的名称 例如 在稍复杂的线性表中 一个数据元素可以是由若干个数据项组成的记录 含有大量记录线性表称为文件 如 一个学校的学生健康情况登记表 数据元素 2 线性表的结构特性 综上三个例子 我们可以如下描述线性表 线性表是n 0个数据元素a1 a2 ai 1 ai ai 1 an的有限序列 线性表的长度定义为线性表中数据元素的个数n 当n 0时 为空表 n 0时记为 a1 a2 an ai 1是ai的直接前驱 a1无直接前趋 ai 1是ai的直接后继 an无直接后继数据元素同构 相邻数据元素之间存在着序偶关系 所以可将线性表记为 a1 ai 1 ai ai 1 an 数据元素在线性表中的位置只取决于它们自己的序号 数据元素之间的相对位置是线性的 2 1线性表的类型定义 3 线性表的基本运算 表的初始化求表长取 或修改 表中的结点查找结点插入结点删除结点 不是全部操作 不同的问题需要的操作不同 2 1线性表的类型定义 4 抽象数据类型线性表的定义P19 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 1 2 n 基本操作 InitList L 创建一个空的线性表LDestroyList L 撤消L 2 1线性表的类型定义 ClearList L 将L重置为空表ListEmpty L 判L是否为空 空为TListLength L 返回表长度 元素个数 GetElemList L I e 用e返回L中第i个数据元素的个数 2 1线性表的类型定义 4 抽象数据类型线性表的定义P19 LocateElem L e compare 查找并返回第1个与e满足关系compare 的元素的位序 若没找到则返回0PriorElem L cur e pre e 找cur e并返回其前驱pre e 否则操作失败 pre e无定义NextElem L cur e next e 找cur e并返回其后继next e 否则操作失败 next e无定义ListInsert L i e ListDelete L i e ListTraverse L visit 依次对L的元素调用visit 如visit 失败 则操作失败 ADTList 2 1线性表的类型定义 例2 1两个线性表LA LB 将存在于线性表LB中而不在LA中的数据元素加入到线性表LA中 即LA LA LB算法思想 逐一取出LB中的元素 判断是否在LA中 若不在 则插入之 仅已知LA LB 1 先求出LA LB长度 2 取LB中一元素 e 若LB取空则转 4 3 如e不在LA中 则插入到LA中 转 2 4 结束 2 1线性表的类型定义 voidunin List La中不存在和e相同的元素 则插入之 union算法的时间复杂度 O ListLength LA ListLength LB 算法2 1实现 求表长 插入 取元素时间复杂度 O 1 2 1线性表的类型定义 例2 2线性表LA和LB是非递减有序的 将两表合并成新的线性表LC 且LC也是非递减的 算法思想 将LA LB两表中的元素逐一按序加入到一个新表LC中 即 1 LA LB均不空 则在LA中取一元素 a LB中取一元素 b 否则转 3 2 若ac 否则b c 转 1 3 若LA不空 则LA剩余部分放到LC尾 4 若LB不空 则LA剩余部分放到LC尾voidMergeList ListLa ListLb List i j k分别指向La Lb Lc初始位置 算法2 2 2 1线性表的类型定义 La len ListLength La Lb len ListLength Lb while i La len 算法2 2 2 1线性表的类型定义 while i La len La还有元素GetElem La i ai ListInsert Lc k ai while j Lb len Lb还有元素GetElem Lb j bj ListInsert Lc k bj MergeList时间复杂度 O ListLength LA ListLength LB 算法2 2 2 1线性表的类型定义 2 2线性表的顺序表示和实现 3 线性表的动态分配顺序存储结构 4 顺序线性表的操作 2 顺序表的特点 1 线性表的顺序表示 5 顺序表的优缺点 1 线性表的顺序表示 定义 用一组地址连续的存储单元存储一个线性表的数据元素 称为顺序表 元素地址计算方法 LOC ai 1 LOC ai L LOC ai LOC a1 i 1 L 其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址 实现 可用C语言的一维数组实现 2 2线性表的顺序表示和实现 typedefintDATATYPE defineM1000DATATYPEdata M 例typedefstructcard intnum charname 20 charauthor 10 charpublisher 30 floatprice DATATYPE DATATYPElibrary M 数据元素不是简单类型时 可定义结构体数组 或动态申请和释放内存DATATYPE pData DATATYPE malloc M sizeof DATATYPE free pData 2 顺序表的特点 特点 实现逻辑上相邻 物理地址相邻实现随机存取 2 2线性表的顺序表示和实现 3 线性表的动态分配顺序存储结构 用一维数组定义一个线性表 defineLIST INIT SIZE100 defineLISTINCREAMENT10typestruct ElemType elem 指向线性表起始地址的指针intlength 线性表实际存放数据长度intlistsize 线性表申请长度 SqList 2 2线性表的顺序表示和实现 4 顺序线性表的操作 顺序表容易实现访问操作 可随机存取元素 但插入和删除操作主要是移动元素 1 初始化操作算法思想 构造一个空表 设置表的起始位置表长可用空间 2 2线性表的顺序表示和实现 线性表初始化算法2 3 StatusInitList Sq SqList InitList Sq 2 2线性表的顺序表示和实现 2 插入定义 线性表的插入是指在第i 1 i n 1 个元素之前插入一个新的数据元素x 使长度为n的线性表 变成长度为n 1的线性表 需将第n至第i 共 n i 1 个元素后移 算法 Ch2 1 c x 插入算法2 4 在表L中的第i个元素之前插入e 见P24 判i值的合法性 1 i 表长 1 判表的空间满否 若满则增加分配 动态分配 从表元素n到i 依次后移一个位置 将e插入第i个位置 表长度增1 算法中定义的线性表是L 以结构形式出现 2 2线性表的顺序表示和实现 StatusListInsert Sq SqList 插入算法2 4实现 2 2线性表的顺序表示和实现 q 插入算法2 4实现 2 2线性表的顺序表示和实现 插入算法2 4时间复杂度 可见插入元素的时间主要花费在移动元素上 而移动元素的个数主要取决于插入的位置 设pi是在第i个元素之前插入一个元素的概率 则在长度为n的线性表中插入一个元素时需移动元素的平均次数为 若在任何位置上插入元素都是等概率 2 2线性表的顺序表示和实现 3 删除算法思想 删除第i个元素 将第 i 1 至第n个元素逐一向前移动一个位置 将长度为n ListInsert Sq a1 a2 ai 1 ai ai 1 an 变成长度为n n 1的线性表 a1 a2 ai 1 ai 1 an 需将第i 1至第n共 n i 个元素前移 算法 Ch2 1 c 在表L中删除第i个元素 放入e 见P24 判i值的合法性 1 i 表长n 取第i个元素 放入e 从i 1到表长n 依次前移 表长度减1 删除算法2 5思想 2 2线性表的顺序表示和实现 删除算法2 5实现 StatusListDelete Sq SqList ListInsert Sq 2 2线性表的顺序表示和实现 删除算法2 5时间复杂度 可见删除元素的时间主要花费在移动元素上 而移动元素的个数主要取决于删除的位置 设qi是删除第i个元素的概率 则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为 若在任何位置上插入元素都是等概率 2 2线性表的顺序表示和实现 查找算法2 6 IntLocateElem Sq SqListL ElemTypee Status compare ElemType ElemType 在顺序线性表L中找第一个值与e满足compare 的元素的位序 找到返回位序 否则返回0i 1 p L elem while i L length LocateElem Sq时间复杂度 O L length 2 2线性表的顺序表示和实现 合并算法2 7实现 IntMergeList Sq SqListLa SqListLb SqList 2 2线性表的顺序表示和实现 pa last La elem La length 1 pb last Lb elem Lb length 1 while pa pa last 插入Lb剩余部分 MergeList Sq 合并算法2 7 2 2线性表的顺序表示和实现 5 顺序表的的优缺点 优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点插入 删除操作需要移动大量的元素预先分配空间需按最大空间分配 利用不充分表容量扩充难 2 2线性表的顺序表示和实现 2 3线性表的链式存储结构 1 特点用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息 指针 用来表示线性表数据元素的逻辑关系结点数据域 元素本身信息指针域 指示直接后继的存储位置 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 43 13 1 NULL 37 7 19 25 头指针 2 线性链表的定义由n个结点链结成一个链表 称为线性链表或单链表 结点 Node 数据域 指针域 指针 链 头指针3 线性链表的实现typedefstructLnode ElemTypedata structLnode next Lnode LinkList 2 3线性表的链式存储结构 2 3线性表的链式存储结构 4 链式存储结构的优点插入 删除操作是不再需要移动大量的元素 但失去了顺序表的可随机存取特点 5 单链表的操作 1 取第i个元素算法思想 单链表是非随机存取结构 每个元素的位置信息都包含在前驱结点的信息中 所以取得第i个元素必须从头指针出发寻找 设置一个指针变量指向第一个结点 然后 让该指针变量逐一向后指向 直到第i个元素 2 3线性表的链式存储结构 StatusGetElem L LinkListL inti ElemType L为带头结点的单链表的头指针 当第i个元素存在时 其值赋给e并返回OK 否则返回ERRORp L next j 1 p指向第一个结点 j做计数器while p GetElem L 取结点算法2 8 2 3线性表的链式存储结构 2 插入操作 要在数据元素a和b之间插入元素x 算法思想 决定a和b之间的相邻关系是由a的指针决定的 若要实现插入 生成x结点 然后让a的指针指向x且x的指针指向b 实现三个元a x和b的逻辑关系 设p为指向结点a的指针 s为指向结点x的指针 则修改s a的指针 插入结点算法2 9 2 3线性表的链式存储结构 s next p next p next s StatusListInsert L ListLInk ListInsert L 插入结点算法2 9实现 2 3线性表的链式存储结构 3 删除操作 p next p next next 删除结点算法2 10实现 StatusListDelete L LinkList ListDelete L 2 3线性表的链式存储结构 动态创建链表算法 动态建立单链表算法 设线性表n个元素 逆位序输入数据元素建立一个单链表 h为头指针 动态创建链表算法2 11实现 VoidCreateList L LinkList CreatList L 2 3线性表的链式存储结构 4 单链表的合并例 将两个有序链表合并为一个有序链表 算法思想 设立三个指针pa pb和pc分别用来指向两个有序链表和合并表的当前元素 比较两个表的当前元素的大小 将小的元素链接到合并表Lc中 让合并表的当前指针指向该元素 然后 修改指针 在归并两个链表为一个链表时 不需要另建新表的结点空间 而只需将原来两个链表中结点之间的关系解除 重新建立关系 合并有序链表算法2 12 2 3线性表的链式存储结构 pc next pb pc next pa 每次链接pa或pb的一个结点后 便做如下操作 pa pa next pc pc next pa和pc分别后移一个位置或pb pb next pc pc next pb和pc分别后移一个位置 合并有序链表算法2 12实现 VoidMergeList L LinkListLa LinkListLb LinkList MergeList L 2 3线性表的链式存储结构 6 静态单链表有些高级语言没有指针 我们可以用数组来表示单链表 在数组中以整型游标来代替指针 这种用数组描述的链表称为静态链表 存储结构 defineMAXSIZE1000typedefstruct ElemTypedata intcur component SLinklist MAXSIZE S i cur指示第i 1个结点的位置 静态链表的操作和动态链表相似 以整型游标代替动态指针 2 3线性表的链式存储结构 S 0 cur为头指针 可以遍历整个静态链表 找到插入位置i 删除ZHENG s 6 cur s 7 cur SHI 5 intLocateElem SL SLinkListS ElemTypee 在静态单链线性表L中查找第1个值为e的元素 找到返回位序 否则返回0i S 0 cur while i 没找到则到链尾 i 0 LocateElem SL 算法2 13静态链表查找 2 3线性表的链式存储结构 假设由终端输入A集合元素并建立静态链表S 然后输入集合B元素在S中查找 若存在和B相同的元素 则从S中删除之 否则插入到S中 算法思想 将整个数组空间初始化成一个链表从备用空间取得一个结点将空闲结点链接到备用链表上 例2 3运算 A B U B A 2 3线性表的链式存储结构 Space 0 cur是备用空闲链表的头指针 space 1 cur是链表的头指针A c b e g f d B a b n f 初始化后 Space 0 cur是备用空闲链表的头指针 space 1 cur是链表的头指针A c b e g f d B a b n f A c b e g f d B a b n f 取B中元素在A中查找 若有与其相同的 则将A中的同元素删除 若没有则在A中插入 A输入结束 取a 在A中找 没有插入 删b space 2 cur A c b e g f d B a b n f 取B中元素在A中查找 若有与其相同的 则将A中的同元素删除 若没有则在A中插入 插入n 删除f space 5 cur space 6 cur voidInitSpace SL SLinkList Malloc SL 算法2 142 15静态链表初始化 2 3线性表的链式存储结构 voidFree SL SLinkList r指向表尾元素 输入A B元素个数 算法2 162 17静态链表初始化 2 3线性表的链式存储结构 for j 1 j m j 建立集合A的链表i Malloc SL space 分配结点 i为结点下标scanf space i data space r cur i r i 插入到表尾 r指向新表尾 forspace r cur 0 创建结束 表尾的指针为空for j 1 j n j 输入B中元素 在插入否删除scanf b p S k space S cur k指向集合A中第一个结点 算法2 17续 2 3线性表的链式存储结构 while k space r cur else for difference 算法2 17续 2 3线性表的链式存储结构 2 4循环链表和双向链表 1 循环链表 循环链表是表中最后一个结点的指针指向头结点 使链表构成环状特点 从表中任一结点出发均可找到表中其他结点 提高查找效率操作与单链表基本一致 循环条件不同单链表p或p next NULL循环链表p next H 2 双向链表在双向链表的结点中有两个指针域 分别指向前驱和后继 双向链表也可以有循环链表 双向链表的存储结构typedefstructDuLNode ElemTypedata structDuLNode prior structDuLNode next DuLNode DuLinklist 2 4循环链表和双向链表 p prior next p p next proir 双向链表的操作双指针使得链表的双向查找更为方便 快捷NextElem和PriorElem的执行时间为O 1 仅需涉及一个方向的指针的操作和线性链表的操作相同插入和删除需同时修改两个方向的指针 2 4循环链表和双向链表 插入算法 在表L中第i个位置之前插入元素e 设P指针 p GetElemP DuL L i 使其指向第i个结点 若p null 则i不存在 pnull 则为e申请结点 e赋值 插入 s prior p prior p prior next s s next p p prior s 算法实现 删除算法 删除表L中第i个元素 赋于e P37算法2 19 设P指针 p GetElemP DuL L i 使其指向第i个结点 p null 则i不存在 若pnull p指向第i个结点 将其赋给e 删除 p prior next p next p next prior p prior 算法实现 算法评价 T n O 1 3 带头结点的线性链表类型类型定义 typedefstructLNode ElemTypedata structLNode next Link Position typedefstruct 链表类型Linkhead tail intlen LinkList 2 4循环链表和双向链表 操作从实际应用出发 重新定义了线性表极其基本操作 基本操作定义见P37利用这些基本操作 很容易实现插入和删除操作 2 4循环链表和双向链表 算法2 20StatusListInsert L LinkList ListInsert L 2 4循环链表和双向链表 StatusMargeList L LinkList 2 4循环链表和双向链表 else DelFirst ha q Append Lc q pa NextPos Lb pb whileif pa Append Lc pa elseAppend Lc pb FreeNode ha FreeNode hb retureOK MergeList L 2 4循环链表和双向链表 2 5一元多项式的表示及相加 可用线性表P表示 但对S x 这样的多项式浪费空间 一般 其中 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构 也可以用单链表 一元多项式的表示 一元多项式相加 单链表的结点定义 TypedefstructPnode floatcoef intexpn structPnode next t