《数据的线性结构》PPT课件.ppt
《《数据的线性结构》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据的线性结构》PPT课件.ppt(82页珍藏版)》请在装配图网上搜索。
“计算机软件技术”课群基础篇之数据结构,第2章数据的线性结构(3学时)第3章查找与排序(2学时),第2章数据的线性结构,2.1.1数据的逻辑结构和存储表示1.基本的概念和术语计算机的应用:科学计算=非数值计算一、两个例子例1、学生档案管理组织成一个二维表,组织成一棵树,例2、在n个城市间建立通信网络,C1,C4,C2,C3,C5,1,3,6,4,代价最小,从上面两个例子中可以看出:数据结构中元素之间存在着逻辑关系,上述例子中给出了三种逻辑结构线性表、树、图。数据结构主要解决:如何分析数据元素之间的关系,并确定合适的逻辑结构;如何在计算机中存储这些数据;为完成对数据的操作设计算法,并作出分析。,二、概念和术语数据(data):表示现实世界中的客观事物、能输入计算机并能被计算机程序处理的符号的总称。数据元素(dataelement):数据集合中的一个个体,是数据的基本单位。(亦称为结点、记录等)数据项(dataitem):数据的不可分割的、含有独立意义的最小单位。数据对象(dataobject):性质相同的数据元素的集合。数据结构(datastructure):相互之间存在着一种或多种关系的数据元素的集合。,数据结构无公认定义,都认为其研究涉及三个方面:数据元素间的逻辑关系(逻辑结构)数据元素的存储方式(物理结构)数据元素间的运算(操作)一般地,一个数据结构中的数据元素属于同一个数据对象。,2.1.2数据的逻辑结构和存储方法一、数据的逻辑结构逻辑结构是指数据元素之间的特定关系,它独立于计算机,是元素之间关系的抽象。1、定义数据结构是一个二元组B=(D,R)。其中D是数据元素(即结点)的有限集合;R是D上的关系的有限集合。一般R中只涉及一种关系。,例如:有4个人,为别为a、b、c、d,其中a是b的父亲,b是c的父亲,c是d的父亲,如果只讨论他们所表达的父子关系,则可以用下面的二元组形式化地表示为:B(D,R)其中D=a,b,c,dR=rr=,,又如:另有4个人,分别为e,f,g,h;其中e是f和g的父亲,g是h的父亲,则可用下面的二元组形式化地表示为:B(D,R)其中D=e,f,g,hR=rr=,,可以用图形方式分别表示为:,a,b,c,d,f,e,g,h,2、几个概念设B=(D,R)是一个逻辑结构,rR,di、djD。如果r,则称di是dj的前驱,dj是di的后继。如果某个结点没有前驱,则称之为开始结点;如果某个结点没有后继,则称之为终端结点;既非开始结点,也非终端结点的结点称之为内部结点。,3、结构分类线性结构只有一个开始结点和一个终端结点,其它结点只有一个前驱结点和一个后继结点,称之为线性结构。即元素之间存在着一对一的关系。非线性结构如果一个结构不是线性结构,则称之为非线性结构。一般地,结构中至少有一个结点存在不止一个前驱结点或后继结点。非线性结构有两类:a、树形结构:元素之间存在着一对多的关系。b、图形结构:元素之间存在着多对多的关系。,线性结构,树形结构图形结构,14,13,12,11,2,3,4,5,6,7,8,9,10,4,5,6,2,3,1,1,2,3,4,5,1,二、数据的存储方法一般地,数据的存储方法有四种:顺序存储链式存储索引存储散列存储(后两种方法主要用于查找,本课程不作详述),1、顺序存储把逻辑上相邻的数据元素存储在物理位置相邻的存储单元之中。通常借助于程序设计语言中的数组来实现。2、链式存储逻辑上相邻的数据元素不要求其物理存储位置相邻,元素间的逻辑关系用附设的指针域来表示。通常借助于程序设计语言中的指针来实现。,例如:有数据结构B=(D,R),其中D=d1,d2,d3,d4,d5R=rr=,则用上述两种存储结构表示为:,顺序存储(假设每个元素占5个存储单元),链式存储,1000,2000,3000,4000,5000,头指针变量,存储地址,存储地址,数据域,指针域,数据域,链式存储图示为:,head,线性结构和非线性结构均可采用这两种存储方法。,2.2线性表的基本概念一、线性表的定义它是最常用且又最简单的线性结构。定义:线性表是n(n0)个性质相同的数据元素所构成的有限序列(a1,a2,a3,.,an)。n称为线性表的长度。当n=0时,称为空表。,数据元素可以是很简单的整数、英文字母等,也可以是较复杂的元素。由复杂元素构成的线性表又称为文件,复杂数据元素称为记录。例如:(1,2,7,5,3,9)(A,D,C,B,E),上面这些都是线性表。,二、线性表的基本运算线性表的初始化(构造一个空的线性表)求表长取第i个数据元素查找具有特定值的结点,确定其序号插入操作(在原表的第i个位置上插入新元素)删除操作(删除原表中第i个元素)随着线性表的存储方法不同,各种运算的实现方法也不一样。下面结合线性表的不同存储结构,讨论实现上述一些运算的算法。,2.3线性表的顺序存储(顺序表)一、顺序表的表示方法用一组地址连续的存储单元依次存放线性表的元素。假设每个元素占用b个存储单元,并以元素的第一个存储单元地址作为元素的存储地址(结点始址),则loc(ai+1)=loc(ai)+b,一般地,第i个元素的存储地址为loc(ai)=loc(a1)+(i-1)*b通常称线性表的第一个元素a1的存储地址为线性表的基地址,设为h,则有loc(ai)=h+(i-1)*b,h,h+b,h+(i-1)b,h+(n-1)b,顺序表特点:逻辑上相邻的元素在物理存储上亦相邻;任一元素的存取时间相同,是一种随机存取结构。(用类C语言描述顺序表),definemaxnum100/*最大元素个数*/typedefstructdatamaxnum;intlength;/*当前长度*/sqlist;返回,二、顺序表上基本运算的实现1、顺序表的初始化把当前表长置0。即:voidinitlist_sq(sqlist*L)*L.length=0;/*或L-length=0*/,2、顺序表的插入操作要求在顺序表的第i个位置上插入一个值为x的新元素。原线性表:(a1,a2,ai-1,ai,ai+1,an)长度为n插入后的线性表:(a1,a2,ai-1,x,ai,ai+1,an)长度为n+1,设i的取值范围为1in+1,插入操作的步骤如下:(算法描述)将anai依次向后移动,为新元素让出位置;将x置入空出的第i个位置;修改表长。,#defineERROR0#defineOK1intlistinsert_sq(sqlist*L,inti,x)intj;if(L-length=maxnum)printf(“listisfull”);return(ERROR);if(iL-length+1)printf(“iisinvalidvalue”);return(ERROR);for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/*元素后移*/L-datai-1=x;/*新元素插入*/L-length+;/*表长加1*/return(OK);返回,3、顺序表的删除操作要求删除顺序表的第i个位置上的元素。原线性表(a1,a2,ai-1,ai,ai+1,an)长度为n删除后的线性表(a1,a2,ai-1,ai+1,an)长度为n-1设i的取值范围为1in,删除操作的步骤如下:将ai+1an依次向前移动;(算法描述)修改表长,intlistdelete_sq(sqlist*L,inti)intj;if(iL-length-1)printf(“iisinvalidvalue”);return(ERROR);for(j=i;jlength;j+)L-dataj-1=L-dataj;/*元素前移*/L-length-;/*长度减1*/return(OK);顺序表插入和删除操作的时间复杂度均为O(n)。返回,2.4线性表的链式存储(链表)2.4.1单链表1、单链表结点结构:链表中每个结点有一个存放数据元素的域,另有一个域存放指向后继结点的指针(表示逻辑关系),故称为单链表。(用类C语言描述为一个结构),typedefstructnodedata;/*数据域*/structnode*next;/*指针域*/NODE;返回,单链表的两种形式,head,head,带头结点的单链表,不带头结点的单链表,指针变量head中存放了链表中第一个结点的起始地址,称之为头指针。该指针变量是“静态”定义的,即用NODE*head;定义了指针变量head。链表中的结点是“动态”生成的(称之为结点变量),每个结点可以存放一个数据元素和后继结点的起始地址。最后一个结点因为没有后继结点,故其指针域中存放NULL(空地址)。当链表中没有数据元素(即空表)时,第一种单链表保留头结点。即,后一种head中为NULL。,head,建立一个空表的算法为(带头结点):NODE*initlist_link()NODE*p;p=(NODE*)malloc(sizeof(NODE);p-next=NULL;return(p);,2、两个标准函数malloc和free设有变量定义:NODE*p;则p=(NODE*)malloc(sizeof(NODE)的作用是由系统生成(得到)一个NODE类型的结点,同时将该结点的起始地址赋给指针变量p。free(p)的作用是由于系统回收(释放)一个由p所指向的NODE类型的结点。注意点:每次调用malloc或free函数只能得到或释放一个结点空间;用malloc函数得到的结点中无确定的内容,必须由程序员给予;用free函数释放一个结点空间,指针变量本身并未释放。,2.4.2单链表上基本运算的实现建立单链表a.正向建:b.逆向建:,head,a1,head,p2,p1,p2,p1,an,a1,head,an-2,head,p,p,算法的详细描述读者可参见本教材实践篇的实验2,单链表的插入操作要求在带头结点的单链表中第i个位置上插入一个值为x的新元素。算法思想:定义三个指针变量p、q和s;(算法描述)在单链表中寻找第i个元素位置,若找到,则由q指向第i个位置,p指向第i-1个位置,继续b);否则结束。向系统申请一个由s指向的新结点,并在数据域置入新元素x。将s指向的新结点插入q之前,结束。,x,p第i-1个位置,q第i个位置,s,intListInsert(NODE*L,inti,x)intj;NODE*p,*q,*s;p=L;q=L-next;j=1;while(q!=NULL该算法的时间复杂度为O(n)。返回,单链表的删除操作要求在带头结点的单链表中删除第i个位置的元素。,p,q第i个位置,算法思想:(算法描述)定义两个指针变量p和q。在单链表中寻找第i个元素位置,若找到则由q指向第i个位置,p指向第i-1个位置,继续b),否则结束。从链表中删除q所指向的结点。释放q所指向的结点空间,结束。,intListDelete(NODE*L,inti)intj;NODE*p,*q;p=L;q=L-next;j=1;while(q!=NULL该算法的时间复杂度为O(n)。返回,2.4.3线性表的其它链式存储1、单循环链表单循环链表是一种特殊的单链表,其最后一个结点的指针域中不存放NULL(空地址),而是放入了链表的头指针。,带头结点的单循环链表不带头结点的单循环链表,head,a1,an,a2,a1,a2,an,head,空表时,head,2、双向链表结点结构:链表中每一个结点除数据域和指向后继结点的指针域外,增加了一个指向前驱结点的指针域。用类C语言描述为:typedefstructdlnodedata;structdlnode*prior,*next;DLNODE;双向链表在做插入和删除操作时,不需要再用两个指针在链表上移动。,双向链表的形式带头结点的双向链表,不带头结点的双向链表,a1,an,非循环,循环,head,a1,an,head,非循环,循环,head,head,3、静态链表用结构数组来描述静态链表。描述方法:#definemaxsize1000/*定义链表的最大长度*/typedefstructdata;intnext;SNODE;SNODEsdmaxsize;intsl;,上图是一个带头结点的单链表,表示了线性表(a1,a2,a3,a4,a5,a6)的链式存储,sl为头指针变量。,data,next,0,1,2,3,4,5,6,maxsize-1,sl=0,2.5栈2.5.1栈的定义和基本运算1、栈的定义实例:装网球的纸筒、子弹夹,a1,an,定义:栈是限定在表的一端(表尾)进行插入和删除操作的线性表。,表尾,表头,允许插入和删除的表尾端称为栈顶。相应的表头端称为栈底。,a1,an,栈顶,栈底,栈的两个要素:存放栈元素的存储空间和栈顶指针。,栈的特点:数据元素后进先出(LIFOLastInFirstOut),2、栈的基本运算栈初始化initstack(s)建立一个空栈s入栈push(s,x)把元素x推入栈s的栈顶出栈pop(s)删除栈s的栈顶元素取栈顶元素gettop(s,x)取出栈s的栈顶元素送入x,由x返回,出栈,入栈,2.5.2栈的存储结构和运算的实现1、顺序存储的栈(顺序栈)用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设栈顶指针top指示栈顶元素在顺序栈中的位置。(类C语言描述为一个结构)例如:,43210,43210,43210,43210,top=-1,top=0,top=4,top=2,#definemaxsize5typedefstructstackintelemmaxsize;inttop;Stack;返回,在顺序栈上基本运算的实现:栈初始化算法描述,43210,top=-1,栈顶指针赋初值-1,voidinitstack(Stack*s)(*s).top=-1;,返回,入栈算法描述,43210,43210,top=1,top=2,if(栈不满)栈顶指针加1;将x的值推入栈顶;else出错;,x=7,#defineERROR0#defineOK1intpush(Stack*s,intx)if(*s).toprear,q-front,队头指针和队尾指针均赋初值-1。即:voidinitqueue(Squeue*q)q-front=q-rear=-1;,入队(算法描述),if(队列不满)队尾指针加1;将元素x插入到队尾;else出错;,43210,43210,q-front,q-rear,q-rear,q-front,#defineERROR0#defineOK1intaddq(Squeue*q,intx)if(q-rear!=maxsize-1)q-rear+;q-elemq-rear=x;return(OK);elsereturn(ERROR);返回,出队(算法描述),if(队列不空)队头指针加1;else出错;,10,15,7,43210,15,7,43210,q-front,q-rear,q-rear,q-front,#defineERROR0#defineOK1intdelq(Squeue*q)if(q-rear!=q-front)q-front+;return(OK);elsereturn(ERROR);返回,取队头元素(算法描述),if(队列不空)队头元素置入x中,由x传出;else出错;,q.front,q.rear,10,15,7,43210,10,15,7,43210,q.rear,q.front,#defineERROR0#defineOK1intgetfront(Squeueq,int*x)if(q.rear!=q.front)*x=q.elemq.front+1;return(OK);elsereturn(ERROR);返回,2、链式存储的队列(链队列)用一个带头结点的单链表作为存储结构。同时根据队列的FIFO原则,它需要一个头指针和一个尾指针。其结点结构和前面的单链表相同。,图中front和rear是两个独立的指针变量,从结构性上考虑,通常把二者封装在一个结构中。,front,rear,基本运算的实现可参见本教材实践篇实验3,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据的线性结构 数据 线性 结构 PPT 课件
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文