数据结构实用课件第一章.ppt
- 文档编号:18022580
- 上传时间:2023-08-05
- 格式:PPT
- 页数:68
- 大小:522KB
数据结构实用课件第一章.ppt
《数据结构实用课件第一章.ppt》由会员分享,可在线阅读,更多相关《数据结构实用课件第一章.ppt(68页珍藏版)》请在冰点文库上搜索。
第2章线性表,2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加,2.1线性表的类型定义,线性结构的特点:
在数据元素的非空有限集中,1)有且仅有一个开始结点;2)有且仅有一个终端结点;3)除第一个结点外,集合中的每个数据元素均有且只有一个前驱;4)除最后一个结点外,集合中的每个数据元素均有且只有一个后继。
线性序列:
线性结构中的所有结点按其关系可以排成一个序列,记为(a1,ai,ai+1,an),2.1线性表的类型定义,1.线性表1)线性表是n(n0)个数据元素的有限序列。
2)线性表是一种最常用且最简单的数据结构。
含有n个数据元素的线性表是一个数据结构:
List=(D,R)其中:
D=ai|aiD0,i=1,2,n,n0R=N,N=|ai-1,aiD0,i=2,3,nD0为某个数据对象数据的子集特性:
均匀性,有序性(线性序列关系),2.1线性表的类型定义,1.线性表3)线性表的长度及空表线性表中数据元素的个数n(n0)定义为线性表的长度当线性表的长度为0时,称为空表。
ai是第i个数据元素,称i为ai在线性表中的位序。
2.线性表的基本操作p19p20,1)InitList(&L)初始化,构造一个空的线性表2)ListLength(L)求长度,返回线性表中数据元素个数3)GetElem(L,i,&e)取表L中第i个数据元素赋值给e4)LocateElem(L,e)按值查找,若表中存在一个或多个值为e的结点,返回第一个找到的数据元素的位序,否则返回一个特殊值。
5)ListInsert(&L,i,e)在L中第i个位置前插入新的数据元素e,表长加1。
6)ListDelete(&L,i,e)删除表中第i个数据元素,e返回其值,表长减1。
线性表的基本操作举例,例2-1求A=ABP20算法2.1时间复杂度:
LocateElem()执行次数O(ListLength(A)*ListLength(B)例2-2合并LA和LB到LC中P20-21算法2.2时间复杂度:
ListInsert()执行次数O(ListLength(LA)+ListLength(LB),2.2线性表的顺序表示和实现1.顺序表线性表的顺序存储结构,1)在计算机内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。
2)假设线性表的每个元素需占用L个存储单元,并以所占的第一个单元的存储地址作为数据元素的起始存储位置,则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系:
Loc(ai+1)=Loc(ai)+L一般来说,线性表的第i个元素ai的存储位置为:
Loc(ai)=Loc(a1)+(i-1)*L其中Loc(a1)是线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置或基地址。
1.顺序表线性表的顺序存储结构,3)线性表的顺序存储结构示意图p22图2.2用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。
根据线性表的顺序存储结构的特点,只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,所以,线性表的顺序存储结构是一种随机存取的存储结构。
#defineLIST_MAX_LENTH100/或者N/或者是一个常数typedefstructElemTypeint*elem;intlength;SqList;SqListL;,2.顺序存储线性表的描述,C语言中静态分配描述p22,求置空表StatusClearList(,2.顺序存储线性表的描述,C语言中静态分配描述p22,求长度StatusListlength(SqListL)length=L.length;returnOK;,2.顺序存储线性表的描述,C语言中静态分配描述p22,初始化StatusInitList_SqList(SqListL)L.elem=(*int)malloc(LIST_MAX_LENGTH*sizeof(int);if(!
L.elem)exit(Overflow);L.length=0;returnOK;,2.顺序存储线性表的描述,C语言中静态分配描述p22,2.顺序表的描述1)C语言中动态分配描述p22,#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize;SqList;SqListL;说明:
elem数组指针指向线性表的基地址;length指示线性表的当前长度;listsize指示顺序表当前分配的存储空间大小。
当空间不足时,再分配的存储空间增量为LISTINCREMENT*sizeof(ElemType),2)几个基本操作初始化,p23算法2.3StatusInitList_SqList(SqList,插入p24算法2.4,StatusListInsert_sq(SqList需将第n(即L.length)至第i个元素向后移动一个位置。
注意:
C语言中数组下标从0开始,则表中第i个数据元素是L.elemi-1。
插入p24算法2.4,函数realloc的格式及功能格式:
void*realloc(void*p,unsignedsize)功能:
将p所指向的已分配内存区域的大小改为size。
size可以比原来分配的空间大或小。
插入(续),q=,删除p24p25算法2.5,StatusListDelete_sq(SqListreturnOK需将第i+1至第L.length个元素向前移动一个位置,插入和删除算法时间分析,用“移动结点的次数”来衡量时间复杂度。
与表长及插入位置有关。
插入:
最坏:
i=1,移动次数为n最好:
i=表长+1,移动次数为0平均:
等概率情况下,平均移动次数n/2删除:
最坏:
i=1,移动次数为n-1最好:
i=表长,移动次数为0平均:
等概率情况下,平均移动次数(n-1)/2,查找,p25p26算法2.6intLocateElem_Sq(SqListL,ElemTypee)i=1;while(i=L.length,查找的另一种描述,i=1;p=L.elem;while(i=L.length,合并P26算法2.7的另外一种描述,voidMergeList_Sq(SqListLa,SqListLb,SqList,合并P26算法2.7,voidMergeList_Sq(SqListLa,SqListLb,SqList,建立,#defineLIST_INIT_SIZE100StatusCreateList_Sq(SqList,递增插入,StatusOrderInsert_Sq(SqList,递减插入,StatusDeOrderInsert_Sq(SqList,4.顺序表的分析,1)优点顺序表的结构简单顺序表的存储效率高,是紧凑结构顺序表是一个随机存储结构(直接存取结构)2)缺点在顺序表中进行插入和删除操作时,需要移动数据元素,算法效率较低。
对长度变化较大的线性表,或者要预先分配较大空间或者要经常扩充线性表,给操作带来不方便。
原因:
数组的静态特性造成,作业,2.1编写程序,建立并显示一个有10个数据元素的顺序线性表。
2.2实现顺序线性表的插入、查找、删除等算法。
顺序表之整体概念:
elem,0,1,length-1,listsize,length,数组下标,内存状态,变量,操作算法,listsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,.,.,.,.,空闲,表区,elem,顺序表之整体概念:
顺序表有下列缺点:
(1)插入、删除操作时需要移动大量元素,效率较低;
(2)最大表长难以估计,太大了浪费空间,太小了容易溢出。
因此,在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适,此时可以选用链式存储结构,数据元素之间的逻辑关系由结点中的指针来指示。
2.3线性表的链式表示和实现1.线性链表,特点:
在内存中用一组任意的存储单元来存储线性表的数据元素,用每个数据元素所带的指针来确定其后继元素的存储位置。
这两部分信息组成数据元素的存储映像,称作结点。
结点:
数据域+指针域(链域)链式存储结构:
n个结点链接成一个链表线性链表(单链表):
链表的每个结点只包含一个指针域。
data,next,单链表(SinglyLinkedList),first头指针last尾指针,指针为空单链表由头指针唯一确定,因此常用头指针的名字来命名。
如表first.,单链表的存储映像,1)线性链表的描述p28,typedefstructLNodeElemTypedata;StructLNode*next;LNode,*LinkList;LinkListL;/L是LinkList类型的变量,表示单链表的头指针,2)术语,头指针:
指向链表中第一个结点第一个数据元素结点(开始结点)头结点:
有时在单链表的第一个数据元素结点之前附设一个结点,称之头结点。
说明:
头结点的next域指向链表中的第一个数据元素结点。
对于头结点数据域的处理:
a.加特殊信息b.置空c.如数据域为整型,则在该处存放链表长度信息。
3)带头结点的单链表示意图p28图2.7,由于开始结点的位置被存放在头结点的指针域中,所以对链表第一个位置的操作同其他位置一样,无须特殊处理。
无论链表是否为空,其头指针是指向头结点的非空指针,因此对空表与非空表的处理也就统一了,简化了链表操作的实现。
非空表空表,2.基本操作,1)取元素p29算法2.82)插入元素p30算法2.93)删除元素p30算法2.104)建立链表p30p31算法2.115)有序链表的合并p31算法2.126)查找(按值查找)7)求长度8)集合的并运算,取元素(按序号查找)p29算法2.8从链表的头指针出发,顺链域next逐个结点往下搜索,直至找到第i个结点为止(j=i),StatusGetElem_L(LinkListL,inti,ElemType,插入元素p30算法2.9在第i个元素之前插入,先找到第i-1个结点,StatusListInsert_L(LinkList,e,s,P-next=s,
(2),(3),p,s-next=p-next,a,
(1),b,在带表头结点的单链表第一个结点前插入新结点,newnodenext=pnext;if(pnext=NULL)last=newnode;pnext=newnode;,删除元素p30算法2.10,StatusListDelete_L(LinkList,q=pnext;pnext=qnext;deleteq;if(pnext=NULL)last=p;,从带表头结点的单链表中删除第一个结点,建立链表(头插法建表)p31算法2.11在链表表头插入新结点,结点次序与输入次序相反。
voidCreateList_L(LinkList尾插法建表:
将新结点插到链表尾部,须增设一个尾指针last,使其始终指向当前链表的尾结点。
合并有序链表p31算法2.12,voidMergeList_L(LinkListLa,LinkListLb,LinkList,查找(按值查找),intLinkLocate_L(LinkListL,intx)inti;LinkListp;p=L-next;i=1;while(p!
=NULL,求长度,intLinkLength_L(LinkListL)intj;LinkListp;p=L-next;j=0;while(p)p=p-next;j+;return(j);注意:
p=NULL与p-next=NULL是不同的。
总结:
带头结点:
链表置空L-next=NULL;判断是否为空的条件if(L-next=NULL)不带头结点:
则置空L=NULL;判空条件if(L=NULL),集合并运算5-2A=AB,voidUnionList_L(LinkList,说明:
first的位置始终不变;插入位置在La表的表头元素之前;查找不会在刚刚插入的结点间进行,只能从first指向的原始La表中进行(因为每次查找时均有q=first)时间复杂度:
O(m*n);,3.循环链表,1)循环链表是一种首尾相接的链表。
循环链表最后一个结点的next指针不为0(NULL),而是指向了表头结点。
在循环链表中没有NULL为简化操作,在循环链表中往往加入表头结点。
特点:
循环链表中,从任一结点出发都可访问到表中所有结点;而在单链表中,必须从头指针开始,否则无法访问到该结点之前的其他结点。
循环链表与单链表不同的是链表中表尾结点的指针域不是NULL,而是链表头结点的指针H(链表指针)循环链表的示例(循环条件:
p!
=H)带表头结点的循环链表(循环条件:
p-next!
=H),2)循环链表的操作,合并两个单链表p=La;while(p-next)p=p-next;p-next=Lb-next;free(Lb);时间复杂度O(m),合并两个循环链表,p=La;while(p-next!
=La)p=p-next;p-next=Lb-next;p=p-next;while(p-next!
=Lb)p=p-next;p-next=La;free(Lb);时间复杂度O(m+n),循环链表的建立算法,voidCreateList_L(LinkList,显示输出算法(带头结点)循环链表,voidPrintList_LC(LinkListL)LinkListp;p=L-next;printf(L-);while(p!
=L)printf(%d-,p-data);p=p-next;printf(Ln);,4.双向链表(DoublyLinkedList),双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。
1)双向链表的结点结构:
前驱方向(a)结点结构后继方向双向链表通常采用带表头结点的循环链表形式。
对双向循环链表中任一结点的指针,有:
p=ppriornext=pnextprior置空表:
pprior=p;pnext=p;,(b)非空双向循环链表(c)空表,2)双向循环链表存储结构的描述p35p36,typedefstructDuLNodeElemTypedata;structDuLNode*prior;structDuLNode*next;DuLNode,*DuLinkList;DuLinkListd,p;,pprior=current;
(1)pnext=currentnext;
(2)currentnext=p;(3)pnextprior=p;(4),双向循环链表的插入算法,currentnextprior=currentprior;currentpriornext=currentnext;,双向循环链表的删除算法,3)基本操作:
双向循环链表的建立,voidCrtList_DuL(DuLinkList,显示输出,voidPrtList_DuL(DuLinkListL)DuLinkListp;p=L-next;printf(L-);while(p!
=L)printf(%d-,p-data);p=p-next;printf(n);,2.4一元多项式的表示和相加,n阶多项式Pn(x)有n+1项。
系数a0,a1,a2,an指数0,1,2,n。
按升幂排列在计算机中,可以用一个线性表来表示P=(a0,a1,an),1.第一种表示方法Pn=(a0,a1,an)适用于指数连续排列、“0”系数较少的情况。
但对于指数不全的多项式,如P20000(x)=3+5x50+14x20000,会造成系统空间的巨大浪费。
2.第二种表示方法一般情况下,一元多项式可写成:
Pn(x)=p1xe1+p2xe2+pmxem其中:
pi是指数为ei的项的非零系数,0e1e2emn二元组表示(p1,e1),(p2,e2),(pm,em)例:
P999(x)=7x3-2x12-8x999表示成:
(7,3),(-2,12),(-8,999),ADTPolynomial数据对象:
D=ai|aiTermSet,i=1,2,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系:
R1=|ai-1,aiD,且ai-1中的指数值ai中的指数值,i=2,n基本操作:
ADTPolynomial,3.一元多项式的抽象数据类型定义,typedefstructfloatcoef;intexpn;term,ElemType;/term用于本ADT,ElemType为LinkList的数据对象名typedefLinkListpolynomial;,4.抽象数据类型(Polynomial)的实现,多项式链表的相加,AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18,两个多项式的相加,结果多项式另存扫描两个相加多项式,若都未检测完:
若当前被检测项指数相等,系数相加。
若未变成0,则将结果加到结果多项式。
若当前被检测项指数不等,将指数小者加到结果多项式。
若有一个多项式已检测完,将另一个多项式剩余部分复制到结果多项式。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实用 课件 第一章