精华内容
下载资源
问答
  • Java数据结构和算法》第二 Robert lafore 编程作业 第三章 参考 https://blog.csdn.net/zhch152/article/details/7906162 3.1 bubbleSort.java程序(清单3.1)和BubbleSort专题applet中,in索引变量都是从...

    《Java数据结构和算法》第二版 Robert lafore  编程作业 第三章

    参考 https://blog.csdn.net/zhch152/article/details/7906162

    1. 3.1 bubbleSort.java程序(清单3.1)和BubbleSort专题applet中,in索引变量都是从左到
                右移动的,直到找到最大数据项并把它移动到右边的out变量外。修改bubbleSort()方法,
                使它成为双向移动的。这样,in索引先像以前一样,将最大的数据项从左移到右,当它到
                达out变量位置时,它掉头并把最小的数据项从右移到左。需要两个外部索引变量,一个在
                右边(以前的out变量),另一个在左边。

       //3.1
         public void bubbleSort()
            {
            int left ,right, in;
            for(right =nElems-1,left=0;right>left;right--,left++){
      
               //从左到右选出最大
            for(in= left;in<right;in++){
                  com++;//比较次数
                  if(a[in]>a[in+1]){
                     swap++;//交换次数
                     swap(in,in+1);
                  }
               }
               //从右到左选出最小
               for(in--;in>left;in--){
                  com++;
                  if(a[in-1]>a[in]){
                     swap++;
                     swap(in,in-1);
                  }
               }
            }

      3.2    在isertSort.java程序(清单3.3)中给ArrayIns类加一个median()方法.这个方法将返回
                数组的中间值.(回忆一下,数组中一半数据项比中间值大,一半数据项比中间值小。)

        /**
             * 3.2返回数组的中间值 如果数组长度为奇数 则放回中间值 否则取两个中间值的平均值
             * @return
             */
            public long media(){
               //将数组排序
               this.insertionSort();
               int midIndex =nElems/2;
               if(nElems%2 == 0){
                  return nElems==0?0:(a[midIndex]+a[midIndex-1])/2;
               }else{
                  return a[midIndex];
               }
      
            }

      3.3    在insertSort.java程序(清单3.3)中增加一个名为noDups()的方法,这个方法从已经有
               序的数组中删掉重复的数据项而不破坏有序性。(可以用insertionSort()方法对数据排序,
               或者也可以简单地用main()方法将数据有序地插入到表中。)一种解决方法是每发现一个重
               复的数据,就从这个位置开始到数组结尾都向前移动一个位置,但这样就导致消耗很长的
               O(N2)的时间级,起码在有很多重复数据项的情况下是这样的。在设计的算法中,不论有多
               少重复数据,要确保数据项最多只能移动一次。这样算法只消耗O(N)数量级的时间。

    2.  /**
             * 3.3删除重复元素(已排序)
             */
            public void noDups(){
               //先循环找出重复元素并设为空
               if(nElems ==0 ) return;
               long lastVal = a[0];
               int newElems = nElems;
               int lastDupIndex = -1;//记录上个重复的索引
               for (int i=1;i< nElems;i++){
                  if(a[i] == lastVal){//等于
                     newElems--;
                     a[i]=0;//默认为0
                     if(lastDupIndex == -1){
                        lastDupIndex = i;
                     }
                  }else {//大于
                     lastVal = a[i];
                     if(lastDupIndex != -1){
                        a[lastDupIndex] =a[i];
                        a[i]=0;//默认为0
                        lastDupIndex++;
                     }
                  }
               }
               nElems =newElems;
            }

      3.4  还有一种简单排序算法是奇偶排序。它的思路是在数组中重复两趟扫描。第一趟扫描选择所有
               的数据项对,a[j]和a[j+1],j是奇数(j=1,3,5,……)。如果它们的关键字的值次序颠倒,就交
               换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2,4,6,……)。重复进行这样两趟
               的排序直到数组全部有序。用oddEvenSort()方法替换bubbleSort.java程序(清单3.1)中的
               bubbleSort()方法。确保它可以在不同数据量的排序中运行,还需要算出两趟扫描的次数。奇
               偶排序实际上在多处理器环境中很有用,处理器可以分别同时处理每一个奇数对,然后又同时
               处理偶数对。因为奇数对是彼此独立的,每一对都可以用不同的处理器比较和交换。这样可以非
               常快速地排序。

        //3.4 奇偶排序
            public void oddEventSort(){
              int count=0;
               boolean isChange = true;
               int start = 0;//0 偶交换 1 奇交换
               while (isChange){
                  count++;
                  isChange = false;
                  for(int i= start ;i<nElems-1;i+=2){
                     com++;
                     if(a[i]>a[i+1]){
                        swap++;
                        isChange = true;
                        swap(i,i+1);
                     }
                  }
                  start = start ==0?1:0;
               }
               System.out.println("count "+count);
      
            }

      3.6    有一个有趣的方法用来删除数组中相同的数据项。插入排序算法中用一个循环嵌套算法,将
               数组中的每一个数据项与其他数据项一一比较。如果要删除相同的数据项,可以这样做(参见第
               2章第2.6小节)。修改insertSort.java中的insertionSort()方法,使它可以在排序过程中
               删除相同的数据项。方法如下:当找到一个重复数据项的时候,通常用一个小于任何值的关键值
               来改写这个相同数据项(如果所有值都是正数,则可取-1)。于是,一般的插入排序算法就会像
               处理其他数据项一样,来处理这个修改了关键值的数据项,把它移到下标为0的位置。从现在开
               始,算法可以忽略这个数据项。下一个相同的数据项将被移到下标为1的位置,依此类推。排序
               完成后,所有相同的数据项(现在关键值为-1)都在数组的开头部分。可以改变数组的容量并
               把需要的数据前移动数组下标为0的位置。

      /**
             * 3.6 插入排序并移除重复数据
             */
            public void insertSortedNoDup() {
               int in,out;
               int dupNum = 0;
      
               for(out =0;out <nElems;out++){
                  long temp = a[out];
                  for(in =out-1;in>=0;in--){
                     com++;
                     if(temp > a[in]){
                        break;
                     }
                     else if(temp == a[in]){
                        for(int index = in;index >dupNum;index--){
                           a[index] =a[index -1];
                        }
                        dupNum++;
                        a[dupNum-1]=-1;
                        break;
                     }else {
                        swap++;
                        a[in + 1] = a[in];
                     }
                  }
                  a[in+1] = temp;
               }
               System.out.println("dupSize" +dupNum);
      
               for (int i=dupNum;i<nElems;i++){
                  a[i-dupNum] = a[i];
               }
               nElems -=dupNum;
            }

       

    展开全文
  • Java数据结构和算法 Robert lafore 编程作业 章 /* 13.1 修改bfs.java程序(清单13.2),通过广度优先搜索找到最小生成树,在 mst.java程序(清单13.3)中,这个工作是由深度优先搜索完成的...

    《Java数据结构和算法》第二版 Robert lafore 编程作业 第十三章

    /*
    	13.1 修改bfs.java程序(清单13.2),通过广度优先搜索找到最小生成树,在
    		 mst.java程序(清单13.3)中,这个工作是由深度优先搜索完成的。在
    		 main()中,创建带有9个顶点和12条边的图,然后找到最小生成树。
     */
    package chap13.pp1;
    
    // bfs.java
    // demonstrates breadth-first search
    // to run this program: C>java BFSApp
    
    class Queue {
    	private final int SIZE = 20;
    	private int[] queArray;
    	private int front;
    	private int rear;
    
    	// -------------------------------------------------------------
    	public Queue()            // constructor
    	{
    		queArray = new int[SIZE];
    		front = 0;
    		rear = -1;
    	}
    
    	// -------------------------------------------------------------
    	public void insert(int j) // put item at rear of queue
    	{
    		if (rear == SIZE - 1)
    			rear = -1;
    		queArray[++rear] = j;
    	}
    
    	// -------------------------------------------------------------
    	public int remove()       // take item from front of queue
    	{
    		int temp = queArray[front++];
    		if (front == SIZE)
    			front = 0;
    		return temp;
    	}
    
    	// -------------------------------------------------------------
    	public boolean isEmpty()  // true if queue is empty
    	{
    		return (rear + 1 == front || (front + SIZE - 1 == rear));
    	}
    	// -------------------------------------------------------------
    }  // end class Queue
    // //
    
    class Vertex {
    	public char label;        // label (e.g. 'A')
    	public boolean wasVisited;
    
    	// -------------------------------------------------------------
    	public Vertex(char lab)   // constructor
    	{
    		label = lab;
    		wasVisited = false;
    	}
    	// -------------------------------------------------------------
    }  // end class Vertex
    // //
    
    class Graph {
    	private final int MAX_VERTS = 20;
    	private Vertex vertexList[]; // list of vertices
    	private int adjMat[][];      // adjacency matrix
    	private int nVerts;          // current number of vertices
    	private Queue theQueue;
    
    	// ------------------------------------------------------------
    	public Graph()               // constructor
    	{
    		vertexList = new Vertex[MAX_VERTS];
    		// adjacency matrix
    		adjMat = new int[MAX_VERTS][MAX_VERTS];
    		nVerts = 0;
    		for (int j = 0; j < MAX_VERTS; j++)
    			// set adjacency
    			for (int k = 0; k < MAX_VERTS; k++)
    				// matrix to 0
    				adjMat[j][k] = 0;
    		theQueue = new Queue();
    	}  // end constructor
    		// -------------------------------------------------------------
    
    	public void addVertex(char lab) {
    		vertexList[nVerts++] = new Vertex(lab);
    	}
    
    	// -------------------------------------------------------------
    	public void addEdge(int start, int end) {
    		adjMat[start][end] = 1;
    		adjMat[end][start] = 1;
    	}
    
    	// -------------------------------------------------------------
    	public void displayVertex(int v) {
    		System.out.print(vertexList[v].label);
    	}
    
    	// -------------------------------------------------------------
    	// ===============================================================
    	// 编程作业 13.1
    	public void mst()                   // breadth-first search
    	{                                // begin at vertex 0
    		vertexList[0].wasVisited = true; // mark it
    		// displayVertex(0); // display it
    		theQueue.insert(0);              // insert at tail
    		int v2;
    
    		while (!theQueue.isEmpty())     // until queue empty,
    		{
    			int v1 = theQueue.remove();   // remove vertex at head
    			// until it has no unvisited neighbors
    			while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {   // get one,
    				vertexList[v2].wasVisited = true;  // mark it
    				displayVertex(v1);
    				displayVertex(v2);                 // display it
    				System.out.print(" ");
    				theQueue.insert(v2);               // insert it
    			}   // end while
    		}  // end while(queue not empty)
    
    		// queue is empty, so we're done
    		for (int j = 0; j < nVerts; j++)
    			// reset flags
    			vertexList[j].wasVisited = false;
    	}  // end bfs()
    
    	// -------------------------------------------------------------
    	// ===============================================================
    	// returns an unvisited vertex adj to v
    	public int getAdjUnvisitedVertex(int v) {
    		for (int j = 0; j < nVerts; j++)
    			if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
    				return j;
    		return -1;
    	}  // end getAdjUnvisitedVertex()
    		// -------------------------------------------------------------
    }  // end class Graph
    // //
    
    public class MSTApp {
    	public static void main(String[] args) {
    		Graph theGraph = new Graph();
    		theGraph.addVertex('A');    // 0 (start for bfs)
    		theGraph.addVertex('B');    // 1
    		theGraph.addVertex('C');    // 2
    		theGraph.addVertex('D');    // 3
    		theGraph.addVertex('E');    // 4
    
    		theGraph.addEdge(0, 1);     // AB
    		theGraph.addEdge(0, 2);     // AC
    		theGraph.addEdge(0, 3);     // AD
    		theGraph.addEdge(0, 4);     // AE
    		theGraph.addEdge(1, 2);     // BC
    		theGraph.addEdge(1, 3);     // BD
    		theGraph.addEdge(1, 4);     // BE
    		theGraph.addEdge(2, 3);     // CD
    		theGraph.addEdge(2, 4);     // CE
    		theGraph.addEdge(3, 4);     // DE
    
    		System.out.print("Minimum spanning tree: ");
    		theGraph.mst();             // minimum spanning tree
    		System.out.println();
    	}  // end main()
    }  // end class BFSApp
    // //
    
    


     

    /*
    	13.2 修改dfs.java程序(清单13.1),用邻接表而不是邻接矩阵执行深度优先
    		 搜索。可以通过修改第5章linkList2.java程序(清单5.2)的Link类和
    		 LinkList类得到链表。修改LinkList中的find()方法,搜索一个未访问的
    		 顶点,而不是一个关键字值。
     */
    package chap13.pp2;
    
    // dfs.java
    // demonstrates depth-first search
    // to run this program: C>java DFSApp
    class Vertex {
    	public char label;        // label (e.g. 'A')
    	public boolean wasVisited;
    
    	// -------------------------------------------------------------
    	public Vertex(char lab)   // constructor
    	{
    		label = lab;
    		wasVisited = false;
    	}
    	// -------------------------------------------------------------
    }  // end class Vertex
    // //
    
    class Link {
    	public Vertex vertex;              // data item (key)
    	public Link next;              // next link in list
    
    	// -------------------------------------------------------------
    
    	public Link(Vertex data) // constructor
    	{
    		this.vertex = data;
    	}
    
    	// -------------------------------------------------------------
    	public void displayLink()      // display ourself
    	{
    		System.out.print(vertex.label);
    	}
    }  // end class Link
    // //
    
    class LinkList {
    	public Link first;            // ref to first link on list
    	public Link last;
    
    	// -------------------------------------------------------------
    	public LinkList(Vertex c)              // constructor
    	{
    		Link newLink = new Link(c);
    		last = first = newLink;               // no links on list yet
    	}
    
    	// -------------------------------------------------------------
    
    	public void insertFirst(Vertex c) {                        // make new link
    		Link newLink = new Link(c);
    		newLink.next = first;       // it points to old first link
    		first = newLink;            // now first points to this
    	}
    
    	// ==============================================================
    	// 编程作业 13.2
    	public void insertLast(Vertex c) {                        // make new link
    		Link newLink = new Link(c);
    		last.next = newLink;            // now first points to this
    		last = newLink;
    	}
    
    	// ==============================================================
    	// 编程作业 13.2
    	public Link find()      // find link with non-visited vertex
    	{                           // (assumes non-empty list)
    		Link current = first.next;              // start at 'first.next'
    		while (current != null && current.vertex.wasVisited)  // while no match,
    		{
    			current = current.next;      // go to next link
    		}
    		return current;                    // found it
    	}
    
    	// ==============================================================
    	// -------------------------------------------------------------
    	public void displayList()      // display the list
    	{
    		Link current = first;       // start at beginning of list
    		System.out.print("List (" + current.vertex.label + "): ");
    		current = current.next;
    		while (current != null)      // until end of list,
    		{
    			current.displayLink();   // print data
    			current = current.next;  // move to next link
    		}
    		System.out.println("");
    	}
    	// -------------------------------------------------------------
    }  // end class LinkList
    // //
    // //
    
    class StackX {
    	private final int SIZE = 20;
    	private Vertex[] st;
    	private int top;
    
    	// ------------------------------------------------------------
    	public StackX()           // constructor
    	{
    		st = new Vertex[SIZE];    // make array
    		top = -1;
    	}
    
    	// ------------------------------------------------------------
    	public void push(Vertex j)   // put item on stack
    	{
    		st[++top] = j;
    	}
    
    	// ------------------------------------------------------------
    	public Vertex pop()          // take item off stack
    	{
    		return st[top--];
    	}
    
    	// ------------------------------------------------------------
    	public Vertex peek()         // peek at top of stack
    	{
    		return st[top];
    	}
    
    	// ------------------------------------------------------------
    	public boolean isEmpty()  // true if nothing on stack
    	{
    		return (top == -1);
    	}
    	// ------------------------------------------------------------
    }  // end class StackX
    // //
    
    class Graph1 {
    	// ============================================================
    	// 编程作业 13.2
    	// 这里只用了一个LinkList数组
    	// 每个LinkList的第一个节点Link表示当前节点
    	// 后面节点表示与前节点相邻接的节点
    	// 其实Link完全可以由Vertex代替,在Vertex里面添加一个域next
    	// 这个next指向与此Vertex相邻接的顶点
    	private final int MAX_VERTS = 20;
    	private LinkList adjList[];      // adjacency list
    	private int nVerts;          // current number of vertices
    	private StackX theStack;
    
    	// ------------------------------------------------------------
    	public Graph1()               // constructor
    	{
    		// adjacency matrix
    		adjList = new LinkList[MAX_VERTS];
    		nVerts = 0;
    		theStack = new StackX();
    	}  // end constructor
    
    	// ------------------------------------------------------------
    	public void addVertex(char lab) {
    		Vertex newVertex = new Vertex(lab);
    		LinkList list = new LinkList(newVertex);
    		adjList[nVerts++] = list;
    	}
    
    	// ------------------------------------------------------------
    	public void addEdge(int start, int end) {
    		adjList[start].insertLast(adjList[end].first.vertex);
    	}
    
    	// ------------------------------------------------------------
    	public void displayVertex(Vertex v) {
    		System.out.print(v.label);
    	}
    
    	// ------------------------------------------------------------
    	// ============================================================
    	// 编程作业 13.2
    	public void dfs()  // depth-first search
    	{                                 // begin at vertex 0
    		adjList[0].first.vertex.wasVisited = true;  			// mark it
    		displayVertex(adjList[0].first.vertex);                 // display it
    		theStack.push(adjList[0].first.vertex);                 // push it
    
    		while (!theStack.isEmpty())      // until stack empty,
    		{
    			// get an unvisited vertex adjacent to stack top
    			Vertex v = getAdjUnvisitedVertex(theStack.peek());
    			if (v == null)                    // if no such vertex,
    				theStack.pop();
    			else                           // if it exists,
    			{
    				v.wasVisited = true;  // mark it
    				displayVertex(v);                 // display it
    				theStack.push(v);                 // push it
    			}
    		}  // end while
    
    		// stack is empty, so we're done
    		for (int j = 0; j < nVerts; j++)
    			// reset flags
    			adjList[j].first.vertex.wasVisited = false;
    	}  // end dfs
    
    	// ============================================================
    	// 编程作业 13.2
    	// returns an unvisited vertex adj to v
    	public Vertex getAdjUnvisitedVertex(Vertex v) {
    		int j = -1;
    		for (int i = 0; i < adjList.length; i++) {
    			if (adjList[i].first.vertex.label == v.label) {
    				j = i;
    				break;
    			}
    		}
    		Link link = adjList[j].find();
    		if (link != null) {
    			return adjList[j].find().vertex;
    		} else {
    			return null;
    		}
    	}  // end getAdjUnvisitedVertex()
    
    	// ============================================================
    }  // end class Graph
    // //
    
    public class DFSApp {
    	public static void main(String[] args) {
    		Graph1 theGraph = new Graph1();
    		theGraph.addVertex('A');    // 0 (start for dfs)
    		theGraph.addVertex('B');    // 1
    		theGraph.addVertex('C');    // 2
    		theGraph.addVertex('D');    // 3
    		theGraph.addVertex('E');    // 4
    		theGraph.addVertex('F');    // 5
    
    		theGraph.addEdge(0, 1);     // AB
    		theGraph.addEdge(1, 2);     // BC
    		theGraph.addEdge(0, 3);     // AD
    		theGraph.addEdge(3, 4);     // DE
    		theGraph.addEdge(0, 5);     // AF
    
    		System.out.print("Visits: ");
    		theGraph.dfs();             // depth-first search
    		System.out.println();
    	}  // end main()
    }  // end class DFSApp
    // //
    
    


     

    /*
     	13.3 修改dfs.java程序(清单13.1)显示有向图的连通性表,就像“有向图的连
    		 通性”那节描述的一样。
     */
    package chap13.pp3;
    
    // dfs.java
    // demonstrates depth-first search
    // to run this program: C>java DFSApp
    
    class StackX {
    	private final int SIZE = 20;
    	private int[] st;
    	private int top;
    
    	// ------------------------------------------------------------
    	public StackX()           // constructor
    	{
    		st = new int[SIZE];    // make array
    		top = -1;
    	}
    
    	// ------------------------------------------------------------
    	public void push(int j)   // put item on stack
    	{
    		st[++top] = j;
    	}
    
    	// ------------------------------------------------------------
    	public int pop()          // take item off stack
    	{
    		return st[top--];
    	}
    
    	// ------------------------------------------------------------
    	public int peek()         // peek at top of stack
    	{
    		return st[top];
    	}
    
    	// ------------------------------------------------------------
    	public boolean isEmpty()  // true if nothing on stack
    	{
    		return (top == -1);
    	}
    	// ------------------------------------------------------------
    }  // end class StackX
    // //
    
    class Vertex {
    	public char label;        // label (e.g. 'A')
    	public boolean wasVisited;
    
    	// ------------------------------------------------------------
    	public Vertex(char lab)   // constructor
    	{
    		label = lab;
    		wasVisited = false;
    	}
    	// ------------------------------------------------------------
    }  // end class Vertex
    // //
    
    class Graph {
    	private final int MAX_VERTS = 20;
    	private Vertex vertexList[]; // list of vertices
    	private int adjMat[][];      // adjacency matrix
    	private int nVerts;          // current number of vertices
    	private StackX theStack;
    
    	// ------------------------------------------------------------
    	public Graph()               // constructor
    	{
    		vertexList = new Vertex[MAX_VERTS];
    		// adjacency matrix
    		adjMat = new int[MAX_VERTS][MAX_VERTS];
    		nVerts = 0;
    		for (int y = 0; y < MAX_VERTS; y++)
    			// set adjacency
    			for (int x = 0; x < MAX_VERTS; x++)
    				// matrix to 0
    				adjMat[x][y] = 0;
    		theStack = new StackX();
    	}  // end constructor
    		// ------------------------------------------------------------
    
    	public void addVertex(char lab) {
    		vertexList[nVerts++] = new Vertex(lab);
    	}
    
    	// ------------------------------------------------------------
    	public void addEdge(int start, int end) {
    		adjMat[start][end] = 1;
    		// adjMat[end][start] = 1;
    	}
    
    	// ------------------------------------------------------------
    	public void displayVertex(int v) {
    		System.out.print(vertexList[v].label);
    	}
    
    	// ------------------------------------------------------------
    	public void dfs()  // depth-first search
    	{                                 // begin at vertex 0
    		vertexList[0].wasVisited = true;  // mark it
    		displayVertex(0);                 // display it
    		theStack.push(0);                 // push it
    
    		while (!theStack.isEmpty())      // until stack empty,
    		{
    			// get an unvisited vertex adjacent to stack top
    			int v = getAdjUnvisitedVertex(theStack.peek());
    			if (v == -1)                    // if no such vertex,
    				theStack.pop();
    			else                           // if it exists,
    			{
    				vertexList[v].wasVisited = true;  // mark it
    				displayVertex(v);                 // display it
    				theStack.push(v);                 // push it
    			}
    		}  // end while
    
    		// stack is empty, so we're done
    		for (int j = 0; j < nVerts; j++)
    			// reset flags
    			vertexList[j].wasVisited = false;
    	}  // end dfs
    
    	// ------------------------------------------------------------
    	// returns an unvisited vertex adj to v
    	public int getAdjUnvisitedVertex(int v) {
    		for (int j = 0; j < nVerts; j++)
    			if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
    				return j;
    		return -1;
    	}  // end getAdjUnvisitedVertex()
    
    	// ------------------------------------------------------------
    	// ============================================================
    	// 编程作业 13.3
    	// Connectivity 连通性
    	// 通过修改dfs()方法得来
    	public void getConnectivity() {
    		for (int i = 0; i < nVerts; i++) {
    			vertexList[i].wasVisited = true;  // mark it
    			displayVertex(i); // display it
    			theStack.push(i);                 // push it
    			while (!theStack.isEmpty())      // until stack empty,
    			{
    				// get an unvisited vertex adjacent to stack top
    				int v = getAdjUnvisitedVertex(theStack.peek());
    				if (v == -1)                    // if no such vertex,
    					theStack.pop();
    				else                           // if it exists,
    				{
    					vertexList[v].wasVisited = true;  // mark it
    					displayVertex(v);                 // display it
    					theStack.push(v);                 // push it
    				}
    			}  // end while
    				// stack is empty, so we're done
    			for (int j = 0; j < nVerts; j++)
    				// reset flags
    				vertexList[j].wasVisited = false;
    			System.out.println();
    		}
    	}
    
    	// ============================================================
    }  // end class Graph
    // //
    
    public class DFSApp {
    	public static void main(String[] args) {
    		Graph theGraph = new Graph();
    		theGraph.addVertex('A');    // 0 (start for dfs)
    		theGraph.addVertex('B');    // 1
    		theGraph.addVertex('C');    // 2
    		theGraph.addVertex('D');    // 3
    		theGraph.addVertex('E');    // 4
    		theGraph.addVertex('F');    // 5
    
    		theGraph.addEdge(0, 1);     // AB
    		theGraph.addEdge(1, 2);     // BC
    		theGraph.addEdge(0, 3);     // AD
    		theGraph.addEdge(3, 4);     // DE
    		theGraph.addEdge(0, 5);     // DE
    
    		System.out.println("连通性: ");
    		theGraph.getConnectivity();
    	}  // end main()
    }  // end class DFSApp
    // //
    
    


     

    /*
    	13.4 实现Warshall算法来找到一个图的传递闭包。可以从编程作业13.3题开始。
    		 它有助于显示在算法的不同阶段显示邻接矩阵。
     */
    package chap13.pp4;
    
    // dfs.java
    // demonstrates depth-first search
    // to run this program: C>java DFSApp
    
    class StackX {
    	private final int SIZE = 20;
    	private int[] st;
    	private int top;
    
    	// ------------------------------------------------------------
    	public StackX()           // constructor
    	{
    		st = new int[SIZE];    // make array
    		top = -1;
    	}
    
    	// ------------------------------------------------------------
    	public void push(int j)   // put item on stack
    	{
    		st[++top] = j;
    	}
    
    	// ------------------------------------------------------------
    	public int pop()          // take item off stack
    	{
    		return st[top--];
    	}
    
    	// ------------------------------------------------------------
    	public int peek()         // peek at top of stack
    	{
    		return st[top];
    	}
    
    	// ------------------------------------------------------------
    	public boolean isEmpty()  // true if nothing on stack
    	{
    		return (top == -1);
    	}
    	// ------------------------------------------------------------
    }  // end class StackX
    // //
    
    class Vertex {
    	public char label;        // label (e.g. 'A')
    	public boolean wasVisited;
    
    	// ------------------------------------------------------------
    	public Vertex(char lab)   // constructor
    	{
    		label = lab;
    		wasVisited = false;
    	}
    	// ------------------------------------------------------------
    }  // end class Vertex
    // //
    
    class Graph {
    	private final int MAX_VERTS = 20;
    	private Vertex vertexList[]; // list of vertices
    	private int adjMat[][];      // adjacency matrix
    	private int nVerts;          // current number of vertices
    	private StackX theStack;
    
    	// ------------------------------------------------------------
    	public Graph()               // constructor
    	{
    		vertexList = new Vertex[MAX_VERTS];
    		// adjacency matrix
    		adjMat = new int[MAX_VERTS][MAX_VERTS];
    		nVerts = 0;
    		for (int y = 0; y < MAX_VERTS; y++)
    			// set adjacency
    			for (int x = 0; x < MAX_VERTS; x++)
    				// matrix to 0
    				adjMat[x][y] = 0;
    		theStack = new StackX();
    	}  // end constructor
    		// ------------------------------------------------------------
    
    	public void addVertex(char lab) {
    		vertexList[nVerts++] = new Vertex(lab);
    	}
    
    	// ------------------------------------------------------------
    	public void addEdge(int start, int end) {
    		adjMat[start][end] = 1;
    		// adjMat[end][start] = 1;
    	}
    
    	// ------------------------------------------------------------
    	public void displayVertex(int v) {
    		System.out.print(vertexList[v].label);
    	}
    
    	// ------------------------------------------------------------
    	public void dfs()  // depth-first search
    	{                                 // begin at vertex 0
    		vertexList[0].wasVisited = true;  // mark it
    		displayVertex(0);                 // display it
    		theStack.push(0);                 // push it
    
    		while (!theStack.isEmpty())      // until stack empty,
    		{
    			// get an unvisited vertex adjacent to stack top
    			int v = getAdjUnvisitedVertex(theStack.peek());
    			if (v == -1)                    // if no such vertex,
    				theStack.pop();
    			else                           // if it exists,
    			{
    				vertexList[v].wasVisited = true;  // mark it
    				displayVertex(v);                 // display it
    				theStack.push(v);                 // push it
    			}
    		}  // end while
    
    		// stack is empty, so we're done
    		for (int j = 0; j < nVerts; j++)
    			// reset flags
    			vertexList[j].wasVisited = false;
    	}  // end dfs
    
    	// ------------------------------------------------------------
    	// returns an unvisited vertex adj to v
    	public int getAdjUnvisitedVertex(int v) {
    		for (int j = 0; j < nVerts; j++)
    			if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
    				return j;
    		return -1;
    	}  // end getAdjUnvisitedVertex()
    
    	// ------------------------------------------------------------
    	// ============================================================
    	// 编程作业 13.4
    	// TransitiveClosure 传递闭包
    	// Warshall算法
    	public void doTransitiveClosure() {
    		for (int x = 0; x < adjMat.length; x++) { // 行
    			for (int y = 0; y < adjMat.length; y++) { // 列
    				if (adjMat[x][y] == 1) { // x -> y
    					for (int z = 0; z < adjMat.length; z++) {// 行
    						if (adjMat[z][x] == 1) { // z -> x
    							adjMat[z][y] = 1; // x -> y
    						}
    					}
    				}
    			}
    		}
    	}
    
    	// ============================================================
    	public void displayMat() {
    		for (int i = 0; i < nVerts; i++) {
    			for (int j = 0; j < nVerts; j++) {
    				System.out.print(adjMat[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    }  // end class Graph
    // //
    
    public class DFSApp {
    	public static void main(String[] args) {
    		Graph theGraph = new Graph();
    		theGraph.addVertex('A');    // 0 (start for dfs)
    		theGraph.addVertex('B');    // 1
    		theGraph.addVertex('C');    // 2
    		theGraph.addVertex('D');    // 3
    		theGraph.addVertex('E');    // 4
    		theGraph.addVertex('F');    // 5
    
    		theGraph.addEdge(0, 1);     // AB
    		theGraph.addEdge(1, 2);     // BC
    		theGraph.addEdge(0, 3);     // AD
    		theGraph.addEdge(3, 4);     // DE
    		theGraph.addEdge(0, 5);     // AF
    		theGraph.displayMat();
    		theGraph.doTransitiveClosure();
    		System.out.println("生成传递闭包: ");
    		theGraph.displayMat();
    	}  // end main()
    }  // end class DFSApp
    // //
    
    


     

    /*
     	13.5 骑士旅行是一个古老而著名的象棋谜题。题目是在一个空的棋盘上移动一个
    		 骑士,从一个方块到另一个,直到踏遍了棋盘的所有的方块。写一个程序,
    		 用深度优先搜索解决这个问题。最好使棋盘的大小可变,这样可以在较小的
    		 棋盘上解决这个问题。8*8的棋盘中,用个人电脑大概需要几年的时间解决
    		 这个问题。5*5的棋盘只需要几分钟而已。
    		 //骑士只能根据象棋的规则进行移动,要么横向跳动一格纵向跳动两格
    		 //要么纵向跳动一格横向跳动两格。   例如,   n=4,m=3   时,若骑士在格子(2;1),   
    		 //则骑士只能移入下面格子:(1;3),(3;3) 或   (4;2)
     */
    package chap13.pp5;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    //=================================================================
    class StackX {
    	private final int SIZE = 200;
    	private Lattice[] st;
    	private int top;
    
    	// ------------------------------------------------------------
    	public StackX()           // constructor
    	{
    		st = new Lattice[SIZE];    // make array
    		top = -1;
    	}
    
    	// ------------------------------------------------------------
    	public void push(Lattice j)   // put item on stack
    	{
    		st[++top] = j;
    	}
    
    	// ------------------------------------------------------------
    	public Lattice pop()          // take item off stack
    	{
    		return st[top--];
    	}
    
    	// ------------------------------------------------------------
    	public Lattice peek()         // peek at top of stack
    	{
    		return st[top];
    	}
    
    	// ------------------------------------------------------------
    	public boolean isEmpty()  // true if nothing on stack
    	{
    		return (top == -1);
    	}
    	// ------------------------------------------------------------
    }  // end class StackX
    
    // =================================================================
    // lattice 格子
    // 棋格
    class Lattice {
    	public int f; // 从前驱棋格的哪个方向而来
    	public int x;
    	public int y;
    
    	public Lattice(int f, int x, int y) {
    		this.f = f;
    		this.x = x;
    		this.y = y;
    	}
    
    	public Lattice getNextLattice(int f, Direction d) {
    		return new Lattice(f, this.x + d.x, this.y + d.y);
    	}
    }
    
    // =================================================================
    // 移动的方向
    class Direction {
    	public int x;
    	public int y;
    
    	public Direction(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    }
    
    // =================================================================
    class Chess {
    
    	// =================================================================
    	// 参数
    	private boolean[][] chessBoard; // 棋盘
    	int MAX_X = 5; // 棋盘宽
    	int MAX_Y = 5; // 棋盘高
    	private int number; // 未访问棋格数
    	private Lattice[] path;
    
    	private Direction[] direction; // 移动方向
    	{
    		direction = new Direction[] { new Direction(2, -1),
    				new Direction(2, 1), new Direction(1, 2), new Direction(-1, 2),
    				new Direction(-2, 1), new Direction(-2, -1),
    				new Direction(-1, -2), new Direction(1, -2) };
    	}
    
    	// =================================================================
    	public Chess(int x, int y) {
    		this.MAX_X = x;
    		this.MAX_Y = y;
    		this.number = MAX_X * MAX_Y; // 未访问棋格数
    		this.chessBoard = new boolean[MAX_X][MAX_Y]; // 棋盘
    		for (int i = 0; i < MAX_X; i++) { // 初始化棋盘
    			for (int j = 0; j < MAX_Y; j++) {
    				chessBoard[i][j] = false;
    			}
    		}
    		path = new Lattice[number];
    	}
    
    	// =================================================================
    	// 判断给定棋格lattice,是否在棋盘内,超出范围则不合法
    	public boolean isValid(Lattice lattice) {
    		if (lattice.x >= 0 && lattice.y >= 0 && lattice.x < MAX_X
    				&& lattice.y < MAX_Y) {
    			return true;
    		}
    		return false;
    	}
    
    	// =================================================================
    	// lattice 给定的棋格
    	// f 开始遍历的方法
    	// 返回lattice的下一个未访问的后继棋格
    	public Lattice getNextUnVisitedLattice(int f, Lattice lattice) {
    		for (int i = f; i < direction.length; i++) {
    			Lattice temp = lattice.getNextLattice(i, direction[i]);
    			if (isValid(temp)) { // 在棋盘内
    				if (!chessBoard[temp.x][temp.y]) { // 没有访问
    					return temp;
    				}
    			}
    		}
    		return null;
    	}
    
    	// =================================================================
    	// 编程作业 13.5
    	// 骑士的旅行
    	// 过程:
    	// 首先任选一个棋格标记为已访问并加入栈
    	// 如果栈不为空-------(1)
    	// --找栈顶棋格的后继未访问棋格
    	// --如果找到,则后继未访问棋格标记为已访问,并入栈
    	// --如果未找到,则把栈顶元素退栈
    	// --如果所有棋格都已入栈,则骑士旅行完成,方法结束
    	// 循环进入(1)
    	// 如果栈为空
    	// 则未找到骑士旅行的路径,方法结束
    	public void knightTour() {
    		StackX path = new StackX(); // 存放已访问的棋格
    		path.push(new Lattice(-1, 0, 0)); // 从第(0,0)个棋格开始
    		number--;
    		chessBoard[0][0] = true;
    		// disPlayChessBoard();
    		int f = 0; // 方向
    
    		while (!path.isEmpty()) {
    			Lattice temp = getNextUnVisitedLattice(f, path.peek()); // 后继未访问棋格
    			if (temp == null) { // 没找到
    				Lattice l = path.pop();
    				chessBoard[l.x][l.y] = false;
    				f = l.f + 1; // 下一个方向
    				number++;
    			} else {// 找到
    				chessBoard[temp.x][temp.y] = true;
    				path.push(temp);
    				f = 0; // 下一个方向
    				number--;
    			}
    
    			// 如果number == 0,说明,全部棋格已入栈,则骑士旅行完成
    			if (number == 0) {
    				int j = this.path.length - 1;
    				while (!path.isEmpty()) { // 把栈中棋格转存入数组
    					this.path[j--] = path.pop();
    
    				}
    				disPlayKnightTour(); // 显示骑士旅行路径
    				System.out.println("success!找到骑士旅行的路径!");
    				return;
    			}
    		}
    		System.out.println("failure!找不到骑士旅行的路径!");
    	}
    
    	// =================================================================
    	// 显示骑士旅行路径
    	public void disPlayKnightTour() {
    		for (int i = 0; i < MAX_X; i++) { // 初始化棋盘
    			for (int k = 0; k < MAX_Y; k++) {
    				chessBoard[i][k] = false;
    			}
    		}
    		for (int i = 0; i < path.length; i++) { // 骑士每移动一步,打印一次棋盘
    			Lattice temp = path[i];
    			chessBoard[temp.x][temp.y] = true;
    			disPlayChessBoard();
    		}
    	}
    
    	// =================================================================
    	// 打印棋盘
    	public void disPlayChessBoard() {
    		System.out.print("  ");
    		for (int i = 0; i < MAX_Y; i++) {
    			System.out.print(" " + i);
    		}
    		System.out.println();
    		for (int i = 0; i < MAX_X; i++) {
    			System.out.print(" " + i);
    			for (int j = 0; j < MAX_Y; j++) {
    				if (chessBoard[i][j] == false) {
    					System.out.print(" □");
    				} else {
    					System.out.print(" ■");
    				}
    			}
    			System.out.println();
    		}
    		System.out.println();
    	}
    
    	// =================================================================
    
    }
    
    public class Knight {
    	public static void main(String[] args) throws IOException {
    		System.out.print("请输入棋盘的宽:");
    		int x = getInt();
    		System.out.print("请输入棋盘的高:");
    		int y = getInt();
    		Chess chess = new Chess(x, y);
    		// chess.disPlayChessBoard();
    		chess.knightTour();
    	}
    
    	// -------------------------------------------------------------
    	public static String getString() throws IOException {
    		InputStreamReader isr = new InputStreamReader(System.in);
    		BufferedReader br = new BufferedReader(isr);
    		String s = br.readLine();
    		return s;
    	}
    
    	// -------------------------------------------------------------
    	public static int getInt() throws IOException {
    		String s = getString();
    		return Integer.parseInt(s);
    	}
    	// -------------------------------------------------------------
    }


     

    展开全文
  • 数据结构与算法分析Java版中文(PDF)附源码 本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。本书把算法分析...
  • Java数据结构和算法 Robert lafore 编程作业 七章 /* 7.1 修改partition.java程序(清单7.2),使partitionIt()方法总是用具有最大的 下标值的数组(最右)数据项作为枢纽,而不是任意一个数据项。...

    《Java数据结构和算法》第二版 Robert lafore  编程作业 第七章

    /*
     	7.1	修改partition.java程序(清单7.2),使partitionIt()方法总是用具有最大的
     		下标值的数组(最右)数据项作为枢纽,而不是任意一个数据项。(这和清单7.3
     		的quickSort.java程序相似。)确保程序对三个或少于三个数据项的数组也能
     		执行。为了达到这个目的,需要增加一些额外的语句。
     	7.2	修改quickSort2.java程序(清单7.4)以计算排序中复制和比较的次数,然后显
     		示总数。这个程序应该和QuickSort2专题applet的执行性能相同,因此对逆序
     		排列数据的复制和比较次数是一致的。(记住一次交换是三个复制。)
     		(7.2题没有做)
     	7.3	在第3章练习题3.2中,提示可以通过排序数据和挑选中间数据项来求一个数据
     		集的中心值。读者可能会想,使用快速排序然后选择一个中间的数据项是找中
     		心值最快的方法,但是还有一个更快的方法。利用划分算法求中心值,而不必
     		对所有的数据项排序。为了理解它是如何实现的,假设在划分数据时,偶然发
     		现枢纽最后停在数组中间的位置上。工作就完成了!枢纽右边的所有数据项都
     		大于(或等于)枢纽,而所有左边的数据项都小于(或等于)枢纽,所以如果
     		枢纽停在数组正中间的位置上,那么它就是中心值。枢纽通常是不会停在数组
     		中间位置上的,但是可以通过再划分包含了中间位置数据项的分组来找到它。
     		假设数组有7个数据项分布在数组的关键字从0到6的单元中。中间位置的数据项
     		的下标为3。如果划分这个数组,并且枢纽停在下标为4的位置上,那么需要对
     		下标为0到4的数据项重新划分(这个划分包含了下标为3的数据项),而不包括
     		下标为5到6的数据项。如果枢纽停在下标为2的分区,总是检查枢纽是否在中间
     		的位置。最后,枢纽会停在中间位置上的,程序也就结束。因为所需要的划分
     		次数比快速排序少,所以这个算法更快。
     		扩展编程作业7.1,来查找一个数组的中心值数据项。可以使用类似快速排序的
     		递归调用,但是只用来划分子数组,而不是对整个数组排序。当找到中心值数
     		据项时这个过程就停止,而不必等数组排序完成之后才停止。
     	7.4	选择的意思是从一个数组中找出第k大或者第k小的数据项。例如,要选择第7大
     		的数据项。找中心值(如编程作业7.2)是选择的一种特殊情况。可以使用同样
     		的划分过程,但不是找中间位置的数据项,而是找一个指定下标的数据项。修
     		改编程作业7.2中的程序,允许选择任意一个指定数据项。你的程序能处理多少
     		的数组呢?
     	7.5	实现本章最后一节所讲的基数排序算法。它应该能处理不同数据量的数据项,
     		以及关键字位数不同的数据。同时,也应该能够实现不同基数的排序(可以是
     		10以外的其他数),但是,除非编写的程序能显示不同的基数值,否则会很难
     		看清运行的情况。
     */
    package chap07;
    
    // partition.java
    // demonstrates partitioning an array
    // to run this program: C>java PartitionApp
    
    class ArrayPar {
    	private long[] theArray;          // ref to array theArray
    	private int nElems;               // number of data items
    
    	// --------------------------------------------------------------
    
    	public ArrayPar(int max)          // constructor
    	{
    		theArray = new long[max];      // create the array
    		nElems = 0;                    // no items yet
    	}
    
    	// --------------------------------------------------------------
    	public void insert(long value)    // put element into array
    	{
    		theArray[nElems] = value;      // insert it
    		nElems++;                      // increment size
    	}
    
    	// --------------------------------------------------------------
    	public int size()                 // return number of items
    	{
    		return nElems;
    	}
    
    	// --------------------------------------------------------------
    	public void display()             // displays array contents
    	{
    		System.out.print("A=");
    		for (int j = 0; j < nElems; j++)
    			// for each element,
    			System.out.print(theArray[j] + " ");  // display it
    		System.out.println("");
    	}
    
    	// --------------------------------------------------------------
    	public int partitionIt(int left, int right, long pivot) {
    		int leftPtr = left - 1;           // right of first elem
    		int rightPtr = right + 1;         // left of pivot
    		while (true) {
    			while (leftPtr < right &&       // find bigger item
    					theArray[++leftPtr] < pivot)
    				;  // (nop)
    
    			while (rightPtr > left &&       // find smaller item
    					theArray[--rightPtr] > pivot)
    				;  // (nop)
    			if (leftPtr >= rightPtr)        // if pointers cross,
    				break;                      // partition done
    			else
    				// not crossed, so
    				swap(leftPtr, rightPtr);    // swap elements
    		}  // end while(true)
    		return leftPtr;                   // return partition
    	}  // end partitionIt()
    
    	// =============================================================
    	// 编程作业 7.1
    	public int partitionIt(int left, int right) {
    		int leftPtr = left - 1;           // right of first elem
    		int rightPtr = right;         	  // left of pivot
    		long pivot = theArray[right];
    		while (true) {
    			while (leftPtr < right &&       // find bigger item
    					theArray[++leftPtr] < pivot)
    				;  // (nop)
    
    			while (rightPtr > left &&       // find smaller item
    					theArray[--rightPtr] > pivot)
    				;  // (nop)
    			if (leftPtr >= rightPtr)        // if pointers cross,
    				break;                      // partition done
    			else
    				// not crossed, so
    				swap(leftPtr, rightPtr);    // swap elements
    		}  // end while(true)
    		swap(leftPtr, right);
    		return leftPtr;                   // return partition
    	}  // end partitionIt()
    
    	// =============================================================
    	// 编程作业 7.3
    	public int findMedian(int left, int right) {
    		int leftPtr = left - 1;           // right of first elem
    		int rightPtr = right;         	  // left of pivot
    		long pivot = theArray[right];
    		while (true) {
    			while (leftPtr < right &&       // find bigger item
    					theArray[++leftPtr] < pivot)
    				;  // (nop)
    
    			while (rightPtr > left &&       // find smaller item
    					theArray[--rightPtr] > pivot)
    				;  // (nop)
    			if (leftPtr >= rightPtr)        // if pointers cross,
    				break;                      // partition done
    			else
    				// not crossed, so
    				swap(leftPtr, rightPtr);    // swap elements
    		}  // end while(true)
    		swap(leftPtr, right);
    
    		int midindex = theArray.length / 2; // 中间位置
    
    		if (leftPtr == midindex) {
    			return leftPtr;
    		} else if (leftPtr > midindex) {
    			return findMedian(left, leftPtr - 1);
    		} else {
    			return findMedian(leftPtr + 1, right);
    		}
    	}
    
    	// =============================================================
    	// 编程作业 7.3
    	public long median() {
    		return theArray[findMedian(0, theArray.length - 1)];
    	}
    
    	// =============================================================
    	// 编程作业 7.4
    	public int findIndex(int left, int right, int index) {
    		int leftPtr = left - 1;           // right of first elem
    		int rightPtr = right;         	  // left of pivot
    		long pivot = theArray[right];
    		while (true) {
    			while (leftPtr < right &&       // find bigger item
    					theArray[++leftPtr] < pivot)
    				;  // (nop)
    
    			while (rightPtr > left &&       // find smaller item
    					theArray[--rightPtr] > pivot)
    				;  // (nop)
    			if (leftPtr >= rightPtr)        // if pointers cross,
    				break;                      // partition done
    			else
    				// not crossed, so
    				swap(leftPtr, rightPtr);    // swap elements
    		}  // end while(true)
    		swap(leftPtr, right);
    
    		if (leftPtr == index) {
    			return leftPtr;
    		} else if (leftPtr > index) {
    			return findIndex(left, leftPtr - 1, index);
    		} else {
    			return findIndex(leftPtr + 1, right, index);
    		}
    	}
    
    	// =============================================================
    	public long findKth(int k) {
    		if (k < 1 || k > theArray.length) {
    			return -1;
    		}
    		return theArray[findIndex(0, theArray.length - 1, k - 1)];
    	}
    
    	// =============================================================
    	// --------------------------------------------------------------
    
    	public void swap(int dex1, int dex2)  // swap two elements
    	{
    		long temp;
    		temp = theArray[dex1];             // A into temp
    		theArray[dex1] = theArray[dex2];   // B into A
    		theArray[dex2] = temp;             // temp into B
    	}  // end swap()
    		// --------------------------------------------------------------
    }  // end class ArrayPar
    // //
    
    public class partition {
    	public static void main(String[] args) {
    		int maxSize = 16;             // array size
    		ArrayPar arr;                 // reference to array
    		arr = new ArrayPar(maxSize);  // create the array
    
    		for (int j = 0; j < maxSize; j++)  // fill array with
    		{                          // random numbers
    			long n = (int) (java.lang.Math.random() * 199);
    			arr.insert(n);
    		}
    		arr.display();                // display unsorted array
    
    		// long pivot = 99; // pivot value
    		// System.out.print("Pivot is " + pivot);
    		// int size = arr.size();
    		// // partition array
    		// int partDex = arr.partitionIt(0, size-1, pivot);
    		//
    		// System.out.println(", Partition is at index " + partDex);
    		// arr.display(); // display partitioned array
    
    		// ===================================================
    		// 编程作业 7.1
    		// int size = arr.size();
    		// int partDex = arr.partitionIt(0, size - 1);
    		// System.out.println("Pation is at index " + partDex);
    		// arr.display();
    		// ====================================================
    		// 编程作业 7.3
    		// System.out.println("中间值是:" + arr.median());
    		// arr.display();
    		// ===================================================
    		// 编程作业 7.4
    		System.out.println("第1小的值是:" + arr.findKth(1));
    		arr.display();
    		// ===================================================
    	}  // end main()
    }  // end class PartitionApp
    // //
    

    package chap07;
    
    class Link {
    	public long dData; // data item
    	public Link next; // next link in list
    
    	// -------------------------------------------------------------
    
    	public Link(long dd) // constructor
    	{
    		dData = dd;
    	}
    
    	// -------------------------------------------------------------
    	public void displayLink() // display this link
    	{
    		System.out.print(dData + " ");
    	}
    } // end class Link
    
    class CircleList {
    	private Link current;
    	private int nItems;
    
    	public CircleList() {
    		current = null;
    	}
    
    	public void insert(long value) {
    		Link link = new Link(value);
    		if (current == null) {
    			current = link;
    			link.next = link;
    		} else {
    			link.next = current.next;
    			current.next = link;
    			current = link;// 插入元素,current要移动要新元素
    		}
    		nItems++;
    	}
    
    	public long remove() {
    		// list为空是没有考虑,在调用remove之前应该判断是否为空
    		long temp = current.next.dData;// 删掉current的下一个元素
    		if (current.next == current) { // 只有一个元素时
    			current = null;
    		} else {
    			current.next = current.next.next;
    		}
    		nItems--;
    		return temp;
    	}
    
    	public long peek() { // 返回最早插入的元素
    		// 调用前要判断是否为空
    		return current.next.dData;
    	}
    
    	public Link find(long value) {
    		Link temp = current; // 保存原来的位置
    		Link result = null;
    		if (current == null) {
    			return result;
    		}
    		do {
    			step(); // 从current的下一个元素开始比较
    			if (current.dData == value) {
    				result = current;
    
    				current = temp; // 还原current到原来的位置,这样就不会打乱插入的顺序,current指向最后插入的元素
    				return result;
    			}
    		} while (current != temp); // current到达原来的位置,一周循环结束
    		return result;
    	}
    
    	// 往下移一步
    	public void step() { // 调用step()方法后,顺序会被打乱
    		if (current != null) {
    			current = current.next;
    		}
    	}
    
    	public void display() {
    		if (current != null) {
    			Link temp = current;
    			do {
    				step(); // 从current的一下个开始显示
    				System.out.print(current.dData + " ");
    			} while (current != temp);
    		}
    		System.out.println();
    	}
    
    	public boolean isEmpty() {
    		return current == null;
    	}
    
    	public int size() {
    		return nItems;
    	}
    }
    
    // =============================================================================
    // 编程作业 7.5
    // 基数排序算法
    // 方法一
    public class RadixSort {
    	// ==============================================
    	// 基数排序算法
    	// ==============================================
    	// 过程如下:
    	// 初数组 8 12 22 15 20 7 25 18 212 基数为10
    	// 首先按个位排序
    	// 结果是 (20)(12 22 212)(15 25)(7)(8 18)
    	// 然后按十位排序
    	// 结果是 (7 8) (12 212 15 18) (20 22 25)
    	// 然后按百位排序
    	// 结果是 (7 8 12 15 18 20 22 25) 212
    	// 排序结束
    	// ==============================================
    	// 此方法用链表暂存元素
    	// ==============================================
    	private static void radixSort(long[] array, int radix, int distance) {
    		// array 为待排序数组
    		// radix 代表基数
    		// distance 代表排序元素的位数 //大于或等于最大的元素的位数
    		int length = array.length;
    		CircleList[] temp = new CircleList[radix];// 用于暂存元素
    		for (int x = 0; x < radix; x++) { // 初始化数组
    			temp[x] = new CircleList();
    		}
    		int divide = 1;
    
    		for (int i = 0; i < distance; i++) {
    			// 个人觉的运用基数排序实现基数排序的重点在下面这些代码
    			for (int j = 0; j < length; j++) { // 按各元素相应位上的数字分组
    				int tempindex = (int) (array[j] / divide) % radix;
    				temp[tempindex].insert(array[j]);
    			}
    			int l = 0;
    			for (int k = 0; k < temp.length; k++) { // 把分好组的元素复制回原数组
    				while (!temp[k].isEmpty()) {
    					array[l++] = temp[k].remove();
    				}
    			}
    			divide = divide * radix;
    		}
    	}
    
    	public static void main(String[] args) {
    		long[] array = { 3, 2, 3, 2, 5, 333, 45566, 2345678, 78, 990, 12, 432, 56 };
    		radixSort(array, 10, 7);
    		for (int i = 0; i < array.length; i++) {
    			System.out.print("  " + array[i]);
    		}
    	}
    }
    // =============================================================================

    展开全文
  • 20集版本第一讲数组.rar第二讲简单排序.A危i第三讲栈队列.A危i第四讲链表.A危i第五讲双端链表双向链表.A危i第六讲递归的应用.A危i第七讲递归的高级应用.A危i第八讲希尔排序.A危i第九讲快速排序.A危i第十讲二叉树...

    20集版本

    第一讲数组.rar

    第二讲简单排序.A危i

    第三讲栈和队列.A危i

    第四讲链表.A危i

    第五讲双端链表和双向链表.A危i

    第六讲递归的应用.A危i

    第七讲递归的高级应用.A危i

    第八讲希尔排序.A危i

    第九讲快速排序.A危i

    第十讲二叉树的基本概念.A危i

    第十一讲二叉树的基本操作.A危i

    第十二讲遍历二叉树.A危i

    第十三讲删除二叉树节点.A危i

    第十四讲红黑树.A危i

    第十五讲哈希表.A危i

    第十六讲开放地址法.A危i

    第十七讲链地址法.A危i

    第十八讲图的基本概念.A危i

    第十九讲:图的搜索.A危i

    第二十讲:图的最小生成树.A危i

    44集版本

    第一讲.exe

    第二讲.exe

    第三讲.exe

    第四讲.exe

    第五讲.exe

    JA危a数据结构和算法第六讲.A危i

    JA危a数据结构和算法第七讲.A危i

    JA危a数据结构和算法第八讲.A危i

    JA危a数据结构和算法第九讲.A危i

    JA危a数据结构和算法第十讲.A危i

    JA危a数据结构和算法第十一讲.A危i

    JA危a数据结构和算法第十二讲.A危i

    JA危a数据结构和算法第十三讲.A危i

    JA危a数据结构和算法第十四讲.A危i

    JA危a数据结构和算法第十五讲.A危i

    JA危a数据结构和算法第十六讲.A危i

    JA危a数据结构和算法第十七讲.A危i

    JA危a数据结构和算法第十八讲.A危i

    JA危a数据结构和算法第十九讲.A危i

    JA危a数据结构和算法第二十讲.A危i

    JA危a数据结构和算法第二十一讲.A危i

    JA危a数据结构和算法第二十二讲.A危i

    JA危a数据结构和算法第二十三讲.A危i

    JA危a数据结构和算法第二十四讲.A危i

    JA危a数据结构和算法第二十五讲.A危i

    JA危a数据结构和算法第二十六讲.A危i

    JA危a数据结构和算法第二十七讲.A危i

    JA危a数据结构和算法第二十八讲.A危i

    JA危a数据结构和算法第二十九讲.A危i

    JA危a数据结构和算法第三十讲.A危i

    JA危a数据结构和算法第三十一讲.A危i

    JA危a数据结构和算法第三十二讲.A危i

    JA危a数据结构和算法第三十三讲.A危i

    JA危a数据结构和算法第三十四讲.A危i

    JA危a数据结构和算法第三十五讲.A危i

    JA危a数据结构和算法第三十六讲.A危i

    JA危a数据结构和算法第三十七讲.A危i

    JA危a数据结构和算法第三十八讲.A危i

    JA危a数据结构和算法第三十九讲.A危i

    JA危a数据结构和算法第四十讲.A危i

    JA危a数据结构和算法第四十一讲.A危i

    JA危a数据结构和算法第四十二讲.A危i

    JA危a数据结构和算法第四十三讲.A危i

    JA危a数据结构和算法第四十四讲.A危i

    JA危a数据结构和算法(PPT和源码).rar

    展开全文
  • 经典java结构教材,合并了原版中文使用更方便!
  • 这一章号称是讲数据结构中最简单的表、栈、队列,但是作为java语言描述,这章的重点在于描述arrayList linkedLisk的性能分析 list.get(i)是怎样实现的,list的迭代器是如何如何的好用(性能上的)对于list的增...
  • 2.6 向highArray.java程序(清单2.3)的HighArray类中加入一个noDup()的方法,使之可以将数组中的所有重复数据项删除.即如果数组中有数据项的关键字为17, noDup()方法将会删除其中的两个.不必考试保持数据项的顺序....
  • 计算机科学丛书·数据结构算法分析:Java语言描述(原书第3) [美]马克·艾伦·维斯 (Mark Allen Weiss) (作者), 冯舜玺 (译者), 陈越 (译者) 目录 出版者的话 前言 1章引论1 1.1本书讨论的内容1 1.2数学知识...
  • 课程介绍:基于JAVA语言的数据结构算法视频教程,非常经典的java数据结构基础理论课程,是学习java的必备技能。课程目录:01.第一讲数组02.第二讲简单排序03.第三讲栈队列04.第四讲链表05.第五讲双端链表双向链表...
  • 第三讲栈队列.avi 第四讲链表.avi 第五讲双端链表双向链表.avi 第六讲递归的应用.avi 第七讲递归的高级应用.avi 第八讲希尔排序.avi 第九讲快速排序.avi 第十讲二叉树的基本概念.avi 第十一讲二叉树的基本操作....
  • 第三章 表、栈、队列 ——【习题解答】数据结构算法分析-Java语言描述 第三版 持续更新中... 3.1 给定一个表L另一个表P,它们包含以升序排列的整数。操作printLots(L,P)将打印L中那些由P所指定的位置上的元素。...
  • 树 树是n个节点的有限集,n=0时称为空树,在任意一棵非空树中,有且仅有一个根节点。每个节点最多只有一个父节点。...树的存储结构,简单的顺序存储不能满足树的实现,需要结合顺序存储链式存储...
  • Java数据结构算法中的源代码applet - 站长下载

    千次下载 热门讨论 2009-09-27 13:38:03
    书名:数据结构Java版 图书编号:2086963 出版社:清华大学 定价:118.0 ISBN:730213544 作者:(美)福特(Ford,W.H.),(美)托普(Topp,W.R.) 著,梁志敏 译 出版日期:2006-11-11 版次: 开本: 简介: 本书...
  • 资源名称:Java常用算法手册 第三版 PDF资源目录:第1章 算法实现算法的Java语法第2章 数据结构第3章 基本算法思想第4章 排序算法第5章 查找算法第6章 基本数学问题第7章 数据结构问题第8章 数论问题第9章 算法...
  • 回溯算法:Backtrack   使用Backtrack类的用户需要提供: 1,应用程序类 实现Application接口。并且要包含内部迭代类,枚举从当前位置开始所有可能的下一步位置 2,Position类 定义“位置”在该应用程序中的意思 ...
  • 标签 : Java 数据结构 算法 作者 : Maxchen 版本 : V1.0.0 日期 : 2020/5/20 目录八皇后问题简介八皇后思路分析代码实现八皇后的代码测试 八皇后问题简介 国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题...
  • 数组的简单排序(经典算法) 数组的简单排序有:冒泡排序、选择排序、插入排序种: 1. 冒泡排序: 原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在...
  • 数据结构算法分析_java语言描述第三版,适合想学习算法java开发同学,比算法导论更时候入门,有中英双版,还附有部分习题的代码哦 全书特点如下: ●专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态...
  • 数据结构和算法是一对孪生兄弟,数据 结构研究的问题包括数据在计算机中存储、组织、传递和转换的过程及方法,这些也是构成与支撑 算法的基础。我们在编写计算机程序来解决应用问题时,最终都要归结并落实到这两个...
  • 题目:使用队列实现栈的功能 思路:使用两个队列,比如我要输入(栈低)0,1,2,3,按照栈的性质,输出为3,2,1,0 第一步:初始化两个队列,queuehelp; 第二步:把元素存入queue...第三步:初始化一个temp队列,
  • 数据结构算法与应用–C++语言描述;数据结构与算法分析 Java语言描述(第2版);算法导论(第三版)英文版 ;算法导论(原书第2版) ;算法导论(中文版)(现代计算机常用数据结构和算法)
  • 让链表两两合并,合并之后的链表再和第三个链表合并。 时间复杂度:k 为链表个数,n 为总的结点数,两两归并,每个结点会被归并 log(k) 次,所以总的时间复杂度为 O(nlog(k)) 。空间复杂度为 O(1)。 publi
  • 数据结构Java语言 人民邮电出版社 知识要点 数据结构中的常用术语 线性结构树形结构层次结构和图形结构的认识及结构特点 算法的定义特性以及描述规则 时间复杂度空间复杂度的定义以及评价规则 一节 1.数据结构三...
  • 最坏情况运行时间平均运行时间都n成线性关系   二,二叉树搜索的递归算法: 要求数组已经进行了排序,一般按照升序 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值...
  • 排序能有多快用决策树分析。排序n个元素,每种排列有一个叶结点,决策树t总共n!个叶结点。n!≤2^height(t) 所以树的高度height(t) ≥log2(n!)O(log(n!))=O(nlogn) ...算法思想:分治法——将原问题划分成
  • JDK6JDK7的算法有一些区别。JDK6是:带哨兵的环形双向链表,JDK7是不带哨兵、但是有first(头节点)last(尾节点)的双向非循环链表。哨兵的好处是使得代码更简洁,但并不能降低对链表的操作的渐进时间界;坏处是如果...
  • Java程序设计与数据结构教程(第二)》学习指导 目录 图书简况 学习指导 第一章 绪论 第二章 数据表达式 第三章 使用类对象 第四章 条件循环 第五章 编写类 第六章 图形用户界面 第七章 数组 第八章 ...
  • 发现有一本Java数据结构和算法.(),之后的内容按照这个来描述,程序都用java来写。跟高数一样也是立flag每日一更。今天简单点,个简单排序,入门级算法,具体不实现了。1.冒泡排序一趟 4,3,2,5,6 ...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 203
精华内容 81
关键字:

java数据结构和算法第三版

java 订阅
数据结构 订阅