版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1第二章线性表1234567891第二章线性表12345678912本章内容2.1线性表的类型定义2.2线性表类型的实现顺序映象2.3线性表类型的实现链式映象2本章内容2.1线性表的类型定义23顺序表示及其特点3顺序表示及其特点34顺序表示及其特点顺序映象——以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。最简单的一种顺序映象方法是:用一组地址连续的存储单元依次存放线性表中的数据元素。
a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址4顺序表示及其特点顺序映象——以x的存储位置和y的45顺序表示及其特点以“存储位置相邻〞表示有序对<ai-1,ai>即:LOC(ai)=LOC(ai-1)+CC是一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C
5顺序表示及其特点以“存储位置相邻〞表示有序对<ai-1,a5小结:顺序表的特点用连续的存储单元存放线性表的元素(采用一维数组存放)。元素存储顺序与元素的逻辑顺序一致。读写元素方便,通过下标即可指定位置。6
a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址小结:顺序表的特点用连续的存储单元存放线性表的元素(采用一维67#defineLIST_INIT_SIZE80
//线性表存储空间的初始分配量#defineLISTINCREMENT10
//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量
//(以sizeof(ElemType)为单位)}SqList;//俗称顺序表7#defineLIST_INIT_SIZE87801….i-2i-1….n-1……顺序表a1a2…ai-1ai…an...L.elem+L.length-1L.elem+L.listsize-1elemlengthlistsizeL注意:由于数组的下标从“0”开始,表中第i个元素是L.elem[i-1].typedefstruct{ElemType*elem;
intlength;
intlistsize;
}SqList;//顺序表SqListL;801….89顺序表的初始化操作StatusInitList_Sq(SqList&L){//构造一个空的线性表
L.elem=(ElemType*)malloc
(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitList_Sqtypedefstruct{ElemType*elem;
intlength;
intlistsize;
}SqList;//顺序表9顺序表的初始化操作StatusInitList_Sq(910顺序表的插入操作ListInsert(&L,i,e)
//插入元素在顺序表L的第i个元素之前插入新的元素e,把e插入到第i个元素的位置
i的合法范围为1≤i≤L.length+101….i-2i-1….n-1a1a2…ai-1ai…anee10顺序表的插入操作ListInsert(&L,i,e)1011操作的过程:ListInsert(&L,6,30)341611825313416118253130341611825313416118302531341611830253111操作的过程:ListInsert(&L,6,30)1112操作的过程:ListInsert(&L,6,30)34161182531341611830253134161182531pqp34161182531pq=&(L.elem[i-1]);p=&(L.elem[L.length-1]);*(p+1)=*p;p--;34161182531p*(p+1)=*p;*q=e;p>=q;插入操作12操作的过程:ListInsert(&L,6,30)1213操作步骤判断插入位置是否合法:1≤i≤L.length+1初始化指针循环:从表尾开场,依次将第i-1个元素之后的元素顺序后移一位将新元素e写入到第i个位置将表的长度加113操作步骤1314StatusListInsert_Sq(SqList&L,inti,ElemTypee){
if(i<1||i>L.length+1)returnERROR;//步骤1:位置不合法
q=&(L.elem[i-1]);//步骤2:q指示插入位置
for(p=&(L.elem[L.length-1]);p>=q;p--)*(p+1)=*p;//步骤3:元素依次后移*q=e;//步骤4:插入e
++L.length;//步骤5:表长加1
returnOK;}//ListInsert_Sq算法时间复杂度取决于:移动元素的次数14StatusListInsert_Sq(SqList1415插入操作的算法复杂度考虑移动元素的平均情况:假设在第i个元素之前插入的概率为pi,那么在长度为n的线性表中插入一个元素所需移动元素次数的期望值为:若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:算法时间复杂度为:O(n)15插入操作的算法复杂度考虑移动元素的平均情况:若假定在线性1516if(L.length>=L.listsize){
//当前存储空间已满,增加分配
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量}如果存储空间已满怎么办?16if(L.length>=L.listsize)1617程序设计方法的两点说明先考虑一般情况,后考虑特殊情况一般不用根本操作实现其他根本操作17程序设计方法的两点说明先考虑一般情况,后考虑特殊情况1718两个实际问题错误的类型:正常处理的错误:是一些常见、合理的错误〔如:用户输入的错误〕,通过错误代码返回。意外错误:抛出Exception,通过try-catch扑捉。初始化问题:数据构造没有初始化就使用往往也是错误,但无法判定。在C++和Java中通过构造函数解决。18两个实际问题错误的类型:1819顺序表的删除操作ListDelete(&L,i,&e)//删除元素删除线性表中第i个元素,并将删除的元素方在e中i的合法范围为1≤i≤L.length删除操作19顺序表的删除操作ListDelete(&L,i,&e1920操作的过程:ListDelete(&L,5,&e)34161253134161253134161182531pp341612531pp=&(L.elem[i-1]);*e=*p;p++;341612531p*(p-1)=*p;p>=L.elem+L.length-1;pp++;341612531p*(p-1)=*p;20操作的过程:ListDelete(&L,5,&e2021操作步骤判断插入位置是否合法:1≤i≤L.length初始化指针将第i个元素的值赋给变量e循环:从第i+1个元素开场,依次将后面的元素顺序前移一位将表的长度减121操作步骤2122StatusListDelete_Sq(SqList&L,inti,ElemType&e){
//步骤1:位置是否合法
if((i<1)||(i>L.length))returnERROR;
p=&(L.elem[i-1]);//步骤2:初始化指针
e=*p;//步骤3:赋给eq=L.elem+L.length-1;//表尾的位置
for(++p;p<=q;++p)*(p-1)=*p;//步骤4:被删除元素之后的元素左移
--L.length;//步骤5:表长减1returnOK;}//ListDelete_Sq算法时间复杂度取决于:移动元素的次数22StatusListDelete_Sq算法时间复杂度取2223删除操作的算法复杂度考虑移动元素的平均情况:假设在删除第i个元素的概率为pi,那么在长度为n的线性表中删除一个元素所需移动元素次数的期望值为:若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:算法时间复杂度为:O(n)23删除操作的算法复杂度考虑移动元素的平均情况:若假定在线性2324LocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p基本操作:将顺序表中的元素逐个和给定值e相比较。定位操作循环结束标志:找到e或者p超过表尾的地址24LocateElem_Sq(SqListL,Elem2425定位操作请大家写出顺序表的定位操作的操作步骤和程序要求:在顺序表中查询第一个满足判定条件的数据元素,假设存在,那么返回它的位序,否那么返回0算法时间复杂度为:O(n)25定位操作请大家写出顺序表的定位操作的算法时间复杂度为:O25小结:顺序表的优缺点优点不需要附加空间随机存取任一个元素〔根据下标〕缺点很难估计所需空间的大小开场就要分配足够大的一片连续的内存空间更新操作代价大26小结:顺序表的优缺点优点262627END27END2728第二章线性表1234567891第二章线性表1234567892829本章内容2.1线性表的类型定义2.2线性表类型的实现顺序映象2.3线性表类型的实现链式映象2本章内容2.1线性表的类型定义2930顺序表示及其特点3顺序表示及其特点3031顺序表示及其特点顺序映象——以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。最简单的一种顺序映象方法是:用一组地址连续的存储单元依次存放线性表中的数据元素。
a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址4顺序表示及其特点顺序映象——以x的存储位置和y的3132顺序表示及其特点以“存储位置相邻〞表示有序对<ai-1,ai>即:LOC(ai)=LOC(ai-1)+CC是一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C
5顺序表示及其特点以“存储位置相邻〞表示有序对<ai-1,a32小结:顺序表的特点用连续的存储单元存放线性表的元素(采用一维数组存放)。元素存储顺序与元素的逻辑顺序一致。读写元素方便,通过下标即可指定位置。33
a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址小结:顺序表的特点用连续的存储单元存放线性表的元素(采用一维3334#defineLIST_INIT_SIZE80
//线性表存储空间的初始分配量#defineLISTINCREMENT10
//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量
//(以sizeof(ElemType)为单位)}SqList;//俗称顺序表7#defineLIST_INIT_SIZE8343501….i-2i-1….n-1……顺序表a1a2…ai-1ai…an...L.elem+L.length-1L.elem+L.listsize-1elemlengthlistsizeL注意:由于数组的下标从“0”开始,表中第i个元素是L.elem[i-1].typedefstruct{ElemType*elem;
intlength;
intlistsize;
}SqList;//顺序表SqListL;801….3536顺序表的初始化操作StatusInitList_Sq(SqList&L){//构造一个空的线性表
L.elem=(ElemType*)malloc
(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitList_Sqtypedefstruct{ElemType*elem;
intlength;
intlistsize;
}SqList;//顺序表9顺序表的初始化操作StatusInitList_Sq(3637顺序表的插入操作ListInsert(&L,i,e)
//插入元素在顺序表L的第i个元素之前插入新的元素e,把e插入到第i个元素的位置
i的合法范围为1≤i≤L.length+101….i-2i-1….n-1a1a2…ai-1ai…anee10顺序表的插入操作ListInsert(&L,i,e)3738操作的过程:ListInsert(&L,6,30)341611825313416118253130341611825313416118302531341611830253111操作的过程:ListInsert(&L,6,30)3839操作的过程:ListInsert(&L,6,30)34161182531341611830253134161182531pqp34161182531pq=&(L.elem[i-1]);p=&(L.elem[L.length-1]);*(p+1)=*p;p--;34161182531p*(p+1)=*p;*q=e;p>=q;插入操作12操作的过程:ListInsert(&L,6,30)3940操作步骤判断插入位置是否合法:1≤i≤L.length+1初始化指针循环:从表尾开场,依次将第i-1个元素之后的元素顺序后移一位将新元素e写入到第i个位置将表的长度加113操作步骤4041StatusListInsert_Sq(SqList&L,inti,ElemTypee){
if(i<1||i>L.length+1)returnERROR;//步骤1:位置不合法
q=&(L.elem[i-1]);//步骤2:q指示插入位置
for(p=&(L.elem[L.length-1]);p>=q;p--)*(p+1)=*p;//步骤3:元素依次后移*q=e;//步骤4:插入e
++L.length;//步骤5:表长加1
returnOK;}//ListInsert_Sq算法时间复杂度取决于:移动元素的次数14StatusListInsert_Sq(SqList4142插入操作的算法复杂度考虑移动元素的平均情况:假设在第i个元素之前插入的概率为pi,那么在长度为n的线性表中插入一个元素所需移动元素次数的期望值为:若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:算法时间复杂度为:O(n)15插入操作的算法复杂度考虑移动元素的平均情况:若假定在线性4243if(L.length>=L.listsize){
//当前存储空间已满,增加分配
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量}如果存储空间已满怎么办?16if(L.length>=L.listsize)4344程序设计方法的两点说明先考虑一般情况,后考虑特殊情况一般不用根本操作实现其他根本操作17程序设计方法的两点说明先考虑一般情况,后考虑特殊情况4445两个实际问题错误的类型:正常处理的错误:是一些常见、合理的错误〔如:用户输入的错误〕,通过错误代码返回。意外错误:抛出Exception,通过try-catch扑捉。初始化问题:数据构造没有初始化就使用往往也是错误,但无法判定。在C++和Java中通过构造函数解决。18两个实际问题错误的类型:4546顺序表的删除操作ListDelete(&L,i,&e)//删除元素删除线性表中第i个元素,并将删除的元素方在e中i的合法范围为1≤i≤L.length删除操作19顺序表的删除操作ListDelete(&L,i,&e4647操作的过程:ListDelete(&L,5,&e)34161253134161253134161182531pp341612531pp=&(L.elem[i-1]);*e=*p;p++;341612531p*(p-1)=*p;p>=L.elem+L.length-1;pp++;341612531p*(p-1)=*p;20操作的过程:ListDelete(&L,5,&e4748操作步骤判断插入位置是否合法:1≤i≤L.length初始化指针将第i个元素的值赋给变量e循环:从第i+1个元素开场,依次将后面的元素顺序前移一位将表的长度减121操作步骤4849StatusListDelete_Sq(SqList&L,inti,ElemType&e){
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年旅游公司浮动抵押合同
- 个人住宅租借押金及季度租金合同样本(2024版)一
- 二零二五年度专业印刷品设计、印刷与打印服务合同3篇
- 事业单位基本建设粉刷工程分包合同2024版B版
- 2025年度烘焙连锁面包砖供应链合作协议4篇
- 二零二五年度干股虚拟股分红激励方案合同范本
- 2025年度玩具货物运输委托服务协议
- 二零二五年度物业小区个人承包社区物业服务综合解决方案协议
- 2025年度家用空调拆装安全操作规范及应急处理合同
- 二零二五年度家政服务公司保姆雇佣协议
- 海外资管机构赴上海投资指南(2024版)
- 山东省青岛市2023-2024学年七年级上学期期末考试数学试题(含答案)
- 墓地销售计划及方案设计书
- 从偏差行为到卓越一生3.0版
- 优佳学案七年级上册历史
- 铝箔行业海外分析
- 纪委办案安全培训课件
- 超市连锁行业招商策划
- 城市道路智慧路灯项目 投标方案(技术标)
- 【公司利润质量研究国内外文献综述3400字】
- 工行全国地区码
评论
0/150
提交评论