数据结构线性表课件

1、数据结构数字媒体技术教研室2 线性表2.1 线性表的定义和特点2.2 案例引入2.3 线性表的类型定义2.4 线性表的顺序表示和实现2.5 线性表的链式表示和实现2.6 顺序表和链表的比较2.7 线性表的应用22.6 顺序表和链表的比较空间性能比较时间性能比较2.6.1 空间性能的比较存储空间的分配顺序表：空间预先分配，表长扩充受限，容易导致空间浪费或短缺链表：不必预先分配空间，表长不受限制应用中若表长变化较大，难以预估存储规模时选用链表作为线性表存储结构2.6.1 空间性能的比较存储密度大小存储密度数据元素本身所占存储空间与整个结点所占存储空间之比存储密度越大，存储空间利用率越高2.6.1

2、空间性能的比较存储密度大小顺序表：存储密度为1，空间利用率100%链表：存储密度小于1，空间利用率小于100%链表结点除了数据元素对应的数据域外还额外具有指针域若线性表长度变化小，易于事先确定大小，则宜采用顺序结构2.6.2 时间性能的比较存取元素的效率顺序表随机存取结构，可在O(1)时间直接访问任意位置i上元素，取值操作效率高链表顺序存取结构，只能从表头开始依次向后遍历直至找到第i个元素，时间复杂度O(n)，取值效率较低若应用中主要操作和元素位置紧密相关，很少插入和删除操作，宜采用顺序表2.6.2 时间性能的比较插入和删除操作的效率顺序表平均要移动近一半的结点，时间复杂度O(n)当结点信息量

3、较大时，移动结点之时间开销尤其可观链表在确定插入或删除位置的前提下无需移动数据，只要修改指针即可，时间复杂度O(1)若进行频繁的插入或删除操作，宜采用链表2 线性表2.1 线性表的定义和特点2.2 案例引入2.3 线性表的类型定义2.4 线性表的顺序表示和实现2.5 线性表的链式表示和实现2.6 顺序表和链表的比较2.7 线性表的应用92.7 线性表的应用线性表的合并有序表的合并2.7.1线性表的合并【例2.1】求一般集合的并集问题已知两个集合A和B，现求解新的集合A=AB例如：设A=(7, 5, 3, 11)，B=(2, 6, 3)，则合并之后A=(7, 5, 3, 11, 2, 6)例2.

4、1分析利用两个线性表LA和LB分别表示集合A和B，线性表中的数据元素即为集合中的成员扩大线性表LA，将存在于LB中而不存在于LA中的元素插入到LA中从LB中依次取每个元素并在LA中查找，若不存在则插入LA表尾2.7.1线性表的合并例2.1算法分别获取LA表长m和LB表长n从LB中第1个元素开始，循环n次：从LB中去第i个元素赋给e在LA中查找元素e：不存在：将e插入到表LA最后存在：转下一次循环2.7.1线性表的合并算法分析基本操作取表LB位置i上的元素：GetElem()在LA中查找元素e：LocateElem()将元素e插入LA末尾：ListInsert()讨论两种存储结构顺序表链表2.7

5、.1线性表的合并算法分析顺序表GetElem()：与表长无关，O(1)ListInsert()：此时是特殊情况，即向LA表尾插入，则无需移动任何元素，故与表长无关，O(1)LocateElem()：耗时与LA表长m成正比算法时间复杂度：O(mn)2.7.1线性表的合并算法分析链表表GetElem()：耗时与LB表长n成正比，O(n)ListInsert()：耗时与LA表长成正比，O(m)LocateElem()：耗时与LA表长m成正比算法时间复杂度：O(mn)2.7.2 有序表的合并有序表：线性表中数据元素之间可以比较表中数据元素以非递增或非递减有序排列2.7.2 有序表的合并【例 2.2】求

6、解有序集合的并集问题已知两个有序集合A和B，都按非递减有序排列求一个新集合C=AB，且C中元素仍然按非递减有序排列如：A=(3,5,8,11)，B=(2,6,8,9,11,15,20)，则：C=(2,3,5,6,8,8,11,11,15,20)2.7.2 有序表的合并【例 2.2】分析将非递减排序的线性表LA和LB合并到新表LC，使其仍按非递减顺序排序LC中的元素或者来自LA，或者来自LB设LC为空表，设指针pa和pb分别指向LA和LB的元素a和b，则当前应当插入LC的元素c当ab时：c = a当ab时：c = b指针pa和pb初值均指向LA和LB的第一个元素，所指元素插入LC后则后移2.7.2 有序表的合并【例 2.2】有序表合并算法实现顺序表实现链表实现1. 顺序表实现算法步骤创建空间大小为m+n的空表LC指针pc初始化指向LC第一个元素指针pa和pb初始化，分别指向LA和LB首元素当指针pa和pb均为达到相应表尾时，比较二者所指向的元素的值，取其中较小的结点插入到LC中pc所指的当前位置1. 顺序表实现算法步骤如果pb已经到达LB表尾，则依次将LA剩余元素插入LC最后如果pa已经到达LA表尾，则依次将LB剩余元素插入LC最后LA35811LB2689111520papbLC2pb3pa5pa6pb8pa8p