《数据结构》课件1第2章 线性表.ppt
《《数据结构》课件1第2章 线性表.ppt》由会员分享,可在线阅读,更多相关《《数据结构》课件1第2章 线性表.ppt(96页珍藏版)》请在文库网上搜索。
1、2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示及相加一元多项式的表示及相加2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象知识点:知识点:重点:重点:难点:难点:线性表、顺序表、链表、有序表 顺序表与链表的描述方法;在两种存储结构上实现线性表的基本运算的算法。线性表在两种存储结构上的插入、删除算法及动态链表的建立和查找算法。课前思考:课前思考:抽象数据抽象数据类型的定型的定义由哪几部分由哪几部分组成?成?按数据元素之按数据元素之间的的逻辑关系不同,数据关系不同,数据结构有哪几构有哪几类?你能你能举出几个你熟悉
2、的出几个你熟悉的序列序列的例子来的例子来吗?数据数据对象、数据关系和基本操作三部分。象、数据关系和基本操作三部分。线性性结构、构、树型型结构、构、图状状结构和集合四构和集合四类。如:如:0,1,2,9,A,B,C,Z。1、线性表的定义:、线性表的定义:一个线性表(Linear List)是由n(n0)个数据元素(结点)所构成的有限序列。线性表逻辑地表示为:(a1,a2,an)。其中,n为线性表的长度,n=0时为空表。称i为ai在线性表中的位序。2、线性表的结构(逻辑结构)特点:、线性表的结构(逻辑结构)特点:a.它由n个同类型的元素组成;(一般)b.有且仅有一个第一个元素和最后一个 元素;c.
3、每个元素除第一个元素和最后一个元 素之外,有仅只有一个前驱和一个后继。2.1 2.1 线性表的类型定义线性表的类型定义3 3、抽象数据类型、抽象数据类型线性表线性表的定义:的定义:ADT List 数据对象数据对象:D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系:R1|ai-1,aiD,i=2,.,n 基本操作:基本操作:ADT List InitList(&L)1 1)初始化操作:)初始化操作:4 4、线性表的基本操作:、线性表的基本操作:2 2)结构销毁操作:结构销毁操作:DestroyList(&L)ListEmpty(L)3 3)线性表判空操作:)线性表判空
4、操作:ListLength(L)4)求线性表的长度:)求线性表的长度:PriorElem(L,cur_e,&pre_e)5)求数据元素的前驱:)求数据元素的前驱:NextElem(L,cur_e,&next_e)6)求数据元素的后继:)求数据元素的后继:GetElem(L,i,&e)7)取线性表中某个数据元素:)取线性表中某个数据元素:LocateElem(L,e,compare()8)定位操作:)定位操作:ListTraverse(L,visit()9)遍历线性表:)遍历线性表:ClearList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)10)线性表置
5、空操作:)线性表置空操作:11)插入操作:)插入操作:12)删除操作:)删除操作:假设上述基本操作已经实现,则可以利用上述定义的线性表基本操作,来基本操作,来实现其它更复杂的操作例例 2-2例例 2-1注注:这是P20-21页的部分的内容,先跳过。略略 用一组地址连续地址连续的存储单元 依次存放依次存放 线性表中的数据元素的存储结构线性表的线性表的起始地址起始地址称作线性表的基地址基地址 a1 a2 ai-1 ai an一一.概念概念顺序存储:顺序存储:顺序表:顺序表:用顺序存储的线性表就称为顺序表n为表的长度为表的长度2.2 2.2 线性表类型的实现线性表类型的实现-顺序映象顺序映象以“存储
6、位置相邻存储位置相邻”表示有序对即:即:LOC(ai)=LOC(ai-1)+C 一个数据元素所占存储量一个数据元素所占存储量 所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址三、地址计算公式三、地址计算公式存储地址存储地址 内在状态内在状态 数据元素在线性表的位序数据元素在线性表的位序a1a2aianb(基地址)基地址)b+Cb+(i-1)*cb+(n-1)*cb+(maxlen-1)*c12in空闲二二.特点:特点:1.逻辑上相邻的数据元素,赋以相邻的逻辑上相邻的数据元素
7、,赋以相邻的 存储位置;存储位置;2.存储密度高;存储密度高;存储密度存储密度 :数据元素的值所需的存储空间数据元素的值所需的存储空间d=该元素实际所需的存储空间该元素实际所需的存储空间3.便于便于随机存取;随机存取;4.不便于不便于插入、删除操作。插入、删除操作。(会引起大量结点的移动)(会引起大量结点的移动)例如例如四四.线性表的线性表的静态顺序存储结构静态顺序存储结构的的 C 语言描述语言描述(补充内容)补充内容)#define MAXLEN 80 /线性表的最大长度typedef struct ElemType elemMAXLEN;int length;SqListtp;/俗称静态顺
8、序表静态顺序表C语言中用一维数组一维数组来描述:说明一个静态顺序表L:Sqlisttp L;(1)查找:查找:在顺序表L中查找第i个元素。(2)求长度:求长度:求顺序表L中元素的个数。(3)插入:插入:在顺序表L中第i个元素前插入元素b。五五.基本操作在基本操作在静态静态顺序表上的实现顺序表上的实现L.elemi-1L.lengthfor(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/第i及其之后的所有元素后移一位,以空出插入位置 L.elemi-1=b;/插入 L.length+;/表长加1(4)删除:)删除:在顺序表L中删除第i个元素。for(j=i;j
9、=L.length-1;j+)L.elemj-1=L.elemj;/将第i元素之后的所有元素前移一位 L.length-;六六.线性表的线性表的动态顺序存储结构动态顺序存储结构的的 C 语言描述语言描述typedef struct SqList;/俗称 动态顺序表动态顺序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量Elemtype*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)P
10、22InitList(&L)/构造一个空表构造一个空表LocateElem(L,e,compare()/查找查找ListInsert(&L,i,e)/插入元素插入元素ListDelete(&L,i)/删除元素删除元素七、基本操作在动态顺序表上的实现七、基本操作在动态顺序表上的实现1.构造一个空线性表:构造一个空线性表:InitList(&L)1)申请分配)申请分配“足够应用足够应用”的线性表的存储空间的线性表的存储空间2)若分配失败,则结束函数的执行)若分配失败,则结束函数的执行3)若分配成功,则置:)若分配成功,则置:a)表的当前长度为表的当前长度为0 b)当前分配的存储容量为预分配空间的大
11、小当前分配的存储容量为预分配空间的大小 L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype)if(!L.elem)exit(OVERFLOW)L.length=0L.listsize=LIST_INIT_SIZEP23/算法算法2.3Status InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复杂度时间复杂度:O(1)L.elem=(ElemType*)malloc(LIST_ INIT_SIZE sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L
12、.length=0;L.listsize=LIST_INIT_SIZEreturn OK;P23/算法算法2.3例如:顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见,基本操作是:将顺序表中的元素逐个和给定值 e 相比较。2.定位操作:定位操作:LocateElem(L,e,compare()P25/算法算法2.6 int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的
13、数据元素,在顺序表中查询第一个满足判定条件的数据元素,/若存在,则返回它的位序,否则返回若存在,则返回它的位序,否则返回 0 0/LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂度为:为:i=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;*p+!=e;P25/算法算法2.63.插入操作 ListInser
14、t(&L,i,e)的实现:首先分析首先分析:1)要求:)要求:在第i个元素之前插入一个值为e的元素 问题:问题:插入元素时,线性表的 逻辑结构逻辑结构发生什么变化发生什么变化?P24/算法算法2.4(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加21 18 30 75 42 56 8721 18 30 75例如:例如:ListInsert_Sq(&L,5,66)L.length-10pppq87564266pL.length-1011for(;p=q;-p)q=&(L.elemi-1);/q
15、 指示插入位置p=&(L.elemL.length-1)*(p+1)=*p;/后移后移*q=e;/将e插入插入到q所指示的位置L.elem a.检测参数检测参数i是否合法及空间是否足够是否合法及空间是否足够 b.插入位置及之后的所有元素后移一位插入位置及之后的所有元素后移一位2)操作步骤:)操作步骤:q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;)若)若i L.length+1,插入位置,插入位置不合法不合法,算法结束;算法结束;)若)若L.length=L.listsize,则无空的,则无空的存储空存储空
16、 间,间,需增加分配。需增加分配。c.插入插入 d.修正表长修正表长*q=e;/插入插入e+L.length;/表长增表长增1 Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq 算法时间复杂度算法时间复杂度为为:O(ListLength(L)q=&(L.elemi-1);/q 指示插入位置指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移元素右移*q=e;/
17、插入插入e+L.length;/表长增表长增1return OK;元素右移元素右移3)算法:)算法:P24/算法算法2.4if(L.length=L.listsize)/当前存储空间已满,增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量if(i L.length+1)return ERROR;/插入位置不
18、合法考虑移动元素的平均情况考虑移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ,则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为:若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的,则移动元素的期望值移动元素的期望值为:首先分析:问题问题:删除元素时,线性表的逻辑 结构发生什么变化?4.删除删除操作操作 ListDelete(&L,i,&e)的实现:1)要求:)要求:将第i个位置上的元素删除P24/算法算法2.5(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的
19、长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 21 18 30 75 42 56 87 L.length-10pppqpp56 87p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;q=&L.elemL.length-1;/q为表尾元素的位置为表尾元素的位置for(;p=q;-p)*(p+1)=*p;/后移一位 若若i L.length,删除删除位置位置不合法不合法,算法结束;算法结束;3.3.修正表长修正表长修正表长修正表长 (表长减(表长减(表长减(表长减1 1)-L.length;/表长减1Status ListDelete_Sq
20、 (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移
21、3)算法:)算法:P24/算法算法2.5考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第 i 个元素的概率为 ,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为:若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值移动元素的期望值为:所以,若表长为所以,若表长为n,则插入和删除则插入和删除算法的时间复杂度都为:算法的时间复杂度都为:O(n)思考题:思考题:(P26/算法算法2.7)有两个有序的顺序表有两个有序的顺序表L(有(有m个个元素)和元素)和L(有(有n个元素)其元素均个元素)其元素均以从小到大的升序排列,编写一个函以从小到
22、大的升序排列,编写一个函数将它们合并成一个顺序表数将它们合并成一个顺序表LC,并,并要求要求LC仍保持其有序性。仍保持其有序性。分析:分析:假设假设LA=(6,7,10,21),),LB=(3,11,13,15,23,25,27)pa pb合并后得合并后得LC=(3,6,7,10,11,13,15,21,23,25,27)方法:方法:引进两个指针引进两个指针pa,pb分别指向分别指向LA和和LB中的某中的某个元素个元素,pc指示指示LC中当前插入元素的位置。中当前插入元素的位置。*pa 当*pa*pb时操作步骤操作步骤:(算法见教材P26/算法算法2.7)1.置初值置初值:1)pa=La.el
23、em;pb=Lb.elem;2)为Lc分配足够的存储空间;2.当当pa=La.elem+La.length-1和和 pb=Lb.elem+Lb.length-1时时,重复执行:重复执行:1)当*pa=*pb,将*pa插入到Lc中pc指针所指示的位置,pa指针后移;否则,将*pb插入到Lc中pc指针所指示的位置,pb指针后移。2)pc指针后移3.pa=La.elem+La.length-1,将La中的剩 余元素全部顺序插入到Lc 的尾部4.pbnext;j=1;/p p指向第一个结点,指向第一个结点,j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找,直到顺指针向后查找,直
24、到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)return ERROR;/参数参数i i不合法不合法 e=p-data;/取得第取得第 i i 个元素个元素return OK;P29/算法算法2.8问:问:能否将变量初始化改为能否将变量初始化改为p=L;j=0;?ai-1 2、线性表的插入操作 ListInsert(&L,i,e)在单链表中的实现:有序对有序对 改变为改变为 和和 eaiai-1P29/算法算法2.9 a.查找第查找第i个结点的前驱结点个结点的前驱结点(或确定待插入的位置或确定待插入的位置)b.产生新结点产生新结点S c.将将S插入到
25、链表指定的位置插入到链表指定的位置2)算法基本步骤:)算法基本步骤:s=(LinkList)malloc(sizeof(LNode);S-data=e;p=L;j=0;while(p&j next;+j;s-next=p-next;p-next=s;eai-1aiai-1sp(能否改为能否改为:p=L-next;j=1;)Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的单链表的头指针,本算法为带头结点的单链表的头指针,本算法 /在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_L
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构课件1第2章 线性表 课件 线性