数据结构笔记

1、队列结构一、定义：队列结构是根据数据运算来分类的，也就是说队列结构具有特殊的运算规则。从数据的逻辑结构看，队列结构其实就是一种线性结构。从数据的存储结构进一步划分，队列结构包括两类：1）顺序队列结构即使用一组地址连续的内存单元依次保存队列中的数据。2）链式队列结构：即使用链表形式保存队列中各元素的值。典型的队列结构如图：从图中能够看出，在队列结构中允许对两端进行操作，但是两端操作不同。在队首只能进行删除操作，在队尾只能进行插入操作。若队列中没有元素，则称为空队列。从数据运算角度分析，队列结构是按照“先进先出”的原则处理结点数据的。二、日常应用队列结构在日常生活中有许多生动的例子。如，银行的排号

2、系统。三、队列的基本操作在队列结构中，数据运算十分简单。一般队列的的基本操作只有两个。1）入队列将一个元素添加至队尾（在队尾排队等候）2）出队列将队首的元素取出，同时删除该元素，使后一个元素成为队首。除此之外还可以有初始化队列、获取队列长度等简单的操作。四、队列操作演示import java.util.Scanner;/* *定义数据部分*/class DATA4String name;int age;/* *定义队列数组*/class SQTypestatic final int QUEUELEN=15; /规定队列长度DATA4 data=new DATA4QUEUELEN;/实例化数据部

3、分int head;/队首int tail;/队尾/初始化队列SQType SQTypeInit()SQType q;if(q=new SQType()!=null)/内存申请结果q.head=0;/设置队首q.tail=0;/设置队尾return q;elsereturn null;/申请失败/判断队列空int SQTypeIsEmpty(SQType q)int temp=0;if(q.head=q.tail)temp=1;/为空返回1return (temp);/判断队列满int SQTypeIsFull(SQType q)int temp=0;if(q.tail=QUEUELEN)te

4、mp=1;/队列满返回1return (temp);/清空队列void SQTypeClear(SQType q)q.head=0;q.tail=0;/释放队列void SQTypeFree(SQType q)q=null;/入队列int InSQType(SQType q,DATA4 data)if(q.tail=QUEUELEN)System.out.println(队列满);return 0;elseq.dataq.tail+=data;/元素入队列return 1;/出队列DATA4 OutSQType(SQType q)if(q.head=q.tail)System.out.prin

5、tln(队列空);System.exit(0);/报错elsereturn q.dataq.head+;/出队列，头向后移1（数组下标自增）return null;/读结点数据DATA4 PeekSQType(SQType q)if(SQTypeIsEmpty(q)=1)System.out.println(队列空);return null;elsereturn q.dataq.head+;/队列长度int SQTypeLen(SQType q)int temp;temp=q.tail-q.head;return temp;/* *队列操作演示*/public class P2_4 publi

6、c static void main(String args) SQType st=new SQType();/实例化队列数据DATA4 data1;Scanner sc=new Scanner(System.in);SQType stack=st.SQTypeInit();/初始化队列System.out.println(-初始化队列结束-);System.out.println(-入队列操作t输入姓名t年龄（全0退出）：);while(true)DATA4 d=new DATA4();/实例化数据部分=sc.next();d.age=sc.nextInt();if(d.age=

7、0)break;elsest.InSQType(stack, d);System.out.println(-入队列结束);System.out.println(队列全长+st.SQTypeLen(stack);System.out.println(-统计队列长结束);int temp=1;System.out.println(-出队列操作，按0结束);temp=sc.nextInt();while(temp!=0)data1=st.OutSQType(stack);System.out.printf(出队列的数据是：(%s,%d)n, ,data1.age);temp=sc

8、.nextInt();System.out.println(-出队列结束);st.SQTypeFree(stack);System.out.println(-释放队列结束 演示完毕);注意：这里需要对比day02中的栈，出栈结果和出队列结果比较，找出不同。第三章 树序前面介绍的集几种数据结构都属于线性结构，但有些问题无法抽象为线性数据结构，例如家谱等。这种可以表示成一种层次关系的问题可以抽象为树结构。一、什么是树结构树结构是一种描述非线性关系的数据结构，其中重要的是树的概念。如图，树是n个数据节点的集合，在该集合中包含一个根节点，根节点之下分布有互不交叉的子集合这些子集合是根节点的子树。树结构

9、的基本特征：1）在一个树结构中，有且仅有一个结点没有直接前驱，这个节点就是树的根节点。2）除根节点外，其余每个结点有且仅有一个直接前驱；3）每个节点可以有任意多个直接后继；如图：A为树的根节点，有三个直接后继结点B、C、D；结点C只有一个前驱结点A。此外，树结构可以为空，空树中没有数据结点，为空集合；如果树结构中仅包含一个结点，那么树根便是它本身。从定义可以看出，属有层次结构限制。从数学角度，树具有递归特性，树中每个结点及其之后的所有结点构成一个子树，这个子树也拥有根结点。如，图中I与N、M构成子树，I为子树的根结点。二、树的基本概念1）父结点和子结点：每个结点的子树的根称为该结点的子结点，相

10、应的，该结点称为其子结点的父结点；2）兄弟结点：具有同一个父结点的结点；3）结点的度：一个结点所包含子树的数量；4）叶结点：树中度为0的结点称为叶结点或终端结点；5）分支结点：树中度不为0的结点称为分支结点或非终端结点；6）结点的层数：结点的层数从树根开始计算，根节点为第1层、依次向下第n层；7）树的深度：树中结点的最大层数；8）有序树：若树中各结点的子树（兄弟结点）是按照一定次序从左向右排列的，称为有序树；9）无序树：若树中各节点的子树（兄弟结点）未按照一定次序排列，称为无序树；10）森林：n（n0）棵互不相交的树的集合。具体分析：如图，为一个基本的树结构。A为根结点，有三个子树，度为3。E

11、有两个子树，度为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)

