《数据结构与算法》课件chap02

1、第二章 线性表Company Logo1、集合中必存在唯一的一个“第一元素”；2、集合中必存在唯一的一个“最后元素”；3、除了最后元素之外，均有唯一的后继；4、除了第一个元素之外，均有唯一的前驱。线性结构的基本特征Company Logo 线性表是最简单常用的线性数据结构，顺序存储结构 链式存储结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常

2、重要，同学们要很好地学习理解和掌握。第二章 线性表Company Logo 2.1 线性表概念及基本操作2.2 线性表的顺序存储和实现2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2.4 一元多项式的表示及相加第二章 线性表Company Logo 线性表是n 个类型相同数据元素的有限序列，通常记作（a1, a2, a3, , an ）。 姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .2. 1 线性表的概念例1、数学中的数列（11，13，15，17，

3、19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某单位的电话号码簿。一 线性表的逻辑结构 Company Logo2.1 线性表的概念说明：设 A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一线性表1） 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前驱，ai+1 是ai 的直接后继；3） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构

4、。线性表是一种线性数据结构；4） 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表；5） ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号；Company Logo2.1 线性表的概念 线性表的其他表示方式 二元组表示 L= ，其中D= a1,a2, a3, . an S= R R=, , 图示表示ai+1a1ai-1a2aian顶点：表示数据边：表示是数据间的顺序结构关系Company Logo抽象数据类型线性表的定义：ADT List 数据对象：ai|ai ElemSet,i=1,2,n,n=0 称n为线性表的表长； 称n0时

5、的线性表为空表 数据关系：R1=|ai-1,aiD，i=1,2,n设线性表为（a1,a2,ai,an）称i为ai在线性表中的位序 基本操作： InitList(&L) 操作结果：构造一个空的线性表。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表LCompany Logo2.1 线性表的概念线性表的基本操作(描述见课本p19)1 存取操作：存取线性表中第i 个数据元素；2 查找操作 ：在线性表中查找满足条件元素；3 插入操作 ：在线性表的第i个元素之前插入一个新元素;4 删除操作 ：删除线性表的第i个元素；5 分解操作 ：将一个线性表拆分为多个线性表；6 合并

6、操作: 7 排序 Company Logo2.1 线性表的概念说明1 上面列出的操作，只是线性表的一些常用的基本操作；2 不同的应用，基本操作可能是不同；3 线性表的复杂操作可通过基本操作实现；Company Logo 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合AAB。例 2-1 Company Logo 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。上述问题可演绎为：Company Logo1从线性表LB中依次察看每个数据元素

7、;2依值在线性表LA中进行查访; 3若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步骤：Company Logo GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); / 求线性表的长度 Lb

8、_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / unionCompany Logo若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered List)。试改变结构，以有序表表示集合。Company Logo 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列，设 LA=（3，5，8，11） LB=（2，6，8，9，11，15，20）

9、 LC=（2，3，5，6，8，8，9，11，11，15，20）例 2-2Company Logovoid MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lcwhile (i = La_len) & (j = Lb_len) / La 和 Lb 均不空 GetElem(La, i, ai); GetElem(Lb, j, bj); InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);Co

10、mpany Logoif (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中ListInsert(Lc, +k, bj); +j; while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素 / merge_li

11、stCompany Logo为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？Company Logo 2.2 线性表的顺序存储和实现 一 线性表的顺序存储结构顺序表 二 顺序表的基本操作算法 三 效率分析Company Logo 线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an 线性表（a1,a2, a3, . an ） 的顺序存储结构用顺序存储结构存储的线性表称为顺序表以“存储位置相邻”表示有序对即：LOC(ai)=LOC(ai-1

12、)+t 2.2 线性表的顺序存储和实现一 线性表的顺序存储结构顺序表 线性表的顺序存储结构Company Logo2.2 线性表的顺序存储和实现说明： 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来； 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) ta1a2ai-1aiai+1ant个单元Loc( a1 )Loc(ai )基地址Company Logo2.2 线性表的顺序存储和实现怎样在计算机上实现线性表的顺序存储结构？

13、 可用C语言中的一维数组来表示,但数组不是线性表,数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如: #define MAX 100 int vMAX;Company Logo2.2 线性表的顺序存储和实现顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef structElemType * elem; /线性表存储空间基址int length; /当前线性表长度int listsize; /当前分配的线性表存储空间大小 /（以sizeof

14、(ElemType)为单位）SqList;Company LogoSqList ：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配 length：存放线性表的表长； listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。Company Logo2.2 线性表的顺序存储和实现存放线性表元素 的一维数组设 A = （a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：顺序表通过元素的存储顺序反映线性表元素间的逻

15、辑关系 a1 a2ai-1 aiai+1 an01i-2i-1in-199L.elemL.lengthL.listsizen99Company Logo2.2 线性表的顺序存储和实现二、顺序表的基本操作算法插入 insert(v, x, i)功能：在顺序表v 中的第 i ( 1=i=n+1)个数据元素之前插入一个新元素x, 插入前线性表为 (a1, a2, a3, ai-1 ,ai, an ) 插入后,线性表长度为n+1, 线性表为 (a1, a2, a3, ai-1 , x, ai, an ) Company Logo2.2 线性表的顺序存储和实现插入前插入后插入操作示意图： a1 a2ai

16、-1 aiai+1 an01i-2i-1in-1MAX-1nP_len a1 a2 ai-1 x ai an01i-2i-1n-2n-1nMAX-1n+1P_lenCompany Logo2.2 线性表的顺序存储和实现int insert ( int v , int i, int x, int * p_len) int j; if (i*p_len) return ( 0 ); /* i 值不合法 for ( j=*p_len , j= i; j-) vj= v j-1; vi-1=x ; *p_len+; /* 插入x , 表长增1 return (1); 插入操作算法Company Log

17、o删除算法的主要步骤1）若i 不合法或表L空，算法结束，并返回 0；否则转2）2）将第i个元素之后的元素（不包括第i个元素）依次向前移动一个位置;3）表长-1 2.2 线性表的顺序存储和实现Company Logo2.2 线性表的顺序存储和实现int delete ( int v , int i, int * p_len) int j; if (i*p_len) return ( 0 ); /* i 值不合法 for ( j=i+1 , jdata0; /* 将基准置入 x 中*/ for(i=1;ilast;i+) if(L-dataidatai; for(j=i-1;j=0;j-) /*移

18、动*/ Ldataj+1=L-dataj; L-data0=y; 算法2.5Company Logo本算法中，有两重循环，外循环执行n1次，内循环中移动元素的次数与当前数据的大小有关，当第个元素小于 a1 时，要移动它上面的 i-1个元素，再加上当前结点的保存及置入，所以移动 i-1+2次，在最坏情况下，a1 后面的结点都小于 a1 ，故总的移动次数为 ： 即最坏情况下移动数据时间性能为()。这个算法简单但效率低，在第章的快速排序中时我们将介绍另一种划分算法，它的性能为(n)。 Company Logo2.2 线性表的顺序存储和实现 顺序表是线性表最简单的一种存储结构 小结顺序表的特点：1 通过元素的存储顺序反映 线性表中 数据元素之间的逻辑关系；2 可随机存取顺序表的元素；3 顺序表的插入、删除操作要通过移动元素实现；Company Logo作 业1、有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。（要求：写出算法思路，用类C写出算法并对算法的时间复杂度进行分析）2、比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A和