版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构,第二章 线性表,第二章 线性表,知 识 点 线性数据结构的基本特征和基本运算 线性表的存储结构 双向链表 循环链表 难 点 循环链表 利用本章的基本知识设计有效的算法解决与线性相关的应用问题,要 求 熟练掌握以下内容: 线性表的基本运算 线性表的特征、基本运算并能设计简单算法 了解以下内容: 线性表运算时间复杂性分析,第二章目录,2.1 线性表的逻辑结构 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 循环链表 2.5 双向链表 小 结 习题与练习,2 线性表(Linear List),线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素, 除了第一个和最后一个以
2、外,都有一个且只有一个前驱元素,同时也都有一个且只有一个后继元素; 第一个元素只有一个后继元素而无前驱元素;最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度,当n=0时,这个表叫做空表。,线性表在计算机内存中采用各元素顺序存储的方式,这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数,由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单,用的也最普遍。,2.1线性表的逻辑结构,线性表的定义 例:Monday,Tuesday,Wednesday, Thursday
3、,Friday,Saturday, Sunday 又 Score=sdudent1,50,student2,60, student3,70 注意线性表和集合的区别。 线性表元素之间是有序的,而集合元素 之间是无序的。,2.1线性表的逻辑结构,线性表的定义 线性表是由n个结点a1,a2,.,an 组成的有限序列,当n=0时,线性表为空,即为空表。 若n0, 则a1是第1个结点,an是最后一个结点。 其形式化的定义为: S=(D,R) 其中:D是由n个元素组成的集合, R是定义在集合D上的一种关系。,2.1线性表的逻辑结构,线性表的逻辑结构 线性表的元素类型是多样的,但同一线性表中的元素必须是同一
4、类型,且相邻元素之间存在一种序偶关系。,2.1线性表的逻辑结构,线性表的基本运算: 1. 求线性表的长度n; 2. 在第i个数据元素前面插入一个新的数据元素; 3. 删除第i个数据元素; 4. 存取或更新线性表第i个元素; 5. 将两个或两个以上的线性表合并成一个线性表; 6. 将一个线性表拆成多个线性表; 7. 将线性表中各数据元素按某个域值(如关键字) 递增或递减的顺序重新排列; 8. 在线性表中查找满足某种条件的数据元素;,2.2 线性表的顺序存储,线性表的顺序存储结构(顺序表) 例:一顺序表 A=(3,6,8,9,2) 顺序存放在一维数组中 顺序存储的特点: 逻辑顺序与物理顺序一致,
5、元素之间的关系由物理位置的相邻关系体现,2.2 线性表的顺序存储,地址计算 设顺序表的每个元素占c个存储单元,并且元素所占的第一个单元的存储地址作为顺序表的存储位置,则顺序表中第I个元素的存储位置 Loc(ai)满足 Loc(ai)=Loc(ai-1)+ c Loc(ai)=Loc(a1)+(i-1)* c,2.2 线性表的顺序存储,结点描述 #define Maxlen typedef struct seqenlist elementtype elements maxlen; int lenth; list;,顺序存储下线性表的运算,1. 数据元素的插入(insert),在顺序表L=(a1,
6、a2, ,ai,an)中第i个元素前插入元素b,使成为 L=(a1,a2, b ,ai, an) 基本思想:把顺序表表中第I个元素至第n个元素后移一个位置,把元素b插入到第i个位置上,线性表的长度加1。,插入函数,int insert(list L, int i, elementtype x) int k; if (iL.lenth+1) printf(“i值错!n”); else for (k=L.lenth; k=i-1; k-) L.elementsk=L.elementsk-1; /*将第i个元素及其后面的元素后移*/ L.elementsi-1=x; L.length+; /*顺序表
7、长度加1*/ return(0); ,插入函数分析,在循环语句中,当i=1时,须循环n次,表示元素插入线性表头的前面,则原线性表中n个元素均须向后移动一个单元,这是最不利的情况。 当i=n+1时,则循环一次也不进行,这时元素直接插入到线性表尾的后面,所以线性表的所有n个元素均不移动,这是最好的情况。,2. 元素的删除(Delete),在顺序表L=(a1,a2, ,ai,an)中删除第i个结点,使成为 L=(a1,a2,ai-1, ai+1, an) 基本思想:要求删除第i个数据元素,由于线性表元素在数组中必须连续排列,中间不能有空单元,故将此元素删除后,它后面的所有元素都需要向前移动一个单元,
8、且数据元素总数由原来的n减少到n-1.,删除函数,Int delete(list L, int i) /*删除顺序表中第I个结点 int k; if (iL.lenth) printf(“i值错!n”); else for (k=i; kL.lenth;k+) L.elementsk-1 = L.elementsk; /*I以后的元 L.lenth- ; /*素前移 return(0) ,删除函数分析,在循环语句中,当i=1时,需循环(n-1)次,这是要删除线性表表头元素,是最不利的情况; 当i=n时,则循环一次也不执行,只是将元素数目n比原来减少一个,而第n个数据元素不必再考虑,其余的各单元
9、的元素均维持不变,这是最好的情况。,算法的时间复杂性,可以用数据元素的移动次数来度量这两个算法的时间复杂性。 插入时,最少循环0次,最多循环n次,如i的各种取值概率相同,则平均循环次数为n/2; 删除时最少的循环次数为0次,最多为n-1次,当i取值概率相同时,平均循环次数为(n-1)/2。 用数量级的形式表示线性表插入、删除运算的时间复杂性均为O(n)。,3.查找定位删除操作,删除一个值为X的元素 基本思想:在线性表中,查找到值为X的元素ai,将 i 之后的元素前移一个位置,且线性表的长度减1。,Int LocateDeleteSeqlist(list sl; elementtype:x) I
10、nt I=0, j; /*删除值为X的元素 IF(sl.lenth=0) printf (“空表!n”); While(Isl.lenth) If (sl.elementsI!=x) I+; else for (j=I+1;j=sl.lenth;j+) sl.elmentsj-1=sl.elementsj ; sl.lenth-; break; 该语句的作用? ,if (i=L.lenth) printf(“i值错!n”); return(0); 顺序表的应用举例,2.3 线性表的链式存储,2.1 单链表 结点: 在链式存储结构中,结点不仅存放数据元素的值,还附加一个指针(链),用来指向该结点
11、的直接后继结点。 其中,data部分称为数据域,用于存储线性表的一个元素,next部分称为指针域或链域,用于存放一个指针,即存放该结点的直接后继结点的地址。,所有结点通过指针的链接而构成的线性表称为单链表。线性表(a1,a2,an,)的单链表可直观地画成: head是单链表的头指针,指向开始结点a1, an是终端结点,其指针域为空,不指向任何结点。 一个单链表由头指针head唯一标识和确定,因此,可用头指针来命名单链表。,单链表的类型定义,单链表的的结点类型定义如下: typedef struct Lnode elementtype data; struct lnode *next; link
12、list 一个结点是由两个域data和next组成的记录, data是结点的数据域,next是结点的链域。,链表举例 空表 ,H,a1,an,为了编程方便,一般在单链表的第一个结点之前加一个“头结点”,如: 当为空表时,即head-next=null, 如下图。,a1,an,head,head,指针的概念,假设p是一个pointer类型,应正确区分指针型变量、指针、指针所指的结点和结点的内容这四个密切相关的不同概念: p的值(如果有的话)是一个指针,即是一个所指结点的地址 。 该指针(若不是NULL)指向的某个node型结点用*p来标识。 结点 *p是由两个域组成的记录,这两个域分别用pdat
13、a域和pnext域来标识,它们各有自己的值,pdata的值是一个数据元素,pnext的值是一个指针。,2.3.2 单链表的基本运算,1. 遍历(Traversal):根据已给的表头指针,按由前向后的次序访问单链表的各个结点。 在实际应用中遍历是对单链表的最基本运算,例如,当要打印或显示出各个结点的数值域值、计算单链表的长度(即结点数目)或寻找某一个结点时都需要遍历单链表。 假设head是单链表的头指针,计算一个已建立好的单链表的结点个数的算法如下:,计算结点个数算法,int length(head) /*求表head的长度*/ int count=0; /*计数器置初值*/ p=head; /
14、*p指向头结点*/ while (p!=NULL) p=p-next; count+; return(count); /*返回表长值*/ ,算法分析,此算法的关键是while循环语句,开始时p指针指向头结点,每一循环都修改指针值,让它指向下一个结点,同时将计数链表长度的变量count加1。 这样每循环一次就向后推移一个结点,直到p所指结点*p的链域值为NULL为止。 空指针NULL起标志的作用,若无此标志,尾结点链域的值为“无定义”,上述算法中的while语句在做最后一次判断时将出现“运行错”,这是应予避免的。,2. 插入,所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x的结点。
15、实现插入算法主要完成三个基本操作: 1) 在单链表上找到插入位置,即找到第i个结点。 可以用遍历的方法,即从表头起顺次访问单链表的结点,直至找到第i个结点。 2) 生成一个以x为值的新结点。 可通过C的库函数malloc(size)来产生。 3) 将新结点链入单链表中。 需要改变相关结点的指针 ,如下面的图所示。,假设指针p指向单链表中的第i个结点,指针s指向已生成的新结点,链入新结点的操作如下: 将新结点*s的链域指向结点*p的后继结点 (即s-next=p-next); 将结点*p的链域指向新结点(即p-next=s)。,insert(head) /*在第i个结点后插入结点S linkli
16、st *p=head; int k=0; while (p!=null) $ (knext; k=k+1; s=(linklist *)malloc(sizeof(linklist) if (s= =null) printf (“没有足够的空间”) Return(null) s-next=p-next; p-next=s; return(head),插入算法,Linklist *insertllist (head, x, k) / 在头指针为 linklist *head; head的单链表的第K个 elementtype x;结点之前插入X int k; linklist *p,*pre,*
17、s; int j=1;p=head;pre=null; while (p!=null) $ (jnext;/*结点pre j+ ,插入算法续,if(j!=k) printf(“k超出链表的长度”); return(null); s=(linklist *)malloc(sizeof(listlist) if (s= =null) printf (“没有足够的空间”) Return(null) ,插入算法续,s-data=x; If (pre=null) /*插入的结点位于链 s-next=head; /*表的头部,即k=1 head=s; else s-next=p; pre-next=s;
18、return(head) ,3. 删除,假设单链表带有头结点,头指针为head,删除单链表上一个其值为x的结点。主要操作 是: 1) 用遍历的方法在单链表上找到该结点; 2) 从单链表上删除该结点。 欲从单链表上删除一个结点,需修改该结点的前一个结点的指针,如下面的图所示。,假设指针q指向待删除结点的前一个结点,指针p指向要删除的结点,删除该结点的操作如下:将该结点的前一个结点*q的链域指向*p的后继结点(即q-next=p-next)。,删除算法,Linklist * Delete (head, x) linklist *head; elementtype x; linklist *q,*p
19、; q=head; p=head-next; while(p!=null) ,删除算法续,if (p=NULL) printf (“x不存在 ”) return(null); else q-next=p-next; /*修改指针 free(p); return(head); ,返回,2.3.3 静态链表,在某些语言中,没有指针类型,就不能实现链表,可用一数组来模拟链表,这就是静态链表。 静态链表的定义 #define maxsize typedef struct elementtype data; int next; slinklist;,如: slinklist slmaxsize; 定义了
20、一个有maxsize个元素的数组,每个元素由信息域和指针域组成。,例:L=(a,b,c,d,e,f), 0 0 1 1 2 2 3 3 4 4 5 5 6 6 插入h之后,2.3.4 线性表实现方法比较,链表:在已知元素个数的情况下,浪费空间; 在未知元素个数的情况下,节约空间; 速度快。 顺序表:在已知元素个数的情况下,空间利用率 高; 在未知元素个数的情况下,可能浪费空 间,利用率低; 速度慢。,2.4 循环链表,循环链表(circular linked list)是一种首尾相接的链表,将单链表表尾结点原来的空指针改为指向表头结点,就成为循环链表。 循环链表并不多占存储单元,但从循环链表的
21、任一个结点出发都可以访问到此链表的每一个结点,因为当访问到表尾结点后又能返回到头结点。,1. 带头结点的循环链表,通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。 表空时空表头结点的指针指向其本身,如下面的图所示为空循环链表。 空表头结点除指针以外的数据域是没有用的,但为了将此结点与一般结点相区别,常常是将其赋以一个特别的数据,以与一般结点相区别。,若p-next=head,则p就是指向最后一个结点; 若head-next=head,则为空表。 例:约瑟夫(Josephus)问题。设编号为1,2,n(n0)个人,按顺时针围坐一圈,每人有一正整数密码m。 首先给定一正整数m,从第1个
22、人开始(顺时针),枪毙第m个人,之后,以该人的密码作为m的新值,继续下去,基本思想: 首先建立一个带头结点,有n个结点的循环链表,头指针为head; 对给定的m(第1次给定m,以后即为结点的pwd),从第一个结点开始,寻找第m个结点,将其输出,并取出该结点的pwd,执行m=pwd;从下一个结点继续寻找第m个结点, 直到表空为止。,结点定义为: Typedef struct Jnode int no; int pwd; struct Jnode *next; clinklist;,Int josephus_seqlist( pseqlist josephus_sq,int s,m) /*顺序存储
23、在josephus_sq中,从第s个元素开始 s1=s-1; for ( i=josephus_seq-length; i0; i-) s1=(s1+m-1)%i; w=josephus_seq-datas1; printf(“ ”,w); delete_seqlist(josephus_seq, s1+1) ,2. 带尾指针的循环链表,另一种方法是不设头指针而改设尾指针,这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示,则头结点的位置是rear-next-next。,2.5 双向链表,双向链表中每个结点除了有向后指针外,还有指向其前一个结点的指针,这样形成的链表中有两条
24、不同方向的链,因此从某一结点均可向两个方向访问。 双链表的结点形式为: 其中链域prior和next分别指向本结点的直接前趋和直接后继结点。,如果循环链表的结点再采用双向指针,就成为双向循环链表。,双向链表为空链表时, head 即 head-next=null,双链表较单链表虽然要多占用一些存储单元,但对其插入和删除操作以及查找结点的前趋和后继都非常方便。 双链表结构是一种对称结构,设指针p指向双链表的某一结点,则双链表的对称性可用下式来表示: p=(p-prior)-next=(p-next)-prior 即结点*p的地址存放在其前趋结点 *(p-prior)的后继指针域中,又存放在它的后
25、继结点*(p-next)的前趋指针域中。,结点定义为: Typedef struct dbnode elementtype data; struct dbnode *prior; struct dbnode *next; Dblinklist;,1. 双链表的插入,设要在p所指结点的前面插入一个新结点*q,则需要修改4个指针 : q-prior=p-prior; q-next=p; (p-prior)-next=q; p-prior=q;,2. 双链表的删除,设p指向待删除的结点,则删除该结点步骤为: (p-prior) -next=p-next; (p-next) -prior=p-prio
26、r; 这两个语句的执行顺序可以颠倒,执行这两个语句之后,可调用free(p),将*p结点释放。,2.6 多项式的加法,运算规则 将二个一元多项式中所有指数相同项的系数相加,相加后,若和不为零,则构造 “和多项式”中的一项; 若和为零,则“和多项式”中无此项; 所有指数不相同的项均考贝到“和多项式”中。,1. 如果用数组来表示一元多项式,以各项的指数作为下标,将各个系数存入一维数组中。 设一个一元多项式为,2. 用单链表表示一元多项式 将单链表的每个结点对应着一元多项式中的一个非零项,它由三个域组成,分别表示非零项的系数、指数和指向下一个结点的指针。 求此两多项式之和C(x)=A(x)+B(x)
27、。,结点的定义如下:typedef struct pnode real coef; Int exp; Struct pnode *next; polyn;,把多项式B(x)加到A(x)中。 基本思想:设A和B为多项式A和B的搜索指针,比较其指数项, 若A-expexp, 则A结点应是和多项式中的一项,A后移; 若A-expB-exp, 将B结点插入到A结点之前,B后移; 若A-exp=B-exp, 则两结点的系数相加,若和不为0,修改A结点的系数,A,B后移;若为0,删除两结点。A,B后移。,例3.1,一个单链表L(至少有一个结点),其头结点指针为head,编写一个函数将L倒置。 基本思想:从
28、头到尾遍历单链表L,并设置3个附加指针p、q、r, p指向当前处理的结点,q指向p的后继,r指向q的后继,q、r的作用是为了防止倒置指针时,下一个结点丢失而设置的。 最后将第一个结点的next域置为NULL,并将头指针指向最后一个结点。,例3.1算法,void invert(node *head) node *p,*q,*r; p=head; q=p-next; while(q!=NULL) /*没有后继时停止*/ r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; ,例3.2,有两个循环单链表,头指针分为head1和head2,编写函数
29、将链表head2链接到链表head1之后,链接后的链表仍保持是循环链表的形式。 解:先找到两个表的表尾,将head2放入链表head1的表尾,然后将head1放入原head2链表的表尾。,例3.2算法,link(node *head1, *head2) node *p,*q; p=head1; while(p-next!=head1) p=p-next; q=head2; while(q-next!=head2) q=q-next; p-next=head2; q-next=head1; ,例3.3,给出在双链表中第i个结点(i0)之后插入一个元素为x的结点的函数。 解:在前面双链表一节中,已经给出了在一个结点之前插入一个新结点的方法,在一个结点之后插入一个新结点的思想与前面是一样的。,例3.3算法,void insert(dnode *head,int i,x) dnode *s,*p; int j; s=(dnode *)malloc(sizeof(dnode); /*建立一个待插入的结点,由s指向*/ s-data=x; if(i=0) /*如i=0,将s所指结点插入到表头后返回*/ s-next=head; head-prior=s; head=s; ,例3.3算法续,else p=head; /*查找第i个结点,由p
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年农业行业并购整合趋势及投后管理研究
- 2026年单身公寓产业发展报告:独居经济场景解析与市场预测
- 2026年教育行业危机预警与应对策略分析
- 2026年制造业项目进度管理及风险应对报告
- 2026年动漫行业5G虚拟偶像产业发展报告
- 2026年金融科技行业分析报告:区块链技术应用与风险控制
- 2026年洗鞋行业市场细分领域市场机遇研究报告
- 2026年金融服务收费模式创新分析报告
- 2026年婚庆市场趋势分析报告及未来五年行业预测
- 2026年新能源产业数字化管理看板市场研究报告
- 小学道德与法治新部编版五年级上册全册教案(2026秋)
- 驾驶员素质提升培训
- My family幼儿园家庭成员介绍手抄报
- 国家安全教育大学生读本-第一章完全准确领会总体国家安全观
- 2016年公务员国考《申论》真题卷及答案(副省级)
- 《外科学》教案:第七章 麻醉
- 产后康复经络与腧穴
- 2023航标灯光强测量和灯光射程计算
- 《工业机器人技术基础》第5章 工业机器人控制系统课件
- 化工传递过程基础全部
- 边坡滑坡及治理
评论
0/150
提交评论