首页 > 代码库 > 基本数据结构

基本数据结构

STACK-EMPTY(S)
 if S.top == 0
    return TRUE
 else return FALSE
 
 PUSH(S,x)
    S.top = S.top + 1
    S[S.top] = x
    
POP(S)
 if STACK-EMPTY(S)
    error "underflow"
 else S.top = S.top -1
    return S[S.top+1]

队列
INSERT, ENQUEUE
DELETE, DEQUEUE

ENQUEUE(Q,x)
 Q[Q.tail]=x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

DEQUEUE(Q.x)
x = Q[Q.head]
if (Q.head == Q.length)
    Q.head = 1
else Q.head = Q.head + 1
return x

链表,双向链表,单向链表,循环链表
LIST-SEARCH(L,k)
 x = L.head
 while x != NULL and x.key != k
    x = x.next
return x

LIST-INSERT(L,x)
 x.next = L.head
 if L.head != NIL
    L.head.prev = x
  L.head = x
  x.prev = NIL
 
LIST-DELETE(L,x)
    if x.prev != NIL
        x.prev.next = x.next
    else L.head = x.next
    if x.next != NIL
        x.next.prev = x.prev
        
哨兵
LIST-SEARCH(L, k)
 x = L.nil.next
 while x != L.nil and x.key != k
    x = x.next
 return x
 
LIST-INSERT(L,x)
 x.next = L.nil.next
 L.nil.next.prev = x
 L.nil.next = x
 x.prev = L.nil
 
指针和对象实现

对象和多数组表示
  技术分享

对象和单数组表示

技术分享

对象的分配与释放

 假设多数组表示法中的个数组长度为m, 某一时刻动态集合中含有n<=m个元素。则n个对象代表现存于动态
集合中的元素,而余下的m-n个对象是自由的,这些自由对象可以用来表示要插入该动态集合的元素

自由表
ALLOCATE-OBJECT()
if free = NIL
    error "out of space"
else x = free
    free = free.next
    return x

FREE-OBJECT(x)
x.next = free
free = x

 

 

 

技术分享

 

多链表多数组表示法

技术分享

 

 

 



基本数据结构