线性表顺序与链式存储的对比分析ppt课件

1、线性表顺序与链式存储的对比分析线性表顺序与链式存储的对比分析by 熊猫烧香熊猫烧香Page 2目录目录顺序与链式存储的构造对比顺序与链式存储的构造对比删除算法的对比分析删除算法的对比分析查找算法的对比分析查找算法的对比分析插入算法的对比分析插入算法的对比分析Page 301 顺序与链式存储的构造对比顺序与链式存储的构造对比一、顺序存储一、顺序存储 在计算机中用一组地址延续的存储单元依次存储线性表的各个数据元素在计算机中用一组地址延续的存储单元依次存储线性表的各个数据元素,称作线性表的顺称作线性表的顺序存储构造序存储构造.二、链式存储二、链式存储 在计算机中用一组恣意的存储单元存储线性表的数据元

2、素在计算机中用一组恣意的存储单元存储线性表的数据元素(这组存储单元可以是延续的这组存储单元可以是延续的,也也可以是不延续的可以是不延续的). 称作线性表的链式存储构造称作线性表的链式存储构造. Page 402 插入算法的对比插入算法的对比n 顺序存储的插入顺序存储的插入n (1) 不用查找插入位置不用查找插入位置i，只需求判别，只需求判别i的合法位置，其范围的合法位置，其范围是是1iL.listsize阐明阐明线性表满了，不能进展插入数据元素操作，要添加存储空线性表满了，不能进展插入数据元素操作，要添加存储空间的分量或者作错误处置。间的分量或者作错误处置。 n (3) 将线性表的最后一个数据

3、元素到第将线性表的最后一个数据元素到第i-1个数据元素依次个数据元素依次往后挪动一个数据单元，空出第往后挪动一个数据单元，空出第i-1个位置的数据单元；个位置的数据单元； n (4)把新的数据元素插入到刚刚空出来的数据单元中，长把新的数据元素插入到刚刚空出来的数据单元中，长度度+1.Page 5n 链式存储构造的插入链式存储构造的插入n (1)链式存储的线性表做插入操作，不判别线性表能否满，链式存储的线性表做插入操作，不判别线性表能否满，但是要从头指针开场，经过循环语句但是要从头指针开场，经过循环语句while(n&ji-1)循循环查找第环查找第i-1个节点。个节点。 n (2)判别判

4、别i的合法性，的合法性，i的合法范围是的合法范围是1in,否那么就不合否那么就不合法。法。 n (3)恳求一个节点的存储空间，并用一个指针变量指向这恳求一个节点的存储空间，并用一个指针变量指向这个节点，把需求插入的数据元素赋值给这个节点的数据域个节点，把需求插入的数据元素赋值给这个节点的数据域中。中。 n (4)修正插入数据元素的指针，完成插入操作修正插入数据元素的指针，完成插入操作Page 603 删除算法的对比分析删除算法的对比分析n 顺序存储的删除算法顺序存储的删除算法 n (1)不用查找删除位置不用查找删除位置i，也不用另外判别线性表，也不用另外判别线性表能否为空，只需取值为能否为空，

5、只需取值为1inext&ji-1)循环循环查找需求删除的第查找需求删除的第i个节点个节点 n (2)判别第判别第i个节点的合法性，个节点的合法性，i的合法范围是的合法范围是1in，否那么不和法。否那么不和法。 n (3)修正删除数据元素的指针，完成删除操作修正删除数据元素的指针，完成删除操作 n (4)释放删除结点的存储空间。释放删除结点的存储空间。Page 804 查找算法的对比分析查找算法的对比分析n 顺序存储可以根据存储数据元素要求不同而分成以下几种算法：顺序存储可以根据存储数据元素要求不同而分成以下几种算法： n (1)顺序查找算法，即以遍历一切元素为目的，与每个数据元素进展顺

