线性表——顺序表.pptx

《线性表——顺序表.pptx》由会员分享，可在线阅读，更多相关《线性表——顺序表.pptx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共26页第2页/共26页1.2 线性表 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。第3页/共26页1.2 线性表1.线性表（Linear List)的定义 具有相同数据类型的n(n0)个数据元素组成的有限 序列。数据元素之间具有的逻辑关系为线性关数据元素之间具有的逻辑关系为线性关系的数据元素集合称为系的数据元素集合称为线性表线性表。n n为线性表为线性表的长度的长度,长度为长度为0 0的线性表称为空表。的线性表称为空表。第4页/共26页1.2 线性表2.线性表的表示L=(a1，a2，a3，ai-1，ai，ai+

2、1，,.,an)表头表尾这里的数据元素ai(1 i n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。第5页/共26页3.线性结构特点:(1)(1)有且只有一个根结点有且只有一个根结点a a1，无前驱，无前驱 。(2)(2)有且只有一个终端结点有且只有一个终端结点a an n ，无后继，无后继 。(3)(3)其他结点有且只有一个直接前驱和一个其他结点有且只有一个直接前驱和一个直接后继。直接后继。1.2 线性表第6页/共26页几个线性表的例子：几个线性表的例子：数列数列：(25，12，78，34，100，88)1 1 1 1a1 a2 a3 a4 a5 a6一个数据元素一个数据元素一个数

3、据元素一个数据元素为一个整数为一个整数为一个整数为一个整数2 2 2 2字母表字母表：(A，B，C，,Z)a1 a2 a3 a26一个数据元素一个数据元素一个数据元素一个数据元素为一个字母为一个字母为一个字母为一个字母1.2 线性表简单线性表第7页/共26页几个线性表的例子：几个线性表的例子：数据文件：数据文件：3 3 3 399001 张张 华华 女女17 99002 李李 军军 男男18 99003 王王 明明 男男17 99050 刘刘 东东 女女19 学号学号 姓姓 名名性别性别 年龄年龄其其 他他 一个数据元素一个数据元素一个数据元素一个数据元素为一个记录为一个记录为一个记录为一个记

4、录a1a2a3 a50.1.2 线性表复杂线性表第8页/共26页 用一组地址连续的存储单元依次存储线性表用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过数中的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映据元素的存储位置直接反映。(a1，a2，a3，.,an )所谓一个元素的所谓一个元素的 是指该元素占用的是指该元素占用的若干若干(连续的连续的)存储单元的第一个单元的地址。存储单元的第一个单元的地址。地址地址LOC(ai)a1a2a3an d1 d2 d3 dn 1.2.2 线性表的顺序存储结构线性表的顺序存储结构第9页/共26页 若假设每个数据元

5、素占用若假设每个数据元素占用k k个存储单元，并且个存储单元，并且已知第一个元素的存储位置已知第一个元素的存储位置LOC(a1)，则有，则有 LOC(ai)=LOC(a1)+(i 1)ka1a2a3an 结论：结论：结论：结论：LOC(a1)=100 k=4 求求LOC(a5)=?a1a2a3an a4a5100 104 108 112 116 LOC(aLOC(a5 5)=100+(5)=100+(5 1)1)4=1164=116第10页/共26页事先分配给线性表的空间事先分配给线性表的空间当前已经占用的空间当前已经占用的空间当前已经占用的空间当前已经占用的空间尚未使用的空间尚未使用的空间尚

6、未使用的空间尚未使用的空间第11页/共26页#define M 100datatype AM;int n;C C 语言语言语言语言第12页/共26页1)顺序存储结构：顺序存储结构：2)第i个元素地址p顺序表的基本运算 插入和删除插入和删除1)1)顺顺序序表表的的插插入入运运算算:在在线线性性表表的的第第i i个个元元素素之之前前插插入入一一个新的元素，先移动，后插入。个新的元素，先移动，后插入。ABCDEFGH空闲空间插队前大哥，求求你？ABCDEFGH空闲空间插队后大哥，谢谢你！第13页/共26页1)顺序存储结构：顺序存储结构：2)第i个元素地址p顺序表的基本运算 插入和删除插入和删除1)1

7、)顺顺序序表表的的插插入入运运算算:在在线线性性表表的的第第i i个个元元素素之之前前插插入入一一个新的元素，先移动，后插入。个新的元素，先移动，后插入。ai-1.a2a1anai+1ai x ai-1.a2 a1 ai an an ai+1 ai ai x第14页/共26页插入程序举例插入程序举例(在在8 8个数中任意位置插入一个数个数中任意位置插入一个数)：#define N 8#define N 8main()main()int aN+1=12,34,45,6,78,9,10,91,i,j,x;int aN+1=12,34,45,6,78,9,10,91,i,j,x;printf(pri

