资源描述：
《数据结构与算法教程 教学课件 作者 朱明方 吴及 第2章 顺序表及其运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第二章线性表的顺序存储及其运算2.1线性表的概念一、线性表的结构特性二、线性表的抽象数据类型2.2顺序表及其运算一、什么是顺序表二、顺序表的运算2.3栈一、栈的概念二、栈的抽象数据类型三、顺序栈及其操作实现四、栈应用例第二章线性表的顺序存储及其运算2.4队列一、队列及其抽象数据类型二、顺序队列及其操作实现三、队列应用例四、优先队列2.5数组与矩阵的表示一、数组的顺序分配二、规则矩阵的压缩存储三、稀疏矩阵的三元组顺序表表示2.1线性表的概念一、线性表的结构特性属性相同的数据元素按某种关系排列的表例：农历节气表(立春,雨水,惊蛰,春分,清明,……,大雪,冬至,小寒,大寒
2、)——表中元素是字符抗灾衣被捐赠登记表——按捐赠时间先后(单位,姓名,棉被,棉衣裤,毛衣裤,帽类)奥运会各国家队奖牌数统计表——按金牌、银牌、铜牌数多少(国家,金牌数,银牌数,铜牌数)——表中元素为记录2.1线性表的概念线性表(LinearList)——具有相同特性数据元素的有限序列；可描述为：B=(D,R)D={ai
3、i=1,2,…,n};R={(ai,ai+1)
4、i=1,2,…,n-1}；也可以简单表示为：B=(a1,a2,…,ai,…,an)表中元素个数n——表长度，n=0时称为空表；结构特性：①元素之间具有线性关系(元素在位置上有序)；②元素在表中的位置由其
5、序号决定；③表长度可变；2.1线性表的概念二、线性表的抽象数据类型数据部分：数据元素，数据元素之间的关系描述；操作部分：根据应用需要确定按照功能可以归纳为以下基本类型：•属性设置：确定类型的基本属性值；•读取属性：读取类型的属性值；•插入：在对象的指定位置加入新的数据元素；•删除：删除对象中的指定数据元素；•查找：在对象查找满足条件的数据元素；•遍历：按某种方式不重复地访问对象中所有数据元素；•关系访问：访问对象中有特定关系的元素；2.1线性表的概念ADTLIST{数据：线性表L=(a0,a1,…,an),n≥0；操作：voidInitList(*L);//初始化L
6、指向的线性表ElemTypeGetElemlist(*L,intpos);//得到表中第pos个元素intFindList(*L,ElemTypeitem);//查找给定关键字元素//修改表中指定元素intModifyList(*L,ElemTypeitem);2.1线性表的概念intInsertList(*L,ElemTypeitem);//向表中插入元素intDeleteList(*L,ElemTypeitem);//删除表中元素intLenthList(*L);//求表的长度voidSortList(*L);//按关键字值对表元素排序voidTraverseL
7、ist(*L);//对表进行遍历并输出voidClearList(*L);//清除表中所有元素}2.2顺序表及其运算一、什么是顺序表顺序表——线性表的顺序存储（向量式存储）存储方法:表中元素按逻辑顺序依次放在连续存储空间中;每个元素所占存储单元长度相同；例：利用数组实现线性表的顺序存储,要求：数组长度>表长度表中元素地址计算：ADR(ai)=ADR(a1)+(i-1)*kk——为每个元素所占字节数；a1an-1a2a3an::a41234::n2.2顺序表及其运算二、顺序表的运算若对表示顺序表的数组空间采用动态分配，对顺序表结构作如下定义：#defineMaxS
8、ize100typedefstruct{ElemTypelist[MaxSize];//存储线性表的数组intlen;//线性表长度}SeqList；数据结构操作的实现与具体的存储结构有关以下考虑以SeqList为类型的顺序表基本操作（运算）的实现最基本的操作（运算）：(1)在表中插入一个元素(2)删除表中某个元素2.2顺序表及其运算1.顺序表初始化为存储线性表动态分配数组空间，置初始线性表为空voidInitList(SeqList*L){//动态分配存储空间L->List=(ElemType*)malloc(MaxSize*sizeof(ElemType))；i
9、f(!L->list){printf("Memoryallocationfailure!")；exit(1)；}L->len=0；//置初始线性表为空}2.顺序表的插入运算在表中第i个位置插入一个元素item设表长为len插入前：A=(a0,a1,…,ai-1,ai,…,alen-1)表长为len插入后：A=(a0,a1,…,ai-1,ai,ai+1,…,alen)表长为len+1表首元素位置不变，表向后增长ak0≤k
