第2章 数据结构-线性表_1_顺序表.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、定义： 假设有一个足够大的连续的存储空间，将线性表中的元素按其逻辑次序依次存储到这一存储空间中，由此方式存储的线性表称为顺序表。 顺序表示意图 seqlist a1 a2 a3 a4 … an data maxlen-1 0 1 2 3 listlen n-1 2、类型描述 #define maxlen 100 typedef struct { elementtype data[maxlen]； int listlen； }seqlist； 变量定义，如：seqlist L，L1； 注：a：data[maxlen]的下标是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 (i1||iL.listlen) error(“序号错”); else x=L.data[i-1]; } 4、按值查找： （找到则返回其序号，否则返回0） int list_locate（seqlist L，elementtype x） { int i; for(i=0;iL.listlen;i++) if (L.data[i]==x) return(i+1); return(0); } 5、插入： … a1 a2 a3 … x ai data an seqlist Listlen maxlen-1 0 1 2 i-1 i an a1 a2 a3 … ai … data seqlist Listlen maxlen-1 0 1 2 i-1 x 全部向后移一个位置 分析： 首先判断顺序表是否为满，以及i的取值； 若可以插入，则执行下列操作： (1)将ai~an后移一位； (2)插入x； (3)表长+1 void list_insert( seqlist *L,int i,elementtype x ) { int j; if (L-listlen==maxlen) error(“溢出”); else if(i1||iL-listlen+1) error(“序号错误”); else { for(j=L-listlen-1;j=i-1;j--)