版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第2章线性表线性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用2.1线性表的逻辑结构2线性表是由类型相同的数据元素组成的有限序列。线性表的数据元素可以是数字、字符或更复杂的信息。英语字母表:(’a’,’b’,’c’,’d’,……,’x’,’y’,’z’)一个人的一年的月收入:(5000,5200,4890,4890,……,5300)学生成绩表:2.1线性表的逻辑结构3
线性表的定义二元组表示
逻辑关系图2.1线性表的逻辑结构4
线性表的抽象数据类型定义GetElem(i,&e)初始条件:线性表已存在,1≤i≤length。操作结果:用e返回第i个元素的值。SetElem(i,e)初始条件:线性表已存在,1≤i≤length。操作结果:将线性表的第i个位置的元素赋值为e。Search(e)初始条件:线性表已存在。操作结果:在线性表中查找值为e的元素,若查找成功,返回其所在的位置,否则返回0。Insert(i,e)初始条件:线性表已存在,1≤i≤ength+1。操作结果:在线性表的第i个元素前插入元素e,线性表长度加1。Delete(i,&e)初始条件:线性表已存在,1≤i≤length。操作结果:删除线性表的第i个元素,并用e返回其值,线性表长度减1。}2.2线性表的顺序表示和实现1.线性表的顺序存储结构——顺序表5
2.2线性表的顺序表示和实现2.顺序表的实现6template<typenameT>classSqList{private: intmaxsize; //顺序表可能达到的最大长度
intlength; //顺序表的长度
T*elem; //存储空间的基地址public: SqList(intsize=DEFAULT_SIZE); //构造函数,DEFAULT_SIZE为符号常量
SqList(Ta[],intn); //构造函数 SqList(SqList<T>&sl); //复制构造函数
~SqList(); //析构函数
intLength(); //求顺序表长度
boolEmpty(); //判断表是否为空
voidClear(); //清空顺序表
voidPrintList(); //输出表中的各个元素
boolGetElem(inti,T&e); //获取指定位置的元素值
boolSetElem(inti,Te); //设置指定位置的元素值
intSearch(Te); //查找元素
boolInsert(inti,Te); //插入元素
boolDelete(inti,T&e); //删除元素};类模板定义2.2线性表的顺序表示和实现2.顺序表的实现7基本操作//求顺序表的长度template<typenameT>intSqList<T>::Length(){ returnlength;}//判断顺序表是否为空template<typenameT>boolSqList<T>::Empty(){ if(length==0) returntrue; else returnfalse;}//清空顺序表template<typenameT>voidSqList<T>::Clear(){ length=0;}//读取元素的值template<typenameT>boolSqList<T>::GetElem(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; returntrue;}//设置元素的值template<typenameT>boolSqList<T>::SetElem(inti,Te){ if(i<1||i>length) returnfalse; elem[i-1]=e; returntrue;}//查找操作template<typenameT>intSqList<T>::Search(Te){ inti; for(i=0;i<length;i++) if(e==elem[i]) returni+1; return0;}2.2线性表的顺序表示和实现2.顺序表的实现8插入操作template<typenameT>boolSqList<T>::Insert(inti,Te){ if(length==maxsize)
returnfalse; if(i<1||i>length+1) returnfalse; for(intj=length;j>=i;j--) elem[j]=elem[j-1]; elem[i-1]=e; length++; returntrue;}算法分析
假设在线性表的任意位置上插入元素的概率相等,即:则:
插入算法的时间复杂度为:O(n)
2.2线性表的顺序表示和实现2.顺序表的实现9删除操作template<classT>boolSqList<T>::Delete(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; for(intj=i;j<length;j++) elem[j-1]=elem[j]; length--; returntrue;}
删除算法的时间复杂度为:O(n)算法分析2.3线性表的链式表示和实现线性表的链式存储结构称为链表。链表是用一组地址任意的存储单元存放线性表中的数据元素,这些存储单元可以连续也可以不连续,甚至可以零散分布在内存中的任意位置。链表中,每个数据元素用一个结点来存储,结点不仅包含元素本身的信息(称为数据域),而且包含表示元素之间逻辑关系的信息(在C++语言中用指针来实现,称为指针域)。由于线性表中的每个元素最多只有一个前驱元素和一个后继元素,因此采用链式存储时,一种最简单、最常用的方法是在每个结点中除包含数据域之外只设置一个指针域,用于指向其后继结点,这样的链表称为单链表;另一种方法是在每个结点中除包含数据域之外设置两个指针域,分别用于指向其前驱结点和后继结点,这样的链表称为双链表。1.线性表的链式存储结构——链表102.3线性表的链式表示和实现单链表是一种最简单的线性表的链式存储结构,用它来存储线性表时,为了能正确表示元素之间的逻辑关系,每个结点在存储数据元素的同时,还必须存储其后继元素所在的地址信息。2.单链表的定义和表示11结点示意图:p->data:该结点的数据元素p->next:指向该结点的后继datanextp单链表结构示意图:a1a2an
∧…head头结点:没有存储任何数据增加头结点:算法实现更简单,效率更高头指针指向单链表的头结点空链表示意图:∧head结点定义template<classT>structNode{ Tdata; //数据域
Node<T>*next; //指针域};2.3线性表的链式表示和实现3.单链表的实现1212基本操作//求单链表的长度template<typenameT>intLinkList<T>::Length(){ intlen=0; Node<T>*p=head->next; while(p!=NULL) { len++; p=p->next; } returnlen;}//判断表是否为空template<typenameT>boolLinkList<T>::Empty(){ returnhead->next==NULL;}//读取元素的值template<typenameT>boolLinkList<T>::GetElem(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i);
e=p->data;
returntrue;}//清空单链表template<typenameT>voidLinkList<T>::Clear(){ Node<T>*p=head->next; while(p!=NULL) { head->next=p->next;
deletep;
p=head->next;
}}//设置元素的值template<typenameT>boolLinkList<T>::SetElem(inti,Te){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i); p->data=e; returntrue;}//查找template<typenameT>intLinkList<T>::Search(Te){ Node<T>*p=head->next; inti=1; while(p!=NULL&&p->data!=e) { p=p->next; i++; } if(p==NULL) return0; else returni;}2.3线性表的链式表示和实现3.单链表的实现1313插入操作template<typenameT>boolLinkList<T>::Insert(inti,Te){ if(i<1||i>Length()+1) returnfalse; Node<T>*q,*p; p=GetPtr(i-1); q=newNode<T>;
q->data=e; q->next=p->next; p->next=q; returntrue;}2.3线性表的链式表示和实现3.单链表的实现1414删除操作template<typenameT>boolLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p,*q; p=GetPtr(i-1); q=p->next; e=q->data; p->next=q->next; deleteq; returntrue;}2.3线性表的链式表示和实现4.双链表1515双向链表(双链表)的结点中有两个指针,分别指向前驱和后继。从双链表的任一结点开始,都可以方便地访问它的前驱结点和后继结点。双链表结点结构:双向链表通常采用带头结点的循环链表形式,称为循环双链表p->back:指向该结点的前驱p->data:
该结点的数据元素p->next:
指向该结点的后继Back
data
nextp循环双链表结构:template<typenameT>structDbNode{ Tdata; DbNode<T>*prior; DbNode<T>*next;};结点定义:2.3线性表的链式表示和实现4.双链表1616插入操作template<typenameT>boolDbLinkList<T>::Insert(inti,T&e){ if(i<1||i>Length()+1) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1个结点
q=newDbNode<T>; //q指向新建结点
q->data=e; //为新结点的数据域赋值
q->prior=p; //新结点的前驱指向p q->next=p->next; //新结点的后继指向p的后继
if(p->next!=NULL) //若p存在后继结点,修改其前驱指针
p->next->prior=q; p->next=q; //修改p的后继指针
returntrue;}2.3线性表的链式表示和实现4.双链表1717删除操作template<typenameT>boolDbLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1个结点
q=p->next; //q指向第i个结点
p->next=q->next; //修改p的后继
if(q->next!=NULL) //若q存在后继结点,修改其前驱指针
q->next->prior=p; e=q->data; //用e存储要删除的元素值
deleteq; //释放被删除结点所占的空间
returntrue;}2.3线性表的链式表示和实现5.循环链表1818循环单链表:将终端结点的next域由指向头结点,结点结构与单链表的结点结构相同。示意图:空循环链表的条件:head->next==head循环双链表:将终端结点的next域指向头结点,将头结点的prior域指向终端结点,结点结构与双链表的结点结构相同。示意图:循环双链表中可以通过head->prior快速找到终端结点2.3线性表的链式表示和实现5.循环链表1919循环链表的基本操作实现算法与对应非循环链表的算法基本相同,主要差别是对于空表或到达终端结点的判定条件不同。在单链表中,判断空表的条件是head->next==NULL,判断指针p指向终端结点的条件是p->next==NULL。在循环链表中,判断空表的条件是head->next==head,判断指针p指向终端结点的条件是p->next==head。2.4顺序表和链表的比较201.空间性能的比较存储空间的分配存储密度的大小2.时间性能的比较由于顺序表需要分配一定长度的连续的存储空间,因此,当线性表的长
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2034年中国净洗剂市场竞争格局及发展战略研究报告
- 2024年医用氮气系统项目申请报告范本
- 2024-2030年中国系统集成行业市场深度分析及发展趋势分析报告
- 2024-2030年中国快速消费品行业发展现状分析及未来前景分析报告
- 2024-2030年中国司法考前培训行业市场专项调研及未来前景展望报告
- 个人借款合同模板版
- 事业单位司机聘用合同
- 2024年陕西省中考化学酸碱盐综合预测试题
- 班组劳务分包合同协议书
- 赣州休闲娱乐场所租赁合同
- 新能源汽车火灾事故处置程序及方法
- 中海物业管理有限公司会所管理手册
- 新教科版六年级上册科学全册一课一练
- 眼镜店管理考核附有答案
- 应用物理学专业毕业设计论文教学大纲
- 重庆市九龙坡区2022-2023学年六年级数学第二学期期末学业水平测试试题含解析
- 沪教版五年级数学下册《可能情况的个数》教案及教学反思
- 江苏丹雪新材料科技有限公司年产1.5万吨高纯石英砂生产项目
- 代收股款协议
- 领导干部个人事项报告漏报情况说明及检讨书范文(通用8篇)
- 面团食谱卡复件面包类SOP制作指导书
评论
0/150
提交评论