经典：C#-数据结构

数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。数据结构基本概念数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。

数据项：是数据的最小单位。一组数据元素具有某种结构形式。对象对象的属性1经典：C#-数据结构全文共72页，当前为第1页。数据结构定义数据结构：描述了一组性质相同的数据元素及元素间的相互关系。都是学生D:一帮学生R:按学号排序2经典：C#-数据结构全文共72页，当前为第2页。数据结构概念的三要素—定义数据元素之间的逻辑关系数据元素在计算机中的存储方式在这些数据元素上定义的运算的集合3经典：C#-数据结构全文共72页，当前为第3页。数据结构的基本分类两大类：

(一)线性结构（线性表）数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。线性表是典型的线性结构，它的数据元素只按先后次序联接。表、栈、队列、字串、数组和文件等方式。(二）非线性结构（树，图）不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。树中的数据元素是分层次的纵向联接。图中的数据元素则有各种各样复杂联接。其它种类的数据结构由这三种基本结构派生的。4经典：C#-数据结构全文共72页，当前为第4页。数据存储结构的基本方式最常用的二种方式是：顺序存储结构链式存储结构。5经典：C#-数据结构全文共72页，当前为第5页。数据元素按某种顺序存放在存储器的连续存储单元中。逻辑相邻，物理上相邻，数据元素之间的关系由存储单元的邻接关系唯一确定。例如数组就是这种存储方式顺序存储结构学生名单(逻辑结构)顺序物理结构(数组student[])071230李俊student[0]071230李俊073181章明student[1]073181章明081293向民student[2]081293向民091281肖进student[3]091281肖进6经典：C#-数据结构全文共72页，当前为第6页。顺序存储结构特点结点中只有自身信息域，没有连接信息域。存储密度大，存储空间利用率高；可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；插入、删除运算会引起大量结点的移动；要求存储在一片连续的地址中。这种存储方式主要用于线性的数据结构。7经典：C#-数据结构全文共72页，当前为第7页。存储数据结构的内存空间可以不连续，数据元素之间的关系由指针来确定。链式存储结构8经典：C#-数据结构全文共72页，当前为第8页。主要特点是：结点由两类域组成：数据域和指针域。链式存储结构特点逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。9经典：C#-数据结构全文共72页，当前为第9页。特点：表中的每个元素呈线性关系，除第一个外，都有一个直接前趋(predecessor)，除最后一个元素外，都仅有一个后继(successor)。线性表——最简单，最常用的数据结构线性表的逻辑结构线性表L用符号表示为：L=(a1，a2，a3，..ai...，an)10经典：C#-数据结构全文共72页，当前为第10页。线性表的存储结构存储结构:顺序存储结构和链接存储结构。具有顺序存储结构的线性表称为顺序表用数组储线性表中的每个数据元素。具有链接存储结构的线性表称为线性链表。用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。11经典：C#-数据结构全文共72页，当前为第11页。顺序表类设计—分析对象的属性：

自己现有的数据：存放在一个数组中现有数据的个数：长度

能存放多少数据：容量动作(Method)

构造方法：传递表的容量，创建一个空表，有效长度=0

插入：新数据插入后，数据还是有序的，长度增1

增加：在表的尾部增加一个数据，长度增1

查找：根据键值，找到数据在表中的位置，并返回，找不到返回-1

更新：用指定的值更新表中指定位置的元素的值

排序：将表中元素按从小到大排序。

获得某位置元素的值：

获得线性表的长度类型[]dataintlengthIntvolume?能为每个方法作定义吗？名字，形参表，返回类型12经典：C#-数据结构全文共72页，当前为第12页。确定表中的元素publicclassStudent{publicstringno,name;publicdoublemath,eng,computer;publicStudent(……){…….}}?这个类有点怪，属性都是public没其他方法这种类称为数据类13经典：C#-数据结构全文共72页，当前为第13页。去重返回类型问题是重新生成一个？还是直接删除应该是：ArrayList应该是：重新生成一个不破坏原来的数据14经典：C#-数据结构全文共72页，当前为第14页。去重的思维你是怎么思维的？15经典：C#-数据结构全文共72页，当前为第15页。扩展思维数据不断添加，顺序表满了后，能否自动长大？原来变更后，原来的2倍Student[]dataStudent[]templength?volume?for(…){temp[i]=data[i]}16经典：C#-数据结构全文共72页，当前为第16页。单链表—线性表的另一种存储方式一链表的基本组成元素由表头指针决定通过移动指针遍历链表，遇到null结束组成要素：节点，节点中包含数据链表的属性定义：null17经典：C#-数据结构全文共72页，当前为第17页。单链表一链表的基本组成元素—节点publicclassNode//定义节点类{publicintdata;publicNodenext;publicNode(inti){data=i; next=null;}}18经典：C#-数据结构全文共72页，当前为第18页。链表的逆转先生成一个空新链表

遍历原链表每取一个节点，向新表的表头插入新节点直到原表遍历结束19经典：C#-数据结构全文共72页，当前为第19页。去重的原理生成一个新链表遍历原表，每取一个节点，判断它在新表中是否存在，如果重复就不加。直到原表结束20经典：C#-数据结构全文共72页，当前为第20页。限定在一端进行插入与删除的线性表。允许操作的一端称为栈顶，而不允许操作的一端为栈底。给定栈(a1,…,an-1

）称a1为栈底元素，an为栈顶元素。特点后进先出(LIFOLastInFirstOut)或先进后出（FILO)的线性表。元素的插入称为进栈，元素的删除称为出栈。堆栈及逻辑结构21经典：C#-数据结构全文共72页，当前为第21页。属性栈顶指针栈的容量栈的属性和方法方法出栈：栈顶元素出栈，指针下移进栈：新元素放栈顶，指针上移判断栈空22经典：C#-数据结构全文共72页，当前为第22页。用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素顺序存储的栈指针top指示栈顶元素的位置。用Volume表示栈的容量用一维数组stack[volume]表示栈，指针top指向栈顶元素.stack[0]为最早进入栈的元素，stack[top]为最迟进入栈的元素。当top=volume-1时，为满栈.初始化top=-123经典：C#-数据结构全文共72页，当前为第23页。数据元素和栈顶指针之间的对应关系24经典：C#-数据结构全文共72页，当前为第24页。链式存储的栈关键点只需一个属性，它就是栈顶指针top基本元素与链表中的一个节点一样，参见Node类定义栈初始化时，让top指针为null

