基本数据结构与算法.pptVIP

二级ACCESS—基本数据结构与算法线性表的插入操作（时间复杂度O(n)）插入前插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后ai＋1a0a1ai-1ai+1ai+1anxlastMaxsize-1插入后ai+23.3.3线性表第30页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法线性表的删除操作（时间复杂度O(n)）3.3.3线性表a0a1ai-1aiai+1an-1删除lastmaxsize删除前a0a1ai-1ai+2an-1lastmaxsize删除后ai+1第31页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法3.3.4栈和队列栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。设栈s=（a1，a2，…,ai，…，an）其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底第32页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法队列的主要运算设置一个空队列；插入一个新的队尾（rear）元素，称为进队；删除队头（front）元素，称为出队；读取队头元素；a1,a2,a3,a4,…………an-1,an队头队尾3.3.4栈和队列队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。第33页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法3210(a)rear=front=0(队空）e3e4(c)e1,e2出队，e4入队rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队3.3.4栈和队列队列的主要运算队空时，令rear=front=0;元素个数＝rear-front当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置第34页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法循环队列元素个数=(rear-front+n)modna1,a2,a3,a4,…………an-1,an队头队尾3.3.4栈和队列循环队列：首尾相接的队列，逻辑上形成一个环状。第35页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法3.3.5线性链表线性表顺序存储结构的特点简单、方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。第36页，共73页，星期日，2025年，2月5日二级ACCESS—基本数据结构与算法将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。?数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。线性链表分为：单链表、双链表、循环链表3.3.5线性链表a1a2∧ana3L…..带头结点的单链表第37页，