【学习笔记10】基本数据结构（栈 队列 链表 有根树）

#1栈和队列：

栈(stack)

动态集合 先进后出（last-in,first-out,LIFO）
Insert-压入-push Delete-弹出-pop 空-stack empty 下溢（对空栈弹出）-underflow 上溢（对满栈压入）-overflow
基本操作伪代码： 单指针：S.top

is_empty(S){
if S.top == 0
return true
else 
return false
}

push(S,x){
S.top++
S[S.top] = x
}

pop(S){
S.top--
return S[S.top+1]
}

三种基本操作push(),pop(),is_empty()-执行时间均为O(1)

队列(queue)

先进先出(FIFO) Insert-入队-Enqueue-O(1) Delete-出队-Dequeue-O(1) 队头-head 队尾-tail
关键词：环绕
基本方法伪代码：
思路为指针对Q进行一圈圈的环绕 enqueue把x元素写入到Q.tail所指的位置中去 dequeue把Q.head所指元素return

enqueue(Q, x) { 
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else 
Q.tail++
}

dequeue(Q){
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else
Q.head++
return x
}

#2链表(linked list)

head-头 tail-尾 sorted-已排序的 unsorted-未排序的 circular list-循环链表（head元素的prev指针指向tail元素） 空链表L.head=NIL

sentinel-哨兵（哑对象，简化边界的处理，慎用）

双向链表(doubly linked list)-每个对象含有key（关键字） prev（前驱） next（后继）

单链表(singly linked)-每个对象含有key（关键字）  next（后继）

主要方法 search(L,元素中的关键字k) insert(L,元素x) delete(L,元素x)

#3无指针类型语言中的结构实现

对象的多数组表示

建立3xn的数组，第一行表示prev，第二行表示key，第三行表示next，同一元素的下标相同，并用一变量L存储表头元素的下标，可做链表用

对象的单数组表示

建一个数组，按prev key next的顺序三个三个的依次存到数组里（每个对象依次占用长度为3的子数组），指向某个对象的指针就是该对象第一个元素的下标，考虑偏移量，易于处理异构对象（不同长度的对象）

#4有根树

二叉树

p-父节点 left-左孩子 right-右孩子 T.root = NIL 空树

无限制分支的有根树

将left right 换成child_1,child_2...child_n 此种方法需要预先知道每个元素孩子的数量，否则无法预先分配 左孩子右兄弟表示法： http://iprai.hust.edu.cn/icl2002/algorithm/datastructure/basic/tree/chapter6_3.htm