数据结构知识点总结

} }

return 1;

ElemType Queue Delete(Q[],front,rear) {

if(rear<=front) { } else { }

3.队列的应用keyboard buffer 32byte

如何解决“假满”?---------还有空的地方却不能再插入。 答:接为环状(上弯下弯不同)

总结:

优点:1.不要求连续的、大块的内存,充分地利用内存空间

2.动态的存储结构

mod QMAX printf(\return 0;

不足:1.空间复杂度增加 2.操作(算法)复杂些

双端队列:限定插入和删除操作在表的两端进行的线性表。这两端分别是端点1和端点2。在实际使用中,还可以有输出受限的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入受限的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变成两个栈底相邻接的栈了。

链队列:用链表表示的队列。

-------------------------------------------------------------------------------

数组和广义表

从一给定的数组A[]中删除元素值在x到 y(x≤y)之间的所有元素(假定数组

中有n个元素)。算法头部约定如下:

void Delete( A[], n, x, y )

本题的算法思想是:先将A[]中所有元素值在x≤y之间的元素置成一个特殊的值

(如0),并不立即删除它们,然后从最后向前依次扫描,对于该特殊值的元素便移动其后面的元素将其删除,这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下: void Delete( A[], n, x, y ) {

for ( i?1; i ≤ n; i++ )

if ( A[i] ≥ x && A[i] ≤ y ) A[i] ? 0; for ( i?n; i ≥ 1; i-- ) if ( A[i] == 0 ) {

for ( k?j; k ≤(n-1); k++ ) A[k] ? A[k+1]; n ? n - 1; } }

--------------------------------------------------------------------- 树和二叉树

设一棵Huffman树中度为2的节点数为n2,则该树的总节点数为2n2+1

度的概念:结点的度指结点的孩子结点个数,例如度为2 就是有2个孩子结点的结点;叶子结点就是度为0的结点,没有孩子结点的结点.

按照这个概念,度为2的结点树为n2,即为非叶子结点,Huffman树中叶子结点个数是非结点个数+1,所以总结点个数:n2+n2+1

有一棵非空的二叉树(第0层为根结点),其第i层上至多有2i个结点。 对于n个节点的满二叉树,设叶节点数为m,分枝节点数为k,则n=k+m 满二叉树中,除了叶子结点,就是分支结点。

联系客服:779662525#qq.com(#替换为@)