数据结构线性表.ppt
《数据结构线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构线性表.ppt(80页珍藏版)》请在课桌文档上搜索。
1、2023/3/2,1,第2章 线性表,2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加2.5 顺序表和链表的综合比较 2.6 总结,2023/3/2,2,2.1 线性表的概念及运算,一、线性表的定义线性表(Linear List)是由n(n0)个类型相同的数据元素组成的有限序列,记做:(a1,a2,,ai-1,ai,ai+1,an),2.1.1 线性表的逻辑结构,2023/3/2,3,线性表的形式定义为:Linear-list=(D,R),其中:D=ai|aiD0,i=1,2,n,n0 R=N N=|ai-1,aiD0,i=2,3n
2、 D0为某个数据对象;n为表的长度。,线性表是一种最简单、最常用的数据结构,2023/3/2,4,二、线性表的特点,同一性:线性表由同类数据元素组成,每一 个ai必须属于同一数据对象。有穷性:线性表由有限个数据元素组成,表 长度就是表中数据元素的个数。有序性:线性表中相邻数据元素之间存在着 序偶关系:,表中必存在唯一的一个“第一元素”;表中必存在唯一的一个“最后元素”;除最后元素之外,均有 唯一的后继;除第一元素之外,均有 唯一的前驱。,2023/3/2,5,2.1.2线性表的抽象数据类型定义,ADT LinearList数据元素:D=ai|aiD0,i=1,2,n n0,D0为某数据对象关系
3、:|ai,ai+1D0,i=1,2,n-1基本操作:(1)InitList(L)操作前提:L为未初始化线性表。操作结果:将L初始化为空表。(2)DestroyList(L)操作前提:线性表L已存在。操作结果:将L销毁。(3)ClearList(L)操作前提:线性表L已存在。操作结果:将表L置为空表。判空表、求表长、查找、插入、删除 ADT LinearList,2023/3/2,6,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储结构,线性表的最简单的顺序存储方法是:,一、顺序表:,顺序存储是以元素在存储器中的相对位置表示元素间的逻辑关系。,用一组地址连续的存储单元,依次存放线性表中的数
4、据元素(顺序表):,2023/3/2,7,LOC(ai)=LOC(a1)+(i-1)k,第一个数据元素a1的存储位置称线性表的起始地址(基地址),所有数据元素的存储位置均取决于a1的存储位置。,LOC(ai)=LOC(ai-1)+k,若每个数据元素所占存储长度为k,则有:,2023/3/2,8,二、顺序表结构示意图,2023/3/2,9,三、顺序表结构的C语言定义,#definemaxsize=线性表可能达到的最大长度;typedef struct ElemType elemmaxsize/*线性表占用的数组空间*/int last;/*记录线性表最后一个元素在数组elem 中的位置(下标值)
5、,空表置为-1*/SeqList;,注意区分元素的序号和数组的下标,如a1的序号为1,而其对应的数组下标为0。,2023/3/2,10,2.2.2 线性表顺序存储结构的基本运算,线性表的基本运算:查找操作 插入操作 删除操作 顺序表合并运算 顺序表的优缺点分析,2023/3/2,11,一、查找操作,线性表的两种基本查找运算:按序号查找 GetData(L,i):要求查找线性表L中第i个数据元素,其结果是L.elemi-1或L-elemi-1。按内容查找 Locate(L,e):要求查找线性表L中与给定值e相等的数据元素,其结果是:若在表L中找到与e相等的元素,则返回该元素在表中的序号;若找不到
6、,则返回一个“空序号”,如-1。,2023/3/2,12,成功,查找操作示意图,查找操作:Locate(L,e),e=,38,P,0,1,2,3,0,7,50,失败,基本操作是:将顺序表中的元素逐个和给定值e相比较。,2023/3/2,13,线性表的查找算法,int Locate(SeqList L,ElemType e)p=0;/*p为扫描计数器,初值为0,即从第一 个元素开始比较*/while(p=L.last)/*若没找到,则返回空序号*/,时间复杂度:O(n),2023/3/2,14,二、插入操作,线性表的插入运算是指在表的第i(1in+1)个位置,插入一个新元素e,使长度为n的线性表
7、:(a1,a2,,ai-1,ai,an)变成长度为n+1的线性表:(a1,,ai-1,e,ai,an)。,2023/3/2,15,插入操作示意图,e,ai,an,操作过程如下:,2023/3/2,16,例:线性表(4,9,15,28,30,30,42,51,62),需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置,然后将“21”插入到第4个位置,,2023/3/2,17,插入算法,int InsList(SeqList*L,int i,ElemType e)int k;if(iL-last+2)printf(“i值不合法”);return(ERROR
8、);if(L-last=maxsize-1)printf(“表已满无法插入”);turn(ERROR);for(k=L-last;k=i-1;k-)L-elemk+1=L-elemk;L-elemi-1=e;L-last+;return(OK);,时间复杂度:O(n),2023/3/2,18,三、删除操作,线性表的删除运算是指将表的第i(1in)个元素删去,使长度为n的线性表(a1,,ai-1,ai,ai+1,an),变成长度为n-1的线性表:(a1,,ai-1,ai+1,an)。,2023/3/2,19,删除操作示意,操作过程如下:,ai+1,an,2023/3/2,20,删除算法,int
9、DelList(SeqList*L,int i,ElemType*e)int k;if(iL-last+1)printf(“位置不合法!”);return(ERROR);*e=L-elemi-1;for(k=i;ilast;k+)L-elemk-1=L-elemk;L-last-;return(OK);,时间复杂度:O(n),2023/3/2,21,四、合并运算,已知:有两个顺序表LA和LB,其元素均为非递减有序排列,要求编写算法,将LA和LB合并成一个顺序表LC,并使LC也是非递减有序排列。,顺序表合并算法:,void merge(SeqList*LA,SeqList*LB,SeqList*
10、LC)i=0;j=0;k=0;,2023/3/2,22,while(ilast,时间复杂度:O(n+m),2023/3/2,23,五、顺序存储结构的优点和缺点,优点:1.无需为表示结点间的逻辑关系而增加额外的存储空间;2.可方便地随机存取表中的任一元素。,缺点:1.插入或删除运算不方便,除表尾的位置外,在表的其 它位置上进行插入或删除操作都必须移动大量的结点,其效率较低;2.由于顺序表要求占用连续的存储空间,存储分配只能 预先进行静态分配。因此当表长变化较大时,难以确 定合适的存储规模。,2023/3/2,24,2.3 线性表的链式存储,链表定义:,我们从两个角度来讨论链表:1.从实现角度:链
11、表可分为动态链表和静态链表;2.从链接方式的角度:链表可分为单链表、循环链表和双链表。,采用链式存储结构的线性表称为链表。,2023/3/2,25,2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表*2.3.5 静态链表,链表,2023/3/2,26,2.3.1 单链表,头指针:指向链表首结点的指针。,用一组地址任意的存储单元存储线性表中的数据元素,对每一数据元素附加指针信息,以便表述元素间的逻辑关系。,因每个结点仅有一个指针域,故称作单链表。,指针:指示后继元素存储地址。,2023/3/2,27,一、单链表的示例图,2023/3/2,28,二、带头
12、结点的单链表示意图,为了操作的方便,一般在单链表的第一个结点之前附设一个头结点。,带头结点的单链表:,带头结点的空单链表:,2023/3/2,29,三、单链表的存储结构描述,typedef struct Node/*结点类型定义*/ElemType data;struct Node*next;Node,*LinkList;/*LinkList为结构指针类型*/,2023/3/2,30,2.3.2 单链表上的基本运算,线性表的基本运算:建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例:求单链表的长度 求两个集合的差,2023/3/2,31,一、建立单链表,1、头插法建表,操作步骤
13、:,1、建立一个“空表”;,2、输入数据元素an,建立结点并插入;,3、输入数据元素an-1,建立结点并插入;,an-1,4、依次类推,直至输入完a1结束。,2023/3/2,32,2、头插法建表算法,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;L=(Linklist)malloc(sizeof(Node);L-next=NULL;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag
14、=0;,2023/3/2,33,3、尾插法建表,操作步骤:,1、建立一个“空表”;,2、输入数据元素a1,建立结点并插入;,3、输入数据元素a2,建立结点并插入;,a2,4、依次类推,直至输 入完an结束。,2023/3/2,34,4、尾插法建表算法,Linklist CreateFromTail()LinkList L;Node*r,*s;int flag=1;L=(Node*)malloc(sizeof(Node);L-next=NULL;r=L;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-n
15、ext=s;r=s else r-next=NULL;flag=0;,2023/3/2,35,二、单链表查找,1、按序号查找,单链表是一种顺序存取结构,为找第 i 个数据元素,必须从头顺序扫描前 i-1 个数据元素,需要计数器 j 与指针 p 协调处理。,其中要求指针p始终指向线性表中第j个数据元素。,2023/3/2,36,0,j,1,2,3,Pdata=30,例i=3时,按序号查找的实现过程:,2、按序号查找示例图,2023/3/2,37,3、按序号查找算法,Node*Get(LinkList L,int i)Node*p;p=L;j=0;/*从头结点开始扫描*/while(p-next!
16、=NULL)&(jnext;j+;if(i=j)return p;/*找到了第i个结点*/else return NULL;/*找不到,i0或in*/,2023/3/2,38,4、按值查找算法,/*在带头结点的单链表L中查找其值等于key的结点,若找到则返回该结点的指针p,否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/*从表中第一个结点比较*/while(p!=NULL)if(p-data!=key)p=p-next;else break;/*找到结点key,退出循环*/return p;,2023/3/2,39,
17、三、单链表插入操作,s,在单链表中第 i 个结点之前插入结点e 的操作即为:,将有序对,可见,在链表中第 i 个结点之前插入结点需要找到并修改第 i-1 个结点的指针。,改变为 和,2023/3/2,40,单链表插入算法,void InsList(LinkList L,int i,ElemType e)Node*pre,*s;int k=0;pre=L;while(pre!=NULL,2023/3/2,41,四、单链表删除,在单链表中删除第 i 个结点的操作即为:,将有序对 和 改变为,可见,在链表中删除第 i 个结点同样需要找到并修改第 i-1 个结点的指针。,2023/3/2,42,单链表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性
链接地址:https://www.desk33.com/p-229784.html