《双向循环链表的创建及相关操作的实现课程设计说明书.doc》由会员分享，可在线阅读，更多相关《双向循环链表的创建及相关操作的实现课程设计说明书.doc（31页珍藏版）》请在金锄头文库上搜索。
1、山东建筑大学计算机科学与技术学院课程设计说明书题 目： 双向链表的创建和操作的实现 树的创建及相关操作的实现课 程： 数据结构与算法院 （部）： 计算机学院专 业： 网络工程班 级： 网络101学生姓名： 王天未学 号： 2010111200指导教师： 伊静完成日期： 2013-7-6山东建筑大学计算机学院课程设计说明书 目 录课程设计任务书1III课程设计任务书2IV双向循环链表的创建及相关操作的实现6一、问题描述6二、数据结构6三、逻辑设计7四、编码8五、 测试数据13六、测试情况13树的创建及相关操作的实现17一、问题描述17二、数据结构17三、逻辑设计18四、编码21五、 测试数据28
2、六、测试情况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设
3、计题目树的创建及相关操作的实现已知技术参数和设计要求1、利用先序遍历和层次遍历的结果建立二叉树2、实现二叉树的层次遍历3、统计二叉树叶子结点的个数（递归）。4、将二叉树左右子树相互交换（递归）设计内容与步骤1.建立结点类2.构造BinaryTree（）3.建立线序遍历树4.建立层次遍历树5.实现树的层次遍历6.统计叶子结点个数7.交换左右子树8.输出树的方法设计工作计划与进度安排6月13日，实验课下完成先序遍历建树，16月14日课程设计时间完成层次遍历建树6月16日课下完成层次遍历和叶子节点个数统计6月18日课程设计时间完成二叉树左右子树相互交换6月19日完成测试函数及纠错设计考核要求1、 考
4、勤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、总体思路对于双向循环链表，建立一个空
5、表，然后实现双向循环链表的插入，删除操作。为了便于逆置的操作，选择建立一个带头节点的双向循环链表，插入第一个节点和插入最后一个节点，只需要在0号位置和size()位置插入节点就行。2、模块划分（以图示的方法给出各个函数的调用关系）建立一个空表删除节点插入节点逆置主函数3、函数或类的具体定义和功能 class Node/节点类定义public class DlList /循环链表主类public boolean add(int idex, AnyType x)/链表插入操作public AnyType remove(int idex )/链表删除操作private void inverse()/
6、链表逆置 四、编码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
7、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 (i
8、dex 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+;/插入方法
9、 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
10、.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
11、;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;