实现其push，pop和isEmpty方法主程序保持顺序存储堆栈的界面和功能25经典：C#-数据结构全文共72页，当前为第25页。压栈过程19top2810node将新给定值形成节点将新节点连接到栈顶26经典：C#-数据结构全文共72页，当前为第26页。弹出top2810保存栈顶值，栈顶指针指向下一个节点返回栈顶值27经典：C#-数据结构全文共72页，当前为第27页。队列（Queue）操作受限的线性表先进先出(FIFO)的线性表.(a1,a2,…,an)允许在表的一端插入，在表的另一端删除，插入的一端叫队尾（rear），删除的一端称队头（front）。队列28经典：C#-数据结构全文共72页，当前为第28页。顺序存储队列何时满29经典：C#-数据结构全文共72页，当前为第29页。顺序队列的属性头、尾、存储数据的数组。构造函数：设置头、尾，都是0；申请数据存储空间的数组队空front==rear满(rear+1)%volume==front进队rear=(rear+1)%volume;queue[rear]=x;出列front=(front+1)%volume;x=queue[front]30经典：C#-数据结构全文共72页，当前为第30页。①出列，booloutQueue(outintx)//ref关键字为把x的值返回给调用函数②入列，voidinQueue(intx)③判断队列是否为空，boolisEmpty()链式队列只有append方法的链表就是队列增加一个出列的方法31经典：C#-数据结构全文共72页，当前为第31页。采用链式存储结构的队列称为链队列。一个链队列需要队头和队尾的两个指针才能唯一确定。headtail32经典：C#-数据结构全文共72页，当前为第32页。二叉树定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。二叉树不是树的特殊情况。二叉树的结点子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。33经典：C#-数据结构全文共72页，当前为第33页。满二叉树：深度为K，有2K-1个结点的二叉树称为满二叉树。每一层上的结点数都是该层上的最大结点数。特殊的二叉树34经典：C#-数据结构全文共72页，当前为第34页。特殊的二叉树完全二叉树：树高为k，除第k层外，其它各层(1～k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树如果对一棵高为K,具有n个结点的完全二叉树或高为K的满二叉树从根结点开始，从上到下，从左到右进行连续编号，则位置编号与结点的编号相同。第K层少一个35经典：C#-数据结构全文共72页，当前为第35页。完全二叉树二叉树图例满二叉树36经典：C#-数据结构全文共72页，当前为第36页。性质1在二叉树中,第i层最多有2i-1个结点。i>=1性质2在深度为K的二叉树中,结点总数最多为2K-1个，K≥1性质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+137经典：C#-数据结构全文共72页，当前为第37页。性质4具有n个结点的完全二叉树的深度为log2n+1。性质4推导过程：假设树的深度为K。则根据性质2和完全二叉树的定义，有

