数据结构线性表顺序表.ppt
数据结构线性表顺序表 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2.1 线性表的定义和运算线性表的定义和运算一、线性表的定义：1、定义：线性表线性表 L是由n个元素a1，a2，an组成的有限序列。记作L=(a1,a2,an)注：（1）n=0为表长；（2）n=0时为L空表；记作L=（）如：字母表A,B,C,Z 数字表（0,1,2,3,9）（同一表中，元素类型相同。）2 2、特点：、特点：,a,ai-1 i-1,a,ai i,a,ai+1 i+1,a ai-1 i-1 称为称为 a ai i 的直接前驱，的直接前驱，a ai+1i+1称为称为 a ai i 的直接后继。的直接后继。除首元素外每个元素除首元素外每个元素有且仅有有且仅有一个直接前驱；一个直接前驱；除尾元素外每个元素除尾元素外每个元素有且仅有有且仅有一个直接后继；一个直接后继；二、线性表的基本运算二、线性表的基本运算（1）初始化 initial_list（L）建空表；（2）求表长 list_length（L）（3）按序号取元素 get_element（L，i）（4）按值查找 list_locate（L，x）（5）插入 list_insert（L，i，x）在表中第i个位置上插入元素x；1 i n+1（6）删除 list_delete（L，i）删除表中第i个元素;1 i n2.2 顺序表顺序表一、线性表的顺序存储结构1、定义：假设有一个足够大的连续的存储空间，将线性表中的元素按其逻辑次序依次存储到这一存储空间中，由此方式存储的线性表称为顺序表顺序表。顺序表示意图seqlista1a2a3a4andatamaxlen-10123listlenn-12、类型描述#define maxlen 100 typedef struct elementtype datamaxlen；int listlen；seqlist；变量定义，如：seqlist L，L1；注：a：datamaxlen的下标是0到maxlen-1；b：listlen是线性表的长度，最后一个元素下标是listlen-1；3、顺序表的特点：逻辑上相邻的元素，其存储地址也相邻；即，可以随机存取元素。二、顺序表运算的实现1、初始化（建空表）：void initial_list（seqlist *L）L-listlen=0;2、求表长：int list_length（seqlist L）return L.listlen;3、按序号取元素：void get_element(seqlist L,int i,elementtype&x)if(iL.listlen)error(“序号错”);else x=L.datai-1;4、按值查找：（找到则返回其序号，否则返回0）int list_locate（seqlist L，elementtype x）int i;for(i=0;ilistlen=maxlen)error(“溢出”);else if(iL-listlen+1)error(“序号错误”);else for(j=L-listlen-1;j=i-1;j-)L-dataj+1=L.dataj;L-datai-1=x;L-listlen+;n n插入算法的时间分析插入算法的时间分析 在在i=1i=1，2 2，n+1n+1时，时，元素移动的次数分为元素移动的次数分为n n，n-1n-1，0 0。平均移动次数（等概率情况下）：平均移动次数（等概率情况下）：(0+1+(0+1+n)/(n+1)=n/2+n)/(n+1)=n/26、删除：maxlen-1 a1a2a3ai-1ai+1 dataanseqlistListlen012i-2i-1ai被删被删除除maxlen-1a1a2a3aiai+1dataanseqlistListlen012i-1i全部向前移一个位置分析：首先判断顺序表是否为空以及i的取值；可以则删除：(1)ai+1an往前移一位；(2)表长-1;void list_deletevoid list_delete（seqlist*Lseqlist*L，int iint i）int j;int j;if(L-listlenlistlen=0)error(“下溢出下溢出”););else if(iL-listlen)error(else if(iL-listlen)error(“序号错误序号错误”););else else for(j=i;jlistlen-1;j+)for(j=i;jlistlen-1;j+)L-dataj-1=L-dataj;L-dataj-1=L-dataj;L-listlen-;L-listlen-;n n删除算法的时间分析：删除算法的时间分析：在在i=1i=1，2 2，n n时，元素移动的次数分别为时，元素移动的次数分别为n-1n-1，n-2n-2，,0,0。平均移动次数：平均移动次数：(0+1+(0+1+(n-1)/n=(n-1)/2+(n-1)/n=(n-1)/2三、顺序表的应用 已知顺序表L递增有序，设计算法，在L中插入元素x，使得L依然递增有序。例例例例算法如下：void insert(seqlist*L,elementtype x)int i=L-listlen-1;if(i=maxlen-1)error(“溢出”);else while(i=0&L-dataix)L-datai+1=L-datai-;L-datai+1=x;L-listlen+;解解解解:
