数据结构课设

交通运输学院

数据结构与算法课程设计

学 院 交通运输学院 班 级 信管1401

姓 名 王龙 学 号 201400717

成 绩 指导老师 刘应东

2017 年 1 月 3 日

交通运输学院课程设计

兰州交通大学交通运输学院课程设计任务书

所在系： 信息管理系 课程名称：数据结构与算法课程设计 指导教师（签名）： 专业班级：信管1401 学生姓名： 王龙 学号：201400717

一、课程设计题目 数据结构与算法课程设计 二、课程设计的目的 (1)培养学生正确的设计思想，对待问题严肃认真、实事求是的科学态度和勇于探索的创新精神。 (2)培养学生将所学的面向对象程序设计理论知识熟练运用于实践，并达到分析和解决问题的能力。 (3)通过课程设计实践，训练并提高学生在统筹全局、结构设计、查阅设计资料和计算机编程方面的能力。 (4)培养学生掌握规范的设计报告的撰写能力。 (5) 通过课程设计,熟悉数据结构的特点、逻辑结构和物理结构，熟悉JAVA编程开发环境以及程序调试方法。 三、课程设计的主要内容和要求 (1)熟悉JAVA编程开发环境Eclipse。要求学会调试程序、改正程序中错误。 (2)熟悉JAVA语法。掌握顺序、分支和循环语法结构，掌握类的定义和应用。 (3)熟悉类的语法结构。掌握类的定义和应用，掌握类的继承性、封装性和多态性，掌握接口、委托的定义和使用。 (4)熟悉各种简答排序和查找的算法。 (5)熟悉数据结构中线性表、树和图的逻辑结构和物理结构。 四、工作进度安排 第1天：分析理解题目，对课程设计的步骤与内容有一个初步的规划； 第2天：查阅参考资料，进一步加深对题目的理解，确定解题思路与方法； 第3-8天：编写指导教师布置的题目。 第10-11天：完善程序，认真完成课程设计报告。 五、主要参考文献 (1) 刘小晶等著.数据结构——java语言描述（第2版）.北京：清华大学出版社，2015 审核批准意见 系主任（签字） 年 月 日 交通运输学院课程设计

指导教师评语及成绩

指 导 教 师 评 语 成 绩 导师签字： 年 月 日

交通运输学院课程设计

目录

1.线性表： ...................................................................................................................................... 2

2.链表： .......................................................................................................................................... 4

3.栈： .............................................................................................................................................. 9

4.队列： ........................................................................................................................................ 12

5.二叉树和树： ............................................................................................................................ 13

6.查找排序： ................................................................................................................................ 19

7.图： ............................................................................................................................................ 28

1

交通运输学院课程设计

1.线性表：

public interface ilist {

public void clear();

public boolean isEmpty(); public int length();

public Object get(int i) throws Exception;

public void insert(int i,Object x) throws Exception; public void remove(int i) throws Exception; public int indexOf(Object x); public void display(); }

