DS02-线性表_201009

1、-1-,第二章 线性表,2.1 线性表的抽象数据类型描述 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示和实现,-2-,总述,2章 4章讨论线性结构 线性结构的特点是： 存在唯一的一个被称作“第一”的数据元素； 存在唯一的一个被称作“最后一个”的数据元素； 除第一个外，集合中的每一个数据元素均只有一个前驱；4）除最后一个外，集合中的每一个数据元素均只有一个后继。,-3-,2.1 线性表的抽象数据类型描述,线性表的定义 线性表的ADT 对线性表ADT的应用,-4-,1 . 线性表的定义,同一线性表中的数据元素类型相同，即属于同一数据对象； 相邻数据元素之

2、间存在序偶关系。 若将线性表记为（a1, ,ai-1, ai, ai+1, ,an），则表中ai-1领先于ai， ai领先于ai+1，则称ai-1是ai的直接前驱，则称ai+1是ai的直接后继。当i=1n-1时，ai有且仅有一个直接后继，当i=2,n时，ai有且仅有一个直接前驱。 线性表中的元素的个数n(n 0)定义为线性表的长度，n=0时称为空表。,-5-,例1,26个英文字母的字母表(A, B, C, , Z),-6-,例2,一个学校的学生健康情况登记表:,-7-,2.线性表的ADT描述,-8-,ADT List 数据对象：D=ai | aiElemSet，i=1,2,n,n0 数据关系：

