栈和队列的共同特点是只允许在端点处插入,删除元素
在深度为5的满二叉树中,叶子节点的个数为2^n - 1
算法分析的目的是分析算法的效率以求改进
两个栈共享一个存储空间的好处是节省空间,降低上溢发生的效率
串的长度是字符的个数
两个串 p 和 q , 求p 和 q 首次出现的位置运算称为模式匹配
N个顶点的连通图边数至少为N-1
在n个节点的单链表中要删除已知结点p,需找到它的前驱节点的位置,其时间复杂度为O(n)
n个单元的循环队列,队满时有n-1个元素
再循环队列中队首指针指向队首元素的前一个位置
KMP
查找方便是顺序存储结构的优点
顺序存储结构与链式存储结构的区别
链表存储结构的内存地址不一定是连续的,但顺序存储结构的内存地址一定是连续的
链式存储适用于在比较频繁地插入,删除,更新元素时,而顺序存储结构适用于频繁查询
顺序存储结构于链式存储结构的优缺点
空间上
顺序比链式节约空间,因为连式结构的每一个节点都有一个指针存储域
假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件为
如果有头结点 front == rear
无头结点 front == null
队列的插入是在队列的队尾进行 , 删除是在队首进行
栈的插入在栈顶进行
单循环链表的主要优点是从表中任一节点出发都能扫描到整个链表
顺序存储的线性表可以实现随机存取
LIFO指后进先出
抽象数据类型ADT可以用三元组(D , S , P)表示 , 它们分别表示 数据对象 数据关系 和 基本操作
二分查找中ASL计算
入队时
rear = (rear + 1) % maxisze
出队时
front = (front + 1) % maxsize
队满
front = (rear + 1)%maxSize
求队长
(rear - front + maxSize) %maxSize
