第2章(线性表)ppt课件.ppt
《第2章(线性表)ppt课件.ppt》由会员分享,可在线阅读,更多相关《第2章(线性表)ppt课件.ppt(51页珍藏版)》请在三一办公上搜索。
1、数据结构,North China Electric Power University,Data Structure,华北电力大学计算机科学与工程系,Dept.of Computer Science&Engineering of North China Electric Power University,第1章 绪论第2章 顺序表第3章 链表 第4章 数组和广义表第5章 串第6章 树第7章 图第8章 查找表第9章 内排序,目 录,North China Electric Power University,数据结构课程的起点:,什么是线性结构?,North China Electric Power
2、 University,本章主要内容,线性表,栈,队列,North China Electric Power University,2.1 线性表,一、线性表的逻辑结构,线性表举例:,例1.一副扑克牌中同一花色的13张牌组成一个线性表(A,2,3,4,5,6,7,8,9,10,J,Q,K),例2.人民币面值的所有种类组成一个线性表(1角,2角,5角,1元,2元,5元,10元,20元,50元,100元),例3.一本书可以看成是一个线性表,每一页是一数据 元素,North China Electric Power University,例4.学生的学籍档案构成一个线性表,数据元素,数据项,Nort
3、h China Electric Power University,线性表是0个或多个元素的有穷序列,通常可表示成 a1,a2,a3,ai,an(n0),n:线性表的表长 n=0时称为空表 n1时,a1称为第一个元素,an称为最后一个元素 ai称为ai+1的前驱,ai+1称为ai的后继,i称为序号或索引,North China Electric Power University,线性表的定义,(1)当1in时,ai的直接前驱为ai-1,ai的直接后继为ai+1。(2)除了第一个元素与最后一个元素,序列中任何一个元素有且仅 有一个直接前驱元素,有且仅有一个直接后继元素。,线性表的特性,North
4、 China Electric Power University,线性表的逻辑结构,线性表的逻辑结构为线性结构,二、线性表的基本运算,1.Initial(L):初始化操作,设定一个空的线性表L。,2.Length(L):返回线性表的表长。,3.Get(L,i):若1iLength(L),返回线性表的第i个元素。,5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。,6.Delete(L,i):删除线性表L的第i个元素。,7.Empty(L):若线性表L为空返回True,否则返回False。,4.Locate(L,x):若L中存在一个或多个值和x相等,运算 结果为这些元素序号的最
5、小值,否则返回0。,North China Electric Power University,线性表的其它运算:,1.求任一元素的直接前驱或直接后继。,2.按照一定的原则,将两个或两个以上的线性表合 并成为一个线性表。,4.按照一定的原则,将一个线性表分解为两个或两 个以上的线性表。,3.复制线性表。,线性表的基本运算示例,North China Electric Power University,例1.设有两个线性表La和Lb,现将La 和Lb合并成一个 新表存于La中。Pascal实现 C语言实现,For i:=1 to Length(Lb)Do x:=Get(Lb,i);,k:=Loc
6、ate(La,x);,if k=0 then Insert(La,n+1,x);n:=n+1;,End;,Procedure Union(Var La:Linear_list;Lb:Linear_list);将所有在Lb中存在而在La中不存在的数据元素插入到La中 Begin n:=Length(La);k:=0;,for(i=1;i=Length(Lb);i+)x=Get(Lb,i);,k=Locate(La,x);,if(k=0)Insert(La,n+1,x);n=n+1;,void union(Linear_list La,Linear_List Lb)/*将所有在Lb中存在而在La中
7、不存在的数据元素插入到La中*/n=Length(La);/确定线性表La的长度,例2.判断两个集合A和B是否相等。,North China Electric Power University,int Compare(Linear_list La,Linear_List Lb)/若La和Lb不仅长度相等,而且所含元素也相同则返回0,否则返回-1。Len_la=Length(La);Len_lb=Length(Lb);if Len_laLen_lb Return(-1)else for(k=1;k=Len_lb;k+)x=Get(La,k);m=Locate(Lb,x);if m=0 then
8、Return(-1);Return(0);,三、线性表的顺序存储结构,用一组地址连续的存储单元依次存放线性表中的数据元素,数据元素之间的逻辑关系通过元素的存储位置直接反映。,存储地址,b=Loc(a1),b+c,b+(i-1)*c,b+(n-1)*c,b+(max-1)*c,顺序存储的线性表的寻址公式:Loc(ai)=Loc(a1)+(i-1)*c(1in),Loc(a1)为线性表的第一个元素a1的存储地址,c为每个元素所占的存储单元。,North China Electric Power University,North China Electric Power University,线性表
9、的顺序存储可以借用数组类型来实现Pascal 语言:A1.n A1,A2,Ai,An,C 语言:An A1,A2,Ai,An,其中A0存放特殊数值。,1)在长度为n的线性表L的第i个位置上插入一个新元素x,插入前:,元素,序号,1,2,3,4,5,6,7,8,主要操作:1.将第i到n个元素依次后移一个位置,2.将新元素x放到线性表的第i个位置上,3.将线性表的表长由n修改为n+1,28,31,43,78,11,14,25,20,North China Electric Power University,四、线性表的基本运算,在线性表L的第i个位置上插入新元素x的算法,North China E
10、lectric Power University,if(in+1)error(“插入的位置非法”);else,void InsertSql(Linear_list L,int&n,int i,ElemType x),时间复杂度分析,North China Electric Power University,North China Electric Power University,2)删除长度为n的线性表L的第i个元素,主要操作:1.将第i+1到n个元素依次前移一个位置,2.将线性表的表长由n修改为n-1,North China Electric Power University,删除线性表L
11、的第i个元素的算法,for(j:=i+1;j=n;j+)Lj-1:=Lj;数据元素依次向前移动一个位置,n:=n-1;,线性表的长度减1,if(in)ERROR(没有这个元素!)else,void Deletesql(Linear_list V,int&n,int i),时间复杂度分析,North China Electric Power University,3)定位运算:求x在线性表L中的最小序号,元素,序号,1,2,3,4,5,6,7,8,28,31,43,78,11,14,25,20,28,x,North China Electric Power University,算法 int L
12、ocatesql(Linear_list L,ElemType item)i=1;while(i=n)&(Li!=item)i=i+1;if(i=n)return(i);/查找成功,返回信息i/else return(0);/查找失败,返回信息0/,North China Electric Power University,4)顺序表的其他算法举例,例1.按照字典序比较两个线性表A和B的大小,int Compare(Linear_list A,Linear_list B)/若AB,则返回1 j=1;,while(jGet(B,j)return(1);else j=j+1;,if(Length(
13、A)=Length(B)return(0);else if(Length(A)Length(B)return(-1);else return(1);,已知长度为n 的线性表A采用顺序存储结构,并且数据元素按值大小非递减排列。写一算法,删除线性表中值相同的多余元素。,void Del(Linear_list A,int,North China Electric Power University,顺序存储的缺点:,1.需要一片地址连续的存储空间;2.插入和删除元素时不方便,大量的时间用在元 素的搬家上;,3.在预分配存储空间时,可能造成空间的浪费;,4.表的容量难以扩充。,North China
14、Electric Power University,North China Electric Power University,栈:所有的插入和删除都只能在表尾(栈顶)进行的线性表。允许进行插入和删除操作的一端叫栈顶,不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。,a1,栈底,栈顶,插入,删除,若给定栈S=(a1,a2,an),则a1是栈底元素,an是栈顶元素,表中元素按a1,a2,an顺序进栈,按an,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。,an,a2,a1,2.2 栈,一、栈的逻辑结构,North China Electri
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 ppt 课件
链接地址:https://www.31ppt.com/p-2104182.html