C和C++与数据结构基础讲义

传智播客c和C++与数据结构基础讲义传智扫地僧1、数据结构概念数据结构相关概念疑惑1、我学完了c语言,可是现在感觉还是写不出代码。2、为什么会有各种各样的程序存在?3、程序的本质是什么?程序是为了具体问题而存在的程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏?数据结构起源计算机从解决数值计算问题到解决生活中的问题现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系不是研究复杂的算法1.13数据结构中的基本概念数据ー程序的操作对象,用于描述客观事物（inta,intbj数据的特点:可以输入到计算机可以被计算机程序处理数据是ー个抽象的概念，将其进行分类后得到程序设计语言中的类型。如:int,float,char等等数据元素:组成数据的基本单位数据项：ー个数据元素由若干数据项组成数据对象一性质相同的数据元素的集合 （比如:数组,链表）〃友情提示,来自结构体课堂代码〃声明一个结构体类型struct_MyTeacher 〃ー种数据类型(charname[32];chartile[32];intage;charaddr[128];｝；intmain21()(struct_MyTeachertl;〃数据元素struct_MyTeachertArray[30];〃数据对象memset(&tl，0,sizeof(tl));strcpy(,“name”);〃数据项strcpy(tl.addr,"addr“);〃数据项strcpy(tl.tile,“addr”);〃数据项tl.age=1;ー个ーー个ー个的结点数据元素之间不是独立的,存在特定的关系,这些关系即结构数据结构指数据对象中数据元素之间的关系如:数组中各个元素之间存在固定的线性关系编写一个“好”的程序之前,必须分析待处理问题中各个对象的特性,以及对象之间的关系。基本概念总结:

数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。逻辑结构可细分为4类:根据数据天素间关系的基本特性.有四种基本数据结构 cC°〇〇〇（集合） 数据え素间除“同属于ー一个集合”外.无其它关式"ー个对ー个.如线ー个对ー个.如线性表、栈、队列ー个对多个.如柯一多个对・多•个.如图数据的物理结构答:物理结构亦称 ,是数据的逻辑结构在计算机存储器内的表示（或映像）〇它依赖•算机。存储结构可分为4大类:顺序、链式、,素引、散列最常用的有•储结构为:顺用存储结构 借助元素在存储器中的相对位咒来表示数据元素间的逻辑关系健式存储结构 借助指示元素存储地址的指针表示数据ヱ布间的逻辑关系 Q1数据的迫辑结构与存储结构密切相关算法设计—►逻辑结构算法实现—►存储结构数据的运算W*3:什幺JL蒙哥的运算（弊作ッU・）答:在数据的逻辑结构上定义的操作,它最常用的数据运算有5种:插ハ、删除、修改,、查找、林序算法算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的ー种解决问题的方法和思想。对于算法而言,语言并不重要,重要的是思想。2=Xc^=vo算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法===今程序=数据结构+算法总结:算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成算法特性输入算法具有。个或多个输入输出算法至少有1个或多个输出有穷性算法在有限的步骤之后会自动结束而不会无限循环确定性算法中的每ー步都有确定的含义,不会出现二义性可行性算法的每ー步都是可行的算法效率的度量1、事后统计法比较不同算法对同一组输入数据的运行处理时间缺陷为了获得不同算法的运行时间必须编写相应程序运行时间严重依赖硬件以及运行时的环境因素算法的测试数据的选取相当困难事后统计法虽然直观,但是实施困难且缺陷多算法效率的度量事前分析估算依据统计的方法对算法效率进行估算影响算法效率的主要因素算法采用的策略和方法问题的输入规模编译器所产生的代码计算机执行速度〃算法最终编译成具体的计算机指令〃每ー个指令,在具体的计算机上运行速度固定〃通过具体的n的步骤,就可以推导出算法的复杂度longsuml(intn)(longret=0;int*array=(int*)malloc(n*sizeof(int));inti=0;for(i=0;i<n;i++){array[i]=i+1;}for(i=0;i<n;i++)(ret+=array[i];free(array);returnret;}longsum2(intn)(longret=0;inti=0;for(i=l;i<=n;i++)ret+=i;}returnret;longsum3(intn)longret=0;if(n>0){ret=(l+n)*n/2;}returnret;}intmain(){printf("%d\n"zsuml(100));printf("%d\n,,/sum2(100));printf("%d\n"zsum3(100));return0;}intfunc(inta[],intlen)(inti=0;intj=0;ints=0;for(i=0;i<len;i++)n(for(j=0;j<len;j++)n(s+=i*j;//n*n))returns;}//n*n

次政・法C(4n*8)•法(n)一法D(2nX)A狭D*(n*)n■1■□131n=216294n-3 201 319i9n«104810201100n»1004081002000110000n-10004008100020000011000000次数A漆G(2n2)算法H(3n+1)A法1(2n2*3n*1)n=1wJ6n«287I15n«55011666n-10200イ31231n-1002000030120301n«1.0002000000।30012003001n1。。。い20000000030001200030001100.00020000000000130000120000300001n-19000to0020000000000001 3000001； 2000003000001注意1:判断ー个算法的效率时,往往只需要关注操作数量的最髙次项,其它次要项和常数项可以忽略。注意2:在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度。2、大0表布法 算法效率严重依赖于操作(Operation)数量在判断时首先关注操作数量的最高次项操作数量的估算可以作为时间复杂度的估算0(5)=0(1)O(2n+l)=O(2n)=O(n)O(n2+n+l)=O(n2)O(3n3+l)=O(3n3)=O(n3)常见时间复杂度数行次・・・阶非正式术电120(1)2n+30(71)1成性阶3n2+2n*l0(J)千オ”51og2n*20O(logn)时数阶2n+3111og2n+19O(r7iog/>)nlogn阶6n'>2n;>3n♦40(/?)Jし才・2b10(2") 指效阶 0(1)<O(logn)<0(n)<O(/rfogn)<0(n2)<0(n3)<0(2")<0(d)<0(ガ)3、算法的空间复杂度算法的空间复杂度通过计算算法的存储空间实现S(n)=0(f{n))其中,n为问题规模,f(n))为在问题规模为n时所占用存储空间的函数大〇表示法同样适用于算法的空间复杂度当算法执行时所需要的空间是常数时,空间复杂度为0(1)空间与时间的策略多数情况下,算法执行时所用的时间更令人关注如果有必要,可以通过增加空间复杂度来降低时间复杂度同理，也可以通过增加时间复杂度来降低空间复杂度 练习1:分析sumlsum2sum3函数的空间复杂度O(4n+12)0(8)=0(l)0(4)=0(l)总结:实现算法时,需要分析具体问题,对执行时间和空间的要求。练习2:时间换空间/*问题:在ー个由自然数1-1000中某些数字所组成的数组中,每个数字可能出现零次或者多次。设计ー个算法,找出出现次数最多的数字。7方法1:排序，然后找出出现次数最多的数字方法2：voidsearch(inta[],intlen)(intsp[1000]={0};inti=0;intmax=0;for(i=0;i<len;i++){intindex=a[i]-1;sp[index]++;}for(i=0;i<1000;i++){if(max<sp[i])2、线性表线性表基本概念线性表定义线性表(List)是零个或多个数据元素的集合线性表中的数据元素之间是有顺序的线性表中的数据元素个数是有限的线性表中的数据元素的类型必须相同先来一个大家最感兴趣的,一年里的星座列表,是不是线性表呢?如图3-2-2所示,白金双巨狮处天射摩水双羊・牛・子•蟹・子・女•秤・手•羯・瓶・鱼数学定义线性表是具有相同类型的n(20)个数据元素的有限序列(al,a2,an)ai是表项,n是表长度。性质a0为线性表的第一个元素,只有一个后继an为线性表的最后ー个元素,只有一个前驱除a0和an外的其它元素ai,既有前驱，又有后继线性表能够逐项访问和顺序存取练习下面的关系中可以用线性表描述的是A.班级中同学的友谊关系N:NB,公司中的上下级关系1:NC.冬天图书馆排队占座关系D.花名册上名字之间的关系1::12.2.5线性表的操作创建线性表销毁线性表清空线性表将元素插入线性表将元素从线性表中删除获取线性表中某个位置的元素获取线性表的长度线性表在程序中表现为ー种特殊的数据类型线性表的操作在程序中的表现为ー组函数 c语言描述=====》线性表的设计与实现ADT抽象层 《[数据结构(C语言版)].严蔚敏一吴伟民.扫描版,pdf》p44页人生财富库积累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;〃创建并且返回一个空的线性表List*List_Create();〃销毁ー个线性表!istvoidList_Destroy(List*list);〃将一个线性表!ist中的所有元素清空,线性表回到创建时的初始状态voidList_Clear(List*list);〃返回一个线性表!ist中的所有元素个数intList_Length(List*list);〃向ー个线性表list的pos位置处插入新元素nodeintList_lnsert(List*list,ListNode*node,intpos);〃获取ー个线性表list的pos位置处的元素ListNode*List_Get(List*list,intpos);〃删除ー个线性表list的pos位置处的元素返回值为被删除的元素,NULL表示删除失败ListNode*List_Delete(List*list,intpos);#endif注意:intUstlnsert(List*list,ListNode*node,intpos);(重点:分离思想)2.2线性表的顺序存储结构基本概念3.4.1顺序存储定义说这么多的线性表,我们来な狗线性表的两种物理结构的第一种一顺序存储结构・线性表的・序存储结构,指的是用一段地址连续的存储单元依次存储线性衰的效据元・。线性表(ana?,……,an)的顺序存储示意图如ド:B|a2•••••• A>.| & ••••••Sq图3412.2.2设计与实现插入元素算法判断线性表是否合法判断插入位置是否合法把最后ー个元素到插入位置的元素后移ー个位置将新元素插入_线性表长度加］ 获取元素操作判断线性表是否合法判断位置是否合法直接通过数组下标的方式获取元素删除元素算法判断线性表是否合法判断删除位置是否合法将元素取出将删除位置后的元素分别向前移动ー个位置线性表长度减1链表顺序存储插入算法和删除算法

〃1元素后移for(i：len〃1元素后移for(i：len(th.l>poe.i~)5Ir®4ナ/ンつク J 需檢空風/严Pろ|ユ匐4«6ンー。アW？ロR然^^^ロロ 亠/ゴ.除空间2.2.3优点和缺点优点:无需为线性表中的逻辑关系增加额外的空间可以快速的获取表中合法位置的元素缺点:插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量2.3线性表的链式存储基本概念链式存储定义为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。n个结点（あ的存储映像）链结成一个链表,即为线性表（珈,az,…，aD）的链式存储结构,因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单縫表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在ー起,如图3-6-2痛。数据信息结点指针 & 0500 如0200 / x中数据域指针域 I地址0500表头结点链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的ー些信息数据结点链表中代表数据元素的结点,包含指向下ー个数据元素的指针和数据元素的信息尾结点链表中的最后ー个数据结点,其下一元素指针为空,表示无后继。链表技术领域推演设计与实现链表链式存储.api实现分析在c语言中可以用结构体来定义链表中的指针域链表中的表头结点也可以用结构体实现typedefstructag_LinkListNodeLinkListNode;structag_LinkListNode(LinkListNode*next:J：结点指针域定义structValue(LinkListNodeheader;structValue(LinkListNodeheader;intv;h数据元素定义示例LinkListNodeheader;intlength;}TLinkList;头结点定义currentcurrent->nextnode带头结点、位置从O的单链表返回链表中第3个位置处,元素的值LinkListNode*LinkList_Get(LinkList*list,intpos)inti=0;TLinkList*tList=(TLinkList*)list;LinkListNode*current二NULL;LinkListNode*ret=NULL;if(listニニNULL|pos<0||pos>=tList->length){returnNULL;)current二(LinkListNode*)tList;for(i=0;i<pos;i++){current=current->next;}ret=current->next;returnret;)返回第三个位置的移动pos次以后,当前指针指向哪里?答案:指向位置2,所以需要返回ret=current->next;备注:循环遍历时, 遍历第1次,指向位置0遍历第2次，指向位置1遍历第3次，指向位置2遍历第n次，指向位置n-l;所以如果想返回位置n的元素的值，需要怎么做ret=current->next;此问题是：指向头结点的指针移动n次和第n个元素之间的关系?删除元素current人ret_一 人ーret->next1f ヽr ヽf 1Hi-Ia. 4ハ・current->next=ret->next;重要技术场景图a.a»+i链表链式存储.插入1指针指向谁就把谁的地址臓给指针2分清理慑表的操作逻辑和辅助指针变量之间的关系链表链式存储ー删除因为慎裏是単同的,3号位置保存在泻位置的next域中〃繚存被則除的节点位置ret=current->next;〃连线〃连线current->next=ret->neit.!指针指向惟就把惟的地址赋给指针2分清更慎表的操作逻辑和れ助指针变量之间的关系优点和缺点优点:无需一次性定制链表的容量插入和删除操作无需移动数据元素缺点:数据元素必须保存后继元素的位置信息获取指定数据的元素操作需要顺序访问之前的元素2.4循环链表2.4.1基本概念循环链表的定义:将单链表中最后ー个数据元素的next指针指向第一个元素天结点循环链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素新增功能:游标的定义在循环链表中可以定义ー个“当前”指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素。■aian,,a2共结点1游标slider尾结点循环链表新操作将游标重置指向链表中的第一个数据元素CircleListNode*CircleList_Reset(CircleList*list);获取当前游标指向的数据元素CircleListNode*CircleList_Current(CircleList*list);尾结点%将游标移动指向到链表中的下ー个数据元素CircleListNode*CircleList_Next(CircleList*list);直接指定删除链表中的某个数据元素CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node);〃根据元素的值删除元素pk根据元素的位置删除元素2.4.2循环链表的应用证明循环链表打印两次。约瑟夫问题求解约瑟夫问题ー循环链表典型应用n个人围成一个圆圈,首先第1个人从1开始ー个人一个人顺时针报数,报到第m个人,令其出列。然后再从下一个人开始从1顺时针报数,报到第m个人,再令其出列，…，如此下去,求出列顺序。大话数据结构3.16结尾:写书的人,也很累;临界点五六十年代出生的人,应该也就是我们父母那ー装,当年计划经济制度下,他们内生活被社会安排好了,先科员再科长、后处长科局长,混到哪算费;学徒、技工、高级技工;教师、中级教师、高级教师，总之无他哪个行业都怆资排辈.这样的生活如何让人奋发努力,所以经济发展缓堂・就像我们的线性表的腕序存储结构ー样,位置是排好的,一切都得慢慢来.可见,舒适环境是很难培养出坚强品格,被安排好的人生,也很难做出伟大事业.市场经济社会下,机会就大多了,你可以从社会的任何ー个位置开始起步,只要你真有决心,没有人可以拦着你・事实也证明,无论出身是什么,之前是凄苦还是富足，都有出人头地的一天.当然,这也就意味着，面临的竞争也是空前激烈的,ー不小心,你的位置就可能被人插足,甚至你就得out出局•这也多像我们銭性表的链式キ储结构,任何位置都可以插入和刷除・ a•不怕苦,吃苦半輩子,怕吃苦,吃苦ー辈子•如果你觉得上学读书是受罪,假设尔可以活到80岁,其实你最多也就吃了20年苦，用人生四分之一的时间来换取其余月间的幸福生活,这点苦不算啥。再说了,跟脣我学习,这也能算是吃苦?好了,今天课就到这,下课。2.4.3设计与实现循环链表插入元素的分析1）普通插入元素（和单链表是ー样的）2）尾插法（和单链表是ー样的,单链表的写法支持尾插法;因:辅助指针向后跳length次,指向最后面那个元素）CircleList_Insert(list,CircleList_Insert(list,CircleList_Insert(list,(CircleListNode*)&vl,CircleList_Length(list));(CircleListNode*)&vl,CircleList_Length(list));3）头插法（要进行头插法,需要求出尾结点,和单链表不一样的地方,保证是循环链表）第一次插入元素时,让游标指向0号结点CircleList_Insert(list,(Circ1eListNode*)&v1,0);CircleListlnsert(1ist,(CircleListNode*)&vl,0);4)第一次插入元素2.432循环链表插入综合场景分析图!普通插入元素（和单悽表是一样的）4头插法,需要求出尾部节点循环链表删除结点分析1,删除普通结点2、删除头结点(删除。号位置处元素),需要求出尾结点2.4.4优点和缺点优点:功能强了。循环链表只是在单链表的基础上做了一个加强循环链表可以完全取代单链表的使用循环链表的Next和Current操作可以高效的遍历链表中的所有元素缺点:代码复杂度提高了大话数据结构3.16结尾:写书的人,也很累;临界点2.5双向链表2.5.I基本概念请思考:为什么需要双向链表?单链表的结点都只有一个指向下ー个结点的指针单链表的数据元素无法直接访问其前驱元素逆序访问单链表中的元素是极其耗时的操作!len=LinkList_Length(list);for(i=len-l;len>=0;i++)//0(n)(LinkListNode*p=LinkList_Get(list,i);//0(n)〃访问数据元素p中的元素

n}双向链表的定义在单链表的结点中增加一个指向其前驱的pre指针…__，大シ^ 11al 旳 %ゆー!t 1L__lt 双向链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素2.5.2设计与实现循环链表一般操作插入操作current->next=node;node->next=next;nextー〉pre=node;node->pre=current;插入操作异常处理插入第一个元素异常处理在。号位置处插入元素;删除操作current->next=next;next->pre=current;删除操作异常处理双向链表的新操作获取当前游标指向的数据元素将游标重置指向链表中的第一个数据元素将游标移动指向到链表中的下ー个数据元素将游标移动指向到链表中的上一个数据元素

直接指定删除链表中的某个数据元素DLinkListNode*DLinkList_DeleteNode(DLinkList*list,DLinkListNode*node);DLinkListNode*DLinkList_Reset(DLinkList*list);DLinkListNode*DLinkList_Current(DLinkList*list);DLinkListNode*DLinkList_Next(DLinkList*list);DLinkListNode*DLinkList_Pre(DLinkList*list);〃大家一定要注意:教科书不会告诉你项目上如何用:哪些点是项目的重点;做ー个企业级的财富库,完成你人生开发经验的积累,是我们的学习重点,要注意!循环链表插入结点技术场景普通価入currentnext通人第一个元素next=current->neitnode->neit=next.current->next=node.node->pre=current,next-循环链表插入结点技术场景普通価入currentnext通人第一个元素next=current->neitnode->neit=next.current->next=node.node->pre=current,next->pre=node;着插入第一个给点,需要到・<!饯後作在足部榆入元素普通插入代码満足循环链表删除结点技术场景界除费:除第一个鮎点ojrrwnt禮ル時:表:罰际后ー个结点ciarrtnt->neit循环链表删除结点技术场景界除费:除第一个鮎点ojrrwnt禮ル時:表:罰际后ー个结点ciarrtnt->neit«rwst-)vr«scurxvnt.2.5.3优点和缺点优点:双向链表在单链表的基础上增加了指向前驱的指针功能上双向链表可以完全取代单链表的使用双向链表的Next,Pre和Current操作可以高效的遍历链表中的所有元素缺点:代码复杂3、栈tack和队列queue3.1栈stack3.1.1Stack基本概念栈是ー种特殊的线性表栈仅能在线性表的一端进行操作栈顶(Top):允许操作的一端栈底(Bottom):不允许操作的一端

首先它是ー个线性表,也就是说,栈元素具有线性关系,即前覧后継关系.只不过它是ー种特殊的线性表而巳,定义中说是在线性表的表尾进行插入和刷除操作,这里麦兄是指栈顶,而不是栈底.它的特殊之处就在于限制了这个线性表的插入和納除位置,它始终只在栈顶进行.这也就使得:桃底是固定的,最先进栈的只能在栈底.栈的插入操作,叫作进栈,也称圧栈、入栈,类似子弾入弹夹,如图4-2-2所示.栈的删除操作,叫作出栈,也有的叫作弾快・如同弾夹中的子弾出夹,如图4-2-3所示.3.1.2Stack的常用操作创建栈销毁栈清空栈进栈出栈获取栈顶元素获取栈的大小C语言描述=二=ニ》栈的设计与实现人生财富库积累ttifndef_MY_STACK_H_#define_MY_STACK_H_typedefvoidStack;Stack*Stack_Create();voidStack_Destroy(Stack*stack);voidStack_Clear(Stack*stack);intStackPush(Stack*stack,void*item);

void*Stack_Pop(Stack*stack);void*Stack_Top(Stack*stack);intStack_Size(Stack*stack);ttendif//MYSTACKH栈模型和链表模型关系分析用戋性表的提式存储来模賴区的线性存储丽レ在隨表用戋性表的提式存储来模賴区的线性存储丽レ在隨表头部通入删除元素比较好000鶴麻對體元素弾也ツ克第茨会涉及到数所以:在数组尾部插入删除元量比较好ロロロ口ロロロ栈的顺序存储设计与实现基本概念设计与实现头文件#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*list);intSeqStack_lnsert(SeqStack*list,SeqListNode*node,intpos);SeqListNode*SeqList_Get(SeqList*list,intpos);SeqListNode*SeqListDelete(SeqList*list,intpos);#endif//_MY_SEQLIST_H_栈的链式存储设计与实现基本概念讲完了栈的顺序存储结构,我们现在来看看帔的整式存储结构,倚称为链栈.想想な,栈只是栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?由于单链表有头指针,而栈顶指针也是必须的,那干吗不让它俩合二为ー呢,所以比较好的办法是把栈顶放在单链费的头部（如图4-6*1所示）•另外,都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义,通常对于链根来说,是不需要头结点的.设计与实现头文件#ifndef_MY_LINKSTACK_H_#define_MY_LINKSTACK_H_typedefvoidLinkstack;LinkStack*LinkStack_Create();voidLinkStackDestroy(LinkStack*stack);voidLinkStack_Clear(LinkStack*stack);intLinkStack_Push(LinkStack*stack,void*item);void*LinkStack_Pop(LinkStack*stack);void*LinkStack_Top(LinkStack*stack);intLinkStack_Size(LinkStack*stack);#endif//MYLINKS7ACKH3.1.6栈的应用案例1:就近匹配应用L一就近匹配 几乎所有的编译器都具有检测括号是否匹配的能力如何实现编译器中的符号成对检测?ftinclude<stdio.h>intmainO{inta[4][4];int(*p)[4];p=a[0];return0;算法思路从第一个字符开始扫描当遇见普通字符时忽略,当遇见左符号时压入栈中当遇见右符号时从栈中弹出栈顶符号,并进行匹配匹配成功:继续读入下ー个字符匹配失败:立即停止，并报错结束:成功:所有字符扫描完毕,且栈为空失败：匹配失败或所有字符扫描完毕但栈非空当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性栈非常适合于需要“就近匹配”的场合计算机的本质工作就是做数学运算，那计算机可以读入字符串“9+(3-1)*5+8/2”并计算值吗?案例2:中缀表达式和后缀表达式应用2:中缀后缀计算机的本质工作就是做数学运算,那计算机可以读入字符串“9+(3-1)*5+8/2”并计算值吗? 后缀表达式==?符合计算机运算波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式对应的,我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯实例:5+4=>54+1+2*3=>123*+8+(3-1)*5=>831-5*+中缀表达式符合人类的阅读和思维习惯后缀表达式符合计算机的“运算习惯”如何将中缀表达式转换成后缀表达式?中缀转后缀算法:遍历中缀表达式中的数字和符号对于数字:直接输出对于符号:左括号：进栈运算符号:与栈顶符号进行优先级比较若栈顶符号优先级低：此符合进栈(默认栈顶若是左括号,左括号优先级最低)若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈右括号:将栈顶符号弹出并输出，直到匹配左括号遍历结束：将栈中的所有符号弹出并输出中缀转后缀transform(exp){S;中while(exp⑴»«W)(1*(exp(i]カ徴字)(Output(exp(i));}elseif(expfi]为符号){while(exp(i]tt5t»<-WB符号)(output(eD«符号)；Pop(S);Push(S,exp[i]);}elseif(exp(i]カ左括号)(Push(S,exp[i])；)elseif(exp(i)为右箍号)(while(後及符号不力左括号)(output(桟术苻号)；Pop(S);从S中聲出左括号:}else(报槽,停止循环;while(Size(S)>0)&&(exp(i)='X〇,,){。utput(极!¢符号)；Pop(S)；计算机是如何基于后缀表达式计算的?831-5*+遍历后缀表达式中的数字和符号对于数字:进栈对于符号:从栈中弹出右操作数从栈中弹出左操作数根据符号进行运算将运算结果压入栈中遍历结束：栈中的唯一数字为计算结果compute(exp){创建桟S;i=o；while(exp[i]1=<'。I){if(exp[i]カ数字){Push(S,exp[i]);}elseif(exp[i]为符号){1.从栈中弾出右操作数;2从栈中弾出左操作數;.根据符号进行运算;.Push(stack,结果)；}else{报错,停止循环;)i++;)if((Size(S)==1)(exp[i]==、。<)){栈中唯一的数字为运算结果;}返回结果;)栈的神奇!中缀表达式是人习惯的表达方式后缀表达式是计算机喜欢的表达方式通过栈可以方便的将中缀形式变换为后缀形式中缀表达式的计算过程类似程序编译运行的过程扩展:给你ー个字符串,计算结果“1+2*(66/(2*3)+7)”1字符串解析词法语法分析优先级分析数据结构选型===》栈还是树?3.2队列queue3.2.1queue基本概念队列仅在线性表的两端进行操作队头(Front):取出数据元素的一端队尾(Rear):插入数据元素的一端队列不允许在中间部位进行操作!療作糸统和客服糸统中,都是应用r一艸数度结佝釆实现刚オ提到的先进先出的排队功籍,这就是队列.队列(queue)是只允许在一端进行插入操作,而在另ー・进行・・掾作的线性表。队列是ー种先进先出(FirstInFirstOut)的线性表，简称FIFO•允许插入的ー端称为队尾,允许删除的一端称为队头。假设队列是q=(at,a2,……,a.)(那么a就是队头元素,而an是队尾元素.这样我们就可以删除时,忌是从a!开始,而插入时,列在最后，这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后，如图4-1C-I所示・图4*I(M队列在程序设计中用得非常頻繁。前面我们已经举了两个例子,再比如用覆盘进行各种字母或数字的输入,到显示器上如记事本软件上的输出,其实就是队列的典型3.2.2queue常用操作销毁队列清空队列进队列出队列获取队头元素获取队列的长度c语言描述=====》队列的设计与实现人生财富库积累ttifndef_MY_QUEUE_H_ttdefine_MY_QUEUE_H_typedefvoidQueue;Queue*Queue_Create();voidQueue_Destroy(Queue*queue);

voidQueue_Clear(Queue*queue);intQueue_Append(Queue*queue,void*item);void*QueueRetrieve(Queue*queue);void*Queue_Header(Queue*queue);intQueue_Length(Queue+queue);ttendif//MYQUEUEH队列模型和链表模型关系分析用数组来模狙队列,从数组的尾部入队列从数组的。号位置出队列0 1 2 3 4 5 6队头二口区同ロコロコロロ对尾用能表来模拟队列.从M列的尾部人队列从・表的。号位置出队列需要把队列结点二ニ〉言表貂点ー:〉入厳表库0gozpロコOD不要忘记让所有结点出队列,然后释放结点的内存对尾队列的顺序存储设计与实现1基本概念队列也是ー种特殊的线性表;可以用线性表顺序存储来模拟队列。2设计与实现#ifndef_MY_SEQQUEUE_H_#define_MY_SEQQUEUE_H_typedefvoidSeqQueue;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);intSeqQueueCapacity(SeqQueue*queue);#endif//MYSEQQUEUEH队列的链式存储设计与实现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*item);void*LinkQueue_Retrieve(LinkQueue*queue);void*LinkQueue_Header(LinkQueue*queue);intLinkQueue_Length(LinkQueue*queue);#endif//MYLINKQUEUEH4、树专题树基本概念基础讲义: 参考《数据结构ー树A.ppt》参考《数据结构ー树B.ppt》 非线性结构,ー个直接前驱,但可能有多个直接后继（l:n）树的定义1）具有递归性,即树中还有树_2）m颗互不相交的集合 根叶子森林有序树无序树双亲孩子兄弟堂兄弟祖先子孙 结点结点的度结点的层次终端结点分支结点树的度所有结点度中的最大值（Max｛各结点的度｝树的深度指所有结点中最大的层数（Max｛各结点的层次｝（或高度）树的表示法图形表示法 广义表表示法左孩子ー右兄弟表示法双亲孩子表示法树的逻辑结构ー对多（l:n）,有多个直接后继（如家谱树、目录树等等）,但只有一个根结点,且子树之间互不相交。广义表表示法左孩子ー右兄弟表示法ニ叉树概念基本概念ニ叉树的结构最简单,规律性最强可以证明,所有树都能转为唯一对应的ニ叉树,不失一般性定义:是n（n20）个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的ニ叉树组成ニ叉树性质性质1:在ニ叉树的第i层上至多有2~1个结点（i>0）性质2:深度为k的ニ叉树至多有2セ1个结点（k>0）性质3:对于任何ー棵ニ叉树,若2度的结点数有1个，则叶子数（n0）必定为立+1（即no=n2+l）满ニ叉树:ー棵深度为k且有2ム1个结点的ニ叉树。（特点:每层都“充满”了结点）完全ニ叉树：深度为k的,有"个结点的二叉树，当且仅当其每ー个结点都与深度为k的满ニ叉树中编号从1至n的结点ーー对应。理解：（k-1层与满ニ叉树完全相同,第k层结点尽力靠左）数据结构数据：［数据结构（C语言版）1.严蔚敏一吴伟民.扫描版.pdfpl24数据结构数据：［数据结构（C语言版））.严蔚敏一吴伟民.扫描版.pdfpl27性质4:具有n个结点的完全ニ叉树的深度必为（jog2n」+l性质5:对完全ニ叉树,若从上至下、从左至右编号,则编号为，的结点,其左孩子编号必为2i,其右孩子编号必为其双亲的编号必为ン2（，=ユ时为根,除外）ニ叉树的存储结构ー、顺序存储结构按ニ叉树的结点”自上而下、从左至右"编号，用ー组连续的存储单元存储。答:一律转为完全ニ叉树!讨论:不是完全ニ叉树怎么办?方法很简单,将各层空缺处统统补上“虚结点”,其内容为空二、链式存储结构ニ叉树的表示ニ叉树表示法P127页/*typedefstructBiTNode(intdata;structBiTNode*lchild,*rchild;JBiTNode,*BiTree;ツstructBiTNode(intdata;structBiTNode*lchild,*rchild;）；typedefstructBiTNodeBiTNode;typedefstructBiTNode*BiTree;树的三叉链表表示〃三叉链表typedefstructTriTNode(intdata;〃左右孩子指针structTriTNode*lchild,*rchild;structTriTNode*parent;}TriTNode,*TriTree;双亲链表法〃双亲链表#defineMAX_TREE_SIZE100typedefstructBPTNode(intdata;intparentPosition;〃指向双亲的指针〃数组下标charLRTag;〃左右孩子标志域}BPTNode;typedefstructBPTree

BPTNodenodes[100];〃因为节点之间是分散的,需要把节点存储到数组中intnum_node;〃节点数目introot;〃根结点的位置〃注意此域存储的是父亲节点在数组的下标}BPTree;〃用这个数据结构能表达出ー颗树,为什么?ニ叉树的遍历口诀:DLR一先序遍历,即先根再左再右

LDR一中序遍历,即先左再根再右LRD—后序遍历,即先左再右再根先序遍历的结果是:A中序遍历的结果是:DBEAC? 后序遍历的结果是：DEBCA先序遍历:ABCDEFGH

中序遍历:BDCEAFHG

后原遍历:DECBHGFA树的遍历本质剖析

从前面的三种遍历算法可以知道:如果・将从前面的三种遍历算法可以知道:如果・将printf语句抹去,从递归的角度看,这三种算法是完全相同的,或者说这三种遍历算法的访问路整是相同的,只是访问结点的时机不同.从虚线的出发点到终点的路径上,每个结点经过3次.第1次经过时访问=先序遍历第2次经过时访问=中序遇历第3次经过时访问=后序遍历】效率:。(n)〃每个结点只访问ー次] ：0(n)//栈占用的故大辅动空间(精确值:树深为k的递归遍历需要k+个辅助单元!)ニ叉树编程实践基本操作typedefstructnode{intdata;structnode*lchild,*rchild；}NODE;NODE*root;DLR(NODE*root)(if(root)〃非空ニ叉树{printf("%d”,root->data);〃访问DDLR(root->lchild);〃递归遍历左子树DLR(root->rchild);〃递归遍历右子树}中序遍历算法LDR(NODE*root){if(root!=NULL){LDR(root->lchild);printf(//%droot->data);LDR(root->rchild);})后序遍历算法LRD(NODE*root){if(root!=NULL){LRD(root->lchild);LRD(root->rchild);printf(〃％d”,rootodata);}}案例1:计算ニ叉树中叶子结点的数目intsum=0;〃全局变量DLR_CountLeafNum(NODE*root)〃采用中序遍历的递归算法{if(root)〃非空ニ叉树条件,还可写成if(root!:NULL){if(!root->lchild&&!root->rchild)〃是叶子结点则统计并打印{sum++;printf("%d\n"/root->data);}DLR_CountLeafNum(root->lchild);〃递归遍历左子树,直到叶子处;DLR_CountLeafNum(root->rchild);}〃递归遍历右子树,直到叶子处;}return(O);}思想:1)求根结点左子树的叶子结点个数,累计到sum中,求根结点右子树的叶子结点个数累计到sum中。2)若左子树还是树,重复步骤1;若右子树还是树,重复步骤1。3)全局变量转成函数参数4)按照先序、中序、后序方式计算叶子结点,==ニ》三种遍历的本质思想强化:访问结点的路径都是ー样的,计算结点的时机不同。案例2:求ニ叉树的深度思想:1)求根结点左子树高度,根结点右子树高度,比较的子树最大髙度,再+1。2)若左子树还是树,重复步骤1;若右子树还是树，重复步骤1。案例3:完全Copyニ叉树思想:1)malloc新结点,2)拷贝左子树,拷贝右子树,让新结点连接左子树,右子树

3)若左子树还是树,重复步骤1、2i若右子树还是树,重复步骤1、2〇案例4:树的非递归遍历(中序遍历)中序遍历的几种情况分析1:什么时候访问根、什么时候访问左子树、什么访问右子树当左子树为空或者左子树已经访问完毕以后,再访问根访问完毕根以后,再访问右子树。分析2:非递归遍历树,访问结点时,为什么是栈，而不是其他模型(比如说是队列)。先走到的后访问、后走到的先访问，显然是栈结构分析3:结点所有路径情况步骤1：如果结点有左子树，该结点入栈:如果结点没有左子树，访问该结点;步骤2：如果结点有右子树，重复步骤1;如果结点没有右子树(结点访问完毕)，根据栈顶指示回退，访问栈顶元素，并访问右子树,重复步骤1如果栈为空，表示遍历结束。注意:入栈的结点表示,本身没有被访问过,同时右子树也没有被访问过。分析4:有一个ー直往左走入栈的操作,中序遍历的起点四、中序遍历算法的非递归描述BiI"N«k!cinlarlcil(BiTreeT.Stack*S)|if(!T)return\lI.lzwhile(T-khild)1l»ush(S.3：I,-T-(child:Ireturnf:昨逼，内止序娃的的耳法voidinorder1(BiTreeT.void••xisii)(TelemType&e))|SlackeS.tirtilarlLS):找到最左下的雨.鼠while<t)(visitu-data).ifit-rchild)t®GoFarLeftCt-rchild.S).dwif(!StackI：mpt>(S»找ス空时遅枝tQRojXS).ekeL、ULL.〃ぜ堂・明当々然果 .JL-UI

4.6ニ叉树的创建中序和先序创建树1、根据中序遍历的结果能确定一棵树吗?中序遍历:结果为:“12345”,这个“12345”能确定一棵树吗?请思考,会有多少种形状。2、如何才能确定一棵树?结论:通过中序遍历和先序遍历可以确定一个树通过中序遍历和后续遍历可以确定一个树通过先序遍历和后序遍历确定不了一个树。单独先序遍历:能求解根,但不能求解左子树什么时候结束、右子树什么时候开始。3、根据先序和中序结果画树算法1、通过先序遍历找到根结点A,再通过A在中序遍历的位置找出左子树,右子树2、在A的左子树中,找左子树的根结点（在先序中找），转步骤13、在A的右子树中，找右子树的根结点（在先序中找），转步骤1讲解:先序遍历结果:ADEBCF中序遍历结果：DEACFB练习:先序遍历结果：ABDHKECFIGJ中序遍历结果：HKDBEAIFCGJ4、学习算法可借助工具、动画光盘有2个;C++有1个#号法创建树1、什么是#号法创建树#创建树,让树的每ー个节点都变成度数为2的树

左子可的右チ，）的橫結点・,リ『油右子树カ:T=(Bintree)malloc(sizeof(BinTNode));BintreeT;charch;scanf("%c”,&ch);左子可的右チ，）的橫結点・,リ『油右子树カ:T=(Bintree)malloc(sizeof(BinTNode));BintreeT;charch;scanf("%c”,&ch);if(かメ#')T=NULL;先序遍历:124###3##可以唯一确定一棵树吗,为什么?3、#号法编程实践利用前序遍历来建树（结点值陆续从键盘输入,用DLR为宜）BintreecreateBTpre（）2#创建树练习先序遍历:ABDH#K###E##CFI###G#J##,请画出树的形状#号法画出树关键点:要清楚的确定左子树什么结束,右子树什么时候开始I的士子竹和右子轲边臬分明軻就■え了T->data=ch;T->lchild=createBTpre();T->rchild=createBTpre();}returnT;〃后序遍历销毁ー个树voidBiTree_Free(BiTNode*T){BiTNode*tmp=NULL;if(T!=NULL){if(T->rchild!=NULL)BiTree_Free(T->rchild);if(T->lchild!=NULL)BiTree_Free(T->lchild);if(T!=NULL){free(T);T=NULL;})4.7ニ叉线索树线索化概念1、前言普通ニ叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得。若可将遍历后对应的有关前驱和后继预存起来,则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。ニ叉线索树思想是干什么的?中序遍历这棵树===》转换成黄表访问2线索化思想(1)采用ニ叉链表!效率这么低,能否利用这些空闲区存放有用的信息?(2)ニ叉链表只能找到结点的左右孩子信息,而不能得到结点在任一序列中的前驱和后继信息,这种信息只有在遍历过程中才能得到,我们可否对ニ叉链表进行改造?增加两个域:fwd和bwd;两种解决方法, ［存放前驱指彳:ス放后继指针利用空链域(n+1个空链域)——我们可以用这n+1个空链域来存放当前结点的直接

前驱和后继等线索,以加快查找速度。-〉ニ叉线索树1）若结点有左子树,则khild指向其左孩子;

否则,khild指向其直接前驱（即线索）;2）若结点有右子树,则rchild指向其右孩子;

否则,rchild指向其直接后继即线索）。ラ了追免混淆,增加两个标志域,如下图所示:IchildLTagdata|RTagrchild当Tag域为0时,表示正常情况;当Tag域为时,表示线索情况.画出以下ニ叉树对应的 线索ニ叉树.该ニ叉树中序遍历结果为: ,D,I,B,E,A,F,C,所以添加线索应当按如下路径进行:结论:线索化过程就是在遍历过程（假设是中序遍历）中修改空指针的过程:将空的Ichild改为结点的直接前驱:将空的rchild改为结点的直接后继。3线索化思想训练请将此树线索化。1）右空指针线索化:2）左空指针线索化3）总结通过图6-10-4（空心箭头实线为前驱,虚线黑箭头为后继）,就更容易看出,其实线簧ニ叉樹,等于是把一棵ニ叉树转变成了一个双向链表,这样对我们的插入刷除结点,査找某个结点都带来了方便.所以我们对ニ叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。图G1CM4.7.2线索化的实现1)线索化树结点typedefstructBiThrNode/・ニ叉线索存储结点结构・/(chardata;/・结点数据・/structBiThrNode*lchildz*rchild;/・左右孩子指针・/int LTag;int RTag; /・左右标志・/}BiThrNode,*BiThrTree;2)线索化思想分析两个勒田计变量文督历字符細組ifCp->lchilduMULL1I1.p->l<hlld3pre}.if(prt->r<hil4=NULL)(pre*>ta«=1,>re>>rchild=p)prs=P.线索化的本质:让前后结点,建立关系;1）两个辅助指针变量形成差值后:后继结点的左孩子指向前驱结点,前驱结点的右孩子指

