10-基本数据结构-算法导论
2016-06-03 21:05:26 0 举报AI智能生成
《算法导论》是一本经典的计算机科学教材，它详细介绍了基本数据结构和算法。这本书涵盖了许多重要的主题，包括排序、搜索、图论、动态规划等。它通过严谨的逻辑和清晰的解释，帮助读者深入理解这些概念，并掌握它们在实际问题中的应用。此外，书中还提供了大量的练习题和实例，帮助读者巩固所学知识。总之，《算法导论》是一本值得一读的计算机科学入门书籍，它为读者提供了坚实的理论基础，帮助他们在计算机科学领域取得成功。
作者其他创作
大纲/内容
栈和队列
栈后进先出(LIFO)，删除的是最近插入的元素
队列先进先出(FIFO),删除的是存在集合中时间最长的那个元素
栈
Push()——插入操作
Pop()——删除操作
数组实现
数组S[1...n]: 实现一个最多可容纳n个元素的栈;
属性S.top——指向最新插入的元素；
S[0]为栈底元素，S[S.top]为栈顶元素；
空栈
S.top = 0,即不包含任何元素
栈下溢与栈上溢
对空栈pop-下溢； pop超出了S.top范围-上溢
几种操作
Stack-Empty(S)
功能：检查栈是否为空
算法
if S.top==0 则return TRUE
否则 返回FALSE
Push(S,x)
算法
S.top = S.top+1
S[ S.top ] = x
Pop(S,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以指向队头，从而形成环序
几种操作
EnQueue(Q,x)
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
几种操作
链表的搜索List-Search(L,k)
x=L.head
while x~=NIL & x.key~=k
x = x.next
% while end
return x
链表的插入List-Insert(L,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.next
else L.head = x.next
if x.next~=NIL ( 即 x不是表尾节点)
x.next.prev = x.prev
哨兵
作用：简化边界条件(即程序中可以不用考虑表头与表尾等特殊情况)
eg. 链表删除可改写为：
List-Delete'(L,x)
x.prev.next = x.next
x.next.prev = x.prev
如何使用哨兵：对链表代码中出现的每一处NIL都用哨兵L.nil（同样具有与其他节点一致的属性）代替
eg. 链表的搜索List-Search'(L,k)
x = L.nil.next
while x~=L.nil & x.key~=k
x = x.next
return x
eg. 链表的插入List-Insert'(L,x)
x.next = L.nil.next
L.nil.next.prev = x
x.prev = L.nil
L.nil.next = x
对象与指针的实现
基本思路
利用数组及其下标实现；
多数组表示对象
eg.对于循环链表的三个属性（prev,key,next）可以采用三个数组来分别保存各节点的属性值
每个属性使用一个数组表示
单数组表示对象
基本思想：偏移量，即
(指针是存储第一个元素的地址，后面在此基础上加偏移量，
利用数组的内存地址的连续性也可以这么处理)
eg. 单个数组表示双链表，那么每个节点都在数组中占据一段连续长度
为3的字数组（分别存储prev,key,next值——对应偏移量分别为0,1,2）,
此时，指向某对象的指针就是该对象内第一个元素的下标
对象的分配与释放
自由表（有点类似与栈）
有根树
二叉树
左右孩子表示法
职业：暂无
0 条评论
下一页
