Data.Structures.And.Algorithm.Analysis.In.C.1992._datastructurevisualization资源-CSDN文库

共599个文件

gif：586个

htm：13个

需积分: 25 68 浏览量 2007-05-06 11:17:36 上传评论 1 收藏 2.41MB RAR 举报

《数据结构与算法分析》是计算机科学领域的一部经典著作，由Mark Allen Weiss撰写，首次出版于1992年。这本书深入浅出地探讨了数据结构和算法这两个编程和软件设计的基础概念，旨在帮助读者理解和掌握如何有效地设计、实现以及分析算法。数据结构是计算机科学中的核心概念，它涉及到如何在计算机内存中组织和存储数据，以便能够高效地访问和操作。书中的主要数据结构包括数组、链表、栈、队列、树（如二叉树、平衡树AVL和红黑树）、图以及哈希表等。作者详细解释了这些数据结构的特性、操作方法以及它们在不同场景下的应用。算法则是解决问题或执行任务的精确步骤集合。书中涵盖了排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序）和搜索算法（如线性搜索、二分搜索和广度优先搜索）等基础算法，同时也深入讨论了动态规划、贪心算法、回溯法和分治策略等高级算法设计技巧。对于每一种算法，Weiss都提供了清晰的伪代码和C语言实现，便于读者理解和实践。此外，书中还涉及了算法分析，这是评估算法性能的关键工具。通过时间复杂度和空间复杂度的分析，读者可以预估算法在处理大数据量时的行为，从而选择最适合的解决方案。作者还讨论了如何通过算法优化来提高程序效率，例如通过降低比较次数或减少不必要的空间消耗。关于“ARP反欺骗”和“防护”这两个标签，虽然不是本书的直接主题，但它们与计算机网络和网络安全相关。ARP（地址解析协议）反欺骗是防止中间人攻击的一种技术，其中攻击者篡改ARP缓存，以控制网络流量。在实际应用中，理解这些概念有助于构建更安全的系统。《数据结构与算法分析》是每一位计算机科学和技术专业人士的必备参考书，无论你是初学者还是经验丰富的开发者，都能从中受益匪浅。通过学习和实践书中的知识，你将能够更好地理解和解决复杂的计算问题，提升软件开发的效率和质量。

资源推荐

资源详情

资源评论

收起资源包目录

Data.Structures.And.Algorithm.Analysis.In.C.1992. （599个子文件）

298_a.gif 26KB

387_c.gif 24KB

79_a.gif 23KB

56_a.gif 21KB

375_a.gif 21KB

372_a.gif 20KB

160_b.gif 18KB

157_a.gif 17KB

186_a.gif 17KB

164_a.gif 17KB

170_a.gif 14KB

250box2.gif 13KB

106_a.gif 13KB

250box3.gif 13KB

250box1.gif 13KB

285_a.gif 13KB

397_c.gif 12KB

169_a.gif 12KB

410_b.gif 12KB

249box2.gif 12KB

249box1.gif 12KB

249box3.gif 12KB

417_a.gif 12KB

249box4.gif 12KB

411_a.gif 11KB

245_a.gif 11KB

363_a.gif 11KB

109_a.gif 11KB

316_a.gif 11KB

248box1.gif 10KB

313_a.gif 10KB

284_a.gif 10KB

212_a.gif 10KB

136_b.gif 10KB

439_a.gif 9KB

168_a.gif 9KB

188_b.gif 9KB

188_a.gif 9KB

187_a.gif 9KB

133_a.gif 9KB

388_a.gif 9KB

188_c.gif 9KB

78_b.gif 8KB

233_a.gif 8KB

20_b.gif 8KB

106_b.gif 8KB

330_a.gif 8KB

268_a.gif 8KB

334_a.gif 8KB

359_a.gif 8KB

310_a.gif 8KB

336_a.gif 8KB

273_a.gif 8KB

309_c.gif 7KB

122_a.gif 7KB

312_a.gif 7KB

307_a.gif 7KB

203_a.gif 7KB

305_d.gif 7KB

53_a.gif 7KB

358_a.gif 7KB

308_a.gif 7KB

150_a.gif 7KB

396_c.gif 7KB

166_b.gif 7KB

227_d.gif 7KB

92_a.gif 7KB

328_a.gif 7KB

160_a.gif 7KB

359_g.gif 7KB

309_b.gif 7KB

182_a.gif 7KB

153_a.gif 7KB

305_b.gif 7KB

182_b.gif 7KB

309_a.gif 7KB

20_a.gif 7KB

305_c.gif 7KB

308_b.gif 7KB

305_a.gif 7KB

444_a.gif 7KB

303_a.gif 7KB

357_a.gif 7KB

25_d.gif 7KB

208_b.gif 7KB

184_a.gif 6KB

396_d.gif 6KB

338_a.gif 6KB

184_b.gif 6KB

340_a.gif 6KB

181_c.gif 6KB

184_c.gif 6KB

410_a.gif 6KB

360_a.gif 6KB

208_a.gif 6KB

380_e.gif 6KB

214_a.gif 6KB

403_a.gif 6KB

198_a.gif 6KB

396_b.gif 6KB

共 599 条

