C#数据结构.pptx
l 数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。数据结构基本概念l数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。l 数据项：是数据的最小单位。l 一组数据元素具有某种结构形式。对象对象的属性数据结构定义 数据结构： 描述了一组性质相同的数据元素及元素间的相互关系。都是学生D:一帮学生R:按学号排序数据结构概念的三要素定义p 数据元素之间的逻辑关系p 数据元素在计算机中的存储方式p 在这些数据元素上定义的运算的集合数据结构的基本分类两大类： (一)线性结构（线性表）线性结构（线性表） 数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。 线性表是典型的线性结构，它的数据元素只按先后次序联接。 表、栈、队列、字串、数组和文件等方式。(二）非线性结构（树，图）非线性结构（树，图） 不满足线性结构特点的数据结构称为非线性结构。 树、图等是非线性结构。 树中的数据元素是分层次的纵向联接。 图中的数据元素则有各种各样复杂联接。 其它种类的数据结构由这三种基本结构派生的。数据存储结构的基本方式最常用的二种方式是：p顺序存储结构顺序存储结构p链式存储结构链式存储结构。p 数据元素按某种顺序存放在存储器的连续存储单元中。p 逻辑相邻，物理上相邻，数据元素之间的关系由存储单元的邻接关系唯一确定。例如 数组就是这种存储方式顺序存储结构 学生名单(逻辑结构) 顺序物理结构(数组student)071230李俊student0071230李俊073181章明student1073181章明081293向民student2081293向民091281肖进student3091281肖进顺序存储结构特点结点中只有自身信息域，没有连接信息域。存储密度大，存储空间利用率高；可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；插入、删除运算会引起大量结点的移动；要求存储在一片连续的地址中。这种存储方式主要用于线性的数据结构。p存储数据结构的内存空间可以不连续， 数据元素之间的关系由指针来确定。链式存储结构主要特点是：结点由两类域组成：数据域和指针域。链式存储结构特点逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。特点：表中的每个元素呈线性关系，除第一个外，都有一个直接前趋(predecessor)，除最后一个元素外，都仅有一个后继(successor)。线性表线性表最简单，最常用的数据结构线性表的逻辑结构线性表的逻辑结构 线性表L用符号表示为：L=(a1，a2，a3，. ai.，an)线性表的存储结构l 存储结构:顺序存储结构和链接存储结构。l 具有顺序存储结构的线性表称为顺序表 用数组储线性表中的每个数据元素。l 具有链接存储结构的线性表称为线性链表。 用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。 常用的链表有单链表、循环链表和双向链表。顺序表类设计分析对象的属性： 自己现有的数据：存放在一个数组中 现有数据的个数：长度 能存放多少数据：容量动作(Method) 构造方法：传递表的容量，创建一个空表，有效长度=0 插入：新数据插入后，数据还是有序的，长度增1 增加：在表的尾部增加一个数据，长度增1 查找：根据键值，找到数据在表中的位置，并返回，找不到返回-1 更新：用指定的值更新表中指定位置的元素的值 排序：将表中元素按从小到大排序。 获得某位置元素的值： 获得线性表的长度类型 dataint lengthInt volume?能为每个方法作定义吗？名字，形参表，返回类型确定表中的元素public class Student public string no,name; public double math,eng,computer; public Student() . ?这个类有点怪，属性都是public没其他方法这种类称为数据类去重 返回类型问题 是重新生成一个？还是直接删除应该是：应该是：ArrayList应该是：重新生成一个应该是：重新生成一个 不破坏原来的数据不破坏原来的数据去重的思维 你是怎么思维的？扩展思维数据不断添加，顺数据不断添加，顺序表满了后，能否序表满了后，能否自动长大？自动长大？原来变更后，原来的2倍StudentdataStudenttemplength?volume?for() tempi = datai单链表线性表的另一种存储方式一一 链表的基本组成元素链表的基本组成元素由表头指针决定由表头指针决定通过移动指针遍历链表，遇到通过移动指针遍历链表，遇到null结束结束组成要素：组成要素：节点，节点中包含数据节点，节点中包含数据链表的属性定义：链表的属性定义：null单链表一 链表的基本组成元素节点public class Node / 定义节点类定义节点类 public int data; public Node next; public Node(int i) data = i; next = null; 链表的逆转先生成一个空新链表先生成一个空新链表 遍历原链表遍历原链表每取一个节点，向新表的表头插入新节点每取一个节点，向新表的表头插入新节点直到原表遍历结束直到原表遍历结束去重的原理 生成一个新链表 遍历原表，每取一个节点，判断它在新表中是否存在，如果重复就不加。 直到原表结束限定在一端进行插入与删除的线性表。允许操作的一端称为栈顶，而不允许操作的一端为栈底。 给定 栈 (a1, ,an-1 ） 称a1为栈底元素， an为栈顶元素。特点 后进先出(LIFO Last In First Out)或先进后出（FILO)的线性表。v元素的插入称为进栈，v元素的删除称为出栈。堆栈及逻辑结构堆栈及逻辑结构属性 栈顶指针 栈的容量栈的属性和方法栈的属性和方法方法 出栈：栈顶元素出栈，指针下移 进栈：新元素放栈顶，指针上移 判断栈空 用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素顺序存储的栈顺序存储的栈 指针top指示栈顶元素的位置。 用Volume表示栈的容量 用一维数组stackvolume表示栈，指针top 指向栈顶元素. stack0为最早进入栈的元素，stacktop为最迟进入栈的元素。当top=volume-1时，为满栈. 初始化 top=-1 数据元素和栈顶指针之间的对应关系数据元素和栈顶指针之间的对应关系链式存储的栈关键点p 只需一个属性，它就是栈顶指针topp 基本元素与链表中的一个节点一样，参见Node类定义p 栈初始化时，让top指针为null p 实现其push，pop和isEmpty 方法p 主程序保持顺序存储堆栈的界面和功能压栈过程19top2810node将新给定值形成节点将新节点连接到栈顶弹出top2810保存栈顶值，栈顶指针指向下一个节点返回栈顶值l 队列（Queue）操作受限的线性表l 先进先出(FIFO)的线性表. (a1,a2, ,an )l 允许在表的一端插入，在表的另一端删除，插入的一端叫队尾（rear），删除的一端称队头（front）。队列顺序存储队列何时满何时满顺序队列的属性 头、尾、存储数据的数组。 构造函数：设置头、尾，都是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方法的方法的链表就是队列链表就是队列增加一个出列的方增加一个出列的方法法 采用链式存储结构的队列称为链队列。 一个链队列需要队头和队尾的两个指针才能唯一确定。headtail二叉树定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。二叉树不是树的特殊情况。 二叉树的结点子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。满二叉树：深度为K，有2K-1个结点的二叉树称为满二叉树。每一层上的结点数都是该层上的最大结点数。特殊的二叉树特殊的二叉树完全二叉树： 树高为k，除第 k 层外，其它各层 (1k-1) 的结点数都达到最大个数，第 k 层从右向左连续缺若干结点，这就是完全二叉树 如果对一棵高为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中总的分支数目。因为除根结点外，其余结点都有一个分支进入，所以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-1log2n1，则其双亲结点数是i/2。q 如果2in，结点i无左孩子(此时结点i为叶子)；否则其左孩子是结点2i。q 如果2i+1n,结点i无右孩子；否则其孩子是结点2i+1。ABDECFGABCDEFG/root二叉树的链式存储二叉树节点设计public class TreeNode public char data; public TreeNode leftChild; public TreeNode rightChild; public TreeNode(char c) data = c; leftChild = null; rightChild = null; 节点类C/TreeNode n = new TreeNode(C);nq 定义：树的每个结点按某种规律恰好被访问一次的过程。二叉树的编历q 从二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，若能依次遍历这三部分，便是遍历了整个二叉树。q 根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。太麻烦q 限定对左右子树的访问次序：先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。遍历后可以从非线性结构的二叉树得到各个结点的线性排列。先序遍历(1)处理根 (2)按先序遍历左子树 (3)按先序遍历右子树中序遍历(1)按中序遍历左子树 (2)处理根 (3)按中序遍历右子树后序遍历(1)按后序遍历左子树 (2)按后序遍历右子树 (3)处理根 ABDEFGCHI遍历的例子先序：ABDEHICFG中序：DBHEIAFCG后序：DHIEBFGCA二叉树类设计public class BiTree private TreeNode root; private string treeStr; / 记录用于创建二叉树的字符串 private int i = 0; / 创建二叉树时，用变量i索引创建的字符串 / 创建二叉树时使用，用来引用treeStr串中的一个字符 private string res
