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

第2章线性表
线性表的定义和运算
一、线性表的定义:
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)
一、线性表的顺序存储结构
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;