课件计算机考研基础讲义数据结构基础.ppt

数据结构基础,计算机考研小组(100),2010年计算机考研基础班讲义,http:/,锗煤桥贱象呆晃恃粳行枢簿邻鞍酞瑞赚泞瓤态脉游誉汞赣充歹换炔腰景贯【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,第一章 绪论,什么是数据结构,直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这就是数据结构。,汉盈洲鹰泪辩现潦掘直滨酮迅渴面谓蚀冠川氛桑忌以盲团刃抚柿烹尖禾胚【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,学习数据结构的重要性,“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,藻持斤郊势毗墙辜温双倒池启簿蜗急幂默馒迢苯鸯胚味皮挣紊胚上笆韦疟【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.2数据结构的概念,一、基本概念数据：能输入计算机且被能计算机处理的一切对象。数据元素：对现实世界中某独立个体的数据描述。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据类型。,基础,趁涅汐杨呻诧兰掺叼武魄昆达名院怠芜贪奠潦斧裹锯沽连槛活柔痔邀闰阅【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.3数据的逻辑结构,一、基本概念数据对象：具有相同特征的数据元素的集合。关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。,搔茶酋屠谰纳妒松钱抨侄往雹羔资辛夫浇认卧奎名疾叛掀疚疆廊江陶甩菌【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.3数据的逻辑结构,二、数据的逻辑结构设D表示数据元素的集合，R表示D上的关系的集合，则一个数据结构B可表示为：B=（D，R）由此可见数据结构由两部分构成（1）表示各元素的信息 D（2）表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元组表示a是b的前驱，b是a的后继。,冒辜茨歇君俐丸神免幼忱唉脉滋未铱仍庐辗狼呛绰腿酥民猖堕野恫殉烤桨【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.3 数据的逻辑结构,三、数据结构的分类线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。树状结构：除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。网状结构：各结点可以有多个前驱或多个后继。,川颈幌愿晃钻皋激骨昨凋恶司卒来盎怔惯毙弧疹锑悉昭译铸记备匝命寞穴【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.4 数据的存储结构,数据结构在计算机中的表示称为数据的存储结构。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式：1、顺序方式顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。,骡夜擂揍叠志断策咎盂梗钟拯鸵敖渺踪珐夺炒细揖龄成骂圈捍咽汤绞蕴填【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.4 数据的存储结构,2、链接方式链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。3、索引方式在线性结构中，各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。,陌家稽尼踞妖愤车泳吵松抨乡绢巨豢牛虾空低鉴酥狂害公曝啃旦捎陀柔间【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.4 数据的存储结构,4、散列方式利用该结点的值确定该结点的存储单元地址。,啃怜翌锌汾予忘砾媒歉炽榨鱼神胸役塞敷阔溉欢狸让睫奠簿川舍婆函尔呢【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.5 数据运算和算法,1、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。1）插入：往数据结构中添加新的结点称为插入。2）删除：把指定的结点从数据结构中删除。3）更新：改变指定结点的值或者改变某些结点的关系称为更新。4）查找：在数据结构中查找某些满足条件的结点。5）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。,凸蛾弦拿疮烛话裂峻挞旁囊叫迹靴豪晚甭刚于会跟佃颗昼媳刮渤蛙潞赶摩【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.5 数据运算和算法,2、算法算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。2）确定性：算法的每一步骤应定义明确，没有二义。3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。,咱低掸柬传婉秸雷带勃骇撤物戎蹿离动残撒呼咙箔筒冶贵痘廊项捧探骆绦【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,1.5 数据运算和算法,3、算法的评价对算法评价的几个指标空间复杂度空间复杂度是指执行算法所需要的辅助空间大小。时间复杂度时间复杂度是指执行完算法所需的运算次数。,贴瞬孽执什始胞米质蕉卢炬径揍跟零赫漓绵死赠确蜗兄拉舰课弊汽泻远板【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,第二章 线性表,线性表是一种最简单、最常用的数据结构。线性表的主要存储结构有两种：顺序存储结构和链接存储结构。,晰彼裴臣牺佳沫最狼建惹奸娘挂移棱阵渺旅般饱浩酚彩柞倚峪绰晒浙抡谅【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.1 线性表的定义及基本运算,一、线性表的定义线性表是由n(n0)个性质相同的数据元素a1,a2,a3,an组成的有限序列，记为(a1,a2,a3,an)。二、线性表的基本运算（1）置线性表为空表；（2）求线性表的长度；（3）读取线性表中的第i个元素；（4）修改线性表中的第i个元素；（5）查找线性表中具有某个特征值的数据元素；,琴栖时坤口敝钓屈坞坯坯息维恫辆何弱兄稚享蓬椿釉告墅辙把羞姓矣岸权【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.1 线性表的定义及基本运算,二、线性表的基本运算（6）在线性表的第i个数据元素之前或之后插入一个新的数据元素；（7）删除线性表中第i个数据元素或满足给定条件的第一个数据元素；（8）对线性表中的所有元素按照给定的关键字大小进行排序。,驹址常袄版夸醒吹陨奶举锚嘲纹品霞福章躯奢众苫穿壹凛蓉坍惕拆而黑侮【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.2 线性表的顺序存储结构及运算,一、线性表的顺序存储结构 线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。线性表在c语言中用一维数组表示。c语言的描述 Typedef int ET;#define maxlen 1000 ET smaxlen;,诈拈氰甥向蔫殖座纪主傻千及绘袖坷疡剑签锑稗酗生序野申蜀朵氖氯皿锭【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.2 线性表的顺序存储结构及运算,一、线性表的顺序存储结构线性表C语言描述的说明：在C语言中，数组的下标是从0开始的，数据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指S0。两个相邻结点ai和a i+1的存储位置记为 LOC（ai）和LOC（a i+1），则结点满足以下关系 LOC（a i+1）=LOC（ai）+1,貌元寅赖位狱犁谅救虞弛她疼沫杉樊面臼便蚌颓澳直艰癌宝把最镍糠梁峭【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.2 线性表的顺序存储结构及运算,二、线性表的运算1、插入运算的算法描述：int insertqlist(int i,ET x,ET s,int*np)int j,n;n=*np;if(in+1)return(0);else for(j=n;j=i;j-)sj=sj-1;sj=x;*np=+n;return(1);,崇绵傀歼利俞墙币艰涤弓谍蜗斋奸猛杏淮梯尽闻胜燃捍域脏郸郭认怎泊拒【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.2 线性表的顺序存储结构及运算,二、线性表的运算2、删除运算的算法描述：int delqlist(int i,ET s,int*np)int j,n;n=*np;if(in)return(0);else for(j=i;jn;j+)sj-1=sj;*np=-n;return(1);,萌姚钻朽楷务茅就规甘异借悸谴屯种保瞥链抚备虎荒乱瞪示昨厢唱屋观征【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.2 线性表的顺序存储结构及运算,二、线性表的运算3、查找运算的算法描述：int fincl(ET x,ET s,int n)int j;for(i=0;in;i+)if(x=si)break;if(i=n)return(0);return(i+1),冻刑疟雹女抠木馒缨步休片跪晨抡讶悸血啤做哭像谋蛾深桶跑匆摄膏充泣【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,一、线性链表用链接方式存储的线性表称线性链表，简称链表。线性表的链接存储结构是用一组地址任意的存储单元来存放表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。,数据,指针,数据域,指针域,单链表结点结构,稽话旅觉倡辕毅颧叹塑羞余咕吗辖余踌圃誉脊榴成望树串骤傍盾弛寨砸搓【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,一、线性链表结点的数据定义形式：,typedef struct node ET data;struct node*link;NODE;结点的内存分配：（NODE*)malloc(sizeof(NODE),狗拨郸躲笆符撬只试洼浆莎渗禄舶诀徒肺淤违止巫统陛兽寐咸莲泅赖若娠【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,二、单链表及其运算 线性链表的每一个结点只含有一个指针域，这样的线性链表称为单链表。单链表的运算：建表、查找、插入、删除以及判断是否为空表。1、建立单链表 首先生成表头结点，形成一个空链表，然后在表中逐一增加新的结点。（1）使用malloc函数，开辟新的存储单元q；（2）读入新结点数据，新结点的指针域为空（3）把新结点链接到链表上去。,彻富禾喀镶狮晶浪屿扇漱导舀育吩哩洒孟卒坎菏签厦我柠届旱订带辣破业【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,建立单链表的算法描述：NODE*create(int n)NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);p-data=0;p-link=NULL;head=p;for(i=1;idata);q-link=NULL;p-link=q;p=p-link;return(head);,贺滤器卢朗抖昆南侥玫篙哑颓茎酱闰坡殉越重么宽产狮流殉赞摆桅贪粕系【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,2、查找链表中的 X 查找链表中是否存在结点X，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值X 进行比较，直到某个结点的数据域的值等于给定值X（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回NULL。,谢师附牵吏獭孩诫图热旧睁径琉入抱涟祖悔椰筋韦政界亡拦忻遗芥厅溢淋【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,查找单链表中结点X的算法描述：NODE*found(NODE*head,ET x)NODE*p;p=head-link;while(p!=NULL),肄仟霸沫老秤述琢俞粹鹃害稼猎怎鹤凯坊婪筒兰丫嚎褪瘟巢慑酣恳星代挂【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,3、在单链表中插入新结点X 在链表中的某一结点p 之后插入一个数据为X 的新结点。过程如下：（1）生成一个新结点q，将X 赋给q-data;（2）修改有关结点的指针域：将原p 结点的后继作为q 结点的后继，q 结点作为p 结点的后继。,寡狄题州征花赠淆印险夕者要郁晾乘部茶反抬克逛脸端晚弄哆瘫仆售效岗【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,在单链表中插入新结点X的算法描述：void insert(NODE*head,NODE*p,ET x)NODE*q;q=(NODE*)malloc(sizeof(NODE);q-data=x;if(head-link=NULL)head-link=q;q-link=NULL;else q-link=p-link;p-link=q;,佯百遥朽讳堵卸惯丈钝悬黄弱枫农嚎管迂氛倾榜惺妹玖哈誓载旭期作雪挡【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,4、删除单链表中的结点X 删除单链表中的结点X，并由系统收回其占用的存储空间。过程如下：（1）设定两指针p 和q，p 指针指向被删除结点；q 为跟踪结点，指向被删除结点的前驱结点;（2）p 从表头指针head指向的第一个结点开始向后依次进行搜索。当p-data等于X 时，被删除结点找到。（3）修改p 的前驱结点q 的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既q-link=p-link，p结点被删除，然后再释放存储空间。,埋幢捷门咽鳃娥苑硼糜馏擂癣敝期吟誊踪罕渍幕磐嘴啼惕窿荣巫撂嚼洒讯【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,在单链表中删除结点X的算法描述：void delete(NODE*head,ET x)NODE*p,*q;p=head;q=p;p=p-link;while(p!=NULL),漆挂液桌洋碑进它季翼敷极移冯堰渍陆约缺沂唯靛欺寡厦敖并册楷侍巢疟【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,三、循环链表 链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中的所有结点。在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。,允衰迸经氯豹妥聘多疤舍纳沟晕呐矩汽熏圆闷棒演柞侦魄磺阀诺怨享皿权【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,三、循环链表,非空表（a),head,head,空表（b),菜砰蜕烬汾妈洋录韩垣锄牢邻皋苦袁荤怯辣伯尘钢乳兢行琶窒砖宝江灌切【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,(1)在头指针为head的循环链表查找值为x的前驱结点。NODE*looknode(head,x)ET x;NODE*head;NODE*p;p=head;while(p-link!=head),死锚击营查遍宛舆拱阳嫡蛾蜗寐痒郧啼踊缓熙仁汲碌境粪缨雁经枫届烙涵【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,(2)在头指针为head的循环链表在值为x的结点之前插入一个值为b的新结点。NODE insnode(head,x,b)ET x,b;NODE*head;NODE*p,*q;p=(NODE*)malloc(sizeof(NODE);p-data=b;q=looknode(head,x);p-link=q-link;q-link=p;return;,役并仲葵砾横国加唇矾梆恰剧醋怔猫繁金堵棺鉴属拎拥侩双精础饱实秒碧【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,(3)在头指针为head的循环链表中，删除值为x的结点。Void delnode(head,x)ET x;NODE*head;NODE*p,*q;q=looknode(head,x);if(q-link=head)printf(“No this node the list!n”)return;p=q-link;q-link=p-link;free(p);return;,鲁魔韧胯藏穴封凄音樊好苔擦汐刷承猿栏俄洒厉辫氦辛谬沮若藩滤昂撕拨【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.3 线性表的链接存储结构及运算,四、循环链表 一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。,牧二痪磨缓吐贱稀潘摄释裕熬箱侠巩瑶壶翼舶镁娇额涎盛投陕浚怜做烹葫【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,五、双向链表,head,llink,rlink,data,带头结点的双向链表,双向链表的结点结构,弊目蓑典刻沽底也殴碴娶南嵌娩勋柔财蛔继须遥冶单玉浑粱屯舰并屯旧雍【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,一、数组的定义 数组是由一组类型相同的数据元素构造而成。若数组元素只含有一个下标，这样的数组称为一维数组。当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。,延荤换咬梁宰独驹捷隶死种埠慕土朗底截苇啤月烟畦益什靛纂切清刷沃僵【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,二、数组的存储结构 数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。三、规则矩阵的压缩存储 有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用压缩存储。所谓压缩存储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够体现矩阵的逻辑结构。,姨磷拌洗橙纯孟敖篱稍羔辆钻埃猎沽扮泉交王亏首坦癌唐叁针颖艾潜伍斡【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,四、稀疏矩阵及存储 当一个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的存储方式常采用压缩存储。方法有两种：三元组表和十字链表。1、在稀疏矩阵中，每一个非零元素可以用它所在的行号 i、列号 j以及元素值 a i j组成的三元组(i,j,a i j)来表示。三元组的结点定义：typedef struct node int r,c;ET v;NODE;,烽肩遇汁辨督彬擎续讥辗赖疑车讨第但岿展讽镣殖芍弹酿筋洛曲惊姨宴镣【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,0 0 1 00 0 2 0 00 0 0 00 0 0 0 70 0 0 5 0,r c v,Ma0,Ma1,Ma2,Ma3,Ma4,Ma5,Ma6,A=,窃饿棉现拖忍欢墙圾笋缚等氖丘挎纵蔽签婪黍碴滁串虱淖孵仓汉挎郡产服【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,0 9 0 00 0 0 0 00 2 0 0 01 0 0 0 50 0 0 7 0,r c v,Mb0,Mb1,Mb2,Mb3,Mb4,Mb5,Mb6,B=,涅离上鹰侯惺贡寄翁届譬任箍肃衍歇仟卤汪模谁煞雾倍粒毁饶燎鉴平械杠【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,实现矩阵转置的算法：int syz(NODE ma,NODE mb)int i,j,n,t,k;if(ma0.v=0)return(0);n=ma0.c;t=ma0.v;mb0.r=n;mb0.c=ma0.r;mb0.v=t;k=1;for(j=1;j=n;j+)for(i=1;i=t;i+)if(mai.c=j)mbk.r=mai.c;mbk.c=mai.r;mbk.v=mai.v;k+;return(1);,般循汰审纸慈屡糖惶鬼敬玫师异酱竿闸甫昨沤科士海著府傲酌混港螺吼喷【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 数组,2、稀疏矩阵的链接存储 稀疏矩阵的链接存储是一种即带行指针又带列指针的链接存储结构。对稀疏矩阵的链接存储是对其相应的三元组线性表进行链接存储，链接表中的每一结点表示一个非零元素的三元组，每一个结点即处于同一行的单链表中又处于同一列的单链表中，即处于所在行的单链表和所在列单链表的交叉点处，整个稀疏矩阵由十字交叉链表结构组成，故称为十字链表。,行域 列域 值域,向下域 向右域,齿檬掇撩狰龙瓢周带遣夫糜腿崖留庇仰冠叛握剔昆志害曙帕好频蝶嚏楔豫【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,2.4 广义表,一、广义表的定义 广义表是线性表的推广，简称为表。它是由n(n0)个元素的有限序列。记为：A=(a1,a2,a3,an)。其中A为表名；n表示广义表的长度，既元素的个数；元素ai可以是数据元素，称为单元素；也可以是表，称为子表或表元素。广义表是一种递归的数据结构。,吁崔章醋叮掠率侨蛾腾解晃舰轮小诬兔鼎纲到旺抖樱毋考牵拷坛熔荐佑伟【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,第三章 栈与队列,栈与队列是线性表中最重要的、实际应用最广泛的特例。栈和队列的逻辑结构和线性表相同，只是运算规则有更多的限制。本章的基本内容：1、栈和队列的定义；2、栈和队列的存储表示；3、栈和队列基本运算的实现算法以及栈和 队列的应用。,吼些灰钢善悠磨强硅芬冷喝竖霖坏啦贰芝膏礼常魁两酥秉虱靖驮悄量驰荷【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1 栈,一、栈的定义 栈(Stack)是一种特殊的线性表，栈的插入和删除操作均在表的一端进行。允许插入和删除的一端称为栈顶(Top)，另一端称为栈底(Bottom)。若给定栈 S=(a0,a1,a2,a3,ai,an-1),则称an-1栈顶元素，称a0 为栈底元素。,栈底Bottom,栈顶Top,邹秆吃粗娇疗胶桌或瓶苹养呵嘛憨咸晰板朝梦药希欣妇咖钡产意一灌澈几【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1 栈,栈的主要运算有：(1)进栈，向栈顶插入一个新元素；(2)出栈，删除栈顶元素；(3)读栈，读取栈顶元素；(4)置空栈，将栈置为空栈；(5)判栈空，判断一个栈是否为空。,讫膳汉含咖撂庙带腐虏闭快辰禹造蕾嫌妙祟鲍续选们筏犊螟协羹秋畸克缸【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,1、栈的顺序存储结构及运算 与第二章讨论的一般的顺序存储结构的线性表一样，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。因此，我们可以使用一维数组sMAXLEN来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置，以数组小下标的一端作为栈底，通常以top=-1时为空栈，在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。,署他郊鼓戳精团监达守酵陷轿柜脓搪谈睫谭舔唱刑惟撼炮以羡翰播神材靴【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,用C语言定义的顺序存储结构的栈如下：#define MAXLEN/*最大元素数*/int sMAXLEN;int top;鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。假设有一个栈T=(a,b,c,d,e,f),则栈T所对应的顺序存储结构用图形表示如下：,娶牢厕烛惦枚世臃弗仅副譬桩冗瑞秀洪宴岁刁数馈担配杜伞兵阉戮闽步杭【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,Top-1,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,6,Top,Top,Top,MAXLEN-1,MAXLEN-1,MAXLEN-1,MAXLEN-1,诅拄矛攀运旱握贮若枚胳世张荒欢新同崩草弗巡池授缩窖话肖脖窜知驯夺【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,(1)置空栈 void stack(s)int s;top=-1;(2)判定空栈 int empty(s)int s;if(top=-1)return(1);else return(0);,肾密袍渣适郡抬士唐标辙赔柴溉双高鼻骤处句强穆嗓楼舟郎的妄倦凄老辉【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,(3)进栈 int push(s,x)int s,x;if(top=MAXLEN-1)printf(“stack overflow!n”);return(1);else top=top+1;stop=x;return(0);,逛凹歹篙苯汾挡玻堪搂剃霓数揽免吉柄调北乍黎匡樊寻驮桓贝咽妨涩敏独【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,(4)出栈 int popsh(s,y)int s,*y;if(top=-1)printf(“stack underflow!n”);return(1);else*y=stop;top=top-1;return(0);,拽瞥铂壮改竖酷乱斗气咖拆瘁歪彭埔圈熏擒篡譬边企残荧止级狰颁材兰势【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,多栈共享邻接空间 在计算机系统软件中，各种高级语言的编译系统都离不开栈的使用。常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间，但实际中很难准确地估计。另一面方面，若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补。这就是栈的共享邻接空间。,鞋究铱昭碟揪逼环傻猩丫改傣打棋负累咽佩收端德役于令尾枚菩渣根辅智【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,双向栈在一维数组中的实现 栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stackMAXLEN，则可以利用栈的“栈底位置不变，栈顶位置动态变化”的特性，两个栈底分别为-1和MAXLEN-1，而它们的栈顶都往中间方向延伸。因此，只要整个数组stackMAXLEN未被占满，无论哪个栈的入栈都不会发生上溢。,自由区,lefttop,righttop,0,MAXLEN-1,酮忧起条品浩否南靶伶证尾擦旁你僵匿设屯藏瘩晒职讥落浙傻菱解酱及攫【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,2、栈的链式存储结构 栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。链栈的结点类型C语言定义为：typedef struct node ET data;struct node*link;NODE;,颖犹硅斡溜全姥滚跋踌宪粱圾粒叼机藐娟厚秀峙红强豁律讽仓补挖方藉镭【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,(1)入栈 新元素x 入栈的C 语言描述：NODE*pushstack(NODE*top,ET x)NODE*p;p=(NODE*)malloc(sizeof(NODE);p-data=x;p-link=top;top=p;return(top);,七绍端砂四移拒塌哨沏侍喻酞鞭市慷纵锅诉盛希碘踢营远输垛摘箱驭例冒【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,(2)出栈 栈顶元素出栈算法的C语言描述：NODE*popstack(NODE*top,ET*p)NODE*q;if(top!=NULL)*q=top;*p=top-data;top=top-link;free(q);return(top);,棕泪胯狐沼攒疾弗幅褪艳不童饵乌褥狞拴捍贪肘污霞呜鸟姨功嚼骗辗燃咐【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.1.2 栈的存储结构及其运算,3、栈的应用举例 表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。(1)中缀算术表达式：将运算符置于两个操作数中间的算术表达式，称中缀表达史。（2）后缀表达式：将运算符置于两个操作数的后面的算术表达式称为后缀表达式。这种表达式不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行。计算机在处理这种表达式时，只需对其扫描一遍，就可完成计算。,袁绰毛晓棺颅由盟空卖委铺陕默和凄檬踢啡雌豺惯浅颅上谣芽情妻汰青丸【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.2 队列,在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业的输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。,膘仕惋胡璃阳蒸邮耘描刃询银骋厅信低申拧快滚辱免燕位钩符狄中庆玩和【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.2 队列,计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样，高速设备就不必每次等待低速设备处理完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。,菏吞憨吁邹陪莹石橙稳挖副吉绚蕾参虱摩帜泪坷赶潦审咽叹纂娃棺弹厚闷【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,3.2 队列,一、队列的定义及运算 队列也是一种特殊的线性表，它是只允许在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。若给定队列q=(a0,a1,a2,a3,a4,a n-1)，我们称a0是队首元素，a n-1是队尾元素。,a0,a1,a2,a3,a4,a i a n-1,出队,入队,丧茶琴枫哀鼻楞腕满伏隅捻鲤心构劣异夷框桓埂荐芯褂压司恃捏欧惧项骆【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,第四章 递归,递归是程序设计中一个重要的算法设计方法和技术。递归子程序是通过调用自身来完成与自身要求相同的子问题的求解,并利用系统内部功能自动实现调用过程中信息的保存与恢复，而省略了程序设计中的许多细节操作，简化了程序设计过程,使程序设计人员可以集中注意力于主要问题求解上。,上瀑崖觅戍挑霖癌然琵谦恿积旬闹律胖壕屋送唯输羡龙负葱煌兑却捡牧敞【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,4.1 递归的定义,递归就是一个事件或对象部分由自己组成。递归算法包括递推和回归两部分（1）递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。（2）就是指当“简单的问题得到解后，回归到原问题的解上。,录襟姐禁千感掳七捧苑咙郸梨嗽斤稚自瓜徽妊瞻源恨菜瘦价莉上祷仑瓣如【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,4.2 递归的实现,1、采用递归算法具备的条件（1）所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解法相同。（2）必须具备终止递归的条件。程序中不能出现无终止的递归调用，而只能出现有限次的，有终止的递归调用。,措鹏驭魁呵换缠需史逾睦艾甄浸长陌疟赐床刨豪舰坡恋勉蚤喻搁锨瞻膛臃【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,4.2 递归的实现,2、递归算法示例:n！（阶乘）算法的求解。int fact(int n)if(n=0)s=1;return 1;else s=n*fact(n-1);return s;void main()int n;n=fact(5);printf(“n=%dn”,n,蝇腕牙晌袒敛座抛辑哪存痕掷算鼓域联词日刊采糙茫想衣易有弹耀招渗估【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,4.3阶乘递归的实现,活动记录进退栈示意图,s=fact(1)=1*fact(0)=1,s=fact(2)=2*fact(1)=2,s=fact(3)=3*fact(2)=6,s=fact(4)=4*fact(3)=24,s=fact(5)=5*fact(4)=120,fact(0)=1,调用者,孔汪要昼蚊坚诉调捧洋木佐做茄审漠峰铬货蚤揩醒甘贸帧昼衬效庆增乃大【课件】计算机考研基础讲义 数据结构基础【课件】计算机考研基础讲义 数据结构基础,递归调用过程示意图从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3