10-基本数据结构-算法导论
2016-06-03 21:05:26 0 举报AI智能生成
登录查看完整内容
《算法导论》是一本经典的计算机科学教材，它详细介绍了基本数据结构和算法。这本书涵盖了许多重要的主题，包括排序、搜索、图论、动态规划等。它通过严谨的逻辑和清晰的解释，帮助读者深入理解这些概念，并掌握它们在实际问题中的应用。此外，书中还提供了大量的练习题和实例，帮助读者巩固所学知识。总之，《算法导论》是一本值得一读的计算机科学入门书籍，它为读者提供了坚实的理论基础，帮助他们在计算机科学领域取得成功。
作者其他创作
大纲/内容
10-基本数据结构-算法导论
栈和队列
栈
Push()——插入操作Pop()——删除操作
数组实现
数组S[1...n]: 实现一个最多可容纳n个元素的栈;属性S.top——指向最新插入的元素；S[0]为栈底元素，S[S.top]为栈顶元素；
空栈
栈下溢与栈上溢
对空栈pop-下溢； pop超出了S.top范围-上溢
几种操作
Stack-Empty(S)
功能：检查栈是否为空
算法
if S.top==0 则return TRUE
否则 返回FALSE
S.top = S.top+1
S[ S.top ] = x
if Stack-Empty(S)则返回error
否则 S.top = S.top-1并返回 S[ S.top+1 ]
队列
EnQueue()-入队（即插入操作）
入队元素被放在队尾额
DeQueue()-出队（即删除操作）
出队是队头位置的元素
队头head和队尾tail
数组Q[1...n]最多容纳n-1个元素
Q.head指向队头元素（不是空节点哈）， Q.tail指向下一个新元素将要插入的位置（是一个没有值的节点）
空队列：Q.head==Q.tail
同栈一样有下溢（空队列时DeQueues）和上溢（满队列时EnQueue）
注意：在Q.tail==Q.length时，Q.tail会被置为1以指向队头，从而形成环序
Q( Q.tail )=x
if Q.tail == Q.length则Q.tail = 1(即指向队头，形成一个环)
否则Q.tail = Q.tai+1
DeQueue(Q)
x = Q[Q.head]
if Q.head ==Q.length 则Q.head=1
否则 Q.head = Q.head + 1
返回 x
链表
线性链表
各对象按线性顺序排列——线性顺序由数组下标决定
双向链表
每个节点包括next和prev连个指针以及关键字key
L.head指向链表第一个元素（L.head-prev==NIL）——头结点不是空节点哈L.tail指向链表最后一个元素（L.tail-next ==NIL）——尾节点不是空节点
循环链表
L.head-prev指向表尾元素L.tail；L.tail-next指向表头元素L.head
x=L.head
while x~=NIL & x.key~=k x = x.next % while end
return x
功能: 将设置好关键字key的元素x插入到链表的前端时耗: O(1)
x.next=L.head
if L.head ~=NIL L.head-prev = x
L.head = x
x.prev = NIL
双向链表且给出了节点
功能: 将元素x从链表L中删除思路: 分别考察x非头结点和非尾节点时的情形即可
if x.prev~=NIL (即if x不是表头节点) x.prev.next = x.nextelse L.head = x.next
if x.next~=NIL ( 即 x不是表尾节点) x.next.prev = x.prev
哨兵
作用：简化边界条件(即程序中可以不用考虑表头与表尾等特殊情况)
eg. 链表删除可改写为：
如何使用哨兵：对链表代码中出现的每一处NIL都用哨兵L.nil（同样具有与其他节点一致的属性）代替
x = L.nil.nextwhile x~=L.nil & x.key~=k x = x.nextreturn x
x.next = L.nil.nextL.nil.next.prev = xx.prev = L.nilL.nil.next = x
对象与指针的实现
基本思路
利用数组及其下标实现；
多数组表示对象
每个属性使用一个数组表示
单数组表示对象
基本思想：偏移量，即(指针是存储第一个元素的地址，后面在此基础上加偏移量， 利用数组的内存地址的连续性也可以这么处理)
对象的分配与释放
自由表（有点类似与栈）
有根树
二叉树
左右孩子表示法
职业：暂无
0 条评论
回复 删除
下一页
