线性表——顺序表PPT学习教案

1、会计学1第1页/共26页第2页/共26页 线性结构是线性结构是最常用、最简单最常用、最简单的一种数的一种数据结构。而线性表是一种典型的线性结构据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是。其基本特点是线性表中的数据元素是有有序序且是有限的。且是有限的。第3页/共26页 数据元素之间具有的逻辑关系为线性关数据元素之间具有的逻辑关系为线性关系的数据元素集合称为系的数据元素集合称为线性表线性表。 n n为线性表为线性表的长度的长度, , 长度为长度为0 0的线性表称为空表。的线性表称为空表。第4页/共26页L=( a1，a2，a3，ai-1，ai ，ai+1，,.,an )

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

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

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

5、k个存储单元，并且个存储单元，并且已知第一个元素的存储位置已知第一个元素的存储位置LOC(a1)，则有，则有 LOC(ai) = LOC(a1)+(i 1) ka1a2a3an 结论：结论：LOC(a1)=100 k=4 求求LOC(a5)=?a1a2a3an a4a5100 104 108 112 116 LOC(a5) = 100+(5 1) 4=116第10页/共26页事先分配给线性表的空间事先分配给线性表的空间当前已经占用的空间当前已经占用的空间尚未使用的空间尚未使用的空间第11页/共26页#define M 100datatype AM;int n;C 语言语言第12页/共26页1)

6、 顺序存储结构：顺序存储结构： 2) 第第i个元素地址个元素地址p顺序表的基本运算顺序表的基本运算 顺序表的插入运算顺序表的插入运算: : 在线性表的第在线性表的第i i个元素之前插入一个元素之前插入一个新的元素，先移动，后插入。个新的元素，先移动，后插入。ABCDEFGH空闲空间插队前大哥，求求你？ABCDEFGH空闲空间插队后大哥，谢谢你！第13页/共26页1) 顺序存储结构：顺序存储结构： 2) 第第i个元素地址个元素地址p顺序表的基本运算顺序表的基本运算 顺序表的插入运算顺序表的插入运算: : 在线性表的第在线性表的第i i个元素之前插入一个元素之前插入一个新的元素，先移动，后插入。个

7、新的元素，先移动，后插入。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( printf(“input the location to be inserted:input the loca

8、tion 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页插入运算时间性能分析：插入运算时间性能分析：11npi等概率：在第在第i i个位置上作插入个位置上作插入x,x,则需将第则需将第i

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

10、移动元素个数局移动元素个数:()*(3+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个元素从线性表

11、中去掉。个元素从线性表中去掉。原表长为原表长为n n：( a1，a2，ai-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第

12、20页/共26页p顺序表的基本运算顺序表的基本运算2)2)顺序表删除运算：顺序表删除运算：时间性能分析：时间性能分析：时间消耗与插入运算相同，时间消耗与插入运算相同，平均移动元素次数：平均移动元素次数：niinn1)(1q qi i: :在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设q qi i=1/n =1/n 共需移动共需移动(n-i)(n-i)个元素。个元素。niiidlMOVEqE1niiinq1)(21n第21页/共26页 i 移动次数移动次数(n-i) 1(删除第删除第1个数个数a0) 22 (删除第删除第2个数个数a1) 13 (删除第删除第3个数个数a2) 0线

13、性表线性表(a0,a1,a2)平平局移动元素个数局移动元素个数:(1/3)*(2+1+0)=1在一线性表在一线性表(a0,a1,a2)中删除任意一数中删除任意一数i，求平局移动，求平局移动元素次数元素次数:niniidlninninqE1121)(1)(作业作业：有一数组，存储十个数，：有一数组，存储十个数，编程序删除其中任意一个数。编程序删除其中任意一个数。第22页/共26页在顺序存储表示的线性在顺序存储表示的线性表中插入或删除一个数表中插入或删除一个数据元素，平均约需要移据元素，平均约需要移动一半的元素动一半的元素 因此，顺序存储表示因此，顺序存储表示仅适用于不经常进行插仅适用于不经常进行插入和删除操作并且表中入和删除操作并且表中元素元素相对稳定相对稳定的表的表第23页/共26页p顺序表优点和缺点顺序表优点和缺点优点：优点：逻辑上相邻元素逻辑上相邻元素存储位置也相邻存储位置也相邻, ,无需增加额外无需增加额外存储空间可方便存储空间可方便随机存取随机存取表中任一