数据结构笔记3

队列结构一、定义：队列结构是根据数据运算来分类的，也就是说队列结构具有特殊的运算规则。从数据的逻辑结构看，队列结构其实就是一种线性结构。从数据的存储结构进一步划分，队列结构包括两类：1）顺序队列结构即使用一组地址连续的内存单元依次保存队列中的数据。2）链式队列结构：即使用链表形式保存队列中各元素的值。典型的队列结构如图：从图中能够看出，在队列结构中允许对两端进行操作，但是两端操作不同。在队首只能进行删除操作，在队尾只能进行插入操作。若队列中没有元素，则称为空队列。从数据运算角度分析，队列结构是按照“先进先出”的原则处理结点数据的。二、日常应用队列结构在日常生活中有许多生动的例子。如，银行的排号系统。三、队列的基本操作在队列结构中，数据运算十分简单。一般队列的的基本操作只有两个。1）入队列将一个元素添加至队尾（在队尾排队等候）2）出队列将队首的元素取出，同时删除该元素，使后一个元素成为队首。除此之外还可以有初始化队列、获取队列长度等简单的操作。四、队列操作演示importjava.util.Scanner;/***定义数据部分*/classDATA4{Stringname;intage;}/***定义队列数组*/classSQType{staticfinalintQUEUELEN=15;//规定队列长度DATA4[]data=newDATA4[QUEUELEN];//实例化数据部分inthead;//队首inttail;//队尾//初始化队列SQTypeSQTypeInit(){SQTypeq;if((q=newSQType())!=null)//内存申请结果{q.head=0;//设置队首q.tail=0;//设置队尾returnq;}elsereturnnull;//申请失败}//判断队列空intSQTypeIsEmpty(SQTypeq){inttemp=0;if(q.head==q.tail)temp=1;//为空返回1return(temp);}//判断队列满intSQTypeIsFull(SQTypeq){inttemp=0;if(q.tail==QUEUELEN)temp=1;//队列满返回1return(temp);}//清空队列voidSQTypeClear(SQTypeq){q.head=0;q.tail=0;}//释放队列voidSQTypeFree(SQTypeq){q=null;}//入队列intInSQType(SQTypeq,DATA4data){if(q.tail==QUEUELEN){System.out.println(队列满);return0;}else{q.data[q.tail++]=data;//元素入队列return1;}}//出队列DATA4OutSQType(SQTypeq){if(q.head==q.tail){System.out.println(队列空);System.exit(0);//报错}else{returnq.data[q.head++];//出队列，头向后移1（数组下标自增）}returnnull;}//读结点数据DATA4PeekSQType(SQTypeq){if(SQTypeIsEmpty(q)==1){System.out.println(队列空);returnnull;}else{returnq.data[q.head++];}}//队列长度intSQTypeLen(SQTypeq){inttemp;temp=q.tail-q.head;returntemp;}}/***队列操作演示*/publicclassP2_4{publicstaticvoidmain(String[]args){SQTypest=newSQType();//实例化队列数据DATA4data1;Scannersc=newScanner(System.in);SQTypestack=st.SQTypeInit();//初始化队列System.out.println(--初始化队列结束--);System.out.println(--入队列操作\t输入姓名\t年龄（全0退出）：);while(true){DATA4d=newDATA4();//实例化数据部分d.name=sc.next();d.age=sc.nextInt();if(d.age==0)break;elsest.InSQType(stack,d);}System.out.println(--入队列结束);System.out.println(队列全长+st.SQTypeLen(stack));System.out.println(--统计队列长结束);inttemp=1;System.out.println(--出队列操作，按0结束);temp=sc.nextInt();while(temp!=0){data1=st.OutSQType(stack);System.out.printf(出队列的数据是：(%s,%d)\n,data1.name,data1.age);temp=sc.nextInt();}System.out.println(--出队列结束);st.SQTypeFree(stack);System.out.println(--释放队列结束演示完毕);}}注意：这里需要对比day02中的栈，出栈结果和出队列结果比较，找出不同。第三章树序前面介绍的集几种数据结构都属于线性结构，但有些问题无法抽象为线性数据结构，例如家谱等。这种可以表示成一种层次关系的问题可以抽象为树结构。一、什么是树结构树结构是一种描述非线性关系的数据结构，其中重要的是树的概念。如图，树是n个数据节点的集合，在该集合中包含一个根节点，根节点之下分布有互不交叉的子集合这些子集合是根节点的子树。树结构的基本特征：1）在一个树结构中，有且仅有一个结点没有直接前驱，这个节点就是树的根节点。2）除根节点外，其余每个结点有且仅有一个直接前驱；3）每个节点可以有任意多个直接后继；如图：A为树的根节点，有三个直接后继结点B、C、D；结点C只有一个前驱结点A。此外，树结构可以为空，空树中没有数据结点，为空集合；如果树结构中仅包含一个结点，那么树根便是它本身。从定义可以看出，属有层次结构限制。从数学角度，树具有递归特性，树中每个结点及其之后的所有结点构成一个子树，这个子树也拥有根结点。如，图中I与N、M构成子树，I为子树的根结点。二、树的基本概念1）父结点和子结点：每个结点的子树的根称为该结点的子结点，相应的，该结点称为其子结点的父结点；2）兄弟结点：具有同一个父结点的结点；3）结点的度：一个结点所包含子树的数量；4）叶结点：树中度为0的结点称为叶结点或终端结点；5）分支结点：树中度不为0的结点称为分支结点或非终端结点；6）结点的层数：结点的层数从树根开始计算，根节点为第1层、依次向下……第n层；7）树的深度：树中结点的最大层数；8）有序树：若树中各结点的子树（兄弟结点）是按照一定次序从左向右排列的，称为有序树；9）无序树：若树中各节点的子树（兄弟结点）未按照一定次序排列，称为无序树；10）森林：n（n0）棵互不相交的树的集合。具体分析：如图，为一个基本的树结构。A为根结点，有三个子树，度为3。E有两个子树，度为2。结点中A的度最大，为3，故整个树的度为3。E为L、K的父结点。K、L为E的子结点。K、L为兄弟结点。整个树中，G、H、K、J、N、O、P、Q均为叶结点。其余为分支结点。整个树的深度为5去除根结点，留下的子树构成森林。三、树的表示树结构不是线性结构，所以很难以数学式子来表示，这就需要用全新的方法表示树。我们采用层次括号法，基本规则如下：1）根结点放入一对圆括号中；2）根结点的子树由左至右放入括号中；3）对子树重复上一步骤。这样，同层子树与其根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。按照这种方法，如图所示的树结构可以表示成如下形式：（A(D(I(N,M)),(H)),(C(G(L,K)),(F(J))),(B(E))）四、二叉树操作演示importjava.util.Scanner;/***定义二叉树结点类型*/classCBTType{Stringdata;//数据CBTTypeleft;//左子树CBTTyperight;//右子树}/***二叉树操作*/publicclassP2_5{staticfinalintMAXLEN=20;//最大长度staticScannersc=newScanner(System.in);//初始化结点CBTTypeInitTree(){CBTTypenode;if((node=newCBTType())!=null)//申请内存{System.out.println(输入结点数据);node.data=sc.next();node.left=null;node.right=null;if(node!=null)//结点不为空{returnnode;}elsereturnnull;}returnnull;}//查找结点CBTTypeTreeFindNode(CBTTypetreeNode,Stringdata){CBTTypeptr;//缓存if(treeNode==null)//若树根结点为空{returnnull;}else{if(treeNode.data.equals(data))//当前结点为查找结点{returntreeNode;//返回当前节点}else{if((ptr=TreeFindNode(treeNode.left,data))!=null)//左子树不为空returnptr;//返回左子树结点elseif((ptr=TreeFindNode(treeNode.right,data))!=null)//右子树不为空returnptr;//返回右子树结点elsereturnnull;}}}//添加结点voidAddTreeNode(CBTTypetreeNode){CBTTypepnode,parent;//定义输入结点与父结点Stringdata;//定义数据intmenusel=1;//标志位置1if((pnode=newCBTType())!=null)//分配内存成功{System.out.println(输入二叉树结点数据);pnode.data=sc.next();pnode.left=null;pnode.right=null;System.out.println(输入父结点数据);data=sc.next();parent=TreeFindNode(treeNode,data);//找父结点if(parent==null){System.out.println(未找到父结点);pnode=null;return;}System.out.println(1.添加结点到左子树\n2.添加结点到右子树);while(menusel==1||menusel==2){menusel=sc.nextInt();if(parent==null){System.out.println(不存在父结点，先设置父结点);break;}else{switch(menusel)//更改父结点中左右子树的值{case1:if(parent.left!=null)System.out.println(左子树结点不为空);elseparent.left=pnode;break;case2:if(parent.right!=null)System.out.println(右子树结点不为空);elseparent.right=pnode;break;default:System.out.println(参数无效);}break;}}}}//获取右子树CBTTypeTreeRightNode(CBTTypetreeNode){if(treeNode!=null)returntr