2K-1-1<n≤2k-1

或

2K-1≤n<2k

于是K-1≤log2n<K

因为K是整数所以K=log2n+138经典：C#-数据结构全文共72页，当前为第38页。性质5

对一棵完全二叉树，n个结点自上而下，自左至右连续地从1开始编号，则对任一结点i(1≤i≤n),有：性质5—有用如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲结点数是[i/2]。如果2i>n，结点i无左孩子(此时结点i为叶子)；否则其左孩子是结点2i。如果2i+1>n,结点i无右孩子；否则其孩子是结点2i+1。39经典：C#-数据结构全文共72页，当前为第39页。ABDECFGABCDEFG////////root二叉树的链式存储40经典：C#-数据结构全文共72页，当前为第40页。二叉树节点设计publicclassTreeNode{publicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}节点类C//TreeNoden=newTreeNode(‘C’);n41经典：C#-数据结构全文共72页，当前为第41页。定义：树的每个结点按某种规律恰好被访问一次的过程。二叉树的编历从二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，若能依次遍历这三部分，便是遍历了整个二叉树。根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。太麻烦限定对左右子树的访问次序：先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。42经典：C#-数据结构全文共72页，当前为第42页。遍历后可以从非线性结构的二叉树得到各个结点的线性排列。先序遍历(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历(1)按中序遍历左子树(2)处理根(3)按中序遍历右子树后序遍历(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根ABDEFGCHI遍历的例子先序：ABDEHICFG中序：DBHEIAFCG后序：DHIEBFGCA43经典：C#-数据结构全文共72页，当前为第43页。二叉树类设计publicclassBiTree{privateTreeNoderoot;privatestringtreeStr;//记录用于创建二叉树的字符串

privateinti=0;//创建二叉树时，用变量i索引创建的字符串//创建二叉树时使用，用来引用treeStr串中的一个字符privatestringresult;//先、中、后遍历时，得到的结果记录在这里publicBiTree()

{root=null;}privatevoidsetTreeStr(strings)//设置用来构造二叉树的字符串{treeStr=s;this.i=0;}}创建树时，需要提供字符串。44经典：C#-数据结构全文共72页，当前为第44页。二叉树先序编历—已知树根voidpreOrder(TreeNodet)//递归先序遍历{if(t!=null){this.result+=""+t.data;//先序遍历的结果，保存在类属性result

