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

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

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

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

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

Python代码的简单实现如下:

#!python
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代码的简单实现:

#!python
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后面会有专门的讲解一些典型的树结构。

后记

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

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Published

Category

clrs

Tags

Contact