《C#数据结构.pptx》由会员分享，可在线阅读，更多相关《C#数据结构.pptx（71页珍藏版）》请在课桌文档上搜索。
1、数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。,数据结构基本概念,数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。,数据项：是数据的最小单位。一组数据元素具有某种结构形式。,对象,对象的属性,数据结构定义,数据结构：描述了一组性质相同的数据元素及元素间的相互关系。,都是学生,D:一帮学生,R:按学号排序,数据结构概念的三要素定义,数据元素之间的逻辑关系,数据元素在计算机中的存储方式,在这些数据元素上定义的运算的集合,数据结构的基本分类,两大类：(一)线性结构（线性表）数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。线性表
2、是典型的线性结构，它的数据元素只按先后次序联接。表、栈、队列、字串、数组和文件等方式。,(二）非线性结构（树，图）不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。树中的数据元素是分层次的纵向联接。图中的数据元素则有各种各样复杂联接。其它种类的数据结构由这三种基本结构派生的。,数据存储结构的基本方式,最常用的二种方式是：顺序存储结构链式存储结构。,数据元素按某种顺序存放在存储器的连续存储单元中。逻辑相邻，物理上相邻，数据元素之间的关系由存储单元的邻接关系唯一确定。例如 数组就是这种存储方式,顺序存储结构,学生名单(逻辑结构)顺序物理结构(数组student),顺序存储结构特点,
3、结点中只有自身信息域，没有连接信息域。存储密度大，存储空间利用率高；,可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；,插入、删除运算会引起大量结点的移动；,要求存储在一片连续的地址中。,这种存储方式主要用于线性的数据结构。,存储数据结构的内存空间可以不连续，数据元素之间的关系由指针来确定。,链式存储结构,主要特点是：结点由两类域组成：数据域和指针域。,链式存储结构特点,逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。,插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。,特点：表中的每个元素呈线性关系，除第一个外，
4、都有一个直接前趋(predecessor)，除最后一个元素外，都仅有一个后继(successor)。,线性表最简单，最常用的数据结构,线性表的逻辑结构 线性表L用符号表示为：L=(a1，a2，a3，.ai.，an),线性表的存储结构,存储结构:顺序存储结构和链接存储结构。,具有顺序存储结构的线性表称为顺序表 用数组储线性表中的每个数据元素。,具有链接存储结构的线性表称为线性链表。用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。,顺序表类设计分析,对象的属性：自己现有的数据：存放在一个数组中 现有数
5、据的个数：长度 能存放多少数据：容量,动作(Method)构造方法：传递表的容量，创建一个空表，有效长度=0 插入：新数据插入后，数据还是有序的，长度增1 增加：在表的尾部增加一个数据，长度增1 查找：根据键值，找到数据在表中的位置，并返回，找不到返回-1 更新：用指定的值更新表中指定位置的元素的值 排序：将表中元素按从小到大排序。获得某位置元素的值：获得线性表的长度,类型 dataint lengthInt volume,?能为每个方法作定义吗？名字，形参表，返回类型,确定表中的元素,public class Student public string no,name;public doub
6、le math,eng,computer;public Student().,?这个类有点怪，属性都是public没其他方法,这种类称为数据类,去重,返回类型问题,是重新生成一个？还是直接删除,应该是：ArrayList,应该是：重新生成一个 不破坏原来的数据,去重的思维,你是怎么思维的？,扩展思维,数据不断添加，顺序表满了后，能否自动长大？,原来,变更后，原来的2倍,Studentdata,Studenttemp,length?volume?,for()tempi=datai,单链表线性表的另一种存储方式,一 链表的基本组成元素,由表头指针决定通过移动指针遍历链表，遇到null结束组成要素：
7、节点，节点中包含数据链表的属性定义：,null,单链表,一 链表的基本组成元素节点,public class Node/定义节点类 public int data;public Node next;public Node(int i)data=i;next=null;,链表的逆转,先生成一个空新链表 遍历原链表每取一个节点，向新表的表头插入新节点直到原表遍历结束,去重的原理,生成一个新链表遍历原表，每取一个节点，判断它在新表中是否存在，如果重复就不加。直到原表结束,限定在一端进行插入与删除的线性表。允许操作的一端称为栈顶，而不允许操作的一端为栈底。给定 栈(a1,an-1）称a1为栈底元素，a
8、n为栈顶元素。特点 后进先出(LIFO Last In First Out)或先进后出（FILO)的线性表。元素的插入称为进栈，元素的删除称为出栈。,堆栈及逻辑结构,属性栈顶指针栈的容量,栈的属性和方法,方法出栈：栈顶元素出栈，指针下移进栈：新元素放栈顶，指针上移判断栈空,用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,顺序存储的栈,指针top指示栈顶元素的位置。,用Volume表示栈的容量,用一维数组stackvolume表示栈，指针top 指向栈顶元素.stack0为最早进入栈的元素，stacktop为最迟进入栈的元素。当top=volume-1时，为满栈.,初始化 top=-1,
9、数据元素和栈顶指针之间的对应关系,链式存储的栈,关键点,只需一个属性，它就是栈顶指针top基本元素与链表中的一个节点一样，参见Node类定义栈初始化时，让top指针为null 实现其push，pop和isEmpty 方法主程序保持顺序存储堆栈的界面和功能,压栈过程,19,top,2,8,10,node,将新给定值形成节点将新节点连接到栈顶,弹出,top,2,8,10,保存栈顶值，栈顶指针指向下一个节点返回栈顶值,队列（Queue）操作受限的线性表先进先出(FIFO)的线性表.(a1,a2,an)允许在表的一端插入，在表的另一端删除，插入的一端叫队尾（rear），删除的一端称队头（front）。
10、,队列,顺序存储队列,何时满,顺序队列的属性,头、尾、存储数据的数组。,构造函数：设置头、尾，都是0；申请数据存储空间的数组,队空 front=rear,满(rear+1)%volume=front进队 rear=(rear+1)%volume;queuerear=x;出列 front=(front+1)%volume;x=queuefront,出列，bool outQueue(out int x)/ref关键字为把x的值返回给调用函数入列，void inQueue(int x)判断队列是否为空，bool isEmpty(),链式队列,只有append方法的链表就是队列增加一个出列的方法,采用
11、链式存储结构的队列称为链队列。一个链队列需要队头和队尾的两个指针才能唯一确定。,head,tail,二叉树,定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。,二叉树不是树的特殊情况。二叉树的结点子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。,满二叉树：深度为K，有2K-1个结点的二叉树称为满二叉树。每一层上的结点数都是该层上的最大结点数。,特殊的二叉树,特殊的二叉树,完全二叉树：树高为k，除第 k 层外，其它各层(1k-1)的结点数都达到最大个数，第 k 层从右向左连续缺若干结
12、点，这就是完全二叉树 如果对一棵高为K,具有n个结点的完全二叉树或高为K的满二叉树从根结点开始，从上到下，从左到右进行连续编号，则位置编号与结点的编号相同。,第K层少一个,完全二叉树,二叉树图例,满二叉树,性质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中总的分支数目。因为除根结点外，其余结
13、点都有一个分支进入，所以m=n-1。但这些分支是由度为1或2的结点射出的，所以m=n1+2n2,于是得n=n1+2n2+1(2)由(1)式和(2)式得 n0=n2+1,性质4 具有n个结点的完全二叉树的深度为log2n+1。,性质4,推导过程：假设树的深度为K。则根据性质2和完全二叉树的定义，有 2K-1-1n2k-1 或 2K-1n2k 于是 K-1log2nK 因为 K 是整数 所以 K=log2n+1,性质5 对一棵完全二叉树，n个结点自上而下，自左至右连续地从1开始编号，则对任一结点i(1in),有：,性质5有用,如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲结点数是i/
14、2。,如果2in，结点i无左孩子(此时结点i为叶子)；否则其左孩子是结点2i。,如果2i+1n,结点i无右孩子；否则其孩子是结点2i+1。,A,B,D,E,C,F,G,A,B,C,D,E,F,G,/,/,/,/,/,/,/,/,root,二叉树的链式存储,二叉树节点设计,public class TreeNode public char data;public TreeNode leftChild;public TreeNode rightChild;public TreeNode(char c)data=c;leftChild=null;rightChild=null;,节点类,C,/,/,
15、TreeNode n=new TreeNode(C);,n,定义：树的每个结点按某种规律恰好被访问一次的过程。,二叉树的编历,从二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，若能依次遍历这三部分，便是遍历了整个二叉树。,根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。太麻烦,限定对左右子树的访问次序：先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。,遍历后可以从非线性结构的二叉树得到各个结点的线性排列。先序遍历(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历(1)按中序遍历左子
16、树(2)处理根(3)按中序遍历右子树后序遍历(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根,A,B,D,E,F,G,C,H,I,遍历的例子,先序：ABDEHICFG,中序：DBHEIAFCG,后序：DHIEBFGCA,二叉树类设计,public class BiTree private TreeNode root;private string treeStr;/记录用于创建二叉树的字符串 private int i=0;/创建二叉树时，用变量i索引创建的字符串/创建二叉树时使用，用来引用treeStr串中的一个字符 private string result;/先、中、后遍历时，得到
17、的结果记录在这里 public BiTree()root=null;private void setTreeStr(string s)/设置用来构造二叉树的字符串 treeStr=s;this.i=0;,创建树时，需要提供字符串。,二叉树先序编历已知树根,void preOrder(TreeNode t)/递归先序遍历 if(t!=null)this.result+=+t.data;/先序遍历的结果，保存在类属性 result preOrder(t.leftChild);preOrder(t.rightChild);,public TreeNode getRoot()return this.r
18、oot;,从类外(窗体类)看二叉树类1 如何调用？2 如何获取结果？,无法操作树根！因为root是私有的,主窗体中：TreeNode tn=tree.getRoot();tree.preOrder(tn);,结果保存在result属性中，私有解决办法：为BiTree类中增加办法,二叉树先序编历存在的问题,每次调用 preOrder前，需要获得树根还需要将result变量初始化，否则下次遍历的结果就不对遍历结束后，还要记住去取结果。,灰常不方便,二叉树先序编历更好的办法,public string preOrder()/先序遍历 this.result=;/每次调用前，result初始化 pre
19、Order(this.root);/类内，直接用root return this.result;/返回遍历结果,利用OOP的重载,原来的定义void preOrder(TreeNode t),重载：同一个类中，方法名相同，形参和返回类型不一样,主窗体中：String ans=tree.preOrder();输出ans,重载的2方法一个private一个public,二叉树的创建-辅助工作,private TreeNode createThisTree()TreeNode t;char c;c=this.treeStr this.i+;/从字符串中取第i个字符，i是类中定义的变量，全局 if(c
20、=#)return(null);else t=new TreeNode(c);t.leftChild=createThisTree();t.rightChild=createThisTree();return(t);,public void createTree(string treeStr)/给定的字符串，创建二叉树 this.setTreeStr(treeStr);root=createThisTree();,还是用重载一个private一个public,/给定的字符串，以#代表树叶,主函数中的调用1 获得创建树字符串str2 tree.createTree(str);,创建二叉树,A,B
21、,C,AB#C#,A,B,AB#,A,C,A#C#,从遍历结果推导树,给出一棵二叉树的先序遍历结果和中序遍历结果，或者给出后序遍历结果和中序遍历结果，就可画出该二叉树；,只给出二叉树先序遍历结果和后序遍历结果，则无法画出该二叉树。,有两棵二叉树T1和T2，它们的先序和后序遍历结果完全相同。显然只凭先序和后序遍历结果无法确定到底是哪一棵二叉树。,先序为ABCDEFGHI 中序为BCAEDGHFI,根据遍历解结果推导树-例子,原则：根据先序定义：A必为根结点。根据中序定义：A前的结点为左子树 A后的结点为右子树。,A,B,E,F,C,D,I,G,H,查找,在数据结构中找出满足某种条件的数据元素,若
22、在数据结构中找到了这样的元素，则称查找成功否则称查找失败。,顺序查找法,从表的第一个元素开始，将给定的值与表中各元素的关键字逐个进行比较，一直到找到相等的关键字，则查找成功；否则就是表中没有要找的元素，查找失败。,顺序查找法,public int search(int keyValue)int i=0；while(datai!=keyValue,public int search(int keyValue)int i=0；for(;ithis.length;i+)if(datai=keyValue)return i;else return-1;,哪儿错了？,线性查找法,适用于有序线性表,二分查
23、找法,以顺序方式存放的有序表的查找可采用对半查找。,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,线性查找法,public int binSearch(char keyValue)int low,high,mid;/low,high,mid分别代表当前查找的表的下限、上限和中间位置 low=0;/初始化下限为数据的第一个元素的位置 high=length-1;/上限为最后一个元素的位置 while(low=high)mid=(low+high)
24、/2;/确定中间位置 if(datamid=keyValue)return(mid);if(datamid keyValue)low=mid+1;else high=mid-1;return(-1);,二分查找法代码,二叉排序树查找,二分查找法特别适合于从已排序的结点中寻找给定值。,若线性表中的结点需要经常插入和删除，最好设计成结合链表和二分法的查找方法。,二叉排序树定义,（1）左子树不空,则左子树上所有的关键字均小于它的根结点的关键字；,（2）右子树不空，则右子树上所有的关键字均大于或等于它的根结点的关键字；,（3）它的左、右子树也是二叉排序树。,92,69,21,89,93,99,97,7
25、8,91,二叉排序树-查找算法,在给定的二叉排序树t中查找给定待查关键字K：,1.如果树t为空，那么查找失败。算法结束；否则，转2。,2.如果t.data=K，则查找成功。算法结束。否则转3。,3.如果Kt.data，那么t=t.lchild，转（1）。否则 t=t.rchild，转（1）。,二叉排序查找,public TreeNode banSearch(double k)TreeNode p=this.root;while(p!=null),代码 重建二叉树,节点的数据类型改成double,92,69,21,89,93,99,97,78,91,k=100 查找返回的结果是什么？,二叉排序创
26、建,92,69,21,89,93,99,97,78,91,79,p,q,找啊找啊找位置，结束的条件是什么。,二叉排序创建,public void insBTree(double k)TreeNode p,q;q=new TreeNode(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;else p.leftChild=q;/*插入到左子树*/else if(p.rightChild!=null)p
27、=p.rightChild;else p.rightChild=q;/*插入到右子树*/end of while,二叉排序树类,public class BiSortTree private TreeNode root;public BiSortTree()root=null;public BiSortTree(TreeNode root)this.root=root;public void insBTree(double k)public TreeNode banSearch(double k),这2个方法的代码在前面,记得数据类型用double,选择排序-快速排序,基本思想：通过一趟分割将
28、线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；,对每一部分再进行分割，直到整个线性表有序为止。,快速排序-分割步骤,设置两个指针i和j，初态分别指向序列中第一个记录和最后一个记录。将第一个记录移向辅助变量x中，再从j所指位置起向前搜索第一个小于x的记录，找到后，将aj移至ai的位置；i+,从i所指向位置开始后搜索第一个关键字大于x的记录，找到后，将ai移至aj的位置；重复这两步过程，直至i=j，最后将x送至ai中去。至此一趟排序完成，序列划分为两个子文件。,数据举例,初始状态 43 33 28 17 52 63 3 26 X i j一次交换 26 33 28 17
29、52 63 3 26 i j二次交换 26 33 28 17 52 63 3 52 i j三次交换 26 33 28 17 3 63 3 52 i j四次交换 26 33 28 17 3 63 63 52 i j 26 33 28 17 3 43 63 52 i=j,数据举例,(a)一趟排序初始状态 45 21 34 19 52 60 34 24第一趟 24 21 34 19 34 45 60 52第二趟 19 21 24 34 34第三趟 19 21第四趟 34 34第五趟 52 60有序文件 19 21 24 34 34 45 52 60,一趟分割算法private void qkOne(
30、int start,int end,ref int mid)/start,end分别为起始位置，mid为最终的中间位置。int x,i,j;i=start;j=end;x=datai;/将第一个值保存在x中 while(i!=j)while(i=x)j-;/*右向左*/if(ij)/找到了 datai=dataj;/将dataj 移动到 datai中 i+;while(ij,后续分割,start,end,mid,start,end,mid,mid-1,mid+1,新end,end,mid+1,堆栈,继续分割这里,压栈等以后处理,利用堆栈实现快速排序算法,public void qkSort()
31、int start=0;int end=this.length-1;int mid=0;LinkedStack ls=new LinkedStack();/建立一个堆栈，使用了前面章节中定义的堆栈 ls.push(start);ls.push(end);while(!ls.isEmpty()end=ls.pop();/与压栈的次序相反，弹出位置 start=ls.pop();while(start end)qkone(start,end,ref mid);ls.push(mid+1);/将分割后的第二个序列压栈 ls.push(end);end=mid-1;调节位置，现在准备去对第一个序列分割，其位置是 start 到 mid-1,归并排序,采用二路归并技术，即每次将数组a中两个相邻的有序序列归并为一个有序序列。排序过程为：假设待排序文件含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1两两归并，得到n/2个长度为2或1的有序子序列再两两归并。直到得到一个长度为n的有序文件为止。,数据举例,初始状态 45 21 34 19 52 60 34 24 第一趟 21 45 19 34 52 60 24 34 第二趟 19 21 34 45 24 34 52 60 第三趟 19 21 24 34 34 45 52 60二路归并排序过程示例,
