双向循环链表的创建及相关操作的实现课程设计说明书.doc

山东建筑大学计算机科学与技术学院课程设计说明书题 目： 双向链表的创建和操作的实现 树的创建及相关操作的实现课 程： 数据结构与算法院 （部）： 计算机学院专 业： 网络工程班 级： 网络101学生姓名： 王天未学 号： 2010111200指导教师： 伊静完成日期： 2013-7-6山东建筑大学计算机学院课程设计说明书 目 录课程设计任务书1iii课程设计任务书2iv双向循环链表的创建及相关操作的实现6一、问题描述6二、数据结构6三、逻辑设计7四、编码8五、 测试数据13六、测试情况13树的创建及相关操作的实现17一、问题描述17二、数据结构17三、逻辑设计18四、编码21五、 测试数据28六、测试情况28结 论30参考文献31课程设计指导教师评语32山东建筑大学计算机科学与技术学院课程设计任务书1设计题目双向循环链表的创建及相关操作的实现已知技术参数和设计要求1、建立一个空表2、插入第i个结点。3、删除第i个结点。4、插入第1个结点。5、插入最后一个结点。6、逆置设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排做双向链表创建方法做双向链表各种操作方法设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%指导教师（签字）： 教研室主任（签字）山东建筑大学计算机科学与技术学院课程设计任务书2设计题目树的创建及相关操作的实现已知技术参数和设计要求1、利用先序遍历和层次遍历的结果建立二叉树2、实现二叉树的层次遍历3、统计二叉树叶子结点的个数（递归）。4、将二叉树左右子树相互交换（递归）设计内容与步骤1.建立结点类2.构造binarytree（）3.建立线序遍历树4.建立层次遍历树5.实现树的层次遍历6.统计叶子结点个数7.交换左右子树8.输出树的方法设计工作计划与进度安排6月13日，实验课下完成先序遍历建树，16月14日课程设计时间完成层次遍历建树6月16日课下完成层次遍历和叶子节点个数统计6月18日课程设计时间完成二叉树左右子树相互交换6月19日完成测试函数及纠错设计考核要求1、 考勤20%2、 课程设计说明书50%3、成果展示30%指导教师（签字）： 教研室主任（签字）29山东建筑大学计算机学院课程设计说明书双向循环链表的创建及相关操作的实现一、问题描述 a0 a1 a2 a3 a41、每个节点的next域构成了一个循环单链表2、每个节点的prev域构成了另一个循环单链表二、数据结构针对所处理的树：1、画出双向循环链表的存储结构 prev data next2、使用所选用语言的功能，描述该存储结构的实现private static class node anytype data;node prev;node next;三、逻辑设计1、总体思路对于双向循环链表，建立一个空表，然后实现双向循环链表的插入，删除操作。为了便于逆置的操作，选择建立一个带头节点的双向循环链表，插入第一个节点和插入最后一个节点，只需要在0号位置和size()位置插入节点就行。2、模块划分（以图示的方法给出各个函数的调用关系）建立一个空表删除节点插入节点逆置主函数3、函数或类的具体定义和功能 class node/节点类定义public class dllist /循环链表主类public boolean add(int idex, anytype x)/链表插入操作public anytype remove(int idex )/链表删除操作private void inverse()/链表逆置 四、编码import java.util.scanner;class node public anytype data; public node prev; public node next; public node() data=null; prev=null; next=null; public node(anytype d) data=d; prev=null; next=null; public node(anytype d,node p,node n) data=d; prev=p; next=n; /节点类public class dllist private node headnode=new node(); /头标记或头节点private int thesize;/长度 public dllist() headnode.next=headnode; headnode.prev=headnode; thesize=0; /创建一个空表 public int size()return thesize; /设定表的长度 public boolean add(anytype x) add(thesize, x);return true;/链表输入操作public boolean add(int idex, anytype x) boolean flag;if (idex thesize) /判断插入的位置是否大于0system.out.println(您输入的要插入元素的位置不正确!);flag = false; elseflag = true;if (flag) node p;p = getnode(idex);addbefore(p, x);/插入操作return flag;private void addbefore(node p, anytype x) node newnode = new node(x, p.prev, p);newnode.prev.next = newnode;p.prev = newnode;thesize+;/插入方法 public anytype remove(int idex ) return remove(getnode(idex); private anytype remove( node p ) p.prev.next=p.next; p.next.prev=p.prev; thesize-; return p.data; /删除操作 private void inverse() node p,q,l; p=headnode.next; q=p.next; while(p!=headnode)l=q.next;/空置的中转结点赋值q.next=p;/将p、q链表的前后域置换。q由p的后域变成前域p.prev=q;p=q;/置换后，将各个结点置换输出。q=l; q.next=p; p.prev=q;/当p为头结点时，直接将前后域置换。 /逆置 private node getnode(int idex)node p;if(idexsize()throw new indexoutofboundsexception(getnode idex:+idex+;size:+size();if(idexsize()/2) p=headnode;for(int i=0;iidex;i-)p=p.prev;return p; /查找结点位置 public void print() for(int i=0;ithis.thesize;i+) system.out.print(getnode(i).data+ ); system.out.println(); /结果输出 public void choose() system.out.println(1.插入第i个节点); system.out.println(2.删除第i个节点); system.out.println(3.插入第一个节点); system.out.println(4.插入最后一个节点); system.out.println(5.逆置); /选择操作项 public static void main(string args) dllist dl=new dllist(); scanner sc=new scanner(system.in); int xuanze; system.out.println(请输入链表的元素的个数(大于0个)：); int n=sc.nextint(); system.out.println(请输入链表的+n+个元素：); for(int i=1;i=n;i+) int l=sc.nextint(); dl.add(l);/链表元素输入 system.out.println(您输入的链表为：); dl.print();/调用print方法，提示操作。 system.out.println(请选择操作项：); dl.choose();/调用choose，选择操作。 while(true) xuanze=sc.nextint(); switch(xuanze) case 1: system.out.println(请输入要插入的位置下标和数据：); int idex=sc.nextint(); int data=sc.nextint(); dl.add(idex, data); dl.print(); break; case 2: system.out.println(请输入要删除节点的下标：); int idex1=sc.nextint(); dl.remove(idex1); dl.print(); break; case 3: system.out.println(请输入插入第一个节点的元素：); int data1=sc.nextint(); dl.add(0,data1); dl.print(); break; case 4: system.out.println(请输入插入最后位置的元素：); int data2=sc.nextint(); dl.add(dl.size(), data2); dl.print(); break; case 5: dl.inverse(); dl.print(); break; default: system.out.println(你的输入有误，请重新输入！); break; 5、 测试数据1、对每个函数的测试数据链表中的元素插入为1、2、3、4、5插入第二个结点的元素为6删除第二个节点的位置的元素6插入第一个节点的元素为7插入最后一个节点的元素为6逆置链表2、对程序整体的测试数据输入元素为1、2、3、4、5的双向循环链表六、测试情况请输入链表的元素的个数(大于0个)：5请输入链表的5个元素：12345您输入的链表为：1 2 3 4 5 请选择操作项：1.插入第i个节点2.删除第i个节点3.插入第一个节点4.插入最后一个节点5.逆置1请输入要插入的位置下标和数据：261 2 6 3 4 5请输入链表的元素的个数(大于0个)：5请输入链表的5个元素：12345您输入的链表为：1 2 3 4 5 请选择操作项：1.插入第i个节点2.删除第i个节点3.插入第一个节点4.插入最后一个节点5.逆置2请输入要删除的位置下标和数据：261 2 3 4 5请输入链表的元素的个数(大于0个)：5请输入链表的5个元素：12345您输入的链表为：1 2 3 4 5 请选择操作项：1.插入第i个节点2.删除第i个节点3.插入第一个节点4.插入最后一个节点5.逆置3请输入插入第一个节点的元素：77 1 2 3 4 5请输入链表的元素的个数(大于0个)：5请输入链表的5个元素：12345您输入的链表为：1 2 3 4 5 请选择操作项：1.插入第i个节点2.删除第i个节点3.插入第一个节点4.插入最后一个节点5.逆置4请输入插入最后位置的元素：61 2 3 4 5 6 请输入链表的元素的个数(大于0个)：5请输入链表的5个元素：12345您输入的链表为：1 2 3 4 5 请选择操作项：1.插入第i个节点2.删除第i个节点3.插入第一个节点4.插入最后一个节点5.逆置55 4 3 2 1 树的创建及相关操作的实现一、问题描述a1.先遍序遍历建树cbnullefdnullnullnullnull2、 遍历方法举例：先序遍历 ：a bd cef层次遍历 ：a bc def二、数据结构针对所处理的树：1、画出存储结构 left data right 2、使用所选用语言的功能，实现上述的该存储结构public static class btnode private anytype data;private btnode parent;private btnode leftnode;private btnode rightnode; 三、逻辑设计1、总体思路首先建立节点类，然后构造binarytree（），再构造先序遍历建树方法，层次遍历建树方法，层次遍历树的方法，统计叶子结点个数方法，交换子树方法，再调试。2、 模块划分（以图示的方法给出各个函数的调用关系）3、 函数或类的具体定义和功能 bitnode()/节点类定义 public bitnode creattree(anytype a)/先序建树方法定义 private void creatpathbinarytree(anytype a)/层次遍历建树定义public void pathorder()/层次遍历方法定义public int countleafnode()/ 统计叶子节点个数方法定义四、编码1.结点类定义package kcsj;public class bitnode implements comparablebitnode anytype data;bitnode left, right;int weight;bitnode() data = null;left = right = null;bitnode(anytype thedata) data = thedata;left = right = null;bitnode(anytype thedata, bitnode lt, bitnode rt) data = thedata;left = lt;right = rt;public bitnode getleft() return left;public bitnode getright() return right;public object getdata() return data;public double getwight() return weight;overridepublic int compareto(bitnode o) if (o.getwight() this.getwight()return 1;if (o.getwight() this.getwight()return -1;return 0;2. binarytree()构造package kcsj;import java.util.linkedlist;import java.util.queue;public class binarytreeanytype extends comparable anytype pre, in;bitnode rootnode = new bitnode();int count = 0;public binarytree() rootnode = null;public binarytree(anytype rootnodeitem) rootnode.data = rootnodeitem;rootnode.left = rootnode.right = null;public binarytree(bitnode t) rootnode = t;/1. 先序遍历建树public bitnode creattree(anytype a) return rootnode = creatbinarytree(a);private bitnode creatbinarytree(anytype a) bitnode p = null;if (count a.length) anytype data = acount;count+;if (data != null) p = new bitnode(anytype) data);p.left = creattree(a);p.right = creattree(a);return p;/1.层次遍历排序建树public void creatpathtree(anytype a) if (a != null) creatpathbinarytree(a);private void creatpathbinarytree(anytype a) queuebitnode q = new linkedlistbitnode();bitnode node = new bitnode(a0);rootnode = node;q.offer(node);int i = 1;while (i a.length) if (ai != null) node = new bitnode(ai);q.element().left = node;q.offer(q.element().left);if (i a.length - 1) if (a+i != null) node = new bitnode(ai);q.element().right = node;q.offer(q.element().right);q.poll();i+;/2.实现二叉树的层次遍历public void pathorder() if (rootnode != null)pathorder(rootnode);public void pathorder(bitnode t) queuebitnode q = new linkedlistbitnode();q.offer(t);while (!q.isempty() if (q.element().left != null)q.offer(q.element().left);if (q.element().right != null)q.offer(q.element().right);system.out.print(q.poll().data + );/ 先序遍历public void preorder() if (rootnode != null)preorder(rootnode);private void preorder(bitnode t) if (t != null) system.out.print(t.data+ );preorder(t.left); preorder(t.right);/ 统计节点的个数public int countnode() return countnode(rootnode);private int countnode(bitnode t) int m, n;if (t = null)return 0;m = countnode(t.left);n = countnode(t.right);return m + n + 1;/ 3.统计叶子节点个数（递归）public int countleafnode() return countleafnode(rootnode);private int countleafnode(bitnode t) int m = 0, n = 0;if (t = null)return 0;if (t.left = null & t.right = null) return 1;m = countleafnode(t.left);n = countleafnode(t.right);return m + n;/ 4.将二叉树左+右子树相互交换（递归）public void exchangetree() if (rootnode != null) exchangetree(rootnode);private bitnode exchangetree(bitnode t) if (t != null) bitnode p = t.right;t.right = t.left;t.left = p;exchangetree(t.right);exchangetree(t.left);return t;/ 计算树的深度public int depth() return depth(rootnode);private int depth(bitnode t) / 返回二叉树的深度int depthleft, depthright;if (t = null)return 0;depthleft = depth(t.left);depthright = depth(t.right);return math.max(depthleft, depthright) + 1;/横向输出树状图public void showtree(bitnode t,int n)if (t=null) return; showtree(t.right,+n);for (int i = 0; i n; i+) system.out.print( );system.out.print(t.data+n); showtree(t.left,n+);3. 测试函数package kcsj;public class test public static void pln(object o) system.out.println(o);public static void main(string args) binarytree bt = new binarytree();character charspre = a, b, d, null, null, null, c, e,null, null, f ;character charspath = a, b, c, d, null, e, f ;pln(先序建树：a,b,d,null,null,null,c,e,null,null,f);bt.creattree(charspre);pln(层序遍历结果：);bt.pathorder();pln( );pln(树图为(横向)：);bt.showtree(bt.rootnode, 1);pln( );pln(层序建树：a,b,c,d,null,e,f);bt.creatpathtree(charspath);pln(先序遍历结果：);bt.preorder();pln( );pln(树图为(横向)：);bt.showtree(bt.rootnode, 1);pln( );pln(叶子节点数： + bt.countleafnode();p