<HTML><HEAD> <TITLE>Structures, Algorithm Analysis: CHAPTER 10: ALGORITHM DESIGN TECHNIQUE</TITLE></HEAD><BODY BGCOLOR="#FFFFFF"> <a href="chap11.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A> <a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A> <a href="chap9.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A> <h1><a name="01d1_0001">CHAPTER 10: ALGORITHM DESIGN TECHNIQUES<a name="01d1_0001"></h1> So far, we have been concerned with the efficient implementation of algorithms. We have seen that when an algorithm is given, the actual data structures need not be specified. It is up to the programmer to choose the approriate data structure in order to make the running time as small as possible. In this chapter, we switch our attention from the implementation of algorithms to the design of algorithms. Most of the algorithms that we have seen so far are straightforward and simple. <A ="algo01b4.htm#01B4_02AD">Chapter 9</A> contains some algorithms that are much more subtle, and some require an argument (in some cases lengthy) to show that they are indeed correct. In this chapter, we will focus on five of the common types of algorithms used to solve problems. For many problems, it is quite likely that at least one of these methods will work. Specifically, for each type of algorithm we will <img src="../images/dot12.gif"> See the general approach. <img src="../images/dot12.gif"> Look at several examples (the exercises at the end of the chapter provide many more examples). <img src="../images/dot12.gif"> Discuss, in general terms, the time and space complexity, where appropriate. <h1><a name="01d3_0391">10.1. Greedy Algorithms<a name="01d3_0391"></h1> <a name="01d3_038d"><a name="01d3_038e">The first type of algorithm we will examine is the greedy algorithm. We have already seen three greedy algorithms in Chapter 9: Dijkstra's, Prim's, and Kruskal's algorithms. Greedy algorithms work in phases. In each phase, a decision is made that appears to be good, without regard for future consequences. Generally, this means that some local optimum is chosen. This "take what you can get now" strategy is the source of the name for this class of algorithms. When the algorithm terminates, we hope that the local optimum is equal to the global optimum. If this is the case, then the algorithm is correct; otherwise, the algorithm has produced a suboptimal solution. If the absolute best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms generally required to generate an exact answer. <a name="01d3_038f"><a name="01d3_0390">There are several real-life examples of greedy algorithms. The most obvious is the coin-changing problem. To make change in U.S. currency, we repeatedly dispense the largest denomination. Thus, to give out seventeen dollars and sixty-one cents in change, we give out a ten-dollar bill, a five-dollar bill, two one-dollar bills, two quarters, one dime, and one penny. By doing this, we are guaranteed to minimize the number of bills and coins. This algorithm does not work in all monetary systems, but fortunately, we can prove that it does work in the American monetary system. Indeed, it works even if two-dollar bills and fifty-cent pieces are allowed. Traffic problems provide an example where making locally optimal choices does not always work. For example, during certain rush hour times in Miami, it is best to stay off the prime streets even if they look empty, because traffic will come to a standstill a mile down the road, and you will be stuck. Even more shocking, it is better in some cases to make a temporary detour in the direction opposite your destination in order to avoid all traffic bottlenecks. In the remainder of this section, we will look at several applications that use greedy algorithms. The first application is a simple scheduling problem. Virtually all scheduling problems are either NP-complete (or of similar difficult complexity) or are solvable by a greedy algorithm. The second application deals with file compression and is one of the earliest results in computer science. Finally, we will look at an example of a greedy approximation algorithm. <h2><a name="01d4_0394">10.1.1. A Simple Scheduling Problem<a name="01d4_0394"></h2> <a name="01d4_0391"><a name="01d4_0392"><a name="01d4_0393">We are given jobs j1, j2, . . . , jn, all with known running times t1, t2, . . . , tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time? In this entire section, we will assume nonpreemptive scheduling: Once a job is started, it must run to completion. As an example, suppose we have the four jobs and associated running times shown in <A ="algo01d4.htm#01D4_0397">Figure 10.1</A>. One possible schedule is shown in <A ="algo01d4.htm#01D4_0398">Figure 10.2</A>. Because j1 finishes in 15 (time units), j2 in 23, j3 in 26, and j4 in 36, the average completion time is 25. A better schedule, which yields a mean completion time of 17.75, is shown in <A ="algo01d4.htm#01D4_0399">Figure 10.3</A>. The schedule given in <A ="algo01d4.htm#01D4_0399">Figure 10.3</A> is arranged by shortest job first. We can show that this will always yield an optimal schedule. Let the jobs in the schedule be ji1, ji2, . . . , jin. The first job finishes in time ti1. The second job finishes after ti1 + ti2, and the third job finishes after ti1 + ti2 + ti3. From this, we see that the total cost, C, of the schedule is <img src="346_a.gif"> <h4><a name="01d4_0395">(10.1)<a name="01d4_0395"></h4> <img src="346_b.gif"> <h4><a name="01d4_0396">(10.2)<a name="01d4_0396"></h4> <pre>Job Time</pre> <pre>---------</pre> <pre> j1 15 </pre> <pre> j2 8 </pre> <pre> j3 3 </pre> <pre> j4 10 </pre> </pre> <h4><a name="01d4_0397">Figure 10.1 Jobs and times<a name="01d4_0397"></h4> <img src="347_a.gif"> <h4><a name="01d4_0398">Figure 10.2 Schedule #1<a name="01d4_0398"></h4> <img src="347_b.gif"> <h4><a name="01d4_0399">Figure 10.3 Schedule #2 (optimal)<a name="01d4_0399"></h4> Notice that in <A ="algo01d4.htm#01D4_0396">Equation (10.2)</A>, the first sum is independent of the job ordering, so only the second sum affects the total cost. Suppose that in an ordering there exists some x > y such that tix < tiy. Then a calculation shows that by swapping jix and jiy, the second sum increases, decreasing the total cost. Thus, any schedule of jobs in which the times are not monotonically nonincreasing must be suboptimal. The only schedules left are those in which the jobs are arranged by smallest running time first, breaking ties arbitrarily. This result indicates the reason the operating system scheduler generally gives precedence to shorter jobs. <h3>The Multiprocessor Case</h3> We can extend this problem to the case of several processors. Again we have jobs j1, j2, . . . , jn, with associated running times t1, t2, . . . ,

评论收藏

内容反馈