public class saqQ implements ilist {

private Object[]listElem; private int curLen; public saqQ(int max) {

curLen=0;

listElem=new Object[max]; }

public void clear() {

curLen=0; }

public boolean isEmpty() {

return curLen==0; }

public int length() {

// TODO Auto-generated method stub return curLen; }

public Object get(int i) throws Exception{ // TODO Auto-generated method stub if(i<0||i>curLen-1)

2

交通运输学院课程设计

throw new Exception(\"di\"+i+\"yuansubucunzai\"); }

return listElem[i]; }

public void insert(int i, Object x) throws Exception { if(curLen==listElem.length )

throw new Exception(\"yiman\"); if(i<0||i>curLen)

throw new Exception(\"BUHEF\"); for(int j=curLen;j>i;j--)

listElem[j]=listElem[j-1]; listElem[i]=x; curLen++; }

public void remove(int i) {

// TODO Auto-generated method stub if(i<0||i>curlen-1)

throw new Exception(\"删除位置不合法！\"); for(int j=i;jpublic int indexOf(Object x) {

// TODO Auto-generated method stub int j=0;

while(jif(jreturn j=-1; }

public void display() {

// TODO Auto-generated method stub for(int j=0;jSystem.out.print(listElem[j]+\"\"); }

System.out.println(); }

3

交通运输学院课程设计

public static void main(String[] args) throws Exception {

// TODO Auto-generated method stub

saqQ l=new saqQ(10); l.insert(0, 'a'); l.insert(1, 'z'); l.insert(2, 'd'); l.insert(3, 'm'); l.insert(4, 'z'); int o=l.indexOf('z'); if(o!=-1)

System.out.print(); else

System.out.print(\"顺序表中第一次出现值为’z\"的数据元素的位置为：”+o);

2.链表：

public class Node { public Object data; public Node next; public Node() {

this(null, null);}

public Node(Object data) { this(data, null);}

public Node(Object data, Node next) { this.data = data; this.next = next;} }

public interface ilist {

public void clear();

public boolean isEmpty(); public int length();

4

交通运输学院课程设计

public Object get(int i) throws Exception;

public void insert(int i,Object x) throws Exception; public void remove(int i) throws Exception; public int indexOf(Object x); public void display(); }

import java.util.Scanner;

public class linklist implements ilist {

public Node head;

public linklist() {

head=new Node(); }

public linklist(int n,boolean order) throws Exception {

this(); if(order)

create1(n); else

create2(n); }

public void create1(int n) throws Exception {

Scanner sc=new Scanner(System.in); for(int j=0;jinsert(length(),sc.next()); } }

public void insert(int i,Object x) throws Exception {

Node p=head; int j=-1;

while(p!=null&&jp=p.next; ++j;

5

交通运输学院课程设计

}

if(j>i-1||p==null)

throw new Exception(\"buhefa\"); Node s=new Node(x); s.next=p.next; p.next=s; }

public void create2(int n) throws Exception {

Scanner sc=new Scanner(System.in); for(int j=0;jinsert(0,sc.next()); } }

public int length() {

Node p=head.next; int length=0; while(p!=null) {

p=p.next; ++length; }

return length; }

public void clear() {

head.data=null; head.next=null; }

public boolean isEmpty() {

return head.next==null; }

public Object get(int i) throws Exception {

Node p=head.next; int j=0;

while(p!=null&&jp=p.next; ++j;

6

交通运输学院课程设计

}

if(j>i||p==null)

throw new Exception(\"ekekw\"); return p.data; }

public void remove(int i) throws Exception {

Node p=head; int j=-1;

while(p.next!=null&&jp=p.next; ++j; }

if(p.next!=null||jthrow new Exception(\"buhefa\"); }

p.next =p.next.next; }

public int indexOf(Object x) {

Node p=head.next; int j=0;

while(p!=null&&!p.data.equals(x)) {

p=p.next; ++j; }

if(p!=null) return j; else

return -1; }

public void display() {

Node p=head.next; while(p!=null) {

System.out.print(p.data+\"\"); p=p.next;

7

交通运输学院课程设计

}

System.out.println(); } }

public static void main(String[] args) throws Exception { int n=10;

linklist L=new linklist(); for(int i=0;iL.insert(i, i); }

System.out.println(\"请输入i的值：\"); int i=new Scanner(System.in).nextInt(); if(i>0&&i<=n)

System.out.println(\"第\"+i+\"个元素的直接前驱是:\"+L.get(i-1)); else

System.out.println(\"第\"+i+\"个元素的直接前驱是不存在！\");

}

}

import java.util.Scanner; public class Example2_5 {

public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int m = 0, n = 0;

System.out.println(\"请输入LA中结点的个数：\"); m = sc.nextInt();

System.out.println(\"请按非递减的方式输入\" + m + \"个数字：\"); LinkList LA = new LinkList(m, true);

System.out.println(\"请输入LB中结点的个数：\"); n = sc.nextInt();

System.out.println(\"请按非递减的方式输入\" + n + \"个数字：\"); LinkList LB = new LinkList(n, true);

System.out.println(\"将单链表LA和LB归并后，新的单链表LA中的各个结点为：\");

8

交通运输学院课程设计

mergeList_L(LA, LB).display();}

public static LinkList mergeList_L(LinkList LA, LinkList LB) { Node pa = LA.head.next; Node pb = LB.head.next; Node pc = LA.head; int da, db;

while (pa != null && pb != null) {

da = Integer.valueOf(pa.data.toString()); db = Integer.valueOf(pb.data.toString()); if (da <= db) { pc.next=pa; pc = pa;

pa = pa.next; } else {

pc.next=pb; pc = pb;

pb = pb.next;}}

pc.next=(pa != null ? pa : pb); return LA; } }

3.栈：

public interface IStack {

public void clear();

public boolean isEmpty(); public int length(); public Object peek();

public void push(Object x)throws Exception; public Object pop();

9

交通运输学院课程设计

}

import java.util.Scanner;

public class LinkStack implements IStack{ private Node top; public void clear() {

top=null; }

public boolean isEmpty() {

return top==null; }

public int length() {

Node p=top; int length=0; while(p!=null) {

p=p.next; length++; }

return length; }

public Object peek() {

if(!isEmpty())

return top.data; else

return null; }

public void push(Object x) {

Node p=new Node(x); p.next=top; top=p; }

public Object pop() {

if(isEmpty()) return null; else {

10

交通运输学院课程设计

Node p=top; top=top.next; return p.data; } }

public void display() {

Node p=top; while(p!=null) {

System.out.print(p.data.toString()+\"\"); p=p.next; } } }

import java.util.Scanner;

public class example {

public static void main(String[] args) throws Exception {

LinkStack l=new LinkStack(); l.clear();

for(int i=0;i<13;i++) l.push(i); l.display();

System.out.println(); l.pop(); l.display();

System.out.println(\"当前栈的长度为：\"+l.length()+\"，栈的栈顶元素是：\"+l.peek()); } }

11

交通运输学院课程设计

4.队列：

public interface IQueue { public void clear();

public boolean isEmpty(); public int length(); public Object peek();

public void offer(Object x)throws Exception; public Object poll(); }

package duilie;

import lianbiao.Node;

public class LinkQueue implements IQueue{ private Node front; private Node rear; public LinkQueue() {

front=rear=null; }

public void clear() {

front = rear=null; }

public boolean isEmpty() {

return front==null; }

public int length() {

Node p=front; int length=0; while(p!=null) {

p=p.next; length++;

12

交通运输学院课程设计

}

return length; }

public Object peek() {

if(front!=null)

return front.data; else

return null; }

public void offer(Object x) {

Node p=new Node(x); if(front!=null) {

rear.next=p; rear=p; } }

public Object poll() {

if(front!=null) {

Node p=front; front=front.next; if(p==rear) rear=null; return p.data; } else

return null; } }

5.二叉树和树：

import duilie.LinkQueue; import zhan.LinkStack; public class BiTree {

private BiTreeNode root; public BiTree() {

13

交通运输学院课程设计

this.root=null; }

public BiTree(BiTreeNode root) {

this.root=root; }

public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) {}

private static int index=0;

public void preRootTraverse(BiTreeNode T) {

if(T!=null) {

System.out.print(T.data); preRootTraverse(T.lchild); preRootTraverse(T.rchild); } }

public void inRootTraverse(BiTreeNode T) {

if(T!=null) {

inRootTraverse(T.lchild); System.out.print(T.data); inRootTraverse(T.rchild); } }

public void postRootTraverse(BiTreeNode T) {

if(T!=null) {

postRootTraverse(T.lchild); postRootTraverse(T.rchild); System.out.print(T.data); } }

public void levelTraverse() {

BiTreeNode T=root; if(T!=null) {

14

交通运输学院课程设计

LinkQueue L=new LinkQueue(); L.offer(T);

while(!L.isEmpty()) {

T=(BiTreeNode)L.poll(); System.out.print(T.data); if(T.lchild!=null) L.offer(T.lchild); if(T.rchild!=null) L.offer(T.rchild); } } }

public BiTreeNode getRoot() {

return root; }

public void setRoot(BiTreeNode root) {

this.root=root; } }

public class BiTreeNode { public Object data;

public BiTreeNode lchild,rchild; public BiTreeNode() {

this(null); }

public BiTreeNode(Object data) {

this(data,null,null); }

public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild) {

this.data=data; this.lchild=lchild; this.rchild=rchild; } }

public class debugBiTree {

15

交通运输学院课程设计

public BiTree createBiTree() {

BiTreeNode d=new BiTreeNode('D'); BiTreeNode g=new BiTreeNode('G'); BiTreeNode h=new BiTreeNode('H');

BiTreeNode e=new BiTreeNode('E',g,null); BiTreeNode b=new BiTreeNode('B',d,e); BiTreeNode f=new BiTreeNode('F',null,h); BiTreeNode c=new BiTreeNode('C',f,null); BiTreeNode a=new BiTreeNode('A',b,c); return new BiTree(a); }

public static void main(String[] args) { debugBiTree db=new debugBiTree(); BiTree bt=db.createBiTree(); BiTreeNode root=bt.getRoot();

System.out.println(\"先根遍历的序列为：\"); bt.preRootTraverse(root); System.out.println();

System.out.println(\"中根遍历的序列为：\"); bt.inRootTraverse(root); System.out.println();

System.out.println(\"后根遍历的序列为：\"); bt.postRootTraverse(root); System.out.println();

System.out.println(\"层次遍历的序列为：\"); bt.levelTraverse(); System.out.println(); }

}

public class Example5_3 {

public int getDepth(BiTreeNode T) { if (T != null) {

int lDepth = getDepth(T.lchild);

16

交通运输学院课程设计

int rDepth = getDepth(T.rchild);

return 1 + (lDepth > rDepth ? lDepth : rDepth);} return 0;}

public int getDepth1(BiTreeNode T) { if (T==null) return 0;

else if (T.lchild==null&&T.rchild==null) return 1; else

return 1 + (getDepth1(T.lchild)> getDepth1(T.rchild)? getDepth1(T.lchild) : getDepth1(T.rchild));} public static void main(String[] args) {

BiTree biTree = new BiTreeCreator().createBiTree(); BiTreeNode root = biTree.getRoot(); Example5_3 e = new Example5_3();

System.out.println(\"树中的深度为： \" + e.getDepth(root)); System.out.println(\"树中的深度为： \" + e.getDepth1(root)); }

public class Example5_2 {

public int countNode(BiTreeNode T) { int count = 0; if (T != null) { ++count;

count += countNode(T.lchild); count += countNode(T.rchild); } return count;}

public int countNode1(BiTreeNode T){ if (T==null) return 0; else

return countNode1(T.lchild)+countNode1(T.rchild)+1; } public static void main(String[] args) {

BiTree biTree = new BiTreeCreator().createBiTree(); BiTreeNode root = biTree.getRoot(); Example5_2 e = new Example5_2();

System.out.println(\"树中的结点个数为： \" + e.countNode(root)); System.out.println(\"树中的结点个数为： \" + e.countNode1(root)); } }

17

交通运输学院课程设计

public class HuffmanNode { public int weight; public int flag;

public HuffmanNode parent, lchild, rchild; public HuffmanNode() { this(0);}

public HuffmanNode(int weight) { this.weight = weight; flag = 0;

parent = lchild = rchild = null; }} //

public class HuffmanTree {

public int[][] huffmanCoding(int[] W) { int n = W.length; int m = 2 * n - 1;

HuffmanNode[] HN = new HuffmanNode[m]; int i;

for (i = 0; i < n; i++)

HN[i] = new HuffmanNode(W[i]); for (i = n; i < m; i++) {

HuffmanNode min1 = selectMin(HN, i - 1); min1.flag=1;

HuffmanNode min2 = selectMin(HN, i - 1); min2.flag=1;

HN[i] = new HuffmanNode(); min1.parent=HN[i]; min2.parent=HN[i]; HN[i].lchild=min1; HN[i].rchild=min2;

HN[i].weight=min1.weight + min2.weight; } int[][] HuffCode = new int[n][n]; for (int j = 0; j < n; j++) { int start = n - 1;

for (HuffmanNode c = HN[j], p = c.parent; p != null; c = p, p = p.parent)

if (p.lchild.equals(c))

HuffCode[j][start--] = 0; else

HuffCode[j][start--] = 1;

18

交通运输学院课程设计

HuffCode[j][start] = -1; } return HuffCode; }

private HuffmanNode selectMin(HuffmanNode[] HN, int end) { HuffmanNode min = HN[end];

for (int i = 0; i <= end; i++) { HuffmanNode h = HN[i];

if (h.flag == 0 && h.weight < min.weight) min = h; } return min; }

public static void main(String[] args) {

int[] W = { 23, 11, 5, 3, 29, 14, 7, 8 }; HuffmanTree T = new HuffmanTree(); int[][] HN = T.huffmanCoding(W);

System.out.println(\"赫夫曼编码为：\"); for (int i = 0; i < HN.length; i++) { System.out.print(W[i] + \"\");

for (int j = 0; j < HN[i].length; j++) { if (HN[i][j] == -1) {

for (int k = j + 1; k < HN[i].length; k++) System.out.print(HN[i][k]); break; }

System.out.println(); } }

6.查找排序：

public class ElementType { public String data;

public ElementType(String data) {

this.data=data; }

public ElementType() { }

public String toString()

19

交通运输学院课程设计

{

return data; } }

public class KeyType implements Comparable{ public int key; public KeyType() { }

public KeyType(int key) {

this.key=key; }

public String toString() {

return key+\"\"; }

public int compareTo(KeyType another) {

int thisVal=this.key;

int anotherVal=another.key;

return (thisValpublic class RecordNode { public Comparable key; public Object element;

public RecordNode(Comparable key) {

this.key=key; }

public RecordNode(Comparable key,Object element) {

this.key=key;

this.element=element; }

20

交通运输学院课程设计

}

package paixu;

public class SeqList {

public RecordNode[] r; public int curlen;

public SeqList(int maxSize) {

this.r=new RecordNode[maxSize]; this.curlen=0; }

public void insert(int i,RecordNode x)throws Exception {

if(curlen==r.length)

throw new Exception(\"顺序表已满!\"); if(i<0||i>curlen)

throw new Exception(\"插入位置不合理\"); for(int j=curlen;j>i;j--) {

r[j]=r[j-1]; }

r[i]=x;

this.curlen++; }

public int length() {

return curlen; }

public void display() {

for(int j=0;jSystem.out.print(r[j].key+\"\"); }

System.out.println(); }

public void insertSort() {

RecordNode temp; int i,j;

for(i=1;i21

交通运输学院课程设计

temp=r[i];

for(j=i-1;j>=0&&temp.key.compareTo(r[j].key)<0;j--) {

r[j+1]=r[j]; }

r[j+1]=temp; } }

public void shellSort(int[] d) {

RecordNode temp; int i,j;

for(int k=0;kint dk=d[k];

for(i=dk;itemp=r[i];

for(j=i-dk;j>=0&&temp.key.compareTo(r[j].key)<0;j-=dk) {

r[j+dk]=r[j]; }

r[j+dk]=temp; } } }

public void bubbleSort() {

RecordNode temp; boolean flag=true;

for(int i=1;iflag=false;

for(int j=0;jif(r[j].key.compareTo(r[j+1].key)>0) {

temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; flag=true; } } }

22

交通运输学院课程设计

}

public void sift(int low,int high) {

int i=low; int j=2*i+1;

RecordNode temp=r[i]; while(jif(j0) {

j++; }

if(temp.key.compareTo(r[j].key)>0) {

r[i]=r[j]; i=j; j=2*i+1; } else{

j=high+1; } }

r[i]=temp; }

public void heapSort() {

System.out.println(\"堆排序\"); int n=this.curlen; RecordNode temp;

for(int i=n/2-1;i>=0;i--) {

sift(i,n); }

for(int i=n-1;i>0;i--) {

temp=r[0]; r[0]=r[i]; r[i]=temp; sift(0,i); } }

public int seqSearch(Comparable key) {

23

交通运输学院课程设计

int i=0,n=length();

while(ii++; }

if(ireturn i; else

return -1; }

public int binarySearch(Comparable key) {

if(length()>0) {

int low=0,high=length()-1; while(low<=high) {

int mid=(low+high)/2;

if(r[mid].key.compareTo(key)==0) return mid; else

if(r[mid].key.compareTo(key)>0) high=mid-1; else

low=mid+1; } }

return -1; } }

package paixu;

import java.util.Scanner;

import paixu.*;

public class Exercise1 {

public static void main(String[] args) throws Exception { // TODO Auto-generated method stub int[] d={52,39,67,95,70,8,25,52};

24

交通运输学院课程设计

int[] dlta={5,3,1}; int maxSize=20;

SeqList l=new SeqList(maxSize); for(int i=0;iRecordNode r=new RecordNode(d[i]); l.insert(l.length(), r); }

System.out.println(\"排序前:\"); l.display();

System.out.println();

Scanner s=new Scanner(System.in); int xz=s.nextInt(); switch(xz) {

case 1:

l.insertSort(); break; case 2:

l.shellSort(dlta); break; case 3:

l.bubbleSort(); break; case 4:

l.heapSort(); break; }

System.out.println(\"排序后：\"); l.display();

System.out.println(\"两种查找方式查找数字67的位置：\"); int num1=l.seqSearch(67); int num2=l.binarySearch(67);

System.out.println(\"用顺序查找67的位置是\"+(num1+1)); System.out.println(\"用二分查找67的位置是：\"+(num2+1));

}

}

25

交通运输学院课程设计

void tournamentSort() { TreeNode[] tree; int leafSize = 1;

while (leafSize < this.curlen) { leafSize *= 2; }

int TreeSize = 2 * leafSize - 1; int loadindex = leafSize - 1; tree = new TreeNode[TreeSize]; int j = 0;

for (int i = loadindex; i < TreeSize; i++) { tree[i] = new TreeNode(); tree[i].index=i;

if (j < this.curlen) { tree[i].active=1; tree[i].data=r[j++]; } else {

tree[i].active=0 ; } } int i = loadindex; while (i > 0) { j = i;

while (j < 2 * i) { if (tree[j + 1].active == ((tree[j].data).key.compareTo((tree[j + 1].data).key)) <= 0) { tree[(j - 1) / 2] = tree[j]; } else {

tree[(j - 1) / 2] = tree[j + 1]; } j += 2; } i = (i - 1) / 2; }

for (i = 0; i < this.curlen - 1; i++) { r[i] = tree[0].data; tree[tree[0].index].active=0;

updateTree(tree, tree[0].index); } r[this.curlen - 1] = tree[0].data; }

void updateTree(TreeNode[] tree, int i) { int j;

if (i % 2 == 0) {

tree[(i - 1) / 2] = tree[i - 1]; } else {

0 ||

26

交通运输学院课程设计

tree[(i - 1) / 2] = tree[i + 1]; } i = (i - 1) / 2; while (i > 0) {

if (i % 2 == 0) { j = i - 1; } else {

j = i + 1; }

if (tree[i].active == 0 || tree[j].active == 0) { if (tree[i].active == 1) {

tree[(i - 1) / 2] = tree[i]; } else {

tree[(i - 1) / 2] = tree[j]; } } else

if ((tree[i].data).key.compareTo((tree[j].data).key) <= 0) {

tree[(i - 1) / 2] = tree[i]; } else {

tree[(i - 1) / 2] = tree[j]; } i = (i - 1) / 2; } } public void sift(int low, int high) {

int i = low; int j = 2 * i + 1; RecordNode temp = r[i]; while (j < high) {

if (j < high - 1 && r[j].key.compareTo(r[j + 1].key) > 0) { j++; }

if (temp.key.compareTo(r[j].key) > 0) { r[i] = r[j]; i = j;

j = 2 * i + 1; } else {

j = high + 1; } } r[i] = temp; } public void heapSort() { int n = this.curlen; RecordNode temp;

for (int i = n / 2 - 1; i >= 0; i--) { sift(i, n); }

for (int i = n - 1; i > 0; i--) { temp = r[0]; r[0] = r[i]; r[i] = temp;

sift(0, i); } }

public void merge(RecordNode[] r, RecordNode[] order, int h, int m, int

27

交通运输学院课程设计

t) {

int i = h, j = m + 1, k = h; while (i <= m && j <= t) {

if (r[i].key.compareTo(r[j].key) <= 0) { order[k++] = r[i++]; } else {

order[k++] = r[j++]; } } while (i <= m) {

order[k++] = r[i++]; } while (j <= t) {

order[k++] = r[j++]; } }

public void mergepass(RecordNode[] r, RecordNode[] order, int s, int n) {

System.out.print(\"子序列长度s=\" + s + \"\"); int p = 0;

while (p + 2 * s - 1 <= n - 1) {

merge(r, order, p, p + s - 1, p + 2 * s - 1); p += 2 * s; } if (p + s - 1 < n - 1) {

merge(r, order, p, p + s - 1, n - 1); } else {

for (int i = p; i <= n - 1; i++) {

order[i] = r[i]; } } }

7.图：

public class ArcNode { public int adjVex; public int value;

private ArcNode nextArc; public ArcNode() {

this(-1,0,null); }

public ArcNode(int adjVex) {

this(adjVex,0,null); }

public ArcNode(int adjVex,int value) {

this(adjVex,value,null); }

28

交通运输学院课程设计

public ArcNode(int adjVex,int value,ArcNode nextArc) {

this.value=value; this.adjVex=adjVex; this.nextArc=nextArc; } }

package tu;

public enum GraphKind { UDG; DG; }

package tu;

public interface IGraph { void createGraph(); int getVexNum(); int getArcNum();

Object getVex(int v) throws Exception; int locateVex(Object vex);

int firstAdjVex(int v) throws Exception; int nextAdjVex(int v,int w); }

package tu;

public class VNode {

public Object firstArc; public VNode() {

this(null,null); }

public VNode(Object data) {

this(data,null); }

public VNode(Object data,ArcNode firstArc) {

this.data=data;

this.firstArc=fitstArc;

29

交通运输学院课程设计

} }

package tu;

import java.util.Scanner;

public class MGraph implements IGraph{

public final static int INFINITY=Integer.MAX_VALUE; private GraphKind kind; private int vexNum,arcNum; private Object[] vexs; private int[][] arcs; public MGraph() {

this(null,0,0,null,null); }

public MGraph(GraphKind kind,int vexNum,int arcNum,Object[] vexs,int[][] arcs) {

this.kind=kind; this.vexNum=vexNum; this.arcNum=arcNum; this.vexs=vexs; this.arcs=arcs; }

public void createUDG() {}

public void createDG() {

Scanner sc=new Scanner(\"请分别输入图的定点数，边数:\"); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs=new VNode[vexNum];

vexs[v]=new VNode(sc.next());

System.out.println(\"请输入各边的顶点\"); for(int k=0;kint v=locateVex(sc.next()); int u=locateVex(sc.next()); }

addArc(v,u,0); }

30

交通运输学院课程设计

public int getVexNum() {

return vexNum; }

public int getArcNum() {

return arcNum; }

public int locateVex(Object vex) {

for(int v=0;vpublic Object getVex(int v)throws Exception {

if(v<0&&v>=vexNum)

throw new Exception(\"第\"+v+\"个顶点不存在\"); return vexs[v]; }

public int firstAdjVex(int v)throws Exception {

if(v<0&&v>=vexNum)

throw new Exception(\"第\"+v+\"个顶点不存在\"); for(int j=0;jif(arcs[v][j]!=0&&arcs[v][j]public int[][] getArcs() {

return arcs; }

public Object[] getVexs() {

return vexs; }

public void createGraph() {

Scanner sc=new Scanner(System.in); System.out.println(\"请输入图的类型:\");

31

交通运输学院课程设计

}

}

GraphKind kind=GraphKind.valueOf(sc.next()); switch(kind) {

case UDG:

createUDG(); break; case DG:

createDG(); break; }

public class Example6_2 {

private boolean[] visited; private int i = 0;

private boolean find = false;

public void findPath(IGraph G, int u, int v, int k) throws Exception {

visited = new boolean[G.getVexNum()]; for (int w = 0; w < G.getVexNum(); w++) visited[w] = false; find_DFS(G, u, v, k); if (find)

System.out.println(G.getVex(u)+\"和\"+G.getVex(v)+\"之间存在一条长度为\"+k+ \"的简单路径\"); else

System.out.println(G.getVex(u)+\"和\"+G.getVex(v)+\"之间不存在一条长度为\"+k+ \"的简单路径\"); }

private void find_DFS(IGraph G, int u, int v, int k) throws Exception {

if (i == k && u == v) find = true; else if (!find) {

visited[u] = true;

for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w)) if (!visited[w]) { if (i < k) { ++i;

find_DFS(G, w, v, k); } else

32

交通运输学院课程设计

break; } --i; }}

public static void main(String[] args) throws Exception { ArcNode ab = new ArcNode(1); VNode A = new VNode(\"A\ ArcNode bc = new ArcNode(2);

ArcNode be = new ArcNode(4, 0, bc); VNode B = new VNode(\"B\ ArcNode cd = new ArcNode(3); VNode C = new VNode(\"C\ ArcNode de = new ArcNode(4); VNode D = new VNode(\"D\ ArcNode ef = new ArcNode(5); VNode E = new VNode(\"E\ ArcNode fa = new ArcNode(0);

ArcNode fb = new ArcNode(1, 0, fa); VNode F = new VNode(\"F\

VNode[] vexs = { A, B, C, D, E, F };

ALGraph G = new ALGraph(GraphKind.DG, 6, 8, vexs); Example6_2 e = new Example6_2(); e.findPath(G, 0, 5, 3); } }

public class ShortestPath_DIJ { private boolean[][] P; private int[] D;

public final static int INFINITY = Integer.MAX_VALUE; public void DIJ(MGraph G, int v0) { int vexNum = G.getVexNum();

P = new boolean[vexNum][vexNum]; D = new int[vexNum];

boolean[] finish = new boolean[vexNum]; for (int v = 0; v < vexNum; v++) { finish[v] = false;

D[v] = G.getArcs()[v0][v];

for (int w = 0; w < vexNum; w++) P[v][w] = false; if (D[v] < INFINITY) { P[v][v0] = true;

P[v][v] = true; } } D[v0] = 0;

33

交通运输学院课程设计

finish[v0] = true; int v = -1;

for (int i = 1; i < vexNum; i++) { int min = INFINITY;

for (int w = 0; w < vexNum; w++) if (!finish[w])

if (D[w] < min) { v = w;

min = D[w]; } finish[v] = true;

for (int w = 0; w < vexNum; w++)

if (!finish[w] && G.getArcs()[v][w] < INFINITY && (min + G.getArcs()[v][w] < D[w])) { D[w] = min + G.getArcs()[v][w];

System.arraycopy(P[v], 0, P[w], 0, P[v].length); P[w][w] = true; } } } public int[] getD() { return D; }

public boolean[][] getP() { return P; }

public static void main(String[] args) throws Exception { MGraph G = GenerateGraph.generateMGraph(); ShortestPath_DIJ dij = new ShortestPath_DIJ(); dij.DIJ(G, 0);

dij.display(G); }

public void display(MGraph G) throws Exception { if (D != null) {

System.out.println(\"各个顶点到v0的最短路径上的点及最短距离分别是：\");

for (int i = 0; i < P.length; i++) {

System.out.print(\"v0 - \" + G.getVex(i) + \": \"); for (int j = 0; j < P[i].length; j++) { if (P[i][j])

System.out.print(G.getVex(j) + \"\\"); } System.out.println(\"最短距离为： \" + D[i]); } }

34