数据结构课程设计报告双向循环链表的创建及相关操作的实现

山东建筑大学计算机科学与技术学院课程设计说明书 题 目： 双向循环链表的创建及相关操作的实现 题 目： 树 题 目: 图 课 程： 数据结构院 （部）： 计算机学院专 业： 软件工程班 级： 学生姓名： 学 号： 指导教师： 伊静完成日期： 2012-12-2721 / 52文档可自由编辑打印目 录课程设计任务书I双向循环链表的的创建及相关操作的实现3二、数据结构3三、逻辑设计3四、编码3五、测试数据3六、测试情况3树的的创建及相关操作的实现3一、问题描述3二、数据结构3三、逻辑设计3四、编码3五、测试数据3六、测试情况3图的的创建及相关操作的实现3一、问题描述3二、数据结构3三、逻辑设计3四、编码3五、测试数据3六、测试情况3结 论4参考文献5课程设计指导教师评语6课程设计任务书设计题目双向循环双向循环链表的创建及相关操作的实现已知技术参数和设计要求对给定的双向循环链表能够实现链表的初始化，节点的添加，节点的删除，和链表的逆置。并对所创建的双向循环链表实现以下的操作：1. 建立一个空的链表。 2. 插入第i个节点。3. 删除第i个节点。4. 插入第一个节点。5. 删除最后一个节点。6. 逆置。设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排根据自己选作的题目，给出完成每项工作的时间表，包括起止时间、工作内容、地点设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%指导教师（签字）： 教研室主任（签字）双向循环链表的创建及相关操作的实现一、问题描述用图示的方法描述所处理的双向循环链表的形态二、数据结构针对所处理的双向循环链表：1、 画出双向循环链表的存储结构 a2a3a1a0三、逻辑设计1、总体思路1.构思： 首先双向循环链表的创建建立在双向链表之上，所以建立双向循环表时 每个节点有三个属性：即数据域、上一个节点和下一个节点。其中第一个节点的上一个节点是最后一节点，最后一个节点的下一个节点是第一个节点。从而构成双向循环链表。1. 首先创建出来一个空的双向循环链表链表里面只有1个节点即beginMarker。一个个节点构成一个空的双向循环链表。2. 创建出链表后调用add方法在beginMarker的后面添加节点，每次添加节点后吧添加的那个节点作为endMarker使其和头结点构成循环。3. 插入一个节点时首先要找到要插入节点的位置，如果是第一个节点，则把第一个节点先保存起来，把新节点添加进去，再把原来的第一个节点添加进来插入最后一个节点是和添加第一个节点的方法类似。 若是在中间的某个位置插入则先找到那个位置的元素，类似于从第一个节点插入。4.删除时先找到要删除的位置如果是第一个位置，则把第一个元素的值先保存，然后把第一个节点的next赋给beginMarker，然后把第一个节点的值致null；在中间删除也是删除最后一个把最后一个节点的前一个节点的next置空。5.逆置是创建一个空的链表把原来的链表的元素添加到空链表当中。然后打印出来2、 模块划分（以图示的方法给出各个函数的调用关系） MyTwoLinkedCycleList list=new MyTwoLinkedCycleList(); MyTwoLinkedCycleList list1=new MyTwoLinkedCycleList(); list.addInit(); List.add(); List.remove() Lst.print(); List.panduan(list1); 3、 函数或类的具体定义和功能 MyTwoLinkedCycleList 1.MyTwoLinkedCycleList()构造方法用于创建空的链表 2.init()初始化各项说明文字 3.addInit()用于向空的链表初始化节点 4.add()用于添加顶点和最后一个顶点之间的节点 5.add(AnyType data,int index)用于添加任意位置的顶点 6.remove()删除顶点操作 7.size()用于求链表的大小 8.inverse()用于逆置链表 9.print()用于打印出链表中的各元素 10.panduan()用于选择是否逆置链表四、编码package package2;import java.util.Scanner;public class MyTwoLinkedCycleListSuppressWarnings(hiding)private class Node AnyType data; Node next; Node previous; private Node() data=null; previous=null; next=null; private Node(AnyType data) this.data=data; this.previous=null; this.next=null; private Node(AnyType data,Node previous,Node next) this.data=data; this.previous=previous; this.next=next; SuppressWarnings(unused)private int size=0;private Node beginMarker;private Node endMarker;/初始化一个空的双向循环链表public MyTwoLinkedCycleList()beginMarker=new Node();endMarker=new Node();beginMarker.previous=endMarker;beginMarker.next=null;endMarker.previous=null;endMarker.next=beginMarker;public void init()System.out.println(*数据结构课程设计*);System.out.println(*改程序用于完成对于双向循环链表的各项操作*);System.out.println(*);System.out.println(1.空的双向循环链表已经建立);/2.用于向空的双向循环链表里面添加数据SuppressWarnings(unchecked)public void addInit()Scanner sc=new Scanner(System.in);System.out.println(2.该步骤执行初始化节点操作);System.out.println(a.请输入要插入节点的个数);int n=sc.nextInt();for(int i=0;in;i+)System.out.println(b.请输入要插入的元素的数值:);AnyType data=(AnyType)sc.next();if(beginMarker.next=null)Node node=new Node(data);beginMarker.next=node;node.previous=beginMarker;endMarker=node;endMarker.next=beginMarker;beginMarker.previous=endMarker; elseNode node=new Node(data);endMarker.next=node;node.previous=endMarker;endMarker=node;endMarker.next=beginMarker;beginMarker.previous=endMarker;/public void add(AnyType data)if(beginMarker.next=null)Node node=new Node(data);beginMarker.next=node;node.previous=beginMarker;endMarker=node;endMarker.next=beginMarker; elseNode node=new Node(data);endMarker.next=node;node.previous=endMarker;endMarker=node;endMarker.next=beginMarker;/该方法用于插入任何一个weizhideSuppressWarnings(unchecked)public void add()Scanner sc=new Scanner(System.in);System.out.println(3.该步骤执行插入节点操作);System.out.print(*请输入要插入节点的个数*);System.out.println(可用于插入第一个和最后一个节点);int n=sc.nextInt();for(int i=0;in;i+)System.out.println(a.请输入要插入节点的位置:);int index=sc.nextInt(); System.out.println(b.请输入要插入的元素的数值);AnyType data=(AnyType)sc.next();int j=0;if (beginMarker=null)Node Node = new Node(data);beginMarker.next=Node;Node.previous=beginMarker;endMarker=Node;endMarker.next=beginMarker;else if(index=0)Node Node=new Node(data);Node temp=beginMarker.next;beginMarker.next=Node;Node.previous=beginMarker;Node.next=temp;temp.previous=Node; else if(index=size()add(data); else NodeNode=new Node(data);Node prior=beginMarker;while (jindex)j+;prior=prior.next;Node temp=prior.next;prior.next=Node;Node.previous=prior;Node.next=temp;temp.previous=Node; public void remove() int j=0;Scanner sc=new Scanner(System.in);System.out.println(4.该步骤执行删除节点操作);System.out.println(a.请输入要删除节点的个数:);int n=sc.nextInt();for(int i=0;in;i+)System.out.println(b.请输入要删除节点的位置:);int index=sc.nextInt(); if (index=size() System.out.println(数组越界); else if(index=0|size()=1) if (size()=0)beginMarker.next=null;endMarker=null; else Node fitst=beginMarker.next;beginMarker.next=fitst.next;fitst=null; else if(index=(size()-1)if(size()=1) if (size()=0)beginMarker.next=null;endMarker=null; else Node fitst=beginMarker.next;beginMarker.next=fitst.next;fitst=null; elseNode pre=endMarker.previous;pre.next=null;endMarker=pre;endMarker.next=beginMarker;endMarker=null; else Node prior=beginMarker.next;while(jindex)j+;prior=prior.next;Node delete=prior;Node pre=delete.previous;Node after=delete.next;pre.next=delete.next;after.previous=pre;delete=null;System.out.println(*);/用于计算链表的大小public int size() int size=0;Node node=beginMarker.next;while(node.data!=null) size+;node=node.next;return size;/用于得到节点public Node getNode(int index) int j=0;Node firstNode=beginMarker.next;if(index=size()System.out.println(数组越界);while(jindex)j+;firstNode=firstNode.next;return firstNode; /该方法用于输出链表中的所有数值public void print()Node firstNode=beginMarker.next;if(firstNode=null)System.out.println(该链表为空); elsewhile(firstNode.data!=null)System.out.println(firstNode.data);firstNode=firstNode.next; SuppressWarnings( rawtypes, unchecked )public void panduan(MyTwoLinkedCycleList list) System.out.println(5.是否执行逆置操作(yes/no)?); Scanner sc=new Scanner(System.in); String str=sc.next(); if(str.equals(yes) this.inverse(list); else System.out.println(*所有操作均已经完成*); /实现链表的逆置操作 public void inverse(MyTwoLinkedCycleList list1) System.out.println(逆置后的结果为:); int size=size(); for(int i=size-1;i=0;i-) list1.add(this.getNode(i).data); list1.print(); System.out.println(*所有操作均已经完成*); public static void main(String args) MyTwoLinkedCycleList list=new MyTwoLinkedCycleList();list.init();MyTwoLinkedCycleList list1=new MyTwoLinkedCycleList();list.addInit();list.add();list.remove(); list.print(); list.panduan(list1); 五、测试数据1、 对每个函数的测试数据 a.创建空的双向循环链表 b. c.D.E.2.对程序整体的测试数据六、 测试情况二、设计题目树的创建及相关操作的实现已知技术参数和设计要求创建一个树对自己所创建的树完成以下操作：1、使用孩子-兄弟表示法作为存储结构，实现树的先根、后根遍历和层次遍历。2、使用孩子-兄弟表示法作为存储结构，统计树中叶子结点的个数。3、使用双亲表示法作为存储结构，统计树的深度。设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排根据自己选作的题目，给出完成每项工作的时间表，包括起止时间、工作内容、地点设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%指导教师（签字）： 教研室主任（签字） 树的创建及相关操作的实现一、问题描述用图示的方法描述所处理的树的形态cabefd二、数据结构三、逻辑设计1、总体思路 a、思路：孩子兄弟表示法又称为二叉链表表示法，可以用二叉链表作为存储 结构表示，节点的属性包括三部分：data、firstChild、nextSibling.所以树的节点类似于data、leftChild、rightChild、树的创建可以以孩子-兄弟表示法作为存储结构用先序遍历创建同时完成其各项遍历工作。b、构思:用一个节点类数组存储树的所有节点，节点类的属性域包括data和parent，parent指的是该节点在数组中的位置，求树的深度时由图可知父节点的指针域的个数就是树的深度。2、 模块划分（以图示的方法给出各个函数的调用关系） A. public class Cs14 private class CSNode tree.initAll(); Cs14.root = tree.CreateTree(); tree.preorder(Cs14.root);tree.initPost();tree.postOrder(Cs14.root);tree.initLevel(); tree.levelOrder(Cs14.root); tree.inputLeaf(); b. PTreeTest15 tree=new PTreeTest15(); tree.store(); tree.countDepth(tree.nodes);3、 函数或类的具体定义和功能4、 a. public void initAll()用于向树中输入节点的个数及节点 public CSNode CreateTree()用于创建树 public void preorder(CSNode node)用于实现树的先序遍历 public void postOrder(CSNode t)用于实现树的先序遍历 public void levelOrder(CSNode node)用于实现树的中序遍历 public int countLeaf(CSNode t) 用于实现树的后序遍历 public static void main(String args)主方法 B. public class PTreeTest15 private class PTNode public PTreeTest15()构造方法用于初始化各项数据 public void init()对数的节点个数及数值进行初始化 public void store()把各节点存储到数组当中 public void countDepth(PTNode nodes)计算树的深度 public static void main(String args)主方法四、编码给出具体的程序代码package ch1;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Cs14 private class CSNode private Object data=null; private CSNode firstChild=null; private CSNode nextSibling=null; private CSNode() this.firstChild = null;this.nextSibling = null; private CSNode(Object data)this.firstChild = null;this.nextSibling = null;this.data = data; static CSNode root ;/ 输入的字符串 char charArray; static int i=0; public void initAll() Scanner sc=new Scanner(System.in); System.out.println(*); System.out.println(该程序用于完成+n+1.+孩子兄弟存储结构中树的先序根遍历，后根遍历和层序遍历+n+2.+求出树中叶子节点的个数并输出其结果); System.out.println(*); System.out.println(a.请输入该树的节点个数(包括空节点在内):); System.out.println(*); int value=sc.nextInt(); this.charArray=new charvalue; System.out.println(*); System.out.println(b.请输入该树的所有节点(包括空节点在内):); System.out.println(*); String str=sc.next(); this.charArray = str.toCharArray(); System.out.println(*); System.out.println(A.在该二叉树中先序遍历输出的结果为:); System.out.println(*); public void initPost() System.out.println(*); System.out.println(B.在该二叉树中后序遍历输出的结果为:); public void initLevel() System.out.println(*); System.out.println(C.请输出层序遍历的结果:); System.out.println(*); System.out.println(*已完成孩子兄弟存储结构的所有操作*); System.out.println(*); public void inputLeaf() System.out.println(); System.out.println(*); System.out.println(D.计算出叶子节点的个数为:); System.out.println(*); System.out.println(this.countLeaf(Cs14.root); System.out.println(*); public CSNode CreateTree() CSNode node = null; if (charArrayi=) node=null; i+; else node=new CSNode(); node.data=charArrayi; i+; node.firstChild=CreateTree(); node.nextSibling=CreateTree(); return node; /实现树的先根遍历 public void preorder(CSNode node) if(node!=null) System.out.println(node.data+t); preorder(node.firstChild);preorder(node.nextSibling); else System.out.println(null+t); /实现树的后根遍历 public void postOrder(CSNode t) /后序遍历 if(t!=null) postOrder(t.firstChild); /遍历左子树 postOrder(t.nextSibling); /遍历右子树System.out.println(t.data+t); /访问根节点 else System.out.print(null+t); /实现根层序遍历 public void levelOrder(CSNode node)Queue queue=new LinkedList(); if(node!=null) queue.add(node); while(!queue.isEmpty() node=(CSNode)queue.remove(); System.out.print(node.data+t); if(node.firstChild!=null) queue.add(node.firstChild); if(node.nextSibling!=null) queue.add(node.nextSibling); /这是求叶子节点的方法 public int countLeaf(CSNode t) if (t=null) return 0; else int firstChild =countLeaf(t.firstChild); int nextSibling=countLeaf(t.nextSibling); if (t.firstChild=null&t.nextSibling=null) return firstChild+nextSibling+1; else return firstChild+nextSibling; /主方法 public static void main(String args)Cs14 tree=new Cs14();tree.initAll();/abdcefCs14.root = tree.CreateTree(); tree.preorder(Cs14.root);tree.initPost();tree.postOrder(Cs14.root);tree.initLevel(); tree.levelOrder(Cs14.root); tree.inputLeaf(); b、package ch1;import java.util.HashSet;import java.util.Scanner;import java.util.Set; public class PTreeTest15 private class PTNode /数据域 SuppressWarnings(unused) private String data; / 双亲位置域 private int parent; private PTNode() private PTNode(String data,int parent) this.data=data; this.parent=parent; /根节点在数组中的位置 int root; /根节点数量 int n; PTNode nodes=new PTNode1000; /节点类 public PTreeTest15() System.out.println(*); System.out.println(该程序用于完成:); System.out.println(1.双亲表示法存储树); System.out.println(2.计算双亲表示法存储树的深度); System.out.println(*); System.out.println(*双亲表示法存储树并求树的深度*); System.out.println(1.双亲表示法存储树); init(); public void init() Scanner s=new Scanner(System.in); System.out.println(*a.请输入根节点的位置*); int value3=s.nextInt(); this.root=value3; System.out.println(*b.请输入节点的个数*); int num=s.nextInt(); this.n=num; public void store()Scanner s=new Scanner(System.in);PTNode nodes=new PTNoden; for(int i=0;in;i+) System.out.println(a.请输入节点的数据:); String value1=s.next(); System.out.println(b.请输入节点的父节点域:); int value2=s.nextInt(); nodesi=new PTNode(value1,value2); this.nodes=nodes; System.out.println(打印出节点的位置及其数据域及其双亲域:); for(int i=0;in;i+) System.out.println(i+t+nodesi.data+t+nodesi.parent); public void countDepth(PTNode nodes)System.out.println(2.计算双亲表示法存储树的深度:);Set set=new HashSet();for(int i=0;i1 1 B-2-3 2 C-3 3 D-null 2、使用所选用语言的功能，实现上述的2种存储结构三、逻辑设计1、总体思路A.邻接矩阵存储用邻接矩阵创建时首先定义一个节点类分别把图中所有的节点创建出来，然后存储到一个一维数组，从而把图中的节点创建出来，在定义一个布尔型的二维数组存储边，边的存储时通过节点的输入，这样顶点和边都创建出来之后图就创建出来。B.邻接链表的存储邻接链表的创建是通过定义一个节点类和一个边类，创建一个节点类数组把创建出来的节点添加到数组中，然后向图中添加边，添加的时候输入的是各顶点存储在数组中的位置。(0,1,2,.)，从而把每一个顶点的邻接点添加到一个邻接链表中有几个节点就有几个邻接顶点。2、 模块划分（以图示的方法给出各个函数的调用关系） 3、 函数或类的具体定义和功能 int nextAdjVex(int v, int w) public void createGraph( )创建图public void createDG() 创建有向图public void createUDG( )创建无向图public void createDN()创建有向网public void createUDN()创建无向网public void addVex(AnyType v) 用于添加节点public void addEdge(int start, int end)用于添加边start为弧尾，end为弧头public void DFS(int v) 用于深度优先搜索public void BFS(int v)用于广度优先搜索public void DeleteVex(int v)删除一个顶点public void DeleteArc(int v,int w)删除边public int degreeIn(int v)求图的入度public int degreeOut(int v)求图的出度public void DFSToplogicalSort(int v) 拓步排序public static void main(String args)主方法四、 编码给出具体的程序代码A.package ch1;import java.util.Scanner;public class LinJieJuZhenCreate class VertexAnyType data;private Vertex()this.data=null;private Vertex(AnyType data)this.data=data;private class Edgestatic int size;Vertex vertex; boolean edgesArray; Supp