算法导论学习笔记7-第十章 基本数据结构

本章的内容非常简单,数据结构是程序员基础中的基础,虽然简单但一定要好好掌握。鉴于我已经在编程世界中摸爬滚打多年,此处的笔记不会做得太详细,只是讲之前自己遗漏的内容进行一下补全,详细的内容可以参看专门的数据结构书籍。

先进后出的结构,是最常用的一种数据结构,递归过程、函数调用等操作,全都依赖于这种栈结构。一个最简单的栈结构应该有如下四个操作:

  • isEmpty(): 判断当前栈中是否有元素
  • pop(): 返回栈顶元素,并且弹出(删除)栈顶元素。
  • top(): 返回栈顶元素,但是不弹出。
  • push(item): 栈中压入一个新元素item。

通常来说,一个栈至少应该有两种异常情况:

  • 上溢: 对空栈执行了pop()top()操作.
  • 下溢: 对已经达到容量上限的栈继续执行push(item)操作。

Python代码的简单实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Stack:
def __init__(self):
self.stack = []

def isEmpty(self):
return len(self.stack) <= 0:

def top(self):
if self.isEmpty() == True:
raise Exception('StackIsEmpty')
else:
x = self.stack[-1]
return x

def push(self,data):
self.stack.append(data)

def pop(self):
if self.isEmpty() == True:
raise Exception('StackIsEmpty')
else:
x = self.stack[-1]
self.stack = self.stack[:-1]
return x

def show(self):
'''
打印出栈中的数据
'''
print(self.stack)

def clear(self):
self.stack=[]

def __len__(self):
return len(self.stack)


队列

结构对应的另外一种数据结构就是队列,它是一种先进先出的结构,这也是一种在实际编程过程中非常常用的数据结构。 它主要有三个操作:

  • isEmpty(): 判断当前队列中是否有元素.
  • enqueue(item): 将元素item推入队列.
  • dequeue(): 返回队首元素,并且删除队首元素.

同样的,一个队列至少应该有两种异常情况:

  • 上溢: 对已经达到容量上限的队列继续执行push(item)操作。
  • 下溢: 对一个空队列执行dequeue()操作。

Python代码的简单实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Queue:
def __init__(self):
self.queue = []
def __len__(self):
return len(self.queue)
def isEmpty(self):
if len(self.queue) <= 0:
return True
else:
return False
def enqueue(self,data):
self.queue.append(data)
def dequeue(self):
if self.isEmpty() == True:
raise Exception('QueueIsEmpty')
else:
x = self.queue[0]
self.queue = self.queue[1:]
return x
def show(self):
'''
打印出队列中的信息
'''
print(self.queue)
def clear(self):
self.queue=[]


链表

链表其实和数组是比较相似的,都是将元素进行顺序存储,唯一的不同点在于链表是不能随机访问的,要想访问某个元素,必须从链表头开始向后扫描,直到找到需要的元素。

它的优点在于删除插入操作是可以在常数时间内完成的,而对于数组来说,它的删除插入操作在最坏情况下是$O(n)$代价的。

另外,需要注意的是,程序员面试过程中经常会问关于链表的题目,常见的问题有如下三个:

  1. 如何判断一个链表中是否存在环
  2. 计算链表中环的长度
  3. 找到环的起始位置

这三个问题连续的,其具体的分析和解答已经在我另外一篇博文中有所论述,此处就不再多言了。

也是一种非常基本的数据结构,在整个计算机领域中有着广泛的应用,而且它的变种有很多,可以变得的非常复杂同时拥有非常好的性能,Linux系统的文件系统就是基于B+树这种数据结构的。

树结构其实可以讲的内容非常多,但是这里只是一个简单的笔记,我就不再深入了,相信随着阅读的深入,CLRS后面会有专门的讲解一些典型的树结构。

后记

曾今看到过一些牛人写的代码,他们把一些很复杂的算法寓于数据结构之中,一个复杂的算法被分解成一个又一个小对象,非常的优雅,可惜我的功力还不够,不能做到如此的游刃有余,只能继续默默努力了。

打赏杯咖啡吧~