preOrder(t.leftChild);preOrder(t.rightChild);}}publicTreeNodegetRoot(){returnthis.root;}从类外(窗体类)看二叉树类1如何调用？2如何获取结果？无法操作树根！因为root是私有的主窗体中：TreeNodetn=tree.getRoot();tree.preOrder(tn);结果保存在result属性中，私有解决办法：为BiTree类中增加办法45经典：C#-数据结构全文共72页，当前为第45页。二叉树先序编历—存在的问题每次调用preOrder前，需要获得树根还需要将result变量初始化，否则下次遍历的结果就不对遍历结束后，还要记住去取结果。

灰常不方便46经典：C#-数据结构全文共72页，当前为第46页。二叉树先序编历—更好的办法publicstringpreOrder()//先序遍历{this.result="";//每次调用前，result初始化

preOrder(this.root);//类内，直接用root

returnthis.result;//返回遍历结果

}利用OOP的重载原来的定义voidpreOrder(TreeNodet)重载：

同一个类中，方法名相同，形参和返回类型不一样

主窗体中：Stringans=tree.preOrder();输出ans重载的2方法一个private一个public47经典：C#-数据结构全文共72页，当前为第47页。二叉树的创建--辅助工作privateTreeNodecreateThisTree(){TreeNodet;charc;c=this.treeStr[this.i++];//从字符串中取第i个字符，i是类中定义的变量，全局if(c=='#')return(null);else{t=newTreeNode(c);t.leftChild=createThisTree();t.rightChild=createThisTree();return(t);}}publicvoidcreateTree(stringtreeStr)//给定的字符串，创建二叉树{this.setTreeStr(treeStr);root=createThisTree();}还是用重载一个private一个public//给定的字符串，以#代表树叶主函数中的调用1获得创建树字符串str2tree.createTree(str);48经典：C#-数据结构全文共72页，当前为第48页。创建二叉树ABCAB##C##ABAB###ACA#C##49经典：C#-数据结构全文共72页，当前为第49页。从遍历结果推导树给出一棵二叉树的先序遍历结果和中序遍历结果，或者给出后序遍历结果和中序遍历结果，就可画出该二叉树；只给出二叉树先序遍历结果和后序遍历结果，则无法画出该二叉树。有两棵二叉树T1和T2，它们的先序和后序遍历结果完全相同。显然只凭先序和后序遍历结果无法确定到底是哪一棵二叉树。50经典：C#-数据结构全文共72页，当前为第50页。先序为ABCDEFGHI

中序为BCAEDGHFI根据遍历解结果推导树--例子原则：根据先序定义：A必为根结点。根据中序定义：A前的结点为左子树

A后的结点为右子树。ABEFCDIGH51经典：C#-数据结构全文共72页，当前为第51页。查找在数据结构中找出满足某种条件的数据元素若在数据结构中找到了这样的元素，则称查找成功否则称查找失败。52经典：C#-数据结构全文共72页，当前为第52页。顺序查找法从表的第一个元素开始，将给定的值与表中各元素的关键字逐个进行比较，一直到找到相等的关键字，则查找成功；否则就是表中没有要找的元素，查找失败。顺序查找法publicintsearch(intkeyValue){inti=0；while(data[i]!=keyValue&&i<this.length)i++;if(i<length)returni;elsereturn-1;}

publicintsearch(intkeyValue){inti=0；for(;i<<this.length;i++){if(data[i]==keyValue)returni;elsereturn-1;}}

哪儿错了？53经典：C#-数据结构全文共72页，当前为第53页。线性查找法适用于有序线性表二分查找法以顺序方式存放的有序表的查找可采用对半查找。1821313743465257639663data[0]data[9]m=(0+9)/2=4data[m]m=(5+9)/2=7data[m]m=(8+9)/2=8data[m]54经典：C#-数据结构全文共72页，当前为第54页。线性查找法publicintbinSearch(charkeyValue){intlow,high,mid;//low,high,mid分别代表当前查找的表的下限、上限和中间位置low=0;//初始化下限为数据的第一个元素的位置high=length-1;//上限为最后一个元素的位置while(low<=high){mid=(low+high)/2;//确定中间位置if(data[mid]==keyValue)return(mid);if(data[mid]<keyValue)low=mid+1;elsehigh=mid-1;}return(-1);}二分查找法—代码55经典：C#-数据结构全文共72页，当前为第55页。二叉排序树查找二分查找法特别适合于从已排序的结点中寻找给定值。若线性表中的结点需要经常插入和删除，最好设计成结合链表和二分法的查找方法。56经典：C#-数据结构全文共72页，当前为第56页。二叉排序树定义（1）左子树不空,则左子树上所有的关键字均小于它的根结点的关键字；（2）右子树不空，则右子树上所有的关键字均大于或等于它的根结点的关键字；（3）它的左、右子树也是二叉排序树。92692189939997789157经典：C#-数据结构全文共72页，当前为第57页。二叉排序树---查找算法在给定的二叉排序树t中查找给定待查关键字K：1.如果树t为空，那么查找失败。算法结束；否则，转2。2.如果t.data=K，则查找成功。算法结束。否则转3。3.如果K<t.data，那么t=t.lchild，转（1）。

否则t=t.rchild，转（1）。58经典：C#-数据结构全文共72页，当前为第58页。二叉排序查找publicTreeNodebanSearch(doublek){TreeNodep=this.root;while((p!=null)&&(p.data!=k)){if(k<p.data)p=p.leftChild;elsep=p.rightChild;}return(p);}代码–重建二叉树,节点的数据类型改成double926921899399977891k=100查找返回的结果是什么？

59经典：C#-数据结构全文共72页，当前为第59页。二叉排序创建92692189939997789179pq找啊找啊找位置，结束的条件是什么。60经典：C#-数据结构全文共72页，当前为第60页。二叉排序创建publicvoidinsBTree(doublek){TreeNodep,q;q=newTreeNode(k);if(root==null){root=q;return;}p=root;while((p.leftChild!=q)&&(p.rightChild!=q)){if(k<p.data){if(p.leftChild!=null)p=p.leftChild;elsep.leftChild=q;}/*插入到左子树*/else{if(p.rightChild!=null)p=p.rightChild;elsep.rightChild=q;}/*插入到右子树*/}//endofwhile}61经典：C#-数据结构全文共72页，当前为第61页。二叉排序树类publicclassBiSortTree{privateTreeNoderoot;publicBiSortTree(){root=null;}publicBiSortTree(TreeNoderoot){this.root=root;}publicvoidinsBTree(doublek){……}publicTreeNodebanSearch(doublek){……}}这2个方法的代码在前面记得数据类型用double62经典：C#-数据结构全文共72页，当前为第62页。选择排序--快速排序基本思想：通过一趟分割将线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；对每一部分再进行分割，直到整个线性表有序为止。63经典：C#-数据结构全文共72页，当前为第63页。快速排序--分割步骤设置两个指针i和j，初态分别指向序列中第一个记录和最后一个记录。将第一个记录移向辅助变量x中，再从j所指位置起向前搜索第一个小于x的记录，找到后，将a[j]移至a[i]的位置；i++,从i所指向位置开始后搜索第一个关键字大于x的记录，找到后，将a[i]移至a[j]的位置；重复这两步过程，直至i==j，最后将x送至a[i]中去。至此一趟排序完成，序列划分为两个子文件。64经典：C#-数据结构全文共72页，当前为第64页。数据举例初始状态433328175263326

Xi←

j一次交换263328175263326i→←j二次交换263328175263352

i→←j三次交换26332817363352i→←j四次交换26332817363

6352ij[263328173]43[6352]i=j

65经典：C#-数据结构全文共72页，当前为第65页。数据举例(a)一趟排序初始状态[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件192124343445526066经典：C#-数据结构全文共72页，当前为第66页。一趟分割算法privatevoidqkOne(intstart,intend,refintmid)//start,end分别为起始位置，mid为最终的中间位置。{intx,i,j;i=start;j=end;x=data[i];//将第一个值保存在x中while(i!=j){while(i<j&&data[j]>=x)j--;/*右向左*/