12、,(H),(C(G(L,K),(F(J),(B(E)）四、二叉树操作演示import java.util.Scanner;/* * 定义二叉树结点类型*/class CBTTypeString data;/数据CBTType left;/左子树CBTType right;/右子树/* * 二叉树操作*/public class P2_5static final int MAXLEN=20;/最大长度static Scanner sc=new Scanner(System.in);/初始化结点CBTType InitTree()CBTType node;if(node=new CBTType()

13、!=null)/申请内存System.out.println(输入结点数据);node.data=sc.next();node.left=null;node.right=null;if(node!=null)/结点不为空return node;elsereturn null;return null;/查找结点CBTType TreeFindNode(CBTType treeNode,String data)CBTType ptr;/缓存if(treeNode=null)/若树根结点为空return null;elseif(treeNode.data.equals(data)/当前结点为查找结点

14、return treeNode;/返回当前节点elseif(ptr=TreeFindNode(treeNode.left,data)!=null)/左子树不为空return ptr;/返回左子树结点else if(ptr=TreeFindNode(treeNode.right,data)!=null)/右子树不为空return ptr;/返回右子树结点elsereturn null;/添加结点void AddTreeNode(CBTType treeNode)CBTType pnode,parent;/定义输入结点与父结点String data;/定义数据int menusel=1;/标志位置

15、1if(pnode=new CBTType()!=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.添加结点

16、到右子树);while(menusel=1|menusel=2)menusel=sc.nextInt();if(parent=null)System.out.println(不存在父结点，先设置父结点);break;elseswitch(menusel)/更改父结点中左右子树的值case 1:if(parent.left!=null)System.out.println(左子树结点不为空);elseparent.left=pnode;break;case 2:if(parent.right!=null)System.out.println(右子树结点不为空);elseparent.right=

17、pnode;break;default:System.out.println(参数无效);break;/获取右子树CBTType TreeRightNode(CBTType treeNode)if(treeNode!=null)return treeNode.right;elsereturn null;/获取左子树CBTType TreeLeftNode(CBTType treeNode)if(treeNode!=null)return treeNode.left;elsereturn null;/判断空树int TreeIsEmpty(CBTType treeNode)if(treeNode

18、!=null)return 0;elsereturn 1;/计算二叉树深度int TreeDepth(CBTType treeNode)/递归，计算二叉树的最大层数int depleft,depright;if(treeNode=null)return 0;elsedepleft=TreeDepth(treeNode.left);/左子树深度depright=TreeDepth(treeNode.right);/右子树深度if(depleftdepright)return depleft+1;elsereturn depright+1;/清空二叉树void ClearTree(CBTType

19、treeNode)if(treeNode!=null)ClearTree(treeNode.left);ClearTree(treeNode.right);treeNode=null;/显示结点数据void TreeNodeData(CBTType p)System.out.printf(%s,p.data);/*按层遍历 * 将每层结点进入队列，逐层遍历*/void LevelTree(CBTType treeNode)CBTType p;CBTType q=new CBTTypeMAXLEN;/定义顺序栈int head=0,tail=0;if(treeNode!=null)/根节点不为空

20、tail=(tail+1)%MAXLEN;/队尾序号qtail=treeNode;/二叉树结点入队列while(head!=tail)head=(head+1)%MAXLEN;p=qhead;TreeNodeData(p);if(p.left!=null)tail=(tail+1)%MAXLEN;qtail=p.left;if(p.right!=null)tail=(tail+1)%MAXLEN;qtail=p.right;/先序遍历void DLRTree(CBTType treeNode)if(treeNode!=null)TreeNodeData(treeNode);DLRTree(tr

21、eeNode.left);DLRTree(treeNode.right);/中序遍历void LDRTree(CBTType treeNode)if(treeNode!=null)LDRTree(treeNode.left);TreeNodeData(treeNode);LDRTree(treeNode.right);/后序遍历void LRDTree(CBTType treeNode)if(treeNode!=null)LRDTree(treeNode.left);LRDTree(treeNode.right);TreeNodeData(treeNode);/二叉树操作演示public static void main(String args) CBTType root=null;int menusel=1;P2_5 t=new P2_5();root=t.InitTree();while(menusel!=0)System.out.println(选择菜