文档介绍：第二章线性表
线性表
顺序表
链表
顺序表与链表的比较
线性表
定义: n(0)个数据元素的有限序列,记作(a1, …ai-1, ai, ai+1,…, an)
其中,ai 是表中数据元素,n 是表长度。
特点:
同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。
顺序表
定义:将线性表中的元素相继存放在一个连续的存储空间中。
存储结构:数组。
特点:线性表的顺序存储方式。
存取方式:顺序存取
顺序存储结构示意图
45 89 90 67 40 78
0 1 2 3 4 5
顺序表的存储方式:
LOC(a i+1) = LOC( a i )+(i-1)*l
LOC(a i) = LOC(a1)+(i-1)*l
a1 a2 … a i ……… an
1 2 … i ……… n
a a+l … a+(i-1)*l ……… a+(n-1)*l idle
顺序表(SeqList)的类型定义
#define ListSize 100 //最大允许长度
typedef int ListData;
typedef struct {
ListData * data; //存储空间基址
int length; //当前元素个数
}
顺序表基本运算
初始化
void InitList ( SeqList & L ) {
= ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( == NULL ) {
printf ( “存储分配失败!\n”);
exit (1);
}
= 0;
}
按值查找:找x在表中的位置,若查找成功,返回表项的位置,否则返回-1
int Find ( SeqList &L, ListData x ) {
int i = 0;
while ( i < && [i] != x )
i++;
if ( i < ) return i;
else return -1;
}
按值查找:判断x是否在表中
int IsIn ( SeqList &L, ListData x )
{ int i = 0, found=0;
while ( i < &&!found )
if([i] != x ) i++;
else found=1;
return found;
}
求表的长度
int Length ( SeqList & L ) {
return ;
}
提取函数:在表中提取第 i 个元素的值
ListData GetData ( SeqList &L, int i ) {
if ( i >= 0 && i < )
return [i];
else printf ( “参数 i 不合理!\n”);
}
按值查找:寻找x的后继
int Next ( SeqList &L, ListData x ) {
int i = Find(x);
if ( i >0 && i < ) return i+1;
else return -1;
}
寻找x的前驱
int Next ( SeqList &L, ListData x ) {
int i = Find(x);
if ( i >0 && i < ) return i-1;
else return -1;
}