数据结构线性表顺序表.ppt

第2章 线性表,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、特点：,ai-1,ai,ai+1,ai-1 称为 ai 的直接前驱，ai+1称为 ai 的直接后继。除首元素外每个元素有且仅有一个直接前驱；除尾元素外每个元素有且仅有一个直接后继；,二、线性表的基本运算,（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 n,2.2 顺序表,一、线性表的顺序存储结构,1、定义：假设有一个足够大的连续的存储空间，将线性表中的元素按其逻辑次序依次存储到这一存储空间中，由此方式存储的线性表称为顺序表。,顺序表示意图,n-1,2、类型描述#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,4、按值查找：（找到则返回其序号，否则返回0）int list_locate（seqlist L，elementtype x）int i;for(i=0;iL.listlen;i+)if(L.datai=x)return(i+1);return(0);,5、插入：,分析：首先判断顺序表是否为满，以及i的取值；若可以插入，则执行下列操作：(1)将aian后移一位；(2)插入x；(3)表长+1,void list_insert(seqlist*L,int i,elementtype x)int j;if(L-listlen=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+;,插入算法的时间分析 在i=1，2，n+1时，元素移动的次数分为n，n-1，0。平均移动次数（等概率情况下）：(0+1+n)/(n+1)=n/2,6、删除：,分析：首先判断顺序表是否为空以及i的取值；可以则删除：(1)ai+1an往前移一位；(2)表长-1;,void list_delete（seqlist*L，int i）int j;if(L-listlenL-listlen)error(“序号错误”);else for(j=i;jlistlen-1;j+)L-dataj-1=L-dataj;L-listlen-;,删除算法的时间分析：在i=1，2，n时，元素移动的次数分别为n-1，n-2，,0。平均移动次数：(0+1+(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,解:,The End,