VB公共基础 第1讲 - 算法与数据结构 - 图文(7)

1.4.2 队列及其基本运算2．循环队列及其运算?队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用?入队运算：队尾指针加1，并当rear=m+1时置rear=1?出队运算：队头指针加1，并当front=m+1时置front=1Q(1..8)rearfront87654321(a)空队列frontrear87654321FEDCBAfrontrearQ(1..8)87654321Q(1..8)XFEDCBAYfrontrear87654321YQ(1..8)XFEDCB(b)有6个元素的循环队列(c)元素X、Y入队后的队列(d)元素A出队后的队列311.5 线性链表321.5.1 线性链表的基本概念1．线性表顺序存储的缺点?插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。?线性表的顺序存储结构下，线性表的存储空间不便于扩充。?线性表的顺序存储结构不便于对存储空间的动态分配。331.5.1 线性链表的基本概念2．线性链表?线性表的链式存储结构?物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的?每个结点由两部分组成：数据域和指针域数据域data指针域nextHEADa1a2?an-1an^(a)结点结构(b)一个非空的线性链表示意图341.5.1 线性链表的基本概念双向链表：每个结点设置两个指针?左指针：指向其前件结点?右指针：指向其后件结点左指针数据域右指针HEAD(a)结点结构^a1a2?an^(b)一个非空的双向链表示意图35