(37)--公共基础计算机二级Office高级应用.ppt

《(37)--公共基础计算机二级Office高级应用.ppt》由会员分享，可在线阅读，更多相关《(37)--公共基础计算机二级Office高级应用.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1.2线性数据结构线性数据结构三、线性表1、线性表特点n有且只有一个根结点，它无前件；有且只有一个根结点，它无前件；n有且只有一个终端结点，它无后件；有且只有一个终端结点，它无后件；n除根结点和终端结点外，其它所有结点有且仅有一个前除根结点和终端结点外，其它所有结点有且仅有一个前件，也有且只有一个后件。件，也有且只有一个后件。冬冬春春夏夏秋秋4.1.2线性数据结构线性数据结构2、线性表的、线性表的 顺序存储结构n顺序存储结构特点：顺序存储结构特点：n所有元素所占的存储空间是连续的。所有元素所占的存储空间是连续的。n各数据元素在存储空间中是按逻辑顺序依次存放的各数据元素在存储空间中是按逻辑顺

2、序依次存放的。冬冬春春夏夏秋秋3012春春夏秋冬3012顺序存储结构存储空间4.1.2线性数据结构线性数据结构3、线性表的插入 与与 删除 操作操作n插入（假设原表中有n个元算）n插入一个元素时移动元素的数目：n最少移动的元素数目：0个n插入时最多移动的元素数目：n个n插入时平均移动的元素数目：n/2个春春夏秋冬301244.1.2线性数据结构线性数据结构n删除（假设原表中有删除（假设原表中有n个元算）个元算）n删除一个元素时移动的数据元素数目n删除时最少移动的元素数目：0个n删除时最多移动的元素数目：n-1个n删除时平均移动的元素数目：n/2个春春夏秋冬301244.1.2线性数据结构线性数

3、据结构四、堆栈和队列的定义四、堆栈和队列的定义1、栈、栈n栈是限定在一端进行插入和删除的特殊的线性表。n栈的特点是：栈的特点是：n先进后出(FILO)ntop、bottom指针指针nbottom指针不动ntop指针根据入栈和出栈来回移动 a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底topbottom4.1.2线性数据结构线性数据结构2、队列、队列n限定只能在一端进行插入，在表的另一端进行删除的线性表限定只能在一端进行插入，在表的另一端进行删除的线性表。（队头出队，队尾入队）（队头出队，队尾入队）n队列特点：队列特点：nFIFO（先进先出）（先进先出）a1 ,a2 ,a3 ,a4 ,an-

4、1 ,an 队头队尾n front和 rear指针nfront总是指向队头元素的前一个空间nrear指向队尾最后一个元素n队列的主要运算队列的主要运算n入队：从队尾入队入队：从队尾入队n退队退队:从对头出队从对头出队FEDCBAH12345678910frontrear队头队尾4.1.2线性数据结构线性数据结构4.1.2线性数据结构线性数据结构n循环队列n存储空间逻辑上首尾相连n采用顺序存储结构 FEDCBAH12345678910frontrearFEDCBAH12345678910frontrearFEDCBAH12345678910front入队X,Y,Z 元素后的指针变化XYZrear

5、初始队列YXFEDCBAZ12345678910frontrear H元算退队后的指针变化H4.1.2线性数据结构线性数据结构n循环队列总结（假设队列的总空间个数为m）：n循环队列采用顺序存储结构n队尾rear指针值可以比对头front指针值大，队尾rear指针值可以比对头front指针值小。n如rear=front则队列为空，或满队，元素个数为0或mn如rearfront则对中的元素个数为rear-frontn如rearfront则对中的元素个数为m-front+rear4.1.2线性数据结构线性数据结构五、线性链表1、线性链表的基本概念：、线性链表的基本概念：n线性表的链式存储结构称为线性

6、链表。单向链表单向链表双向链表双向链表4.1.2线性数据结构线性数据结构n循环链表4.1.2线性数据结构线性数据结构n链接存储结构特点链接存储结构特点n比顺序存储结构占用的空间多n(每个节点都由数据域和指针域组成)。n逻辑上相邻的节点物理上不必相邻：n即存储空间可以不连续n各数据结点的存储顺序与数据元素之间的逻辑关系顺序可以不一致。n插入、删除灵活：(不必移动节点，只要改变节点中的指针)。n查找结点时链式存储要比顺序存储慢。4.1.2线性数据结构线性数据结构30124657冬冬春春夏夏秋秋夏夏春冬秋30124657春春夏秋冬3012线性表的顺序存储结构线性表的链式存储结构 下课了。下课了。追求追求休息一会儿。休息一会儿。