向后继结点。2）赋值指针变量和业务操作的逻辑关系有了线索ニ叉树后,我们对它进行遍历时发现,其实就等于是操作ー个双向铢表埒构・和双向摄表结构ー样,在ニ叉树线索链表上添加一个头结点,如图6-10-6所示,并令其khild域的指针指向ニ叉树的艰结点（囲中的①）,其rchiH域的指针指向中序遍历时访冋的最后ー个结点（图中的②）.反之，令ニ叉恸的中序序列中的第一个结点中,IchiH域指针和最后ー个结点的rchild域指针均指向头结点（图中的③和④）.这样定义的好处就是我们既可以从第一个结点起期后继进行遍历，也可以从最后ー个结点起顺前驱进行遍历.IHIIHIBilhrNode♦pre./*主局嫌蝦掴冋刖刖幽竣續点«//・史庄遍历进摩統化・/-voidInThreading(BilhrNode*p)Iif(p)(InThreading(p->lchild);〃劇覇迂因线度化if(p->lchild=NULL)/Z没有左直子(p->LTag=1;p->lchild=pre, //®黑线盂左基王指出B回前里)if(pre->rchild=NULL)/Z飕没亙右就(pre->RTag=1;pre->rchild=p;//)Pre=p; //侯技困損物的J遽InThreading(p->rchild);/Z递归有モ松t线索化4）ニ叉树线索化树的遍历/・中序遍历ニ叉线索树T（头结点）的非递归算法・/intlnOrderTraverse_Thr（BiThrNode*T）BiThrNode*p;p=T->lchild;/*p指向根结点・/while(p!=T)(/・空树或遍历结束时,p==T*/while(p->LTag==Link)p=p->lchild;printf("%c",p->data);while(p->RTag==Thread&&p->rchild!=T)(p=p->rchild;printf("%c",p->data);)p=p->rchild;)return0;}4.8霍夫曼树概念组建一个网络,耗费最小WPL最小;这个方法是霍夫曼想出来的,称为霍夫曼树我们先把这两慄ニ叉樹简化成叶子结点带权的ニ叉樹,如图6-12-4所示.其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀.毎个叶子的分支线上的数字就是刚オ我们提到的五级分制的成绩所占比例數.二又•U ニ叉树bffi6-12-4桂夫曼大叔说,从慌中一个结点到另ー个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度。图6-12-4的ニ文树a中,根结点到结点D的路径长度就为♦,ニ叉树b中根结点到结点D的路径长度为2.树的路径长度就是从樹根到毎ー结点的路径长度之和。ニ叉树a的棚路径长度就为1“+2+2+3+3+4+4=2〇.ニ叉树b的树路径长度就为1+2+3+3+2“+2+2=16.如果考虑到带权的结点,结点的帯权的路径长度为从该结点到樹根之间的路径长度与结点上权的乘积.树的帯权路径氏度为悦中所有叶子结点的带权路径长度之和.假设有n个权值｛WLWZ.Wj,构造ー棵有!!个叶子结点的ニ叉树,每个叶子结点带权Wk,每个叶子的路整长度为1k,我们通冨记作,则其中帯权路径长度WPL，小的二叉树称做赫夫曼樹。也有不少书中也称为最优ニ叉树,我个人觉得为了妃念做出巨大贡献的科学家,既然用他们的名字命名,就应愎要坚持用他们的名字称呼•事怕・最优”更能体现这棵树的品质也应该只作为别名.霍夫曼树的构造对于文本"BADCADFEED”的传输而言,因为重复出现的只有"ABCDEド’这6个字符,因此可以用下面的方式编码:ABCDEF000001010011100101BADCADFEEDI)001000011010000011101100100011接收方可以根据每3个bit进行一次字符解码的方式还原文本信息。这样的编码方式需要30个bit位才能表示10个字符那么当传输ー篇500个字符的情报时,需要15000个bit位在战争年代,这种编码方式对于情报的发送和接受是很低效且容易出错的。如何提高收发效率? 一要提髙效率，必然要从编码方式的改进入手，要避免每个字符都占用相同的bit位ABCDEF01100110100111000BADCADFEEDI)1001010010101001000111100准则:任一字符的编码都不是另ー个字符编码的前缀!也就是说:每ー个字符的编码路径,都不包含另外一个字符的路径。霍夫曼树.给定n个数值{vl,v2,…,vn}.根据这n个数值构造ニ叉树集合FF={Tl,T2,...»Tn}Ti的数据域为vi,左右子树为空.在F中选取两棵根结点的值最小的树作为左右子树构造一棵新的ニ叉树,这棵ニ叉树的根结点中的值为左右子树根结点中的值之和.在F中删除这两棵子树,并将构造的新ニ叉树加入F中.重复3和4,直到F中只剩下ー个树为止。这棵树即霍夫曼树假设经过统计ABCDEF在需要传输的报文中出现的概率如下ABCDEF27%8%15%15%30%5%

