搜索
数据结构第二章数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。数据项：是数据的最小单位。一组数据元素具有某种结构形式。基本概念数据结构定义•数据结构：数据结构描述了一组性质相同的数据元素及元素间的相互关系。数据结构概念的三个方面数据元素之间的逻辑关系数据元素在计算机中的存储方式在这些数据元素上定义的运算的集合数据的逻辑结构数据的逻辑结构有时可直接称为数据结构。数据的逻辑结构的三种基本类型：线性表、树和图。逻辑结构分类两大类：(一)线性结构（线性表）数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。线性表是典型的线性结构，它的数据元素只按先后次序联接。有顺序表、链表、堆栈、队列等。(二）非线性结构（树，图）不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。定义：数据的逻辑结构在计算机存储设备中的映象称为数据的存储结构(亦称为物理结构)。同一个逻辑结构可以有不同的存储结构。最常用的二种方式是：顺序存储结构链式存储结构。大多数据结构的存储表示都采用其中的一种方式或两种方式的结合。物理结构数据元素按某种顺序存放在存储器的连续存储单元中。将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，而数据元素之间的关系由存储单元的邻接关系唯一确定。例如数组就是这种存储方式主要特点：1.结点中只有自身信息域，没有连接信息域。因此存储密度大，存储空间利用率高；2.可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；3.插入、删除运算会引起大量结点的移动；4.要求存储在一片连续的地址中。这种存储方式主要用于线性的数据结构。顺序存储结构存储数据结构的存储空间可以不连续，数据元素之间的关系由指针来确定。主要特点是：1.结点由两类域组成：数据域和指针域。2.逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。3.插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。链式存储结构线性表的存储结构存储结构:顺序存储结构和链接存储结构。具有顺序存储结构的线性表称为顺序表用一组地址连续的存储单元依次存储线性表中的每个数据元素。具有链接存储结构的线性表称为线性链表。用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。顺序表类设计—分析对象的属性：自己现有的数据：存放在一个数组中现有数据的个数：长度能存放多少数据：容量动作(Method)构造方法：传递表的容量，创建一个空表，长度=0，插入：新数据插入后，数据还是有序的，长度增1增加：在表的尾部增加一个数据，长度增1查找：根据键值，找到数据在表中的位置，并返回，找不到，返回-1更新：用指定的值更新表中指定位置的元素的值排序：将表中元素按从小到大排序。获得某位置元素的值：获得线性表的长度定义顺序表的类—编写文件ArrayList.cs属性定义及构造函数publicclassArrayList{int[]data;//存放线性表的数据元素,注意一维数组的定义intvolume;//线性表的容量intlength;//当前线性表的长度publicArrayList(intn)//构造方法{this.data=newint[n];//动态定义一个可以存放n个元素的数组this.volume=n;//线性表的最大容量this.length=0;//新生成的线性表中，有效的数据元素个数为0}}复习原来的作业单链表一链表的基本组成元素publicclassNode//定义节点类{publicintdata;publicNodenext;publicNode(inti){data=i;next=null;}}单链表二链表整体publicclassLinkedList//定义链表类{privateNodehead;//头指针privateNodetail;//尾指针privateNodecurrent;//遍历链表时的当前指针//-----------------------------------------------------------------------------------publicLinkedList(){head=null;tail=null;}}单链表三追加节点publicvoidaddNode(intvalue)//向链表尾部增加一个节点{NodenewNode=newNode(value);if(isEmpty()){head=newNode;tail=newNode;}else{tail.next=newNode;tail=newNode;}}publicboolisEmpty(){//链表是否为空returnhead==null;}单链表四链表的遍历辅助函数publicvoidgotoHead(){//指向链表的表头current=head;}publicintgetValue(){//获得指向的节点的数据returncurrent.data;}publicvoidnext(){//移动到下一个节点current=current.next;}publicboolisEnd(){//是否走到链表的尾部returncurrent==null;}限定在一端进行插入与删除的线性表。允许增加和删除的一端称为栈顶，不允许增加和删除的一端称为栈底。给定栈(a0,a1,…,an-1）称a0为栈底元素，an-1为栈顶元素。特点后进先出(LIFOLastInFirstOut)或先进后出（FILO)的表。堆栈用数组依次存放自栈底到栈顶的数据元素设指针top指示栈顶元素的位置。用Volume表示栈的容量用一维数组s[volume]表示栈，指针top指向栈顶元素.s[0]为最早进入栈的元素，s[top]为最迟进入栈的元素。当top=volume-1时，为满栈.初始化top=-1注：top,max为全局变量顺序存储的栈顺序堆栈设计publicclassArrayStack{privateint[]stack;//存放进栈数据的数组privateintvolume;//栈的容量privateinttop;//栈顶指针publicArrayStack(intn){具体实现}//构造函数publicboolpush(intvalue){具体实现}//进栈,如果进栈成功，则返回truepublicintpop(){具体实现}publicboolisEmpty(){具体实现}判断栈是否为空}栈操作publicArrayStack(intn){this.volume=n;top=-1;stack=newint[n];}构造函数栈操作publicboolpush(intvalue)//进栈{if(top==volume-1)returnfalse;elsestack[++top]=value;returntrue;}publicintpop()//出栈{if(isEmpty())return-1;/*下溢*/elsereturnstack[top--];}publicboolisEmpty()//判断栈是否为空{returntop==-1;}进栈出栈链式堆栈作业关键点找作业复习只需一个属性，它就是栈顶指针top基本元素与链表中的一个节点一样，参见Node类定义栈初始化时，让top指针为null实现其push，pop和isEmpty方法主程序保持顺序存储堆栈的界面和功能队列（Queue）是操作受限的线性表队列是先进先出(FIFO)的线性表.(a1,a2,…,an)允许在表的一端进行插入，在另一端删除，允许插入的一端叫做队尾（tail），允许删除的一端则称队头（head）。称这样队列为“单向队”。队列与链表很相似①出列，booloutQueue(refintx)//ref关键字为把x的值返回给调用函数②入列，voidinQueue(intx)③判断队列是否为空，boolisEmpty()队列操作①出列，booloutQueue(refintx)//ref关键字为把x的值返回给调用函数②入列，voidinQueue(intx)③判断队列是否为空，boolisEmpty()链式队列链式队列设计publicclassQueue{privateNodehead;//Node类的定义与链表中的一样，以前已经定义privateNodetail;publicQueue()//类的构造函数{head=tail=null;}publicboolisEmpty(){returnhead==null;}}采用链式存储结构的队列称为链队列。一个链队列需要队头和队尾的两个指针才能唯一确定。headtail链式队列设计publicvoidinQueue(intvalue)//向队列中增加一个元素{Nodetemp=newNode(value);if(isEmpty()){head=tail=temp}else{tail.next=temp;tail=temp;}}入列链式队列设计booloutQueue(refintx)//结果保存在x中，ref关键字使得调用程序可以获得x的值{if(isEmpty()){returnfalse;}else{x=head.data;head=head.next;}}出列二叉树•定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。•二叉树不是树的特殊情况。二叉树的结点子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。ABDECFGABCDEFG////////T二叉树的链式存储二叉树节点设计publicclassTreeNode{privatechardata;privateTreeNodeleftChild;privateTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}节点类二叉树的遍历，是指树的每个结点按某种规律恰好被访问一次的过程。若对左右子树的访问次序限定是先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。二叉树的编历遍历后可以从非线性结构的二叉树得到各个结点的线性排列。先序遍历(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历(1)按中序遍历左子树(2)处理根(3)按中序遍历右子树后序遍历(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根ABDEFGCHI遍历的例子二叉树类设计publicclassBiTree{privateTreeNoderoot;privatestringtreeStr;//记录用于创建二叉树的字符串privateinti=0;//创建二叉树时，用变量i索引字符//创建二叉树时使用，用来引用treeStr串中的一个字符privatestringretult;//先、中、后遍历时，得到的结果记录在这里publicBiTree(){root=null;}privatevoidsetTreeStr(strings)//设置用来构造二叉树的字符串{treeStr=s;this.i=0;}}二叉树先序编历privatevoidpreOrder(TreeNodet)//递归先序遍历{if(t!=null){this.retult+=“”+t.data;//先序遍历的结果，保存在类属性result中preOrder(t.leftChild);preOrder(t.rightChild);}}publicstringpreOrder()//先序遍历{retult=;//为避免多次调用导致结果错误，每次调用前，resu