[数据结构课件] 第2章 线性表.pdf
《[数据结构课件] 第2章 线性表.pdf》由会员分享,可在线阅读,更多相关《[数据结构课件] 第2章 线性表.pdf(117页珍藏版)》请在咨信网上搜索。
1、从第2章至第4章将讨论 线性结构。线性结构的特点是:在数据元素的非空有限集中,/(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元 素;(3)除第一个之外,集合中的每个数据元素均只有 一个前驱;(4)除最后一个之外,集合中每个数据元素均只有 一个后继。第2章线性表第2.1线性表的类型定义 2.2线性表的顺序表示和实现、2.3线性表的链式表示和实现目2.4 一元多项式的表示及相加21线性表的类型定义a学时)V/乂性(Linear_List)是最常地目晨简单的一种数据结构。简言之,一个线性表是n个数据元素的有限序列。至于每个 数据元素的具体含义,在不同的
2、情况下各不相同,它可以 是一个数、或一个符号,也可以是一页书,甚至其它更复 杂的信息。例如,26个英文字母的字母表:(A,B,C,,Z)是一个线性表,表中的数据元素是单个字母字符。又如,某校从1978 年到1983年各种型号的计算机拥有量的变化情况,可以用线性表的形 式给出:(6,17,28,50,92,188)表中的数据元素是整数。在稍复杂的线性表中,一个 可以由若干个(Item)组成。在这种情况下,常把数据元素称为(Record),含有大量记录的线性表又称(File)。例如,一个学校的学生健康情况登记表如图2.1所示,表中每个学 生的情况为一个记录,它由姓名、学号、性别、年龄、班级和健康状
3、况 等六个数据项组成。图2.1学生健康情况登记表姓名学号性别年龄班级健康状况王小林790631男18计98健康陈红790631女20计98一般刘键平790633男21计98健康张立立790634男17计98神经衰弱 综合上述三个例子可见,线性表中的数据元素可 以是各种各样的,但同一线性表中的元素必定具有相 同特性,即属同一数据对象,相邻数据元素之间存在 春序偶关系。若将线性表记为,、/(a,冏一1,a1+i,(2 1)线性表中元素的个数n(nNO)定义为线性表的长度,n=0时称为空表。在非空表中的每个数据元素都有一个 确定的位置,如为是第一个数据元素。位是最后一个 数据元素,码是第i个数据元素
4、,称i为数据元素马在线 性表中的位序。线性表是一个相当灵活的数据结构,它的长度可根据 需要增长或缩短,即对线性表的数据元素不仅可以进行访 问,还可进行插入和删除等。/抽象数据类型线性表的定义如下:ADT List数据对象:D=aj|a,eElemSet,i=1,2,3,n,n0数据关系:R1=|如-eD,i=2,.,n基本操作:/lnitList(&L)I 操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已存在。操作结果:销毁线性表。ClearList(&L)初痛条件:线性表L已存在。/I操作结果:将L重置为空表。ListEmpty(L)初法条件:线性表L已存在
5、操作结果:若L为空表,贝U返回TRUE,否则返回FALSE。ListLength(L)初始条件:线性表L已存在。操作结果:返回L中数据元素个数。GetElem(L,i,&e)初始条件:线性表L已存在,iWKListLength(L)。操作结果:用e返回L中第i数据个元素的值。ILocateElem(L,e,compare()初始条件:线性表L已存在,compare()是数据元素判定函数。操作结果:返回1_中第1个与e满足关系compare()的数据元素的位序。不存在,则返 值为0。PriorElem(L,cur_e,&pre_e)初始条件:线性表L已存在、/I操作结果:若cur_e是L的数据元
6、素,且不是 第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。NextElem(L,cur_e,&next_e)初始条件:线性表L已存在。操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作作失败,next_e 无定义。Listlnsert(&L,i,e)初始条件:线性表L已存在,1iListLengWL)+1o/操作结果:在L中第i个立置之前插入新的数据元素e,L的长廖加1。/IListDelete(&L,i,&e)初始条件:线性表L已存在且非空,1i ListLength(L)o操作结果:删除L的第i个数据元素,并用e返回其值,L的
7、长度减1。ListTraverse(L,visit()初始条件:线性表L已存在。I操作结果:依次对L的每个数据元素调用函数visit()oADT List例2-1假设利用两个线性表LA和LB分别表示两个集合A 和B(即:线性表中的数据元素即为集合中的成员),现要求一 个新的集合A二AUB。V/void union(List&La,List Lb)I 将所有在线性表Lb中但不在La中的数据元素插入到La中 HLa_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/La中不存在和e相同的数据元
8、素,则插入 if(!LocateElem(La,e,equal)Listinsert(La,+La_len,e);/union-算法?1-例2-2已知线性表LA和LB中的数据元素按值非递减有 序排列,现要求将LA和LB归并为一个新的线性表LC,且LC 中的数据元素仍按值非递减有序排列。例如,设 ILA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,8,9,11,11,15,20)void MergeList(List La,List Lb,List&Lc)已知线性表La和Lb中的数据元素按值非递减排列。归并La/I 和Lb得到新的线性表Lc,Lc的
9、数据元素也按值非递减排列。/InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLehgth(Lb);while(i=La_len)&(j=Lb_len)Get曰em(La,i,&ai);GetElem(Lb,j,&bj);if(ai=bj)Listlnsert(Lc,+k,ai);+i;else Listinsert(Lc,+k,bj);+j;)算法2.2上述两个算法的时间复杂度分析:假如GetElem和Listinsert这两个操作的执行时间 和表长无关,LocateElem的执行时间和表长成正比,邛 /H/算法2的时间复杂度y
10、,.O(ListLength(LA)*ListLength(LB),算法2.2的时间复杂/则 O(ListLength(LA)+ListLength(LB)o虽然算法2.2中含三个(while)循环语句,但只有当i和j均指向 表中实际存在的数据元素时,才能取得数据元素的值并进行相互 比较;并且当其中一个线性表的数据元素均已插入到线性表LC中 后,只要将另外一个线性表中的剩余元素依次插入即可。因此,对于每一组具体的输入(LA和LB),后两个(while)循环语句只执行 一个循环体。2.2线性表的顺序表示和实现(1学时)线性表的顺序表示指的是用一组地址连续的存储单元依 次存储线性表的数据元素。假设
11、线性表的每个元素需占用L个存储单元,并以所占 的第一个单元的存储地址作为数据元素的存储位置。则线性 表中第i+1个数据元素的存储位置LOC(aj+i)和第i个数据元素 的存储位置LOC(aJ之间满足下列关系:LOC(ai+1)=LOC(aj)+L一般来说,线性表的第i个数据元素司的存储位置为 ILOC(aJ=L0C(ai)+(i-1)*L式中LOC(ai)是线性表的第一个数据元素的存储位置,通 常称做线性表的起始位置或基地址。线性表的这种机内表示称做线佳表的小同雷结构或顺(Sequential Mapping),反之,称这种存储结构的线性存储地址 表为顺序表。它的特点是,为表中相邻 b 的元素
12、马和ai+1赋以相邻的存 b+i、储位置 LOC(a)和 LOC(aj+i)。换句话说,以元素在计算机内内存状态a2数据元素在线 性表中的位序12“物理位置相邻”来表示线性 表中数据元素之间的逻辑关系o(见图2.2)。由此,只要确定 了存储线性表的起始位置,线 性表中任一数据元素都可随机 存取,所以线性表的顺序存储b+(i-1)*Laib+(n-1)*L结构是一种 的存储结构。由于高级程序设计语言中的数组类型也有随机存取的 特性,因此,瞰都用数组来描述数据结构中的顺年存储 结核。在此,由于线性表的长度可变,且所需最存储空间 随问题不同而不同,则在C语言中可用动态分配的一维数 组,如下描述。/-
13、线性表的动态分配顺序存储结晶一 仙efine LIST_INIT_SIZE 100 线性表存储空间的初始分配量#define LISTINCREMENT 10 线性表存储空间的分配增量 Mtypedef struct ElemType*elem/存储空间基址int length;当前长度int listsize;/当前分配的存储容量(以sizeof(ElemType)为单位)JSqList;Status lnitList_Sq(SqList&L)构造-个空的线咐L。V/L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(E1emType)if(!L.e
14、lem)exit(OVERFLOW);/存储分配失败L.length=0;/空表长度为0L.listsize=LIST_INIT_SIZE;/初始存储容量return OK;/lnitList_Sq算法2.3在这种存储结构中,容易实现线性表的某些操作,如随机存取第i个数据 元素等。只是要特别注意的是,C语言中数组的下标从“0”开始,因此,若L是SqList类型的顺序表,则表中第i个数据元素是L.EIemi-1。下面重 点讨论线性表的插入和删除两种操作在顺序存储表示时的实现方法。图2.3线性表插入前后的状况(a)插入前n=8;(b)插入后n=9;序号序号数据儿余儿乐112112213213321
15、321插入4 _A2442425 5285256306287427308778429977(a)(b)例如,图2.3表示一个 线性表在进行插入操作的前、后4其数据元素在存储空间 中的位置变化。为了在线性 表的第4和第5个元素之间插 入一个值为25的数据元素,则需将第5个至第8个数据元 素依次往后移动一个位置。|一般情况下,在第 1 i(14Wn)个元素之前插入一个 元素时,需将第n至第i(共n-i+1)个元素向后移动一个位 置,如算法2.4所示。Status Listlnsert_Sq(SqList&L,int i,ElemType e)/在顺序线性表L中第i末位置之前插入新的元素e,/./i
16、的合法值为 14iVListLength_Sq(L)+1if(iL.length+1)return ERROR;i值不合法/if(Length 二Listsize)/当前存储空间已满,增加分配 newbase=(ElemType*)realloc(L.elem,(L.1istsize+LISTINCREMENT)*sizeof(ElemType)if(!newbase)exit(OVERFLOW);存储分配失败L.elem=newbase;新基址L.listsize+=LISTINCREMENT;/增加存储容量q=&(L.EIemi-1);/q 为插入位置for(p=&(L.elemL.len
17、gth-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入 e+L.length;/表长增 1return OK;/Listinsert _Sq算法2.4反之,线性表的删除操作是使长度为n的线性表变成长度为n-1的线性表。/一般情况下,删除第i(14in)个元素时需将从第 i+1至第n(共n-i)个元素依次向前移动一个位置,如算法 2.5所示。Status ListDelete_Sq(SqList&L,int i,ElemType&e)/在顺序线性表I中删除第i个元素,并用e返回/其值,i的合法值为10iListLength_Sq(L)if(iL.length)
18、return ERROR;p=&(L.elemi-1);/p为被删除元素的位置/e=*p;/被删除元素的值赋给e q=L.elem+L.1ength-1;表尾元素的位置 for(+p;pnext;7 j=i;初始化,p指向第一个元素结点,j为计数器 while(p&jnext;+j;)if(!p|ji)return ERROR;第i个元素不存在 e=p-data;/取第i个元素return OK;/GetElem_L算法2.8“插入r和”在单链表中,何实现r操作呢?(a)插入前;为插入数据兀素X,首先要 生成一个数据域为X的结点,然 后插入在单链表中。根据插入操 作的逻辑定义,还需要修改结点a
19、中的指针域,令其指向结点x,而结点x中的指针域应指向结点 b,从而实现三个元素a,b和x 之间逻辑关系的变化。插入后的 单链表如图2.8(b)所示。假设s 为指向结点x的指针,则上述指 针修改用语句描述即为:s-next=p-next;p-next=s;a(b)插入后。图2.8在单链表中插入 结点时指针变化状况反之,如图2.9所不在 线性表中删除元素b时,为 在单链表中实现元素a、b和 c之间逻辑关系的变化,仅 需修改结点a中的指针域即 可。假设p为指向结点a的指 针,则修改指针的语句为:p-n ext=p-n ext-next;可见,在已知链表中元 素插入或删除的确切位置的 情况下,在单链表
20、中插入或 删除一个结点时,仅需修改 指针而木需要移动兀素。J j一 a;b 1c图2.9在单链表中删除结 点时指针变化状况算法2.9和算法2.10分别为Listinsert和ListDelete在单链浮中的实现。A/Status Listlnsert_L(LinkList&L,int i,ElemType e)/在带头结点的单链线性表L中第i个.I/位置之前插入元素e/.p=L;j=0;while(p&jnext;+j;/寻找第i-1 个结点if(!p|ji-1)return ERROR;s=(LinkList)malloc(sixeof(LNode);s-data=e;s-n ext=p-n
21、ext;p-next=s;return OK;/Listlnsert_L算法2.9Status ListDelete_L(LinkList&L,int i,ElemType e)/在带头结点的单链线性表L,删/除第i个元素,并由e返回其(/p=L;j=0;while(p-next&j next;+j;)if(!(p-next)|j-1)return ERROR;q=p-next;,p-next=q-next;册!I除并释放结点 e=q-data;free(q);return OK;/ListDelete_L删除位置不合理算法2.10单链表和顺序存储结构不同,它是一种动态结构。整个可用存储空间可
22、为多个链表共同享用,每个链表 占用的空间不需预先分配划定,而是可以由系统应需 求即时生成。因此,建出性表的链式上储结构的过 程就是一个动态生成链表的过程。即从“空表”的初 始状态,依次建立各元素结点,并逐个插入链表。void CreateList_L(LinkList&L,int n)逆位序输入n个元素的值,建立带表头结点的单链线性表L。L=(LinkList)malloc(sizeof(LNode);/L-next=NULL;先建立一带头结点的单链表 Ifor(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);输入元素值7 H
23、p-next=L-next;L-next=p;/插入至表头)算法2.11(其时间复杂度为0(n)。)下面讨W如何够两个有序 链表则一个有序冷?假设头指针为La和Lb的单 链表分别为线性表LA和LB的存 储结构,现要归并La和Lb得到 单链表Lc,按照2.1节中算法 MergeList的思想,需设立三个 指针pa、pb和pc,其中pa和pb 分别指向La表和Lb表中当前待 比较插入的结点,而pc指向Lc 表中当前最后一个结点,若pa-data data,则将pa所指 结点链接到pc所指结点之后,否则将pb所指结点链接到pc所 指结点之后。/paLa|十void MergeList_L(LinkL
24、ist&La,LinkList&Lb,LinkList&Lc)/已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc,/Lc的元素也按值非递减排列o pa=La-next;pb=Lb-next;Lc=pc=La;用La的头结点作为Lc的头结点while(pa&pb)if(pa-data data)pc-next=pa;pc=pa;pa=pa-next;)else pc-next=pb;pc=pb;pb=pb-next)pc-next=pa?pa:pb/插入乘U余段free(Lb);释放Lb的头结点/MerqeList_L算法2.12有时,也可借用一维数组来描述线性
25、链表,其类型说 明,如下所示:线性表的静态单链表存储结构Y/#define MAXSIZE 1000 链表的最大长度typedef structElemTyPe data;int Cur;component,SLinkList MAXSIZE;这种描述方法便于在不设“指针”类型的高级程序设 计语言中使用链表结构。在如上描述的链表中,数组的一 个分量表示一个结点,同时用游标(指示器cur 代替指针 指示结点在数组中的相对位置。数组的第零分量可看成头 结点,其指针域指示链表的第一个结点。1ZHAO2QIA.3SU4LI/5ZHOU6WU7ZHENG8WANG011ZHAO22QIAN33SUN44
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课件 数据结构课件 第2章 线性表 数据结构 课件 线性
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。