霍夫曼树是ー种特殊的ニ叉树霍夫曼树应用于信息编码和数据压缩领域霍夫曼树是现代压缩算法的基础5、排序排序基本概念现实生活中排序很重要宝貝店铺淘宝网［所有分类>诺密件下査找Q共3.28万件宝贝程序设计培调课程大学教材数据库计算机,网络其它你是不是您找:歎据结梅戸衛勒 大话歎修结构 勲据结悯c-+ jav臟据结构 数据结构股人是 计算机蛆成原理 数据结构セ领所有宝贝天雷二手r宝貝店铺淘宝网［所有分类>诺密件下査找Q共3.28万件宝贝程序设计培调课程大学教材数据库计算机,网络其它你是不是您找:歎据结梅戸衛勒 大话歎修结构 勲据结悯c-+ jav臟据结构 数据结构股人是 计算机蛆成原理 数据结构セ领所有宝贝天雷二手r发货保隆r7-^1»r正品保障r海外商品厂旺旺在续r货到付款全新缘台2013最新版数据结构（:语言版附光盘+题集C语言版共2本产鼾被夫TnAucon世安书缭图书さ数色和我”納里 信用，量新,价格¥45.00运费:0.00信用卡北京所在地ー合并卖凛if：：108人付款83人收债

10幅评论も正品保防E!正退换初8结杓（C诸言版）（含光盘）产前敝.吴 ・24.S0 用》背后 “人付款25人（W・ もsaw*体艮済华大学出版社 运费，*。。 2降ヰ论 n沃达提算法已写好代码复用&_和我们需要学习前辈们的经验不矛盾,也不代表我们不需要不学习。 排序是计算机内经常进行的ー种操作,其目的是将一组“无序”的数据元素调整为“有序”的数据元素。排序数学定义:假设含n个数据元素的序列为｛R1,R2,…,Rn｝其相应的关键字序列为｛KI,K2,…,Kn｝这些关键字相互之间可以进行比较,即在它们之间存在着这样ー个关系:KplWKp2近…WKpn按此固有关系将上式记录序列重新排列为｛Rpl,Rp2,…,Rpn｝的操作称作排序排序的稳定性如果在序列中有两个数据元素中]和r[j],它们的关键字k[i]==k[j],且在排序之前,对象r[i]排在内]前面。如果在排序之后,对象中]仍在巾]前面,则称这个排序方法是稳定的;否则称这个排序方法是不稳定的。 多关键字排序排序时需要比较的关键字多余ー个排序结果首先按关键字1进行排序当关键字1相同时按关键字2进行排序当关键字n-1相同时按关键字n进行排序对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可! 排序中的关键操作比较任意两个数据元素通过比较操作确定先后次序交换_数据元素之间需要交换才能得到预期结果 内排序和外排序内排序整个排序过程不需要访问外存便能完成外排序待排序的数据元素数量很大,整个序列的排序过程不可能在内存中完成 排序的审判时间性能关犍性能差异体现在比较和交换的数量辅助存储空间为完成排序操作需要的额外的存储空间必要时可以“空间换时间’'算法的实现复杂性_过于复杂的排序法会影响代码的可读性和可维护性,也可能影响排序的性能 总结排序是数据元素从无序到有序的过程排序具有稳定性,是选择排序算法的因素之ー比较和交换是排序的基本操作多关键字排序与单关键字排序无本质区别排序的时间性能是区分排序算法好坏的主要因素选择法基本思想每ー趟（例如第i趟,i=0,1,…,ル2）在后面n-i个待排的数据元素中选出关键字最小的元素,作为有序元素序列的第i个元素。排序过程首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换

