维基百科数据结构教程（英文PDF）

需积分: 3 160 浏览量更新于2024-07-27 收藏 1.9MB PDF 举报

"datastructurefromwikibooks.pdf 是一个源自维基百科的关于数据结构的详细教程，以英文呈现，采用Pdf格式。该资源遵循创作共用 Attribution-ShareAlike 3.0 Unported 许可协议，允许分享和衍生作品，但需正确归功，并在相同或兼容许可下分发。源代码部分被视为公共领域，而使用的图像具有各自独立的版权状态。此资源部分引用了维基百科的内容，并对引用表示感谢。数据结构是计算机科学中的核心概念，它探讨如何有效地存储、组织和操作大量数据。这本教程涵盖了多个关键的数据结构主题： 1. 引言：这部分通常会介绍数据结构的基本概念，以及学习数据结构的重要性。它可能会涉及算法分析的基础，如渐近记法（例如大O记法），用于评估算法的时间复杂度和空间复杂度。 2. 数组：数组是最基础的数据结构之一，它允许通过索引来访问和操作固定大小的元素集合。讨论可能包括一维数组、二维数组以及数组在内存中的表示。 3. 列表结构和迭代器：列表是可变大小的元素集合，可以支持插入、删除和遍历操作。迭代器是一种机制，用于顺序访问列表或其他容器的元素，而无需暴露其底层表示。 4. 栈和队列：栈是一种后进先出（LIFO）的数据结构，常用于表达式求值、递归等场景；队列则是一种先进先出（FIFO）的数据结构，常见于任务调度和多线程编程。 5. 树：树形数据结构包括二叉树、平衡树（如AVL树和红黑树）、堆（如最小堆和最大堆）等，它们广泛应用于搜索、排序和优先级队列等。 6. 图：图由节点和边组成，用于表示对象之间的关系。图的算法包括路径查找（如Dijkstra算法和Floyd-Warshall算法）、最短路径问题、图的遍历等。 7. 哈希表：哈希表提供快速的存取和查找，通过哈希函数将键映射到槽位。它支持平均时间复杂度为O(1)的查找、插入和删除操作。 8. 集合：集合是一组不重复元素的无序组合，可以进行交集、并集和差集操作。在某些实现中，集合可能基于哈希表或二叉树。 9. 权衡：不同的数据结构有各自的优缺点，如空间效率、时间效率、动态扩展能力等。理解这些权衡对于选择合适的数据结构至关重要。通过学习这些数据结构，程序员能够设计更高效、更具弹性的算法和系统，从而更好地处理现代计算面临的大量数据挑战。"

Data Structures/All Chapters

# Do stuff with the iterator

iter.move-next()

end while

Second, each operation gives a worst-case running time. Any implementation of the List ADT is guaranteed to be

able to run these operation at least that fast. Most implementations will run most of the operations faster. For

example, the node chain implementation of List can run insert-after() in .

Third, some of the operations say that they have a default implementation. This means that these operations can be

implemented in terms of other, more primitive operations. They're included in the ADT so that certain

implementations can implement them faster. For example, the default implementation of get-nth() runs in

because it has to traverse all of the elements before the nth. Yet the array implementation of List can

implement it in using its get-element() operation. The other default implementations are:

abstract type List<item-type>

method is-empty()

return get-begin().equal(get-end())

end method

method get-size():Integer

var size:Integer := 0

var iter:List Iterator<item-type> := get-begin()

while(not iter.equal(get-end()))

size := size+1

iter.move-next()

end while

return size

end method

helper method find-nth(n:Integer):List Iterator<item-type>

if n >= get-size()

error "The index is past the end of the list"

end if

var iter:List Iterator<item-type> := get-begin()

while(n > 0)

iter.move-next()

n := n-1

end while

return iter

end method

method get-nth(n:Integer):item-type

return find-nth(n).get-value()

end method

method set-nth(n:Integer, new-value:item-type)

find-nth(n).set-value(new-value)

end method

end type

Data Structures/All Chapters

end constructor

method get-begin():Vector Iterator<item-type>

return new Vector-Iterator(array, 0)

end method

The end iterator has an index of size. That's one more than the highest valid index.

method get-end():List Iterator<item-type>

return new Vector-Iterator(array, size)

end method

We'll use this method to help us implement the insertion routines. After it is called, the capacity of the array is

guaranteed to be at least new-capacity. A naive implementation would simply allocate a new array with exactly

new-capacity elements and copy the old array over. To see why this is inefficient, think what would happen if

we started appending elements in a loop. Once we exceeded the original capacity, each new element would require

us to copy the entire array. That's why this implementation at least doubles the size of the underlying array any time

it needs to grow.

helper method ensure-capacity(new-capacity:Integer)

If the current capacity is already big enough, return quickly.

if capacity >= new-capacity

return

end if

Now, find the new capacity we'll need,

var allocated-capacity:Integer := max(capacity*2, new-capacity)

var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)

copy over the old array,

for i in 0..size-1

new-array.set-element(i, array.get-element(i))

end for

and update the Vector's state.

array := new-array

capacity := allocated-capacity

end method

This method uses a normally-illegal iterator, which refers to the item one before the start of the Vector, to trick

insert-after() into doing the right thing. By doing this, we avoid duplicating code.

method prepend(new-item:item-type)

insert-after(new Vector-Iterator(array, -1), new-item)

end method

insert-after() needs to copy all of the elements between iter and the end of the Vector. This means that in

general, it runs in time. However, in the special case where iter refers to the last element in the vector, we

don't need to copy any elements to make room for the new one. An append operation can run in time, plus the

time needed for the ensure-capacity() call. ensure-capacity() will sometimes need to copy the

剩余128页未读，继续阅读

zhangshiwu2008

粉丝: 0
资源: 7

维基百科数据结构教程（英文PDF）

用Python编程实现控制台爱心形状绘制技术教程

优选驾考小程序 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

【国信期货-2024研报】宏观2025年投资策略报告：经济结构性矛盾现拐点 2025年注重破局.pdf

renren-security-v5.2.0.zip

毕业设计&课设_校园卡管理系统.zip

毕业设计&课设_网上图书商城：计算机毕业设计项目.zip

使用yolo3作为特征提取器的ocr，由keras实现，并由tensorrt加速.zip

BANDIZIP-SETUP-STD-X64.EXE

在 win10 运行 yolov5 deepsort 行人车辆跟踪检测计数.zip

【大越期货-2024研报】生猪期货早报.pdf

最新资源

优选驾考小程序微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip