数据结构线性表课件.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)+lLocate(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),22,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 单链表：,存储地址 数据域 指针域 1Li 43 7Qian 13 13Sun 1 19Wang NULL 25Wu 37 31Zhao 7 37Zheng 19 43Zhou 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,作 业,在顺序存储结构的线性表中，写出在第三个元素前插入一个数据元素和删除第二个数据元素的操作，并绘图表示。在单链表中，假设head为队首指针，请给出在第二个元素后进行插入s结点和删除第二个结点的操作，并绘图表示。,54,1.已知线性表LA的数据元素（n个，n为偶数），现要求将LA拆开成两个新的线性表LB，LC。要求LB中的数据元素为LA中的奇数位序的数据元素（a1,a3,an-1），LC中的数据元素为LA中的偶数位序的数据元素（a2,a4,an）。2.已知线性表LA的数据元素（n个），现要求将LA的数据元素复制到另一个线性表LB中。3.设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（n个）。设在O(n)时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。,思考题,55,4.设线性表LA（a1,a2,am），LB（b1,b2,bn）。试编写一个算法，将LA、LB合并为线性表LC，使要求LA、LB和LC均以单链表为存储结构，且LC表利用LA和LB中结点空间，这里m和n的值没有保存在头结点中，并分析算法时间复杂度。,思考题,56,5.约瑟夫问题：设编号为1，2，n的n（n0）个人按顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列（采用循环单链表结构）。6.试比较顺序存储结构和链表存储结构的优缺点。,思考题,57,正确实现所要求的功能（能够通过测试）界面友好程序注释（可读性好）良好的编程风格健壮性,作业要求,