C# 数据结构PPT课件.ppt

.,1,数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。,数据结构基本概念,数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。,数据项：是数据的最小单位。一组数据元素具有某种结构形式。,对象,对象的属性,.,2,数据结构定义,数据结构：描述了一组性质相同的数据元素及元素间的相互关系。,都是学生,D:一帮学生,R:按学号排序,.,3,数据结构概念的三要素定义,数据元素之间的逻辑关系,数据元素在计算机中的存储方式,在这些数据元素上定义的运算的集合,.,4,数据结构的基本分类,两大类：(一)线性结构（线性表）数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。线性表是典型的线性结构，它的数据元素只按先后次序联接。表、栈、队列、字串、数组和文件等方式。,(二）非线性结构（树，图）不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。树中的数据元素是分层次的纵向联接。图中的数据元素则有各种各样复杂联接。其它种类的数据结构由这三种基本结构派生的。,.,5,数据存储结构的基本方式,最常用的二种方式是：顺序存储结构链式存储结构。,.,6,数据元素按某种顺序存放在存储器的连续存储单元中。逻辑相邻，物理上相邻，数据元素之间的关系由存储单元的邻接关系唯一确定。例如数组就是这种存储方式,顺序存储结构,学生名单(逻辑结构)顺序物理结构(数组student),.,7,顺序存储结构特点,结点中只有自身信息域，没有连接信息域。存储密度大，存储空间利用率高；,可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；,插入、删除运算会引起大量结点的移动；,要求存储在一片连续的地址中。,这种存储方式主要用于线性的数据结构。,.,8,存储数据结构的内存空间可以不连续，数据元素之间的关系由指针来确定。,链式存储结构,.,9,主要特点是：结点由两类域组成：数据域和指针域。,链式存储结构特点,逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。,插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。,.,10,特点：表中的每个元素呈线性关系，除第一个外，都有一个直接前趋(predecessor)，除最后一个元素外，都仅有一个后继(successor)。,线性表最简单，最常用的数据结构,线性表的逻辑结构线性表L用符号表示为：L=(a1，a2，a3，.ai.，an),.,11,线性表的存储结构,存储结构:顺序存储结构和链接存储结构。,具有顺序存储结构的线性表称为顺序表用数组储线性表中的每个数据元素。,具有链接存储结构的线性表称为线性链表。用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。,.,12,顺序表类设计分析,对象的属性：自己现有的数据：存放在一个数组中现有数据的个数：长度能存放多少数据：容量,动作(Method)构造方法：传递表的容量，创建一个空表，有效长度=0插入：新数据插入后，数据还是有序的，长度增1增加：在表的尾部增加一个数据，长度增1查找：根据键值，找到数据在表中的位置，并返回，找不到返回-1更新：用指定的值更新表中指定位置的元素的值排序：将表中元素按从小到大排序。获得某位置元素的值：获得线性表的长度,类型dataintlengthIntvolume,?能为每个方法作定义吗？名字，形参表，返回类型,.,13,确定表中的元素,publicclassStudentpublicstringno,name;publicdoublemath,eng,computer;publicStudent().,?这个类有点怪，属性都是public没其他方法,这种类称为数据类,.,14,去重,返回类型问题,是重新生成一个？还是直接删除,应该是：ArrayList,应该是：重新生成一个不破坏原来的数据,.,15,去重的思维,你是怎么思维的？,.,16,扩展思维,数据不断添加，顺序表满了后，能否自动长大？,原来,变更后，原来的2倍,Studentdata,Studenttemp,length?volume?,for()tempi=datai,.,17,单链表线性表的另一种存储方式,一链表的基本组成元素,由表头指针决定通过移动指针遍历链表，遇到null结束组成要素：节点，节点中包含数据链表的属性定义：,null,.,18,单链表,一链表的基本组成元素节点,publicclassNode/定义节点类publicintdata;publicNodenext;publicNode(inti)data=i;next=null;,.,19,链表的逆转,先生成一个空新链表遍历原链表每取一个节点，向新表的表头插入新节点直到原表遍历结束,.,20,去重的原理,生成一个新链表遍历原表，每取一个节点，判断它在新表中是否存在，如果重复就不加。直到原表结束,.,21,限定在一端进行插入与删除的线性表。允许操作的一端称为栈顶，而不允许操作的一端为栈底。给定栈(a1,an-1）称a1为栈底元素，an为栈顶元素。特点后进先出(LIFOLastInFirstOut)或先进后出（FILO)的线性表。元素的插入称为进栈，元素的删除称为出栈。,堆栈及逻辑结构,.,22,属性栈顶指针栈的容量,栈的属性和方法,方法出栈：栈顶元素出栈，指针下移进栈：新元素放栈顶，指针上移判断栈空,.,23,用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,顺序存储的栈,指针top指示栈顶元素的位置。,用Volume表示栈的容量,用一维数组stackvolume表示栈，指针top指向栈顶元素.stack0为最早进入栈的元素，stacktop为最迟进入栈的元素。当top=volume-1时，为满栈.,初始化top=-1,.,24,数据元素和栈顶指针之间的对应关系,.,25,链式存储的栈,关键点,只需一个属性，它就是栈顶指针top基本元素与链表中的一个节点一样，参见Node类定义栈初始化时，让top指针为null实现其push，pop和isEmpty方法主程序保持顺序存储堆栈的界面和功能,.,26,压栈过程,19,top,2,8,10,node,将新给定值形成节点将新节点连接到栈顶,.,27,弹出,top,2,8,10,保存栈顶值，栈顶指针指向下一个节点返回栈顶值,.,28,队列（Queue）操作受限的线性表先进先出(FIFO)的线性表.(a1,a2,an)允许在表的一端插入，在表的另一端删除，插入的一端叫队尾（rear），删除的一端称队头（front）。,队列,.,29,顺序存储队列,何时满,.,30,顺序队列的属性,头、尾、存储数据的数组。,构造函数：设置头、尾，都是0；申请数据存储空间的数组,队空front=rear,满(rear+1)%volume=front进队rear=(rear+1)%volume;queuerear=x;出列front=(front+1)%volume;x=queuefront,.,31,出列，booloutQueue(outintx)/ref关键字为把x的值返回给调用函数入列，voidinQueue(intx)判断队列是否为空，boolisEmpty(),链式队列,只有append方法的链表就是队列增加一个出列的方法,.,32,采用链式存储结构的队列称为链队列。一个链队列需要队头和队尾的两个指针才能唯一确定。,head,tail,.,33,二叉树,定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。,二叉树不是树的特殊情况。二叉树的结点子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。,.,34,满二叉树：深度为K，有2K-1个结点的二叉树称为满二叉树。每一层上的结点数都是该层上的最大结点数。,特殊的二叉树,.,35,特殊的二叉树,完全二叉树：树高为k，除第k层外，其它各层(1k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树如果对一棵高为K,具有n个结点的完全二叉树或高为K的满二叉树从根结点开始，从上到下，从左到右进行连续编号，则位置编号与结点的编号相同。,第K层少一个,.,36,完全二叉树,二叉树图例,满二叉树,.,37,性质1在二叉树中,第i层最多有2i-1个结点。i=1性质2在深度为K的二叉树中,结点总数最多为2K-1个，K1性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1。,二叉树性质,推导：设n1为二叉树T度为1的结点数。因为二叉树T中结点的度数均小于或等于2，所以其结点总数为:n=n0+n1+n2(1)设m为二叉树T中总的分支数目。因为除根结点外，其余结点都有一个分支进入，所以m=n-1。但这些分支是由度为1或2的结点射出的，所以m=n1+2n2,于是得n=n1+2n2+1(2)由(1)式和(2)式得n0=n2+1,.,38,性质4具有n个结点的完全二叉树的深度为log2n+1。,性质4,推导过程：假设树的深度为K。则根据性质2和完全二叉树的定义，有2K-1-1n2k-1或2K-1nn，结点i无左孩子(此时结点i为叶子)；否则其左孩子是结点2i。,如果2i+1n,结点i无右孩子；否则其孩子是结点2i+1。,.,40,A,B,D,E,C,F,G,A,B,C,D,E,F,G,/,/,/,/,/,/,/,/,root,二叉树的链式存储,.,41,二叉树节点设计,publicclassTreeNodepublicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc)data=c;leftChild=null;rightChild=null;,节点类,C,/,/,TreeNoden=newTreeNode(C);,n,.,42,定义：树的每个结点按某种规律恰好被访问一次的过程。,二叉树的编历,从二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，若能依次遍历这三部分，便是遍历了整个二叉树。,根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。太麻烦,限定对左右子树的访问次序：先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。,.,43,遍历后可以从非线性结构的二叉树得到各个结点的线性排列。先序遍历(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历(1)按中序遍历左子树(2)处理根(3)按中序遍历右子树后序遍历(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根,A,B,D,E,F,G,C,H,I,遍历的例子,先序：ABDEHICFG,中序：DBHEIAFCG,后序：DHIEBFGCA,.,44,二叉树类设计,publicclassBiTreeprivateTreeNoderoot;privatestringtreeStr;/记录用于创建二叉树的字符串privateinti=0;/创建二叉树时，用变量i索引创建的字符串/创建二叉树时使用，用来引用treeStr串中的一个字符privatestringresult;/先、中、后遍历时，得到的结果记录在这里publicBiTree()root=null;privatevoidsetTreeStr(strings)/设置用来构造二叉树的字符串treeStr=s;this.i=0;,创建树时，需要提供字符串。,.,45,二叉树先序编历已知树根,voidpreOrder(TreeNodet)/递归先序遍历if(t!=null)this.result+=+t.data;/先序遍历的结果，保存在类属性resultpreOrder(t.leftChild);preOrder(t.rightChild);,publicTreeNodegetRoot()returnthis.root;,从类外(窗体类)看二叉树类1如何调用？2如何获取结果？,无法操作树根！因为root是私有的,主窗体中：TreeNodetn=tree.getRoot();tree.preOrder(tn);,结果保存在result属性中，私有解决办法：为BiTree类中增加办法,.,46,二叉树先序编历存在的问题,每次调用preOrder前，需要获得树根还需要将result变量初始化，否则下次遍历的结果就不对遍历结束后，还要记住去取结果。,灰常不方便,.,47,二叉树先序编历更好的办法,publicstringpreOrder()/先序遍历this.result=;/每次调用前，result初始化preOrder(this.root);/类内，直接用rootreturnthis.result;/返回遍历结果,利用OOP的重载,原来的定义voidpreOrder(TreeNodet),重载：同一个类中，方法名相同，形参和返回类型不一样,主窗体中：Stringans=tree.preOrder();输出ans,重载的2方法一个private一个public,.,48,二叉树的创建-辅助工作,privateTreeNodecreateThisTree()TreeNodet;charc;c=this.treeStrthis.i+;/从字符串中取第i个字符，i是类中定义的变量，全局if(c=#)return(null);elset=newTreeNode(c);t.leftChild=createThisTree();t.rightChild=createThisTree();return(t);,publicvoidcreateTree(stringtreeStr)/给定的字符串，创建二叉树this.setTreeStr(treeStr);root=createThisTree();,还是用重载一个private一个public,/给定的字符串，以#代表树叶,主函数中的调用1获得创建树字符串str2tree.createTree(str);,.,49,创建二叉树,A,B,C,AB#C#,A,B,AB#,A,C,A#C#,.,50,从遍历结果推导树,给出一棵二叉树的先序遍历结果和中序遍历结果，或者给出后序遍历结果和中序遍历结果，就可画出该二叉树；,只给出二叉树先序遍历结果和后序遍历结果，则无法画出该二叉树。,有两棵二叉树T1和T2，它们的先序和后序遍历结果完全相同。显然只凭先序和后序遍历结果无法确定到底是哪一棵二叉树。,.,51,先序为ABCDEFGHI中序为BCAEDGHFI,根据遍历解结果推导树-例子,原则：根据先序定义：A必为根结点。根据中序定义：A前的结点为左子树A后的结点为右子树。,A,B,E,F,C,D,I,G,H,.,52,查找,在数据结构中找出满足某种条件的数据元素,若在数据结构中找到了这样的元素，则称查找成功否则称查找失败。,.,53,顺序查找法,从表的第一个元素开始，将给定的值与表中各元素的关键字逐个进行比较，一直到找到相等的关键字，则查找成功；否则就是表中没有要找的元素，查找失败。,顺序查找法,publicintsearch(intkeyValue)inti=0；while(datai!=keyValue,publicintsearch(intkeyValue)inti=0；for(;ithis.length;i+)if(datai=keyValue)returni;elsereturn-1;,哪儿错了？,.,54,线性查找法,适用于有序线性表,二分查找法,以顺序方式存放的有序表的查找可采用对半查找。,18,21,31,37,43,46,52,57,63,96,63,data0,data9,m=(0+9)/2=4,datam,m=(5+9)/2=7,datam,m=(8+9)/2=8,datam,.,55,线性查找法,publicintbinSearch(charkeyValue)intlow,high,mid;/low,high,mid分别代表当前查找的表的下限、上限和中间位置low=0;/初始化下限为数据的第一个元素的位置high=length-1;/上限为最后一个元素的位置while(low=high)mid=(low+high)/2;/确定中间位置if(datamid=keyValue)return(mid);if(datamidkeyValue)low=mid+1;elsehigh=mid-1;return(-1);,二分查找法代码,.,56,二叉排序树查找,二分查找法特别适合于从已排序的结点中寻找给定值。,若线性表中的结点需要经常插入和删除，最好设计成结合链表和二分法的查找方法。,.,57,二叉排序树定义,（1）左子树不空,则左子树上所有的关键字均小于它的根结点的关键字；,（2）右子树不空，则右子树上所有的关键字均大于或等于它的根结点的关键字；,（3）它的左、右子树也是二叉排序树。,92,69,21,89,93,99,97,78,91,.,58,二叉排序树-查找算法,在给定的二叉排序树t中查找给定待查关键字K：,1.如果树t为空，那么查找失败。算法结束；否则，转2。,2.如果t.data=K，则查找成功。算法结束。否则转3。,3.如果Kt.data，那么t=t.lchild，转（1）。否则t=t.rchild，转（1）。,.,59,二叉排序查找,publicTreeNodebanSearch(doublek)TreeNodep=this.root;while(p!=null),代码重建二叉树,节点的数据类型改成double,92,69,21,89,93,99,97,78,91,k=100查找返回的结果是什么？,.,60,二叉排序创建,92,69,21,89,93,99,97,78,91,79,p,q,找啊找啊找位置，结束的条件是什么。,.,61,二叉排序创建,publicvoidinsBTree(doublek)TreeNodep,q;q=newTreeNode(k);if(root=null)root=q;return;p=root;while(p.leftChild!=q)elsep.leftChild=q;/*插入到左子树*/elseif(p.rightChild!=null)p=p.rightChild;elsep.rightChild=q;/*插入到右子树*/endofwhile,.,62,二叉排序树类,publicclassBiSortTreeprivateTreeNoderoot;publicBiSortTree()root=null;publicBiSortTree(TreeNoderoot)this.root=root;publicvoidinsBTree(doublek)publicTreeNodebanSearch(doublek),这2个方法的代码在前面,记得数据类型用double,.,63,选择排序-快速排序,基本思想：通过一趟分割将线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；,对每一部分再进行分割，直到整个线性表有序为止。,.,64,快速排序-分割步骤,设置两个指针i和j，初态分别指向序列中第一个记录和最后一个记录。将第一个记录移向辅助变量x中，再从j所指位置起向前搜索第一个小于x的记录，找到后，将aj移至ai的位置；i+,从i所指向位置开始后搜索第一个关键字大于x的记录，找到后，将ai移至aj的位置；重复这两步过程，直至i=j，最后将x送至ai中去。至此一趟排序完成，序列划分为两个子文件。,.,65,数据举例,初始状态433328175263326Xij一次交换263328175263326ij二次交换263328175263352ij三次交换26332817363352ij四次交换263328173636352ij263328173436352i=j,.,66,数据举例,(a)一趟排序初始状态4521341952603424第一趟242