数据与结构算法中对线性表的理解.ppt
《数据与结构算法中对线性表的理解.ppt》由会员分享,可在线阅读,更多相关《数据与结构算法中对线性表的理解.ppt(108页珍藏版)》请在三一办公上搜索。
1、线性表顺序表 链表顺序表与链表的比较,第二章 线性表,线性表(Linear List),线性表的定义和特点 定义 n(0)个数据元素的有限序列,记作(a1,a2,an)ai 是表中数据元素,n 是表长,n=0时为空表 遍历 逐项访问:从前向后 从后向前,线性表的特点,除第一个元素外,其他每一个元素有且仅有一个直接前驱除最后一个元素外,其他每一个元素有且仅有一个直接后继,a1,a2,a3,a4,a5,线性表的初始化 Init_List(L)求线性表的长度 Length_List(L)取表元 Get_List(L,i)按值查找 Locate_List(L,x)插入操作 Insert_List(L,
2、i,x)删除操作 Delete_List(L,i),线性表的基本操作,顺序表(Sequential List),顺序表的定义和特点 定义 将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构 特点 逻辑顺序与物理顺序一致 访问 顺序存取,随机存取,25 34 57 16 48 09,0 1 2 3 4 5,data,顺序表的连续存储方式,35 27 49 18 60 54 77 83 41 02,1 2 3 4 5 6 7 8 9 10,l l l l l l l l l l,Loc(ai)=Loc(a1)+(i1)*l 1in,a,顺序表(SeqList)的定义,#de
3、fine Maxsize 100/最大允许长度typedef int datetype;typedef struct datatype dataMaxsize;/存储数组 int last;/当前元素个数 SeqList;SeqList*L;(或SeqList L;),顺序表基本运算的实现,顺序表的初始化 SeqList*inti_Seqlist()SeqList*L;L=(SeqList*)malloc(sizeof(SeqList);Llast=-1;return L;,求表的长度 int Length(SeqList*L)return Llast+1;取表元:在表中提取第 i 个元素的值
4、 datatype GetData(SeqList*L,int i)if(i=1,按值查找:在顺序表中查找结点值等于给定值 x 的结点,动画演示,i=Llast,按值查找动画演示,25 34 57 16 48 09,0 1 2 3 4 5,data,查找 16,i,0 1 2 3 4 5,查找成功,返回i的值,查找 50,25 34 57 16 48 09,0 1 2 3 4 5,data,i,0 1 2 3 4 5,查找失败,返回1,查找成功的平均比较次数 若查找概率相等,则:查找不成功,数据比较 n 次,O(n),25 34 57 16 48 09 63,0 1 2 3 4 5 6 7,d
5、ata,25 34 57,0 1 2 3 4 5 6 7,data,50,i=4,例:在第个位置(i=4)插入一个值为50的新元素,插入运算:在顺序表的第 i(1i n+1)个位置插入一个值为 x 的新元素,63,09,48,16,i与Llast的关系?,int Insert(SeqList*L,datatype x,int i)/在表中第 i 个位置插入新元素 x if(i)return 0;if(Llast=Maxsize-1)return-1;/参数不合理或表已满,插入不成功 for(j=Llast;j=;j-)Ldataj+1=Ldataj;=x;Llast+;return 1;/插入
6、成功,Llast+2,i-1,Ldatai-1,算法分析:,在顺序表上做插入操作需要移动表中一半的元素,时间复杂度为(n),16,25 34 57 16 48 09 63,0 1 2 3 4 5 6 7,data,25 34 57,0 1 2 3 4 5 6 7,data,i=4,例:将表中第个位置(i=4)上的元素删除,删除运算:将顺序表中的第 i(1i n)个元素从表中删除,63,09,48,i与Llast的关系?,int Delete(SeqList*L,datatype x)/删除表中第 i 个位置上的元素 if(i Llast+1)return 0;for(;j=Llast;j+)L
7、dataj-1=Ldataj;Llast-;return 1;/删除成功,j=i,算法分析:,在顺序表上做删除操作大约需要移动表中一半的元素,时间复杂度为(n),例题,顺序表应用举例,例1将顺序(a1,a2,.,an)表重新排列为以a1为界的两部分,a1前面的值均比a1小,a1后面的值都比a1大,i=,x,25,30,20,60,10,35,15,y,25,if(L-dataix)i+;,if(L-dataix),顺序表应用举例,例1将顺序表重新排列为以a1为界的两部分,a1前面的值均比a1小,a1后面的值都比a1大 算法思想:依次取原链表中的每个结点,将其做为第一个结点插入到新链表中。,算法
8、实现见书P29,顺序表溢出的处理,顺序表的问题在于:如果其空间大小已经分配,一旦空间占满,再加入新元素将产生溢出。已知顺序表的大小为 ListSize,其定义和分配如下:datatype*elem=new datatypeListSize;现已产生溢出,处理溢出的方法为:,const int NewSize=100;datatype*newArray=new datatypeNewSize;if(newArray=NULL)cout“存储分配错!n”);exit(1);int n=NewSize;datatype*srcptr=elem;datatype*destptr=newArray;wh
9、ile(n-)*destptr+=*srcptr+;delete elem;elem=newArray;,链表(Linked List),链表是线性表的链接存储表示单链表静态链表 循环链表双向链表,单链表,每个结点由数据域(data)和指针域(next)构成 线性表(a1,a2,an)通过每个结点的指针域指向下一个结点,形成单链表:结点可以连续存储也可以不连续存储,使得结点的逻辑顺序与物理顺序可以不一致,单链表的存储映像,free,(a)可利用的存储空间,free,head,(b)经过一段运行后的单链表结构,单链表的定义,typedef char datatype;typedef struct
10、 node/单链表结点 datatype data;struct node*next;LNode;typedef LNode*LinkList;LinkList head;/链表头指针,空链表的表示:头指针的值为NULL,head,s,x,思考:s-next=?如何利用next指针在空 表的基础上建立一非空的单链表?,申请结点空间:LNode*s;s=(LNode)malloc(sizeof(LNode);s-data=x;,LinkList head=NULL;,前插法 建立单链表,从一个空表开始,重复读入数据:用malloc函数生成新结点读入的数据存放到新结点的data域中将该新结点插入到
11、链表的最前端直到读入的数据等于结束符flag为止。,动画演示,s,25,head,flag值为-1,x=25,s,s,x=45,x=18,45,18,x=-1,2条重要的指针赋值语句:,s-next=head;,head=s;,前插法 建立单链表的动画演示,LinkList CreateListL()int x;ListNode head=NULL;LNode*s;scanf(“%d”,s-next=head;,head=s;,后插法 建立单链表,从一个空表开始,重复读入数据:用malloc函数生成新结点读入的数据存放到新结点的data域中将该新结点插入到链表的最后端直到读入的数据等于结束符f
12、lag为止。,动画演示,关键:引入尾指针r,总是指向表中尾结点,head,s,x=25,s,s,x=45,x=18,25,45,18,x=-1,r,flag值为-1,后插法 建立单链表的动画演示,对于空表与非空表,后插结点的操作是否一致?,思考:,后插法 建立单链表的两种情况:,x,s,head,x,s,r,r,NULL,r-next=s;,head=s;,空 表:,非空表:,if(head=NULL)else,r=s;,r=s;,LinkList CreateListR()LinkList head=NULL;LNode*s,*r=NULL;int x;scanf(“%d”,r=s;,r!=
13、NULL,前插法与后插法比较前插法:不用辅助存储变量,简单;空表与非空表的操作一致后插法:需要辅助存储变量;空表与非空表的操作不一致为使空表与非空表的操作一致,可在链表的头部加入“头结点”,带头结点的单链表,头结点位于表的最前端,本身不带数据,仅标志表头,可用malloc语句申请头结点空间设置头结点的目的:统一空表与非空表的操作,简化链表操作,空表 非空表,an,a1,head,head,x,s,r-next=s;,head,x,s,r-next=s;,空表 非空表,r=s;,r=s;,例:带头结点的单链表的后插法建立,结论:带头结点的单链表同样也会简化其它的链表操作(如:插入、删除),hea
14、d,p,a0,a1,a2,j=0,head,p,a0,a1,a2,j=1,head,p,a0,a1,a2,j=2,head,p,a0,a1,a2,j=3,计算带头结点的单链表长度,int Length(LinkList head)LNode*p=head;/指针 p 指示头结点 int j=0;while(p-next!=NULL)/逐个结点检测 p=p-next;j+;return j;,计算带头结点的单链表长度,head,0,p,j=0,思考:空表是否适用该算法?,int Length2(LinkList head)int j;LNode*p=head;/指针 p 指示头结点 if(p-n
15、ext=NULL)return 0;j=1;while(p-next!=NULL)/逐个结点检测 p=p-next;j+;return j;,p,j=1,计算不带头结点的单链表长度,以后的算法如不加说明都是带头结点的,LNode*Find(LinkList head,datatype x)/在链表中从头查找数据域的值为x的结点 LNode*p=head-next;/检测指针 p 指示第 1 号结点 while(p!=NULL,在单链表中按值查找,head,p,a1,a2,a3,LNode*Locate(LinkList head,int i)/返回表中第 i 个元素的地址 LNode*p=he
16、ad;int j=0;/置于表头 while(p-next!=NULL/返回第 i 个结点地址或NULL,在单链表中按序号查找(定位),head,p,a1,a2,a3,j=0,(插入前)(插入后),后插结点:在*p之后插入*s s-next=p-next;p-next=s;,s,p,s,p,单链表中的插入与删除,前插结点:在*p之前插入*s,head,p,a0,a1,a2,qhead;while(q-next!=p)q=q-next;s-next=q-next;q-next=s;,int Insert(LinkList head,int x,int i)/在链表第 i(=0)个位置处插入新元素
17、 x LNode*p=head,*s;p=Locate(head,i-1);/找第 i-1个结点 if(p=NULL)printf(“无效的插入位置!n”);return 0;else s=(Lnode*)malloc(sizeof(Lnode);/创建新结点 s-data=x;s-next=p-next;p-next=s;return 1;,O(n),删除删除结点删除运算,ai-1,ai-1,ai,ai,ai+1,ai+1,q,p,删除前,删除后,q-nest=p-next;free(p);,int Delete(LinkList head,int i)/在链表中删除第 i 个结点 LNod
18、e*p=head,*s;p=Locate(head,i-1);/找第 i-1个结点 if(p=NULL)printf(“第i1个结点不存在!n”);return-1;else if(p-next=NULL)printf(“第i个结点不存在”);return 0;else s=p-next;p-next=s-next;free(s);/删除s return 1;,O(n),head,a0,a1,a2,【练习1】单链表清空,void makeEmpty(LinkList head)/删去链表中除表头结点外的所有其他结点 LNode*q;while()q=head-next;/将表头结点后第 1 个
19、结点从链中摘下/释放它,head-next!=NULL,head-next=q-next;,free(q);,【练习2】写出函数体 单链表求和函数 typedef int datatype;int sum(LinkList head)LNode*p=head-next;int sum=0;while(p!=NULL)sum+=p-data;/累加 p=p-next;return sum;,循环链表(Circular List),循环链表:使单链表最后一个结点的 next 指针不为 NULL,而是指向了表的最前端。为简化操作,往往在循环链表中加入表头结点。特点:只要知道表中某一结点的地址,就可搜
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 结构 算法 线性 理解
链接地址:https://www.31ppt.com/p-5985356.html