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

第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