第二章线性表.doc

第二章线性表 1．什么是顺序存储结构？什么是链式存储结构？ 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素，它的特点是，线性表中相邻的元素a[i]和a[i+1]赋以相邻的存储位置LOC(ai) 和LOC(a i+ 1 ) 。即，以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。简言之逻辑相邻，物理相邻。相邻元素之间查一个元素所占的物理空间，因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 线性量的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的) . 因此，为了表示每个数据元素ai与其直接后继数据元素a i+ 1之间的逻辑关系，对数据元素a i 来说，除了存储其本身的信息之外，还需存储-个指示其直接后继的信息〈即直接接后继的存储位置〉 . 这两部份信息组成数据元素ai的存储映映像，称为结点(node) . 它包括两个域:其中存储数据元素信息的称为数据域，存储直接后继存储位置的域称为指针域. 指针域中存储的信息称做指针或链. 2．线性表的顺序存储结构和链式存储结构各有什么特点？ 顺序存储结构，逻辑相邻的元素，物理上也相邻，每个结点只需存储数据本身，不许存储逻辑关系，节约存储空间，查找元素方便，但插入或删除元素需要大量移动元素，效率低。适合查找多但插入删除少的情况。 链式存储结构，逻辑上相邻的元素，物理上不一定相邻，每个结点除了存储元素本身外，还要存储元素之间的逻辑关系，占用存储空间大，但查找元素都要从头开始，查找费时间，但插入或删除元素不需要大量移动元素，只需要知道插入或删除位置结点的前驱指针，进行简单的指针变换即可。适合查找少，插入删除相对多的情况。 3．设线性表中数据元素的总数基本不变，并很少进行插入或删除工作，若要以最快的速度存取线性表中的数据元素，应选择线性表的何种存储结构？为什么? 用顺序存储，原因在1 和2之间； 4．线性表的主要操作有哪些？ 1）．?InitList(L) 初始化：构造一个空的线性表L。 2）. DestroyList(L) 销毁：销毁一个业已存在的线性表L。 3）. ClearList(L) 清空：将一业已存在的线性表L重置为空表。 4）. ListEmpty(L) 判表空：若L为空表，则返回TRUE；否则返回FALSE 。 5）．?ListLength(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 6）．?GetElem(L,i,e) 对给定的线性表L，取第i个数据元素。0≤i≤Length(L)-1），用e返回L中第i个数据元素的值。 7）. LocateElem(L,e,compare()) 定位 返回L中第一个与e满足关系compare( )的数据元素的位序, 若这种数据元素不存在, 则返回0 。 8）. PriorElem(L,cur_e,pre_e) 求前驱：若cur_e是L的数据元素, 且不是第一个, 则用pre_e返回它的前驱, 否则操作失败, pre_e无定义。 9）. NextElem(L,cur_e,next_e)求后继 若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败, next_e无定义。10）. ListInsert(L,i,e) 插入 在L中第i个位置之前插入新的数据元素e,L的长度加1 。1=i =Listlength(L)+111）. ListDelete(L,i,e) 删除 删除L的第i个数据元素,并用e返回其值,L的长度减1 。1=i =Listlength(L)+112）. ListTraverse(L,visit()) 遍历 对给定的线性表L，依次输出L的每一个数据元素。遍历时不许重复13）. Copy(L,C) 复制 将给定的线性表L复制到线性表C中。14）. Merge(A,B,C) 合并 将给定的线性表A和B合并为线性表C。 5．简述数组与顺序存储结构线性表的区别和联系。 顺序存储结构的线性表，它是用一个结构体变量来描述一个线性表，该变量包含三个分量，一个是一维数组来存储线性表中的元素，一个是线性表的元素个数length ，一个是线性表最大长度。对于线性表中的数组，每个元素必须是连续存放，若是对线性表插入或删除，对应位置需要靠右移或左移来重新保持紧密连接关系。而且插入或删除只能在合理位置（插入在1~length +1的位置，且不能越界，删除在1~length 的位置上，）。 而数组要灵活很多，数组里的元素不必连续