第11章 数据结构和数据抽象

上传人:无*** 文档编号:244352805 上传时间:2024-10-04 格式:PPT 页数:26 大小:93KB
返回 下载 相关 举报
第11章 数据结构和数据抽象_第1页
第1页 / 共26页
第11章 数据结构和数据抽象_第2页
第2页 / 共26页
第11章 数据结构和数据抽象_第3页
第3页 / 共26页
点击查看更多>>
资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,程序设计基础(C语言)wh,*,第 十一 章,数据结构和数据抽象,10/4/2024,1,程序设计基础(C语言)wh,本章内容,11.1,数据抽象,11.2,线性表,11.3,堆栈,11.4,队列,小 结,10/4/2024,2,程序设计基础(C语言)wh,11.1,数据抽象,11.1.1,数据结构和数据类型,数据结构用来反映数据的内部构成 ,有逻辑上的数据结构和物理上的数据结构之分 。,数据类型是一个值的集合和定义在此集合上的一组操作的总称。,数据结构是指计算机处理的数据元素的组织形式和相互关系,数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型支持下,可以根据从问题中抽象出来的各种数据模型,逐步构造出描述这些数据模型的各种新的数据结构。,10/4/2024,3,程序设计基础(C语言)wh,11.1.2,抽象数据类型,抽象数据类型,(abstract data type, ADT),是用户进行软件设计时,从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的一组操作,而不考虑计算机的具体存储结构和操作的具体实现算法。,抽象数据类型可用,(D, S, P),三元组表示。其中,,D,是数据对象;,S,是,D,上的关系集;,P,是,D,中数据运算的基本运算集。其基本格式如下:,ADT,抽象数据类型名,数据对象:,数据关系:,基本运算:, ADT,抽象数据类型名,10/4/2024,4,程序设计基础(C语言)wh,11.2,线性表,11.2.1,线性表的定义,线性表是具有相同特性的,n(n0),个数据元素的有限序列,通常记为:,(a1,,,a2,,, ai-1,,,ai,,,ai+1,,, an),其中,n,为表长,,n,0,时称为空表。,特点:,均匀性:同一线性表的各数据元素必定有相同的数据类型和长度。,有序性:有唯一的“第一个”和“最后一个”元素,每个元素只有一个直接前趋和一个直接后续。,10/4/2024,5,程序设计基础(C语言)wh,11.2.2,线性表的基本操作,线性表上的基本操作有:,(1),线性表初始化:,InitList(&L,),(2),求线性表的长度:,ListLength,(L),(3),求线性表中某个数据元素值:,GetElem(L,i,&x,),(4),按元素值查找:,LocateElem(L,x,),(5),插入操作:,InsertList(&L,i,x,),(6),删除操作:,DeleteList(&L,i,&x,),说明:,(1),某数据结构上的基本运算,不是它的全部运算,而是一些常用的基本的运算,而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。,(2),在上面各操作中定义的线性表仅仅是一个抽象在逻辑结构层次的线性表,尚未涉及到它的存储结构,因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法。,10/4/2024,6,程序设计基础(C语言)wh,11.2.3,线性表的顺序存储,从结构上考虑,通常线性表的存储类型可以描述如下:,typedef,struct,elemtype,dataMAXSIZE,;,int,length;,SeqList,;,定义一个顺序表:,SeqList,L;,有时定义一个指向,SeqList,类型的指针更为方便:,SeqList,*L;,L,是一个指针变量,指向,SeqList,类型的数据,线性表的存储空间通过如下语句获得:,L=(,SeqList,*),malloc(sizeof(SeqList,);,10/4/2024,7,程序设计基础(C语言)wh,11.2.4,顺序表上基本运算的实现,【,算法,11.1】,顺序表的初始化,SeqList,*,Init_SeqList,( ),SeqList,*L;,L=(,SeqList,*),malloc(sizeof(SeqList,);,L-length=0;,return L;,10/4/2024,8,程序设计基础(C语言)wh,【,算法,11.2】,插入,int,Insert_SeqList(SeqList,*,L,int,I,elemtype,x),int,j ;,if(i,L-length+1) return(0) ; /*,检查插入位置的正确性*,/,for(j,=L-,length;j,=,i;j,-),L-,dataj,=L-dataj-1 ; /*,向后移动*,/,L-,datai,=x ;/*,新元素插入*,/,L-length+ ; /*,顺序表长度增加,1*/,return (1) ; /*,插入成功,返回*,/,10/4/2024,9,程序设计基础(C语言)wh,【,算法,11.3】,删除,int,Delete_SeqList(SeqList,*,L,int,i),int,j;,if(i,L-length)/*,检查空表及删除位置的合法性*,/,return(0);,for(j,=,i;j,length-1;j+),L-dataj-1=L-,dataj,;/*,向前移动*,/,L-length-;/*,顺序表长度减,1*/,return(1);,10/4/2024,10,程序设计基础(C语言)wh,【,算法,11.4】,按值查找,int,Location_SeqList(SeqList,*L,elemtype,x),int,i=0;,while(i,length & L-,datai,!= x),i+;,if (i=L-length),return 0;,else,return i+1; /*,返回该元素的位序*,/,10/4/2024,11,程序设计基础(C语言)wh,11.3,堆栈,11.3.1,抽象栈的定义及基本操作,堆栈(也称为栈,,stack,)是一个线性表,其插入(也称为添加)和删除操作都在表的同一端进行。其中允许插入和删除的一端称为栈顶(,top,),另一端称为栈底(,bottom,)。,抽象堆栈类型的操作:,构造空栈:,InitStack(&S,),。,判断栈是否为空:,StackEmpty(S,),。,判断栈是否为满:,StackFull(S,),。,出栈:,Pop(&S, &x),。,取栈顶元素:,GetTop(S, &x),。,10/4/2024,12,程序设计基础(C语言)wh,11.3.2,抽象栈的定义,堆栈是一个受限的线性表,可以参考线性表描述,用顺序的方式存储。,基于顺序表,栈类型和栈元素类型的定义:,typedef,struct,elemtype,dataMAXSIZE,;,int,top;,SeqStack,;,10/4/2024,13,程序设计基础(C语言)wh,11.3.3,顺序栈的基本运算的实现,【,算法,11.5】,栈的初始化,SeqStack,*,Init_SeqStack,( ),SeqStack,*S;,S=(,SeqStack,*),malloc(sizeof(SeqStack,);,S-top=-1;,return S;,10/4/2024,14,程序设计基础(C语言)wh,【,算法,11.6】,判断栈是否为空,int,Stack_Empty(SeqStack,S),if (s-top=0),return FALSE;,else,return TRUE;,10/4/2024,15,程序设计基础(C语言)wh,【,算法,11.7】,进栈,int,Push(SeqStack,*,S,elemtype,x),if (s-top=MAXSIZE-1) return 0; /*,栈满的情况,即栈上溢出*,/,s-top+;,s-,datas,-top,x;,return 1;,10/4/2024,16,程序设计基础(C语言)wh,【,算法,11.8】,出栈,int,Pop(SeqStack,*S,elemtype,&x),if (s-top=-1) return 0;/*,栈空的情况,即栈下溢出*,/,x,s-,datas,-top;,s-top-;,return 1;,10/4/2024,17,程序设计基础(C语言)wh,【,算法,11.9】,取栈顶,int,GetTop(SeqStack,S,elemtype,&x),if (s-top=-1) return 0;/*,栈空的情况,即栈下溢出*,/,x,s-,datas,-top;,return 1;,10/4/2024,18,程序设计基础(C语言)wh,11.4,队列,11.4.1,队列的定义,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端叫队尾(,rear,),允许删除的一端则称为队头(,front,)。,10/4/2024,19,程序设计基础(C语言)wh,11.4.2,队列的存储结构及其相关算法,假设队列的元素个数最大不超过正整数,MAXSIZE,,所有的元素都具有同一数据类型,即,elemtype,,则顺序队列类型,SqQueue,定义如下:,typedef,struct,elemtype,dataMAXSIZE,;,int,front,rear,;,SqQueue,;,10/4/2024,20,程序设计基础(C语言)wh,为了克服“假溢出” 造成的空间浪费,设想将数组的首尾相连,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。循环队列首尾相连,当队首指针,sq.front,=MAXZISE-1,后,再前进一个位置就自动到,0,。,队满条件为:,(sq.rear+1)%MAXSIZE=,sq.front,队空条件为:,sq.rear,=,sq.front,10/4/2024,21,程序设计基础(C语言)wh,【,算法,11.10】,循环队列初始化,void,InitQueue(SqQueue,*q),q=(,SqQueue,*),malloc(sizeof(SqQueue,);,q-front=q-rear=0;,【,算法,11.11】,入队列,/*,如果队满返回,0,,否则,x,入队并返回,1*/,int,InQueue(SqQueue,*,q,elemtype,x),if (q-rear+1)%MAXSIZE=q-front) return 0; /*,队满*,/,q-rear=(q-rear+1)%MAXSIZE;,q-,dataq,-rear=x;,return 1;,10/4/2024,22,程序设计基础(C语言)wh,【,算法,11.12】,出队列,/*,如果队空则给出出错信息;否则删除队头元素*,/,void,OutQueue(SqQueue,*,q,elemtype,&x),if(q,-front=q-rear) return 0;/*,队空*,/,q-front=(q-front+1)%maxsize;,x=q-,dataq,-front;,return 1;,10/4/2024,23,程序设计基础(C语言)wh,【,算法,11.13】,判队空,/*,判别队列是否为空,若为空返回,1,,否则返回,0*/,int,empty(SqQueue,q),if(q,-rear=q-front),return 1;,else,return 0;,10/4/2024,24,程序设计基础(C语言)wh,小 结,数据抽象把系统中需要处理的数据和这些数据上的操作结合在一起,根据其功能、性质、作用等因素抽象成不同的抽象数据类型。,抽象数据类型是用户进行软件设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑上的一组操作,而不考虑计算机的具体存储结构和操作的具体实现算法。,10/4/2024,25,程序设计基础(C语言)wh,THE END,!,10/4/2024,26,程序设计基础(C语言)wh,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 管理文书 > 施工组织


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!