《数据结构常见问题：12单元5 线性表的存储结构.docx》由会员分享，可在线阅读，更多相关《数据结构常见问题：12单元5 线性表的存储结构.docx（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程常见问题单元5线性表的存储结构i.线性表的顺序存储结构解析:元素在毁僮表中的色序0效据元素存储地址Lo4)Loc(70)+dn-1Loc(%)4i 怕火(。0)依1)归在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。计算机存储空间中的存储地址为：Loc(%)= Loc( )+i*d特点是：线性表中逻辑上相邻的结点在存储结构中也相邻.线性表的链式存储结构(1)单向链表head(a)空单向链表head A Q口 5 八(b)非空单向链表a、初始化b、单向链表的插入操作 c、单链表的删除操作、(2)循环链表headhead(a)循环磋表的交表形式
2、headheadCb)循环卷表的一般形式(3)循环链表双向链表head.A%A（a）至双向链表Cb）非宝双向耀表2 .在实际应用中顺序表和链表，究竟选用哪一种存储结构呢？顺序表和链表各有短长。这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑:顺序表链表基 于 空 间 考 虑分 配 方 式静态分配。程序执行之前必须明确 规定存储规模。假设线性表长度n变化较 大，那么存储规模难于预先确定估计过大 将造成空间浪费，估计太小又将使空间 溢出机会增多。动态分配只要内存空间尚有 空闲，就不会产生溢出。因此， 当线性表的长度变化较大，难以 估计其存储规模时，以采用动态 链表作为存储结构为好。存密
3、度为1。当线性表的长度变化不大，易 于事先确定其大小时; 为了节约存储空 间，宜采用顺序表作为存储结构。1基 于 时 间 考 虑存 取法随机存取结构，对表中任一结点都 可在。（1）时间内直接取得 线性表的 操作主要是进行查找，很少做插入和删 除操作时，采用顺序表做存储结构为 宜。顺序存取结构，链表中的结 点，需从头指针起顺着链扫描才 能取得。入 删 除 操 作在顺序表中进行插入和删除，平均 要移动表中近一半的结点，尤其是当每 个结点的信息量较大时，移动结点的时 间开销就相当可观。在链表中的任何位置上进行 插入和删除，都只需要修改指针。 对于频繁进行插入和删除的线性 表，宜采用链表做存储结构。假设 表的插入和删除主要发生在表的 首尾两端，那么采用尾指针表示的 单循环链表为宜。