线性表.ppt
《线性表.ppt》由会员分享,可在线阅读,更多相关《线性表.ppt(79页珍藏版)》请在三一文库上搜索。
1、第2章 线性表,主要内容,线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 一元多项式的表示及相加,重点与难点,本章的重点 掌握顺序表和单链表上实现基本操作的算法。 本章的难点 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。,线性结构的特点,在数据元素的非空有限集中 存在唯一的一个被称做“第一个”的数据元素; 存在唯一的一个被称做“最后一个”的数据元素; 除第一个之外,集合中的每个数据元素均只有一个前驱; 除最后一个之外,集合中每个数据元素均只有一个后继。,2.1 线性表的逻辑结构,线性表的定义 线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有
2、限序列:(a1,a2,a3,an) 数据元素可以是一个数、一个符号、也可以是一幅图、一页书等。 数据元素也可由若干个数据项组成,这时常把数据元素称为记录,含有大量记录的线性表又称文件。,在数据元素的非空有限集中线性表中的数据元素类型多种多样; 同一线性表中的元素必定具有相同特性,即属同一数据对象; 相邻数据元素之间存在着序偶关系:ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。,2.1 线性表的逻辑结构,抽象数据类型线性表的定义如下: ADT List 数据对象: D=ai| ai(-ElemSet,i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D,i=2,
3、.,n 基本操作: InitList(&L) 操作结果:构造一个空的线性表L。 DestroyList(&L) 初始条件:线性表已经存在。 操作结果:销毁线性表L。,2.1 线性表的逻辑结构,ClearList(&L) 初始条件:线性表已经存在。 操作结果:将L重置为空表。 ListEmpty(L) 初始条件:线性表已经存在。 操作结果:若L为空表,则返回TRUE,否则返回FALSE。 ListLength(L) 初始条件:线性表已经存在。 操作结果:返回L中数据元素的个数。 GetElem(L,i,&e) 初始条件:线性表已经存在,1=i=ListLength(L). 操作结果:用e返回第i
4、个数据元素的值。,2.1 线性表的逻辑结构,LocateElem(L,e,compare() 初始条件:线性表已经存在,compare()是数据元素的判定函数。 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序,若这样的数据元素不存在则返回值为0。 PriorElem(L,cur_e,&pre_e) 初始条件:线性表已经存在。 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义 NextElem(L,cur_e,&next_e) 初始条件:线性表已经存在。 操作结果:若cur_e是L的数据元素,且不是最后一个,则
5、用next_e返回它的后继,否则操作失败,next_e无定义,2.1 线性表的逻辑结构,ListInsert(&L,i,e) 初始条件:线性表已经存在,=i=ListLength(L)+1. 操作结果:在中第i个元素位置之前插入新的数据元素e,的长度加。 ListDelete(&L,i,&e) 初始条件:线性表已经存在且非空,=i=ListLength(L). 操作结果:删除的第i个数据元素,并用e返回其值,的长度减。 ListTraverse(L,visit() 初始条件:线性表已经存在。 操作结果:依次对的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。 ADT L
6、ist,2.1 线性表的逻辑结构,2.1 线性表的逻辑结构,部分操作的类C实现(详见2-1.c) 例2.1 利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=AB。 例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。,2.1 线性表的逻辑结构,例2.1 利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=AB。 LA=(3,20,67,5,8, 55,32) LB=(60,5,30,22,8) LA=( 3,20,67,5,8, 55,32,60,30,22)
7、,2.1 线性表的逻辑结构,步骤描述(用自然语言描述) 1 从B中取出一个元素e; 2 查找A中是否存在该元素e? 3 若A中有元素e,转向4;否则,将该元素e插入到A; 4 判断B中元素是否取完? 5 若没有取完,转向1;否则,转向6; 6 结束。,2.1 线性表的逻辑结构,步骤描述(用类C语言描述) void union(List ,2.1 线性表的逻辑结构,例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。 LA=(3,5,8,11)/非递减有序 LB=(2,6,8,9,11,15,20)
8、LC=(2,3,5,6,8,8,9,11,11,15,20),2.1 线性表的逻辑结构,步骤描述(用自然语言描述) 1 初始化一张新的线性表LC; 2 分别从LA、LB中取出元素ai、bj; 3 比较ai、bj的大小? 4 若ai小,则将ai插入到LC,取LA中的下一个元素;否则将bj插入到LC,取LB中的下一个元素; 5 若LA、LB中的元素均未取完,转向3;否则转向6; 6 若LA未取完元素,将剩余元素依次插入到LC; 7 若LB未取完元素,将剩余元素依次插入到LC; 8 结束。,2.1 线性表的逻辑结构,步骤描述(用类C语言描述) void MergeList(List La,List
9、Lb,List ,2.2 线性表的顺序表示和实现,线性表的顺序表示 用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。,2.2 线性表的顺序表示和实现,C语言中的数组即采用顺序存储方式。,2.2 线性表的顺序表示和实现,2.2 线性表的顺序表示和实现,顺序表的特点 以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem;/存储空间基址 int length;
10、 /当前长度 int listsize;/当前分配的存储容量以一数据元素存储长度为单位 SqList;,2.2 线性表的顺序表示和实现,顺序表的插入与删除操作,2.2 线性表的顺序表示和实现,顺序表的插入算法ListInsert( /*ListInsert Before i */,2.2 线性表的顺序表示和实现,顺序表的删除算法ListDelete( ,2.2 线性表的顺序表示和实现,顺序表的构造算法 Status InitList_sq(SqList ,2.2 线性表的顺序表示和实现,顺序表中指定元素的定位算法 int LocateElem_sq(SqList l,ElemType e, S
11、tatus(*compare)(ElemType,ElemType) /在顺序线性表L中查找第1个值与e满足compare()的元素的位置,若找到返回该元素位置,若找不到,返回0 i=1;/初始查找位置 p=L.elem;/p的初值为第1个元素的存储位置 while(i=L.length ,2.2 线性表的顺序表示和实现,例2.1 利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=AB。(顺序存储) void UnionList(SqList La, SqList Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i
12、=0;iLb_len;i+)/从Lb中依次取出元素,若不在La中则插入。 GetElem(Lb,i, ,2.2 线性表的顺序表示和实现,例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。 (顺序存储) void MergeList(SqList La,SqList Lb,List /将Lb中的所有剩余元素插入到Lb ,2.2 线性表的顺序表示和实现,算法设计典型题目 集合的相关运算:并集、交集、差集 两张表的按条件合并 删除指定位置或指定条件的元素 一张表的有条件拆分 算法的核心操作 插入 删除,
13、2.3 线性表的链式表示和实现,顺序存储结构: 优点无需为表示结点间的逻辑关系而增加额外的存储空间;可方便地随机存取表中的任一元素。 缺点插入或删除运算不方便,除表尾的位置外,在表的其它位置上进行插入或删除操作都必须移动大量的结点,其效率较低; 由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配。因此当表长变化较大时,难以确定合适的存储规模。,2.3 线性表的链式表示和实现,线性链表的特点 该线性表中的数据元素可用任意的存储单元来存储。线性表中逻辑相邻两元素的存储空间可以是不连续的。 除存储本身的信息之外,还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象,称为结
14、点。(D,R),2.2 线性表的链式表示和实现,C语言中的链表即采用非顺序存储方式,2.3 线性表的链式表示和实现,用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示。,2.3 线性表的链式表示和实现,线性链表的分类: 从实现角度看,链表可分为:动态链表、静态链表; 从链接方式的角度看,链表可分为:单向链表、单向循环链表、双向链表、双向循环链表。,2.3 线性表的链式表示和实现,线性单向链表的存储实现: #define LIST_INIT_SIZE 100 struct LNODE ElemType data; struct LNODE *next; ; typedef str
15、uct LNODE LNode; typedef struct LNODE * LinkList;,2.3 线性表的链式表示和实现,注意: 区别指针变量、结点变量 区别头指针、头结点(不带头结点链表、带头结点链表) 内存分配: p=(LNode *)malloc(sizeof(LNode); 内存释放: free(p);,2.3 线性表的链式表示和实现,初始化操作InitList( /分配失败 ,2.3 线性表的链式表示和实现,取某序号元素操作GetElem(L,i, /GetElem_L,2.3 线性表的链式表示和实现,插入操作ListInsert(&L,i,e),2.3 线性表的链式表示和
16、实现,插入操作ListInsert( /ListInsert_L,2.3 线性表的链式表示和实现,删除操作ListDelete( /ListDelete_L,2.3 线性表的链式表示和实现,删除操作ListDelete(&L,i,&e),2.3 线性表的链式表示和实现,建立单链表操作createlist (LinkList &L) 后接法createlistr(LinkList &L) 前插法createlistf(LinkList &L),2.3 线性表的链式表示和实现,后接法建立链表createlistr(LinkList ,?,2.3 线性表的链式表示和实现,前插法建立链表createl
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性
链接地址:https://www.31doc.com/p-4098103.html