6、序查找算法，即以遍历一切元素为目的，与每个数据元素进展比较，假设相等那么查找胜利，假设遍历后仍无相等元素那么没有查比较，假设相等那么查找胜利，假设遍历后仍无相等元素那么没有查找的数据。找的数据。n (2)折半查找是要求顺序存储和存储的数据元素有序，查找时把给定折半查找是要求顺序存储和存储的数据元素有序，查找时把给定的关键字与表中的中间位置元素进展比较，假设相等就查找胜利，假的关键字与表中的中间位置元素进展比较，假设相等就查找胜利，假设关键字比中间位置大，那么下次在右半部分查找；反之那么下次在设关键字比中间位置大，那么下次在右半部分查找；反之那么下次在左半部分查找，依次反复，直到遍历一切数据元素

7、也没有找到与关键左半部分查找，依次反复，直到遍历一切数据元素也没有找到与关键字相等的数据元素存在，那么查找失败。字相等的数据元素存在，那么查找失败。 n (3)索引查找是把顺序表索引查找是把顺序表(主表主表)中的数据元素等分成相等的几部分中的数据元素等分成相等的几部分(子子表表)，使后一个子表的一切数据元素均大于前一个子表的最大数据元，使后一个子表的一切数据元素均大于前一个子表的最大数据元素，并用每一个子表的最大关键字建立索引表。进展查找时，将给定素，并用每一个子表的最大关键字建立索引表。进展查找时，将给定关键字先与索引表中的关键字进展比较，确定此关键字属于哪一个子关键字先与索引表中的关键字进

8、展比较，确定此关键字属于哪一个子表，再在这个子表上进展查找。表，再在这个子表上进展查找。Page 9n 链式存储查找算法链式存储查找算法 n 链式存储可以根据存储数据元素要求的不同而分链式存储可以根据存储数据元素要求的不同而分成以下几种链表方式的查找算法：成以下几种链表方式的查找算法： n (1)单链表。只能从头指针开场，一个结点接着一单链表。只能从头指针开场，一个结点接着一个结点地顺序查找，不能找节点前驱，只能找结个结点地顺序查找，不能找节点前驱，只能找结点后继结点。点后继结点。 n (2)循环链表。可以从头指针开场，也可以从尾指循环链表。可以从头指针开场，也可以从尾指针开场顺序地查找结点的

9、后继元素。针开场顺序地查找结点的后继元素。 n (3)双向链表。从头指针开场顺序查找结点，即可双向链表。从头指针开场顺序查找结点，即可以查找结点的前驱元素，也可以查找结点的后继以查找结点的前驱元素，也可以查找结点的后继元素。元素。Page 1005 优缺陷的对比优缺陷的对比n 顺序存储顺序存储n 优点：优点： n 1、随机存取运算便利。对表中任一结点都可在、随机存取运算便利。对表中任一结点都可在O(1)时间时间内直接获得内直接获得 n 2、存储密度大、存储密度大1，存储空间利用率高。，存储空间利用率高。n 缺陷：缺陷： n 1、 插入和删除运算不方便，平均要挪动表中近一半的结插入和删除运算不方

10、便，平均要挪动表中近一半的结点。信息量较大。点。信息量较大。 n 2、 由于要求占用延续的存储空间，存储分配只能按最大由于要求占用延续的存储空间，存储分配只能按最大存储空间预先进展，能够呵斥空间浪费。存储空间预先进展，能够呵斥空间浪费。 n 3、 扩展容量需继续恳求。扩展容量需继续恳求。Page 11n 链式存储链式存储n 优点：优点： n 1、 插入、删除操作很方便，可经过修正结点的指针实现，插入、删除操作很方便，可经过修正结点的指针实现，无须挪动元素。无须挪动元素。n 2、 方便扩展存储空间。只需内存空间尚有空闲，就不方便扩展存储空间。只需内存空间尚有空闲，就不会产生溢出。会产生溢出。n 缺陷：缺陷： n 1、 不能随机存取元素。不能随机存取元素。 n 2、 存储密度小存储密度小1，存储空间利用率低，存储空间利用率低Page 1206 小结小结n 1、 顺序表适宜于做查找这样的静态操作；链表宜于做插顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。入、删除这样的动态操作