3、R1=| ai-1,ai, D,i=2,n 基本操作： InitList( ,-14-,void union( List ,-15-,例子2-2,问题描述： 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列。现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 思考？,-16-,思路,设两个指针i和 j分别指向LA和LB中某个元素，设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到LC中的元素c为：,-17-,void Merge( List La, List Lb, List ,-18-,算法时间复杂度分析,上述两个算法的时间复杂度取决于抽象数据

4、类型list定义中基本操作的执行时间。GetElem和 ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比。 则算法2.1的时间复杂度为 O(ListLength(LA) ListLength(LB) 算法2.2的时间复杂度则为 O( List Length(LA)+ListLength(LB),-19-,2.2 线性表的 顺序表示和实现,-20-,线性表的顺序存储,线性表的顺序表示，就是线性表的顺序存储，即用一组地址连续的存储单元依次存储线性表的数据元素。设每个元素占L个存储单元 由此可得： LOC(a i+1)=LOC(ai)+L LOC(a i

5、)LOC(a1)+(i-1)L,-21-,特点,以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。 对于这种存储方式，要访问第i个数据元素，就可以直接计算出ai的存储位置Loc(ai)，因而能随机存取表中任一数据元素。换言之，数据元素在顺序表中的存储位置取决于该数据元素在线性表中的序号。因此线性表的顺序存储结构是一种随机存取的存储结构。,-22-,线性表顺序存储结构的类型描述,/顺序表的动态分配的顺序存储结构 # define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 # define LISTINCREMENT 10 /线性表存储空间的分配增量 t

6、ypedef struct ElemType *elem； /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量 SqList ；,-23-,线性表顺序存储结构的类型描述,/顺序表的静态分配的顺序存储结构 # define LIST_SIZE 100 /线性表存储空间的分配量 typedef struct ElemType elemLIST_SIZE； /存储空间 int length; /当前长度 SqList ；,-24-,顺序表上基本运算,顺序表的初始化 按值查找 插入运算 删除运算,-25-,1. 顺序表的初始化,Status InitL

7、ist_Sq(SqList /InitList_Sq,-26-,思考？,ListEmpty(L) ListLength(L) GetElem(L, i, 插入和删除算法的时间复杂度为O(n); 求表长为O(1)，GetElem为O(1)。,在顺序表上进行插入和删除数据元素，平均要移动表中约一半的结点，平均时间复杂度是O(n)。,-40-,4. 线性表的按值查找,按值查找,返回位序,无返回0 int LocateElem( SqList L，ElemType e , status (*compare)(ElemType, ElemType ) p = L.elem； i = 1； while (

8、 i next; while( p ) printf(*p); p = p-next; ,-61-,单链表中结点的插入,算法思想： 让指针p定位在待插入结点的前一个结点 生成待插入结点x，并让指针s指向x； 将结点x插入链表,-62-,a,b,步骤1 ：生成一个数据域为x的结点。,p,x,s,data,next,3.插入运算,用C语句描述为： s = (LNode *)malloc(sizeof(LNode); s-data = x;,-63-,a,b,p,data,next,步骤2 ：将数据元素x插在a和b元素之间。,-64-,a,b,步骤3 ：将数据元素x插在a和b元素之间。,p,data

9、,next,s,-65-,a,b,用C语言描述为： s-next = p-next; p-next = s;,p,x,s,data,next,-66-,a,b,p,data,next,即： p-next = s; s-next = p-next;,s,注意语句的顺序,如改为以下顺序，什么情况会发生？,b结点的地址？,-67-,在带头结点单链表L中第i个位置之前插入元素e：,ai-1,ai,p,a1,L,定位到第i-1个元素结点,后插入,-68-,Status ListInsert_L(LinkList / LinstInsert_L,-69-,单链表中结点的删除,算法思想 指针p定位到待删除结

10、点的前一个结点上 将结点从单链表中取下来 释放结点所占用的存储空间,-70-,a,b,p,c,data,next,b,删除元素b：,4. 删除运算,用C语言语句描述为： p-next=p-next-next;,如何释放？,-71-,删除元素b并释放之：,a,b,p,c,data,next,b,步骤1：将b的地址记录下来 即：q=p-next;,q,-72-,a,b,p,c,data,next,b,删除元素b并释放之：,步骤2：让p-next指向b后第一个结点 即：p-next=q-next;,q,-73-,a,b,p,c,data,next,b,删除元素b并释放之：,q,步骤3：释放b结点 即

11、：free(q),-74-,Status ListDelete_L(LinkList / ListDelete_L,-75-,单链表的生成,不仅初始化单链表，并且生成单链表中相应的结点。 方法： 尾插法建表 头插法建表,-76-,头插法建表 void CreateList_L (LinkList /插入到头结点之后 / CreateList_L 尾插法建表？自己考虑。,-77-,练习,算法2.2：将两个有序表合并成一个有序表（ p20 ）。 现要求采用线性表的链式存储结构来实现此算法。,-78-,void MergeList_L( LinkList La, LinkList Lb, LinkL

12、ist / 释放 Lb 的头结点 / MergeList_L,-79-,小结,顺序表/单链表是最基本的数据结构, 掌握表示、建立、插入、删除、定位等基本运算、特点等。,-80-,3. 循环链表,-81-,什么是循环链表,空表,特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。 从表中任一结点出发均可找到表中其它结点。,-82-,说明,存储类型描述和单链表一致 循环链表的操作和单链表基本一致，差别仅在于链表搜索结束的标志不是p为空，而是p是否等于头指针。 实际的很多问题可以采用尾指针指示的单循环链表来进行处理。例如，两个循环链表合并。（如何实现？） 尾结点: p-next=H,-83

13、-,4. 双向链表,-84-,什么是双向链表,d-next-prior = d-prior-next = d,-85-,双向循环链表,非空的双向循环链表,-86-,双向循环链表,-87-,双向链表的存储类型描述,typedef struct DulNode ElemType data; struct DulNode *prior; struct DulNode *next; DulNode , *DuLinkList;,-88-,思考,ListLength GetElem LocateElem PrintList 插入和删除,-89-,双向链表中结点的删除,p-prior-next = p-n

14、ext；,p-next-prior = p-prior；,free(p)；,-90-,双向链表中结点的插入(在p结点之前),(1) S-prior = p-prior； (2) p- prior-next = S； (3) S-next = p； (4) p- prior = S；,-91-,详细算法参见教材p3637,-92-,从实际应用出发重新定义单链表,参加p37,typedef struct LNode /结点类型 ElemType data; struct LNode *next; *Link，*Position； typedef struct /链表类型 Link head , t

15、ail; /指向头结点和最后一个结点 int len; /线性链表中数据元素的个数 LinkList；,-93-,2.4一元多项式的表示和实现,-94-,提要,多项式的运算问题，是线性表应用的经典问题。 多项式的数学模型 顺序存储结构 链式存储结构,-95-,多项式的数学模型,一个多项式Pn(x)可按升幂写成,-96-,Rn(x)=Pn(x)+Qm(x),两个多项式相加Rn(x)=Pn(x)+Qm(x)的结果表示成线性表R,-97-,实例,在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。此时可以考虑存储系数和指数。,-98-,多项式的数学模型,其中pi是指数为ei的项的非零系数，且满足0=e1e2exp,p-exp exp: p结点是和多项式中的一项， p后移,