第 2章 线性表线性结构
线性结构 是一个数据元素的有序（次序）集合。
它有 四个基本特征,
1．集合中必存在唯一的一个 "第一元素 "；
2．集合中必存在唯一的一个 "最后元素 "；
3．除最后元素之外，其它数据元素均有唯一的
"后继 "；
4．除第一元素之外，其它数据元素均有唯一的
"前驱 "。
第一节 线性表的类型定义
2.1.1 抽象数据类型线性表的定义
通常可以下列 " n 个数据元素的序列 "表示 线性表 (Linear_List) ( a1,a2,...,ai-1,ai,ai+1,...,an)
序列中数据元素的个数 n 定义为线性表的表长
n=0 时的线性表被称为空表
称 i 为 ai在线性表中的位序线性表的抽象数据类型的定义
ADT List {
数据对象,D＝ {ai | ai ∈ ElemSet,i=1,2,...,n,n≥0 }
数据关系,R1＝ { <ai-1,ai >| ai-1,ai∈ D,i=2,...,n }
基本操作,
{结构初始化 }
InitList( &L )
操作结果：构造一个空的线性表 L 。
{销毁结构 }
DestroyList( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L 。
{引用型操作 }
ListEmpty( L )
初始条件：线性表 L已存在。
操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。
ListLength( L )
初始条件：线性表 L 已存在。
操作结果：返回 L 中元素个数。
PriorElem( L,cur_e,&pre_e )
初始条件：线性表 L 已存在。
操作结果：若 cur_e 是 L 中的数据元素，则用
pre_e 返回它的前驱，否则操作失败,pre_e 无定义。
NextElem( L,cur_e,&next_e )
初始条件：线性表 L 已存在。
操作结果：若 cur_e 是 L 中的数据元素，则用
next_e 返回它的后继，否则操作失败,next_e 无定义。
GetElem( L,i,&e )
初始条件：线性表 L 已存在,1≤i≤LengthList(L)。
操作结果：用 e 返回 L 中第 i 个元素的值。
LocateElem( L,e,compare( ) )
初始条件：线性表 L 已存在,compare( ) 是元素判定函数。
操作结果：返回 L 中第 1个与 e 满足关系 compare( )
的元素的位序。若这样的元素不存在，则返回值为 0。
ListTraverse(L,visit( ))
初始条件：线性表 L 已存在,visit( ) 为元素的访问函数。
操作结果：依次对 L 的每个元素调用函数 visit( )。
一旦 visit( ) 失败，则操作失败。
{加工型操作 }
ClearList( &L )
初始条件：线性表 L 已存在。
操作结果：将 L 重置为空表。
PutElem( &L,i,&e )
初始条件：线性表 L已存在,1≤i≤LengthList(L)。
操作结果,L 中第 i 个元素赋值同 e 的值。
ListInsert( &L,i,e )
初始条件：线性表 L 已存在,1≤i≤LengthList(L)+1。
操作结果：在 L 的第 i 个元素 之前 插入新的元素 e，
L 的长度增 1。
ListDelete( &L,i,&e )
初始条件：线性表 L 已存在且非空，
1≤i≤LengthList(L)。
操作结果：删除 L 的第 i 个元素，并用 e 返回其值，
L 的长度减 1。
} ADT List
2.1.2 线性表类型的应用
例 1 已知集合 A 和 B，求两个集合的并集，使 A
＝ A∪ B，且 B 不再单独存在。
分析,以线性表 LA 和 LB 分别表示集合 A 和 B，
对集合 B 中的所有元素一个一个地检查，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。
具体操作步骤为,
1．从线性表 LB 中取出一个数据元素；
2．依值在线性表 LA 中进行查询；
3．若不存在，则将它插入到 LA 中。
重复上述三步直至 LB 为空表止。
对应的线性表基本操作：
1,ListDelete( LB,1,e );
2,LocateElem( LA,e,equal() );
3,ListInsert( LA,n+1,e )
void union(List &LA,List &LB)
{
La_len = ListLength(LA);// 求得线性表 LA 的长度
while (!ListEmpty(LB)) // 依次处理 LB 中元素直至 LB
为空表止
{
// 从 LB 中删除第 1个数据元素并赋给 e
ListDelete(LB,1,e);
// 当 LA中不存在和 e 值相同的数据元素时进行插入
if (!LocateElem(LA,e,equal( ))
ListInsert(LA,++La_len,e);
}
DestroyList(LB); // 销毁线性表 LB
} // union
例 2 已知一个“非纯集合” B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元素。
分析,将每个从 B 中取出的元素和已经加入到集合 A 中的元素相比较。
void purge(List &LA,List LB)
{ // 构造线性表 LA，使其只包含 LB中所有值不相同的数据元素,算法不改变线性表 LB
InitList(LA); // 创建一个空的线性表 LA
La_len = 0;
Lb_len = ListLength(LB); // 求线性表 LB 的长度
for (i = 1; i <= Lb_len; i++)// 处理 LB 中每个元素
{
GetElem(LB,i,e); // 取 LB中第 i 个数据赋给 e
// 当 LA 中没有和 e 值相同的数据元素时进行插入 if (!LocateElem( LA,e,equal( ) )
ListInsert( LA,++La_len,e );
} // for
} // purge
例 3 判别两个集合是否相等。
分析,首先判别两者的表长是否相等；在表长相等的前提下，对于一个表中的所有元素，是否都能在另一个表中找到和它相等的元素,
如果 "集合 "中的元素 不能保证都相异,还应反过来判别 LB 中每个元素都能在 LA 中找到相同者。
2.2 线性表的顺序存储结构
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。
L为每个数据元素所占据的存储单元数目。
位置的计算公式为：
LOC(ai+1)=LOC(a1)+(i-
1)*L
存储地址 内存单元
...
d a
1
d+ L a
2
d+ 2L a
3
...
d+ (i -1)L a
i
...
d+ (n-1 )L a
n
...,..
顺序存储结构的特点
（ 1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致
（ 2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。
#define LIST_MAX_LENGTH 100 //
线性表的最大长度
typedef struct
{
EntryType *item; //指向存放线性表中数据元素的基地
int length; //线性表的当前长度
}SQ_LIST；
典型操作的算法实现
1,初始化线性表 L
int InitList(SQ_LIST &L)
{
L->item=(EntryType*)malloc
(LIST_MAX_LENGTH *sizeof(EntryType)); //分配空间
if (L->item==NULL) return ERROR; //若分配空间不成功,返回 ERROR
L->length=0; //将当前线性表长度置 0
return OK; //成功返回 OK
}
2,销毁线性表 L
void DestroyList(SQ_LIST &L)
{
if (L->item) free(L->item); //释放线性表占据的所有存储空间
}
3,清空线性表 L
void ClearList(SQ_LIST &L)
{
L->length=0; //将线性表的长度置为 0
}
4,求线性表 L的长度
int GetLength(SQ_LIST L)
{
return (L.length);
}
5,判断线性表 L是否为空
int IsEmpty(SQ_LIST L)
{
if (L.length==0) return TRUE;
else return FALSE;
}
6,获取线性表 L中的某个数据元素的内容
int GetElem(SQ_LIST L,int i,EntryType
&e)
{
if (i<1||i>L.length) return ERROR; //判断 i值是否合理,若不合理,返回 ERROR
e=L.item[i-1]; //数组中第 i-1的单元存储着线性表中第 i个数据元素的内容
return OK;
}
7,在线性表 L中检索值为 e的数据元素
int LocateELem(SQ_LIST L,EntryType e)
{
for (i=0;i< L.length;i++)
if (L.item[i]==e) return i+1;
return 0;
}
8,在线性表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(SQ_LIST &L,int i,EntryType e)
{ //检查是否有剩余空间
if (L->length==LIST_MAX_LENGTH) return ERROR;
if (i<1||i>L->length+1) return ERROR; //i值是否合理
for (j=L->length-1;j>=i-1;i++) //将线性表第 i个元素之后的所有元素向后移动
L.->item[j+1]=L->item[j];
L->item[i-1]=e; //将新元素的内容放入线性表的第 i个位置
L->length++;
return OK;
}
9,将线性表 L中第 i个数据元素删除
int ListDelete(SQ_LIST &L,int i,EntryType &e)
{
if (IsEmpty(L)) return ERROR; //检测线性表是否为空
if (i<1||i>L->length) return ERROR; //检查 i
值是否合理
e=L->item[i-1]; //将欲删除的数据元素内容保留在 e所指示的存储单元中
for (j=i;j<=L->length-1;j++) //将线性表第 i+1
个元素之后的所有元素向前移动
L->item[j-1]=L->item[j];
L->length--;
return OK;
}
2.3 线性表的链式存储结构
线性表顺序存储结构的特点,
它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，
从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
l 在做插入或删除元素的操作时，会产生大量的数据元素移动；
l 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
l 线性表的容量难以扩充。
链式存储结构 是指用一组任意的存储单元
（可以连续，也可以不连续）存储线性表中的数据元素。
为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，
还要附加一个表示它的直接后继元素存储位置的信息。
假设有一个线性表（ a,b,c,d）
存储地址 内容 直接后继存储地址
100 b 120
...,..,..
120 c 160
...,..,.
144 a 100
...,..,..
160 d N U L L
...,..,..
首元素位置术语
每个数据元素的两部分信息组合在一起被称为 结点
其中表示数据元素内容的部分被称为 数据域 （ data）
表示直接后继元素存储地址的部分被称为指针 或 指针域 （ next）
单链表简化的图形描述形式
head d ^cba
head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点
由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值 NULL。
NULL值在图示中常用（ ^）符号表示。
head d ^cba
带头结点的单链表
为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。
head d ^cba
链式存储结构的特点
（ 1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致
（ 2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。
链式存储结构的类型定义
typedef strcut node
{ //结点类型
EntryType item;
struct node *next;
}NODE;
typedef struct
{ //链表类型
NODE *head;
}LINK_LIST;
典型操作的算法实现
1,初始化链表 L
int InitList(LINK_LIST &L)
{
L->head=(*NODE)malloc(sizeof(NODE));
//为 头结点 分配存储单元
if (L->head)
{L->head->next=NULL;
return OK;}
else
return ERROR ;
}
L->head d ^cba
2,销毁链表 L
void DestoryList(LINK_LIST &L)
{
NODE *p;
while (L->head)
{//依次删除链表中的所有结点
p=L->head;
L->head=L->head->next;
free(p);
}
}
L->head d ^cba
3,清空链表 L
void ClearList(LINK_LIST &L)
{
NODE *p;
while (L->head->next)
{
p=L->head->next; //p指向链表中头结点后面的第一个结点
L->head->next=p->next; //删除 p结点
free(p); //释放 p结点占据的存储空间
}
}
L->head d ^cba
4,求链表 L的长度
int ListLength(LINK_LIST L)
{
NODE *p;
int len;
for(p=L.head,len=0;p->next==NULL;
p=p->next,len++);
return(len);
}
L->head d ^cba
5,判链表 L空否。
int IsEmpty(LINK_LIST L)
{
if (L.head->next==NULL) return TRUE;
else return FALSE;
}
L->head d ^cba
6,通过 e返回链表 L中第 i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType &e)
{
NODE *p;
int j;
if (i<1||i>ListLength(L)) exit ERROR;
//检测 i值的合理性
for (p=L.head,j=0; j!=i;p=p->next,j++);
//找到第 i个结点
e=p->item;
//将第 i个结点的内容赋给 e指针所指向的存储单元中
}
L->head d ^cba
7,在链表 L中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST
L,EntryType e)
{
NODE *p;
for (p=L.head->next;p&&p->item!=e;p=p-
>next);
//寻找满足条件的结点
return(p);
}
L->head d ^cba
8,返回链表 L中结点 e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE * e)
{
NODE *p;
if (L.head->next==e) return NULL;
//检测第一个结点
for (p=L.head;p->next&&p->next!=e;p=p-
>next);
if (p->next==e) return p;
esle return NULL;
}
L->head d ^cba
9,返回链表 L中结点 e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE * e)
{
NODE *p;
for(p=L.head->next;p&&p!=e;p=p->next);
if (p) p=p->next;
return p;
}
L->head d ^cba
10,在链表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(LINK_LIST &L,int i,EntryType e)
{
NODE *p,*s;
int j;
if (i<1||i>ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s->next=p->next; p->next=s; //将 s结点插入
return OK;
}
L->head d ^cba
11,将链表 L中第 i个数据元素删除,并将其内容保存在 e中 。
int ListDelete(LINK_LIST &L,int i,EntryType &e)
{
NODE *p*s;
int j;
if (i<1||i>ListLength(L)) return ERROR;
//检查 i值的合理性
for(p=L->head,j=0;j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s=p->next; //用 s指向将要删除的结点
e=s->item;
p->next=s->next; //删除 s指针所指向的结点
free(s);
return OK;
}
L->head d ^cba
线性结构 是一个数据元素的有序（次序）集合。
它有 四个基本特征,
1．集合中必存在唯一的一个 "第一元素 "；
2．集合中必存在唯一的一个 "最后元素 "；
3．除最后元素之外，其它数据元素均有唯一的
"后继 "；
4．除第一元素之外，其它数据元素均有唯一的
"前驱 "。
第一节 线性表的类型定义
2.1.1 抽象数据类型线性表的定义
通常可以下列 " n 个数据元素的序列 "表示 线性表 (Linear_List) ( a1,a2,...,ai-1,ai,ai+1,...,an)
序列中数据元素的个数 n 定义为线性表的表长
n=0 时的线性表被称为空表
称 i 为 ai在线性表中的位序线性表的抽象数据类型的定义
ADT List {
数据对象,D＝ {ai | ai ∈ ElemSet,i=1,2,...,n,n≥0 }
数据关系,R1＝ { <ai-1,ai >| ai-1,ai∈ D,i=2,...,n }
基本操作,
{结构初始化 }
InitList( &L )
操作结果：构造一个空的线性表 L 。
{销毁结构 }
DestroyList( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L 。
{引用型操作 }
ListEmpty( L )
初始条件：线性表 L已存在。
操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。
ListLength( L )
初始条件：线性表 L 已存在。
操作结果：返回 L 中元素个数。
PriorElem( L,cur_e,&pre_e )
初始条件：线性表 L 已存在。
操作结果：若 cur_e 是 L 中的数据元素，则用
pre_e 返回它的前驱，否则操作失败,pre_e 无定义。
NextElem( L,cur_e,&next_e )
初始条件：线性表 L 已存在。
操作结果：若 cur_e 是 L 中的数据元素，则用
next_e 返回它的后继，否则操作失败,next_e 无定义。
GetElem( L,i,&e )
初始条件：线性表 L 已存在,1≤i≤LengthList(L)。
操作结果：用 e 返回 L 中第 i 个元素的值。
LocateElem( L,e,compare( ) )
初始条件：线性表 L 已存在,compare( ) 是元素判定函数。
操作结果：返回 L 中第 1个与 e 满足关系 compare( )
的元素的位序。若这样的元素不存在，则返回值为 0。
ListTraverse(L,visit( ))
初始条件：线性表 L 已存在,visit( ) 为元素的访问函数。
操作结果：依次对 L 的每个元素调用函数 visit( )。
一旦 visit( ) 失败，则操作失败。
{加工型操作 }
ClearList( &L )
初始条件：线性表 L 已存在。
操作结果：将 L 重置为空表。
PutElem( &L,i,&e )
初始条件：线性表 L已存在,1≤i≤LengthList(L)。
操作结果,L 中第 i 个元素赋值同 e 的值。
ListInsert( &L,i,e )
初始条件：线性表 L 已存在,1≤i≤LengthList(L)+1。
操作结果：在 L 的第 i 个元素 之前 插入新的元素 e，
L 的长度增 1。
ListDelete( &L,i,&e )
初始条件：线性表 L 已存在且非空，
1≤i≤LengthList(L)。
操作结果：删除 L 的第 i 个元素，并用 e 返回其值，
L 的长度减 1。
} ADT List
2.1.2 线性表类型的应用
例 1 已知集合 A 和 B，求两个集合的并集，使 A
＝ A∪ B，且 B 不再单独存在。
分析,以线性表 LA 和 LB 分别表示集合 A 和 B，
对集合 B 中的所有元素一个一个地检查，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。
具体操作步骤为,
1．从线性表 LB 中取出一个数据元素；
2．依值在线性表 LA 中进行查询；
3．若不存在，则将它插入到 LA 中。
重复上述三步直至 LB 为空表止。
对应的线性表基本操作：
1,ListDelete( LB,1,e );
2,LocateElem( LA,e,equal() );
3,ListInsert( LA,n+1,e )
void union(List &LA,List &LB)
{
La_len = ListLength(LA);// 求得线性表 LA 的长度
while (!ListEmpty(LB)) // 依次处理 LB 中元素直至 LB
为空表止
{
// 从 LB 中删除第 1个数据元素并赋给 e
ListDelete(LB,1,e);
// 当 LA中不存在和 e 值相同的数据元素时进行插入
if (!LocateElem(LA,e,equal( ))
ListInsert(LA,++La_len,e);
}
DestroyList(LB); // 销毁线性表 LB
} // union
例 2 已知一个“非纯集合” B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元素。
分析,将每个从 B 中取出的元素和已经加入到集合 A 中的元素相比较。
void purge(List &LA,List LB)
{ // 构造线性表 LA，使其只包含 LB中所有值不相同的数据元素,算法不改变线性表 LB
InitList(LA); // 创建一个空的线性表 LA
La_len = 0;
Lb_len = ListLength(LB); // 求线性表 LB 的长度
for (i = 1; i <= Lb_len; i++)// 处理 LB 中每个元素
{
GetElem(LB,i,e); // 取 LB中第 i 个数据赋给 e
// 当 LA 中没有和 e 值相同的数据元素时进行插入 if (!LocateElem( LA,e,equal( ) )
ListInsert( LA,++La_len,e );
} // for
} // purge
例 3 判别两个集合是否相等。
分析,首先判别两者的表长是否相等；在表长相等的前提下，对于一个表中的所有元素，是否都能在另一个表中找到和它相等的元素,
如果 "集合 "中的元素 不能保证都相异,还应反过来判别 LB 中每个元素都能在 LA 中找到相同者。
2.2 线性表的顺序存储结构
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。
L为每个数据元素所占据的存储单元数目。
位置的计算公式为：
LOC(ai+1)=LOC(a1)+(i-
1)*L
存储地址 内存单元
...
d a
1
d+ L a
2
d+ 2L a
3
...
d+ (i -1)L a
i
...
d+ (n-1 )L a
n
...,..
顺序存储结构的特点
（ 1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致
（ 2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。
#define LIST_MAX_LENGTH 100 //
线性表的最大长度
typedef struct
{
EntryType *item; //指向存放线性表中数据元素的基地
int length; //线性表的当前长度
}SQ_LIST；
典型操作的算法实现
1,初始化线性表 L
int InitList(SQ_LIST &L)
{
L->item=(EntryType*)malloc
(LIST_MAX_LENGTH *sizeof(EntryType)); //分配空间
if (L->item==NULL) return ERROR; //若分配空间不成功,返回 ERROR
L->length=0; //将当前线性表长度置 0
return OK; //成功返回 OK
}
2,销毁线性表 L
void DestroyList(SQ_LIST &L)
{
if (L->item) free(L->item); //释放线性表占据的所有存储空间
}
3,清空线性表 L
void ClearList(SQ_LIST &L)
{
L->length=0; //将线性表的长度置为 0
}
4,求线性表 L的长度
int GetLength(SQ_LIST L)
{
return (L.length);
}
5,判断线性表 L是否为空
int IsEmpty(SQ_LIST L)
{
if (L.length==0) return TRUE;
else return FALSE;
}
6,获取线性表 L中的某个数据元素的内容
int GetElem(SQ_LIST L,int i,EntryType
&e)
{
if (i<1||i>L.length) return ERROR; //判断 i值是否合理,若不合理,返回 ERROR
e=L.item[i-1]; //数组中第 i-1的单元存储着线性表中第 i个数据元素的内容
return OK;
}
7,在线性表 L中检索值为 e的数据元素
int LocateELem(SQ_LIST L,EntryType e)
{
for (i=0;i< L.length;i++)
if (L.item[i]==e) return i+1;
return 0;
}
8,在线性表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(SQ_LIST &L,int i,EntryType e)
{ //检查是否有剩余空间
if (L->length==LIST_MAX_LENGTH) return ERROR;
if (i<1||i>L->length+1) return ERROR; //i值是否合理
for (j=L->length-1;j>=i-1;i++) //将线性表第 i个元素之后的所有元素向后移动
L.->item[j+1]=L->item[j];
L->item[i-1]=e; //将新元素的内容放入线性表的第 i个位置
L->length++;
return OK;
}
9,将线性表 L中第 i个数据元素删除
int ListDelete(SQ_LIST &L,int i,EntryType &e)
{
if (IsEmpty(L)) return ERROR; //检测线性表是否为空
if (i<1||i>L->length) return ERROR; //检查 i
值是否合理
e=L->item[i-1]; //将欲删除的数据元素内容保留在 e所指示的存储单元中
for (j=i;j<=L->length-1;j++) //将线性表第 i+1
个元素之后的所有元素向前移动
L->item[j-1]=L->item[j];
L->length--;
return OK;
}
2.3 线性表的链式存储结构
线性表顺序存储结构的特点,
它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，
从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
l 在做插入或删除元素的操作时，会产生大量的数据元素移动；
l 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
l 线性表的容量难以扩充。
链式存储结构 是指用一组任意的存储单元
（可以连续，也可以不连续）存储线性表中的数据元素。
为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，
还要附加一个表示它的直接后继元素存储位置的信息。
假设有一个线性表（ a,b,c,d）
存储地址 内容 直接后继存储地址
100 b 120
...,..,..
120 c 160
...,..,.
144 a 100
...,..,..
160 d N U L L
...,..,..
首元素位置术语
每个数据元素的两部分信息组合在一起被称为 结点
其中表示数据元素内容的部分被称为 数据域 （ data）
表示直接后继元素存储地址的部分被称为指针 或 指针域 （ next）
单链表简化的图形描述形式
head d ^cba
head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点
由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值 NULL。
NULL值在图示中常用（ ^）符号表示。
head d ^cba
带头结点的单链表
为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。
head d ^cba
链式存储结构的特点
（ 1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致
（ 2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。
链式存储结构的类型定义
typedef strcut node
{ //结点类型
EntryType item;
struct node *next;
}NODE;
typedef struct
{ //链表类型
NODE *head;
}LINK_LIST;
典型操作的算法实现
1,初始化链表 L
int InitList(LINK_LIST &L)
{
L->head=(*NODE)malloc(sizeof(NODE));
//为 头结点 分配存储单元
if (L->head)
{L->head->next=NULL;
return OK;}
else
return ERROR ;
}
L->head d ^cba
2,销毁链表 L
void DestoryList(LINK_LIST &L)
{
NODE *p;
while (L->head)
{//依次删除链表中的所有结点
p=L->head;
L->head=L->head->next;
free(p);
}
}
L->head d ^cba
3,清空链表 L
void ClearList(LINK_LIST &L)
{
NODE *p;
while (L->head->next)
{
p=L->head->next; //p指向链表中头结点后面的第一个结点
L->head->next=p->next; //删除 p结点
free(p); //释放 p结点占据的存储空间
}
}
L->head d ^cba
4,求链表 L的长度
int ListLength(LINK_LIST L)
{
NODE *p;
int len;
for(p=L.head,len=0;p->next==NULL;
p=p->next,len++);
return(len);
}
L->head d ^cba
5,判链表 L空否。
int IsEmpty(LINK_LIST L)
{
if (L.head->next==NULL) return TRUE;
else return FALSE;
}
L->head d ^cba
6,通过 e返回链表 L中第 i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType &e)
{
NODE *p;
int j;
if (i<1||i>ListLength(L)) exit ERROR;
//检测 i值的合理性
for (p=L.head,j=0; j!=i;p=p->next,j++);
//找到第 i个结点
e=p->item;
//将第 i个结点的内容赋给 e指针所指向的存储单元中
}
L->head d ^cba
7,在链表 L中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST
L,EntryType e)
{
NODE *p;
for (p=L.head->next;p&&p->item!=e;p=p-
>next);
//寻找满足条件的结点
return(p);
}
L->head d ^cba
8,返回链表 L中结点 e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE * e)
{
NODE *p;
if (L.head->next==e) return NULL;
//检测第一个结点
for (p=L.head;p->next&&p->next!=e;p=p-
>next);
if (p->next==e) return p;
esle return NULL;
}
L->head d ^cba
9,返回链表 L中结点 e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE * e)
{
NODE *p;
for(p=L.head->next;p&&p!=e;p=p->next);
if (p) p=p->next;
return p;
}
L->head d ^cba
10,在链表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(LINK_LIST &L,int i,EntryType e)
{
NODE *p,*s;
int j;
if (i<1||i>ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s->next=p->next; p->next=s; //将 s结点插入
return OK;
}
L->head d ^cba
11,将链表 L中第 i个数据元素删除,并将其内容保存在 e中 。
int ListDelete(LINK_LIST &L,int i,EntryType &e)
{
NODE *p*s;
int j;
if (i<1||i>ListLength(L)) return ERROR;
//检查 i值的合理性
for(p=L->head,j=0;j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s=p->next; //用 s指向将要删除的结点
e=s->item;
p->next=s->next; //删除 s指针所指向的结点
free(s);
return OK;
}
L->head d ^cba