再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交重复上述操作,共进行n-1趟排序后,排序结束kk1 1k例i=l初始:[.38659776・2,]jjjjjjkki=2ー趟:13.65977649■]"tttt+jjjjj二趟:13 27[6597764938] 1三趟:13 2738甲764965]四趟:13 273849[769765]五趟:13 27384965[9776]六趟：13 2738496576[97]排序结束:13 2738496576 97假设排序过程中,待排数据元素序列的状态为:有序序列无序序列R[i..n]从中选出第j趟 丨关键字最小的元素ォ序序列「[0.•列无序序列R[i+l..n]插入排序基本思想:

元素1个元素,排序过程:整个排序过程为n-l趟插入,即先将序列中第1个记录看成是ー个有序子序列,然后从第2个记录开始,逐个进行插入，直至整个序列有序实质:对线性表执行n-l次插入操作，只是先要找到插入位置V[O],Vロ），…,已经排好序。这时已经排好序。这时,用V[i）的关键字与…的关键字进行比较,找到插入位置即将V[小插入,原来位置上的对象向后顺移。插入排序关键点:：I、拿出ー个元素，留出位置、2符合条件的元素后移例 ア1例 ア1i=2i=3i=4i=5i=6i=7ITOC\o"1-5"\h\z(38 49) 6597 76 13 27(38 49 65)97 76 13 27(38 49 6597) 76 13 27(3849657697)1327I(133849657697)彳7排序结果:(13273849657697)冒泡排序排序过程・将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].key>r[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止 第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上・对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位