📄 chapter1.htm

📁 介绍高级数据结构和算法的讲义

💻 HTM

字号:

<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" --> 
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" --> 
<title>算法与数据结构 -- 指针转移</title>
<!-- #EndEditable --> 
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" --> 
<script language="JavaScript">
previous = "index.htm";
next = "chapter1_1.htm";
contents="";
topic="并行算法";
</script>
<!-- #EndEditable --> 
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" --> 
  <h2>第一节 指针转移</h2>
  <p>在各种PRAM算法中，涉及指针的算法是非常有趣的。在本节中，我们要讨论一种称为指针转移的技术，应用这一技术可以获得有关链表操作的快速算法。我们要特别介绍一种O(lgn)时间的算法，该算法用于计算n个对象组成的链表中每个对象到表尾的距离。然后，我们对该算法进行修改，以在O(lgn)的时间内对n个对象组成的链表执行“并行前缀”计算。最后，我们探讨一种把有关树的问题转化为关于链表问题的技术，后一种问题可用指针转移技术来解决。本节中的所有算法都是EREW算法：不需要对全局存储器进行并发存取。</p>
  <ul>
    <li><a href="chapter1_1.htm">1.1 表排序</a></li>
    <li><a href="chapter1_2.htm">1.2 列表的并行前缀</a></li>
    <li><a href="chapter1_3.htm">1.3 欧拉回路技术</a></li>
  </ul>
  <!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C

搜索代码 Ctrl + F

全屏模式 F11

切换主题 Ctrl + Shift + D

显示快捷键 ?

增大字号 Ctrl + =

减小字号 Ctrl + -