加载中…
个人资料
whutgy
whutgy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,090
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
访客
加载中…
好友
加载中…
评论
加载中…
博文
标签:

杂谈

分类: DataStructures&Algorith笔记
  递归和栈之间有一种紧密的联系。事实上,大部分的编译器都是使用栈来实现递归的。正如我们曾经提到过的,当调用一个方法的时候,编译器会把这个方法的所有参数及其返回地址(这个方法返回时控制到达的地方)都压入栈中,然后把控制转移给这个方法。当这个方法返回的时候,这些值退栈。参数消失了,并且控制权重新回到返回地址处
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
通用数据结构
  若想存储真实世界中的类似人事记录、存货目录、合同表或销售业绩等数据,则只需要一般用途的数据结构。在本书中属于这种类型的结构有数组、链表、树和哈希表。它们被称之为通用的数据结构是因为他们通过关键字的值来存储并查找数据,这一点在通用数据库程序中常见到(栈等特殊结构正好相反,它们只允许存取一定的数据项)。

 

  Libraries of data structures are available commercially in all major programming languages. Languages themselves may have some structures built in. Java, for example, includes Vector, Stack, and Hashtable classes. C++ includes the Standard Template Library (STL), which contains classes for many data structures and algorithms.

 

  Using a commercial library may eliminate or at least reduce the programming necessary to create the data structures described in this book. When that's the case, using a complex structure such as a balanced tree, or a delicate algorithm such as quicksort, becomes a more attra

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记
(7)
完整的代码:

class DistPar             // distance and parent
                       // items stored in sPath array
   public int distance;   // distance from start to this vertex
   public int parentVert; // current parent of this vertex
// -------------------------------------------------------------
   public DistPar(int pv, int d)  // constructor
      {
      distance = d;
      parentVert = pv;
      }
// -------------------------------------------------------------
   // end class DistPar
///////////////////////////////////////////////////////////////
cl

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
最短路径问题(The Shortest-Path Problem)

  可能在带权图中最常遇到的问题就是,寻找两点间的最短路径问题。

 

  Although in this situation we're interested in the cheapest fares, the graph problem is nevertheless always referred to as the shortest path problem.
  在图论中,这类问题叫做最短路径问题(SPP)。这里所说的最短并不总是指距离上的最短;它也可以代表最便宜,最快或最好的路径,或其他衡量标准。

 

Dijkstra算法
  The solution we'll show for the shortest-path problem is called Dijkstra's Algorithm, after Edsger Dijkstra, who first described it in 1959. This algorithm is based on the adjacency matrix representation of a graph. Somewhat surprisingly, it finds not only the shortest path from one specified vertex to another, but the shortest paths from the specified vertex to all the other vertices.
(为解决最短路径问题而提出的方法叫做Dijkstra算法,Edsger Dijkstra在1959年首次解决了这个问题。这个算法的实

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(9)
  The PriorityQ class uses an array to hold the members. As we noted, in a program dealing with large graphs a heap would be more appropriate than the array shown here. The PriorityQ class has been augmented with various methods. It can, as we've seen, find an edge with a given destination vertex with find(). It can also peek at an arbitrary member with peekN() and remove an arbitrary member with removeN(). Most of the rest of this program you've seen before. Listing 14.1 shows the complete mstw.java program.

class Edge
   {
   public int srcVert;   // index of a vertex starting edge
   public int destVert;  // index of a vertex ending edge
   public int distance;  // distance from src to dest
// -------------------------------------------------------------
   public Edge(int sv, int dv, int d)  // constructor
      {

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
In the last chapter we saw that a graph's edges can have direction. In this chapter we'll explore another edge feature: weight.

当把权值当作边的特性时,一些有趣和复杂的问题也就出现了。什么是带权图的最小生成树?什么是两个顶点间的最短(或造价最低)距离?这些问题在现实世界中有重要的意义。

 

(2)
带权图的最小生成树(Minimum Spanning Tree with Weighted Graphs)
要引入带权图,首先回到最小生成树的问题。在有向图中创建这样一棵树比在无向图中要复杂一点。
(实际上是一个NP完全问题,要找到真正的全局最优,可能需要穷举。往往用一些优化算法,或者用局部最优代替。)

An Example: Cable TV in the Jungle
  Suppose we want to install a cable television line th

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
最小生成树(MST)(Minimum Spanning Trees)
执行这种算法的结果就是产生了一个图,它用最少的边连接了所有的顶点。
(The result would be a graph with the minimum number of edges necessary to connect the vertices.)

 

对给定的一组顶点,可能有很多种最小生成树。最小生成树边E的数量总比顶点V的数量小1: E=V-1

Remember that we're not worried here about the length of the edges. We're not trying to find a minimum physical length, just the minimum number of edges. (This will change when we talk about weighted graphs in the next chapter.)

 

创建最小生成树的算法与搜索的算法几乎是相同的。它同样可以基于广度优先搜索或深度优先搜索。

 

It turns out that by executing the depth-first search and recording the edges you've traveled to make the search, you automatically create a minimum spanning tree. The only difference between the minimum spanning tree method mst(), which we'll see in a moment, and the depth-first search method

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
  图是一种与树有些相像的数据结构。实际上,从数学意义上说,树是图的一种。然而,在计算机程序设计中,图的应用方式与树不同。

  The data structures examined previously in this book have an architecture dictated by the algorithms used on them. For example, a binary tree is shaped the way it is because that shape makes it easy to search for data and insert new data. The edges in a tree represent quick ways to get from node to node.

  Graphs, on the other hand, often have a shape dictated by a physical problem. For example, nodes in a graph may represent cities, while edges may represent airline flight routes between the cities. Another more abstract example is a graph representing the individual tasks necessary to complete a project. In the graph, nodes may represent tasks, while directed edges (with an arrow at one end) indicate which task must be completed before another. In both cases, the shape of the graph arises from the specific real-world situ

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2009-09-08 09:13)
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
  第四章中介绍了优先级队列,它是一种对最小(或最大)关键字的数据项提供便利访问的数据结构。

  优先级队列是一个抽象数据类型(ADT),它提供了删除最大(或最小)关键字值的数据项的方法,插入数据项的方法,有时还有一些其他操作的方法。配合不同的ADT,优先级队列可以用不同的内部结构来实现。第4章中可以看到,优先级队列是用有序数组来实现的。这种作法的问题是,尽管删除最大数据项的时间复杂度为O(1),但是插入还是需要较长的O(N)时间。这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数组依然有序。

  Priority queues are also used internally in other computer algorithms. In Chapter 14, 'Weighted Graphs,' we'll see priority queues used in graph algorithms, such as Dijkstra's Algorithm.

  本章将介绍实现优先级队列的另一种结构:堆。堆是一种树,由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些,但是插入的时间快得多了。当速度非常重要且有很多插入操作是,可以选择堆来实现优先级队列。

 

堆是

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
链地址法(Separate Chaining)

  In open addressing, collisions are resolved by looking for an open cell in the hash table. A different approach is to install a linked list at each index in the hash table. A data item's key is hashed to the index in the usual way, and the item is inserted into the linked list at that index. Other items that hash to the same index are simply added to the linked list; there's no need to search for empty cells in the primary array.


  The load factor (the ratio of the number of items in a hash table to its size) is typically different in separate chaining than in open addressing. In separate chaining it's normal to put N or more items into an N-cell array; thus the load factor can be 1 or greater. There's no problem with this; some locations will simply contain two or more items in their lists.
链地址法中的装填因子(数据项和哈希表容量的比值)与开放地址法的不同。在链地址法中,需要在有N个单元的数组中装入N个或

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有