8、ntf(“input the location to be inserted:input the location to be inserted:”););scanf(scanf(“%d,%d%d,%d”,&i,&x);,&i,&x);ai-1=x;ai-1=x;for(j=0;j=N;j+)for(j=0;j=N;j+)printf(printf(“%d,%d,”,aj);,aj);for(j=i-1;j=for(j=i-1;j=i-1;j-);j=i-1;j-)aj+1=aj;aj+1=aj;第15页/共26页插入运算时间性能分析：插入运算时间性能分析：在第在第i i个位置上作插入个位置上

9、作插入x,x,则需将第则需将第i i个至第个至第n n个元素移动，即共个元素移动，即共需移动需移动(n-i+1)(n-i+1)个元素。个元素。插入运算，时间主要消耗在数据移动上。在长度为插入运算，时间主要消耗在数据移动上。在长度为n n的线性表的线性表中插入一个元素，则中插入一个元素，则平均移动元素次数平均移动元素次数(期望值期望值)：p pi i：在第：在第i i个位置上作插入的概率。个位置上作插入的概率。等差数列求和公式等差数列求和公式:(首项首项+末项末项)项数项数)/2(n-i+1)MOVEi第16页/共26页线性表线性表(a0,a1,a2)平平局移动元素个数局移动元素个数:()*(3

10、+2+1+0)=1.5在一线性表在一线性表(a0,a1,a2)中插入任意一数中插入任意一数i，求平局移动元，求平局移动元素次数素次数:i 移动次数移动次数(n-i+1)1(插入到第个数插入到第个数a0前前)3 2(插入到第插入到第2个数个数a1前前)23(插入到第插入到第3个数个数a2前前)1(插入到第插入到第3个数个数a2后后)0 第17页/共26页1)顺序存储结构：顺序存储结构：2)第i个元素地址p顺序表的基本运算插入和删除插入和删除2)2)顺序表删除运算：顺序表删除运算：定义：定义：指将表中第指将表中第i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：(a1，a2，a

11、i-1，ai，ai+1，an)新表长为新表长为n-1n-1：(a1，a2，ai-1，ai+1，an)步骤：步骤：(1)将将ai+1 an，顺序向前移动顺序向前移动(2)表长表长减一减一第18页/共26页ABCDEFGH空闲空间空闲空间逃离后ABCDEFGH空闲空间空闲空间逃离前骗子，还我钱第19页/共26页 (删除第五个元素删除第五个元素21)6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 867第20页/共26页p顺序表的基本运算2)2)顺序表删除运算：顺序表删除运算：时间性能分析：时间性能分析：时间消耗与插入运算相同，时

12、间消耗与插入运算相同，平均移动元素次数：平均移动元素次数：q qi i:在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设q qi i=1/n=1/n 共需移动共需移动(n-i)(n-i)个元素。个元素。第21页/共26页 i 移动次数移动次数(n-i)1(删除第删除第1个数个数a0)22(删除第删除第2个数个数a1)13(删除第删除第3个数个数a2)0线性表线性表(a0,a1,a2)平平局移动元素个数局移动元素个数:(1/3)*(2+1+0)=1在一线性表在一线性表(a0,a1,a2)中删除任意一数中删除任意一数i，求平局移动元，求平局移动元素次数素次数:作业：有一数组，存储十个

13、数，编程序删除其中任意一个数。第22页/共26页重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素 因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表第23页/共26页p顺序表优点和缺点顺序表优点和缺点优点：优点：逻辑上相邻元素逻辑上相邻元素存储位置也相邻存储位置也相邻,无需增加额外存无需增加额外存储空间可方便储空间可方便随机存取随机存取表中任一元素。表中任一元素。缺点：缺点：插入和删除运算不方便插入和删除运算不方便,必须移动大量结点必须移动大量结点,效率较低效率较低不适合元素经常变动的大的线性表。不适合元素经常变动的大的线性表。对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；容易造成存储空间的“碎片”第24页/共26页思路(链式存储）：元素可以散落在任何位置，不必相邻让每个元素知道它的下一个元素在哪里我们只需要知道第一个元素的位置插入删除不再需要移动元素而是需要修改元素间的关系123456234561顺序存储结构不足的解决办法第25页/共26页感谢您的观看！第26页/共26页