数据结构线性表课件.ppt

1,第二章 线性表,线性结构的特点： 在数据元素的非空有限集中， 1）存在唯一的一个被称为“第一个”的数据元素 2）存在唯一的一个被称为“最后一个”的数据元素 3）除第一个之外，集合中的每个数据元素均只有一个前驱 4）除最后一个之外，集合中的每个数据元素均只有一个后继,2,第二章 线性表,重点： 理解线性表的逻辑结构特性 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作 熟练掌握线性表的链式存储结构的描述方法，灵活使用单链表，学会在相应存储结构下实现其各种基本算法及相关的时间性能分析,3,第二章 线性表,难点： 能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用场合 使用本章所学的基本知识设计有效算法，解决与线性表相关的应用问题,4,第二章 线性表,线性结构的特点： 在数据元素的非空有限集中， 1）存在唯一的一个被称为“第一个”的数据元素 2）存在唯一的一个被称为“最后一个”的数据元素 3）除第一个之外，集合中的每个数据元素均只有一个前驱 4）除最后一个之外，集合中的每个数据元素均只有一个后继,5,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表,6,一、定义 1. 线性表(linear_list)： 定义：简称为表，是n个元素的有限序列，通常可以表示成(a1, a2, , an)(n 0) 表的长度：表中所含元素的个数 n。 空表：长度为零的表 表项：表中的元素 ai 位序：数据元素 ai 在线性表中的位置,2.1 线性表的类型定义,7,1. 线性表： 线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息 例1. 26个字母(A, B, , Z) 例2. 班级人数(33, 32, 35, 30) 例3. 学生情况登记表：数据元素为记录，有若干个数据项组成（如姓名，学号，性别，年龄) p18图2.1,2.1 线性表的类型定义,8,2. 线性表的特点： 线性表中的数据元素是各种各样的，但同一线性表中的元素必定具有相同特性，即属于同一数据对象 相邻数据元素之间存在序偶关系 (a1, a2, , ai-1, ai, ai+1, , an) ai-1是 ai的直接前驱元素，ai+1是ai的直接后继元素 相当灵活，长度可以增长或缩短,2.1 线性表的类型定义,9,3. 线性表的基本运算 在线性表中插入一个元素； 在线性表中删除某个元素； 在线性表中查找某个特定元素； 在线性表中查找某个元素的后继元素； 在线性表中查找某个元素的前驱元素； 创建空线性表； 判别一个线性表是否为空表。 由基本运算可以构成其它较为复杂的运算,2.1 线性表的类型定义,10,二、抽象数据类型线性表的定义（P19） ADT List 数据对象：D=ai |aiElemSet, i=1, 2, , n, n 0 数据关系：R1=| ai-1, ai D, i= 2, , n 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在 操作结果：销毁线性表 ,2.1 线性表的类型定义,11,二、 抽象数据类型线性表的定义（P19） ClearList(&L) 初始条件：线性表L已存在 操作结果：将线性表L重置为空表 ListEmpty(L) 初始条件：线性表L已存在 操作结果：若L为空表，则返回TRUE， 否则返回FALSE ListLength(L) 初始条件：线性表L已存在 操作结果：返回L中数据元素个数,2.1 线性表的类型定义,12,二、 抽象数据类型线性表的定义（P19） GetElem( L, i, &e ) 初始条件：线性表L已存在，1iLengthList(L) 操作结果：用e返回L中第i个元素的值 LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( )是元素判定 函数 操作结果：返回L中第1个与e满足关系compare( )的 元素的位序。若这样的元素不存在，则 返回值为0 PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在 操作结果：若cur_e是L的元素，但不是第一个，则 用pre_e 返回它的前驱，否则操作失败，pre_e无定义,2.1 线性表的类型定义,13,二、 抽象数据类型线性表的定义（P19） NextElem( L, cur_e, &next_e ) 初始条件：线性表L已存在 操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义 ListTraverse(L, visit( ) 初始条件：线性表L已存在 操作结果：依次对L的每个元素调用函数visit( )。一 旦visit( )失败，则操作失败 PutElem( L, i, &e ) 初始条件：线性表L已存在，1iLengthList(L) 操作结果：L中第i个元素赋值同e的值,2.1 线性表的类型定义,14,二、 抽象数据类型线性表的定义（P19） ListInsert( &L, i, e ) 初始条件：线性表L已存在，1iLengthList(L)+1 操作结果：在L的第i个元素之前插入新的元素e，L 的长度增1 ListDelete(&L, i, &e) 初始条件：线性表L已存在且非空， 1iLengthList(L) 操作结果：删除L的第i个元素，并用e返回其值，L 的长度减1 ADT List,2.1 线性表的类型定义,15,三、应用 例2-1 假设利用两个线性表LA和LB分别表示两个集合A和B（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合AAB。 上述问题等价于：要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。 P20 算法2.1 分下列三步进行： 1）从线性表LB中依次取得每个数据元素; 2）依值在线性表LA中进行查访; 3）若不存在，则插入之。,2.1 线性表的类型定义,16,例2-2 归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性 void MergeList(List La, List Lb, List ,2.1 线性表的类型定义,17,if (ai = bj) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i = La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j = Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / merge_list 算法 2.2,2.1 线性表的类型定义,18,算法2.1的时间复杂度为 O(ListLength(LA)ListLength(LB)； 算法2.2的时间复杂度为 O(ListLength(LA)ListLength(LB) 例：清华大学1998年试题 线性表是具有n个（ ）的有限序列。 （1） 表元素 （2）字符 （3）数据元素 （4）数据项,2.1 线性表的类型定义,19,一、线性表的顺序表示： 以元素在计算机内存中的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，如下所示： Locate(ai+1) = Locate(ai) + l Locate(ai) = Locate(a1) + l *（ i1） 只要确定了首地址，线性表中任意数据元素都可以随机存取 称第一个数据元素的存储地址为线性表的起始地址，称作线性表的基地址,2.2 线性表的顺序表示和实现,20,2.2 线性表的顺序表示和实现,二、顺序表的定义：在C语言中可以用一维数组表示 # define LIST_INIT_SIZE 100 /表初始分配空间 #define LISTINCREMENT10 /空间分配增量基址 typedef struct ElemType *elem; /存储空间 int length; /当前长度 int listsize; /当前存储容量 SqList;,21,2.2 线性表的顺序表示和实现,三、应用 1、初始化线性表 Status InitList_Sq(SqList /InitList_Sq 时间复杂度 O(1),2.2 线性表的顺序表示和实现,2、插入元素 Status ListInsert_Sq(SqList ,23,2.2 线性表的顺序表示和实现,q= /ListInsert_Sq 在最坏情况下（即插入在第一个元素之前），所需移动元素数为L.length，时间复杂度为O(ListLength(L)。,24,2.2 线性表的顺序表示和实现,3、删除元素 Status ListDelete_Sq(SqList /ListDelete_Sq 在最坏情况下（即删除第一个元素），所需移动个数为L.length-1，时间复杂度近似为O(ListLength(L)。,25,2.2 线性表的顺序表示和实现,插入元素时的时间效率： 设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值（平均次数）为：,设,则有,26,2.2 线性表的顺序表示和实现,删除元素时的时间效率： 设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的次数的期望值（平均次数）为：,设,则有,27,2.2 线性表的顺序表示和实现,4、两个顺序表的合并 void MergeList_Sq(SqList la, SqList lb, SqList ,28,2.2 线性表的顺序表示和实现,while(pa = pa_last /插入lb的剩余元素 / End of MergeList_Sq(),29,2.2 线性表的顺序表示和实现,例：顺序表第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ ）。 A 110 B 108 C 100 D 120 例：若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）。（1in1） A O(0) B O(1) C O(n) D O(n2),30,2.3 线性表的链式表示及实现,一、定义 顺序表的缺陷：插入/删除耗费大量时间 线性链表：用一组任意单元表示数据元素和数据元素之间的关系（这些单元可以是连续的，也可以是不连续的） 其结点由两部分信息组成： （1）数据域：存储数据元素信息； （2）指针域：存储直接后继的存储位置（地址）。,31,2.3 线性表的链式表示及实现,2.3.1 单链表：,存储地址 数据域 指针域 1 Li 43 7 Qian 13 13 Sun 1 19 Wang NULL 25 Wu 37 31 Zhao 7 37 Zheng 19 43 Zhou 25,32,2.3 线性表的链式表示及实现,单链表：,线性链表的逻辑状态,33,2.3 线性表的链式表示及实现,单链表：,非空表,空表,34,二、线性链表的定义 typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型 */ struct LNode; /* 单链表结点类型 */ typedef struct LNode *PNode; /* 结点指针类型 */ struct LNode /* 单链表结点结构 */ ElemType data; LNode *next; ;,2.3 线性表的链式表示及实现,35,2.3 线性表的链式表示及实现,基本操作：1.取元素 Status GetElem_L(LinkList L, int i, ElemType /GetElem_L,36,单链表结点插入和删除时的情形,2.3 线性表的链式表示及实现,单链表,s-next = p-next; 注：顺序不能反 单链表插入结点时的情况,p-next = p-next-next; 单链表删除结点时的情况, p-next = s;,37,2.3 线性表的链式表示及实现,2.插入元素 Status ListInsert_L(LinkList /ListInsert_L,38,2.3 线性表的链式表示及实现,3.删除元素 Status ListDelete_L(LinkList /ListDelete_L,39,2.3 线性表的链式表示及实现,4.创建链表 Void CreateList_L(LinkList / CreateList_L,40,5.将两个有序链表归并为一个新的有序链表。 分析：有两个非递减有序链表La, Lb. 现归并La, Lb得到Lc。其条件为大于前者，不小于后者 Void MergeList_L(LinkList ,2.3 线性表的链式表示及实现,41,while (pa / MergeList_L 时间复杂度分析：O(n),2.3 线性表的链式表示及实现,42,单链表与顺序表的比较： 单链表的存储密度比顺序表低，它多占用了存储空间。但在许多情况下，链式的分配比顺序分配有效，顺序表必须分配足够大的连续的存储空间，而链表可以利用零星的存储单元 在单链表里进行插入、删除运算比在顺序表里容易得多 对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于在成批地、顺序地处理线性表中的元素时采用,2.3 线性表的链式表示及实现,43,2.3.2 循环链表 最后一个结点的指针域的指针又指回第一个结点 操作与线性链表基本一致 循环条件：p-next = = p-head 表空条件：p-head-next = = p-head,2.3 线性表的链式表示及实现,空循环 链表,非空循 环链表,44,2.3.3 双向链表 可以在单链表的每一个结点里再增加一个指向其前趋和后继的指针域。这样链表中有两条不同方向的链 优点：既可以找前驱，也可以找后继,2.3 线性表的链式表示及实现,空双向 链表,非空双 向链表,45,双向链表存储结构： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;,2.3 线性表的链式表示及实现,46,双向循环链表,2.3 线性表的链式表示及实现,空双向 循环链表,非空双向 循环链表,47,双向(循环)链表,2.3 线性表的链式表示及实现,删除双向链表的结点 p-prior-next=p-next; p-next-prior = p-prior;,往双向链表中插入结点 s-prior=p-prior; p-prior-next = s; s-next = p; p-prior = s,48,双向循环链表的插入算法： Status ListInsert_Dul(DuLinkList / ListInsert_Dul,2.3 线性表的链式表示及实现,49,双向循环链表的删除算法： Status ListDelete_Dul(DuLinkList / ListDelete_Dul,2.3 线性表的链式表示及实现,50,线性链表与顺序表的比较： 线性链表 优点：空间的合理利用；插入和删除时不需要移动 缺点：实现基本操作（如求表长）不如顺序表 数据元素的“位序”概念被淡化 很多场合下，是线性表的首选存储结构,2.3 线性表的链式表示及实现,51,一个带头结点的线性链表类型：P3738,2.3 线性表的链式表示及实现,52,小 结,了解线性表的逻辑结构特征 熟悉掌握顺序表和链表的描述方法、特点及有关概念 重点掌握顺序表上的插入和删除算法 重点掌握链表的建立、查找、插入和删除算法 掌握从时间和空间的角度综合比较顺序表以及链表的不同特点及其适用场合,53,作 业,在顺序存储结构的线性表中，写出在第三个元素前插入一个数据元素和删除第二个数据元素的操作，并