计算机二级课件第二讲.ppt

主讲：谢刚 讲师 单位：数学与计算机科学学院 Email:xg328@ 复习 上次课我们讲了哪些内容？ 1.3 线性表（1.3，1.5.1，1.5.2） 线性表的基本概念 线性表的运算 线性表的存储结构 1.3.1 线性表的基本概念 线性表：由n个数据元素a1,a2,…,an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个直接前件（前驱），除了最后一个外，有且只有一个直接后件（后继）。 n为线性表的长度。 当n=0,则该线性表为空表。 n≥1,该线性表不空。非空线性表有什么特征呀？ 线性表的表示 非空线性表的结构特征 有且只有一个根结点a1,它无前件（前驱） 有且只有一个终端结点an,它无后件（后继） 除根结点和终端结点外，其他所有结点有且只有一个直接前件（前驱），也只有一个直接后件（后继） 线性表的运算 插入 删除 查找 排序 1.3.2 线性表的存储结构 顺序存储结构 链式存储结构 一、线性表的顺序存储结构 线性表的顺序存储结构的特点 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 线性表的顺序存储结构 顺序表：线性表的顺序存储结构 实现：一维数组 运算：插入、删除、查找、排序、分解、合并、复制、逆转 顺序表的插入运算 总结 插入运算的步骤：先腾位置，然后再插入 该运算是改变了数据结构的数据元素个数，数据元素之间的关系。 缺点： 效率低、因为要进行数据元素的移动 当顺序表的空间已满，就不能插入新元素 计算机的存储空间得不到充分利用 不便于对存储空间进行动态分配 顺序表的删除运算 删除运算的步骤：从后往前覆盖。 该运算是改变了数据结构的数据元素个数，数据元素之间的关系。 缺点 效率低、因为要进行数据元素的移动。 顺序表 适用于小线性表或长度固定的线性表 适用于元素变动比较小的线性表 线性表的链式存储结构 为什么？ 线性链表：线性表的链式存储结构 逻辑结构 存储结构 运算 线性链表的逻辑结构 线性链表的存储结构 链式存储结构的特点 线性链表中所有元素所占的存储空间是可以连续的，也可以不连续 线性链表中各数据元素在存储空间中可以不按逻辑顺序依次存放的。即存储顺序与逻辑顺序可以不一致。 存储顺序由指针域来确定。 线性链表的运算 插入 删除 合并 分解 查找 排序 复制 逆转 查找 目的，找到找到进行插入或删除的位置。 步骤：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为要查找的数据为止 链表的插入 与顺序表进行比较 插入时不会出现上溢 实现存储空间的动态分配 插入过程不发生数据移动的现象，只需改变有关结点的指针域的值即可，从而提高插入的效率 链表的删除 线性链表删除的内存变化情况 与顺序表进行比较 不需要移动表的数据元素 只需更改被删除结点的前一个结点的指针域 删除的结点可进行回收再利用 （1）链表不具有的特点是 A）不必事先估计存储空间 ? B）可随机访问任一元素 ? C）插入删除不需要移动元素 ? D）所需空间与线性表长度成正比（20079） （1）链表不具有的特点是 A）不必事先估计存储空间 ? B）可随机访问任一元素 ? C）插入删除不需要移动元素 ? D）所需空间与线性表长度成正比（20079） （2）下列叙述中正确的是 A.一个逻辑数据结构只能有一种存储结构 B.数据的逻辑结构属于线性结构，存储结构属于非线性结构 C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 （2）下列叙述中正确的是 A.一个逻辑数据结构只能有一种存储结构 B.数据的逻辑结构属于线性结构，存储结构属于非线性结构 C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 （3）下列叙述中正确的是（ ）。（20089） A）顺序存储结构的存储一定是连续的，链存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间 （3）下列叙述中正确的是（ ）。（20089） A）顺序存储结构的存储一定是连续的，链存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间 * * B=（D，R） D={a1,a2,…,an} R={（a1，a2），（