山东建筑大学计算机科学与技术学院
课程设计说明书
题 目： 双向链表的创建和操作的实现
树的创建和相关操作的实现
课 程： 数据结构与算法分析
院 （部）： 计算机学院
专 业： 软件工程
班 级： 软件133
学生姓名： 孙振宇
学 号： 20131112110
指导教师： 伊静
完成日期： 20##-1-8
目 录
课程设计任务书一............................................... 2
课程设计任务书二............................................... 3
双向循环链表的创建及相关操作的实现............................. 4
一、 问题描述.............................................. 4
二、数据结构............................................... 5
三、逻辑设计............................................... 5
四、编码................................................... 6
五、测试数据.............................................. 11
六、测试情况.............................................. 12
树的创建及相关操作的实现...................................... 13
一、问题描述.............................................. 13
三、逻辑设计.............................................. 15
四、编码.................................................. 15
五、测试数据.............................................. 18
六、测试情况.............................................. 18
结 论......................................................... 19
参考文献...................................................... 19
课程设计指导教师评语.......................................... 20
山东建筑大学计算机科学与技术学院
课程设计任务书一
山东建筑大学计算机科学与技术学院
课程设计任务书二
双向循环链表的创建及相关操作的实现
一、问题描述
双向循环链表的逻辑形态
插入操作
删除操作
二、数据结构
class Node<AnyType>{
AnyType data;
Node<AnyType> prev;
Node<AnyType> next;
public Node()
{
}
public Node(AnyType data)
{
this.data=data;
this.prev=null;
this.next=null;
}
public Node(AnyType data,Node<AnyType> p,Node<AnyType> q)
{
this.data=data;
this.prev=p;
this.next=q;
}
}
三、逻辑设计
1、总体思路
先找出有用的数据存储结构 --> 编写相关方法 --> 完成对数据 的操作
2、模块划分
3、函数或类的具体定义和功能
public MyLinkedList()remove(int idx)//删除
public Node<AnyType> getNode(int pos)//得到某一位置的节点
publicboolean add(AnyType data)//添加
publicvoid nizhi()//逆置
publicvoid print(MyLinkedList<AnyType> dl)//打印
publicstaticvoid main(String[] args)//主方法
class Node<AnyType>{//节点类
AnyType data;
Node<AnyType> prev;
Node<AnyType> next;
public Node()
{
}
public Node(AnyType data)
{
this.data=data;
this.prev=null;
this.next=null;
}
public Node(AnyType data,Node<AnyType> p,Node<AnyType> q)
{
this.data=data;
this.prev=p;
this.next=q;
}
}
四、编码
import java.util.Scanner;
class Node<AnyType>{
AnyType data;
Node<AnyType> prev;
Node<AnyType> next;
public Node()
{
}
public Node(AnyType data)
{
this.data=data;
this.prev=null;
this.next=null;
}
public Node(AnyType data,Node<AnyType> p,Node<AnyType> q)
{
this.data=data;
this.prev=p;
this.next=q;
}
}
publicclass MyLinkedList<AnyType> {
privateint theSize=0;
public Node<AnyType>beginMarker;
public Node <AnyType> endMarker;
publicvoid print(MyLinkedList<AnyType> dl) {
Node<AnyType> 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<AnyType>(null,null,null);
endMarker= new Node<AnyType>(null, beginMarker,null);
beginMarker.next= endMarker;
theSize = 0;
}
public Node<AnyType> getNode(int pos)
{
Node<AnyType>p;
if(pos<0||pos>theSize)
thrownew IndexOutOfBoundsException("getNode():"+pos);
if(pos<theSize/2)
{
p=beginMarker.next;
for(int i=0;i<pos;i++)
{
p=p.next;
}
}
else
{
p=endMarker;
for(int i=theSize;i>pos;i--)
{
p=p.prev;
}
}
return p;
}
//添加
publicboolean add(AnyType data)
{
add(theSize,data);
returntrue;
}
publicvoid add(int pos,AnyType data)
{
Node<AnyType>p=getNode(pos);
addBefore(p,data);
}
publicvoid addBefore(Node<AnyType> p,AnyType data)
{
Node<AnyType> newNode=new Node<AnyType>(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<AnyType> p)
{
p.next.prev=p.prev;
p.prev.next=p.next;
theSize--;
return p.data;
}
//逆转
publicvoid nizhi()
{
Node<AnyType> p=beginMarker;
boolean flag=true;
while(flag)
{
if(p!=endMarker)
{
Node<AnyType> a=p;
Node<AnyType> b=p.next;
a.next=a.prev;
a.prev=b;
p=p.prev;
}
else
{
flag=false;
Node<AnyType> b=endMarker.next;
endMarker.next=endMarker.prev;
endMarker.prev=b;
Node<AnyType> e=beginMarker;
beginMarker=endMarker;
endMarker=e;
break;
}
}
}
publicstaticvoid main(String[] args){
MyLinkedList<Integer> la=new MyLinkedList<Integer>();
System.out.println("请输入链表的大小：");
Scanner s=new Scanner(System.in);
int len=s.nextInt();
System.out.println("请输入链表的各个点的数据域：");
for(int i=0;i<len;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("请输入 您要删除的位置：");
intpos1=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
六、测试情况
树的创建及相关操作的实现
一、问题描述
树
1
2 3 4
5 6
双亲表示法 孩子链表示法
孩子兄弟表示法
二、数据结构
publicclass 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;
}
publicint getKey() {
return key;
}
publicvoid setKey(int key) {
this.key = key;
}
public String getData() {
return data;
}
publicvoid setData(String data) {
this.data = data;
}
public Node getZuo() {
return zuo;
}
publicvoid setZuo(Node zuo) {
this.zuo = zuo;
}
public Node getYou() {
return you;
}
publicvoid 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) //交换左右子树
四、编码
importjava.util.ArrayDeque;
import java.util.ArrayList;
importjava.util.Collections;
importjava.util.List;
importjava.util.Queue;
publicclass 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 = e[i];
i++;
if (!data.equals("@")) {
root = new Node(data);
root.zuo = jiantree(e);
root.you = jiantree(e);
}
}
return root;
}
//树叶的个数
publicint shuyz(Node root) {
if (root == null)
return 0;
if (root.zuo == null && root.you == null)
return 1;
else
return shuyz(root.zuo) + shuyz(root.you);
}
//层次遍历
publicvoid chengci(Node root) {
ArrayList<Node> list = new ArrayList<Node>();
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();
}
//交换左右子树
publicvoid 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;
}
}publicstaticvoid main(String[] args) {
Scanner cin = new Scanner(System.in);
int n;
n=cin.nextInt();
String[] tr = new String[n];
for(int i=0;i<n;i++){
tr[i] = 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);
}
}
五、测试数据
11
10 9 7 @ @ 6 @ @ 8 @ @
层次遍历的结果为
10 9 8 7 6
叶子的节点数为：
3
交换左右子树：
10 8 9 6 7
六、测试情况
结 论
本次课程设计做了双向循环链表的创建和相关操作（建立节点，添加，删除，逆置等）以及关于二叉树的相关操作（建树，统计叶子树，层次遍历，以及交换叶子树）。在其过程中遇到了很多问题。比如双向循环链表中当输入超过当前链表的数值时，导致运行失败即没有抛异常，还有在链表中不能做到多数据插入，最后通过一个for循环轻松解决。在做关于二叉树的实验中对我来说最大的问题就是课堂知识掌握不全导致在代码运行阶段频频出错，最后也是通过看课件问同学解决了问题。所以在运行代码阶段给我最大的启迪就是不要眼高手低，别浮躁，脚踏实地的先从基础知识学起。
数据结构这门课程主要是理解，只有理解了记忆就简单了，代码不能靠死记硬背，即使背了过了也没有意义。还有一点就是基础差没关系，数据结构的知识点都是很容易理解的，学习过程中不要遗漏知识点，因为编写代码过程中，经常就是因为一个知识点的不会而导致整段代码模糊不清。
就这次课程设计而言，自己学到了很多，JAVA也提高了不少，做不到特别完美，希望在以后的学习过程中能弥补欠缺。
参考文献
[1] 严蔚敏, 吴伟民. 数据结构. 清华大学出版社, 2005.11
[2] 谭浩强. C语言程序设计. 清华大学出版社, 2005.11
[3] 范辉. Visual C++程序设计. 高等教育出版社
[4] Robert L. Kruse,Alexandeer J. Ryba编.Data Structures and Program Design in C++.高等教育出版社2002（影印版）
[5]Mark Allen Weiss著，冯舜玺译. Data Structures and Algorithm Analysis in Java (Second Edition).机械工业出版社
[6]Clifford A. Shaffer ， A Practical Introduction to Data Structures and Algorithm Analysis(2nd Edition)，电子工业出版社，2005.7
[7]Richard F. Gilberg，Behrouz A. Forouzan，Data Structures-A Pseudocode Approach with C++，人民邮电出版社，2002.1
山东建筑大学计算机科学与技术学院
课程设计指导教师评语
班级： 学生姓名： 学号：
指导教师评语（包括工作态度，遵守纪律；基本理论、知识、技能；独立工作能力和分析解决问题的能力；完成任务情况及水平）：
学生成绩（百分制）：
指导教师签名： 年 月 日