双向链表的创建和操作的实现树的创建和相关操作的实现-软件工程课程设计说明书.doc

xx建筑大学计算机科学与技术学院课程设计说明书题 目： 双向链表的创建和操作的实现树的创建和相关操作的实现课 程： 数据结构与算法分析院 （部）： 计算机学院专 业： 软件工程班 级： 软件133学生姓名： xx学 号： 指导教师： xx完成日期： 2015-1-8xx建筑大学计算机学院课程设计说明书目 录课程设计任务书一2课程设计任务书二3双向循环链表的创建及相关操作的实现4一、 问题描述4二、数据结构5三、逻辑设计5四、编码6五、测试数据11六、测试情况12树的创建及相关操作的实现13一、问题描述13三、逻辑设计15四、编码15五、测试数据18六、测试情况18结 论19参考文献19课程设计指导教师评语20- I -xxx建筑大学计算机学院课程设计说明书xx建筑大学计算机科学与技术学院课程设计任务书一设计题目双向循环链表操作的实现已知技术参数和设计要求1、 建立一个空表。2、 插入第i个结点。3、 删除第i个结点。4、 插入第1个结点。5、 插入最后一个结点。6、 就地逆置设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排2014年12月29日-31日，确定方法思路2015年1月1日-6日，编写代码，运行测试2015年1月7日-8日，设计报告和幻灯片设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%xx建筑大学计算机科学与技术学院课程设计任务书二设计题目二叉树和树操作的实现已知技术参数和设计要求一、二叉树：利用带空的先序遍历结果或不带空的先序和中序遍历结果建立二叉树后，完成以下操作：1、 实现二叉树的层次遍历；2、 统计二叉树叶子结点的个数（递归）；3、 将二叉树左右子树相互交换（递归）；4、 判断所给定的二叉树是不是完全二叉树，如果是，将存储结构转换为顺序存储；5、 若是完全二叉树，将其转换为顺序存储后，判断是不是堆，若不是，将其调整为堆，并输出结果检查调整后的结果是否正确；6、 实现哈夫曼算法；7、 判断二叉树是不是二叉查找树。二、 树1、 分别使用双亲表示法、孩子链表、孩子-兄弟表示法建立树，并输出任一种遍历序列检查所建树的正确性；2、 使用孩子-兄弟表示法作为存储结构，实现树的先根、后根遍历和层次遍历；3、 使用孩子-兄弟表示法作为存储结构，统计树中叶子结点的个数；4、 使用双亲表示法作为存储结构，统计树的深度本设计完成的是一、树的1、2、3小题设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排2014年12月29日-31日，确定方法思路2015年1月1日-6日，编写代码，运行测试2015年1月7日-8日，设计报告和幻灯片设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%双向循环链表的创建及相关操作的实现1、 问题描述双向循环链表的逻辑形态插入操作 删除操作二、数据结构class NodeAnyType data;Node prev;Node next;public Node()public Node(AnyType data)this.data=data;this.prev=null;this.next=null;public Node(AnyType data,Node p,Node q)this.data=data; this.prev=p; this.next=q;三、逻辑设计1、总体思路先找出有用的数据存储结构 - 编写相关方法 - 完成对数据 的操作2、模块划分maingetaddremovegetNodeaddBefore3、函数或类的具体定义和功能 public MyLinkedList()remove(int idx)/删除 public Node getNode(int pos)/得到某一位置的节点 public boolean add(AnyType data)/添加public void nizhi()/逆置public void print(MyLinkedList dl)/打印public static void main(String args)/主方法 class Node/节点类AnyType data;Node prev;Node next;public Node()public Node(AnyType data)this.data=data;this.prev=null;this.next=null;public Node(AnyType data,Node p,Node q)this.data=data; this.prev=p; this.next=q;四、编码import java.util.Scanner;class NodeAnyType data;Node prev;Node next;public Node()public Node(AnyType data)this.data=data;this.prev=null;this.next=null;public Node(AnyType data,Node p,Node q)this.data=data; this.prev=p; this.next=q;public class MyLinkedList private int theSize=0;public NodebeginMarker;public Node endMarker;public void print(MyLinkedList dl) Node p = dl.beginMarker.next;System.out.println(循环双链表的元素为:);for (int i = 0; i theSize; i+) System.out.print(p.data + );p = p.next;System.out.println();public MyLinkedList()/构造一个头结点和尾节点的双向链表beginMarker=new Node(null,null,null);endMarker= new Node(null, beginMarker,null);beginMarker.next= endMarker; theSize = 0;public Node getNode(int pos)Nodep;if(postheSize)throw new IndexOutOfBoundsException(getNode():+pos);if(postheSize/2)p=beginMarker.next;for(int i=0;ipos;i-)p=p.prev;return p;/添加public boolean add(AnyType data)add(theSize,data);return true;public void add(int pos,AnyType data)Nodep=getNode(pos);addBefore(p,data);public void addBefore(Node p,AnyType data)Node newNode=new Node(data,p.prev,p);newNode.prev.next=newNode;p.prev=newNode;theSize+;/删除public AnyType remove(int pos)return remove(getNode(pos);public AnyType remove(Node p)p.next.prev=p.prev;p.prev.next=p.next;theSize-;return p.data;/逆转public void nizhi()Node p=beginMarker; boolean flag=true; while(flag) if(p!=endMarker) Node a=p; Node b=p.next; a.next=a.prev; a.prev=b; p=p.prev; else flag=false; Node b=endMarker.next; endMarker.next=endMarker.prev; endMarker.prev=b; Node e=beginMarker; beginMarker=endMarker; endMarker=e; break; public static void main(String args)MyLinkedList la=new MyLinkedList();System.out.println(请输入链表的大小：);Scanner s=new Scanner(System.in);int len=s.nextInt();System.out.println(请输入链表的各个点的数据域：);for(int i=0;ilen;i+)int a=s.nextInt();la.add(a); System.out.println(请输入 您要插入的位置和数据：);int pos=s.nextInt();int d=s.nextInt();la.add(pos-1, d);System.out.println(链表的顺序是：);la.print(la);System.out.println(请输入 您要删除的位置：);int pos1=s.nextInt();la.remove(pos-1);System.out.println(链表的顺序是：);la.print(la); System.out.println(请输入要插入第一个顶点的值：); int val1=s.nextInt(); la.add(0,val1); System.out.println(链表的顺序是：); la.print(la); System.out.println(请输入要插入最后一个顶点的值：); int val2=s.nextInt(); la.add(val2); System.out.println(链表的顺序是：); la.print(la); la.nizhi(); System.out.println(就地逆转之后的链表的顺序是：); la.print(la); 五、测试数据请输入链表的大小：6请输入链表的各个点的数据域：1 2 3 4 5 6请输入 您要插入的位置和数据：2 7链表的顺序是：循环双链表的元素为:1 7 2 3 4 5 6 请输入 您要删除的位置：2链表的顺序是：循环双链表的元素为:1 2 3 4 5 6 请输入要插入第一个顶点的值：0链表的顺序是：循环双链表的元素为:0 1 2 3 4 5 6 请输入要插入最后一个顶点的值：7链表的顺序是：循环双链表的元素为:0 1 2 3 4 5 6 7 就地逆转之后的链表的顺序是：循环双链表的元素为:7 6 5 4 3 2 1 0 六、测试情况树的创建及相关操作的实现一、问题描述树12 3 45 6双亲表示法 孩子链表示法231-12030405161112435456 孩子兄弟表示法123546二、数据结构public class Node int key;String data;Node zuo,you;public Node (String data)super();this.data = data;zuo=you=null;public Node (String data,Node zuo,Node you)this.data=data;this.zuo=zuo;this.you=you;public Node()data= null;zuo=you=null;public int getKey() return key;public void setKey(int key) this.key = key;public String getData() return data;public void setData(String data) this.data = data;public Node getZuo() return zuo;public void setZuo(Node zuo) this.zuo = zuo;public Node getYou() return you;public void setYou(Node you) this.you = you;三、逻辑设计1、总体思路创建双向循环链表-编写各种方法-实现链表的各种操作2、模块划分 jiantree(String e) Main() shuyz(Node root) chengci(Node root) jiaohuan(Node root)3、函数或类的具体定义和功能 函数：public Node jiantree(String e)/创建树public int shuyz(Node root)/ 统计叶子节点个数public void chengci(Node root) / 层次遍历 public void jiaohuan(Node root) /交换左右子树四、编码import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Queue;public class Tree Node root;int i = 0;int yz = 0;public Tree() public Tree(String e) root.data = e;root.zuo = root.you = null;public Tree(Node e) root = e;/建树public Node jiantree(String e) Node root = null;if (i e.length) String data = ei;i+;if (!data.equals() root = new Node(data);root.zuo = jiantree(e);root.you = jiantree(e);return root;/树叶的个数public int shuyz(Node root) if (root = null)return 0;if (root.zuo = null & root.you = null)return 1;elsereturn shuyz(root.zuo) + shuyz(root.you);/层次遍历public void chengci(Node root) ArrayList list = new ArrayList();list.add(root);int i = 0;Node w = list.get(i);if (root = null)return;for (; i list.size(); i+) w = list.get(i);if (w.zuo != null) list.add(w.zuo);if (w.you != null) list.add(w.you);for (int j = 0; j list.size(); j+) w = list.get(j);System.out.printf(w.data + );System.out.println();/交换左右子树public void jiaohuan(Node root) Node t;if (root = null)return;jiaohuan(root.zuo);jiaohuan(root.you);t=root.zuo;root.zuo=root.you;root.you=t;return;public static void main(String args) Scanner cin = new Scanner(System.in);int n;n=cin.nextInt();String tr = new Stringn;for(int i=0;in;i+)tri = cin.next();Tree tree = new Tree();Node node = tree.jiantree(tr);Tree text = new Tree(node);System.out.println(层次遍历的结果为);text.chengci(text.root);System.out.println(叶子的节点数为：+ text.shuyz(text.root);text.jiaohuan(text.root);text.chengci(text.root);五、测试数据1110 9 7 6 8 层次遍历的结果为10 9 8 7 6 叶子的节点数为：3交换左右子树：10 8 9 6 7 六、测试情况结 论本次课程设计做了双向循环链表的创建和相关操作（建立节点，添加，删除，逆置等）以及关于二叉树的相关操作（建树，统计叶子树，层次遍历，以及交换叶子树）。在其过程中遇到了很多问题。比如双向循环链表中当输入超过当前链表的数值时，导致运行失败即没有抛异常，还有在链表中不能做到多数据插入，最后通过一个for循环轻松解决。在做关于二叉树的实验中对我来说最大的问题就是课堂知识掌握不全导致在代码运行阶段频频出错，最后也是通过看课件问同学解决了问题。所以在运行代码阶段给我最大的启迪就是不要眼高手低，别浮躁，脚踏实地的先