传智播客C和C++与数据结构基础讲义

1、传智播客C和C+丐数据结构基础讲义传智扫地僧1、数据结构概念1.1 数据结构相关概念1.1.1 疑惑1、我学完了C语言，可是现在感觉还是写不出代码。2、为什么会有各种各样的程序存在？3、程序的本质是什么？程序是为了具体问题而存在的程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏？1.1.2 数据结构起源计算机从解决数值计算问题到解决生活中的问题现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系不是研究复杂的算法1.1.3 数据结构中的

2、基本概念数据-程序的操作对象，用于描述客观事物(inta,intb,)数据的特点：可以输入到计算机可以被计算机程序处理int， float ， char数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：数据元素：组成数据的基本单位数据项：一个数据元素由若干数据项组成数据对象-性质相同的数据元素的集合(比如：数组，链表)友情提示，来自结构体课堂代码/声明一个结构体类型struct_MyTeacher/一种数据类型charname32;chartile32;intage;charaddr128;；intmain21()struct_MyTeachert1;/数据元素struct_M

3、yTeachertArray30;/数据对象memset(&t1,0,sizeof(tl);strcpy(,"name");数据项strcpy(t1.addr,"addr");/数据项strcpy(t1.tile,"addr");/数据项t1.age=1;数据元素之间不是独立的，存在特定的关系，这些关系即结构数据结构指数据对象中数据元素之间的关系如：数组中各个元素之间存在固定的线性关系编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。基本概念总结：78 / 731.1.4数据的逻辑

4、结构天其它关指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：1.1.5 数据的物理结构答：物理结构亦称.是数据的逻枳结构在计算机存储器内的表示（或映像）口它Sni"TbJnl3.1yT*"wo存储结构可分为大类：廉序.健武去人散对电常用的存储结构为：顺厅存储结构借助元麦在存储器中的和对位直来表示I数据元-麓间的更辑关系O链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系数据的逻精给构与存储结构密切相关算法设计逻辑造物茸法实现1.1.6 数据的运算：什金JL-据操作或处理昔：在数据的逗辑结构上定义的操作

5、，它最常用的数据运算有5种：括入、删除修改.查找,林方1.2、 算法1.2.1 算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。1.2.2 算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法=程序至据z构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成1.2.3 算法特性输入算法具有0个或多个输入输出算法至少有1个或多个输出有穷性算法在有限的步骤之后会自动结束而不会无限循环确定性算法中的每一

6、步都有确定的含义，不会出现二义性可行性算法的每一步都是可行的1.2.4 算法效率的度量1、事后统计法比较不同算法对同一组输入数据的运行处理时间缺陷为了获得不同算法的运行时间必须编写相应程序运行时间严重依赖硬件以及运行时的环境因素算法的测试数据的选取相当困难事后统计法虽然直观，但是实施困难且缺陷多算法效率的度量事前分析估算依据统计的方法对算法效率进行估算影响算法效率的主要因素算法采用的策略和方法问题的输入规模编译器所产生的代码计算机执行速度算法最终编译成具体的计算机指令每一个指令，在具体的计算机上运行速度固定通过具体的n的步骤，就可以推导出算法的复杂度longsum1(intn)longret=

7、0;int*array=(int*)malloc(n*sizeof(int);inti=0;for(i=0;i<n;i+)arrayi=i+1;for(i=0;i<n;i+)ret+=arrayi;free(array);returnret;longsum2(intn)longret=0;inti=0;for(i=1;i<=n;i+)ret+=i;returnret;longsum3(intn)longret=0;if(n>0)ret=(1+n)*n/2;returnret;intmain()printf("%dn",sum1(100);printf

8、("%dn",sum2(100);printf("%dn",sum3(100);return0;intfunc(inta口，intlen)inti=0;intj=0;ints=0;for(i=0;i<len;i+)nfor(j=0;j<len;j+)ns+=i*j;/n*nreturns;/n*n2、大O表不法算法效率严重依赖于操作(Operation)数量在判断时首先关注操作数量的最高次项操作数量的估算可以作为时间复杂度的估算0(5)=0(1)0(2n+1)=0(2n)=0(n)0(n2+n+1)=0(n2)O(3n3+1)=O(3n3)=

9、0(n3)常见时间复杂度执行次贴函时1»1r堂正木水12110(1)1京做阶2n-+-310(/3)喊初阶3nJ+2n+10(/)千方阶51njn+20O(1ogo)1时救阶2n+3rde19O(rrio-gA)nlo-gn阶601-+in1-*'3n+4j'0方暗2"i0(2")居林阶关系0(1)<O(1og/I)<O(w)<O(nogn)<O(n2)<0(/)<0(21)<0(讯)<0(nn)3、算法的空间复杂度算法的空间复杂度通过计算算法的存储空间实现S(n)=O(f(n)其中，n为问题规模，f

10、(n)为在问题规模为n时所占用存储空间的函数大O表示法同样适用于算法的空间复杂度当算法执行时所需要的空间是常数时，空间复杂度为0(1)空间与时间的策略多数情况下，算法执行时所用的时间更令人关注如果有必要，可以通过增加空间复杂度来降低时间复杂度同理，也可以通过增加时间复杂度来降低空间复杂度练习1:分析sumlsum2sum3函数的空间复杂度O(4n+12)0(8)=0(1)0(4)=0(1)总结：实现算法时，需要分析具体问题，对执行时间和空间的要求。练习2:时间换空间/*问题：在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。设计一个算法，找出出现次数最多的数字。

11、*/方法1：排序，然后找出出现次数最多的数字方法2:voidsearch(inta口，intlen)intsp1000=0;inti=0;intmax=0;for(i=0;i<len;i+)intindex=ai-1;spindex+;for(i=0;i<1000;i+)if(max<spi)max=spi;for(i=0;i<1000;i+)if(max=spi)printf("%dn",i+1);intmain()intarray口=1,1,3,4,5,6,6,6,2,3;search(array,sizeof(array)/sizeof(*ar

12、ray);return0;把每个数字出现的次数的中间结果，缓存下来；在缓存的结果中求最大值。UiX义ONJ,UJ.JL数字n出现的次数放在新开辟的内存空间的式51的位置把每一个数字的中间结果给堞存下来.2、线性表2.1 线性表基本概念2.1.1 线性表定义线性表(List)是零个或多个数据元素的集合线性表中的数据元素之间是有顺序的线性表中的数据元素个数是有限的线性表中的数据元素的类型必须相同先来一个大家最感兴趣的，一年里的星座列表，是不是线性表呢？如图3-2-2所白金双巨狮处天射摩水双羊牛,子蟹子女秤手,羯瓶,鱼2.1.2 数学定义线性表是具有相同类型的n(>0)个数据元素的有限序列(a

13、1,a2,，an)ai是表项，n是表长度。2.1.3 性质a0为线性表的第一个元素，只有一个后继an为线性表的最后一个元素，只有一个前驱除a0和an外的其它元素ai,既有前驱，又有后继线性表能够逐项访问和顺序存取2.1.4 练习下面的关系中可以用线性表描述的是A.班级中同学的友谊关系N:NB.公司中的上下级关系1:NC冬天图书馆排队占座关系D.花名册上名字之间的关系1:12.2.5线性表的操作创建线性表销毁线性表清空线性表将元素插入线性表将元素从线性表中删除获取线性表中某个位置的元素获取线性表的长度线性表在程序中表现为一种特殊的数据类型线性表的操作在程序中的表现为一组函数c语言描述=线性表的设

14、计与实现ADT抽象层数据Z勾(C语言版).严蔚敏_吴伟民.扫描版.pdfp44页人生财富库积累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;/创建并且返回一个空的线性表List*List_Create();/销毁一个线性表listvoidList_Destroy(List*list);将一个线性表list中的所有元素清空，线性表回到创建时的初始状态voidList_Clear(List*list);/返回一个线性表list中的所有元素个数intList_Length(List*list);/向

15、一个线性表list的pos位置处插入新元素nodeintList_Insert(List*list,ListNode*node,intpos);/获取一个线性表list的pos位置处的元素ListNode*List_Get(List*list,intpos);/删除一个线性表list的pos位置处的元素返回值为被删除的元素，NULL表示删除失败ListNode*List_Delete(List*list,intpos);#endif注意：intListInsert(List*list,ListNode*node,intpos);(重点：分离思想)2.2线性表的顺序存储结构2.2.1基本概念34

16、1顺序存储定义说这么多的税性表,我们来看看线性及的胸牌枷理结梅的第种顺序存储站构.线性衰的序存佛结构，指的是用一段地址连续的存储单元侬次存储场性表的触据元*口线性衣闰C的顺序存储示意图如下：2.2.2设计与实现插入元素算法判断线性表是否合法判断插入位置是否合法把最后一个元素到插入位置的元素后移一个位置将新元素插入线性表长度加1获取元素操作判断线性表是否合法判断位置是否合法直接通过数组下标的方式获取元素删除元素算法判断线性表是否合法判断删除位置是否合法将元素取出将删除位置后的元素分别向前移动一个位置线性表长度减1链表顺序存储插入算法和删除算法*股垠序存他:语表的答民和短表的实阮无县出商户工司网酒

17、主叵匚立zu口口耳二口口剧索空闾外呼一I-*/d662)"Gm演郊|/1”后移为1鼻=1咏时口；irWE；1)jLU-川工I=aUJ/j73.钵九元聿2.2.3优点和缺点优点：无需为线性表中的逻辑关系增加额外的空间可以快速的获取表中合法位置的元素缺点：插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量2.3线性表的链式存储2.3.1基本概念链式存储定义为了表示每个数据元素与其直接后继元素之间的逻辑关系,的信息外，还需要存储指示其直接后继的信息。每个元素除了存储本身n个结点Qi的存储映像）链结成一个链表，即为线性表（au正，a.）的链式存储结构，因为此链表的每个

18、结点中只包含一个指针域，所以叫做单链表.单橙表正是通过每个结点的指针域将线性表的数据元裁按其逻辑次序链接在一起，如图352所示*表头结点链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息数据结点链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息尾结点链表中的最后一个数据结点，其下一元素指针为空，表示无后继。2.3.2链表技术领域推演修统域悒2.3.2设计与实现链表链式存储_api实现分析在c语言中可以用结构体来定义链表中的指针域链表中的表头结点也可以用结构体实现typedefstruct_tagLinkListHodeLiniLislHode;strud

19、tawLinkListHode(LinkListNode*fieut：站点指针域定义typedefstruct_tag_LinkLiff't(LinkListNodeheader：intlength.TLinkList：义站点定义structValueLinlrListNodeheader;intv,数据元案定义示例插入元素操作currentciirr«nt'>nftTtaiH2J1nndrnbde-current->next；currezlt，-'next=node;nodeint pos)带头结点、位置从0的单链表返回链表中第3个位置处，元素的

20、值LinkListNode*LinkList_Get(LinkList*list,inti=0;TLinkList*tList=(TLinkList*)list;LinkListNode*current=NULL;LinkListNode*ret=NULL;if(list=NULL11Pos<0|pos>=tList->length)returnNULL;current=(LinkListNode*)tList;for(i=0;i<pos;i+)current=current->next;ret=current->next;returnret;返回第三个位置

21、的移动pos次以后，当前指针指向哪里？答案：指向位置2,所以需要返回ret=current->next;备注：循环遍历时，遍历第1次，指向位置0遍历第2次，指向位置1遍历第3次，指向位置2遍历第n次，指向位置n-1;所以如果想返回位置n的元素的值，需要怎么做ret=current->next;此问题是：指向头结点的指针移动n次和第n个元素之间的关系?删除元素current->next=ret->next;重要技术场景图链表链式存储插入专UTTEEitLijudcSiuEit=4UTETnl->r诅工I,2tunent->Mxt-g;b;1将丈指向惟就把址他地

22、址赋始拒针2分精董健表的操作逻楫和辅助指针变量之间的美桑链表链式存储删除2.3.3优点和缺点优点：无需一次性定制链表的容量插入和删除操作无需移动数据元素缺点：数据元素必须保存后继元素的位置信息获取指定数据的元素操作需要顺序访问之前的元素2.4循环链表2.4.1基本概念循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素循环链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素新增功能：游标的定义在循环链表中可以定义一个“当前”历链表中的所有兀素。指针，这个指针通常称为游标，可以通过这个游标来遍天结点尾结直游

23、标glider循环链表新操作将游标重置指向链表中的第一个数据元素CircleListNode*CircleList_Reset(CircleList*list);获取当前游标指向的数据元素CircleListNode*CircleList_Current(CircleList*list);将游标移动指向到链表中的下一个数据元素CircleListNode*CircleList_Next(CircleList*list);直接指定删除链表中的某个数据元素CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node

24、);/根据元素的值删除元素pk根据元素的位置删除元素2.4.2循环链表的应用证明循环链表打印两次。约瑟夫问题求解约瑟夫问题-循环链表典型应用n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m个人,令其出列。然后再从下一个人开始从1顺时针报数，报到第m个人，再令其出列，如此下去，求出列顺序。大话数据结构3.16结尾：写书的人，也很累；临界点在六十年代出生的人应该也就是我们父母那一基，当年计倒经济制度下他们的生活被社会安排好心先科员再科后处长再局长，混到哪算哪；学徒、技工、高级技_L;敦新-中领教帅一高级教师，总之无论喙个行业榭论蟋排芈.这怦的生活

25、如何让人奋发勇力,所以经济发展缓慢.就像我们的线性表的顺序存储结构一样，位就是排好的，一切都得慢慢来.可见，舒适环境是很唯培养出坚强品格,被安排好的人生，也很雁做出伟大事业”市场经济社会下，机会就大多了，你可以从社会的任何一个位置开始起步，只要你真有决心.没有人可以拦着你.书实也证明，无论出身是什么之前是凄苦还是富足，都有出入头他的一天当然，这也就意味着，面临的竞争也是空ft烈的，一不小心，你的位就可能被人嫡足，甚至你就得out山叮。这也塞像我线性友的蛀式存储结构，任何位置都可以插入和删除.a不怕苫，吃苦半辈F,怕吃苦，吃苦一般干.如果你觉得上学读书是受罪，假设你可以活到日。岁.其实你楠多也就

26、吃了20年苦口用人生四分之一的时间来换取其余时同的幸福生活.这点苦不算啥，再说了跟着我学习，这也能算是吃苦？好了，今天课就到这，下课.2.4.3 设计与实现 循环链表插入元素的分析1)普通插入元素(和单链表是一样的)2)尾插法(和单链表是一样的，单链表的写法支持尾插法；因：辅助指针向后跳length次，指向最后面那个元素)CircleList_Insert(list,(CircleListNode*)&v1,CircleList_Length(list);CircleList_Insert(list,(CircleListNode*)&v1,CircleList_

27、Length(list);3)头插法(要进行头插法，需要求出尾结点，和单链表不一样的地方，保证是循环链表)第一次插入元素时，让游标指向0号结点CircleList_Insert(list,(CircleListNode*)&v1,0);CircleList_Insert(list,(CircleListNode*)&v1,0);4）第一次插入元素 循环链表插入综合场景分析图1兰建插入工希（和年经表是一甘左）4、无到有的国航抽入和运蹲表是一咻彷HULL41插法，驻要求出玩相汴点?od 循环链表删除结点分析1、删除普通结点2、删除头结点(删除0号位置处元

28、素)，需要求出尾结点2.4.4 优点和缺点优点：功能强了。循环链表只是在单链表的基础上做了一个加强循环链表可以完全取代单链表的使用循环链表的Next和Current操作可以高效的遍历链表中的所有元素缺点：代码复杂度提高了大话数据结构3.16结尾：写书的人，也很累；临界点2.5双向链表2.5.1 基本概念请思考：为什么需要双向链表？单链表的结点都只有一个指向下一个结点的指针单链表的数据元素无法直接访问其前驱元素逆序访问单链表中的元素是极其耗时的操作!len=LinkList_Length(list);for(i=len-1;len>=0;i+)O(n)LinkListNode*p=Link

29、List_Get(list,i);O(n)访问数据元素p中的元素/双向链表的定义在单链表的结点中增加一个指向其前驱的pre指针双向链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素2.5.2 设计与实现循环链表一般操作插入操作currentnext *t 1、一nodecurrent->next=node;node->next=next;next->pi:e=node;node->pre=current:插入操作异常处理插入第一个元素异常处理在0号位置处插入元素；删除操作current->n

30、ext=next;next*>pre=current;删除操作异常处理双向链表的新操作获取当前游标指向的数据元素将游标重置指向链表中的第一个数据元素将游标移动指向到链表中的下一个数据元素将游标移动指向到链表中的上一个数据元素直接指定删除链表中的某个数据元素DLinkListNode*DLinkList_DeleteNode(DLinkList*list,DLinkListNode*node);DLinkListNode*DLinkList_Reset(DLinkList*list);DLinkListNode*DLinkList_Current(DLinkList*list);DLink

31、ListNode*DLinkList_Next(DLinkList*list);DLinkListNode*DLinkList_Pre(DLinkList*list);大家一定要注意：教科书不会告诉你项目上如何用；哪些点是项目的重点；做一个企业级的财富库，完成你人生开发经验的积累，是我们的学习重点，要注意!双向链表重要技术场景循环链表插入结点技术场景U通植入c urz- ETlt与性人第一个早点r E要判断 七问梯作nas r-L-ijrr&nt -3、atGUTTEt-An乎- nnd«nade ->pre - turrent, nCTt->pre - nodn

32、在尼尔崎，元臬普通话人代码潮足循环链表删除结点技术场景2.5.3 优点和缺点优点：双向链表在单链表的基础上增加了指向前驱的指针功能上双向链表可以完全取代单链表的使用双向链表的Next,Pre和Current操作可以高效的遍历链表中的所有元素缺点：代码复杂3、栈tack和队列queue3.1栈stack3.1.1Stack基本概念栈是一种特殊的线性表栈仅能在线性表的一端进行操作栈顶(Top):允许操作的一端栈底(Bottom):不允许操作的一端首先它是一个税性表,也就是说,钱元素具有线性美系，即前解后继美系,只不过它是一种将殊的统性表而已,定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指

33、栈顶.而不是榭在口它的特殊之处就在于限制了这个我性我的插人和冽除位置，它始绛只在炭顶进行这也就使得：根底是固定的,最先进栈的只能在枝底.栈的插入操祚，叫作进根，也称压栈，入栈u类似弹入弹夹，如图42由所示.栈的JM除操作,叫作出栈，也有的叫作弹栈.如同弹夹中的子弹出火.如图4233.1.2Stack的常用操作创建栈销毁栈清空栈进栈出栈获取栈顶元素获取栈的大小c语言描述=栈的设计与实现人生财富库积累#ifndef_MY_STACK_H_#define_MY_STACK_H_typedefvoidStack;Stack*Stack_Create();voidStack_Destroy(Stack*

34、stack);voidStack_Clear(Stack*stack);intStackPush(Stack*stack,void*item);void*Stack_Pop(Stack*stack);void*Stack_Top(Stack*stack);intStack_Size(Stack*stack);#endif/MYSTACKH3.1.3栈模型和链表模型关系分析统性恚的顺序耳盲来漠刁抬4 在尾拿蛀成普丽兀器不会替班别觉 组但兀手”是¥刻，防口：生粒咽足型插入JH联元.于匕找等用魁我内铤式寿金来 摸故怪的些性有特 斫如在碓亮狙部插人削解弟希比粒好sn 工，r3.1.4栈的顺序

35、存储设计与实现基本概念枝有两个元素.至核，(CFfTiJtop«U设计与实现头文件#ifndef_MY_SEQLIST_H_#define_MY_SEQLIST_H_typedefvoidSeqList;typedefvoidSeqListNode;SeqList*SeqStack_Create(intcapacity);voidSeqStack_Destroy(SeqStack*list);voidSeqStack_Clear(SeqStack*list);intSeqStack_Length(SeqStack*list);intSeqStack_Capacity(SeqStack

36、*list);intSeqStack_Insert(SeqStack*list,SeqListNode*node,intpos);SeqListNode*SeqList_Get(SeqList*list,intpos);SeqListNode*SeqListDelete(SeqList*list,intpos);#endif_MY_SEQLIST_H_3.1.5栈的链式存储设计与实现基本概念讲完哎的顺序存隔结构，我们筑在来看狗栈的链式存储结沟，筒称为链找.想想行.栈只是桎顶来做插入和恻除操作.栈顶放弃钻去的头部还旱尾部呢？由于单缝去行头指针，而覆顶指针也是必纨的，那干吗不让它俩合二为一呢，所以

37、比较好的办法是把栈顶放在单桩表的头部（如图4&1所示）*另外，都已豌有了钱顶在头部了，单链表中二转常用的头转点也就失去了意义，通常豺干镂愧来说，是不需襄头结点的&A住底设计与实现头文件#ifndef_MY_LINKSTACK_H_#define_MY_LINKSTACK_H_typedefvoidLinkStack;LinkStack*LinkStack_Create();voidLinkStackDestroy(LinkStack*stack);voidLinkStack_Clear(LinkStack*stack);intLinkStack_Push(LinkStack*s

38、tack,void*item);void*LinkStack_Pop(LinkStack*stack);void*LinkStack_Top(LinkStack*stack);intLinkStack_Size(LinkStack*stack);#endif_MY_LINKSTACK_H_3.1.6栈的应用案例1：就近匹配应用1：就近匹配几乎所有的编译器都具有检测括号是否匹配的能力如何实现编译器中的符号成对检测？#include<stdio.h>intmain()inta44;int(*p)4;p=a0;return0;算法思路从第一个字符开始扫描当遇见普通字符时忽略，当遇见左符号

39、时压入栈中当遇见右符号时从栈中弹出栈顶符号，并进行匹配匹配成功：继续读入下一个字符匹配失败：立即停止，并报错结束：成功：所有字符扫描完毕，且栈为空失败：匹配失败或所有字符扫描完毕但栈非空当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性栈非常适合于需要“就近匹配”的场合计算机的本质工作就是做数学运算，那计算机可以读入字符串“9+(3-1)*5+8/2”并计算值吗？案例2:中缀表达式和后缀表达式应用2:中缀后缀计算机的本质工作就是做数学运算，那计算机可以读入字符串“9+(3-1)*5+8/2”并计算值吗？后缀表达式=?符合计算机运算波兰科学家在20世纪50年代提出了一种将运算符放

40、在数字后面的后缀表达式对应的,我们习惯的数学表达式叫做中缀表达式=»符合人类思考习惯实例：5+4=>54+1+2*3=>123*+8+(3-1)*5=>831-5*+中缀表达式符合人类的阅读和思维习惯后缀表达式符合计算机的“运算习惯”如何将中缀表达式转换成后缀表达式？中缀转后缀算法：遍历中缀表达式中的数字和符号对于数字：直接输出对于符号：左括号：进栈运算符号：与栈顶符号进行优先级比较若栈顶符号优先级低：此符合进栈(默认栈顶若是左括号，左括号优先级最低)若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈右括号：将栈顶符号弹出并输出，直到匹配左括号遍历结束：将栈中的所

41、有符号弹出并输出中缀转后缀whil*( eKp(i ，= j )if( expli为数字)(trarisform(exp)(电低控S;Output(e»p|il);elself(expli)向符号)(wHiUspill优先场<=极预苻号优先照)output；pop(s)；1Push之印)；elseift*p|i为左括号)(Push(工exp(i)；tls«iffexp(i)为右推号)(mile筏型存号不为在括号>output(335Pop(S)；从S甲牌出左括号一else<根档.停止循环；1+:whi.le(Sie(S)>卜3(expi)Output

42、崔项布号);P叩S);计算机是如何基于后缀表达式计算的?831-5*+遍历后缀表达式中的数字和符号对于数字：进栈对于符号：从栈中弹出右操作数从栈中弹出左操作数根据符号进行运算将运算结果压入栈中遍历结束：栈中的唯一数字为计算结果compute(exp)包建粮S;1 =0;while!expi!空y)if(expi为野字)(Pushexpil;elseif(expi为符号)1从柱中弹出右寸蜃作热；2 .从柱中弹左操作数；3 .概据符号进行运苒；4 .Push(stack,结果)；)else(报格,停止循环；1+十；)if(Size(5)-L)&&(expi=,oi)横甲唯一的数字为

43、运算缩果；返回结果;)栈的神奇！中缀表达式是人习惯的表达方式后缀表达式是计算机喜欢的表达方式通过栈可以方便的将中缀形式变换为后缀形式中缀表达式的计算过程类似程序编译运行的过程扩展：给你一个字符串，计算结果1+2*(66/(2*3)+7)”1字符串解析词法语法分析优先级分析数据结本选型=»栈还是树？3.2队列queue3.2.1queue基本概念队列是一种特殊的线性表队列仅在线性表的两端进行操作队头(Front):取出数据元素的一端队尾(Rear):插入数据元素的一端队列不允许在中间部位进行操作！AM石条咬和善服手班卬.都是座用广忏钗瘠结带来实现刚才提至I的先迸先山的排队功能，这就是队

44、列.队列，queue是只允许在一端进行播入谶作.而在另一第进行除操作的线性衰队列是一种先进先出(FirstInFirstOut)的线性表，筒称FIFO.允许插入的一端称为队尾，允许删除的T称为队头.假设队列是q=(也，事，*Ah那么<1就是队员元素，而斯是队尾元素.这样我们就可以删除时，总是从*开始,而播人时，列在最后，这也比较符合我们逋常生活中的习惯，排在第一个的优先出列，最后来的当热排在队伍最后，如图4T0-1所示.队头|鼠尾I3a2a3匹11ffl4-10-1队列在程序设计中用4WE常频鬟.前面我们巳经举了两个例子.再比如用键盘进行各种字扉或数字的愉入.到显示器上如记事本软件上的输

45、出,其实就是队列的典型3.2.2queue常用操作销毁队列清空队列进队列出队列获取队头元素获取队列的长度c语言描述=队列的设计与实现人生财富库积累#ifndef_MY_QUEUE_H_#define_MY_QUEUE_H_typedefvoidQueue;Queue*Queue_Create();voidQueue_Destroy(Queue*queue);voidQueue_Clear(Queue*queue);intQueue_Append(Queue*queue,void*item);void*Queue_Retrieve(Queue*queue);void*Queue_Header(Q

46、ueue*queue);intQueue_Length(Queue*queue);#endif/MYQUEUEH3.2.3 队列模型和链表模型关系分析用象里来摸息a剂；从致幻的足煞入m列队抵蛆的口号位考出队列I.口头F口目国口需要把队列给点=力豌表年占=入锥表库用静表兼模皿认到.出总到的星器人觊列从畸表的。号也曾出队列不费忘记让所有菇点出队列，然后评兼结点的内存3.2.4 队列的顺序存储设计与实现1基本概念队列也是一种特殊的线性表；可以用线性表顺序存储来模拟队列。2设计与实现#ifndef_MY_SEQQUEUE_H_#define_MY_SEQQUEUE_H_typedefvoidSeqQu

47、eue;SeqQueue*SeqQueue_Create(intcapacity);voidSeqQueue_Destroy(SeqQueue*queue);voidSeqQueue_Clear(SeqQueue*queue);intSeqQueue_Append(SeqQueue*queue,void*item);void*SeqQueue_Retrieve(SeqQueue*queue);void*SeqQueue_Header(SeqQueue*queue);intSeqQueue_Length(SeqQueue*queue);intSeqQueue_Capacity(SeqQueue*

48、queue);#endif/MYSEQQUEUEH3.2.5 队列的链式存储设计与实现1基本概念队列也是一种特殊的线性表；可以用线性表链式存储来模拟队列的链式存储。2设计与实现#ifndef_MY_LINKQUEUE_H_#define_MY_LINKQUEUE_H_typedefvoidLinkQueue;LinkQueue*LinkQueueCreate();voidLinkQueue_Destroy(LinkQueue*queue);voidLinkQueue_Clear(LinkQueue*queue);intLinkQueue_Append(LinkQueue*queue,void*

49、item);void*LinkQueue_Retrieve(LinkQueue*queue);void*LinkQueue_Header(LinkQueue*queue);intLinkQueue_Length(LinkQueue*queue);#endifMYLINKQUEUEH4、树专题4.1 树基本概念基础讲义：参考数据结构_树A.ppt»参考数据结构_树B.ppt非线性结构，一个直接前驱，但可能有多个直接后继（1n）树的定义1）具有递归性，即树中还有树2）m颗互不相交的集合根叶子森林有序树无序树双亲孩子兄弟堂兄弟祖先子孙结点结点的度结点的层次终端结点分支结点树的度所有结点度中

50、的最大值（Max各结点的度树的深度指所有结点中最大的层数（Max各结点的层次（或高度）4.2 树的表示法图形表示法广义表表示法左孩子-右兄弟表示法双亲孩子表示法4.3 树的逻辑结构一对多（1：n）,有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。广义表表示法左孩子一右兄弟表示法4.4 二叉树概念4.4.1 基本概念二叉树的结构最简单，规律性最强可以证明，所有树都能转为唯一对应的二叉树，不失一般性定义：是n（n>0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成二叉树性质性质1:在二叉机勺第i层上至多有2i-1个结点（i&

51、gt;0）性质2:深度为k的二叉树至多有2k-i个结点（k>0）性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（no）必定为n2+1（即no=n2+1）满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k"¥满二叉树中编号从1至n的结点对应。理解：（k-1层与满二叉树完全相同，第k层结点尽力靠左）数据结构数据：数据Z构（C语言版）.严蔚敏吴伟民.扫描版.pdfp124数据结构数据：数据Z构（C语言版）.严蔚敏吴伟民.扫描版.pdfp127性质4:具有n

52、个结点的完全二叉树的深度必为log2n+1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2（i=1时为根，除外）二叉树的存储结构一、顺序存储结构按二叉树的结点自上而下、从左至右”编号，用一组连续的存储单元存储。答：一律转为完全二叉树！讨论：不是完全二叉树怎么办？方法很简单，将各层空缺处统统补上虚结点”，其内容为空二、链式存储结构4.4.2 二叉树的表示二叉树表示法P127页/*typedefstructBiTNodeintdata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;*/structBiTNodeintdata;structBiTNode*lchild,*rchild;typedefst